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一、實驗目的掌握棧的基本操作:初始化棧、判棧為空、出棧、入棧等運算。二、實驗規(guī)定認真閱讀和掌握本實驗的算法。上機將本算法實現。保存程序的運營結果，并結合程序進行分析。三、實驗內容運用棧的基本操作實現將任意一個十進制整數轉化為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算法。二、實驗規(guī)定A1.認真理解簡樸模式匹配思想，高效實現簡樸模式匹配：.結合參考程序調試KMP算法,努力算法思想；.保存程序的運營結果,并結合程序進行分析。三、實驗內容1、通過鍵盤初始化H的串和模式串，通過簡樸模式匹配算法實現串的模式匹配，匹配成功后規(guī)定輸出模式串在目的串中的位置；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、掌握線性表的基本操作:插入、刪除、查找等運算在順序存儲結構和鏈式存儲結構上的運算。二、實驗規(guī)定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■實驗四二叉樹操作一、實驗目的.進一步掌握指針變量的含義。.掌握二叉樹的結構特性，以及各種存儲結構的特點及使用范圍。.掌握用指針類型描述、訪問和解決二叉樹的運算。二、實驗規(guī)定.認真閱讀和掌握本實驗的參考程序。.按照對二叉樹的操作需要，在創(chuàng)建好二叉樹后再通過遍歷算法驗證創(chuàng)建結果。.保存程序的運營結果，并結合程序進行分析。三、實驗內率以下參考程序是按完全二叉樹思想將輸入的字符串生成二叉樹，并通過遍歷來驗證二叉樹創(chuàng)建對的與否，但不能創(chuàng)建非完全二叉樹，請認真研究該程序，然后模仿教材例6.4初始化方式創(chuàng)建二又樹:所有的空指針均用井表達，如教材圖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);/*創(chuàng)建新結點的左子樹?/p->rchild=cre_tree(str,2*i+2,m);/*創(chuàng)建新結點的右子樹*/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("二叉樹已成功創(chuàng)建!結點序列為:");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二叉樹己成功創(chuàng)建？結點序列為：asdfqwer先根遍歷結果：a->s->￡->r->q->d->w->e中根遍歷結果：nFsqawde后根遍歷結果：i'fqsweda葉子數為：4樹的深度為：4交換左右子樹后先序遍歷序列為：a->d->e->w->s->q->f->rPressanykeytocontinue實驗五圖的創(chuàng)建與遍歷.一、實驗目的.掌握圖的含義；.掌握用鄰接矩陣和鄰接表的方法描述圖的存儲結構；.理解并掌握深度優(yōu)先遍歷和廣度優(yōu)先遍歷的存儲結構。二、實驗規(guī)定.認真閱讀和掌握本實驗的參考程序。.按照對圖的操作需要，在創(chuàng)建好圖后再通過遍歷算法驗證創(chuàng)建結果。.保存程序的運營結果，并結合程序進行分析。三、實驗內亂以下參考程序是按鄰接表的方法創(chuàng)建圖,然后用深度優(yōu)先遍歷方法遍歷圖.請認真理解程序,然后實現圖的廣度優(yōu)先遍歷。四、程序流程圖、算法及運營結果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.創(chuàng)建圖*/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("圖已經創(chuàng)建完畢!”)；)/*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.圖的深度環(huán)游*/voidDFS(GRAPHg,intqidian,intmark[])/*從第qidian個點出發(fā)深度優(yōu)先環(huán)游圖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.圖的深度環(huán)游*/voidGraphDFS(GRAPHg)/*深度優(yōu)先環(huán)游圖g中能訪問的各個頂點*/(intqidian,v,vl,mark[maxsize];Printf(*\n深度環(huá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)/*將順序循環(huán)隊列sq置空(初始化)*/(sq—>front=0;sq->rear=0；)intQueuelsEmpty(SEQQUEUEsq)/*假如順序循環(huán)隊列sq為空,成功返回1,否則返回0*/(if(sq.rear==sq.front)return(1);elsreturn(O);intQueueFront(SEQQUEUEsq,DATATYPE*e)/*將順序循環(huán)隊列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.圖的廣度環(huán)游*/voidBFS(GRAPHg,intv,intmark[])/*從v出發(fā)廣度優(yōu)先環(huán)游圖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.圖的廣度環(huán)游*/voidGraphBFS(GRAPHg)/*深度優(yōu)先環(huán)游圖g中能訪問的各個頂點*/(intqidian,v,vl,mark[maxsize];printf("\n廣度環(huá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百己經創(chuàng)建完晌圖的頂點數目為：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一、實驗目的.通過實驗掌握查找的基本概念；.掌握順序查找算法與實現；.掌握折半查找算法與實現。二、實驗規(guī)定.認真閱讀和掌握本實驗的參考程序。.保存程序的運營結果，并結合程序進行分析。三、實驗內容1、建立一個線性表,對表中數據元素存放的先后順序沒有任何規(guī)定。輸入待查數據元素的關鍵字進行查找。為了簡化算法，數據元素只含一個整型關鍵字字段，數據元素的其余數據部分忽略不考慮。建議采用前哨的作用，以提高查找效率。2、查找表的存儲結構為有序表，輸入待查數據元素的關鍵字運用折半杳找方法進行查找。此程序中規(guī)定對整型量關鍵字數據的輸入按從小到大排序輸入。四、程序流程圖、算法及運營結果算法：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);/*在左子表上繼續(xù)查找*/elsereturnBinsch(A,mid+Lhigh,K);/*在右子表上繼續(xù)查找*/)eIsereturn0;/*查找失敗，返回0*/)實驗七各種排序方法的比較一、實驗目的.通過實驗掌握排序的基本概念，對排序的穩(wěn)定性及排序的時間復雜性有深刻的結識。.掌握各種排序方法的基本思想和算法實現。.可以靈活地選用某種排序方法解決問題。二、實驗規(guī)定.認真閱讀和掌握本實驗的參考程序。.保存程序的運營結果，并結合程序進行分析。三、實驗內容編寫一個程序，對所給的數據(程序中給出或通過鍵盤初始化均可)進行排序，規(guī)定盡也許多的選擇不同的排序算法,并顯示排序前和排序后的結果。四、程序流程圖、算法及運營結果算法：常用排序算法總結及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