2022年数据结构实验题目和源程序 .pdf

《2022年数据结构实验题目和源程序 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构实验题目和源程序 .pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1、直接插入排序2、希尔排序3、2-路归并排序4、折半插入排序5、冒泡排序6、快速排序7、堆排序/*-*07_排序.cpp-排序的相关操作*对排序的每个基本操作都用单独的函数来实现*水上飘2011 年写-*/ds07.cpp:定义控制台应用程序的入口点。/#include stdafx.h#include stdio.h#include#include using namespace std;#define MAXSIZE 20 typedefintKeyType;typedefstruct KeyType key;/关键字项KeyType data;/数据项RedType;/记录类型type

2、defstruct RedTypearrMAXSIZE+1;/arr0 闲置或用作哨兵单元int length;/顺序表长度SqList;/顺序表类型typedefSqListHeapType;/对顺序表L做一趟希尔插入排序/前后记录位置的增量是dk/r0 只是暂存单元/当 j=0 时，插入位置已找到voidshellInsert(SqList&L,intdk)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 8 页 -int i,j;for(i=dk+1;i=L.length;i+)if(L.arri.key 0&L.arr0.key L.arrj.key;j-=dk)L.arr

3、j+dk=L.arrj;/记录后移，查找插入位置/end for j L.arrj+dk=L.arr0;/插入/end if/end for i/shellInsert/按增量序列dlta0.t-1 对顺序表做希尔排序voidshellSort(SqList&L,intdlta,int t)for(int k=0;k t;k+)shellInsert(L,dltak);/一趟增量为dltak 的插入序列 /折半插入排序voidbInsertSort(SqList&L)for(int i=2;i=L.length;i+)L.arr0=L.arri;/将其暂存到arr0 int low=1;int

4、 high=i-1;while(low=high)/在 arrlow.high 中折半查找有序插入的位置int m=(low+high)/2;/折半if(L.arr0.key=high+1;j-)L.arrj+1=L.arrj;/记录后移L.arrhigh+1=L.arr0;/插入/for/BInsertSort/直接插入排序名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 8 页 -voidinsertSort(SqList&L)for(int i=2;i=L.length;i+)if(L.arri.key L.arri-1.key)/if,需将 L.arri插入有序子表L.ar

5、r0=L.arri;/复制为哨兵L.arri=L.arri-1;int j;for(j=i-2;L.arr0.key L.arrj.key;j-)L.arrj+1=L.arrj;/记录后移L.arrj+1=L.arr0;/插入到正确位置/if/for/InsertSort/冒泡排序voidbubbleSort(SqList&L)RedType*temp=NULL;for(int i=1;i L.length;i+)/第 i 趟排序for(int j=1;j L.arrj+1.key)/交换前后的位置L.arr0=L.arrj;L.arrj=L.arrj+1;L.arrj+1=L.arr0;/i

