數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)手冊(cè)

實(shí)驗(yàn)一線性表的次序儲(chǔ)存實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?、掌握用VisualC++上機(jī)調(diào)試次序表的基本方法2、掌握次序表的基本操作，插入、刪除、查找、以及有序次序表的歸并等算法的實(shí)現(xiàn)二、實(shí)驗(yàn)內(nèi)容1、次序表基本操作的實(shí)現(xiàn)[問(wèn)題描繪]當(dāng)我們要在次序表的第i個(gè)地點(diǎn)上插入一個(gè)元素時(shí)，一定先將次序表中第i個(gè)元素以后的全部元素挨次后移一個(gè)地點(diǎn)，以便凌空一個(gè)地點(diǎn)，再把新元素插入到該地點(diǎn)。假如欲刪除第i個(gè)元素時(shí)，也一定把第i個(gè)元素以后的全部元素前移一個(gè)地點(diǎn)。[基本要求]要求生成次序表時(shí)，能夠鍵盤上讀取元素，用次序儲(chǔ)存結(jié)構(gòu)實(shí)現(xiàn)儲(chǔ)存。[實(shí)現(xiàn)提示]要實(shí)現(xiàn)基本操作，可用實(shí)現(xiàn)的基本操作，也可設(shè)計(jì)簡(jiǎn)單的算法實(shí)現(xiàn)。[程序?qū)崿F(xiàn)]#include<>#include<>typedefintDataType;definemaxnum20typedefstruct{intdata[maxnum];intlength;}SeqList;/*插入函數(shù)*/intinsert(SeqList*L,inti,DataTypex)/*將新結(jié)點(diǎn)x插入到次序表L第i個(gè)地點(diǎn)*/{intj;if(i<0||i>(*L).length+1){printf("\ni值不合法!");return0;}if((*L).length>=maxnum-1){printf("\n表滿不可以插入!");return0;}for(j=(*L).length;j>=i;j--)(*L).data[j+1]=(*L).data[j];(*L).data[i]=x;(*L).length++;return1;}/*刪除函數(shù)*/intdelete(SeqList*L,inti)/*從次序L中刪除第i個(gè)結(jié)點(diǎn)*/{intj;if(i<0||i>(*L).length){printf("\n

刪除地點(diǎn)錯(cuò)誤

!");return0;}for(j=i+1;j<=(*L).length;j++)(*L).data[j-1]=(*L).data[j];(*L).length--;return1;}/*生成次序表*/voidcreatlist(SeqList*L){intn,i,j;printf("請(qǐng)輸入次序表L的數(shù)據(jù)個(gè)數(shù)：\n");scanf("%d",&n);for(i=0;i<n;i++){printf("data[%d]=",i);scanf("%d",&((*L).data[i]));}(*L).length=n-1;printf("\n");}/*creatlist*//*輸出次序表L*/printout(SeqList*L){inti;for(i=0;i<=(*L).length;i++){printf("data[%d]=",i);printf("%d",(*L).data[i]);}/*printout*/printf("\n");}main(){SeqList*L;charcmd;inti,t,x;clrscr();creatlist(L);do{printf("\ni,I-----printf("d,D-----printf("q,Q-----

插入\n");刪除\n");退出\n");do{cmd=getchar();}while((cmd!='i')&&(cmd!='I')&&(cmd!='d')&&(cmd!='D')&&(cmd!='q')&&(cmd!='Q'));switch(cmd){case'i':case'I':printf("\nPleaseinputtheDATA:");scanf("%d",&x);printf("\nWhere?");scanf("%d",&i);insert(L,i,x);printout(L);break;case'd':case'D':printf("\nWheretoDelete?");scanf("%d",&i);delete(L,i);printout(L);break;}}while((cmd!='q')&&(cmd!='Q'));}2、有序次序表的歸并[問(wèn)題描繪]已知次序表la和lb中的數(shù)據(jù)元素按非遞減有序擺列，將la和lb表中的數(shù)據(jù)元素，歸并成為一個(gè)新的次序表lc[基本要求]lc中的數(shù)據(jù)元素仍按非遞減有序擺列，并且不損壞la和lb表[程序?qū)崿F(xiàn)]#include<>#definemaxnum20typedefintDataType;typedefstruct{DataTypedata[maxnum];intlength;}SeqList;intMergeQL(SeqListla,SeqListlb,SeqList*lc){inti,j,k;if+1++1>maxnum){printf("\narrayoverflow!");return0;}i=j=k=0;while(i<=&&j<={if[i]<=[j])lc->data[k++]=[i++];elselc->data[k++]=[j++];}/*辦理節(jié)余部分*/while(i<=lc->data[k++]=[i++];while(j<=lc->data[k++]=[j++];lc->length=k-1;return1;}main(){SeqListla={{3,4,7,12,15},4};SeqListlb={{2,5,7,15,18,19},5};SeqListlc;inti;if(MergeQL(la,lb,&lc)){printf("\n");for(i=0;i<=;i++)printf("%4d",[i]);}}實(shí)驗(yàn)二單鏈表實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?、掌握用VisualC++上機(jī)調(diào)試單鏈表的基本方法2、掌握單鏈表的插入、刪除、查找、求表長(zhǎng)以及有序單鏈表的歸并算法的實(shí)現(xiàn)二、實(shí)現(xiàn)內(nèi)容1、單鏈表基本操作的實(shí)現(xiàn)[問(wèn)題描繪]要在帶頭結(jié)點(diǎn)的單鏈表h中第i個(gè)數(shù)據(jù)元素以前插入一個(gè)數(shù)據(jù)元素x，第一需要在單鏈表中找尋到第i-1個(gè)結(jié)點(diǎn)并用指針p指示，而后申請(qǐng)一個(gè)由指針s指示的結(jié)點(diǎn)空間，并置x為其數(shù)據(jù)域值，最后改正第i-1個(gè)結(jié)點(diǎn)，并使x結(jié)點(diǎn)的指針指向第i個(gè)結(jié)點(diǎn)，要在帶頭結(jié)點(diǎn)的單鏈表h中刪除第i個(gè)結(jié)點(diǎn)，第一要計(jì)數(shù)找尋到第i個(gè)結(jié)點(diǎn)并使指針p指向其前驅(qū)第i-1個(gè)結(jié)點(diǎn)，而后刪除第i個(gè)結(jié)點(diǎn)并開(kāi)釋被刪除結(jié)點(diǎn)空間。[基本要求]用鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)實(shí)現(xiàn)儲(chǔ)存[實(shí)現(xiàn)提示]鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)不是隨機(jī)儲(chǔ)存結(jié)構(gòu)，即不可以直接取到單鏈表中某個(gè)結(jié)點(diǎn)，而要從單鏈表的頭結(jié)點(diǎn)開(kāi)始一個(gè)一個(gè)地計(jì)數(shù)找尋。[程序?qū)崿F(xiàn)]include<>include<>typedefcharDataType;typedefstructnode{DataTypedata;structnode*next;

