2023年新版数据结构实验报告

SHUJU7JIEGOUTCYUYANBAN薮相结施l（Ci1言版）———1姓名：关宏新学号：班级：计084班指导教师：储岳中getch();c：*C:\Docu>entsand$6七七11185\4<1>11115七百上01\桌面\实睑内容1\源代码\$1\口61>118.插入前的顺序表为：014916插入前的顺序表为：01491625插入后的顺庠表为：01491655删除前的顺序表为：01491625删除后的顺序表为:01492536检索的内容下标为：436496481253649648136496481496481一、实验目的掌握栈的基本操作:初始化栈、判栈为空、出栈、入栈等运算。二、实验规定认真阅读和掌握本实验的算法。上机将本算法实现。保存程序的运营结果，并结合程序进行分析。三、实验内容运用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：1、定义栈的顺序存取结构2、分别定义栈的基本操作(初始化栈、判栈为空、出栈、入栈等)3、定义一个函数用来实现上面问题：⑴十进制整数X和R作为形参(2)初始化栈(3)只要X不为0反复做下列动作将X%R入栈，X=X/R(4)只要栈不为空反复做下列动作栈顶出栈，输出栈顶元索四、程序流程图、算法及运营结果2-1ttinclude<stdio.h>include<stdlib.h>tfinclude<malloc.h>#definestack_init_size100definestackincrement10typedefstructsqstack(int*base;int*top;intstacksize;}sqstack;intStacklnit(sqstack*s)(s->base=(int*)maHoc(stack_init_size*sizeof(int));if(!s—>base)return0；s->top=s—>base;s->stacksize=stack_init_size；return1；intPush(sqstack*s,inte)if(s->top-s->base>=s->stacksize)(s->base=(int*)rea11oc(s->base,(s->stacksize+stackincrement)*sizeof(int))；if(!s->base)return0；s->top=s->base+s->stacksize;s—>stacksize+=stackincrement;}*(s->top++)=e;returne;)intPop(sqstack*s,inte)(if(s->top=s—>base)return0;e=*—s->top；returne;)intstackempty(sqstack*s)(if(s—>top==s->base)return1；)else(return0;})intconversion(sqstack*s)(intn,e=0,flag=0；printf("输入要转化的十进制数:\n");scanf("%d”,&n)；printf("要转化为多少进制：2进制、8进制、16进制填数字!\n");scanf("%d”,&f1ag);printf("将十进制数%d转化为%d进制是:\nM,n,flag);whi1e(n)(Push(s,n%flag)；n=n/flag；)while(!stackempty(s))(e=Pop(s,e)；switch(e)(case10:printf(MA*);break;case11:printf("B");break;case12:printf(*C*);break；case13:printf("D")；break;case14：printf(*E")；break;case15:printf("F")；break;defau1t:printf(*%d",e);)}printf("\n*);return0;)intmain()(sqstacks;StackInit(&s);conversion(&s);return0;c\"C:\DocuMentsand$61:1::£1185\人（1>:111：15112101'\桌面\实验内容1\源代码\!输入要转化的十进制数:矍转化为多少进制：2进制、8进制、16进制填数字！2将十进制数25转化为2进制是：11001[Pressanykeytocontinue.2-2#include<stdlib.h>#defineMAXSIZE100structstack(intdata[MAXSIZE];inttop;)；voidinit(structstack*s)(s->top=-l;)intempty(structstack*s)(if(s->top==-1)return1;eIsereturn0;)voidpush(structstack*s,inti)if(s->top==MAXSIZE-1){printf("Stackisfull.\n");return;)s->top++;s->data[s->top]=i；}intpop(structstack*s)(if(empty(s)){printf("Stackisempty.");return-1;)return(s->data[s->top—])；)voidtrans(intnum){structstacks;intk；init(&s);while(num){k=num%16;push(&s,k);num=num/16;while(!empty(&s)){k=pop(&s);if(k<10)printfk);e1seprintf(M%c”,k+55)；)printf('\n");)main()(intnum；clrscr()；printf(*Inputanum(-1toquit):\n")；scanf&num);whi1e(num!=-1){trans(num);scanf&num);)getch();3C:\DOCU!E-l\AD・nn〜1\桌面,实验内〜1\源代码\S2\2TInputanun<-ltoquit>：452D实验三串的模式匹配一、实验目的.运用顺序结构存储串，并实现串的匹配算法。.掌握简朴模式匹配思想，熟悉KMP算法。二、实验规定A1.认真理解简朴模式匹配思想，高效实现简朴模式匹配：.结合参考程序调试KMP算法,努力算法思想；.保存程序的运营结果,并结合程序进行分析。三、实验内容1、通过键盘初始化H的串和模式串，通过简朴模式匹配算法实现串的模式匹配，匹配成功后规定输出模式串在目的串中的位置；2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目的串并设计匹配算法完整调试KMP算法,并与简朴模式匹配算法进行比较。四、程序流程图、算法及运营结果3-1#include<stdio.h>#include<string.h>#defineMAXSIZE100intStrIndex_BF(chars[MAXSIZE],chart[MAXSIZE])(inti=1,j=1;whi1e(i<=s[0]&&j<=t[0])if(s[i]==t[j]){i++；j++；)eIse{i=i-j+2;j=l;)}if(j>t[0])return(i-t[0]);elsereturn-1;}intmain()(chars[MAXSIZE];chart[MAXSIZE];intanswer,i;printf(*SString->\n");gets(s)；printf(*TString—>\n")；gets(t)；printfStrindex_BF(s,t))；/*验证*/实验一线性表基本操作的实现一、实验目的I、掌握使用TurboC2.0上机调试线性表的基本方法；2、掌握线性表的基本操作:插入、删除、查找等运算在顺序存储结构和链式存储结构上的运算。二、实验规定1、链表插入、删除和查找算法的代码；程序运营结果及分析；3、实验总结。三、实验内容1、认真阅读和掌握本实验的参考程序。2、上机运营本程序,并完善删除、查找等运算。3、保存程序的运营结果,并结合程序进行分析。4、按照你对链表操作需要，重新改写算法并运营，实现链表的插入、删除、查找等运算，并保存运营结果。四、程序流程图、算法及运营结果1-1#include"stdio.h"#include"std1ib.h*'#defineMAXSIZE100structSeqList{intdata[MAXSIZE]；int1ength;）；typedefstructSeqList*PSeqList;PSeqListcreaeNullList_seq()if((answer=Strindex_BF(s,t))>=0)printf(*\n");printf("%s\nM,s)；for(i=0;i<answer；i++)printf(*");printf("%s”,t);printf(*\n\nPatternFoundat1ocation：%d\n”,answer)；)elseprintf(*\nPatternNOTFOUND.\n");getch()；return0;c("C:\DocuMentsandSettings\Ad*inistrator\桌面'实验内容SString—>