6、f/for j/for i/bubbleSort/交换顺序表中子表L.arrlow.high 的记录,/枢轴记录到位,并返回其所在位置int partition(SqList&L,int low,int high)L.arr0=L.arrlow;/子表的第一个记录做枢轴记录KeyTypepivotKey=L.arrlow.key;/枢轴记录关键字while(low high)/从表的两端交替向中间扫描while(low=pivotKey)high-;/while L.arrlow=L.arrhigh;/将比枢轴小的记录移到低端while(low high&L.arrlow.key=pivotK

7、ey)low+;/while 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 8 页 -L.arrhigh=L.arrlow;/将比枢轴大的记录移到高端/while L.arrlow=L.arr0;/枢轴记录到位return low;/返回枢轴位置/paitition/对顺序表L中的子序列L.arrlow.high 做快速排序voidqSort(SqList&L,int low,int high)if(low high)/长度大于1 KeyTypepivotLoc=partition(L,low,high);/将 L.arrlow.high 一分为二qSort(L,low,piv

8、otLoc-1);/对低子表递归排序，pivotLoc 是枢轴位置qSort(L,pivotLoc+1,high);/对高子表递归排序/if/qSort/对顺序表L做快速排序voidquickSort(SqList&L)qSort(L,1,L.length);/quickSort/调整 H.arrs的关键字，使H.arrs.m 成为一个大顶堆/（对其中记录的关键字而言）voidheapAdjust(HeapType&H,int s,int m)RedTyperc=H.arrs;for(int j=2*s;j=m;j=j*2)/沿 key 较大的孩子结点向下筛选if(j m&H.arrj.key

9、 H.arrj+1.key)j+;/j 为 key 叫大记录的下标/if if(!(rc.key 0;i-)/把 H.arr1.H.length 建成大顶堆名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 8 页 -heapAdjust(H,i,H.length);/for for(int i=H.length;i 1;i-)/将堆记录当前未经排序的子序列H.arr1.i 中的最后一个记录交换H.arr0=H.arr1;H.arr1=H.arri;H.arri=H.arr0;heapAdjust(H,1,i-1);/将 H.arr1.i-1 重新调整为大顶堆/for/heapSor

10、t/将有序的SRi.m和 SRm+1.n归并为有序的TRi.n void Merge(RedType SR,RedType*TR,int i,int m,int n)int j,k;for(j=m+1,k=i;i=m&j=n;k+)/将 SR中记录由小到大地并入TR if(SRi.key=SRj.key)TRk=SRi+;else TRk=SRj+;/end for j,k if(i=m)/将剩余的SRi.m复制到 TR for(;k=n&i=m;k+,i+)TRk=SRi;/end if i if(j=n)/将剩余的SRj.n复制到 TR for(;k=n&j=n;k+,j+)TRk=SRj

11、;/end if j/Merge/将 SRs.t归并排序为TR1s.t voidMSort(RedType SR,RedType TR1,int s,int t)int m;名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 8 页 -RedTypeTR2MAXSIZE;if(s=t)TR1s=SRs;else m=(s+t)/2;/将 SRs.t平分为 SRs.m和 SRm+1.t MSort(SR,TR2,s,m);/递归地将 SRs.m归并为有序的TR2s.m MSort(SR,TR2,m+1,t);/递归地将 SRm+1.t归并为有序的TR2m+1.t Merge(TR2,T

12、R1,s,m,t);/将 TR2s.m和 TR2m+1.t归并到 TR1s.t /MSort/对顺序表L做归并排序voidmergeSort(SqList&L)MSort(L.arr,L.arr,1,L.length);/mergeSort/初始化顺序表，给其赋值voidsetValue(SqList&L)KeyTypedata8=49,38,65,97,76,13,27,49;int n=8;L.arr0.data=0;L.length=n;for(int i=1;i=L.length;i+)L.arri.data=datai-1;L.arri.key=L.arri.data;/end fo

13、r i/setValue/输出顺序表void show(SqList&L)for(int i=1;i=L.length;i+)if(i%5=0)coutendl;coutsetw(5)L.arri.data;coutendl;/show 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 8 页 -/调用排序函数进行排序void performance(SqList&L)cout 原始序列：endl;show(L);SqList LI=L;insertSort(LI);cout 直接插入排序结果：endl;show(LI);SqList LS=L;intdlta3=4,3,1;int

14、 t=3;shellSort(LS,dlta,t);cout 希尔排序结果：endl;show(LS);SqList LM=L;mergeSort(LM);cout 2-路归并排序结果：endl;show(LM);SqList LB=L;bInsertSort(LB);cout 折半插入排序结果：endl;show(LB);SqList LBB=L;bubbleSort(LBB);cout 冒泡排序结果：endl;show(LBB);SqList LQ=L;cout 快速排序结果：endl;quickSort(LQ);show(LQ);HeapType H=L;cout 堆排序结果：endl;heapSort(H);show(H);/performance int _tmain(intargc,_TCHAR*argv)SqList L;setValue(L);performance(L);system(pause);名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 8 页 -return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 8 页 -