#include<iostream>

using namespace std;

#define MAXSIZE 100 //参加排序元素的最大个数 typedef struct list

{

int key;

}RedType;

typedef struct

{

RedType r[MAXSIZE+1];

int length; //参加排序元素的个数 }SqList;

void output1(SqList &L)

{

for(int i=1;i<=L.length;i++)

cout<<L.r[i].key<<" ";

cout<<endl;

}

void output2(SqList &L)

{

for(int i=L.length;i>=1;i--)

cout<<L.r[i].key<<" ";

cout<<endl;

}

/*****************************冒泡排序*/ void BubbleSort(SqList &L)

{

int i,j;

int temp;

for(i=1;i<=L.length;i++)

for(j=1;j<=L.length-i;j++)

{

if(L.r[j].key>L.r[j+1].key)

{

temp=L.r[j].key;

L.r[j].key=L.r[j+1].key; L.r[j+1].key=temp; }

}

}

//折半插入排序

void BInsertSort(SqList &L)

{

int i,j,low,high,m;

for(i=2;i<=L.length;++i)

{

L.r[0]=L.r[i];

low=1;

high=i-1;

while(low<=high)

{

m=(low+high)/2;

if(L.r[0].key>L.r[m].key) high=m-1;

else

low=m+1;

}

for(j=i-1;j>=high+1;--j)

L.r[j+1]=L.r[j];

L.r[high+1]=L.r[0];

}

}

/**********************************希尔排序*/ void ShellSort(SqList &L)

{

int d=(L.length+1)/2;

int i,j,temp;

while(d>=1)

{

for(i=d;i<=L.length;i++)

{

temp=L.r[i].key;

j=i-d;

while(j>0&&L.r[j].key>temp) {

L.r[j+d]=L.r[j];

j=j-d;

}

L.r[j+d].key=temp;

}

d=d/2;

}

}

/****************************直接插入排序*/ void InsertSort(SqList &L)

{

int i,j;

for(i=2;i<=L.length;i++)

{

if(L.r[i].key<L.r[i-1].key)

{

L.r[0]=L.r[i];

for(j=i-1;L.r[0].key<L.r[j].key;--j) L.r[j+1]=L.r[j];

L.r[j+1]=L.r[0];

}

}

}

/****************************** 简单选择排序 */ int SelectMinKey(SqList &L,int i)

{

int min=i;

int j;

for(j=i+1;j<=L.length;j++)

if(L.r[min].key>L.r[j].key)

min=j;

return min;

}

void SelectSort(SqList &L)

{

int i,j;

for(i=1;i<L.length;i++)

{

j=SelectMinKey(L,i);

if(i!=j)

{

int temp;

temp=L.r[i].key;

L.r[i].key=L.r[j].key;

L.r[j].key=temp;

}

}

}

/************************************快速排序*/ int Partition(SqList &L,int low,int high) //拆成两个子序列 {

L.r[0]=L.r[low];

int pivotkey=L.r[low].key;

while(low<high)

{

while(low<high&L.r[high].key>=pivotkey) --high;

L.r[low]=L.r[high];

while(low<high&&L.r[low].key<=pivotkey) ++low;

L.r[high]=L.r[low];

}

L.r[low]=L.r[0];

return low;

}

void QuickSort(SqList &L,int low,int high)//递归调用，多次分割 {

if(low<high)

{

int middle=Partition(L,low,high);

QuickSort(L,low,middle-1);

QuickSort(L,middle+1,high);

}

}

//堆排序

typedef SqList HeapType;

void HeapAdjust(HeapType &H,int s,int m)

{

RedType rc=H.r[s];

for(int j=2*s;j<=m;j*=2)

{

if(j<m&&(H.r[j].key<H.r[j+1].key))

++j;

if(rc.key>H.r[j].key)

break;

H.r[s]=H.r[j];

s=j;

}

H.r[s]=rc;

}

void HeapSort(HeapType &H)

{

for(int i=H.length/2;i>0;i--)

HeapAdjust(H,i,H.length);

for(int i=H.length;i>1;--i)

{

RedType Temp;

Temp=H.r[1];

H.r[1]=H.r[i];

H.r[i]=Temp;

HeapAdjust(H,1,i-1);

}

}

void choose()

{

cout<<"1.使用冒泡排序"<<endl;

cout<<"2.使用折半插入排序"<<endl;

cout<<"3.使用希尔排序"<<endl;

cout<<"4.使用直接插入排序"<<endl;

cout<<"5.使用简单选择排序"<<endl;

cout<<"6.使用快速排序"<<endl;

cout<<"7.使用堆排序"<<endl;

cout<<"请选择："<<endl;

}

int main()

{

SqList L;

cout<<"请输入参加排序的元素的个数：";

cin>>L.length;

cout<<"请依次输入"<<L.length<<"个元素：";

for(int i=1;i<=L.length;i++)

cin>>L.r[i].key;

int flag;

do{

choose();

cin>>flag;

switch(flag)

{

case 1:

cout<<"冒泡排序后的结果为："; BubbleSort(L);

output1(L);

break;

case 2:

cout<<"折半插入排序后的结果为："; BInsertSort(L);

output1(L);

break;

case 3:

{

cout<<"希尔排序后的结果为："; ShellSort(L);

output1(L);

break;

}

case 4:

cout<<"直接插入排序后的结果为："; InsertSort(L);

output1(L);

break;

case 5:

cout<<"";

SelectSort(L);

output1(L);

break;

case 6:

cout<<"快速排序后的结果为："; QuickSort(L,1,L.length);

output1(L);

break;

case 7:

{

cout<<"堆排序后的结果为："; HeapSort(L);

output1(L);

break;

}

}

}while(flag!=0);

system("pause");

return 0;

}

 

第二篇：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)的排序方法; ·记录的大小(规模);记录大最好用链表作为存储结构，而快速排序和堆排序在链表上难于实现;

·关键字的结构及其初始状态;

·对稳定性的要求;

·语言工具的条件;

·存储结构;

·时间和辅助空间复杂度。