數(shù)據(jù)結(jié)構(gòu)實驗指導書重要參考.doc

數(shù)據(jù)結(jié)構(gòu)實驗指導前 言數(shù)據(jù)結(jié)構(gòu)是計算機相關(guān)專業(yè)的一門核心基礎(chǔ)課程，也是很多高?？佳袑I(yè)課之一。它主要介紹線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖狀結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲實現(xiàn)，在此基礎(chǔ)上介紹一些典型算法效率分析。這門課程的主要任務(wù)是培養(yǎng)學生的算法設(shè)計能力及良好的程序設(shè)計習慣。通過學習，要求學生能夠掌握典型算法的設(shè)計思想及程序?qū)崿F(xiàn)，能夠根據(jù)實際問題選取合適的存儲方案設(shè)計出簡潔、高效、實用的算法，為后續(xù)課程的學習及軟件開發(fā)打下良好的基礎(chǔ)。學習這門課程，習題和實驗是兩個關(guān)鍵環(huán)節(jié)。學生理解算法，上機實驗是最佳的途徑之一。因此，實驗環(huán)節(jié)的好壞是學生能否學好數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。為了更好地配合學生實驗，特編寫試驗指導書；同時，為每個主要的知識點配有精選的典型習題。希望學生對習題要注意理解。一、實驗?zāi)康?更好的理解算法的思想、培養(yǎng)編程能力。二、實驗要求1. 每次實驗前學生必須根據(jù)試驗內(nèi)容認真準備實驗程序及調(diào)試時所需的輸入數(shù)據(jù)。2. 在指導教師的幫助下能夠完成實驗內(nèi)容，得出正確的實驗結(jié)果。3. 實驗結(jié)束后總結(jié)實驗內(nèi)容、書寫實驗報告。4. 遵守實驗室規(guī)章制度、不缺席、按時上、下機。5. 實驗學時內(nèi)必須做數(shù)據(jù)結(jié)構(gòu)的有關(guān)內(nèi)容，不允許上網(wǎng)聊天或玩游戲，如發(fā)現(xiàn)上述現(xiàn)象，取消本次上機資格，平時成績扣10分。6. 實驗報告有一次不合格，扣5分，兩次以上不合格者，平時成績以零分記。三、實驗環(huán)境 Turbo C或VC+6.0四、說明1. 本實驗的所有算法中元素類型可以根據(jù)實際需要選擇。2. 實驗題目中帶者為較高要求，學生可自選；其余部分為基本內(nèi)容，應(yīng)盡量完成（至少完成70%，否則實驗不合格）。3. 數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學考試的專業(yè)課之一，希望有志于考研的學生能夠在學習過程中注意各種算法的理解，以便為考研做一定的準備。五、實驗報告的書寫要求1. 明確實驗的目的及要求;2. 記錄實驗的輸入數(shù)據(jù)和輸出結(jié)果;3. 說明實驗中出現(xiàn)的問題和解決過程;4. 寫出實驗的體會和實驗過程中沒能解決的問題;六、成績考評辦法1 期末考試占80分，閉卷。2 平時考評占20分。其中實驗環(huán)節(jié)占15分（實驗準備、上機、報告、考試等）；平時占5分（出勤，作業(yè)，測驗等）七、參考書目1. 數(shù)據(jù)結(jié)構(gòu)（語言版） 嚴蔚敏等 清華大學出版社 2. 數(shù)據(jù)結(jié)構(gòu)題集 （C語言版） 嚴蔚敏等 清華大學出版社 3. DATA STRUCTURE WITH C+ William Ford,William Topp清華大學出版社（影印版）實驗一 線性表的順序存儲結(jié)構(gòu)實驗學時 2學時背景知識:順序表的插入、刪除及應(yīng)用。目的要求： 1掌握順序存儲結(jié)構(gòu)的特點。 2掌握順序存儲結(jié)構(gòu)的常見算法。實驗內(nèi)容 1輸入一組整型元素序列，建立順序表。 2實現(xiàn)該順序表的遍歷。 3在該順序表中進行順序查找某一元素,查找成功返回1,否則返回0。 4判斷該順序表中元素是否對稱,對稱返回1,否則返回0。5實現(xiàn)把該表中所有奇數(shù)排在偶數(shù)之前,即表的前面為奇數(shù),后面為偶數(shù)。6輸入整型元素序列利用有序表插入算法建立一個有序表。 7利用算法6建立兩個非遞減有序表并把它們合并成一個非遞減有序表。8編寫一個主函數(shù),調(diào)試上述算法。 * 9綜合訓練：利用順序表實現(xiàn)一個班級學生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等）實驗說明 1.算法1至算法7可以以頭文件的方式存儲,主函數(shù)實現(xiàn)該頭文件的包含即可調(diào)用 2.存儲定義 #define MAXSIZE 100 /表中元素的最大個數(shù) typedef int ElemType；/元素類型 typedef struct list ElemType elemMAXSIZE;/靜態(tài)線性表 int length; /表的實際長度 SqList;/順序表的類型名 3.建立順序表時可利用隨機函數(shù)自動產(chǎn)生數(shù)據(jù)。注意問題 插入、刪除時元素的移動原因、方向及先后順序。 解不同的函數(shù)形參與實參的傳遞關(guān)系。實驗二 鏈式存儲結(jié)構(gòu)（一）-單向鏈表的有關(guān)操作實驗學時 學時背景知識：單向鏈表的插入、刪除及應(yīng)用。目的要求 1掌握單向鏈表的存儲特點及其實現(xiàn)。 2掌握單向鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實驗內(nèi)容 1隨機產(chǎn)生或鍵盤輸入一組元素，建立一個帶頭結(jié)點的單向鏈表（無序）。 2遍歷單向鏈表。 3把單向鏈表中元素逆置（不允許申請新的結(jié)點空間）。 4在單向鏈表中刪除所有的偶數(shù)元素結(jié)點。 5編寫在非遞減有序鏈表中插入一個元素使鏈表元素仍有序的函數(shù)，并利用該函數(shù)建立一個非遞減有序單向鏈表。 6利用算法5建立兩個非遞減有序單向鏈表，然后合并成一個非遞增鏈表。 7利用算法5建立兩個非遞減有序單向鏈表，然后合并成一個非遞減鏈表。 8利用算法1建立的鏈表，實現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間）。 * 9采用單向鏈表實現(xiàn)一元多項式的存儲并實現(xiàn)兩個多項式相加并輸出結(jié)果。10在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。 *11綜合訓練：利用鏈表實現(xiàn)一個班級學生信息管理（數(shù)據(jù)錄入、插入、刪除、排序、查找等，并能夠?qū)崿F(xiàn)將數(shù)據(jù)存儲到文件中）實驗說明 1類型定義 #include typedef int ElemType；/元素類型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; 2為了算法實現(xiàn)簡單，最好采用帶頭結(jié)點的單向鏈表。注意問題 1重點理解鏈式存儲的特點及指針的含義。 2注意比較順序存儲與鏈式存儲的各自特點。 3注意比較帶頭結(jié)點、無頭結(jié)點鏈表實現(xiàn)插入、刪除算法時的區(qū)別。 4單向鏈表的操作是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，一定要注意對這部分的常見算法的理解。實驗三 鏈式存儲結(jié)構(gòu)（二）-雙向鏈表的有關(guān)操作實驗學時 學時背景知識：雙向鏈表的插入、刪除及應(yīng)用。目的要求 掌握雙向鏈表的存儲特點及其實現(xiàn)。 掌握雙向鏈表的插入、刪除算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。實驗內(nèi)容 利用尾插法建立一個雙向鏈表。 遍歷雙向鏈表。 實現(xiàn)雙向鏈表中刪除一個指定元素。 在非遞減有序雙向鏈表中實現(xiàn)插入元素e仍有序算法。 判斷雙向鏈表中元素是否對稱若對稱返回1否則返回0。 設(shè)元素為正整型,實現(xiàn)算法把所有奇數(shù)排列在偶數(shù)之前。 在主函數(shù)中設(shè)計一個簡單的菜單調(diào)試上述算法。雙向鏈表的類型定義 typedef int ElemType；/元素類型 typedef struct DuLNode ElemType data; struct DuLNode *prior,*next; DuLNode,*DuLinkList; 注意問題 注意比較單向、雙向鏈表的特點。實驗四 棧隊列實驗學時 學時背景知識：入棧、出棧，入隊、出隊。目的要求 1掌握棧、隊列的思想及其存儲實現(xiàn)。 2掌握棧、隊列的常見算法的程序?qū)崿F(xiàn)。實驗內(nèi)容 1采用鏈式存儲實現(xiàn)棧的初始化、入棧、出棧操作。 2采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作。 3采用鏈式存儲實現(xiàn)隊列的初始化、入隊、出隊操作。 4采用順序存儲實現(xiàn)循環(huán)隊列的初始化、入隊、出隊操作。 5在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。 *6綜合訓練:1)利用棧實現(xiàn)表達式求值算法。 2)利用棧實現(xiàn)迷宮求解。實驗說明 1基本要求：實現(xiàn)算法1、3或算法2、4即可。 2類型定義 順序棧示例#define MAX 100 /棧的最大值typedefstruct ElemType *base；int top；SqStack； 順序隊列示例#define MAX 100 /隊列的最大長度typedefstruct ElemType *base；int front，rear；SqQueue； 3算法6的每個子功能盡可能寫成函數(shù)形式。注意問題 1重點理解棧、隊列的算法思想，能夠根據(jù)實際情況選擇合適的存儲結(jié)構(gòu)。 2注意算法6的各個函數(shù)之間值的傳遞情況。 3棧、隊列的算法是后續(xù)實驗的基礎(chǔ)（廣義表、樹、圖、查找、排序等）。實驗五 二叉樹的常見操作實驗學時 學時背景知識：二叉樹的存儲、建立、遍歷及其應(yīng)用。目的要求 1掌握二叉樹的存儲實現(xiàn)。 2掌握二叉樹的遍歷思想。 3掌握二叉樹的常見算法的程序?qū)崿F(xiàn)。實驗內(nèi)容 1輸入字符序列，建立二叉鏈表。 2中序遍歷二叉樹:遞歸算法。 3中序遍歷二叉樹:非遞歸算法。（最好也能實現(xiàn)先序，后序非遞歸算法） 4求二叉樹的高度 。 5求二叉樹的葉子個數(shù)。 *6將二叉鏈表視為森林的孩子兄弟鏈表，計算森林中葉子個數(shù)。 *7建立中序線索二叉樹，并實現(xiàn)中序遍歷。 8借助隊列實現(xiàn)二叉樹的層次遍歷。 9在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。 *10綜合訓練：為N個權(quán)值設(shè)計哈夫曼編碼。實驗說明 類型定義 /二叉鏈表存儲 #define ElemType char/元素類型 typedef struct BiTNode ElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;元素類型可以根據(jù)實際情況選取。注意問題 1注意理解遞歸算法的執(zhí)行步驟。2注意字符類型數(shù)據(jù)在輸入時的處理。3重點理解如何利用棧結(jié)構(gòu)實現(xiàn)非遞歸算法。實驗六 圖的有關(guān)操作實驗學時 學時背景知識：圖的存儲、遍歷、及其應(yīng)用。目的要求 掌握圖的存儲思想及其存儲實現(xiàn)。 掌握圖的深度、廣度優(yōu)先遍歷算法思想及其程序?qū)崿F(xiàn)。 掌握圖的常見應(yīng)用算法的思想及其程序?qū)崿F(xiàn)。實驗內(nèi)容 鍵盤輸入數(shù)據(jù)，建立一個有向圖的鄰接表。 輸出該鄰接表。 *建立一個無向圖的十字鏈表。 在有向圖的鄰接表的基礎(chǔ)上計算各頂點的度，并輸出。 以有向圖的鄰接表為基礎(chǔ)實現(xiàn)輸出它的拓撲排序序列。 *采用鄰接矩陣存儲一個有向圖，輸出單源點到其它頂點的最短路徑。 采用鄰接表存儲實現(xiàn)無向圖的深度優(yōu)先非遞歸遍歷。 采用鄰接表存儲實現(xiàn)無向圖的廣度優(yōu)先遍歷。 *采用鄰接矩陣存儲實現(xiàn)無向圖的最小生成樹的PRIM算法。 *10判斷無向圖任意兩個頂點間是否有路徑，若有輸出路徑上的頂點序列。11在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法。 *12綜合訓練：為計算機專業(yè)設(shè)計教學計劃：4個學年，每學年2個學期，開設(shè)50門課程，每學期所開課程門數(shù)盡量均衡，課程的安排必須滿足先修關(guān)系。實驗說明 類型定義（鄰接表存儲） #define MAX_VERTEX_NUM 8 /頂點最大個數(shù) typedef struct ArcNode int adjvex; struct ArcNode *nextarc; int weight; /邊的權(quán) ArcNode; /表結(jié)點 #define VertexType int /頂點元素類型 typedef struct VNode int degree,indegree;/頂點的度，入度 VertexType data; ArcNode *firstarc; VNode/*頭結(jié)點*/,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; int vexnum,arcnum;/頂點的實際數(shù)，邊的實際數(shù) ALGraph; 上述類型定義可以根據(jù)實際情況適當調(diào)整。算法、分別利用棧、隊列實現(xiàn)非遞歸算法。 注意問題 注意理解各算法實現(xiàn)時所采用的存儲結(jié)構(gòu)。注意區(qū)別正、逆鄰接。實驗七 查找的有關(guān)操作實驗學時 2學時背景知識:順序查找、樹表查找、散列查找。目的要求： 1掌握折半查找算法的思想及程序?qū)崿F(xiàn)。 2掌握二叉排序樹、AVL樹的查找、插入、刪除、建立算法的思想及程序?qū)崿F(xiàn)。3掌握散列存儲結(jié)構(gòu)的思想，能選擇合適散列函數(shù)，實現(xiàn)不同沖突處理方法的散列表的查找、建立。實驗內(nèi)容 1利用實驗一建立有序表，采用折半查找實現(xiàn)某一已知的關(guān)鍵字的查找。 2隨機產(chǎn)生一組關(guān)鍵字，利用二叉排序樹的插入算法建立二叉排序樹，然后刪除某一指定關(guān)鍵字元素。 *3建立樹并實現(xiàn)刪除某一指定關(guān)鍵字元素。 4已知散列函數(shù)為H(key)=key%p（p為自定的常數(shù)），沖突處理方法分別為線性探測法、外拉鏈法實現(xiàn)散列表的建立（利用插入算法實現(xiàn)）。 實驗說明 1存儲定義（散列表的外拉鏈法） #define n 9 typedef struct node int key; struct node *next; NODE; NODE *HashTable9; 算法1、2、3可以參考順序表，二叉鏈表的存儲實現(xiàn)。2各種關(guān)鍵字數(shù)據(jù)輸入可利用隨機函數(shù)自動產(chǎn)生，以便節(jié)省上機時間。3算法1存儲在文件seqlist.h中,算法2、3存儲在文件bintree.h中,算法4存儲在文件hash.h中注意問題 1注意理解折半查找的適用條件（鏈表能否實現(xiàn)折半查找？）。 2注意建立二叉排序樹、散列表時相同元素的處理。3注意理解靜態(tài)查找、動態(tài)查找概念。4比較各種查找算法的各自特點，能夠根據(jù)實際情況選擇合適的查找方法。實驗八 排序?qū)嶒瀸W時 學時背景知識：各種排序方法目的要求 掌握常見的排序算法的思想及其適用條件。 掌握常見的排序算法的程序?qū)崿F(xiàn)。實驗內(nèi)容 輸入一組關(guān)鍵字序列分別實現(xiàn)下列排序: 1.實現(xiàn)簡單選擇排序、直接插入排序和冒泡排序。 2.實現(xiàn)希爾排序算法。 3.實現(xiàn)快速排序算法。 4.實現(xiàn)堆排序算法。 *5.快速排序的非遞歸算法。 *6.實現(xiàn)折半插入排序。 *7.采用鏈式存儲實現(xiàn)簡單選擇排序、直接插入排序和冒泡排序。8.在主函數(shù)中設(shè)計一個簡單的菜單，分別測試上述算法。 *9綜合訓練：采用幾組不同數(shù)據(jù)測試各個排序算法的性能（比較次數(shù)和移動次數(shù)）。實驗說明 1類型定義 #define MAXSIZE 100 /*參加排序元素的最大個數(shù)*/ typedef struct list int key; RedType; typedef struct RedType rMAXSIZE+1; int length; /*參加排序元素的實際個數(shù)*/ SqList;2算法可以借助棧實現(xiàn)。注意問題 1在RedType中增加一個數(shù)據(jù)項驗證各種排序算法的穩(wěn)定性。2注意理解各種算法的思想、了解算法的適用情況及時間復雜度，能夠根據(jù)實際情況選擇合適的排序方法。/部分算法程序示例/實驗一 線性表的順序存儲結(jié)構(gòu) #include stdio.h #include stdlib.h #define Status int #define OVERFLOW 0 #define TRUE 1 #define FALSE 0 #define OK 1 #define MAXSIZE 100 typedef int ElemType; typedef struct list ElemType elemMAXSIZE; int length; SqList; void InitList(SqList &L) L.length=0; /*建立順序表*/ void CreateList(SqList &L) int i; printf(input the length); scanf(%d,&L.length);/輸入表長 for(i=1;i=L.length;i+) scanf(%d,&L.elemi-1);/輸入元素 /順序表的遍歷 void printdata(ElemType e) printf(%4d,e); void Traverse(SqList L,void (*visit)(ElemType e) int i; printf(The elements of the lists are:n); for(i=1;i=L.length;i+) if (i%10=0)printf(n);/每行顯示10個元素 visit(L.elemi-1);/輸出表中元素 printf(n); /有序順序表L中插入元素e使序列仍有序 void Insert(SqList &L,ElemType e) int i,j; if (L.length=MAXSIZE)exit(OVERFLOW);/表滿,不能插入 for(i=1;i=L.length&L.elemi-1=i;j-) L.elemj=L.elemj-1;/元素后移 L.elemi-1=e;/插入e L.length=L.length+1;/表長加 /建立遞增有序的順序表 void CreateList_Sorted(SqList &L) int i,num; ElemType e; L.length=0; printf(Create a sorted list,Input the length of the listn); scanf(%d,&num); printf(Input the data %d numbersn,num); for(i=1;iMAXSIZE) exit(OVERFLOW); else pa=La.elem;pb=Lb.elem;pc=Lc.elem; while (paLa.elem+La.length&pbLb.elem+Lb.length) *pc+=(*pa=*pb)?*pa+:*pb+;/*公共部分合并*/ while (paLa.elem+La.length) *pc+=*pa+; /*R1表的剩余部分放到R的后部*/ while (pbLb.elem+Lb.length) *pc+=*pb+; /*R2表的剩余部分放到R的后部*/ Lc.length=La.length+Lb.length;/*R表長*/ /判斷元素是否對稱，對稱返回TRUE 否則返回FALSE Status Symmetric(SqList L) int low,high; low=0; high=L.length-1; while(lowhigh) if (L.elemlow=L.elemhigh)low+;high-; else return(FALSE); return(TRUE); /順序表的主函數(shù)部分/#include seqlist.h void main() SqList L1,L2,L; int select; ElemType e; doprintf(n1 insert 2 merge); printf(n3 symmetric 0 exit n); printf(Please select(0-3)n); scanf(%d,&select); switch(select) case 1: InitList(L); CreateList_Sorted(L); Traverse(L,printdata); printf(nInput the element of insertedn); scanf(%d,&e); Insert(L,e); Traverse(L,printdata); break; case 2: InitList(L1); CreateList_Sorted(L1); Traverse(L1,printdata); InitList(L2); CreateList_Sorted(L2); Traverse(L2,printdata); InitList(L); MergeList(L1,L2,L); Traverse(L,printdata); break; case 3: InitList(L); CreateList(L); Traverse(L,printdata); if (Symmetric(L) printf(Yes!n); else printf(Notn); break; case 0:break; default:printf(Error! Try again!n); while(select); /*實驗二 鏈式存儲結(jié)構(gòu)（一）-單向鏈表的有關(guān)操作/*類型定義及頭文件部分,文件名為sllink.h*/ #include #include typedef int ElemType;/元素實際類型 typedef struct LNode ElemType data; struct LNode *next; LNode,*LinkList; /定義結(jié)點、指針類型名 /頭插法建立無序鏈表 void CreateList(LinkList &L) LinkList p; ElemType e; L=(LinkList)malloc(sizeof(LNode); L-next=NULL; printf(頭插法建立鏈表，以0結(jié)束n); scanf(%d,&e); while(e) p=(LinkList)malloc(sizeof(LNode); p-data=e; p-next=L-next; L-next=p; scanf(%d,&e); /*非遞減有序單向鏈表L插入元素e序列仍有序*/ void Insert_Sort(LinkList &L,ElemType e) LinkList p,s; s=(LinkList)malloc(sizeof(LNode); s-data=e; p=L; while(p-next&p-next-datanext;/*查找插入位置*/ s-next=p-next; /*插入語句*p結(jié)點后插入*s結(jié)點*/ p-next=s; /*建立遞增有序的單向鏈表*/ void Create_Sort(LinkList &L) ElemType e; L=(LinkList)malloc(sizeof(LNode); L-next=NULL; printf(建立有序表，輸入任意個整型數(shù)據(jù)以0結(jié)束n); scanf(%d,&e); while(e) Insert_Sort(L,e); scanf(%d,&e); /*單向鏈表的遍歷*/ void Traverse(LinkList L) LinkList p; printf(遍歷鏈表); for(p=L-next;p;p=p-next) printf(%5d,p-data); printf(n); /*在單向鏈表刪除元素e*/ void Delete(LinkList &L,ElemType e) LinkList p,q; p=L; q=L-next; while(q& q-data!=e)/查找元素的刪除位置 p=q; q=q-next; if(!q) printf(nnot deleted);/*未找到元素e*/ else p-next=q-next;/*找到刪除*/ free(q); /*單向鏈表的逆置*/ void exch(LinkList &L) LinkList p,s; p=L-next; L-next=NULL; while(p) s=p; p=p-next; s-next=L-next; L-next=s; /*兩個非遞減有序單向鏈表合并后仍為非遞減序列*/ void MergeIncrease(LinkList La,LinkList Lb,LinkList &Lc) LinkList p,q,s,rear; p=La-next; q=Lb-next; Lc=rear=La; free(Lb); while(p&q) if (p-datadata) s=p;p=p-next; else s=q;q=q-next; rear-next=s;/*較小元素插入表尾*/ rear=rear-next; if (p) rear-next=p; else rear-next=q; /*主函數(shù)部分,文件名為sllink.c*/#include sllink.h void main() LinkList La,Lb,Lc; ElemType e; int select; do printf( 1 建立無序表，再刪除指定元素n); printf( 2 建立遞增有序表，再逆置n); printf( 3 建立兩個遞增有序表，將它們和并為一個仍遞增表n); printf( 0 退出，請輸入選項(0-3)n); scanf(%d,&select); switch(select) case 0: break; case 1: CreateList(La); Traverse(La); printf(輸入需刪除的元素n); scanf(%d,&e); Delete(La,e); Traverse(La); break; case 2: Create_Sort(La); Traverse(La); exch(La); printf(The list that is exchagedn); Traverse(La); break; case 3: Create_Sort(La);Traverse(La); Create_Sort(Lb);Traverse(Lb); MergeIncrease(La,Lb,Lc);Traverse(Lc); break; default: printf(輸入選項錯誤，請重新輸入！n); while(select); 實驗三 鏈式存儲結(jié)構(gòu)（二）-雙向鏈表的有關(guān)操作/*雙向鏈表的有關(guān)操作*/ #include #include typedef int ElemType; typedef struct DuLNode ElemType data; struct DuLNode *prior,*next; DuLNode,*DuLinkList; /*尾插法建立雙向鏈表*/ void CreateList(DuLinkList *L) DuLinkList p; ElemType e; printf(Create a new double_linked_list:n); *L=(DuLinkList)malloc(sizeof(DuLNode); (*L)-next=(*L)-prior=*L; printf(Input data(end of 0)n); scanf(%d,&e); while(e) p=(DuLinkList)malloc(sizeof(DuLNode); p-data=e; p-next=*L; p-prior=(*L)-prior; (*L)-prior=(*L)-prior-next=p; /*在*h結(jié)點前插入結(jié)點*p*/ scanf(%d,&e); /*遍歷雙向鏈表*/ void visit(DuLinkList L) DuLinkList p; printf(遍歷鏈表n); for(p=L-next;p!=L;p=p-next) printf(%5d,p-data); printf(n); /*設(shè)元素為整型,把所有奇數(shù)排列在偶數(shù)之前*/ void Divi(DuLinkList *L) DuLinkList p,q; p=(*L)-next; q=(*L)-prior; while (p!=q) while(p!=q&p-data%2!=0)p=p-next; /*從前向后查找偶數(shù)*/ while(p!=q&q-data%2=0)q=q-prior; /*從后向前查找奇數(shù)*/ (*L)-data=p-data; p-data=q-data; q-data=(*L)-data; / p, q所指結(jié)點的元素交換，頭結(jié)點為中間變量 /*非遞減有序雙向鏈表的插入元素k序列仍有序*/ void Insert(DuLinkList *L,ElemType e) DuLinkList p,s; s=(DuLinkList )malloc(sizeof(DuLNode); s-data=e; p=(*L)-next; while(p!=*L & p-datanext; s-next=p; s-prior=p-prior; p-prior=p-prior-next=s; /*結(jié)點*p之前插入結(jié)點*s */ /*判斷雙向鏈表中元素是否對稱若對稱返回1否則返回0*/ int Symmetric(DuLinkList L) DuLinkList p,q; p=L-next; q=L-prior; while (p!=q&q-next!=p) if (p-data=q-data) p=p-next;q=q-prior; else return(0); return(1); /*主函數(shù)部分*/ void main() DuLinkList L; ElemType e; int select; do printf(n1 Judge if the list is symmetric); printf(n2 divide odd and even); printf(n3 Insert an element in a sorted list); printf(n0 退出 Please select(0-3):n); scanf(%d,&select); switch(select) case 1: CreateList(&L); visit(L); if(Symmetric(L) printf(n元素對稱！); else printf(n元素不對稱！); break; case 2: CreateList(&L);visit(L); Divi(&L);visit(L); break; case 3: CreateList(&L);visit(L); printf(Input an element); scanf(%d,&e); Insert(&L,e); visit(L); break; case 0: break; default: printf(Error! Again!n); while(select); /* 實驗四 棧和隊列 */ #include #include typedef int SElemType;/棧的元素類型 /*鏈棧的定義*/ typedef struct Node SElemType data; struct Node *next; NODE; typedef struct NODE *top;/鏈式棧的棧頂指針 Stack; #define TRUE 1 #define FALSE 0 #define OK 1 #define OVERFLOW -2 typedef int Status; /*鏈式棧的操作示例*/ void InitStack(Stack &S) S.top=(NODE *)malloc(sizeof(NODE); if (!S.top)exit(OVERFLOW);/棧溢出 S.top-next=NULL; Status StackEmpty(Stack S) if (S.top-next=NULL) return(TRUE); else return(FALSE); void Push(Stack &S,SElemType e) NODE *p; p=(NODE *)malloc(sizeof(NODE); if (!p)return; /棧滿溢出 p-data=e; p-next=S.top-next; S.top-next=p; void Pop(Stack &S,SElemType &e) NODE *p; if (StackEmpty(S) return;/?？?else p=S.top-next; e=p-data; S.top-next=p-next; free(p); SElemType Gettop(Stack &S) NODE *p; if (StackEmpty(S)return 0;/?？?else p=S.top-next; return(p-data); /*主函數(shù)部分示例文件名為stackqueue.c*/#include linksq.h void main() int select; SElemType num=1,e; Stack S; InitStack(S); do printf(n1 Push 2 Popn); printf(0 exitn please selcet(0-2)n); scanf(%d,&select); switch(select) case 1: printf(Push%2d ,num); Push(S,num+); b