數(shù)據(jù)結(jié)構(gòu)-實驗指導(dǎo)書(自編簡).doc

數(shù)據(jù)結(jié)構(gòu)（C語言版）實驗指導(dǎo)書（非計算機專業(yè)適用）廣州大學(xué)2013.1目 錄實驗一 線性表的順序存儲及其操作1實驗二 線性表的鏈?zhǔn)酱鎯捌洳僮?實驗三 棧和隊列的應(yīng)用7實驗四 串及其操作9實驗五 樹及其操作11實驗六 圖及其操作16實驗七 查找和排序22實驗一 線性表的順序存儲及其操作預(yù)習(xí)題：1、 線性表是如何定義的？有什么特點？2、 線性表有哪些實現(xiàn)方法？3、 線性表的順序存儲和鏈?zhǔn)酱鎯Ω饔惺裁磧?yōu)缺點？4、 在線性表的順序存儲中，插入和刪除都需要進行數(shù)據(jù)元素的遷移，問：兩者遷移的方法有何異同？（從遷移的內(nèi)容、遷移的順序來分析）5、 順序存儲的線性表進行內(nèi)容的翻轉(zhuǎn)時，和數(shù)據(jù)元素的奇偶性有關(guān)嗎？實驗項目：線性表的順序?qū)崿F(xiàn)：查找、插入、刪除、翻轉(zhuǎn)實驗類型: 基礎(chǔ)性指導(dǎo)思想：用數(shù)組存儲線性表，實現(xiàn)線性表的基本操作。實驗?zāi)康募耙螅?、 復(fù)習(xí)C語言的數(shù)組的定義；2、 理解線性表的屬性；3、 實踐線性表的順序?qū)崿F(xiàn)方法以及相關(guān)的操作；4、 要求：提交實驗報告，附源程序、打印運行結(jié)果。涉及的知識點：線性表的邏輯屬性、運算單數(shù)組的操作：定義、輸入、輸出、數(shù)組內(nèi)容的翻轉(zhuǎn)元素/數(shù)組的操作：元素的檢索、插入、刪除實驗內(nèi)容：實現(xiàn)數(shù)組的輸入、輸出、查找、插入、刪除、翻轉(zhuǎn)等功能，每個功能用一個函數(shù)實現(xiàn)，在主程序中按以下要求把這些函數(shù)組織起來。實驗步驟：編寫具有以下功能的程序：1、 從鍵盤讀入10個整數(shù)（或字符）； 2、 顯示當(dāng)前數(shù)組內(nèi)容；3、 輸入一個數(shù)組元素，顯示該元素在線性表中的位置；重復(fù)本過程，元素在表頭、表中、表尾的各一次；4、 輸入一個不在數(shù)組中的數(shù)據(jù)，程序要檢測出該元素不在線性表內(nèi)；5、 輸入一個新的數(shù)組元素和要插入的位置，把該元素插入后顯示數(shù)組內(nèi)容；重復(fù)本過程，插入的位置在表頭、表中、表尾的各一次；6、 輸入一個合理的元素位置，刪除該位置上的元素，顯示數(shù)組內(nèi)容；重復(fù)本過程，插入的位置在表頭、表中、表尾的各一次；7、 把數(shù)組的內(nèi)容翻轉(zhuǎn)后輸出；8、 刪除一個數(shù)組元素，使得數(shù)組元素個數(shù)的奇偶性改變，再翻轉(zhuǎn)一次、輸出，以確認翻轉(zhuǎn)過程適合于奇數(shù)和偶數(shù)長度的數(shù)組。- 22 -實驗二 線性表的鏈?zhǔn)酱鎯捌洳僮黝A(yù)習(xí)題：1、 線性表的鏈?zhǔn)酱鎯υ谀男┓矫姹软樞虼鎯σ茫?、 在線性表的鏈?zhǔn)酱鎯χ?，插入和刪除都需要進行數(shù)據(jù)元素的遷移嗎？3、 為什么鏈表的插入和刪除操作都需要記住被操作的結(jié)點的前一個結(jié)點？4、 鏈?zhǔn)酱鎯Φ木€性表進行內(nèi)容的翻轉(zhuǎn)時，和數(shù)據(jù)元素的奇偶性有關(guān)嗎？實驗項目：線性表的鏈表實現(xiàn)：遍歷、插入、刪除、翻轉(zhuǎn)實驗類型: 基礎(chǔ)性指導(dǎo)思想：用鏈表存儲線性表，實現(xiàn)線性表的基本操作。實驗?zāi)康募耙螅?、 復(fù)習(xí)C語言的指針的定義、鏈表的使用；2、 理解線性表的屬性；3、 實踐線性表的鏈?zhǔn)綄崿F(xiàn)方法以及相關(guān)的操作。4、 要求：提交實驗報告，附源程序中填空的內(nèi)容（10處）、打印運行結(jié)果涉及的知識點：線性表的邏輯屬性、運算帶表頭的單鏈表的操作：定義、輸入、輸出、鏈表內(nèi)容的翻轉(zhuǎn)元素/鏈表的操作：元素的插入、刪除實驗內(nèi)容：實現(xiàn)鏈表的輸入、輸出、插入、刪除、翻轉(zhuǎn)等功能，教師提供主要源代碼，其中有10處標(biāo)出需要學(xué)生填空，使得整個程序能正確運行。問題描述：用帶表頭的鏈表存放輸入的數(shù)據(jù)，每讀入一個數(shù)，按升序順序插入到鏈表中，鏈表中允許兩個結(jié)點有相同值。鏈表的頭結(jié)點存放鏈表后面的結(jié)點個數(shù)，初始化時就生成頭結(jié)點（初值為0）。鏈表翻轉(zhuǎn)是把數(shù)據(jù)逆序（變成降序），注意，頭結(jié)點不動。翻轉(zhuǎn)后要再翻轉(zhuǎn)一次，恢復(fù)升序后才能插入新元素，否則會出錯。實驗步驟：讀懂后面附帶的源代碼，在標(biāo)注“填空”的位置填寫適當(dāng)?shù)谋磉_式或語句，使得程序完成指定功能。測試要求：1、 連續(xù)插入5個實數(shù)；要求：插入的元素要分別位于表頭、表中、表尾，以確保該插入函數(shù)適合于各種情況；2、 翻轉(zhuǎn)鏈表，確認成功后再翻轉(zhuǎn)一次，恢復(fù)元素的升序序列；3、 刪除3個數(shù)組元素，刪除的元素要分別要位于表頭、表中、表尾，以確保該刪除函數(shù)適合于各種情況；4、 刪除一個不存在的元素，確認鏈表的內(nèi)容沒被改變。以下是待填空的源代碼，請同學(xué)們粘貼到系統(tǒng)中填空、運行、測試：/* 鏈表操作：插入、刪除、輸出、翻轉(zhuǎn)用帶表頭的鏈表存放輸入的數(shù)據(jù)，每讀入一個數(shù)，按升序順序插入到鏈表中，鏈表中允許兩個結(jié)點有相同值。鏈表的頭結(jié)點存放鏈表后面的結(jié)點個數(shù)，初始化時就生成頭結(jié)點（初值為0）。鏈表翻轉(zhuǎn)是把數(shù)據(jù)逆序（變成降序），注意，頭結(jié)點不動。翻轉(zhuǎn)后要再翻轉(zhuǎn)一次，恢復(fù)升序后才能插入新元素，否則會出錯。 */#include #include malloc.h#define null 0struct node float data;struct node *next;void insert(float aa,struct node *vq)struct node *newnode,*p;newnode=(struct node *)malloc(sizeof(struct node);newnode-data=aa;p=vq;while (p-next!=null)&(p-next-datanext=p-next;/* 填空2 */;vq-data=vq-data+1;void dele(float aa,struct node *vq) struct node *p,*q;p=vq;while (p-next!=null)&(p-next-datanext=null)|(p-next-data!=aa)printf(n%5.1f is not in the link !,aa);else if (p-next-data=aa) q=p-next;p-next=/* 填空4 */;free(/* 填空5 */);vq-data=vq-data-1;void print(struct node *vq)struct node *p;printf(nthe length of link is %4.0f,vq-data);p=vq-next;printf(nthe link is:);while (/* 填空6 */) printf(%5.1f,p-data);/* 填空7 */;void reverse(struct node *vq) struct node *q,*p;p=(*vq)-next;(*vq)-next=/* 填空8 */;while (p!=null) q=p; p=/* 填空9 */; q-next=/* 填空10 */; (*vq)-next=q; main() int mark=1,op;float aa;struct node *vq;vq=(struct node *)malloc(sizeof(struct node);vq-data=0;vq-next=null;while (mark=1) printf(nWhich kind of operation will you select ? );printf(ninsert-1, delete-2, print-3, reverse-4, exit-0 : );scanf(%d,&op);switch (op) case 0: mark=0; break;case 1: printf(nPlease input the new element:);scanf(%f,&aa);insert(aa,vq);print(vq);break;case 2: if (vq-data=0)printf(n the link is null !,aa);elseprintf(nPlease input the deleted element:);scanf(%f,&aa);dele(aa,vq); print(vq);break;case 3: print(vq); break;case 4: reverse(&vq); print(vq);break;default:printf( input error!n);/*程序結(jié)束*/實驗三 棧和隊列的應(yīng)用預(yù)習(xí)題：1、 棧和隊列是如何定義的？各有什么特點？2、 棧和隊列有哪些實現(xiàn)方法？3、 棧和隊列的順序存儲和鏈?zhǔn)酱鎯Ω饔惺裁磧?yōu)缺點？實驗項目：棧和隊列及其操作的實現(xiàn)；棧和隊列的應(yīng)用實驗類型：設(shè)計性指導(dǎo)思想：棧和隊列是兩種常用的和重要的數(shù)據(jù)結(jié)構(gòu)。利用順序存儲或鏈?zhǔn)酱鎯崿F(xiàn)棧和隊列及其基本操作，在此基礎(chǔ)上，應(yīng)用棧和隊列解決實際問題。培養(yǎng)學(xué)生解決問題的能力。實驗?zāi)康募耙螅?、 熟悉棧和隊列的定義和特點；2、 實踐棧和隊列的順序和鏈?zhǔn)綄崿F(xiàn)方法以及相關(guān)的操作；3、 根據(jù)實際問題的要求，合理使用棧和隊列，設(shè)計相關(guān)程序；4、 要求：提交實驗報告，附源程序、打印運行結(jié)果。涉及的知識點：棧和隊列的存儲方法棧的常用操作（構(gòu)造、銷毀、入棧、出棧、讀棧、判斷棧空或滿）隊列的常用操作（構(gòu)造、銷毀、入隊列、出隊列、判斷隊列空或滿）實驗內(nèi)容：根據(jù)以下兩個問題的要求，合理使用棧和隊列，設(shè)計相關(guān)程序：項目一：字符串回文的判斷“回文”英語叫做Palindrome，是指一個單字或名詞或句子，順讀倒讀都可成立的，英語單字中順讀倒讀仍是同一字的有：civic，deed，did，gag，level，madam，noon，peep，refer，rotator。亞當(dāng)同學(xué)剛剛碰到夏娃小姐時說的是什么？“Madam, Im Adam.”Napoleon被關(guān)的時候因為過度無聊也寫過這玩意兒: Able Was I Ere I Saw Elba還有一些palindrome：No lemons，no melon.Dogs sass GodSilly ram ate wet amaryllis!Now, evil, Ive won!Was it a cat I saw? 這個的高級版本是Was it a car or a cat I saw？通過程序自動判斷用戶輸入的字符串是否回文。提示：首先構(gòu)造一個棧和隊列，將用戶輸入的字符串同時入棧和入隊列。然后當(dāng)?；蜿犃胁粸榭諘r，將出棧和出隊列的元素進行比較，若全部一致，則為回文。顯示效果如下圖所示：項目二：判別表達式中的括號（“ 、()” ）是否匹配表達式運算是計算機重要應(yīng)用之一，而判斷表達式是表達式運算的基礎(chǔ)。通過程序自動判斷用戶輸入的表達式中的括號是否匹配。顯示效果如下圖所示：實驗四 串及其操作預(yù)習(xí)題：1、 C語言是如何存儲字符串的？與普通的字符型數(shù)組有何區(qū)別？2、 C語言的標(biāo)準(zhǔn)庫函數(shù)提供了哪些串的函數(shù)？你自己能編寫實現(xiàn)其相同功能的函數(shù)嗎？3、 多個字符串合并時，如何處理結(jié)束符？4、 串的模式匹配算法是怎樣的？5、 若主串中有多個地方匹配子串，要返回首次匹配的位置、返回最后匹配的位置、返回所有匹配的位置，各如何處理？實驗項目：串的操作：單個字符串的長度統(tǒng)計、翻轉(zhuǎn)、多個字符串的合并、子串判別實驗類型：基礎(chǔ)性指導(dǎo)思想：熟練掌握C語言的字符串操作方法，理解字符串與字符型數(shù)組的差異。實驗?zāi)康募耙螅?、 復(fù)習(xí)C語言的字符串的使用；2、 理解串的操作；3、 實現(xiàn)串的模式匹配算法；4、 要求：提交實驗報告，附源程序、打印運行結(jié)果。涉及的知識點：串的存儲方法常見的串的函數(shù)（求長度、兩個字符串的連接）串的模式匹配BF算法（又稱古典的、經(jīng)典的、樸素的、窮舉的）實驗內(nèi)容：讀入兩個字符串，輸出其長度、連接之后的結(jié)果，再判斷第一個字符串是否第二個串的子串。實驗步驟：編寫具有以下功能的程序：1. 讀入兩個字符串S1、S22. 分別顯示這S1、S2的及長度3. 自己編寫函數(shù)，把S1的內(nèi)容翻轉(zhuǎn)，即把S1逆序，生成S3，顯示S3的內(nèi)容、長度。提示：字符串結(jié)束符要單獨處理。4. 分別顯示S1+S2、S2+S1的結(jié)果5. 判斷S1是否S2的子串6. 測試要求：a) S1、S2要帶字母、數(shù)字、空格b) S1是S2的子串、S1不是S2的子串的各試一次實驗五 樹及其操作預(yù)習(xí)題：1、 二叉樹是如何遞歸定義的？有什么特點？2、 滿二叉樹和完全二叉樹有何區(qū)別？3、 為什么要進行樹的遍歷？4、 樹的遍歷方法有幾種？對于每一種來說，遍歷的結(jié)果是惟一的嗎？5、 根據(jù)哪兩種遍歷結(jié)果，能夠還原二叉樹的結(jié)構(gòu)？6、 樹的層次遍歷要用到我們前面學(xué)的什么結(jié)構(gòu)？實驗項目：二叉樹的存儲及先序、中序、后序、層次遍歷實驗類型：設(shè)計性指導(dǎo)思想：掌握把非線性結(jié)構(gòu)的樹數(shù)據(jù)轉(zhuǎn)換為線性結(jié)構(gòu)的多種方法實驗?zāi)康募耙螅?、 理解樹的邏輯結(jié)構(gòu)以及實現(xiàn)方法，尤其是在程序中的表達；2、 掌握樹的多種遍歷方法，先序、中序、后序的遞歸方法以及層次遍歷的思想和實現(xiàn)方法；3、 設(shè)計統(tǒng)計二叉樹的結(jié)點個數(shù)、葉片個數(shù)的算法；4、 要求：提交實驗報告，附自己編寫中序、后序遞歸函數(shù)、層次遍歷函數(shù)、統(tǒng)計二叉樹的結(jié)點個數(shù)、葉片個數(shù)函數(shù)的代碼，并打印運行結(jié)果。涉及的知識點：樹的三種遞歸遍歷方法、遞歸程序設(shè)計樹的層次遍歷算法、隊列實驗內(nèi)容：自己編寫或粘貼后面附錄的源程序，完成樹的輸入、先序、中序、后序、層次遍歷等功能。實驗步驟：1. 設(shè)計二叉樹的表達方法；2. 輸入一棵二叉樹：要求該樹至少包含五個結(jié)點，帶有一個兒子、兩個兒子的結(jié)點；3. 編寫樹的先序、中序、后序遍歷的函數(shù)，看輸出結(jié)果，確認樹的結(jié)構(gòu)和自己輸入的一致；4. 在上一步正確的基礎(chǔ)上，運用隊列結(jié)構(gòu)，對樹進行層次遍歷；5. 統(tǒng)計并輸出樹的結(jié)點個數(shù)、葉片個數(shù)；附錄：樹的操作的部分源代碼：#include #include #define null 0typedef char nodedatatype;typedef struct node nodedatatype data; struct node *lchild,*rchild;bintnode;/* 定義二叉鏈表結(jié)點結(jié)構(gòu) */typedef bintnode *bintree;/* 定義二叉鏈表指針類型 */ABCDEF/* 使用已經(jīng)定義的循環(huán)隊列*/typedef bintree DataType;typedef int Status;#include SQueue.hcreatebintree(bintree *t) /* 輸入二叉樹的先序遍歷序列*/*（例如上圖所示二叉樹的先序遍歷序列輸入為：ABDECF，其中表示空格）*/* 創(chuàng)建二叉鏈表 */ char ch; if (ch=getchar()= )/* 如果讀入空格字符，創(chuàng)建空樹 */ *t=null; else *t=(bintnode*)malloc(sizeof(bintnode);/* 申請根結(jié)點*t空間 */ (*t)-data=ch;/* 將結(jié)點數(shù)據(jù)ch放入根結(jié)點的數(shù)據(jù)域 */ createbintree(&(*t)-lchild);/* 建左子樹 */ createbintree(&(*t)-rchild);/* 建右子樹 */ /* end of if */ /* end of creatbintree */preorder(bintree t) /* 對二叉樹進行先序遍歷 */ if (t) printf(%c,t-data); preorder(t-lchild); preorder(t-rchild); /* end of if */ /* end of preorder */ inorder(bintree t) /* 對二叉樹進行中序遍歷 */ /* end of inorder */postorder(bintree t) /* 對二叉樹進行后序遍歷 */ /* end of postorder */error(char *message) /* 出錯時，調(diào)用的返回出錯信息，終止程序運行的函數(shù) */ fprintf(stderr,error:%sn,message); exit(1); leverorder(bintree t) /* 對二叉樹進行層次遍歷，用到隊列 */ SQInit(&myQueue);/*創(chuàng)建隊列*/ SQAppend(&myQueue,t);/* 將根結(jié)點入隊 */ while (!SQIsEmpty(myQueue) /* end of while */ /* end of leverorder */int leave(bintree t) /* 求以t為樹根的二叉樹的葉子總數(shù) */ leavelist(bintree t) /* 輸出以t為樹根的二叉樹的葉子信息 */ if (t) leavelist(t-lchild);/* 輸出左子樹中的所有葉子 */ if (t-lchild=null)&(t-rchild=null) /* 若根結(jié)點為葉子，則輸出葉子的數(shù)據(jù)域信息 */ printf(%c,t-data); leavelist(t-rchild);/* 輸出右子樹中的所有葉子 */ /* end of if */ /* end of inorder */int nodes(bintree t) /* 求以t為樹根的二叉樹的結(jié)點總數(shù) */ /* end of node */main()/* 主函數(shù) */ /* 建立二叉樹的二叉鏈表表示，并進行先序遍歷、中序遍歷、后序遍歷和按層次遍歷， */ /* 求出所有葉子和結(jié)點總數(shù)。 */ bintree t=null; int n; printf(please input nodes of bintree:n); createbintree(&t);/* 建立二叉鏈表 */ printf(the preorder is:); preorder(t);/* 對二叉樹t進行先序遍歷 */ printf(n); printf(the inorder is:); inorder(t);/* 對二叉樹t進行中序遍歷 */ printf(nthe postorder is:); postorder(t);/* 對二叉樹t進行后序遍歷 */ printf(nthe leverorder is:); leverorder(t);/*對二叉樹t進行按層次遍歷 */ n=leave(t);/* 求出二叉樹的葉子數(shù)n */ printf(nthe leave of bintree is: %d,n);/* 打印二叉樹的葉子總數(shù) */ if (n)/* 當(dāng)葉子數(shù)不為0 */ printf(nthe list of leave is:); leavelist(t);/* 輸出所有的葉子 */ else printf(nno leave!);/* 輸出無葉子（即空樹）信息 */ printf(nthe nodes of bintree is: %dn,nodes(t);/* 輸出二叉樹的總結(jié)點數(shù) */ getchar();/*暫停，任意鍵繼續(xù)*/ getchar(); 顯示結(jié)果如右圖所示。實驗六 圖及其操作預(yù)習(xí)題：1、 為什么要進行圖的遍歷？2、 圖有幾種遍歷方法？遍歷的結(jié)果是惟一的嗎？3、 任何一個無向連通圖都有生成樹嗎？4、 一個無向連通圖的生成樹是惟一的嗎？5、 從指定的結(jié)點出發(fā)，一個無向連通圖的深度（廣度）優(yōu)先樹是惟一的嗎？6、 對于某個圖來說，廣度優(yōu)先生成樹和深度優(yōu)先生成樹有可能相同嗎？實驗項目：修改已有的先深、先廣遍歷程序，求先深、先廣遍歷生成樹實驗類型：基礎(chǔ)性指導(dǎo)思想：掌握非線性結(jié)構(gòu)的圖在程序中的存儲方法以及相應(yīng)的操作實驗?zāi)康募耙螅?、 學(xué)會把圖轉(zhuǎn)化為程序能識別的鄰接矩陣；2、 透徹理解圖的兩種遍歷方法及對應(yīng)的生成樹。涉及的知識點：圖的表示法生成樹的概念圖的深度優(yōu)先遍歷算法圖的廣度優(yōu)先遍歷算法ABCDEFGH實驗內(nèi)容：自己編寫或粘貼后面附錄的源程序，把圖的深度優(yōu)先遍歷、廣度優(yōu)先遍歷改為輸出深度優(yōu)先生成樹、廣度優(yōu)先生成樹。實驗步驟：1問題的描述該程序是對圖進行先深、先廣遍歷，請在此基礎(chǔ)上，改為處理指定圖，求該圖從指定結(jié)點出發(fā)的先深、先廣遍歷生成樹。實驗步驟：1、讀懂教師給定的程序或課本的程序；2、輸入指定的圖；3、把顯示遍歷序列改為顯示先深、先廣遍歷生成樹，要求輸出結(jié)果是：ABCDEFGH先廣遍歷生成樹ABCDEFGH先深遍歷生成樹2實驗報告的書寫：二、實驗原理：填寫程序改動的方法、依據(jù)五、實驗過程原始記錄：打印與自己改寫的源代碼相關(guān)的程序段，附加注解。六、實驗結(jié)果及分析：打印屏幕輸入、輸出結(jié)果。注意：除了從頂點1出發(fā)之外，再選擇另一個結(jié)點，即打印兩組測試數(shù)據(jù)（均使用上面指定輸入的圖）附錄：圖的深度優(yōu)先、廣度優(yōu)先遍歷/*用鄰接矩陣表示的圖的深度優(yōu)先搜索和廣度優(yōu)先搜索*/#include #define maxvertexnum 100/* 設(shè)置鄰接矩陣的最大階數(shù) */* 設(shè)置圖的頂點信息為字符型 */typedef char vertextype;/* 設(shè)置邊上權(quán)值和循環(huán)隊列數(shù)據(jù)元素為整型 */typedef int edgetype,DataType,Status;/*用已定義的循環(huán)隊列頭文件SQueue.h */#include SQueue.htypedef struct vertextype vexsmaxvertexnum;/* 圖的頂點信息表 */ edgetype edgesmaxvertexnummaxvertexnum;/* 圖的鄰接矩陣 */ int n,e;/* 圖的頂點數(shù)和邊數(shù) */ mgraph;/* 圖的鄰接矩陣表示結(jié)構(gòu)定義 */typedef enumFALSE,TRUEboolean;boolean visitedmaxvertexnum;/* 頂點訪問標(biāo)記向量 */main()/* 主函數(shù) */ /* 建立用鄰接矩陣表示的圖，并進行深度優(yōu)先搜索和廣度優(yōu)先搜索 */ mgraph *g;char anychar; g=(mgraph*)malloc(sizeof(mgraph);/* 申請圖g的鄰接矩陣表示空間 */ createmgraph(g);/* 建立圖g */ printf(the dfs is:);/* 對圖g進行深度優(yōu)先搜索 */ dfstraverse(g); printf(the bfs is:);/* 對圖g進行廣度優(yōu)先搜索 */ bfstraverse(g); printf(Press any key to continue.); scanf( %c,&anychar); createmgraph(mgraph *g) /* 建立圖g的鄰接矩陣表示 */ int i,j,k,w; int flag; printf(nPlease select which graphic that you want to creat:n); printf(digragh-0n); printf(undigragh-1n); scanf(%d,&flag); printf(Please input Number of Vertex,Edge:n); scanf(%d,%d,&g-n,&g-e);/* 輸入圖*g的頂點數(shù)和邊數(shù) */ printf(input the infomation of Vertexs:n); for(i=0;in;i+) /* 輸入n個頂點的信息 */ /* %c前添加空格，在接收單字符時可清除緩沖區(qū)中的空格和回車 */ scanf( %c,&(g-vexsi); for(i=0;in;i+)/* 將鄰接矩陣數(shù)組初始化 */ for(j=0;jn;j+) g-edgesij=0; for(k=0;ke;k+) /* 讀入n有向邊對應(yīng)的三元組(i,j,w),若構(gòu)造有向圖， */ /* i為有向邊的弧尾，j是有向邊的弧頭， */ /* w是有向邊的權(quán)值（建立一般的有向圖時，可輸入1） */ printf(input i,j,w:n); scanf(%d,%d,%d,&i,&j,&w); g-edgesij=w; if (flag)/* 構(gòu)造無向圖，即為對稱矩陣 */ g-edgesji=w; dfsm(mgraph *g,int i) /* 對以鄰接矩陣表示的圖，以序號為i的頂點為出發(fā)點進行深度優(yōu)先搜索 */ int j; printf(visit vertex:%c ,g-vexsi);/* 訪問序號為i的頂點 */ visitedi=TRUE;/* 將序號為i的頂點設(shè)置訪問過標(biāo)記 */ for(j=0;jn;j+)/* 掃描鄰接矩陣的第i行，做以下操作 */ if (g-edgesij!=0)&(!visitedj) /* 尋找序號為i的頂點的未訪問過的鄰接點(設(shè)序號為k), */ dfsm(g,j);/* 以序號為k的頂點為出發(fā)點進行深度優(yōu)先搜索 */ /* end of dfsm */dfstraverse(mgraph *g) /* 對以鄰接矩陣表示的圖，進行深度優(yōu)先搜索 */ int i; for(i=0;in;i+)/* 將圖的所有頂點設(shè)置為未訪問過 */ visitedi=FALSE; for(i=0;in;i+)/* 對圖*g進行深度優(yōu)先搜索 */ if(!visitedi) dfsm(g,i); printf(n); /* end of dfstraverse */bfsm(mgraph *g,int k) /* 對以鄰接矩陣表示的圖，以序號為k的頂點作為出發(fā)點進行廣度優(yōu)先搜索 */ int i,j; SQueue myQueue; SQInit(&myQueue);/* 創(chuàng)建循環(huán)隊列myQueue */ printf(visit vertex:%c ,g-vexsk);/* 訪問序號為k的頂點 */ visitedk=TRUE;/* 將序號為k是結(jié)點設(shè)置為已訪問過 */ SQAppend(&myQueue, k);/* 將序號為k的頂點入隊 */ while(!SQIsEmpty(myQueue)/* 若隊列不為空，則做以下操作 */ SQDelete(&myQueue, &i); /* 將隊首元素(序號為i的頂點)出隊 */ for(j=0;jn;j+)/* 尋找序號為i頂點的鄰接點，并做如下處理 */ if(g-edgesij!=0)&(!visitedj)/* 若序號為i的頂點有未訪問過鄰接點 */ printf(visit vertex:%c ,g-vexsj);/* 訪問序號為j的頂點 */ visitedj=TRUE;/* 設(shè)置序號為j的頂點訪問過標(biāo)記 */ SQAppend(&myQueue, j); /* 將序號為j的頂點入隊 */ /* end of if */ /* end of for */ /* end of bfsm */bfstraverse(mgraph *g) /* 對以鄰接矩陣表示的圖，進行廣度優(yōu)先搜索 */ int i; for(i=0;in;i+)/* 將所有頂點設(shè)置為未訪問過 */ visitedi=FALSE; for(i=0;in;i+)/* 對鄰接矩陣表示的圖進行廣度優(yōu)先搜索 */ if(!visitedi) bfsm(g,i); pr