/*/*

結(jié)點(diǎn)的數(shù)據(jù)域結(jié)點(diǎn)的指針域

*/*/}ListNode;voidInit_List(ListNode**L){(*L)=(ListNode*)malloc(sizeof(ListNode));/*產(chǎn)生頭結(jié)點(diǎn)*/(*L)->next=NULL;}intList_Length(ListNode*L){intn=0;ListNode*p=L->next;while(p!=NULL){n++;p=p->next;}returnn;}ListNode*GetNode(ListNode*L,inti){intj;ListNode*p;p=L;j=0;/*while(p->next&&j!=i)/*{p=p->next;j++;}if(i==j)returnp;/*找到了第elsereturnNULL;/*當(dāng)i<0或}

從頭結(jié)點(diǎn)開(kāi)始掃描*/順指針向后掃描,直到p->nexti個(gè)結(jié)點(diǎn)*/i>0時(shí),找不到第i個(gè)結(jié)點(diǎn)*/

為NULL或i=j

為止*/voidInsertList(ListNode*L,DataTypex,inti){ListNode*p,*s;p=GetNode(L,i-1);/*if(p==NULL)/*i<1

找尋第i-1個(gè)結(jié)點(diǎn)*/或i>n+1時(shí)插入地點(diǎn)

i有錯(cuò)*/{printf("positionerror");return;}s=(ListNode*)malloc(sizeof(ListNode));s->data=x;s->next=p->next;p->next=s;}voidDeleteList(ListNode*L,inti){ListNode*p,*r;p=GetNode(L,i-1);/*if(p==NULL||p->next==NULL)/*i<1

找到第i-1或i>n

個(gè)結(jié)點(diǎn)*/時(shí),刪除地點(diǎn)錯(cuò)

*/{printf("positionerror");return;}r=p->next;p->next=r->next;

/*

/*

使r將ai

指向被刪除的結(jié)點(diǎn)從鏈上刪除*/

a*/free(r);}/*使用頭插法成立帶頭結(jié)點(diǎn)鏈表算法*/ListNode*CreatListF(void){charch;ListNode*head=(ListNode*)malloc(sizeof(ListNode));/*ListNode*s;/*工作指針*/

生成頭結(jié)點(diǎn)

*/head->next=NULL;ch=getchar();/*

讀入第

1個(gè)字符*/while(ch!='\n'){s=(ListNode*)malloc(sizeof(ListNode));/*生成新結(jié)點(diǎn)*/s->data=ch;/*將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中s->next=head->next;head->next=s;ch=getchar();/*讀入下一字符*/

*/}returnhead;}/*使用尾插法成立帶頭結(jié)點(diǎn)鏈表算法*/ListNode*CreatListR1(void){charch;ListNode*head=(ListNode*)malloc(sizeof(ListNode));/*ListNode*s,*r;/*工作指針*/r=head;/*尾指針初值也指向頭結(jié)點(diǎn)*/

生成頭結(jié)點(diǎn)

*/while((ch=getchar())!='\n'){s=(ListNode*)malloc(sizeof(ListNode));s->data=ch;r->next=s;r=s;}r->next=NULL;/*終端結(jié)點(diǎn)的指針域置空,或空表的頭結(jié)點(diǎn)指針域置空*/returnhead;}/*復(fù)制鏈表A中的內(nèi)容到表B中*/voidcopy(ListNode*a,ListNode*b){ListNode*pa=a->next;ListNode*u;ListNode*rb=b;while(pa!=NULL){u=(ListNode*)malloc(sizeof(ListNode));u->data=pa->data;rb->next=u;rb=u;pa=pa->next;}rb->next=NULL;}/*輸出帶頭結(jié)點(diǎn)的單鏈表*/voidDisplaySL(ListNode*la,char*comment){ListNode*p;p=la->next;if(p)printf("\n%s\n",comment);while(p){printf("%4c",p->data);p=p->next;}printf("\n");}/*主函數(shù)*/main(){ListNode*la,*lb,*lc,*p;intn,x,i;printf("\n用頭插法成立鏈表la，請(qǐng)輸入節(jié)點(diǎn)內(nèi)容:");la=CreatListF();DisplaySL(la,"重生成鏈la節(jié)點(diǎn)內(nèi)容:");printf("\n鏈表la的長(zhǎng)度:%2d",List_Length(la));printf("\n請(qǐng)輸入要插入的元素:");scanf("%c",&x);printf("\n請(qǐng)輸入要插入的地點(diǎn)：");scanf("%d",&i);InsertList(la,x,i);DisplaySL(la,"插入后鏈la節(jié)點(diǎn)內(nèi)容");printf("\n請(qǐng)輸入要?jiǎng)h除元素的地點(diǎn)：");scanf("%d",&i);DeleteList(la,i);DisplaySL(la,"刪除后鏈la節(jié)點(diǎn)內(nèi)容");printf("\n用尾插法成立鏈表lb，請(qǐng)輸入節(jié)點(diǎn)內(nèi)容:");fflush(stdin);lb=CreatListR1();DisplaySL(lb,"重生成鏈lb節(jié)點(diǎn)內(nèi)容:");Init_List(&lc);copy(la,lc);DisplaySL(lc,"

復(fù)制生成的鏈

lc

節(jié)點(diǎn)內(nèi)容

:");}2、有序單鏈表的歸并[問(wèn)題描繪]已知單鏈表la和lb中的數(shù)據(jù)元素按非遞減有序擺列，將據(jù)元素,歸并為一個(gè)新的單鏈表lc,lc中的數(shù)據(jù)元素仍按非遞減有序擺列。[基本要求]不損壞la表和lb表的結(jié)構(gòu)。[程序?qū)崿F(xiàn)]

la和lb中的數(shù)include<>#include<>#defineNULL0typedefintDataType;typedefstructSLNode{DataTypedata;structSLNode*next;}slnodetype;intMergeSL(slnodetype*la,slnodetype*lb,slnodetype**lc);intCreateSL(slnodetype*la,intn);voidDisplaySL(slnodetype*la,char*comment);main(){slnodetype*la,*lb,*lc,*p;intn,m;la=(slnodetype*)malloc(sizeof(slnodetype));la->next=NULL;lb=(slnodetype*)malloc(sizeof(slnodetype));lb->next=NULL;lc=(slnodetype*)malloc(sizeof(slnodetype));lc->next=NULL;printf("\n輸入鏈la節(jié)點(diǎn)數(shù):");scanf("%d",&n);printf("\n輸入鏈la節(jié)點(diǎn)內(nèi)容:");CreateSL(la,n);DisplaySL(la,"鏈la節(jié)點(diǎn)內(nèi)容:");printf("\n輸入鏈lb節(jié)點(diǎn)數(shù):");scanf("%d",&m);printf("\n輸入鏈lb節(jié)點(diǎn)內(nèi)容:");CreateSL(lb,m);DisplaySL(lb,"鏈lb節(jié)點(diǎn)內(nèi)容:");if(MergeSL(la,lb,&lc))DisplaySL(lc,"getchar();}

合成后的鏈

lc:");intMergeSL(slnodetype*la,slnodetype*lb,slnodetype**lc){slnodetype*pa,*pb,*pc;lc=(slnodetype*)malloc(sizeof(slnodetype));pa=la->next;pb=lb->next;pc=*lc;while(pa&&pb){pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;if(pa->data<=pb->data){pc->data=pa->data;pa=pa->next;}else{pc->data=pb->data;pb=pb->next;}}while(pa)/*插入la鏈的節(jié)余段*/{pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;pc->data=pa->data;pa=pa->next;}/*插入lb鏈的節(jié)余段*/while(pb){pc->next=(slnodetype*)malloc(sizeof(slnodetype));pc=pc->next;pc->data=pb->data;pb=pb->next;}/*生成單鏈表*/intCreateSL(slnodetype*la,intn){inti;slnodetype*p,*q;q=la;for(i=1;i<=n;i++){p=(slnodetype*)malloc(sizeof(slnodetype));scanf("%d",&p->data);q->next=p;q=p;}q->next=NULL;return1;}/*輸出單鏈表*/voidDisplaySL(slnodetype*la,char*comment){slnodetype*p;p=la->next;if(p)printf("\n%s\n",comment);while(p){printf("\n%3d",p->data);p=p->next;}printf("\n");}實(shí)驗(yàn)三循環(huán)鏈表實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?、掌握用VisualC++上機(jī)調(diào)試循環(huán)鏈表的基本方法2、進(jìn)一步掌握循環(huán)單鏈表的插入、刪除、查找算法的實(shí)現(xiàn)二、實(shí)現(xiàn)內(nèi)容1.約瑟夫環(huán)問(wèn)題[問(wèn)題描繪]設(shè)有N個(gè)人圍坐一圈，現(xiàn)從某個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到M的人出列，接著從出列的下一個(gè)人開(kāi)始從頭報(bào)數(shù)，數(shù)到M的人以出列，這樣下去，直到全部人都出列為此。試設(shè)計(jì)確立他們的出列序次序列的程序。[基本要求]選擇單向循環(huán)鏈表作為儲(chǔ)存結(jié)構(gòu)模擬整個(gè)過(guò)程，并挨次輸出列的各人的編號(hào)。[實(shí)現(xiàn)提示

]

程序運(yùn)轉(zhuǎn)以后，第一要求用戶指定初始報(bào)數(shù)的下限值，能夠

n<=30,此題循環(huán)鏈表可不設(shè)頭節(jié)點(diǎn)，并且一定注意空表和非空表的界線。如n=8,m=4時(shí)，若從第一個(gè)人，設(shè)每個(gè)人的編號(hào)挨次為1，2，3，開(kāi)始報(bào)數(shù)，則獲得的出列序次為4，8，5，2，1，3，7，6，以下列圖所示，內(nèi)層數(shù)字表示人的編號(hào)，每個(gè)編號(hào)外層的數(shù)字代表人出列的序號(hào)。[程序?qū)崿F(xiàn)]#include<>#include<>typedefstructnode{intnum;structnode*next;}linklist;linklist*creat(head,n)/*使n個(gè)人圍成一圈，并給每個(gè)人表記號(hào)數(shù)*/linklist*head;intn;{linklist*s,*p;inti;s=(linklist*)malloc(sizeof(linklist));head=s;s->num=1;p=s;for(i=2;i<=n;i++){s=(linklist*)malloc(sizeof(linklist));s->num=i;p->next=s;p=s;}p->next=head;return(head);}/*creat*/linklist*select(linklist*head,intm){linklist*p,*q;inti,t;p=head;t=1;q=p;/*q為p的前趨指針*/p=p->next;do{t=t+1;/*if(t%m==0)

報(bào)一次數(shù)

*/{printf("%4d",p->num);q->next=p->next;free(p);p=q->next;}else{q=p;p=p->next;}}while(q!=p);head=p;printf("%4d",p->num);return(head);}/*select*/main(){intn,m;linklist*head;printf("\ninputthetotalnumber:n=");scanf("%d",&n);printf("\ninputthenumbertocall:m=");scanf("%d",&m);head=creat(head,n);head=select(head,m);printf("\nthelastoneis:%d",head->num);}/*main*/思慮題：編程實(shí)現(xiàn)兩個(gè)循環(huán)單鏈表的歸并。實(shí)驗(yàn)四棧、行列的實(shí)現(xiàn)及應(yīng)用一、實(shí)驗(yàn)?zāi)康?、掌握棧和行列的次序儲(chǔ)存結(jié)構(gòu)和鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)，以便在實(shí)質(zhì)背景下靈巧運(yùn)用。2、掌握棧和行列的特色，即先進(jìn)后出與先進(jìn)先出的原則。3、掌握棧和行列的基本操作實(shí)現(xiàn)方法。二、實(shí)驗(yàn)內(nèi)容1、實(shí)現(xiàn)棧的次序儲(chǔ)存defineMAXSIZE100typedefintElemType;typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*s){s->top=0;return1;}intStackEmpty(SeqStack*s){if(s->top==0)return1;elsereturn0;}intStackFull(SeqStack*s){if(s->top==MAXSIZE-1)return1;elsereturn0;}voidPush(SeqStack*s,intx){if(StackFull(s)){printf("thestackisoverflow!\n");return0;}else{s->data[s->top]=x;s->top++;}}voidDisplay(SeqStack*s){if(s->top==0)printf("thestackisempty!\n");else{while(s->top!=0){printf("%d->",s->data[s->top]);s->top=s->top-1;}}}ElemTypePop(SeqStack*s){if(StackEmpty(s))return0;elsereturns->data[--s->top];}ElemTypeStackTop(SeqStack*s){inti;if(StackEmpty(s))return0;else{i=s->top-1;returns->data[i];}/*

返回棧頂元素的值，但不改變棧頂指針

*/}main(SeqStack*p){intn,i,k,h,x1,x2,select;printf("createaemptystack!\n");InitStack(p);printf("inputastacklength:\n");scanf("%d",&n);for(i=0;i<n;i++){printf("inputastackvalue:\n");scanf("%d",&k);Push(p,k);}printf("select1:Display()\n");printf("select2:Push()\n");printf("select3:Pop()\n");printf("select4:StackTop()\n");printf("inputayourselect(1-4):\n");scanf("%d",&select);switch(select){case1:{display(p);break;}case2:{printf("inputapushavalue:\n");scanf("%d",&h);Push(p,h);display(p);break;}case3:{x1=Pop(p);printf("x1->%d\n",x1);display(p);break;}case4:{x2=StackTop(p);printf("x2->%d",x2);break;}}}2、利用棧實(shí)現(xiàn)數(shù)制變換#defineMAXSIZE100typedefintElemType；/*將次序棧的元素定義為整型*/typedefstruct{ElemTypedata[MAXSIZE];inttop;}SeqStack;voidInitStack(SeqStack*s){s->top=0;return1;}intStackEmpty(SeqStack*s){if(s->top==0)return1;elsereturn0;}intStackFull(SeqStack*s){if(s->top==m-1)return1;elsereturn0;}voidPush(SeqStack*s,intx){if(StackFull(s)){printf("thestackisoverflow!\n");return0;}else{s->data[s->top]=x;s->top++;}}ElemTypePop(SeqStack*s){ElemTypey;if(StackEmpty(s)){printf("thestackisempty!\n");return0;}else{y=s->data[s->top];s->top=s->top-1;returny;}}ElemTypeStackTop(SeqStack*s){if(StackEmpty(s))return0;elsereturns->data[s->top];}voidDec_to_Ocx(intN)/*n