asdfdsassdTString—>

ass-1

PatternNOTFOUND.3-2#inc1ude<stdio.h>#include<string.h>#defineMAXSIZE100voidget_nextval(unsignedcharpat[],intnextva1[])intlength=strlen(pat);inti=1;intj=0;nextva1[l]=0;while(i<length)(if(j=0||pat[i-1]==pat[j-1]){++i;++j；if(pat[i—1]!=pat[j—1])nextva1[i]=j;elsenextva1[i]=nextval[j]；)eIsej=nextval[j];)}nextval[])nextval[])nextval[])intIndex_KMP(unsignedchartext[],unsignedcharpat[],int(nextval[])inti=1；intj=1;intt_len=strlen(text)；intp_1en=strlen(pat);while(i<=t_len&&j<=p_1en)if(j=0I|text[i-1]==pat[j-l]){++i;++j;}elsej=nextval[j];)if(j>P_1en)returni-1-p_len;elsereturn-1；}intmain()(unsignedchartext[MAXSIZE];unsignedcharpat[MAXSIZE]；intnextval[MAXSIZE];intanswer,i；printf(M\nBoyer-MooreStringSearchingProgram");printf(*\n==========================*).printf("\n\nTextString—>”);gets(text);printf(*'\nPatternString—>");gets(pat);get_nextval(pat,nextval);if((answer=Index_KMP(text,pat,nextval))>=0)(printf(”\n");printf(*'%s\n”,text);for(i=0；i<answer;i++)printf("")；printfpat)；printf(*\n\nPatternFoundat1ocation%d\n*,answer)；}eIseprintf(*\nPa11ernNOTFOUND.\n*)；getch();return0;)c(*C:\DocuaentsandSettingsYAdBinistrator\桌面,实验内:Boyer-MooreStringSearchingProgranTextString——>asdfdddssaPatternString——>dsasdfdddssadsPatternFoundatlocation63-3#include*stdio.h"voidGetNext1(char*t,intnext[])(inti=l,j=0;next[l]=0;while(i<=9)if(j==OI|t[i]==t[j]){++i;++j；next[i]=j;}elsej=next[j];))voidGetNext2(char*t,intnext[])(inti=1,j=0；next[l]=0;while(i<=9)(whi1e(j>=l&&t[i]!=t[j])j=next[j];i++；j++；if(t[i]=t[j])next[i]=next[j];elsenext[i]=j;))voidmain()(char*p=*abcaababc";inti,str[10];GetNext1(p,str);printf(MPutout:\n");for(i=1;i<10;i++)printf("%d*,str[i]);GetNext2(p,str);printf("\n");for(i=l;i<10;i++)printf(*%d*,str[i])；printf;getch();)cT*C:\Docu*entsandSettings\Ad*inistraPutout：011112123011102013■实验四二叉树操作一、实验目的.进一步掌握指针变量的含义。.掌握二叉树的结构特性，以及各种存储结构的特点及使用范围。.掌握用指针类型描述、访问和解决二叉树的运算。二、实验规定.认真阅读和掌握本实验的参考程序。.按照对二叉树的操作需要，在创建好二叉树后再通过遍历算法验证创建结果。.保存程序的运营结果，并结合程序进行分析。三、实验内率以下参考程序是按完全二叉树思想将输入的字符串生成二叉树，并通过遍历来验证二叉树创建对的与否，但不能创建非完全二叉树，请认真研究该程序，然后模仿教材例6.4初始化方式创建二又树:所有的空指针均用井表达，如教材图6-13相应的二叉树，建立时的初始序列为:##o四、程序流程图、算法及运营结果4-1#include*stdio.h"#definemax30#defineNULL0typedefstructBNode(chardata;/*数据域*/structBNode*1child,*rchild；/*指向左右子女*/}BinTree;voidpreorder(BinTree*t)；/*声明先根遍历函数*/voidinorder(BinTree*t);/*声明中根遍历函数*/voidpostorder(BinTree*t)；/*声明后根遍历函数*/intleafs(BinTree*b);/*声明求叶子数函数*/inttreedeep(BinTree*p);/*声明求树的深度函数*/BinTree*swap(BinTree*p);/*声明互换二叉树的所有结点的左右子树的函数*//*将字符串中的第i个字符开始的m个字符作为数据生成相应的二叉树*/BinTree*cre_tree(char*str,inti,intm)(BinTree*p;if(i>=m)/*无效结点*/returnNULL；p=(BinTree*)maHoc(sizeof(BinTree));/*生成新结点*/p->data=str[i];p->lchi1d=cre_tree(str,2*i+1,m);/*创建新结点的左子树♦/p->rchild=cre_tree(str,2*i+2,m);/*创建新结点的右子树*/returnp;)voidmain()(inti,n；charstr[max]；BinTree*root;/*根结点*/Printf("请输入二叉树的结点数:")；scanf&n);getchar();/*输入数字*/printf("请输入长度为%d的字符串n);for(i=0；i<n;i++)scanfC%c",&str[i]);printf(*\n");root=cre_tree(str,0,n)；printf("二叉树已成功创建!结点序列为:");for(i=0;i<n;i++)printf("%cstr[i]);printf("\n");/*先根遍历*/Printf("\n先根遍历结果:");preorder(root)；printf('\n")；/*中根遍历*/printf("\n中根遍历结果:");inorder(root);printf(*\nn)；/*后根遍历*/printf("\n后根遍历结果：")；postorder(root);printf(*\n*);printf("\n叶子数为：%d\n",1eafs(root));printf(M\n树的深度为：％d\n”,treedeep(root));printf("\n互换左右子树后先序遍历序列为:");preorder(swap(root));printf("\n\n*);)voidpreorder(BinTree*t)(if(t!=NULL)(printf(*%ct—>data);chi1d)(printf("->");preorder(t->lchi1d)；)if(t—>rchi1d)printf("一>")；preorder(t->rchiId);)})voidinorder(BinTree*t)(if(t!=NULL)(inorder(t->lchild)；printf('%c",t—>data)；inorder(t->rchi1d);})voidpostorder(BinTree*t)(if(t!=NULL)(postorder(t->1chi1d);postorder(t->rchiId);printf(M%c*,t->data);})intleafs(BinTree*b)/*求叶子数*/PSeqListpalist=(PSeqList)mal1oc(sizeof(structSeqList));if(palist!=NULL)(palist->length=0;return(palist);)printf(MOutofspacel!\n*)；returnNULL;)intisNullList_seq(PSeqListpalist)(return(pa1ist->length==O);)intinsertPre_seq(PSeqListpalist,intp,intx)(intq；if(palist->1ength>=MAXSIZE：)(printf("overflow!\n")；return(0);)if(p<0IIp>palist->length){printf("Notexist!\n");return(0)；intnuml,num2;if(b==NULL)return(0);eIseif(b->lchi1d==NULL&&b->rchi1d==NULL)return(1)；else(numl=leafs(b->1child)；num2=leafs(b->rchi1d);return(numl+num2)；})inttreedeep(BinTree*p)/*求树的深度*/(int1deep,rdeep,deep;if(p==NULL)deep=0；else{Ideep=treedeep(p—>1chi1d);rdeep=treedeep(p->rchild);deep=(1deep>rdeep?1deep：rdeep)+l;)returndeep；}BinTree*swap(BinTree*p)/*互换二叉树的所有结点的左右子树*/(BinTree*stack[max];intk=0;stack[k]=NULL;if(p!=NULL){stack[+4-k]=p—>1child;p—>1child=p->rchi1d；p->rchild=stack[k];p->lchild=swap(p->lchiId);p->rchi1d=swap(p->rchiId);}returnp；)c：（*C:\Docu*entsand$6七±11185\4（1>11115t1@七01'\桌面\实娑内容1\源代码\54\。61）11即请输入二叉树的结点越：8请输入长度为8的字符串：asdfqwer二叉树己成功创建？结点序列为：asdfqwer先根遍历结果：a->s->£->r->q->d->w->e中根遍历结果：nFsqawde后根遍历结果：i'fqsweda叶子数为：4树的深度为：4交换左右子树后先序遍历序列为：a->d->e->w->s->q->f->rPressanykeytocontinue实验五图的创建与遍历.一、实验目的.掌握图的含义；.掌握用邻接矩阵和邻接表的方法描述图的存储结构；.理解并掌握深度优先遍历和广度优先遍历的存储结构。二、实验规定.认真阅读和掌握本实验的参考程序。.按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。.保存程序的运营结果，并结合程序进行分析。三、实验内乱以下参考程序是按邻接表的方法创建图,然后用深度优先遍历方法遍历图.请认真理解程序,然后实现图的广度优先遍历。四、程序流程图、算法及运营结果5-1#include*stdio.h"#definemaxsize1024/*假定线性表的最大长度为1024*/ftdefinenlOO/*图的顶点最大个数*/typedefintdatatype；/*假定线性表元素的类型为整型文/typedefcharVEXTYPE；/*顶点的数据类型*/typedeff1oatADJTYPE；/*权值类型*/typedefstruct(VEXTYPEvexs[n];/*顶点信息数组*/ADJTYPEarcs[n][n];/*边权数组*/intnum;/*顶点的实际个数*/}GRAPH;/*1.置空图*/voidGraphinit(GRAPH*L)L->num=0;/*2.求结点数*/intGraphVexs(GRAPH*L)(return(L->num);}/*3.创建图*/voidGraphCreate(GRAPH*L)(inti,j;GraphInit(L)；printf("请输入顶点数目：”)；scanf("%d”,&L->num);printf(〃请输入各顶点的信息(单个符号)：");for(i=0;i<L->num;i++)(fflush(stdin);scanf("%c",&L->vexs[i]);}printf。请输入边权矩阵的信息：”)；for(i=0;i<L->num;i++)(for(j=0;j<L->num;j++)scanf&L->arcs[i][j])；printf("图已经创建完毕!”)；)/*4.图的输出*/voidGraphOut(GRAPHL)(inti,j;printf("\n图的顶点数目为：%d*,L.num);printf("\n图的各顶点的信息为：\n");for(i=0；i<L.num;i++)printf(*%c”,L.vexs[i]);printf("\n图的边权矩阵的信息为：\n");for(i=0;i<L.num;i++)(for(j=0;j<L.num;j++)(printfC%6.2f",L.arcs[i][j]);}printf(M\n*);)printf("图己经输出完毕!〃)；}/*5.图的深度环游*/voidDFS(GRAPHg,intqidian,intmark[])/*从第qidian个点出发深度优先环游图g中能访问的各个顶点*/intv1;mark[qidian]=1；printf("%c*,g.vexs[qidian]);for(v1=0；vl<g.num；vl++)(if(g.arcs[qidian][vl]!=0&&mark[v1]==0)DFS(g,v1,mark);))/*6.图的深度环游*/voidGraphDFS(GRAPHg)/*深度优先环游图g中能访问的各个顶点*/(intqidian,v,vl,mark[maxsize];Printf(*\n深度环游：")；printf("\n请输入起点的下标:")；scanf(*%d",&qidian);for(v=0；v<g.num;v++)(mark[v]=0;}for(v=qidian;v<g.num+qidian;v-H-)(vl=v%g.num;if(mark[vl]==0)DFS(g,vl,mark);}/*队列元素的数据类型*/typedefintDATATYPE；typedefstruct(DATATYPEdataEmaxsize];/*队中元素*/intfront,rear;/*队头元素下标、队尾元素后面位置的下标*/}SEQQUEUE;voidQueueinit(SEQQUEUE*sq)/*将顺序循环队列sq置空(初始化)*/(sq—>front=0;sq->rear=0；)intQueuelsEmpty(SEQQUEUEsq)/*假如顺序循环队列sq为空,成功返回1,否则返回0*/(if(sq.rear==sq.front)return(1);elsreturn(O);intQueueFront(SEQQUEUEsq,DATATYPE*e)/*将顺序循环队列sq的队头元素保存到e所指地址，成功返回1,失败返回0*/(if(QueueIsEmpty(sq)){printf("queueisempty!\n")；return0;}e1se{*e=sq.data[(sq.front)];return1;}}intQueueIn(SEQQUEUE*sq,DATATYPEx)/*将元素x入队列sq的队尾,成功返回1,失败返回0*/(if(sq—>front==(sq->rear+1)%maxsize)(printf(*queueisfull!\n*)；return0；)else(sq->data[sq->rear]=x;sq—>rear=(sq->rear4-1)%maxsize;return(1);intQueueOut(SEQQUEUE*sq)/♦将队列sq队首元素出队列,成功返回1,失败返回0*/(if(QueueIsEmpty(*sq))(printf(*queueisempty!\nn);return0;)e1se(sq->front=(sq->front+1)%maxsize；return1;})/*7.图的广度环游*/voidBFS(GRAPHg,intv,intmark[])/*从v出发广度优先环游图g中能访问的各个顶点*/(intvl,v2；SEQQUEUEq;QueueInit(&q)；Queueln(&q,v)；mark[v]=1;printf("%cn,g.vexs[v]);while(QueuelsEmpty(q)==0)QueueFront(q,&vl)；QueueOut(&q);for(v2=0;v2<g.num;v2++)(if(g.arcs[vl][v2]!=0&&mark[v2]==0)(Queuein(&q,v2);mark[v2]=1；printf('%c",g.vexs[v2])；))))/*8.图的广度环游*/voidGraphBFS(GRAPHg)/*深度优先环游图g中能访问的各个顶点*/(intqidian,v,vl,mark[maxsize];printf("\n广度环游:");printf(M\n请输入起点的下标:");scanf("%d”,&qidian);for(v=0;v<g.num;v++)mark[v]=0;if(isNul1List_seq(pa1ist))pa1ist->data[0]=x；palist->length=l;return(1);}for(q=palist->length-l;q>=p;q—)Palist->data[q+1]=palist->data[q];pa1ist->data[p]=x;palist—>1ength=palist->length+1；return(1);)voidmainO(inti；PSeqListlist;ist=creaeNullList_seq();printf(〃插入前的顺序表为：\n");for(i=0；i<=9;i++)(insertPre_seq(list,i,i*i);printf("%d*,list->data[i]);)insertPre_seq(list,5,55);for(v=qidian;v<g.num+qidian;v++)vl=v%g.num;if(mark[v1]=0)BFS(g,vl,mark);))voidmain(){GRAPHtu；GraphCreate(&tu);Graph0ut(tu)；GraphDFS(tu)；GraphBFS(tu);)c<*C:\Docu*entsandSettings\Ad*inistrat1\^f^m\S5\Debug...请揄入顶点数目：5请输入各顶点的信息〈单个符号）括输入边权矩阵的信息：1111213141536171819202122232425百己经创建完晌图的顶点数目为：5图的各顶点的信息为:向市边,紊阵需信息为:1.002.003.004.006.007.008.009.0011.0012.0013.0014.0016.0017.0018.0019.0021.0022.0023.0024.005.0010.0015.0020.0025.00图己经输出完毕！房度周凝：情输入起点的下标:

