《軟件技術(shù)基礎(chǔ)》實(shí)驗(yàn)指導(dǎo)

PAGE1PAGE32說明每個(gè)實(shí)驗(yàn)題目含有一個(gè)main函數(shù)和一些函數(shù)，與實(shí)驗(yàn)題目相關(guān)的基本運(yùn)算的函數(shù)定義和main函數(shù)定義的代碼在附錄以及對(duì)應(yīng)的文件夾中給出，供上機(jī)實(shí)驗(yàn)參考使用。對(duì)于每個(gè)題目，只需要根據(jù)題目要求設(shè)計(jì)算法，補(bǔ)充函數(shù)定義，然后對(duì)程序進(jìn)行編譯、調(diào)試。實(shí)驗(yàn)一線性表實(shí)驗(yàn)?zāi)康氖煜ぞ€性表的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)掌握線性表的基本運(yùn)算能夠利用線性表的基本運(yùn)算完成線性表應(yīng)用的運(yùn)算實(shí)驗(yàn)內(nèi)容設(shè)有一個(gè)線性表E={e1,e2,…,en-1,en}，設(shè)計(jì)一個(gè)算法，將線性表逆置，即使元素排列次序顛倒過來，成為逆線性表E’={en,en-1,…,e2,e1}，要求逆線性表占用原線性表空間，并且用順序表和單鏈表兩種方法表示，分別用兩個(gè)程序來完成。（文件夾：順序表逆置、單鏈表逆置）已知由不具有頭結(jié)點(diǎn)的單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素（字母、數(shù)字和其他字符），試編寫算法構(gòu)造三個(gè)以循環(huán)鏈表表示的線性表，使每個(gè)表中只含有同一類的字符，且利用原表中的結(jié)點(diǎn)空間，頭結(jié)點(diǎn)可另辟空間。（文件夾：分解單鏈表）實(shí)驗(yàn)二棧和隊(duì)列實(shí)驗(yàn)?zāi)康氖煜：完?duì)列的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)掌握棧和隊(duì)列的基本運(yùn)算能夠利用棧和隊(duì)列的基本運(yùn)算完成棧和隊(duì)列應(yīng)用的運(yùn)算實(shí)驗(yàn)內(nèi)容設(shè)單鏈表中存放有n個(gè)字符，試編寫算法，判斷該字符串是否有中心對(duì)稱的關(guān)系，例如xyzzyx是中心對(duì)稱的字符串。（提示：將單鏈表中的一半字符先依次進(jìn)棧，然后依次出棧與單鏈表中的另一半字符進(jìn)行比較。）（文件夾：判字符串中心對(duì)稱）假設(shè)以數(shù)組sequ[m]存放循環(huán)隊(duì)列的元素，同時(shí)設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和內(nèi)含元素的個(gè)數(shù)。編寫實(shí)現(xiàn)該循環(huán)隊(duì)列的入隊(duì)和出隊(duì)操作的算法。提示：隊(duì)空的條件：sq->quelen==0；隊(duì)滿的條件：sq->quelen==m。（文件夾：循環(huán)隊(duì)列）實(shí)驗(yàn)三串實(shí)驗(yàn)?zāi)康氖煜ご捻樞虼鎯?chǔ)結(jié)構(gòu)掌握串的基本運(yùn)算及應(yīng)用實(shí)驗(yàn)內(nèi)容1．串采用順序存儲(chǔ)結(jié)構(gòu)，編寫樸素模式匹配算法，查找在串中是否存在給定的子串。（文件夾：模式匹配）2．若S是一個(gè)采用順序結(jié)構(gòu)存儲(chǔ)的串，利用C的庫(kù)函數(shù)strlen和strcpy（或strncpy）編寫一算法voidSteDelete(char*S,intI,intm)，要求從S中刪除從第i個(gè)字符開始的連續(xù)m個(gè)字符。若i≥strlen(S)，則沒有字符被刪除；若i+m≥strlen(S)，則將S中從位置i開始直至末尾的字符均刪除。（文件夾：刪除子串）實(shí)驗(yàn)四數(shù)組實(shí)驗(yàn)?zāi)康氖煜?shù)組的結(jié)構(gòu)掌握矩陣的壓縮存儲(chǔ)能夠?qū)?shù)組和矩陣的壓縮存儲(chǔ)進(jìn)行運(yùn)算實(shí)驗(yàn)內(nèi)容若在矩陣Am×n中存在一個(gè)元素A[i][j]，其滿足A[i][j]是第i行元素中最小值，且又是第j列元素中最大值，則稱此元素為該矩陣的一個(gè)馬鞍點(diǎn)。用二維數(shù)組存儲(chǔ)矩陣Am×n，設(shè)計(jì)算法求出矩陣中所有馬鞍點(diǎn)。（文件夾：找馬鞍點(diǎn)）A和B是兩個(gè)n×n階的對(duì)稱矩陣，以行為主序輸入對(duì)稱矩陣的下三角元素，壓縮存儲(chǔ)存入一維數(shù)組A和B，編寫一個(gè)算法計(jì)算對(duì)稱矩陣A和B的乘積，結(jié)果存入二維數(shù)組C。（文件夾：對(duì)稱矩陣相乘）實(shí)驗(yàn)五樹實(shí)驗(yàn)?zāi)康氖煜ざ鏄涞逆準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)掌握二叉樹的建立、深度優(yōu)先遞歸遍歷等算法能夠利用遍歷算法實(shí)現(xiàn)一些應(yīng)用實(shí)驗(yàn)內(nèi)容已知二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，編寫一個(gè)算法交換二叉樹所有左、右子樹的位置，即結(jié)點(diǎn)的左子樹變?yōu)榻Y(jié)點(diǎn)的右子樹，右子樹變?yōu)樽笞訕洹＃ㄎ募A：交換左右子樹）采用二叉鏈表結(jié)構(gòu)存儲(chǔ)一棵二叉樹，編寫一個(gè)算法統(tǒng)計(jì)該二叉樹中結(jié)點(diǎn)總數(shù)及葉子結(jié)點(diǎn)總數(shù)。（文件夾：統(tǒng)計(jì)二叉樹結(jié)點(diǎn)）實(shí)驗(yàn)六圖實(shí)驗(yàn)?zāi)康氖煜D的鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)熟悉圖的鄰接矩陣和鄰接表的建立算法掌握?qǐng)D的遍歷算法實(shí)驗(yàn)內(nèi)容無向圖采用鄰接矩陣存儲(chǔ)，編寫深度優(yōu)先搜索遍歷算法，從不同的頂點(diǎn)出發(fā)對(duì)無向圖進(jìn)行遍歷。（文件夾：無向圖鄰接矩陣）BBCADEFGH實(shí)驗(yàn)七排序?qū)嶒?yàn)?zāi)康氖煜じ鞣N內(nèi)部排序算法能夠編寫程序顯示排序過程中各趟排序的結(jié)果能夠編寫一些排序的算法實(shí)驗(yàn)內(nèi)容采用希爾排序方法對(duì)順序表中的證型數(shù)據(jù)進(jìn)行排序，設(shè)計(jì)希爾排序算法并顯示每趟排序的結(jié)果。（文件夾：希爾排序）編寫一個(gè)雙向起泡的排序算法，即在排序過程中交替改變掃描方向，同時(shí)顯示各趟排序的結(jié)果。（文件夾：雙向起泡排序）實(shí)驗(yàn)八查找實(shí)驗(yàn)?zāi)康氖煜ぞ€性表、二叉排序樹和散列表的查找能夠編寫一些查找的算法實(shí)驗(yàn)內(nèi)容18個(gè)記錄的關(guān)鍵字為22、12、13、8、9、20、33、42、44、38、24、48、60、58、74、49、86、53，編寫分塊查找的算法進(jìn)行查找。（文件夾：分塊查找）編寫一個(gè)判別給定的二叉樹是否為二叉排序樹的算法，設(shè)二叉樹以二叉鏈表存儲(chǔ)表示，結(jié)點(diǎn)的數(shù)據(jù)域只存放正整數(shù)。（文件夾：判斷二叉排序樹）附錄：原代碼實(shí)驗(yàn)一：第1題（1）//順序表逆置的程序代碼#include<stdio.h>#include<malloc.h>//順序表結(jié)構(gòu)類型定義typedefchardatatype;constintmaxsize=1024;typedefstruct{datatypedata[maxsize];intlast;}sequenlist;voidcreate(sequenlist*&);voidprint(sequenlist*);voidinvert(sequenlist*);voidmain(){ sequenlist*L; create(L);//建立順序表 print(L);//輸出順序表 invert(L);//調(diào)用順序表逆值的函數(shù) print(L);//輸出順序表}//建立順序表voidcreate(sequenlist*&L){ L=(sequenlist*)malloc(sizeof(sequenlist)); L->last=0; charch; while((ch=getchar())!='*') { L->last++; L->data[L->last]=ch; }}//輸出順序表voidprint(sequenlist*L){ for(inti=1;i<=L->last;i++) printf("%2c",L->data[i]); printf("\n");}//順序表逆置voidinvert(sequenlist*L){inti;chara[maxsize];for(i=1;i<L->last+1-i;i++){ a[i]=L->data[i];L->data[i]=L->data[L->last+1-i];L->data[L->last+1-i]=a[i];}}實(shí)驗(yàn)一：第1題（2）//單鏈表逆置的程序代碼#include<malloc.h>#include<stdio.h>//單鏈表結(jié)構(gòu)類型定義typedefchardatatype;typedefstructnode{ datatypedata; structnode*next;}linklist;voidcreate(linklist*&);voidprint(linklist*);voidinvert(linklist*);voidmain(){ linklist*head; create(head); print(head); invert(head);//調(diào)用單鏈表逆置的函數(shù) print(head);}//采用尾插法建立具有頭結(jié)點(diǎn)的單鏈表voidcreate(linklist*&head){ charch; linklist*s,*r; head=(linklist*)malloc(sizeof(linklist)); r=head; while((ch=getchar())!='*') { s=(linklist*)malloc(sizeof(linklist)); s->data=ch; r->next=s; r=s; } r->next=NULL;}//輸出單鏈表voidprint(linklist*head){ linklist*p=head->next; while(p!=NULL) { printf("%2c",p->data); p=p->next; } printf("\n");}//單鏈表逆置voidinvert(linklist*head){ linklist*p,*q; //定義結(jié)構(gòu)體指針p,q p=head->next; head->next=NULL; while(p!=NULL) { q=p->next;//q指向p的后繼結(jié)點(diǎn) p->next=head->next; head->next=p; p=q; }}實(shí)驗(yàn)一：第2題//分解單鏈表的程序代碼#include<stdio.h>#include<malloc.h>//鏈表結(jié)構(gòu)類型定義typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}linklist;voidcreate(linklist*&);voidresolve(linklist*,linklist*,linklist*,linklist*);voidinsert(linklist*,linklist*);voidprint1(linklist*);voidprint2(linklist*);voidmain(){linklist*head,*letter,*digit,*other;create(head);print1(head);letter=(linklist*)malloc(sizeof(linklist));//建立3個(gè)空循環(huán)鏈表letter->next=letter;digit=(linklist*)malloc(sizeof(linklist));digit->next=digit;other=(linklist*)malloc(sizeof(linklist));other->next=other;resolve(head,letter,digit,other);//調(diào)用分解單鏈表的函數(shù)print2(letter);//輸出循環(huán)鏈表print2(digit);print2(other);}//建立單鏈表voidcreate(linklist*&head){datatypex;linklist*s,*r;head=newlinklist;r=head;while((x=getchar())!='$'){ s=(linklist*)malloc(sizeof(linklist));s->data=x; r->next=s; r=s;}r->next=NULL;}//在循環(huán)鏈表中插入voidinsert(linklist*h,linklist*p){linklist*q=h;while(q->next!=h)q=q->next;q->next=p;p->next=h;}//輸出單鏈表voidprint1(linklist*head){linklist*p=head->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}//輸出循環(huán)鏈表voidprint2(linklist*head){linklist*p=head->next;while(p!=head){ printf("%c",p->data);p=p->next;}printf("\n");}//按字母、數(shù)字、其它字符分解單鏈表voidresolve(linklist*head,linklist*letter,linklist*digit,linklist*other){linklist*p=head->next;linklist*q=letter;linklist*r=digit;linklist*v=other;linklist*s;while(p!=NULL){ s=(linklist*)malloc(sizeof(linklist));s->data=p->data; if(s->data>=65&&s->data<=122)//如果為字母 { s->next=letter; q->next=s; q=q->next; } elseif(s->data>=48&&s->data<=57)//如果為數(shù)字 { s->next=digit; r->next=s; r=r->next; } else//其他{ s->next=other; v->next=s; v=v->next; } //free(s);為什么不能釋放呢？？ p=p->next;}}實(shí)驗(yàn)二：第1題//判字符串中心對(duì)稱的程序代碼#include<stdio.h>#include<malloc.h>#include<string.h>//定義單鏈表結(jié)構(gòu)類型typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}linklist;//定義順序棧結(jié)構(gòu)類型constintmaxsize=40;typedefstruct{datatypeelements[maxsize];inttop;}stack;voidsetnull(stack*&);intlength(linklist*);voidprintlink(linklist*);voidcreate(linklist*&,datatype*);voidpush(stack*,datatype);datatypepop(stack*);intsymmetry(linklist*,stack*);//判字符串是否中心對(duì)稱的函數(shù)聲明voidmain(){ linklist*head;stack*s; datatypestr[80]; gets(str); create(head,str); printlink(head); setnull(s); if(symmetry(head,s))printf("字符串\"%s\"中心對(duì)稱\n",str); elseprintf("字符串\"%s\"不是中心對(duì)稱\n",str);}//棧初始化voidsetnull(stack*&s){ s=(stack*)malloc(sizeof(stack)); s->top=-1;}//求單鏈表長(zhǎng)度intlength(linklist*head){linklist*p=head->next;intn=0;while(p!=NULL){n++;p=p->next;}returnn;}//輸出單鏈表voidprintlink(linklist*head){linklist*p=head->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");}//建立具有頭結(jié)點(diǎn)的單鏈表voidcreate(linklist*&head,datatype*str){datatype*p=str;linklist*s,*r;head=(linklist*)malloc(sizeof(linklist));r=head;while(*p!='\0'){ s=(linklist*)malloc(sizeof(linklist));s->data=*p; r->next=s; r=s; p++;}r->next=NULL;}//順序棧入棧voidpush(stack*s,datatypee){ s->top++; s->elements[s->top]=e;}//順序棧出棧datatypepop(stack*s){ datatypetemp; s->top--; temp=s->elements[s->top+1]; returntemp;}//判字符串是否中心對(duì)稱intsymmetry(linklist*head,stack*s){ inti=1,j=1;intn=length(head);// printf("n=%d\n",n); linklist*p=head->next; //先把前一半字符依次進(jìn)棧 //datatypem; for(i=1;i<=n/2;i++) {push(s,p->data); p=p->next; } //依次出棧與另一半字符進(jìn)行比較 if(n%2!=0)//判斷n的奇偶 p=p->next; else p=p;while(s->elements[s->top]==p->data&&p!=NULL&&s->top>0)//循環(huán)至不等或其中一個(gè)為空 { j++; pop(s); p=p->next; } //printf("j=%2d;n/2=%2d\n",j,n/2); if(j==n/2) return1; else return0; }實(shí)驗(yàn)二：第2題//循環(huán)隊(duì)列入隊(duì)出隊(duì)的程序代碼#include<stdio.h>#include<stdlib.h>#include<malloc.h>//循環(huán)隊(duì)列的結(jié)構(gòu)類型定義constintm=5;typedefintdatatype;typedefstruct{datatypesequ[m];intrear,quelen;}qu;voidsetnull(qu*);voidenqueue(qu*,datatype);datatype*dequeue(qu*);voidmain(){qu*sq;datatypex,*p;intkey;sq=(qu*)malloc(sizeof(qu));setnull(sq);do{printf("1.EnterQueue2.DeleteQueue-1.Quit:");scanf("%d",&key);switch(key){case1:printf("EntertheData:");scanf("%d",&x); enqueue(sq,x);break; case2:p=dequeue(sq); if(p!=NULL)printf("%d\n",*p); break; case-1:exit(0);}}while(1);}//置空隊(duì)voidsetnull(qu*sq){sq->rear=m-1;sq->quelen=0;}//添加入隊(duì)算法voidenqueue(qu*sq,datatypex){ if(sq->quelen==m)//判隊(duì)滿{printf("隊(duì)列上溢");}else{sq->rear=(sq->rear+1)%m;//尾指針加1sq->sequ[sq->rear]=x;sq->quelen++;}}//添加出隊(duì)算法datatype*dequeue(qu*sq)//出隊(duì){//datatypetmp;if(sq->quelen==0)//判隊(duì)空{(diào)printf("隊(duì)列下溢");}else{//tmp=sq->sequ[(sq->rear-sq->quelen+m)%m]; sq->quelen--;return(&sq->sequ[(sq->rear-sq->quelen+m)%m]);}}實(shí)驗(yàn)三：第1題//模式匹配的程序代碼#include<stdio.h>#include<string.h>#include<malloc.h>//順序串的結(jié)構(gòu)類型定義#definemaxsize100typedefstruct{ charstr[maxsize];intlen;}seqstring;intIndex(seqstring*,seqstring*);voidmain(){ seqstring*S,*subS; S=(seqstring*)malloc(sizeof(seqstring)); subS=(seqstring*)malloc(sizeof(seqstring)); printf("輸入串：");gets(S->str); S->len=strlen(S->str); printf("輸入子串：");gets(subS->str); subS->len=strlen(subS->str); if(Index(S,subS)>0)printf("匹配成功！\n"); elseprintf("匹配失??！\n");}//順序串的樸素模式匹配intIndex(seqstring*S,seqstring*subS){inti=1,j=1;//目標(biāo)串從第一個(gè)字符開始與模式串的第一個(gè)字符開始進(jìn)行比較while(i<=S->len&&j<=subS->len)//循環(huán)至i超出目標(biāo)串的長(zhǎng)度或j超出模式串的長(zhǎng)度 { if(S->str[i-1]==subS->str[j-1])//若相等 {i++; j++; printf("A:i=%2d,j=%2d\n",i,j); }else//若不等 {i=i-j+2; j=1; printf("B:i=%2d,j=%2d\n",i,j); } } if(j>subS->len) { printf("i-subS->len=%2d\n",i-subS->len);return(i-subS->len);} elsereturn(0);}實(shí)驗(yàn)三：第2題//刪除子串的程序代碼#include<stdio.h>#include<string.h>#include<malloc.h>//順序串的結(jié)構(gòu)類型定義#definemaxsize100typedefstruct{ charstr[maxsize];intlen;}seqstring;voidstrPut(seqstring*);voidstrDelete(seqstring*,int,int);voidmain(){ seqstring*S; inti,m; S=(seqstring*)malloc(sizeof(seqstring)); printf("輸入串：");gets(S->str); S->len=strlen(S->str); strPut(S); printf("刪除的開始位置:");scanf("%d",&i); printf("刪除的字符個(gè)數(shù):");scanf("%d",&m); strDelete(S,i,m); strPut(S);}//輸出串voidstrPut(seqstring*S){ inti; for(i=0;i<S->len;i++) printf("%c",S->str[i]); printf("\n");}//刪除子串voidstrDelete(seqstring*S,inti,intm){ intn=strlen(S->str); chartemp[maxsize];if(i>=n)printf("沒有字符被刪除\n");elseif(i+m>=n){ printf("從位置%2d至末尾的字符均刪除\n",i);//strcpy(temp,S->str); //strcpy(S->str,temp); S->len=i-1;}else{ printf("刪除從第%2d個(gè)字符開始的連續(xù)%2d個(gè)字符\n",i,m);strcpy(temp,S->str+i-2);//把i個(gè)字符前的i-1個(gè)（str[0]--str[i-2]）字符放入指針temp中 strcpy(temp+i-1,S->str+i+m-1);//把 //strcpy(temp,S->str+i+m-1); strcpy(S->str,temp);S->len=S->len-m;}}實(shí)驗(yàn)四：第1題//找馬鞍點(diǎn)程序代碼#include<stdio.h>#include<malloc.h>//數(shù)組的結(jié)構(gòu)類型定義constintm=3;constintn=3;typedefstruct{ intA[m+1][n+1]; intmax[m+1],min[n+1];}array;voidminmax(array*);voidmain(){ array*pa=(array*)malloc(sizeof(array));inti,j;for(i=1;i<=m;i++)for(j=1;j<=n;j++)scanf("%d",&pa->A[i][j]);minmax(pa);}//找馬鞍點(diǎn)voidminmax(array*pa){inti,j,k=0; for(i=1;i<=m;i++)//打印出矩陣形式 { for(j=1;j<=n;j++) { printf("%3d",pa->A[i][j]); } printf("\n"); } for(i=1;i<=m;i++)//計(jì)算找出每行的最小元素，放入pa->min[M]中 { pa->min[i]=pa->A[i][1]; for(j=1;j<=n;j++) { if(pa->min[i]>pa->A[i][j]) { pa->min[i]=pa->A[i][j]; } } } for(i=1;i<=n;i++)//計(jì)算找出每列的最大元素，放入pa->max[N]中 { pa->max[i]=pa->A[1][i]; for(j=1;j<=m;j++) { if(pa->max[i]<pa->A[j][i]) { pa->max[i]=pa->A[j][i]; } } } for(i=1;i<=m;i++)//按照題目意思，進(jìn)行匹配 { for(j=1;j<=n;j++) { if(pa->min[i]==pa->max[j]) { printf("馬鞍點(diǎn)是:(%d,%d):%d\n",i,j,pa->A[i][j]); k=1; } } } if(k==0) { printf("沒有馬鞍點(diǎn)!\n"); }}實(shí)驗(yàn)四：第2題//對(duì)稱矩陣相乘的程序代碼#include<stdio.h>#include<malloc.h>//數(shù)組結(jié)構(gòu)類型的定義.hconstintn=3;constintsize=n*(n+1)/2;typedefintdatatype;typedefstruct{ datatypeA[size],B[size],C[n][n];}array;voidinput(datatype[]);voidoutput(datatype[][n]);voidmult(array*);voidmain(){ array*pa; pa=(array*)malloc(sizeof(array)); printf("以行為主序輸入矩陣A的下三角:\n");input(pa->A);//以行為主序輸入矩陣A的下三角 printf("以行為主序輸入矩陣B的下三角:\n"); input(pa->B);//以行為主序輸入矩陣B的下三角 mult(pa); output(pa->C);//輸出矩陣C}//對(duì)稱矩陣的輸入voidinput(datatypex[]){ for(inti=0;i<size;i++) scanf("%d",&x[i]);}//矩陣的輸出voidoutput(datatypex[][n]){ for(inti=0;i<n;i++){ for(intj=0;j<n;j++) printf("%5d",x[i][j]); printf("\n"); }}//對(duì)稱矩陣相乘voidmult(array*pa){inti,j,k=0,a[n][n],b[n][n],p,q;for(i=0;i<n;i++)//先還原矩陣A,B{ for(j=0;j<n;j++) { if(i>=j)//還原下三角 { a[i][j]=pa->A[k]; b[i][j]=pa->B[k]; k++; } if(i>j)//根據(jù)對(duì)稱還原上三角 { a[j][i]=a[i][j];b[j][i]=b[i][j]; } }}printf("矩陣A:\n");output(a);printf("矩陣B:\n");output(b);printf("矩陣C:\n");for(i=0;i<n;i++)//求相乘后的矩陣Cfor(j=0;j<n;j++) { pa->C[i][j]=0; for(p=0;p<n;p++) pa->C[i][j]=pa->C[i][j]+a[i][p]*b[p][j]; } }實(shí)驗(yàn)五：第1題//交換左右子樹的程序代碼#include<stdio.h>#include<malloc.h>//二叉鏈表的結(jié)構(gòu)類型定義constintmaxsize=1024;typedefchardatatype;typedefstructnode{ datatypedata; structnode*lchild,*rchild;}bitree;bitree*creattree();voidpreorder(bitree*);bitree*swap(bitree*);voidmain(){ bitree*pb; pb=creattree(); preorder(pb); printf("\n"); swap(pb); preorder(pb); printf("\n");}//二叉樹的建立bitree*creattree(){ charch; bitree*Q[maxsize]; intfront,rear; bitree*root,*s; root=NULL; front=1;rear=0; printf("按層次輸入二叉樹，虛結(jié)點(diǎn)輸入'@'，以'#'結(jié)束輸入：\n"); while((ch=getchar())!='#') { s=NULL; if(ch!='@') { s=(bitree*)malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; elseQ[front]->rchild=s; if(rear%2==1)front++; } } returnroot;}//先序遍歷按層次輸出二叉樹voidpreorder(bitree*p){ if(p!=NULL) { printf("%c",p->data); if(p->lchild!=NULL||p->rchild!=NULL) { printf("("); preorder(p->lchild); if(p->rchild!=NULL)printf(","); preorder(p->rchild); printf(")"); } }}//交換左右子樹bitree*swap(bitree*r){ bitree*p=r; bitree*q; if(p) { //printf("%c",p->data); q=p->lchild; p->lchild=p->rchild; p->rchild=q; swap(p->lchild); swap(p->rchild); }return(r);}實(shí)驗(yàn)五：第2題//統(tǒng)計(jì)結(jié)點(diǎn)總數(shù)、葉子結(jié)點(diǎn)總數(shù)及樹深的程序代碼#include<stdio.h>#include<malloc.h>//二叉鏈表的結(jié)構(gòu)類型定義constintmaxsize=1024;typedefchardatatype;typedefstructnode{ datatypedata; structnode*lchild,*rchild;}bitree;bitree*creattree();voidpreorder(bitree*);intcountnode(bitree*);intcountleaf(bitree*);intdeep(bitree*p)；voidmain(){ bitree*root; intleafnum,nodenum，treedeep; root=creattree(); printf("刪除子樹之前的二叉樹："); preorder(root); printf("\n");nodenum=countnode(root);printf("結(jié)點(diǎn)總數(shù)是：%d\n",nodenum); leafnum=countleaf(root);printf("葉子結(jié)點(diǎn)總數(shù)是：%d\n",leafnum);treedeep=deep(root);printf(“樹深為：%d\n”,treedeep);}//建立二叉樹bitree*creattree(){ datatypech; bitree*Q[maxsize]; intfront,rear; bitree*root,*s; root=NULL; front=1;rear=0; printf("按層次輸入結(jié)點(diǎn)值，虛結(jié)點(diǎn)輸入'@'，以換行符結(jié)束："); while((ch=getchar())!='\n') { s=NULL; if(ch!='@') { s=(bitree*)malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else { if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; elseQ[front]->rchild=s; if(rear%2==1)front++; } } returnroot;}//先序遍歷輸出二叉樹voidpreorder(bitree*p){ if(p!=NULL) { printf("%c",p->data); if(p->lchild!=NULL||p->rchild!=NULL) { printf("("); preorder(p->lchild); if(p->rchild!=NULL)printf(","); preorder(p->rchild); printf(")"); } }}//添加統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)算法(先根，中根，后根遍歷均可)intcountnode(bitree*p){staticintn=0;if(p!=NULL){ countnode(p->lchild);n++;printf("%c",p->data);countnode(p->rchild);}returnn;}//添加統(tǒng)計(jì)葉子結(jié)點(diǎn)個(gè)數(shù)算法(先根、中根、后根均可)intcountleaf(bitree*p){staticintn=0;if(p!=NULL){countleaf(p->lchild);//遍歷左子樹if(p->lchild==NULL&&p->rchild==NULL) { n++;printf("%c",p->data);//打印葉子節(jié)點(diǎn) }//endifcountleaf(p->rchild);//遍歷右子樹}//endifreturnn;}//求樹深(三種遍歷均可)intdeep(bitree*p){ intdl,dr; if(p) { dl=deep(p->lchild); printf("%c",p->data); dr=deep(p->rchild); if(dl>dr) return(dl+1); else return(dr+1); }return(0);}實(shí)驗(yàn)六：第1題//無向圖鄰接矩陣搜索遍歷的程序代碼#include<stdio.h>//圖的鄰接矩陣類型定義constintn=8;constinte=10;typedefcharvextype;typedefintadjtype;typedefstruct{ vextypevexs[n]; adjtypearcs[n][n];}graph;graph*g=newgraph;voidcreatgraph();voiddfsa(int);intvisited[n];voidmain(){ creatgraph(); inti; while(1) { for(i=0;i<n;i++) visited[i]=0; printf("輸入出發(fā)點(diǎn)序號(hào)（0-7），輸入-1結(jié)束："); scanf("%d",&i); if(i==-1)break; dfsa(i); }}//建立無向圖鄰接矩陣voidcreatgraph(){ inti,j,k; charch; printf("輸入8個(gè)頂點(diǎn)的字符數(shù)據(jù)信息:\n"); for(i=0;i<n;i++) if((ch=getchar())!='\n')g->vexs[i]=ch; for(i=0;i<n;i++) for(j=0;j<n;j++) g->arcs[i][j]=0; printf("輸入10條邊的起、終點(diǎn)i,j:\n"); for(k=0;k<e;k++) { scanf("%d,%d",&i,&j);//頂點(diǎn)序號(hào)從0開始 g->arcs[i][j]=g->arcs[j][i]=1; }}//深度優(yōu)先搜索遍歷實(shí)驗(yàn)七：第1題//希爾排序的程序代碼#include<stdio.h>//順序表結(jié)構(gòu)類型定義typedefintdatatype;typedefstruct{ intkey; datatypedata;}rectype;constintN=10;constintD1=5;voidcreate(rectype[],int);voidprint(rectype[],int);voidshellsort(rectype[],int[]);voidmain(){rectyper[N+D1];//D1個(gè)元素存放監(jiān)視哨，N個(gè)元素存放記錄intd[3]={5,3,1};//設(shè)置3趟的增量 create(r,N);//建立存放記錄的順序表 printf("排序前的數(shù)據(jù)："); print(r,N);//輸出排序前的記錄表 shellsort(r,d);//希爾排序 printf("排序后的數(shù)據(jù)："); print(r,N);//輸出排序后的記錄表}//建立順序表voidcreate(rectyper[],intn){ printf("輸入10個(gè)整型數(shù)："); for(inti=0;i<n;i++) scanf("%d",&r[D1+i].key);}//輸出順序表voidprint(rectyper[],intn){ for(inti=0;i<n;i++) printf("%5d",r[D1+i].key); printf("\n");}//希爾排序voidshellsort(rectypeR[],intd[]){ intk,i,j,s; for(k=0;k!=3;++k) { for(i=D1+d[k];i<N+D1;++i) { s=D1-d[k]+(i-D1)%d[k]; R[s]=R[i]; j=i-d[k]; while(R[s].key<R[j].key) { R[j+d[k]]=R[j]; j-=d[k]; } R[j+d[k]]=R[s]; } }}實(shí)驗(yàn)七：第2題//雙向起泡排序的程序代碼#include<stdio.h>#include<stdlib.h>#include<time.h>//順序表結(jié)構(gòu)類型定義typedefintdatatype;typedefstruct{ intkey; datatypedata;}sequenlist;voidcreate(sequenlist[],int);voidprint(sequenlist[],int);voiddbubblesort(sequenlist[],int);voidmain(){ constintn=10; sequenlistr[n+1]; create(r,n); printf("排序前的數(shù)據(jù)："); print(r,n); dbubblesort(r,n); printf("排序后的數(shù)據(jù)："); print(r,n);}//建立順序表voidcreate(sequenlistr[],intn){ srand(time(0)); for(inti=1;i<=n;i++) r[i].key=rand()%90;}//輸出順序表voidprint(sequenlistr[],intn){ for(inti=1;i<=n;i++) printf("%5d",r[i].key); printf("\n");}//雙向起泡排序?qū)嶒?yàn)八：第1題//分塊查找的程序代碼#include<stdio.h>//類型定義typedefintkeytype;typedefstruct{ keytypekey; intlow,high;}index;typedefstruct{ keytypekey;}record;constintrecN=18;constintidxN=3;intblksearch(record[],index[],keytype,int);voidmain(){ recordr[recN]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53}; indexidx[idxN]={{22,0,5},{48,6,11},{86,12,17}}; keytypekey; intloc,i; printf("待查找的記錄關(guān)鍵字表：\n"); for(i=0;i<recN;i++) printf("%5d",r[i]); printf("\n"); printf("輸入所要查找記錄的關(guān)鍵字："); scanf("%d",&key); loc=blksearch(r,idx,key,idxN); if(loc!=-1)printf("查找到，是第%d個(gè)記錄。\n",loc+1); elseprintf("記錄查找不到！\n");}//折半查找索引表，塊內(nèi)順序查找實(shí)驗(yàn)八：第2題//判斷二叉排序樹的程序代碼#include<stdio.h>#include<stdlib.h>#include<malloc.h>//二叉鏈表的結(jié)構(gòu)類型定義constintmaxsize=1024;typedefintkeytype;typedefstructnode{ keytypekey; structnode*lchild,*rchild;}bitree;bitr