是非負(fù)的十進(jìn)制整數(shù)，輸出等值的八進(jìn)制數(shù)

*/{SeqStack*S；

/*

定義一個(gè)次序棧

*/ElemTypex；Init_SeqStack(S)

；

/*

初始化棧*/if(N<0){printf("\nError,Thenumbermustbeover0

。")；return

；}if(!N)Push(S,0)

；while(N){Push(SN=N/8

/*自右向左產(chǎn)生八進(jìn)制的各位數(shù)字，并將其進(jìn)棧，N%8)；/*余數(shù)入棧*/；/*商作為被除數(shù)*/

*/}printf("Number%dconvertedtoOCT:",N);while(StackEmpty(S))/*棧非空時(shí)退棧輸出

*/{x=Pop(S)

；printf(

“%d”

,x)

；}printf("\n");}main(){intn;printf("InputanumbertoconverttoOCT:\n");scanf("%d",&n);Dec_to_Ocx(n);}3、實(shí)現(xiàn)循環(huán)行列的次序儲(chǔ)存#definemaxsize100typedefstruct{intdata[maxsize];intfront;intrear;}seqqueue;intsqinit(seqqueue*p){p->front=0;p->rear=0;return1;}intenqueue(seqqueue*q,inte){if((q->rear+1)%maxsize==q->front)return0;elseq->data[q->rear]=e;q->rear=(q->rear+1)%maxsize;return1;}intdequeue(seqqueue*q){inte;if(q->front==q->rear)return0;e=q->data[q->front];q->front=(q->front+1)%maxsize;returne;}intempty(seqqueue*q){intv;if(q->front==q->rear)v=1;elsev=0;returnv;}intgethead(seqqueue*q){inte;if(q->front==q->rear)e=-1;elsee=q->data[q->front];returne;}voiddisplay(seqqueue*q){ints;s=q->front;printf("thesequeueisdisplay:\n");if(q->front==q->rear)printf("thesequeueisempty!");else{while(s<q->rear){printf("->%d",q->data[s]);s=(s+1)%maxsize;}printf("\n");}}main(seqqueue*head){intn,i,m,x,y,select,xq;printf("createaemptysequeue\n");sqinit(head);printf("pleaseinputthesequeuelength:\n");scanf("%d",&n);for(i=0;i<n;i++){printf("pleaseinputasequeuevalue:\n");scanf("%d",&m);enqueue(head,m);}printf("head->rear:%d\n",head->rear);printf("head->front:%d\n",head->front);display(head);printf("select1****enqueue()\n");printf("select2****dequeue()\n");printf("select3****empty()\n");printf("select4****gethead()\n");printf("select5****display()\n");printf("pleaseselect(1--5):");scanf("%d",&select);switch(select){case1:{printf("pleaseinputavalue:\n");scanf("%d",&x);enqueue(head,x);display(head);break;}case2:{dequeue(head);display(head);break;}case3:{if(empty(head))printf("thesequeueisempty");elseprintf("thesequeueisfull");}case4:{y=gethead(head);printf("outputheadvalue:%d\n",y);break;}case5:{display(head);break;}}}實(shí)驗(yàn)五串及數(shù)組的實(shí)驗(yàn)一、實(shí)驗(yàn)?zāi)康?、認(rèn)識(shí)串及數(shù)組的兩種儲(chǔ)存方法，掌握數(shù)組在作為儲(chǔ)存結(jié)構(gòu)中的地點(diǎn)計(jì)算方法。2、認(rèn)識(shí)稀少矩陣的兩種壓縮儲(chǔ)存方法的特色和合用范圍，領(lǐng)悟稀少矩陣運(yùn)算采納的辦理方法。二、實(shí)驗(yàn)內(nèi)容1、次序串的基本操作#defineMaxSize100typedefstruct{charstr[MaxSize];intlen;}strtype;voidassign(strtype*s,chart[]){inti=0;while(t[i]!='\0'){s->str[i]=t[i];i++;}s->str[i]='\0';s->len=i;}voidstrcopy(strtype*s,strtypet){inti;for(i=0;i<=;i++)s->str[i]=[i];}intlength(strtypes){return;}intequal(strtypes,strtypet){inti=0;if!=return(0);else{for(i=0;i<;i++)if[i]!=[i])return(0);return(1);}}strtypeconcat(strtypes,strtypet){strtyper;inti,j;for(i=0;i<;i++)[i]=[i];for(j=0;j<=;j++)[+j]=[j];=i+j;return(r);}intindex(strtypes,strtypet){inti,j,k;for(i=0;[i];i++)for(j=i,k=0;[j]==[k];j++,k++)if(![k+1])return(i);return(-1);}strtypesubstr(strtypes,inti,intk){strtypet;intj;for(j=i;j<i+k;j++)[j-i]=[j];=k;[]='\0';return(t);}voidinsert(strtype*s,inti,strtypet){strtyper;intj;if(i>s->len)printf("

地點(diǎn)參數(shù)值錯(cuò)誤

\n");else{for(j=i;j<s->len;j++)

/*

將s的第

i個(gè)地點(diǎn)以后的字串復(fù)制到

r中*/[j-i]=s->str[j];=j-i;[]='\0';for(j=0;j<;j++)

/*

將t

串通接到

s的第

i

個(gè)字符以后

*/s->str[i+j]=[j];for(j=0;j<;j++)

/*

將r

串通接到

s串以后*/s->str[i++j]=[j];s->len=s->len+;

/*

改正

s串長(zhǎng)度*/s->str[s->len]='\0';}}voiddelete(strtype*s,inti,intk){intj;if(i>s->len||i+k>s->len)printf("地點(diǎn)參數(shù)值錯(cuò)誤\n");else{for(j=i+k;j<s->len;j++)

/*

將s的第

i+k

個(gè)地點(diǎn)以后的字串前移

k位*/s->str[j-k]=s->str[j];s->len=s->len-k;

/*

改正

s的長(zhǎng)度*/s->str[s->len]='\0';}}strtypereplace(strtypes,strtypet,strtypev){inti;i=index(s,t);while(i>=0){delete(&s,i,;insert(&s,i,v);i=index(s,t);}return(s);}voiddisplay(strtypes){printf("字符串:%s\n",;}main(){strtypes,t,r,v;assign(&s,"aababababad");assign(&t,"aba");assign(&v,"121");display(s);display(t);display(v);printf("sprintf("t

長(zhǎng)度=%d\n",length(s));與v連結(jié)");display(concat(t,v));printf("s

中的

t

替代成

v后的");display(replace(s,t,v));}2、三元組稀少矩陣的基本操作#include<>#defineMax100#defineM3#defineN3#defineK3typedefintsmat[Max][3];voiddisplay();voidcreatmat(intA[M][N],smatB)/*A是一個(gè)稀少矩陣,B是產(chǎn)生的相對(duì)應(yīng)的三元組儲(chǔ)存*/{inti,j,k=1;for(i=0;i<M;i++)/*按行優(yōu)先次序掃描A的元素,不為0者存入B中*/for(j=0;j<N;j++)if(A[i][j]!=0){B[k][0]=i;B[k][1]=j;B[k][2]=A[i][j];k++;}B[0][0]=M;B[0][1]=N;B[0][2]=k-1;/*

存入非0元素個(gè)數(shù)

*/}intfindval(smatA,intx){inti,t;t=A[0][2];/*非0元素個(gè)數(shù)i=1;while(i<=t&&A[i][2]!=x)i++;/*if(i<=t)return(1);elsereturn(0);

*/

查找等于

x的元素值

*/}voidtrsmat(smatA,smatB)/*A

是稀少矩陣的三元組形式

,B是寄存A的轉(zhuǎn)置矩陣的三元組

*/{intm,n,p,q,t,col;/*m:A中的行數(shù);n:A中的列數(shù);t:A/*q:B的下一個(gè)項(xiàng)地點(diǎn);p:A

的非0元素個(gè)數(shù)的目前項(xiàng)*/

*/m=A[0][0];n=A[0][1];t=A[0][2];B[0][0]=n;B[0][1]=m;B[0][2]=t;/*if(t>0)/*{

產(chǎn)生第0行的結(jié)果非0元素才做轉(zhuǎn)置

*/*/q=1;for(col=0;col<n;col++)

/*

按列轉(zhuǎn)置

*/for(p=1;p<=t;p++)if(A[p][1]==col){B[q][0]=A[p][1];B[q][1]=A[p][0];B[q][2]=A[p][2];q++;}}}voidmatadd(smatA,smatB,smatC){inti=1,j=1,k=1;while(i<=A[0][2]&&j<=B[0][2])/*若A的目前項(xiàng)的行號(hào)等于B的目前項(xiàng)的行號(hào),則比較其列號(hào)/*存入C中,假如列號(hào)也相等,則將對(duì)應(yīng)的元素值相加后存入

,將較小列的項(xiàng)C中*/

*/if(A[i][0]==B[j][0])if(A[i][1]<B[j][1]){C[k][0]=A[i][0];C[k][1]=A[i][1];C[k][2]=A[i][2];k++;i++;}elseif(A[i][1]>B[j][1]){C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=B[j][2];k++;j++;}else{C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=A[i][2]+B[j][2];k++;i++;j++;}elseif(A[i][0]<B[j][0])/*若A的目前項(xiàng)的行號(hào)小于B的目前項(xiàng)的行號(hào),則將A的項(xiàng)存入C中*/{C[k][0]=A[i][0];C[k][1]=A[i][1];C[k][2]=A[i][2];k++;i++;}else/*若A的目前項(xiàng)的行號(hào)大于B的目前項(xiàng)的行號(hào),則將B的項(xiàng)存入C中*/{C[k][0]=B[j][0];C[k][1]=B[j][1];C[k][2]=B[j][2];k++;j++;}C[0][0]=A[0][0];/*產(chǎn)生第0行的結(jié)果*/C[0][1]=A[0][1];C[0][2]=k-1;}voidmatmul(intm,intn,intk,smatA,smatB,smatC){inti,j,l,p=1,s;for(i=0;i<m;i++)for(j=0;j<k;j++){s=0;/*計(jì)算C[i][j]之值*/for(l=0;l<n;l++)s=s+value(A,i,l)*value(B,l,j);if(s!=0)/*產(chǎn)生一個(gè)三元組元素*/{C[p][0]=i;C[p][1]=j;C[p][2]=s;p++;}}C[0][0]=m;/*產(chǎn)生第0行的結(jié)果*/C[0][1]=k;C[0][2]=p-1;}intvalue(smatC,inti,intj)/*

用在matmul函數(shù)之中

,計(jì)算C[i][j]

的值*/{intk=1;while(k<=C[0][2]&&(C[k][0]!=i||C[k][1]!=j))k++;if(k<=C[0][2])return(C[k][2]);/*elsereturn(0);/*

找到了返回該地點(diǎn)的值未找到說(shuō)明該元素為

*/0*/}voiddisplay(char*s,smatA){inti;printf("%s三元組:\n\tRowColVal\n",s);for(i=1;i<=A[0][2];i++)printf("\t%4d%4d%4d\n",A[i][0],A[i][1],A[i][2]);}main(){intA[M][N]={{0,1,0},{6,0,0},{1,0,0}};intB[M][N]={{1,2,0},{0,4,0},{0,3,0}};smatC,D,E,F,G;creatmat(A,C);creatmat(B,D);display("C

矩陣",C);printf("C(0,1)處的值:%d\n",value(C,0,1));printf("元素3能否存在:%d\n",findval(C,2));matadd(C,D,E);display("E=A+B",E);matmul(M,N,K,C,D,F);display("F=A×B",F);trsmat(C,G);display("C'",G);}c實(shí)驗(yàn)七查找一、實(shí)驗(yàn)?zāi)康?、掌握查找的不一樣方法，并能用高級(jí)語(yǔ)言實(shí)現(xiàn)查找算法。2、嫻熟掌握次序表的查找方法和有序次序表的折半查找算法以及靜態(tài)查找樹的結(jié)構(gòu)方法和查找算法。3、掌握二叉排序樹的生成、插入、刪除、輸出運(yùn)算。二、實(shí)驗(yàn)內(nèi)容1、次序表的次序查找#include<>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intseq_search(KEYTYPEk,SSTABLE*st){/*次序表上查找元素*/intj;j=st->len;st->r[0].key=k;while(st->r[j].key!=k)returnj;

/*/*st->r[0]j--;/*/*j=0,

次序表元素個(gè)數(shù)*/單元作為監(jiān)督哨*/次序表從后向前查找*/找不到；j<>0找到*/}main(){SSTABLEa;inti,j,k;printf("請(qǐng)輸入次序表元素(整型量)，用空格分開(kāi)，j=0;k=1;i=0;scanf("%d",&i);while(i!=-99){j++;[k].key=i;k++;scanf("%d",&i);}/*=j;printf("\n次序表元素列表顯示：");for(i=1;i<=;i++)printf("%d",[i].key);printf("\n");printf("\n輸入待查元素重點(diǎn)字:");scanf("%d",&i);k=seq_search(i,&a);if(k==0)printf("表中待查元素不存在\n\n");elseprintf("表中待查元素存在,為第%d個(gè)元素\n"}

-99為結(jié)束標(biāo)記輸入次序表元素，k);

：");*/2、有序次序表的二分查找的遞歸算法#include<>#defineKEYTYPEint#defineMAXSIZE100typedefstruct{KEYTYPEkey;}SSELEMENT;typedefstruct{SSELEMENTr[MAXSIZE];intlen;}SSTABLE;intsearch_bin(KEYTYPEk,intlow,inthigh){/*有序表上二分法查找,遞歸算法*/intmid;mid=-1;if(low<=high)/*low表示目前表中第1個(gè)元素所在下標(biāo)*//*high表示目前表中最后一個(gè)元素所在下標(biāo)*/{mid=(low+high)/2;/*mid表示目前表中中間一個(gè)元素所在下標(biāo)*/if[mid].key<k)mid=search_bin(k,mid+1,high);/*二分法遞歸查找*/elseif[mid].key>k)mid=search_bin(k,low,high-1);}returnmid;/*mid=-1查找不行功；mid!=-1查找成功*/}main(){SSTABLEa;inti,j,k;printf("請(qǐng)輸入有序表元素，元素為整型量（從小到大輸入），用空格分開(kāi)，-99為結(jié)束標(biāo)記：");j=0;k=1;i=0;scanf("%d",&i);while(i!=-99){j++;[k].key=i;k++;scanf("%d",&i);}/*輸入有序表元素*/=j;printf("\n有序表元素列表顯示：");for(i=1;i<=;i++)printf("%d",[i]);printf("\n");printf("\n輸入待查元素重點(diǎn)字:");scanf("%d",&i);k=search_bin(i,1,;if(k==-1)printf("表中待查元素不存在\n\n");elseprintf("表中待查元素存在,為第%d個(gè)元素\n"，k);}3、在用拉鏈法解決矛盾的散列表上插入元素#include<>#include<>#defineKEYTYPEint#defineMAXSIZE100typedefstructnode{KEYTYPEkey;structnode*next;}CHAINHASH;voidcreat_chain_hash(CHAINHASH*HTC[]){/*成立開(kāi)散列表*/CHAINHASH*p;inti,j;scanf("%d",&i);/*輸入開(kāi)散列表元素重點(diǎn)字值*/while(i!=-99){j=i%13;/*散列函數(shù)：ADD(rec(key))=keyMOD13*/p=(CHAINHASH*)malloc(sizeof(CHAINHASH));/*

生成結(jié)點(diǎn)，掛入開(kāi)散列表中

*/p->next=HTC[j];p->key=i;HTC[j]=p;scanf("%d",&i);}

/*

輸入開(kāi)散列表元素重點(diǎn)字值

*/}voidprint_chain_hash(CHAINHASH*HTC[]){/*顯示開(kāi)散列表*/inti;CHAINHASH*p;for(i=0;i<13;i++){if(HTC[i]==NULL)printf("%3d|^\n",i);else{p=HTC[i];printf("%3d|->",i);while(p!=NULL){printf("%5d->",p->key);p=p->next;}printf("\n");}}}intsearch_chain_hash(CHAINHASH*HTC[],intk){/*開(kāi)散列表中查找元素*/CHAINHASH*p;intj;j=k%13;/*散列函數(shù)：ADD(rec(key))=keyMOD13*/p=HTC[j];if(p!=NULL)/*開(kāi)散列表中查找元素*/{while((p->key!=k)&&(p->next!=NULL))p=p->next;if(p->key==k)return1;/*查找成功，返回1*/elsereturn0;/*查找不行功，返回0*/}elsereturn0;}insert_chain_hash(CHAINHASH*HTC[],inti){/*元素插入散列表中

*/CHAINHASH*p;intj;j=i%13;/*

散列函數(shù)：

ADD(rec(key))=keyMOD13*/p=(CHAINHASH*)malloc(sizeof(CHAINHASH));/*生成結(jié)點(diǎn)，掛入開(kāi)散列表中*/p->next=HTC[j];p->key=i;HTC[j]=p;}main(){CHAINHASH*HTC[MAXSIZE];inti,k;printf("\n成立開(kāi)散列表\n\n");for(i=0;i<MAXSIZE;i++)HTC[i]=NULL;printf("請(qǐng)輸入開(kāi)散列表元素重點(diǎn)字值,重點(diǎn)字為正整型量，用空格分開(kāi)，-99為結(jié)束標(biāo)記:");creat_chain_hash(HTC);printf("顯示成立的開(kāi)散列表:\n\n");print_chain_hash(HTC);printf("\n輸入待插入元素重點(diǎn)字:");scanf("%d",&i);k=search_chain_hash(HTC,i);if(k==0){printf("表中待插入元素不存在,可插入散列表中\(zhòng)n\n");insert_chain_hash(HTC,i);printf("顯示插入后的開(kāi)散列表:\n\n");print_chain_hash(HTC);}elseprintf("表中待插入元素存在，不行插入散列表中\(zhòng)n\n");}實(shí)驗(yàn)八排序一、實(shí)驗(yàn)?zāi)康?、掌握常用的排序方法，并能用高級(jí)語(yǔ)言實(shí)現(xiàn)排序算法。2、深刻理解排序的定義和各樣排序方法的特色，并能加以靈巧運(yùn)用。3、認(rèn)識(shí)各樣方法的排序過(guò)程及依照的原則，并掌握各樣排序方法的時(shí)間復(fù)雜度的剖析方法。二、實(shí)驗(yàn)內(nèi)容1、排序綜合練習(xí)#include<>#defineKEYTYPEint#defineMAXSIZE100intcreateList(RECNODE*r){intj,k;printf("\n\n輸入待排序數(shù)據(jù)(整數(shù)，以空格分開(kāi)，0scanf("%d",&j);

結(jié)束):");

k=

0;while(j!=0){k++;r[k].key=j;scanf("%d",&j);}returnk;}frontdisplayList(RECNODE*r,intn){inti;printf("\n排序前:");for(i=0;i<n;i++)printf("%d",r[i+1].key);printf("\n\n");}reardisplayList(RECNODE*r,intn){inti;printf("\n\n排序后:");for(i=0;i<n;i++)printf(