z±.mmzz.oazj.ohj图己经趟出完毕！巷展周潘：情输入起点的下标：d请输入抢点的下标：a请输入抢点的下标：a请输入抢点的下标：aPi、essanykeytocontinue实验六请输入抢点的下标：aPi、essanykeytocontinue一、实验目的.通过实验掌握查找的基本概念；.掌握顺序查找算法与实现；.掌握折半查找算法与实现。二、实验规定.认真阅读和掌握本实验的参考程序。.保存程序的运营结果，并结合程序进行分析。三、实验内容1、建立一个线性表,对表中数据元素存放的先后顺序没有任何规定。输入待查数据元素的关键字进行查找。为了简化算法，数据元素只含一个整型关键字字段，数据元素的其余数据部分忽略不考虑。建议采用前哨的作用，以提高查找效率。2、查找表的存储结构为有序表，输入待查数据元素的关键字运用折半杳找方法进行查找。此程序中规定对整型量关键字数据的输入按从小到大排序输入。四、程序流程图、算法及运营结果算法：6-1#inc1ude"type.h"intseach_seq(SSTableA,E1emTypekey){inti,n;n=A.1ength;A.e1em[n].key=key；for(i=0;A.elem[i].key!=key;++i)returni；)2#inc1ude"type,h”intBinsch(SSE1ementA口，int1ow,inthigh,E1emTypeK){intmid;if(low<=high){intmid=(1ow+high)/2;if(K=A[mid].key)returnmid;/*查找成功，返回元素的下标*/eIseif(K<A[mid].key)returnBinsch(A,low,mid-1,K);/*在左子表上继续查找*/elsereturnBinsch(A,mid+Lhigh,K);/*在右子表上继续查找*/)eIsereturn0;/*查找失败，返回0*/)实验七各种排序方法的比较一、实验目的.通过实验掌握排序的基本概念，对排序的稳定性及排序的时间复杂性有深刻的结识。.掌握各种排序方法的基本思想和算法实现。.可以灵活地选用某种排序方法解决问题。二、实验规定.认真阅读和掌握本实验的参考程序。.保存程序的运营结果，并结合程序进行分析。三、实验内容编写一个程序，对所给的数据(程序中给出或通过键盘初始化均可)进行排序，规定尽也许多的选择不同的排序算法,并显示排序前和排序后的结果。四、程序流程图、算法及运营结果算法：常用排序算法总结及C源程序a/*直接插入排序*/voidInsertSort(int*out,int*op,int1ength)A{Ainti,j;Aintdata;memepy(out,op,length*sizeof(int));Afor(i=1；i<1ength;i++){adata=out;Afor(j=i-1;data<out[j]&&j>=0;j—)a{aout[j+1]=out[j];A)Aout[j+1]=data;a)}/*折半插入排序*/voidBInsertSort(int*out,int*op,intlengtH)a{aintlow,mid,high;inti,j,data;.i(nemepy(out,op,length*sizeof(int));for(i=1;i<length；i++)4{“ata=out;a1ow=0;Ahigh=i-1;while(low<=high)(mid=(low+high)/2;if(data<out[mid])high=mid-1;elseAlow=mid+1：a}Afor(j=i-1；j>=high+l;j-)out[j+l]=out[j];aout[j+l]=data;}}a/*冒泡算法*/avoidBubb1eSort(int*out,int*op,int1ength)a{*sizeof(int));inti,j;电emcpy(out,op,lengthfor(i=1ength-1;i>=0;i-)从{*sizeof(int));for(j=0;j<i;j++){▲if(out[j]>out[j+1])a{aswap(out+j,out+j+1)；a}a}a}a}/*快速排序*/intPartition(int*out,int*op,intlength,int1ow,inthigh)a{intpivokey;Amemcpy(out,op,length*sizeof(int));Apivokey=outflow];Awhile(1ow<high)a{whi1e(out[high]>pivokey&&low<high){ahigh―}swap(out+high,&pivokey);while(out[low]<pivokey&&low<high)a{ow++;a)swap(out+low,&pivokey);}areturnlow；a}〃递归形式的快速排序算法voidQSort(int*out,int*op,intlength,intlow,inthigh)a{intpivoloc;memcpy(out,op,1ength*sizeof(int));if(low<high){Apivo1oc=Partition(out,op,1ength,low,high);QSort(out,out,lengQSort(out,out,length,1ow,pivo1oc-1)；ath,pivo1oc+Lhigh)QSort(out,out,leng选择排序简朴选择排序intSelectMinKey(int*op,intlength,inti)A{

