《算法與數(shù)據(jù)結(jié)構(gòu)》上機(jī)指導(dǎo)書

算法與數(shù)據(jù)結(jié)構(gòu) 課程上機(jī)指導(dǎo)書電子信息工程 專業(yè)周月霞 編佛山科學(xué)技術(shù)學(xué)院2005 年 8 月摘 要本書是為了配合電子信息工程專業(yè)算法與數(shù)據(jù)結(jié)構(gòu)課程而編寫的，與高等教育出版社出版的數(shù)據(jù)結(jié)構(gòu)用C語言描述（唐策善等編）相配套。本指導(dǎo)書針對教學(xué)內(nèi)容組織了十三個上機(jī)實驗題目，分別涵蓋線性表、棧與隊列、串、數(shù)組和廣義表、樹和二叉樹、圖、動態(tài)存儲管理、集合（查找表）、內(nèi)部排序和外部排序、文件等內(nèi)容。并給予必要的上機(jī)指導(dǎo)，使學(xué)生能更深透地理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)的基本概念以及有關(guān)算法，培養(yǎng)基本的、良好的程序設(shè)計技能，編制高效可靠的程序。 本書內(nèi)容豐富，涉及面廣，實用性強(qiáng)，與算法與數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容緊密結(jié)合?？梢怨└黝悓W(xué)生課程學(xué)習(xí)使用，也可供教師或其他專業(yè)技術(shù)人員參考。目 錄 前言實驗一 順序表基本操作 1實驗二 順序表其它操作 5實驗三 鏈表基本操作 10實驗四 鏈表其它操作 14實驗五 表達(dá)式求值 24實驗六 數(shù)組的建立和使用 26實驗七 二叉樹基本操作 26實驗八 二叉樹其它操作 27實驗九 圖的基本操作 29實驗十 圖的其它操作 33實驗十一 二叉排序樹操作 41實驗十二 哈希表操作 44實驗十三 各種內(nèi)部排序方法 52主要參考書 57附錄1 程序設(shè)計風(fēng)格和注釋要求 58附錄2 上機(jī)實驗報告格式 59前 言算法與數(shù)據(jù)結(jié)構(gòu)是計算機(jī)科學(xué)與技術(shù)專業(yè)和其他有志從事計算機(jī)技術(shù)工作的人員的一門重要的專業(yè)基礎(chǔ)課。算法與數(shù)據(jù)結(jié)構(gòu)課程的教學(xué)要求是學(xué)會分析研究計算機(jī)加工的數(shù)據(jù)對象的特征，以便在實際應(yīng)用中選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和相應(yīng)的算法，初步掌握算法的時間與空間性能分析技巧，得到復(fù)雜程序設(shè)計的訓(xùn)練。本書是與高等教育出版社出版的數(shù)據(jù)結(jié)構(gòu)用C語言描述（唐策善等編）相配套的，給出了十三個上機(jī)實驗指導(dǎo)，每個實驗都給出了幾道上機(jī)題目，每個實驗題目都介紹了實驗?zāi)康模饕捎玫姆椒ㄅc技術(shù)和C語言實現(xiàn)程序。通過實驗使學(xué)生了解并學(xué)會如何運(yùn)用數(shù)據(jù)結(jié)構(gòu)只是去解決現(xiàn)實世界的某些實際問題，具備設(shè)計較復(fù)雜程序的初步能力。本書的出發(fā)點(diǎn)是幫助學(xué)生學(xué)好算法與數(shù)據(jù)結(jié)構(gòu)這門課程，所以在使用本書的過程中要注意以下幾點(diǎn)：第一要與課程內(nèi)容的學(xué)習(xí)同步，有利于進(jìn)一步理解掌握各知識點(diǎn)和鞏固課堂效果教學(xué)。第二算法設(shè)計具有不唯一性，對實驗題目本書只給出一種或幾種算法，要在學(xué)習(xí)、理解、領(lǐng)會的基礎(chǔ)上自己動手設(shè)計算法程序，這樣才會取得良好的效果。切忌照抄照搬，否則會影響學(xué)習(xí)效果。第三要學(xué)會舉一反三，觸類旁通，實驗內(nèi)容知識點(diǎn)是有限的，但運(yùn)用這些知識點(diǎn)、運(yùn)用所介紹的方法和技術(shù)解決的實際問題卻是無限的，重在掌握基本原理、基本方法和基本技術(shù)，并學(xué)會靈活運(yùn)用。第四要有C語言的基礎(chǔ)。本書算法是用C語言描述，所以讀者應(yīng)先了解C語言的基本內(nèi)容。由于時間倉促和作者水平有限，本書一定還存在著許多問題，敬請廣大讀者批評指正。 作者 2005年8月63實驗一 順序表基本操作一、目的和要求1、熟悉C語言的上機(jī)環(huán)境，掌握C語言的基本結(jié)構(gòu)。2、會定義線性表的順序存儲結(jié)構(gòu)。3、熟悉對順序表的一些基本操作和具體的函數(shù)定義。 二、實驗內(nèi)容1、該程序的功能是對元素類型為整型的順序表進(jìn)行一些操作。該程序包括順序表結(jié)構(gòu)類型的定義以及對順序表操作的具體的函數(shù)定義和主函數(shù)。 三、儀器、設(shè)備和材料1、 計算機(jī)若干臺  四、實驗步驟/* 定義ElemType為int類型 */typedef int ElemType;/*順序表存儲空間的總分配量*/#define MAXSIZE 100#define FALSE 0#define TRUE 1/* 順序存儲類型 */typedef structElemType dataMAXSIZE; /*存放線性表的數(shù)組*/ int length; /* length是順序表的長度*/SeqList;/* 初始化順序表 */SeqList SeqListInit( )SeqList L; L.length=0; return L; /* 清空順序表 */SeqList ListClear(SeqList L)L.length=0; return L;/* 求順序表長度 */int ListLength(SeqList L) return(L.length);/* 檢查順序表是否為空 */int ListEmpty(SeqList L)if(L.length) return(FALSE); else return(TRUE);/*檢查順序表是否為滿 */int ListFull(SeqList L)if(L.length=MAXSIZE) return(TRUE); else return(FALSE);/* 遍歷順序表 */void ListTraverse(SeqList L)int i; if(L.length<=0) printf("順序表為空n"); else printf("當(dāng)前順序表中的元素為:n"); for(i=1;i<=L.length;i+) printf("%d ",L.datai-1); printf("n"); /* 從順序表中查找元素 */ElemType ListGet(SeqList L ,int i)ElemType e; e=L.datai-1; return(e);/* 從順序表中查找與給定元素值相同的元素在順序表中的位置 */int ListLocate(SeqList L, ElemType x)int i=0; while(i<L.length && L.datai!=x) i+; if (i<L.length) return (i+1); else return 0;/* 向順序表中插入元素 */SeqList ListInsert(SeqList L,int i,ElemType x)int j; if(L.length=MAXSIZE) printf("表滿,不能插入n"); else if(i<1|i>L.length+1) printf("插入位置不正確n"); else for(j=L.length-1;j>=i-1;j-)L.dataj+1=L.dataj; L.datai-1=x; L.length+; return L; /* 從順序表中刪除元素 */SeqList ListDelete(SeqList L,int i)int j;ElemType x; if (i<1|i>L.length)printf("刪除位置不正確n"); else x=L.datai-1; for(j=i;j<=L.length-1;j+) L.dataj-1=L.dataj; L.length-; printf("%d已被刪除n",x); return L;/*求順序表中元素的前驅(qū)*/ElemType SeqListPrior(SeqList L,ElemType e)int i=0; while(i<L.length&&L.datai!=e)i+; if(i=0) printf("第一個元素沒有前驅(qū)n");return 0; else if(i<=L.length-1) return(L.datai-1);else printf("不存在值為%d的元素n",e);return 0;/*求順序表中元素的后繼*/ElemType SeqListNext(SeqList L,ElemType e)int i=0; while(i<L.length&&L.datai!=e) i+; if(i=L.length-1) printf("最后一個元素沒有后繼n");return 0; else if(i<L.length-1) return(L.datai+1);else printf("不存在值為%d的元素n",e);return 0;int scan()int d; printf("請選擇所要進(jìn)行的操作n"); printf("1.初始化 2.清空3.求順序表長度4.檢查順序表是否為空n"); printf("5.檢查順序表是否為滿 6.遍歷順序表 7.從順序表中查找元素n"); printf("8.從順序表中查找與給定元素值相同的元素在順序表中的位置n"); printf("9.向順序表中插入元素10. 從順序表中刪除元素n"); printf("11.求元素的前驅(qū) 12.求元素的后繼n"); printf("其他鍵退出.n"); scanf("%d",&d); return(d);main()int quit=0;int i,location; ElemType e,prior,next; SeqList L; printf("第一次操作需選擇初始化n"); while(!quit) switch(scan() case 1:L=SeqListInit();break; case 2:ListClear(L);break; case 3:printf("順序表的長度為%dn",ListLength(L);break; case 4:if(ListEmpty(L)printf("順序表為空n");else printf("順序表不為空n");break; case 5:if(ListFull(L)printf("順序表滿n");else printf("順序表不滿n");break; case 6:ListTraverse(L);break; case 7:printf("請輸入要查找的元素的位置n");scanf("%d",&i);if(L.length=0) printf("順序表已空n");else if(i<=0|i>L.length) printf("查找的位置不正確n"); else printf("順序表中第%d個元素的值為:%dn",i,ListGet(L,i);break; case 8:printf("請輸入要查找的元素的值n");scanf("%d",&e);if(L.length=0) printf("順序表已空n");else location=ListLocate(L,e); if(location=0) printf("順序表中不存在值為%d的元素n",e); else printf("順序表中%d的位置是:%dn",e,ListLocate(L,e);break; case 9:printf("請輸入要插入的元素的位置和其值:n");scanf("%d%d",&i,&e);L=ListInsert(L,i,e);break; case 10:printf("請輸入要刪除的元素的位置:n"); scanf("%d",&i); L=ListDelete(L,i); break; case 11:scanf("%d",&e); prior=SeqListPrior(L,e); if(prior) printf("%d的前驅(qū)是:%dn",e,prior);break; case 12:scanf("%d",&e); next=SeqListNext(L,e); if(next) printf("%d的后繼是:%dn",e,next);break; default:quit=1;五、實驗注意事項1、在做第一次“數(shù)據(jù)結(jié)構(gòu)”課程實驗之前，要在硬盤上建立好自己的工作目錄，專門來存儲你所做的實驗程序及相關(guān)信息，以后每次做實驗都采用這個目錄。實驗二 順序表其它操作一、目的和要求1、進(jìn)一步掌握在線性表的順序存儲結(jié)構(gòu)上的一些其它操作。 二、實驗內(nèi)容1、已知一個線性表，用另辟空間和利用原表兩種方法把線性表逆置。2、已知兩個非遞減有序的線性表LA和LB，將LA和LB合并成一個線性表LC，LC也非遞減有序。3、已知兩個非遞減有序的線性表LA和LB，長度分別為m和n，假設(shè)LA的空間足夠大，利用原表LA，將LA和LB合并成一個仍然非遞減有序的線性表。要求時間復(fù)雜度為O(m+n)。4、約瑟夫環(huán)問題：任給正整數(shù)N和K，按下述方法可以得到1,2, ,n的一個置換，將數(shù)字1,2,n環(huán)形排列，按順時針方向自1開始報數(shù)，報到K時輸出該位置上的數(shù)字，并使其出列。然后從他在順時針方向的下一個數(shù)字繼續(xù)報數(shù)，如此下去，直到所有的數(shù)字全部出列為止。例如N=10，K=3，則正確的出列順序應(yīng)為3，6，9，2，7，1，8，5，10，4。 三、儀器、設(shè)備和材料1、 計算機(jī)若干臺  四、實驗步驟1、已知一個線性表，用另辟空間和利用原表兩種方法把線性表逆置。typedef int ElemType; /* 定義ElemType為int類型 */*順序表存儲空間的總分配量*/#define MAXSIZE 100#define FALSE 0#define TRUE 1typedef struct /* 順序存儲類型 */ElemType dataMAXSIZE; /*存放線性表的數(shù)組*/ int length; /* length是順序表的長度*/SeqList;SeqList reverse(SeqList A) /*順序表的就地逆置 */ int i,j;ElemType temp; for(i=0,j=A.length-1;i<j;i+,j-) /*i,j分別是低端和高端下標(biāo)*/temp=A.datai; /*交換*/ A.datai=A.dataj; A.dataj =temp; return A;/* 遍歷順序表 */void ListTraverse(SeqList L)int i; if(L.length<=0) printf("順序表為空n"); else printf("當(dāng)前順序表中的元素為:n"); for(i=1;i<=L.length;i+) printf("%d ",L.datai-1); printf("n"); SeqList create(int n)SeqList L;ElemType e; int i; printf("input element:n"); for(i=0;i<n;i+) scanf("%d",&e); L.datai=e; L.length=n; return L;main()int n;SeqList L; printf("input the number:"); scanf("%d",&n); L=create(n); L=reverse(L); printf("順序表已經(jīng)逆置n"); ListTraverse(L);2、已知兩個非遞減有序的線性表LA和LB，將LA和LB合并成一個線性表LC，LC也非遞減有序。SeqList MergeSeqList(SeqList La,SeqList Lb)int i,j,k;SeqList Lc; i=0;j=0;k=0; while(i<La.length&&j<Lb.length) /*La,Lb都沒結(jié)束*/ if(La.datai<=Lb.dataj) Lc.datak=La.datai;i+;k+; /*La當(dāng)前元素小復(fù)制到Lc中*/ elseLc.datak=Lb.dataj;j+;k+;/*Lb當(dāng)前元素小復(fù)制到Lc中*/ while(i<La.length) Lc.datak=La.datai;i+;k+; /*La還沒結(jié)束*/ while(j<Lb.length) Lc.datak=Lb.dataj;j+;k+; /*Lb還沒結(jié)束*/ Lc.length=k; /*Lc表長為k*/ return Lc;void ListTraverse(SeqList L) /* 遍歷順序表 */int i; if(L.length<=0) printf("順序表為空n"); else printf("當(dāng)前順序表中的元素為:n"); for(i=1;i<=L.length;i+) printf("%d ",L.datai-1); printf("n"); SeqList create()SeqList L;ElemType e; int i=0; scanf("%d",&e); while(e!=-1) L.datai=e;i+;scanf("%d",&e); L.length=i; return L;main()int n;SeqList La,Lb,Lc; printf("請輸入非遞減有序的La的元素,輸入-1結(jié)束:n"); La=create(); printf("請輸入非遞減有序的Lb的元素,輸入-1結(jié)束:n"); Lb=create(); Lc=MergeSeqList(La,Lb); printf("順序表已經(jīng)合并n"); ListTraverse(Lc);3、已知兩個非遞減有序的線性表LA和LB，長度分別為m和n，假設(shè)LA的空間足夠大，利用原表LA，將LA和LB合并成一個仍然非遞減有序的線性表。要求時間復(fù)雜度為O(m+n)。SeqList MergeSeqList(SeqList La,SeqList Lb,int m,int n)int i,j,k; SeqList Lc; i=La.length-1;j=Lb.length-1;k=m+n-1;/*從后向前比較*/ while(i>=0&&j>=0)if(La.datai>=Lb.dataj) /*大的向La的后面復(fù)制*/ La.datak=La.datai;i-;k-; else La.datak=Lb.dataj;j-;k-; while(i>0) Lc.datak=La.datai;i-;k-;/*La沒有結(jié)束*/ while(j>0) Lc.datak=Lb.dataj;j-;k-; /*Lb沒有結(jié)束*/ La.length=m+n; /*合并后的表長*/ return La;void ListTraverse(SeqList L) /* 遍歷順序表 */int i; if(L.length<=0) printf("順序表為空n"); else printf("當(dāng)前順序表中的元素為:n"); for(i=1;i<=L.length;i+) printf("%d ",L.datai-1); printf("n"); SeqList create()SeqList L;ElemType e; int i=0; scanf("%d",&e); while(e!=-1) L.datai=e;i+;scanf("%d",&e); L.length=i; return L;main()int n;SeqList La,Lb,Lc; printf("請輸入非遞減有序的La的元素,輸入-1結(jié)束:n"); La=create(); printf("請輸入非遞減有序的Lb的元素,輸入-1結(jié)束:n"); Lb=create(); Lc=MergeSeqList(La,Lb,La.length,Lb.length); printf("順序表已經(jīng)合并n"); ListTraverse(Lc);4、約瑟夫環(huán)問題#define MAXSIZE 100void Js(int n,int k)int i,j,s,AMAXSIZE; for(i=0;i<n;i+) Ai=1; /*1為是否輸出標(biāo)志*/ j=0; for(i=0;i<n;i+)s=0; while(s<k) j=(j%n)+1; s=s+Aj-1; printf("%d ",j); Aj-1=0; /*輸出當(dāng)前應(yīng)該出列的元素,標(biāo)志置為0*/main()int N,K; printf("請輸入約瑟夫環(huán)中的元素個數(shù)N和K :"); scanf("%d%d",&N,&K); Js(N,K);五、實驗注意事項1、在做第一次“數(shù)據(jù)結(jié)構(gòu)”課程實驗之前，要在硬盤上建立好自己的工作目錄，專門來存儲你所做的實驗程序及相關(guān)信息，以后每次做實驗都采用這個目錄。實驗三 鏈表基本操作一、目的和要求1、定義單鏈表的結(jié)點(diǎn)類型。 2、熟悉對單鏈表的一些基本操作和具體的函數(shù)定義。3、通過單鏈表的定義掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的特點(diǎn)。 4、掌握循環(huán)鏈表和雙鏈表的定義和構(gòu)造方法。二、實驗內(nèi)容1、該程序的功能是實現(xiàn)單鏈表的定義和操作。該程序包括單鏈表結(jié)構(gòu)類型以及對單鏈表操作的具體的函數(shù)定義和主函數(shù)。 三、儀器、設(shè)備和材料1、 計算機(jī)若干臺  四、實驗步驟/* 定義ElemType為int類型 */typedef int ElemType;#define TRUE 1#define FALSE 0#define NULL 0#define flag -1typedef struct Lnode /* 單鏈表的結(jié)點(diǎn)類型 */ElemType data; struct LNode *next; LNode,*LinkedList;LinkedList LinkedListInit() /* 初始化單鏈表 */LinkedList L; L=(LinkedList)malloc(sizeof(LNode); L->next=NULL; return L;void LinkedListClear(LinkedList L) /* 清空單鏈表 */L->next=NULL; printf("鏈表已經(jīng)清空n");int LinkedListEmpty(LinkedList L) /* 檢查單鏈表是否為空 */if(L->next=NULL) return TRUE; else return FALSE;void LinkedListTraverse(LinkedList L) /* 遍歷單鏈表 */LinkedList p; p=L->next; if(p=NULL) printf("單鏈表為空表n"); elseprintf("鏈表中的元素為:n"); while(p!=NULL) printf("%d ",p->data); p=p->next; printf("n");int LinkedListLength (LinkedList L)LinkedList p; int j; p=L->next; j=0; while(p!=NULL) j+;p=p->next; return j; LinkedList LinkedListGet(LinkedList L,int i)LinkedList p;int j; p=L->next;j=1; while (p!=NULL && j<i ) p=p->next; j+; if (j=i) return p; else return NULL;int LinkedListLocate ( LinkedList L, ElemType x)LinkedList p;int j; p=L->next; j=1; while ( p!=NULL && p->data != x) p=p->next;j+; if(p) return j; else return 0; void LinkedListInsert(LinkedList L, int i, ElemType x)LinkedList p,s; int j; j=1;p=L; while(p&&j<i) p=p->next;j+; if(p=NULL|j>i) printf("插入位置不正確n"); else s=(LNode *)malloc(sizeof(LNode); s->data=x; s->next=p->next; p->next=s; printf("%d已插入到鏈表中n",x); void LinkedListDel(LinkedList L,int i) LinkedList p,q; int j; j=1;p=L; while(p->next&&j<i)p=p->next;j+; if(p->next=NULL)printf("刪除位置不正確n"); else q=p->next;p->next=q->next;free(q); printf("第%d個元素已從鏈表中刪除n",i); LinkedList LinkedListCreat( ) LinkedList L=LinkedListInit(),p,r; ElemType x; r=L; printf("請依次輸入鏈表中的元素,輸入-1結(jié)束n"); scanf("%d",&x); while (x!=flag)p=(LinkedList)malloc(sizeof(LNode);p->data=x;r->next=p;r=p;scanf("%d",&x);r->next=NULL;return L;int scan()int d; printf("請選擇要進(jìn)行的操作n"); printf("1.初始化 2.清空3.求鏈表長度4.檢查鏈表是否為空n"); printf("5.遍歷鏈表 6.從鏈表中查找元素n"); printf("7.從鏈表中查找與給定元素值相同的元素在順序表中的位置n"); printf("8.向鏈表中插入元素9. 從鏈表中刪除元素n"); printf("其他鍵退出。n"); scanf("%d",&d); return(d);main()int quit=0;int i,locate;ElemType e; LinkedList L,p; while(!quit) switch(scan() case 1:L=LinkedListInit();printf("n");break; case 2:LinkedListClear(L);printf("n");break; case 3:printf("鏈表的長度為 %dn",LinkedListLength(L);break; case 4:if(LinkedListEmpty(L)printf("鏈表為空n");else printf("鏈表非空n");break; case 5:LinkedListTraverse(L);break; case 6:printf("請輸入待查詢元素在鏈表中的位置:");scanf("%d",&i);p=LinkedListGet(L,i);if(p)printf("鏈表中第%d個元素的值為:%dn",i,p->data);else printf("查詢位置不正確n");break; case 7:printf("請輸入待查詢元素的值:");scanf("%d",&e);locate=LinkedListLocate(L,e);if(locate) printf("%d在鏈表中的位置是:%dn",e,locate);else printf("鏈表中沒有值為%d的元素n",e);break; case 8:printf("請輸入插入元素的位置和值(中間以空格或回車分隔):n");scanf("%d%d",&i,&e);LinkedListInsert(L,i,e);break; case 9:if(LinkedListLength(L)=0)printf("鏈表已經(jīng)為空,不能刪除n"); else printf("請輸入待刪除元素的位置:n");scanf("%d",&i);LinkedListDel(L,i);break; case 10:L=LinkedListCreat(); printf("n");break; default:quit=1;實驗四 鏈表其它操作一、目的和要求1、熟悉對單鏈表的一些其它操作。2、掌握循環(huán)鏈表和雙鏈表的一些操作，理解與單鏈表操作的不同。二、實驗內(nèi)容1、設(shè)單鏈表L是一個非遞減有序表，寫一算法將x插入其中后仍保持L的有序性。2、利用原空間，將兩個單鏈表合并成一個單鏈表。3、已知兩個非遞減有序的單鏈表la和lb，將la和lb合并成一個線性表lc，lc也非遞減有序。4、已知一個單鏈表，利用原表把單鏈表逆置。5、在計算機(jī)上先輸入一串正整數(shù)的序列。請編寫一個程序，首先用鏈表存儲該序列。然后執(zhí)行刪除操作，即先從鏈表中找出最小的結(jié)點(diǎn)，刪除它。然后再在剩余的鏈表中，找出最小的結(jié)點(diǎn)，再刪除之。直至表空為止。6、利用單循環(huán)鏈表作為存儲結(jié)構(gòu)，實現(xiàn)實驗二中的約瑟夫環(huán)問題。7、在雙向鏈表上實現(xiàn)線性表運(yùn)算。8、設(shè)有一個雙鏈表，每個結(jié)點(diǎn)中除有prior，next及data可設(shè)為正整數(shù)三個域之外，還有一個專門記錄訪問該結(jié)點(diǎn)次數(shù)的數(shù)據(jù)域freq，其值在初始化時為零。每當(dāng)在鏈表中進(jìn)行一次Searchl，key時，則數(shù)據(jù)域data之值等于key的結(jié)點(diǎn)，其freq域之值將加一。并使該雙鏈表中結(jié)點(diǎn)按freq之值的遞減順序排列，freq值越大的結(jié)點(diǎn)越靠近表頭。請編寫符合上述要求的Searchl，key程序。 三、儀器、設(shè)備和材料1、 計算機(jī)若干臺  四、實驗步驟1、將x插入L后仍保持L的有序性。#include "stdio.h"#define NULL 0typedef struct LNodeint data; struct LNode *next; LNode,*LinkedList;LinkedList LinkedListCreat( ) LinkedList L,p,r; int x,flag=-1; L=(LinkedList)malloc(sizeof(LNode); L->next=NULL; r=L; printf("請輸入遞增的有序序列,輸入-1結(jié)束n"); scanf("%d",&x); while (x!=flag)p=(LinkedList)malloc(sizeof(LNode); p->data=x; r->next=p; r=p;scanf("%d",&x); r->next=NULL; return L;void InsertList(LinkedList L,int x)LinkedList p,q,s; q=L;p=q->next; while(p!=NULL&&p->data<x) q=p; p=p->next; s=(LinkedList)malloc(sizeof(LNode); s->data=x; s->next=q->next; q->next=s;void print(LinkedList L) /*輸出鏈表中的結(jié)點(diǎn)*/LinkedList p; p=L->next; while(p!=NULL) printf("%d ",p->data); p=p->next; main( )LinkedList L; int x; L=LinkedListCreat( ); printf("請輸入要插入的元素:"); scanf("%d",&x); InsertList(L,x); print(L);2、利用原空間，將兩個單鏈表合并成一個單鏈表。#include "stdio.h"#define NULL 0typedef struct LNodeint data; struct LNode *next; LNode,*LinkedList;LinkedList LinkedListCreat( ) LinkedList L,p,r; int x,flag=-1; L=(LinkedList)malloc(sizeof(LNode); L->next=NULL; r=L; printf("請輸入鏈表中的結(jié)點(diǎn),以-1結(jié)束n"); scanf("%d",&x); while (x!=flag)p=(LinkedList)malloc(sizeof(LNode); p->data=x; r->next=p; r=p;scanf("%d",&x); r->next=NULL; return L;LinkedList ListConcat(LinkedList La,LinkedList Lb)/*把鏈表Lb接在La后面*/ LinkedList Lc,p; Lc=La;p=La; while(p->next) p=p->next; p->next=Lb->next; return Lc;void print(LinkedList L) /*輸出鏈表中的結(jié)點(diǎn)*/LinkedList p; p=L->next; while(p!=NULL) printf("%d ",p->data); p=p->next; main( )LinkedList La,Lb; La=LinkedListCreat( ); Lb= LinkedListCreat( ); La=ListConcat(La,Lb); print(La);3、兩個非遞減有序的單鏈表la和lb，合并成一個非遞減有序線性表lc。#define NULL 0typedef struct LNodeint data; struct LNode *next; LNode,*LinkedList;LinkedList LinkedListCreat() LinkedList L,p,r; int x,flag=-1; L=(LinkedList)malloc(sizeof(LNode); L->next=NULL; r=L; printf("請輸入非遞減有序表,以-1結(jié)束n"); scanf("%d",&x); while (x!=flag)p=(LinkedList)malloc(sizeof(LNode); p->data=x; r->next=p; r=p;scanf("%d",&x); r->next=NULL; return L;LinkedList un(LinkedList La,LinkedList Lb) /*合并鏈表*/LinkedList p,q,r; p=La->next; q=Lb->next; r=La; while(p!=NULL)&&(q!=NULL) if(p->data<=q->data) r->next=p; r=p;p=p->next; else r->next=q; r=q;q=q->next; if(p!=NULL) r->next=p; if(q!=NULL) r->next=q; return La;void print(LinkedList L) /*輸出鏈表中的結(jié)點(diǎn)*/LinkedList p; p=L->next; while(p!=NULL) printf("%d ",p->data); p=p->next; main( )LinkedList La,Lb,Lc; La=LinkedListCreat( ); Lb= LinkedListCreat( ); Lc=un(La,Lb); print(Lc);4、把單鏈表逆置（見課后習(xí)題）。5、在計算機(jī)上先輸入一串正整數(shù)的序列。首先用鏈表存儲該序列。然后從鏈表中找出最小的結(jié)點(diǎn)，刪除它。直至表空為止。6、利用單循環(huán)鏈表作為存儲結(jié)構(gòu)，實現(xiàn)實驗二中的約瑟夫環(huán)問題。7、在雙向鏈表上實現(xiàn)線性表的下列運(yùn)算：a) 建立 DLinkedList creat()b) 插入void DlistInsert(DLinkedList L,int x,int i)c)刪除void DlistDelete(DLinkedList L,int i)8、設(shè)有一個雙鏈表，每個結(jié)點(diǎn)中除有prior，next及data可設(shè)為正整數(shù)三個域之外，還有一個專門記錄訪問該結(jié)點(diǎn)次數(shù)的數(shù)據(jù)域freq，其值在初始化時為零。每當(dāng)在鏈表中進(jìn)行一次Searchl，key時，則數(shù)據(jù)域data之值等于key的結(jié)點(diǎn)，其freq域之值將加一。并使該雙鏈表中結(jié)點(diǎn)按freq之值的遞減順序排列，freq值越大的結(jié)點(diǎn)越靠近表頭。#define NULL 0typedef struct DLNodeint data,freq; struct DLNode *prior,*next;DLNode,*DLinkedList;DLinkedList creat()int num; DLinkedList head,p1,p2; head=(DLinkedList)malloc(sizeof(DLNode);head->next=NULL; /*表頭為空 */ p2=head;printf("輸入元素,以-1結(jié)束:");scanf("%d",&num);while(num!=-1) p1=(DLinkedList)malloc(sizeof(DLNode); p1->data=num; p1->freq=0; p2->next=p1; p1->prior=p2; p2=p1; scanf("%d",&num); p2->next=NULL;return head;void search(DLinkedList head, int key)DLinkedList p1,p2,temp; p2=head; p1=p2->next; while(p1) if(p1->data=key) p1->freq+; break; else p2=p1; p1=p2->next; if(p1=NULL) printf("沒有發(fā)現(xiàn).n"); else if(p1->next=NULL) p2->next=p1->next; temp=p1; else p2->next=p1->next; p1->next->prior=p2;temp=p1;for(p2=head,p1=p2->next; p1 && p1->freq > temp->freq;p2=p1,p1=p2->next); /*插入*/ if(p1=NULL) p2->next=temp; temp->prior=p2; temp->next=NULL; else p2->next=temp; temp->prior=p2; temp->next=p1; p1->prior=temp;void print(DLinkedList head)DLinkedList p; p=head->next; doprintf("元素=%d " , p->data); printf("頻度=%dn", p->freq); p=p->next; while(p);int main()DLinkedList head; int key; head=creat(); printf("現(xiàn)在元素和其訪問的頻度(按遞減的順序輸出)為:n" ); print(head); printf("請輸入要訪問的元素,以-1結(jié)束:"); scanf("%d",&key); while(key!=-1) search(head,key); print(head); printf( "請輸入要訪問的元素,以-1結(jié)束:"); scanf("%d",&key); 實驗五 表達(dá)式求值一、目的和要求1、會定義順序棧和鏈棧的結(jié)點(diǎn)類型。 2、掌握棧的插入和刪除結(jié)點(diǎn)在操作上的特點(diǎn)。3、熟悉對棧的一些基本操作和具體的函數(shù)定義。 二、實驗內(nèi)容1、實現(xiàn)順序棧的定義和操作。該程序包括定義的棧結(jié)構(gòu)類型以及對每一種棧操作的具體的函數(shù)定義和主函數(shù)。2、用順序棧實現(xiàn)算術(shù)表達(dá)式求值。3、用鏈棧實現(xiàn)算術(shù)表達(dá)式求值。 三、儀器、設(shè)備和材料1、 計算機(jī)若干臺  四、實驗步驟1、該程序包括定義的棧結(jié)構(gòu)類型以及對每一種棧操作的具體的函數(shù)定義和主函數(shù)。typedef int DataType; /* 定義DataType為int類型 */ /* 棧的結(jié)點(diǎn)類型 */#define MAXSIZE 1024 typedef struct