【正文】 個元素是整型，則使用typedef int ElemType?！菊f明2】――鏈表的定義與操作1．根據(jù)一個完整的C 語言組成，將實(shí)驗(yàn)內(nèi)容組合成如上所述的三個組成部分，功能清晰明了，其常量定義和常用系統(tǒng)函數(shù)原型聲明的文件“”代碼復(fù)用，不需另行建立。四、基本實(shí)驗(yàn)的參考程序（一）線性表的順序存儲結(jié)構(gòu)的定義及其基本操作的參考程序（順序表）(1) 文件1： pubuse. h 是公共使用的常量定義和系統(tǒng)函數(shù)調(diào)用聲明，以后每個實(shí)驗(yàn)中幾乎都涉及到此文件。 /* 存儲空間基址*/int length。L) /* 算法2. 3 */{ /* 操作結(jié)果：構(gòu)造一個空的順序線性表*/L. elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))。 /* 初始存儲容量*/return OK。if(L. length=L. listsize) /* 當(dāng)前存儲空間已滿,增加分配*/{newbase=(ElemType *)realloc(L. elem,(L. listsize+LISTINCREMENT)*sizeof(ElemType))。 /* 增加存儲容量*/}q=L. elem+i1。*q=e。L,int i,ElemType *e) /* 算法2. 5 */{ /* 初始條件：順序線性表L 已存在，1≤i≤ListLength(L) *//* 操作結(jié)果：刪除L 的第i 個數(shù)據(jù)元素，并用e 返回其值，L 的長度減1 */ElemType *p,*q。 /* 被刪除元素的值賦給e */q=L. elem+L. length1。L. length。for(i=0。}Status ListDestroy_Sq(SqList L){/*初始條件：順序線性表L已存在*//*操作結(jié)果：銷毀順序線性表L*/free()。return OK。elsereturn FALSE。return OK。int j。j=5。/* 隨機(jī)指定插入點(diǎn)位置，假設(shè)在第二個元素前插入新的元素，其值為20 */ListDelete_Sq(L,4,amp。/* 檢驗(yàn)一下插入和刪除后的結(jié)果，輸出表La 的內(nèi)容*/}（二）線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的定義及其基本操作的參考程序（鏈表）1． 是線性表的單鏈表存儲結(jié)構(gòu)的定義struct LNode{ElemType data。 /* 另一種定義LinkList 的方法*/2． 是單鏈表的基本算法描述/* 以下的算法均是針對帶表頭結(jié)點(diǎn)的單鏈表*/Status ListInit_Link(LinkList amp。 /* 指針域?yàn)榭?/return OK。free(L)。*//* 操作結(jié)果：將L 重置為空表*/LinkList p,q。p=q。*//* 操作結(jié)果：若L 為空表，則返回TRUE，否則返回FALSE */if(Lnext) /* 非空*/return FALSE。LinkList p=Lnext。}Status GetElem_Link (LinkList L,int i,ElemType amp。amp。e=pdata。LinkList p=Lnext。}return 0。amp。s=(LinkList)malloc(sizeof(struct LNode))。return OK。while(pnextamp。}if(!pnext||ji1) /* 刪除位置不合理*/return ERROR。free(q)。p=pnext。L,int n) /* */{ /* 逆位序(插在表頭)輸入n 個元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表L */int i。 /* 先建立一個帶頭結(jié)點(diǎn)的單鏈表*/printf(請輸入%d 個數(shù)據(jù)\n,n)。 /* 生成新結(jié)點(diǎn)*/scanf(%d,amp。}}3．將測試數(shù)據(jù)和主函數(shù)新定義一個文件,如取名為:./* 、*/includetypedef int ElemType。ElemType e。 /* 輸出鏈表Lb 的內(nèi)容*/ListTraverse_Link (Lb)。e)。 /* 輸出鏈表Lc 的內(nèi)容*/ListTraverse_Link (Lb)。ListDelete_Link (Lb,i,e)。}五、實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)步驟實(shí)驗(yàn)環(huán)境： 利用Visual C++集成開發(fā)環(huán)境進(jìn)行本實(shí)驗(yàn)的操作。4. 新建文件/C/C++ Header File，選中“添加到工程的復(fù)選按鈕”，輸入文件名“seqlistDef. h”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。8．按Ctrl+F5 鍵，或工具圖標(biāo)進(jìn)行工程的執(zhí)行。4. 新建文件/C/C++ Header File，選中“添加到工程的復(fù)選按鈕”，輸入文件名“”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。六、思考題1．寫出動態(tài)生成鏈表的算法或程序。定義鏈?zhǔn)疥?duì)列，完成隊(duì)列的基本操作：入隊(duì)和出隊(duì)。. 讀取棧頂指針?biāo)赶虻脑氐闹?。以此來?shí)現(xiàn)十進(jìn)制數(shù)與八進(jìn)制數(shù)的轉(zhuǎn)換。. 完成一個元素的出隊(duì)操作，修改隊(duì)頭指針。.“初始化棧算法”操作結(jié)果：構(gòu)造一個空棧S。.“求棧的長度算法” 操作結(jié)果：返回S 的元素個數(shù)，即棧的長度。否則返回ERROR。.“銷毀隊(duì)列算法”操作結(jié)果：銷毀隊(duì)列Q(無論空否均可)。.“取隊(duì)頭元素算法” 操作結(jié)果：若隊(duì)列不空,則用e 返回Q 的隊(duì)頭元素,并返回OK,否則返回ERROR。2． 將順序棧的基本操作算法也集中放在一個文件之中。2．將鏈?zhǔn)疥?duì)列的基本操作算法也集中放在一個文件之中。 /* 在棧構(gòu)造之前和銷毀之后，base 的值為NULL */SElemType *top。S){ /* 構(gòu)造一個空棧S */=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))。return OK。=NULL。S){ /* 把S 置為空棧*/=。}int StackLength(SqStack S){ /* 返回S 的元素個數(shù)，即棧的長度*/return 。return OK。if(!)exit(OVERFLOW)。return OK。否則返回ERROR */if(==)return ERROR。*//* 一旦visit()失敗，則操作失敗*/while()visit(*++)。unsigned n。scanf(%u,amp。}while(!StackEmpty(s)) /* 當(dāng)棧不空*/{Pop(s,e)。typedef int SElemType。struct QNode *next。2． 中實(shí)現(xiàn)的鏈隊(duì)列的基本算法。next=NULL。free()。Q){ /* 將Q 清為空隊(duì)列*/QueuePtr p,q。while(p){q=p。}Status QueueEmpty(LinkQueue Q){ /* 若Q 為空隊(duì)列,則返回TRUE,否則返回FALSE */if(==)return TRUE。p=。}Status GetHead_Q(LinkQueue Q,QElemType amp。e=pdata。if(!p) /* 存儲分配失敗*/exit(OVERFLOW)。=p。e){ /* 若隊(duì)列不空,刪除Q 的隊(duì)頭元素,用e 返回其值,并返回OK,否則返回ERROR */QueuePtr p。next=pnext。}Status QueueTraverse(LinkQueue Q,void(*vi)(QElemType)){ /* 從隊(duì)頭到隊(duì)尾依次對隊(duì)列Q 中每個元素調(diào)用函數(shù)vi()。p=pnext。include /* 與實(shí)驗(yàn)一的意義相同*/typedef int QElemType。LinkQueue q。printf(隊(duì)列的長度為%d\n,QueueLength(q))。printf(插入3 個元素(5,5,10)后,隊(duì)列的長度為%d\n,QueueLength(q))。i=GetHead_Q(q,d)。i=GetHead_Q(q,d)。DestroyQueue(q)。，選擇輸入位置：如“d:\”，輸入工程的名稱：如“SqStackDemo”。6. 新建文件/C++ Source File，選中“添加到工程的復(fù)選按鈕”，輸入文件名“”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。按“確定”按鈕，選擇“An Empty Project”，再按“完成”按鈕，3． 選中菜單的”project”“add to project” “files”選擇已存在文件，確定， 拷貝到所建的工程目錄下。7．構(gòu)件、調(diào)試、運(yùn)行與實(shí)驗(yàn)一相同，在此不再復(fù)述。首先從線性表第1 個元素開始，依次將其元素壓入棧中，然后將棧中元素依次彈出，重新放入數(shù)組a 中。在循環(huán)隊(duì)列中，最初隊(duì)列為空時隊(duì)首指針front 和隊(duì)尾指針rear都指向同一位置，當(dāng)有元素入隊(duì)時，由于是循環(huán)的，所以rear 位置前移，即：QU. rear = (QU. rear + 1) % mo將插入元素放到rear 的新位置上。. 實(shí)現(xiàn)二叉樹的遞歸(先序、中序或后序)遍歷算法。. 判斷某棵二叉樹是否為空。. 編寫主程序，實(shí)現(xiàn)對各不同的算法調(diào)用。操作結(jié)果: 銷毀二叉樹T 。操作結(jié)果: 若T 為空二叉樹,則返回TRUE,否則FALSE 。操作結(jié)果: 返回T 的根。操作結(jié)果: 中序遞歸遍歷T,對每個結(jié)點(diǎn)調(diào)用函數(shù)Visit 一次且僅一次。2．將二叉樹的基本操作算法也集中放在一個文件之中。2． 中實(shí)現(xiàn)了二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)定義typedef struct BiTNode{TElemType data。T){ /* 操作結(jié)果: 構(gòu)造空二叉樹T */T=NULL。操作結(jié)果: 銷毀二叉樹T */if(T) /* 非空樹*/{if(Tlchild) /* 有左孩子*/DestroyBiTree(Tlchild)。 /* 空指針賦0 */}}define ClearBiTree DestroyBiTreevoid CreateBiTree(BiTree amp。ifdef CHARscanf(%c,amp。endifif(ch==Nil) /* 空*/T=NULL。 /* 生成根結(jié)點(diǎn)*/CreateBiTree(Tlchild)。}int BiTreeDepth(BiTree T){ /* 初始條件: 二叉樹T 存在。elsei=0。}TElemType Root(BiTree T){ /* 初始條件: 二叉樹T 存在。}void Assign(BiTree p,TElemType value){ /* 給p 所指結(jié)點(diǎn)賦值為value */pdata=value。 /* 再先序遍歷左子樹*/PreOrderTraverse(Trchild,Visit)。 /* 最后中序遍歷右子樹*/}}void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始條件: 二叉樹T 存在,Visit 是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)*//* 操作結(jié)果: 后序遞歸遍歷T,對每個結(jié)點(diǎn)調(diào)用函數(shù)Visit 一次且僅一次*/if(T) /* T 不空*/{PostOrderTraverse(Tlchild,Visit)。TElemType Nil=39。 /* 整型以0 為空*/endifinclude /* 二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)定義*/include /* 二叉樹基本算法和擴(kuò)展算法定義*/Status visitT(TElemType e){ifdef CHARprintf(%c ,e)。TElemType e1。if(e1!=Nil)ifdef CHARprintf(二叉樹的根為: %c\n,e1)。endififdef INTprintf(請先序輸入二叉樹(如:1 2 0 0 0 表示1 為根結(jié)點(diǎn),2 為左子樹的二叉樹)\n)。if(e1!=Nil)ifdef CHARprintf(二叉樹的根為: %c\n,e1)。InOrderTraverse(T,visitT)。（一）基本實(shí)驗(yàn)的實(shí)驗(yàn)步驟：1．啟動VC++。5. 新建文件/C/C++ Header File，選中“添加到工程的復(fù)選按鈕”，輸入文件名“”，按“確定”按鈕，在顯示的代碼編輯區(qū)內(nèi)輸入如上的參考程序。. 用廣度優(yōu)先搜索方法找出從一頂點(diǎn)到另一頂點(diǎn)邊數(shù)最少的路徑。. 實(shí)現(xiàn)從第v 個頂點(diǎn)出發(fā)對圖進(jìn)行深度優(yōu)先遞歸遍歷。2．實(shí)現(xiàn)要求：（以鄰接表存儲形式為例）編寫圖的基本操作函數(shù):：對圖的各項(xiàng)操作一定要編寫成為C（C++）語言函數(shù)，組合成模塊化的形式，每個算法的實(shí)現(xiàn)要從時間復(fù)雜度和空間復(fù)雜度上進(jìn)行評價。操作結(jié)果：返回圖的按廣度遍歷的結(jié)果。三、實(shí)驗(yàn)指導(dǎo):本實(shí)驗(yàn)以圖的鄰接表存儲結(jié)構(gòu)為例，要求完成基本要求，同時對無向圖，有向網(wǎng)，無向網(wǎng)也一并實(shí)現(xiàn)其相關(guān)的操作，課后同學(xué)們可以用鄰接矩陣式存儲結(jié)構(gòu)完成以上操作。2． 是鏈?zhǔn)疥?duì)列的存儲結(jié)構(gòu)。 /* 該弧所指向的頂點(diǎn)的位置*/struct ArcNode *nextarc。 /* 頂點(diǎn)信息*/ArcNode *fi