#include"stdio.h"
#include"stdlib.h"
#define Max 100 //假设文件长度 typedef struct{ //定义记录类型 int key;
}RecType;
typedef RecType SeqList[Max+1];
int n;
//直接插入排序法
void InsertSort(SeqList R)
{
int i,j;
for(i=2;i<=n;i++)
if(R[i].key<R[i-1].key){
R[0]=R[i];j=i-1;
do {
R[j+1]=R[j]; j--;
}while(R[0].key<R[j].key);
R[j+1]=R[0]; }
}
typedef enum{FALSE,TRUE} Boolean;
//冒泡排序
void BubbleSort(SeqList R) { int i,j; Boolean exchange; for(i=1;i<n;i++) {
exchange=FALSE;
for(j=n-1;j>=i;j--)
if(R[j+1].key<R[j].key){ R[0]=R[j+1]; R[j+1]=R[j]; R[j]=R[0];
exchange=TRUE; }
if(! exchange)
return;
}
}
//一次划分函数
int Partition(SeqList R,int i,int j)
{
RecType pivot=R[i];
while(i<j) {
while(i<j &&R[j].key>=pivot.key) j--;
if(i<j)
R[i++]=R[j];
while(i<j &&R[i].key<=pivot.key) i++;
if(i<j)
R[j--]=R[i];
}
R[i]=pivot;
return i;
}
//快速排序
void QuickSort(SeqList R,int low,int high)
{
int pivotpos;
if(low<high) {
pivotpos=Partition(R,low,high);
QuickSort(R,low,pivotpos-1); QuickSort(R,pivotpos+1,high); }
}
//直接选择排序
void SelectSort(SeqList R)
{
int i,j,k;
for(i=1;i<n;i++){
k=i;
for(j=i+1;j<=n;j++)
if(R[j].key<R[k].key)
k=j;
if(k!=i) {
R[0]=R[i];R[i]=R[k];R[k]=R[0];
}
}
}
//大根堆调整函数
void Heapify(SeqList R,int low,int high)
{ // 将R[low..high]调整为大根堆，除R[low]外，其余结点均满足堆性质
int large;
RecType temp=R[low];
for(large=2*low; large<=high;large*=2){
//若large>high,表示R[low]是叶子，调整结束;否则令large指向R[low]的左孩子
if(large<high && R[large].key<R[large+1].key)
large++;
//现在R[large]是调整结点R[low]的左右孩子结点中关键字较大者
if(temp.key>=R[large].key) //temp始终对应R[low]
break;
R[low]=R[large];
low=large;
}
R[low]=temp;
}
//构造大根堆
void BuildHeap(SeqList R)
{ //将初始文件R[1..n]构造为堆
int i;
for(i=n/2;i>0;i--)
Heapify(R,i,n);
}
//堆排序
void HeapSort(SeqList R)
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i;
BuildHeap(R);
for(i=n;i>1;i--){
R[0]=R[1]; R[1]=R[i];R[i]=R[0];
Heapify(R,1,i-1);
}
}
//将两个有序的子序列R[low..m]和R[m+1..high]归并成有序的序列R[low..high] void Merge(SeqList R,int low,int m,int high)
{
int i=low,j=m+1,p=0;
RecType *R1;
R1=(RecType *)malloc((high-low+1)*sizeof(RecType));
while(i<=m && j<=high) //两个子序列非空时取其小者输出到R1[p]上 R1[p++]=(R[i].key<=R[j].key)? R[i++]:R[j++];
while(i<=m) //若第一个子序列非空，则复制剩余记录到R1
R1[p++]=R[i++];
while(j<=high) //若第二个子序列非空，则复制剩余记录到R1中
R1[p++]=R[j++];
for(p=0,i=low;i<=high;p++,i++)
R[i]=R1[p];
}
//对R[1..n]做一趟归并排序
void MergePass(SeqList R,int length)
{
int i;
for(i=1;i+2*length-1<=n;i=i+2*length)
Merge(R,i,i+length-1,i+2*length-1);
if(i+length-1<n) //尚有一个子序列，其中后一个长度小于length Merge(R,i,i+length-1,n);
//注意：若i≤n且i+length-1≥n时，则剩余一个子序列轮空，无须归并 }
//自底向上对R[1..n]做二路归并排序
void MergeSort(SeqList R)
{
int length;
for(length=1;length<n;length*=2)
MergePass(R,length);
}
//输入顺序表
void input_int(SeqList R)
{
int i;
printf("Please input num(int):");
scanf("%d",&n);
printf("Plase input %d integer:",n);
for(i=1;i<=n;i++)
scanf("%d",&R[i].key);
}
//输出顺序表
void output_int(SeqList R)
{
int i;
for(i=1;i<=n;i++)
printf("%4d",R[i].key);
}
//主函数
void main()
{
int i;
SeqList R;
input_int(R);
printf("\t******** Select **********\n");
printf("\t1: Insert Sort\n");
printf("\t2: Bubble Sort\n");
printf("\t3: Quick Sort\n");
printf("\t4: Straight Selection Sort\n");
printf("\t5: Heap Sort\n");
printf("\t6: Merge Sort\n");
printf("\t7: Exit\n");
printf("\t***************************\n");
scanf("%d",&i);
switch (i){
case 1: InsertSort(R); break; // 直接插入排序法
case 2: BubbleSort(R); break; //冒泡排序
case 3: QuickSort(R,1,n); break; //快速排序
case 4: SelectSort(R); break; //直接选择排序
case 5: HeapSort(R); break; //堆排序
case 6: MergeSort(R); break; //自底向上对R[1..n]做二路归并排序 case 7: exit(0);
}
printf("Sort reult:");
output_int(R);
}
第二篇：20xx年自学考试《数据结构》各章复习要点总结
20xx年自学考试《数据结构》各章复习要点总结(4) 龙耒为你整理：
第七章 图
图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。
图GraphG=(V，E)，V是顶点的有穷非空集合，E是顶点偶对的有穷集。 有向图Digraph：每条边有方向;
无向图Undigraph：每条边没有方向;
有向完全图：具有n*(n-1)条边的有向图;
无向完全图：具有n*(n-1)/2条边的无向图;
有根图：有一个顶点有路径到达其它顶点的有向图;
简单路径：是经过顶点不同的路径;
简单回路：是开始和终端重合的简单路径;
网络：是带权的图。
图的存储结构：
·邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的，适合稠密图。 ·无向图：邻接矩阵是对称的。
·有向图：行是出度，列是入度。
建立邻接矩阵算法的时间是O(n+n^2+e)，其时间复杂度为O(n^2) ·邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。
·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。 ·邻接表：用头指针确定。
·无向图称边表;
·有向图又分出边表和逆邻接表;
·邻接表结点结构为 adjvex | next，时间复杂度为O(n+e)，空间复杂度为O(n+e)。
图的遍历：
·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。 ·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。 生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树。 最小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树(MST)。 构造最小生成树的算法： ·Prim算法的时间复杂度为O(n^2)与边数无关适于稠密图。
·Kruskal算法的时间复杂度为O(lge)，主要取决于边数，较适合于稀疏图。 最短路径的算法：
·Dijkstra算法，时间复杂度为O(n^2)。
·类似于prim算法。
拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，若∈E(G)，则在线性序列u在v之前，这种线性序列称为拓扑序列。
拓扑排序也有两种方法： ·无前趋的顶点优先：每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。
·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。
第八章 排序 记录中可用某一项来标识一个记录，则称为关键字项，该数据项的值称为关键字。
排序是使文件中的记录按关键字递增(或递减)次序排列起来。
·基本操作：比较关键字大小;改变指向记录的指针或移动记录。 ·存储结构：顺序结构、链表结构、索引结构。 经过排序后这些具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的，否则排序算法是不稳定的。
排序过程中不涉及数据的内、外存交换则称之为“内部排序”(内排序)，反之，若存在数据的内外存交换，则称之为外排序。
内部排序方法可分五类：插入排序、选择排序、交换排序、归并排序和分配排序。
评价排序算法好坏的标准主要有两条：执行时间和所需的辅助空间，另外算法的复杂程序也是要考虑的一个因素。 插入排序： ·直接插入排序;
·逐个向前插入到合适位置;
·哨兵(监视哨)有两个作用;
·作为临变量存放R[i];
·是在查找循环中用来监视下标变量j是否越界;
·直接插入排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为(n+2)(n-1)/2;移动次数为(n+4)(n-1)/2。
希尔排序：
·等间隔的数据比较并按要求顺序排列，最后间隔为1; ·希尔排序是就地的不稳定排序。时间复杂度为O(n^1.25)，比较次数为(n^1.25);移动次数为(1.6n^1.25);
交换排序： 冒泡排序：
·自下向上确定最轻的一个。
·自上向下确定最重的一个。
·自下向上确定最轻的一个，后自上向下确定最重的一个。 ·冒泡排序是就地的稳定排序。时间复杂度为O(n^2)，比较次数为n(n-1)/2;移动次数为3n(n-1)/2;
快速排序：
·以第一个元素为参考基准，设定、动两个指针，发生交换后指针交换位置，直到指针重合。重复直到排序完成。 ·快速排序是非就地的不稳定排序。时间复杂度为O(nlog2n)，比较次数为n(n-1)/2。 选择排序：
·直接选择排序;
·选择最小的放在比较区前; ·直接选择排序就地的不稳定排序。时间复杂度为O(n^2)。比较次数为n(n-1)/2。
堆排序
·建堆：按层次将数据填入完全二叉树，从int(n/2)处向前逐个调整位置。 ·然后将树根与最后一个叶子交换值并断开与树的连接并重建堆，直到全断开。
·堆排序是就地不稳定的排序，时间复杂度为O(nlog2n)，不适宜于记录数较少的文件。
归并排序：
·先两个一组排序，形成(n+1)/2组，再将两组并一组，直到剩下一组为止。 ·归并排序是非就地稳定排序，时间复杂度是O(nlog2n)，
分配排序：
箱排序：
·按关键字的取值范围确定箱子数，按关键字投入箱子，链接所有非空箱。 ·箱排序的平均时间复杂度是线性的O(n)。
基数排序：
·从低位到高位依次对关键字进行箱排序。
·基数排序是非就稳定的排序，时间复杂度是O(d*n+d*rd)。
各种排序方法的比较和选择：
·待排序的记录数目n;n较大的要用时间复杂度为O(nlog2n)的排序方法; ·记录的大小(规模);记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现;
·关键字的结构及其初始状态;
·对稳定性的要求;
·语言工具的条件;
·存储结构;
·时间和辅助空间复杂度。