数据结构实训一(顺序表).doc

数据结构实训一（顺序表）#include#include/包含getch()函数#include#define MAXSIZE 1000/定义顺序表类型typedef int ElemType;typedef structElemType dataMAXSIZE;int length;SeqList;/给顺序表类型起一个别名SeqList;/定义接口int InputChoice();/选择函数void InitList(SeqList *List);/初始化顺序表void Display(SeqList List);/显示函数void Insert(SeqList *List);/插入函数void Search(SeqList List);/查找函数void Delete(SeqList *List);/删除函数void SimpleSort(SeqList List);/简单选择排序int Partition(SeqList List,int left,int right);/快排分割调整void QuickSort(SeqList *List,int left,int right);/快速排序void BinarySearch(SeqList List);/折半查找void Inveser(SeqList List);/逆置顺序表void InsertSort(SeqList List);/直接插入排序void BubbleSort(SeqList List);/冒泡排序void OrderInsert(SeqList *List);/有序插入void DeleteBetweenXY(SeqList *List);/删除介于X和Y之间的值void MergeList(SeqList *List_1,SeqList *List_2,SeqList *List_3);/合并顺序表void SplitList(SeqList *List_1,SeqList *List_2,SeqList *List_3);/拆分顺序表void ShellSort(SeqList List);/希尔排序void HeapAdjust(SeqList *List,int root,int length);/建立大顶堆void HeapSort(SeqList List);/堆排序void main()int myChoice;SeqList List;SeqList List_1;SeqList List_2;SeqList List_3;while(1)system(cls);myChoice=InputChoice();switch(myChoice)case 0:exit(0);break;case 1:InitList(&List);break;case 2:printf(当前顺序表为：);Display(List);getch();break;case 3:Insert(&List);break;case 4:Search(List);break;case 5:Delete(&List);break;case 6:SimpleSort(List);break;case 7:printf(排序前：);Display(List);QuickSort(&List,0,List.length-1);printf(n快速排序成功!n由于能力有限,暂无法计算移动和比较次数.nn);printf(排序后：);Display(List);getch();break;case 8:BinarySearch(List);break;case 9:Inveser(List);break;case 10:InsertSort(List);break;case 11:BubbleSort(List);break;case 12:OrderInsert(&List);break;case 13:DeleteBetweenXY(&List);break;case 14:MergeList(&List_1,&List_2,&List_3);break;case 15:SplitList(&List_1,&List_2,&List_3);break;case 16:HeapSort(List);break;case 17:ShellSort(List);break;default :break;/选择函数int InputChoice()int myChoice;printf(nn);printf(tttt 顺序表操作 n);printf(tt-n);printf(tt 1：初始化t);printf(tt 2：显示n);printf(tt 3：插入t);printf(tt 4：查找n);printf(tt 5：删除t);printf(tt 6：简单选择排序n);printf(tt 7：快速排序t);printf(tt 8：折半查找n);printf(tt 9：逆置线性表t);printf(tt 10：直接插入排序n);printf(tt 11：冒泡排序t);printf(tt 12：有序插入n);printf(tt 13：删除介于X&Y值之间的数);printf(t 14：合并顺序表 n);printf(tt 15：拆分顺序表 t);printf(t 16：堆排序 n);printf(tt 17：希尔排序t);printf(tt 0：退出n);printf(tt-n);printf(ttt请选择：);scanf(%d,&myChoice);printf(n);return myChoice;/初始化void InitList(SeqList *List)int length,seed;printf(请输入元素个数(0-%d)：,MAXSIZE);while(1)scanf(%d,&length);if(length=0 & length:);printf(请输入随机数种子(0-32767)：);while(1)scanf(%d,&seed);if(seed=0 & seed:);srand(seed);/初始化数据和长度for(int i=0;idatai=rand()%90+10;for(int j=length;jdataj=0;List-length=length;printf(初始化成功.n);getch();/显示函数void Display(SeqList List)for(int i=0;ilength=MAXSIZE)printf(该顺序表存储空间已满，无法继续插入.n);elseprintf(n请输入插入位置：);while(1)scanf(%d,&location);if(location0 & locationlength)break;elseprintf(插入位置不合法，请重新输入-:);printf(请输入插入的元素：);scanf(%d,&element);List-length+;for(int i=List-length-1;i=location;i-)List-datai=List-datai-1;List-datalocation-1=element;printf(元素 %d 插入 %d 位置成功.n,element,location);printf(插入后顺序表为：);Display(*List);getch();/查找函数void Search(SeqList List)ElemType element;int i=0;printf(请输入要查找的元素：);scanf(%d,&element);while(iList.length)if(List.datai+=element)break;printf(整个查找过程共移动了 %d 次n,i);if(iList.length)printf(查找成功.n);printf(元素 %d 在顺序表中的位置是：%d,element,i);elseprintf(查找失败.n);printf(在该顺序表中未找到元素 %d .n,element);getch();/删除函数void Delete(SeqList *List)int element;int i=0,j;printf(请输入要删除的元素：);scanf(%d,&element);while(ilength)if(List-datai+=element)break;printf(本次删除共比较 %d 次,移动 %d 次.n,i,List-length-i);if(ilength)for(j=i;jlength;j+)List-dataj-1=List-dataj;printf(删除成功.n);printf(删除后的顺序表为：);/顺序表长度减一List-length-;Display(*List);elseprintf(删除失败,该顺序表中不含有元素 %d .n,element);getch();/简单选择排序void SimpleSort(SeqList List)int i,j,min;int iCount=0,jCount=0;printf(排序前：);Display(List);for(i=0;iList.length-1;i+)min=i;for(j=i+1;jList.length;j+)if(List.datajdatai;while(i!=j)while(idataj=temp)j-;if(idatai=List-dataj;while(idatai=temp)i+;if(idataj=List-datai;List-datai=temp;return i;/快速排序void QuickSort(SeqList *List,int left,int right)int i;if(leftright)i=Partition(List,left,right);QuickSort(List,left,i-1);QuickSort(List,i+1,right);/折半查找void BinarySearch(SeqList List)int count=0;/记录比较次数int element,low,mid,high;low=0;high=List.length-1;printf(请输入要查找的元素：);scanf(%d,&element);/快速排序使其成为有序数列QuickSort(&List,0,List.length-1);while(low=high)mid=(low+high)/2;count+;if(List.datamid=element)break;elseif(List.datamidelement)low=mid+1;else high=mid-1;printf(本次查找次数为：%d .n,count);if(low=high)printf(查找成功.n);printf(元素 %d 在顺序表中的位置是：%d .,element,mid+1);elseprintf(查找失败.n);printf(元素 %d 不在该顺序表中.n,element);getch();/逆置顺序表void Inveser(SeqList List)int j=List.length-1;printf(逆置前：);Display(List);for(int i=0;iList.length/2;i+)List.datai=List.datai+List.dataj;List.dataj=List.datai-List.dataj;List.datai=List.datai-List.dataj;j-;printf(逆置后：);Display(List);getch();/直接插入排序void InsertSort(SeqList List)int i,j,k,temp;printf(排序前：);Display(List);for(j=1;j=0;i-)if(List.datajList.datai)break;if(i!=j-1)temp=List.dataj;for(k=j;ki+1;k-)List.datak=List.datak-1;List.datai+1=temp;printf(排序后：);Display(List);getch();/冒泡排序void BubbleSort(SeqList List)printf(排序前：);Display(List);int i,j=List.length-1;while(j0)for(i=0;iList.datai+1)List.datai=List.datai+List.datai+1;List.datai+1=List.datai-List.datai+1;List.datai=List.datai-List.datai+1;j-;printf(排序后：);Display(List);getch();/有序插入void OrderInsert(SeqList *List)/溢出判断if(List-length=MAXSIZE)printf(顺序表存储空间已满,无法进行插入操作.n);elseint i,j,element;/快排使其成为有序数列QuickSort(List,0,List-length-1);printf(插入前：);Display(*List);printf(n);printf(请输入要插入的元素：);scanf(%d,&element);/根据数值大小找到插入位置for(i=0;ilength;i+)if(elementdatai)break;List-length+;/表长加一/空出插入位置后赋值插入for(j=List-length-1;ji;j-)List-dataj=List-dataj-1;List-datai=element;printf(本次插入比较的次数为：%d ,移动的次数为：%d .n,i,List-length-i-1);printf(插入后：);Display(*List);getch();/删除X和Y之间的值void DeleteBetweenXY(SeqList *List)int m,n,max,min;int i,j=0;printf(删除前：);Display(*List);printf(请输入要删除的范围.n);printf(最大值：);scanf(%d,&m);printf(最小值：);scanf(%d,&n);if(nm)printf(您的输入不和逻辑，系统将自动更正.n);m=m+n;n=m-n;m=m-n;max=m;min=n;for(i=0;ilength;i+)/遍历所有数值，不在X和Y之间的值赋值给jif(List-dataidataimax)List-dataj+=List-datai;List-length=j;printf(删除后：);Display(*List);getch();/合并顺序表void MergeList(SeqList *List_1,SeqList *List_2,SeqList *List_3)int i,j,k;printf(初始化顺序表1.n);InitList(List_1);printf(n);printf(初始化顺序表2.n);InitList(List_2);printf(n);QuickSort(List_1,0,List_1-length-1);QuickSort(List_2,0,List_2-length-1);printf(合并前.n);printf(顺序表1：);Display(*List_1);printf(顺序表2：);Display(*List_2);/比较两个表中是否存在相同的值for(i=0;ilength;i+)for(j=0;jlength;j+)if(List_2-dataj=List_1-datai)List_1-datai=-1;i=0; j=0; k=0;/当两个表同时存在时while(ilength & jlength)if(List_1-dataidataj)if(List_1-datai=-1)i+;elseList_3-datak+=List_1-datai+;elseList_3-datak+=List_2-dataj+;/当仅有表1存在时while(ilength)if(List_1-datai=-1)i+;elseList_3-datak+=List_1-datai+;/当仅有表2存在时while(jlength)List_3-datak+=List_2-dataj+;/表3的长度为kList_3-length=k;printf(合并后.n);printf(顺序表为：);Display(*List_3);getch();/拆分顺序表void SplitList(SeqList *List_1,SeqList *List_2,SeqList *List_3)int i,j=0,k=0;printf(初始化顺序表.n);InitList(List_1);printf(n);printf(拆分前.n);printf(顺序表为：);Display(*List_1);printf(n);for(i=0;ilength;i+)if(List_1-datai%2=0)List_2-dataj+=List_1-datai;elseList_3-datak+=List_1-datai;List_2-length=j;List_3-length=k;printf(拆分后.n);printf(偶数顺序表为：);Display(*List_2);printf(奇数顺序表为：);Display(*List_3);getch();/希尔排序void ShellSor