数据结构中有哪些基本算法_CMS教程

数据结构中最基本的算法有：查找、排序、快速排序，堆排序，归并排序，，二分搜索算法

等等。

1、用的最多也是最简单的数据结构是线性表。

2、有前途的又难数据结构是图。

3、常用的80％算法是排序和查找。

排序常用的算法有：插入算法（直接插入算法、折半插入算法、希尔算法）、选择算法（简单选择算法、堆排序算法）、快速算法(冒泡排序、快速排序算法)

以下程序给出了各种算法的实现，其接口为void sort(int array,int len),每个文件实现一个算法，最后和mainc文件编译实现。

1、直接插入算法：//direct_insert_sortc

2、折半插入排序：//binary_insert_sortc

3、希尔排序：//shell_sortc

4、简单选择排序：//simple_select_sort

按照程序设计的自顶向下，逐步求精的机构化程序设计思想来完成这个任务。

①大概的顶层框架是：随机数产生模块，文件保存模块，排序以及统计排序过程信息的模块。

②分别设计出随机数产生算法，三种排序算法。

③按照逻辑的顺序进行组装，并给出必要的过程信息。

算法的设计实现以及程序运行结果：

int a[10] = {6,8,7,9,0,1,3,2,4,5};

int b;

int count = 0;

b = calloc(410,1);

while(count < 10)

{

int c = INT_MAX;

for(int i=1;i<10;i++)

{

if(a[i] < c)

{

c = a[i];

}

if(c == count)break;

}

b[count] = c;

count++;

}

结果：b = {0,1,2,3,4,5,6,7,8,9}

#include "stdioh"//标准io头文件

#include "stdlibh"//库文件

#include "timeh"//时间系头文件

#define N0 100000 //定义常量

typedef int keytype; //类型命名

typedef struct node //定义结构体

{ keytype key; //只是类型命名成keytype，其实就是int的

}Etp;//结构体类型叫做Etp

Etp R[N0+1]; // R[1]R[n] //定义数组

int n=50, count;//全局变量

void readData( Etp R[], int n)//读数据的函数

{ int i;

count=0;

srand( time( NULL ));//初始化时间种子

for( i=1; i<=n; i++) //对数组初始化

R[i]key=1000+

(int)((99990-1000)rand()/RAND_MAX); // 0RAND_MAX

}

void printData( Etp R[], int n )//打印显示数据的函数

{ int i;

for( i=1; i<=n; i++)

printf("%8d%s", //格式化显示数组的数据

R[i]key, i%5==0"\n":"");

printf("\ncount=%d\n", count);

}

void bubberSort( Etp R[], int n )//冒泡排序的函数

{ int i,j;//（这个函数块就是冒泡排序的算法程序）

bool swap;

for( i=1; i<=n-1; i++)

{ swap=false;

for( j=1; j<=n-i; j++)

if( count++,R[j]key>R[j+1]key )

{ R[0]=R[j];

R[j]=R[j+1];

R[j+1]=R[0];

swap=true;

}

if( !swap ) break;

}

void bubberSort1( Etp R[], int n )//这个也是另一个冒泡排序的函数

{ int j;//跟上面不同的是这个算法用的是递归的方式，上面的是非递归的

for( j=1; j<=n-1; j++)

if( count++,R[j]key>R[j+1]key )

{ R[0]=R[j];

R[j]=R[j+1];//________;//就是两个变量交换值

R[j+1]=R[0];

}

if( n>1 ) bubberSort1( R, n-1); //___________;//递归调用

}

void selectSort( Etp R[], int n )//这个是选择排序

{ int i,j,k;//（这个函数块就是选择排序的算法程序）

for( i=1; i<=n-1; i++)

{

k=i;

for( j=i+1; j<=n; j++)

if( count++,R[j]key<R[k]key ) k=j;

if( k!=i )

{ R[0]=R[i];

R[i]=R[k];

R[k]=R[0];

}

void insertSort( Etp R[], int n )//这个是插入排序

{ int i,j;

for( i=2; i<=n; i++)

{

R[0]=R[i];

j=i-1;

while( count++,R[j]key>R[0]key ) R[j+1]=R[j--];

R[j+1]=R[0];

count++;

}

void sift( Etp R[], int i, int m)//堆排序中的步骤

{ int k=2i;

R[0]=R[i];

while( k<=m )

{ if( count++, k+1<=m && R[k+1]key>R[k]key) k++;

if( count++,R[0]key<R[k]key ) R[i]=R[k];

else break;

i=k;

k=2i;

}

R[i]=R[0];

}

void heapSort( Etp R[], int n )//这个是堆排序

{ int j;

for( j=n/2; j>=1; j--) sift( R, j, n);

for( j=n; j>=2; j--)

{ R[0]=R[1];

R[1]=R[j];

R[j]=R[0];

sift( R, 1, j-1 );

}

int main()//主函数的进入口

{

readData( R, n );//读取数据

bubberSort1( R, n );//调用递归冒泡排序

printData( R, n);//显示数据

readData( R, n );//读取数据

selectSort( R, n );//调用选择排序

printData( R, n);//显示数据

readData( R, n );//读取数据

insertSort( R, n );//调用插入排序

printData( R, n);//显示数据

readData( R, n );//读取数据

heapSort( R, n );//调用堆排序

printData( R, n);//显示数据

return 0;

}

//诶·~注释完我总算看出来了，难道你要我解释各个排序的过程？

//那你还不如直接baidu或者看书，你要是不理解原理是不可能看懂过程的。

//注释也只是语句的解释，但是过程的含义是无法描述的

虽然算法与计算机程序密切相关，但二者也存在区别：计算机程序是算法的一个实例，是将算法通过某种计算机语言表达出来的具体形式；同一个算法可以用任何一种计算机语言来表达。

算法列表

图论

路径问题

0/1边权最短路径

BFS

非负边权最短路径（Dijkstra）

可以用Dijkstra解决问题的特征

负边权最短路径

Bellman-Ford

Bellman-Ford的Yen-氏优化

差分约束系统

Floyd

广义路径问题

传递闭包

极小极大距离 / 极大极小距离

Euler Path / Tour

圈套圈算法

混合图的 Euler Path / Tour

Hamilton Path / Tour

特殊图的Hamilton Path / Tour 构造

生成树问题

最小生成树

第k小生成树

最优比率生成树

0/1分数规划

度限制生成树

连通性问题

强大的DFS算法

无向图连通性

割点

割边

二连通分支

有向图连通性

强连通分支

2-SAT

最小点基

有向无环图

拓扑排序

有向无环图与动态规划的关系

二分图匹配问题

一般图问题与二分图问题的转换思路

最大匹配

有向图的最小路径覆盖

0 / 1矩阵的最小覆盖

完备匹配

最优匹配

稳定婚姻

网络流问题

网络流模型的简单特征和与线性规划的关系

最大流最小割定理

最大流问题

有上下界的最大流问题

循环流

最小费用最大流 / 最大费用最大流

弦图的性质和判定

组合数学

解决组合数学问题时常用的思想

逼近

递推/动态规划

概率问题

Polya定理

计算几何 / 解析几何

计算几何的核心：叉积 / 面积

解析几何的主力：复数

基本形

点

直线，线段

多边形

凸多边形 / 凸包

凸包算法的引进，卷包裹法

Graham扫描法

水平序的引进，共线凸包的补丁

完美凸包算法

数据结构中有哪些基本算法

发表评论

评论列表（0条）