课程设计---查找及排序.doc

题目：查找和排序（一）查找一、 需求分析1. 本程序实现2种查找：无序表的直接查找，顺序表的折半查找。 2. 顺序表的数据元素都是整数。二、 查找程序的概要设计1.无序表的直接查找抽样数据类型顺序表的定义如下：ADT SqList数据对象：D = ai| aiElemSet, i = 1,2，,n,n0数据关系：R1 = |a(i-1),aiD,i=2,n基本操作： Init(SqList &L) 操作结果：构造一个空的顺序表L。 insert(SqList &L,int &m)初始条件：顺序表L已存在。操作结果：在顺序表中有序插入新的数据元素m，L的长度加1。Locate(SqList L,int e)初始条件：顺序表L已存在。操作结果：查找e的位置。print(SqList L)初始条件：顺序表L已存在。操作结果：依次显示出L中的数据元素。ADT SqList2.有序表的折半查找抽样数据类型顺序表的定义如下：ADT SqList数据对象：D = ai| aiElemSet, i = 1,2，,n,n0数据关系：R1 = |a(i-1),aiD,i=2,n基本操作： Init(SqList &L) 操作结果：构造一个空的顺序表L。 insert(SqList &L,int &m)初始条件：顺序表L已存在。操作结果：在顺序表中有序插入新的数据元素m，L的长度加1。Search_Bin(SqList L,int m)初始条件：顺序表L已存在。操作结果：折半查找m的位置。print(SqList L)初始条件：顺序表L已存在。操作结果：依次显示出L中的数据元素。ADT SqList三、 详细设计1无序表的直接查找#include#include#include#include#define LS 100/顺序表存储空间的初始分配量#define LC 10/顺序表存储空间的分配增量using namespace std;typedef int Status;using namespace std;/- - - 动态分配顺序存储结构 - - -typedef struct int *elem;/存储空间基址 int listsize;/当前分配的存储容量（以sizeof（int）为单位） int len;/当前长度 SqList;Status Init(SqList &L)/构造一个空的顺序表L L.elem=(int *)malloc(sizeof(int)*LS); if(!L.elem) exit(-1);/存储分配失败 L.listsize=LS;/初始存储容量 L.len=0;/空表长度为0 return 1;/算法的时间复杂度O(c)Status insert(SqList &L,int m)/插入数据元素 if(L.lenL.listsize) L.elem=(int *)realloc(L.elem,sizeof(int)*(L.listsize+=LC); if(!L.elem) exit(-1); *(L.elem+L.len+)=m; return 1;int compare(int m,int n)/比较数据元素是否相同 if(m=n)return 1; else return 0;Status Locate(SqList L,int e)/查找数据元素的位置 int i=1; int* p=L.elem; while(i=L.len&!(compare(*p+,e) +i; if(i=L.len) cout第一个e在顺序表的第i个位置endl; else /查找失败 coutcant find 数据元素 e1) for(int i=1; iL.len; +i) printf( %d,*(L.elem+i); printf(n);int main() SqList L; int m,n; Init(L); puts(插入数据元素的个数为：); scanf(%d,&n); cout插入以下n个数据元素：endl; for(int i=0;in;i+) scanf(%d,&m); insert(L,m); puts(得到的顺序表为:); print(L); cout查找的数据元素是:; scanf(%d,&n); printf(%dn,n); Locate(L,n);2.有序表的折半查找#include#include#include#include#define LS 100/顺序表存储空间的初始分配量#define LZ 10/顺序表存储空间的分配增量#define Status intusing namespace std;/- - - 动态分配顺序存储结构 - - -typedef struct int *elem;/存储空间基址 int len;/当前长度 int lsz;/当前分配的存储容量（以sizeof（int）为单位） SqList ;Status Init(SqList &L)/构造一个空的顺序表L L.elem =(int *)malloc(LS*sizeof(int); if (!L.elem) exit(-2);/存储分配失败 L.len=0;/空表长度为0 L.lsz =LS;/初始存储容量 return 1;/算法的时间复杂度O(c)Status insert(SqList &L,int &m)/有序插入数据元素 if(L.len+1L.lsz) int *newbase; newbase=(int*)realloc(L.elem,(L.lsz+LZ)*sizeof (int); if(!newbase)exit (-2); L.elem=newbase; L.lsz+=LZ; int i=0,j; for(; im) j=i; for(i=L.len; ij; -i) L.elemi=L.elemi-1; L.elemj=m; +L.len; return 0; L.elemi=m; +L.len; return 0;int Search_Bin(SqList L,int m)/*在有序表L中，折半查找数据元素m。若找到，则函数值为该数据元素在表中的位置。*/ int low=1; int high=L.len;/置区间初值 while (low=high) int mid=(low+high)/2; if(m=*(L.elem+mid-1)/找到待查数据元素 cout第一个m在有序表的第mid个位置endl; return mid; else if(m*(L.elem+mid-1)/继续在前半区间进行查找 high=mid-1; else low=mid+1;/继续在后半区间进行查找 cout没有找到数据元素m1) for(int i=1; iL.len; +i) printf( %d,*(L.elem+i); printf(n);int main() SqList L; int m,n; Init(L); puts(插入数据元素的个数为：); scanf(%d,&n); cout插入以下n个数据元素：endl; for(int i=0; in; i+) scanf(%d,&m); insert(L,m); puts(得到的顺序表为:); print(L); cout查找的数据元素是:; scanf(%d,&n); printf(%dn,n); Search_Bin(L,n);四、 调试分析在无序表的查找程序中，在向顺序表插入数据元素时，要保证无序插入；在有序表的折半查找程序中，在向顺序表插入数据元素时，插入的数据元素排序了之后，再进行查找。五、 测试结果1.无序表的查找2.有序表的折半查找（二）排序一、需求分析1. 5种排序：堆排序，简单选择排序，冒泡排序，折半插入排序，直接插入排序。2.待排序表的数据元素都是整数。二、概要设计1.堆排序抽样数据类型顺序表的定义如下：ADT SqList数据对象：D = ai| aiElemSet, i = 1,2，,n,n0数据关系：R1 = |a(i-1),aiD,i=2,n基本操作： Init(SqList &L) 操作结果：构造一个空的顺序表L。 insert(SqList &L,int &m)初始条件：顺序表L已存在。操作结果：在顺序表中插入新的数据元素m，L的长度加1。HeapSort(SqList &L)初始条件：顺序表L已存在。操作结果：对顺序表进行堆排序。print(SqList L)初始条件：顺序表L已存在。操作结果：依次显示出L中的数据元素。ADT SqList2.简单选择排序抽样数据类型顺序表的定义如下：ADT SqList数据对象：D = ai| aiElemSet, i = 1,2，,n,n0数据关系：R1 = |a(i-1),aiD,i=2,n基本操作： Init(SqList &L) 操作结果：构造一个空的顺序表L。 insert(SqList &L,int &m)初始条件：顺序表L已存在。操作结果：在顺序表中插入新的数据元素m，L的长度加1。SelectSort(SqList L)初始条件：顺序表L已存在。操作结果：对顺序表进行简单选择排序。print(SqList L)初始条件：顺序表L已存在。操作结果：依次显示出L中的数据元素。ADT SqList3. 冒泡排序抽样数据类型顺序表的定义如下：ADT SqList数据对象：D = ai| aiElemSet, i = 1,2，,n,n0数据关系：R1 = |a(i-1),aiD,i=2,n基本操作： Init(SqList &L) 操作结果：构造一个空的顺序表L。 insert(SqList &L,int &m)初始条件：顺序表L已存在。操作结果：在顺序表中插入新的数据元素m，L的长度加1。BubbleSort(SqList L)初始条件：顺序表L已存在。操作结果：对顺序表进行冒泡排序。print(SqList L)初始条件：顺序表L已存在。操作结果：依次显示出L中的数据元素。ADT SqList4. 折半插入排序抽样数据类型顺序表的定义如下：ADT SqList数据对象：D = ai| aiElemSet, i = 1,2，,n,n0数据关系：R1 = |a(i-1),aiD,i=2,n基本操作： Init(SqList &L) 操作结果：构造一个空的顺序表L。 insert(SqList &L,int &m)初始条件：顺序表L已存在。操作结果：在顺序表中插入新的数据元素m，L的长度加1。BInsertSort(L)初始条件：顺序表L已存在。操作结果：对顺序表进行折半插入排序。print(SqList L)初始条件：顺序表L已存在。操作结果：依次显示出L中的数据元素。ADT SqList5. 直接插入排序抽样数据类型顺序表的定义如下：ADT SqList数据对象：D = ai| aiElemSet, i = 1,2，,n,n0数据关系：R1 = |a(i-1),aiD,i=2,n基本操作： Init(SqList &L) 操作结果：构造一个空的顺序表L。 insert(SqList &L,int &m)初始条件：顺序表L已存在。操作结果：在顺序表中插入新的数据元素m，L的长度加1。InsertSort(SqList &L,int &m)初始条件：顺序表L已存在。操作结果：对顺序表进行直接插入排序。print(SqList L)初始条件：顺序表L已存在。操作结果：依次显示出L中的数据元素。ADT SqList三、详细设计1.堆排序#include#include#include#include#define LS 100/顺序表存储空间的初始分配量#define LC 10/顺序表存储空间的分配增量using namespace std;typedef int Status;using namespace std;/- - - 动态分配顺序存储结构 - - -typedef struct int *elem;/存储空间基址 int listsize;/当前分配的存储容量（以sizeof（int）为单位） int len;/当前长度 SqList;Status Init(SqList &L)/构造一个空的顺序表L L.elem=(int *)malloc(sizeof(int)*LS); if(!L.elem) exit(-1);/存储分配失败 L.listsize=LS;/初始存储容量 L.len=1;/空表长度为1 return 1;/算法的时间复杂度O(c)Status insert(SqList &L,int m)/插入数据元素 if(L.lenL.listsize) L.elem=(int *)realloc(L.elem,sizeof(int)*(L.listsize+=LC); if(!L.elem) exit(-1); *(L.elem+L.len+)=m; return 1;void HeapAdjust(SqList &L,int s,int m) /已知*(L.elem+s.m)中记录的数据元素除*(L.elem+s)之外均满足堆的定义，本函数调整*(L.elem+s) /的数据元素，使*(L.elem+s.m)成为一个大顶堆（对其中记录的数据元素而言） int rc=*(L.elem+s); for (int j=2*s; j=m; j*=2)/沿数据元素较大的孩子结点向下筛选 if (jm&(*(L.elem+j)*(L.elem+j+1)/j为数据元素较大的记录的下标 +j; if(!(rc0; -i)/把*(L.elem+1.L.len)建成大顶堆 HeapAdjust(L,i,L.len); for( i=L.len; i1; -i) int t=*(L.elem+1);/将堆顶记录和当前未经排序子序列 *(L.elem+1)=*(L.elem+i);/(L.elem+1.i)中最后一个记录 *(L.elem+i)=t;/相互交换 HeapAdjust(L,1,i-1);/将(L.elem+1.i-1)重新调整为大顶堆 void print(SqList L)/遍历函数 printf(%d,*(L.elem+1); if(L.len1) for(int i=2; iL.len; +i) printf( %d,*(L.elem+i); printf(n);int main() SqList L; int m; Init(L); puts(插入以下数据元素：); while(scanf(%d,&m)=1) insert(L,m); puts(得到的顺序表为:); print(L); HeapSort(L); puts(堆排序后的顺序表为:); print(L);2.简单选择排序#include#include#include#include#define LS 100/顺序表存储空间的初始分配量#define LC 10/顺序表存储空间的分配增量using namespace std;typedef int Status;using namespace std;/- - - 动态分配顺序存储结构 - - -typedef struct int *elem;/存储空间基址 int listsize;/当前分配的存储容量（以sizeof（int）为单位） int len;/当前长度 SqList;Status Init(SqList &L)/构造一个空的顺序表L L.elem=(int *)malloc(sizeof(int)*LS); if(!L.elem) exit(-1);/存储分配失败 L.listsize=LS;/初始存储容量 L.len=0;/空表长度为0 return 1;/算法的时间复杂度O(c)Status insert(SqList &L,int m)/插入数据元素 if(L.lenL.listsize) L.elem=(int *)realloc(L.elem,sizeof(int)*(L.listsize+=LC); if(!L.elem) exit(-1); *(L.elem+L.len+)=m; return 1;int SelectMinKey(SqList L,int i) int Min=*(L.elem+i),MIN=i; for(i=i+1; i*(L.elem+i) Min=*(L.elem+i); MIN=i; return MIN;void SelectSort(SqList L)/对顺序表L作简单选择排序 int i,j,t; for(i=0; i1) for(int i=1; iL.len; +i) printf( %d,*(L.elem+i); printf(n);int main() SqList L; int m; Init(L); puts(插入以下数据元素：); while(scanf(%d,&m)=1) insert(L,m); puts(得到的顺序表为:); print(L); SelectSort(L); puts(简单选择排序后的顺序表为:); print(L);3.冒泡排序#include#include#include#include#define LS 100/顺序表存储空间的初始分配量#define LC 10/顺序表存储空间的分配增量using namespace std;typedef int Status;using namespace std;/- - - 动态分配顺序存储结构 - - -typedef struct int *elem;/存储空间基址 int listsize;/当前分配的存储容量（以sizeof（int）为单位） int len;/当前长度 SqList;Status Init(SqList &L)/构造一个空的顺序表L L.elem=(int *)malloc(sizeof(int)*LS); if(!L.elem) exit(-1);/存储分配失败 L.listsize=LS;/初始存储容量 L.len=0;/空表长度为0 return 1;/算法的时间复杂度O(c)Status insert(SqList &L,int m)/插入数据元素 if(L.lenL.listsize) L.elem=(int *)realloc(L.elem,sizeof(int)*(L.listsize+=LC); if(!L.elem) exit(-1); *(L.elem+L.len+)=m; return 1;int BubbleSort(SqList L)/冒泡排序 int i,j,account,t; for(i=1; i=L.len; +i) account=0; for(j=0; j*(L.elem+j+1) t=*(L.elem+j); *(L.elem+j)=*(L.elem+j+1); *(L.elem+j+1)=t; +account; if(!account) break; return 0;void print(SqList L) printf(%d,*(L.elem); if(L.len1) for(int i=1; iL.len; +i) printf( %d,*(L.elem+i); printf(n);int main() SqList L; int m; Init(L); puts(插入以下数据元素：); while(scanf(%d,&m)=1) insert(L,m); puts(得到的顺序表为:); print(L); BubbleSort(L); puts(冒泡排序后的顺序表为：); print(L);4.折半插入排序#include#include#include#include#define LS 100/顺序表存储空间的初始分配量#define LC 10/顺序表存储空间的分配增量using namespace std;typedef int Status;using namespace std;/- - - 动态分配顺序存储结构 - - -typedef struct int *elem;/存储空间基址 int listsize;/当前分配的存储容量（以sizeof（int）为单位） int len;/当前长度 SqList;Status Init(SqList &L)/构造一个空的顺序表L L.elem=(int *)malloc(sizeof(int)*LS); if(!L.elem) exit(-1);/存储分配失败 L.listsize=LS;/初始存储容量 L.len=1;/空表长度为1 return 1;/算法的时间复杂度O(c)Status insert(SqList &L,int m)/插入数据元素 if(L.lenL.listsize) L.elem=(int *)realloc(L.elem,sizeof(int)*(L.listsize+=LC); if(!L.elem) exit(-1); *(L.elem+L.len+)=m; return 1;void BInsertSort(SqList &L)/对顺序表L作折半插入排序 int low,m,high; for(int i=2; i=L.len; +i) *( L.elem+0)=*(L.elem+i);/将*（L.elem+i）暂存到*（L.elem+0） low=1; high=i-1; while(low=high)/在*(L.elem+low.high)中折半查找有序插入的位置 m=(low+high)/2;/折半 if(*(L.elem+0)=high+1; -j) *(L.elem+j+1)=*(L.elem+j);/记录后移 *(L.elem+high+1)=*(L.elem+0);/ 插入 void print(SqList L)/遍历 printf(%d,*(L.elem+1); if(L.len1) for(int i=2; iL.len; +i) printf( %d,*(L.elem+i); printf(n);int main() SqList L; int m; Init(L); puts(插入以下数据元素：); while(scanf(%d,&m)=1) insert(L,m); puts(得到的顺序表为:); print(L); BInsertSort(L); puts( 折半排序后的顺序表为:); print(L);5.直接插入排序#include#