intintintPO1，j;母ntmin=op；Afor(ji+1；j<1ength;j++)a{Aif(op[j]<min)intPO1，j;母ntmin=op；Afor(ji+1；j<1ength;j++)a{Aif(op[j]<pos=j;)}returnpos；a}//简朴选择排序AvoidSelectSort(int*out,int*op,intlength){Ainti,j；%emcpy(out,op,length*sizeof(int))；for(i=0;i<length;i4-+)A(Aj=SelectMinKey(out,length,i)；aif(i!=j)a{swap(out+i,out+j);)}4}自/*希尔排序*/村。1(1Shell(int*out,int*op,intlength,intdk)//一趟希尔排序a{//与直接插入排序相比，前后记录位置的增量为dk,而不是1inti,j,data;Amemcpy(out,op,1ength*sizeof(int));for(i=dk;i<1ength;i++)(data=out；Afor(j=i-dk;(data<out[j])&&j>=0;j=j—dk)(out[j+dk]=out[j];}aout[j+dk]=data*}}，/按增量序列dlta[0,...,t-l]对顺序表作希尔排序voidShellSort(int*out,int*op,int*dlta,intt,int1ength)a{Mntk;for(k=0；k<t;k++)Shell(out,op,1ength,d1ta[k]);printf("\n插入后的顺序表为：\n*);for(i=0;i<list->1ength;i++)printf(*%d,list—>data[i]);printf('\n");getchO;)八'C:\DocuBeirtsand$©七1:11185\4(1*1虱51]@±0工\桌面\实睑内容1\源代#include"stdio.hn#include"stdlib.h"#defineMAXSIZE100structSeqList{ntdata[MAXSIZE];ntlength;}；typedefstructSeqList*PSeqList；PSeqListcreaeNulIList_seq()(PSeqListpaIist=(PSeqL