4 posts tagged with "算法"

View All Tags

C++高斯列主元消去法

Ban

Ban

ChangAn University
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;
int main()
{
int i, j, k, n;
double eps, ratio, sum, max, temp;
ifstream data_in("gauss_source.txt");
ofstream data_out("gauss_result.txt");
//输入增广矩阵系数
data_in >> n; //输入方程个数
double *x = new double[n]; //动态分配存储空间（指针）
double **a = new double *[n]; //二级指针指向指针数组首地址，n 个方程，二维动态数组
for (i = 0; i < n; i++)
{
a[i] = new double[n + 1]; // 给指针数组每个元素申请空间,每个元素都是一个指针,每 个方程有 n+1 个系数(包括常数项)
}
//存储空间申请成功后，和一般二维数组操作类似
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
{
data_in >> a[i][j];
//输入系数矩阵
}
for (i = 0; i < n; i++)
{
data_in >> a[i][n]; //输入等号右端向量的各元素 a[][]为增广矩阵
}
data_in >> eps; //输入最小主元素.为了避免主元素为 0 的情况，设置 一个比较小的实数
data_in.close();
//执行高斯消去法
for (k = 0; k < (n - 1); k++) //消元
{
for (i = (k + 1); i < n; i++)
{
if (fabs(a[k][k]) < eps) //fabs(x)函数是求浮点型数 x 的绝对值
{
cout << "Start exchanging principal..." << endl;
//选择列主元
max = fabs(a[k][k]);
for (int m = k; m < n; m++)
{
if (max < fabs(a[m][k]))
{
max = fabs(a[m][k]);
}
}
//交换行
for (int m = k; m < n; m++)
{
if (max == fabs(a[m][k]))
{
for (int q = k; q < n; q++)
{
temp = a[k][q];
a[k][q] = a[m][q];
a[m][q] = temp;
}
// 交换常数部分
cout << "Exchaging const..." << endl;
temp = a[k][n];
a[k][n] = a[m][n];
a[m][n] = temp;
}
}
}
ratio = a[i][k] / a[k][k];
for (j = (k + 1); j < (n + 1); j++)
{
a[i][j] -= ratio * a[k][j];
}
a[i][k] = 0;
}
}
x[n - 1] = a[n - 1][n] / a[n - 1][n - 1]; //回代
for (i = (n - 2); i >= 0; --i)
{
sum = 0.0;
for (j = (i + 1); j < n; j++)
{
sum += a[i][j] * x[j];
}
x[i] = (a[i][n] - sum) / a[i][i];
} //结果输出
for (i = 0; i < n; i++)
{
data_out << "\nx[" << i << "]=" << x[i] << endl;
}
data_out.close();
//释放堆内存
delete[] x;
for (i = 0; i < n; i++)
{
delete[] a[i];
}
delete[] a;
cout << "Calculate finished!, please check the output file" << endl;
/*
eps = 0.0001
int put matrix:
0.00001 2.000 3.000 1.000
-1.000 3.712 4.623 2.000
-2.000 1.072 5.643 3.000
expect result:
x[0] = -0.4911
x[1] = -0.0509
x[2] = 0.3673
output:
x[0] = -0.491052
x[1] = -0.0508876
x[2] = 0.36726
*/
system("pause");
return 0;
}

LeetCode树与图

Ban

Ban

ChangAn University

二叉树

二叉树基础

二叉树前序遍历

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/*
前序遍历
*/
void preorder_print(TreeNode *node, int layer)
{
if (!node)
{
return;
}
for (int i = 0; i < layer; i++)
{
printf("-----");
}
printf("[%d]\n", node->val);
preorder_print(node->left, layer + 1);
preorder_print(node->right, layer + 1);
}
int main()
{
TreeNode a(1);
TreeNode b(2);
TreeNode c(5);
TreeNode d(3);
TreeNode e(4);
TreeNode f(6);
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.right = &f;
preorder_print(&a, 0);
return 0;
}
//java code
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
class Test {
public static void preorderPrint(TreeNode node, int layer) {
if (node == null) {
return;
}
for (int i = 0; i < layer; i++) {
System.out.print("-----");
}
System.out.format("[%d]\n", node.val);
preorderPrint(node.left, ++layer);
preorderPrint(node.right, ++layer);
}
public static void main(String[] args) {
TreeNode a = new TreeNode(1);
TreeNode b = new TreeNode(2);
TreeNode c = new TreeNode(5);
TreeNode d = new TreeNode(3);
TreeNode e = new TreeNode(4);
TreeNode f = new TreeNode(6);
a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;
preorderPrint(a, 0);
}
}
//伪代码
//中序
preOrderPrint(node.left, ++layer);
System.out.format("[%d]\n", node.val);
preOrderPrint(node.right, ++layer);
//后序
preOrderPrint(node.left, ++layer);
preOrderPrint(node.right, ++layer);
System.out.format("[%d]\n", node.val);

LeetCode栈、队列与堆

Ban

Ban

ChangAn University

  • 225:使用队列实现栈(Easy)（栈、队列）
  • 使用栈实现队列(East)(栈、队列)
  • 包含min函数的栈(Easy)(栈)
  • 合法的出栈序列(Medium)（栈、队列）
  • 简单的计算器(hard)（栈）
  • 数组中第K大的数(Easy)（堆）
  • 寻找中位数(hard)（堆）

LeetCode链表

Ban

Ban

ChangAn University

链表

链表基础

/*
链表基础
*/
struct ListNode
{
int value;
ListNode *next;
};
int main()
{
ListNode a;
ListNode b;
ListNode c;
ListNode d;
ListNode e;
a.value = 10;
b.value = 20;
c.value = 30;
d.value = 40;
e.value = 50;
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = NULL;
ListNode *head = &a;
while (head)
{
printf("%d", head->value);
head = head->next;
}
system("pause");
return 0;
}