數(shù)據(jù)結構實驗指導書樣本

《數(shù)據(jù)構造》實驗指引書計算機專業(yè)實驗中心編TIME\@"yyyy'年'M'月'd'日'"10月23日

目錄《數(shù)據(jù)構造》上機實驗內容和規(guī)定 3實驗一、順序表實現(xiàn)及應用 5實驗二、鏈表實現(xiàn)及應用 8實驗三、棧實現(xiàn)及應用 13實驗四、隊列實現(xiàn)及應用 14實驗五、二叉樹操作及應用 15實驗六、圖遍歷操作及應用 20實驗七、查找算法實現(xiàn) 27實驗八、排序算法實現(xiàn) 29

《數(shù)據(jù)構造》上機實驗內容和規(guī)定通過上機實驗加深對課程內容理解，增長感性結識，提高程序設計、開發(fā)及調試能力。序號實驗名稱內容提要每組人數(shù)實驗時數(shù)實驗規(guī)定實驗類別分值（總100分）1順序表實現(xiàn)及應用掌握順序表構造，實現(xiàn)其插入、刪除等算法。運用順序表將兩個有序線性表合并為一種有序表。12必做設計10分2鏈表實現(xiàn)及應用掌握單鏈表構造，實現(xiàn)其插入、刪除、查找等算法。運用單鏈表將兩個有序鏈表合并為一種有序鏈表。12必做設計10分3棧實現(xiàn)及應用掌握棧構造，將棧應用于表達式計算問題12必做設計15分4隊列實現(xiàn)及應用掌握隊列構造，將隊列應用于模仿服務臺前排隊現(xiàn)象問題12必做設計15分5二叉樹操作及應用掌握二叉樹存儲，實現(xiàn)三種遍歷遞歸算法、實現(xiàn)前序或中序非遞歸遍歷算法12必做設計15分6圖遍歷操作及應用實現(xiàn)圖存儲、深度遍歷和廣度遍歷算法12必做設計10分7查找算法實現(xiàn)實現(xiàn)順序表二分查找算法12必做設計10分8排序算法實現(xiàn)實現(xiàn)直接插入排序、迅速排序等算法12必做設計15分本實驗指引書合用于16學時《數(shù)據(jù)構造》實驗課，實驗項目詳細內容如下：實驗報告規(guī)定請按照實驗教師規(guī)定，準時提交實驗報告電子版文獻。實驗報告格式可個性化定義，內容涉及但不限于如下內容：題目、姓名、學號、班級（首頁）需求分析：陳述程序設計任務，強調程序要做什么，明確規(guī)定：輸入形式和輸出值范疇；輸出形式；程序所能達到功能；測試數(shù)據(jù)：涉及對的輸入輸出成果和錯誤輸入及輸出成果。概要設計：闡明用到數(shù)據(jù)構造定義、主程序流程及各程序模塊之間調用關系。詳細設計：提交帶注釋源程序或者用偽代碼寫出每個操作所涉及算法。調試分析：調試過程中所遇到問題及解決辦法；算法時空分析；經驗與體會。顧客使用闡明：闡明如何使用你設計程序，詳細列出每一步操作環(huán)節(jié)。（如果程序操作簡樸，可略去）測試成果：列出對于給定輸入所產生輸出成果。（若有也許，測試隨輸入規(guī)模增長所用算法實際運營時間變化）8、總結

實驗一、順序表實現(xiàn)及應用一、實驗目理解和掌握線性表順序存儲構造；掌握用C語言上機調試線性表基本辦法；掌握線性表基本操作：插入、刪除、查找以及線性表合并等運算在順序存儲構造和鏈接存儲構造上運算，以及對相應算法性能分析。二、實驗規(guī)定給定一段程序代碼，程序代碼所完畢功能為：（1）建立一種線性表；（2）依次輸入數(shù)據(jù)元素1,2,3,4,5,6,7,8,9,10；（3）刪除數(shù)據(jù)元素5；（4）依次顯示當前線性表中數(shù)據(jù)元素。假設該線性表數(shù)據(jù)元素個數(shù)在最壞狀況下不會超過100個，規(guī)定使用順序表。程序中有3處錯誤地方，有標記，屬于邏輯錯誤，對照書中代碼仔細分析后，規(guī)定同窗們修改錯誤代碼，修改后上機調試得到對的運營成果。三、程序代碼#include<stdio.h>#defineMaxSize100typedefintDataType;typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;voidListInitiate(SeqList*L)/*初始化順序表L*/{L->size=0;/*定義初始數(shù)據(jù)元素個數(shù)*/}intListLength(SeqListL)/*返回順序表L當前數(shù)據(jù)元素個數(shù)*/{returnL.size;}intListInsert(SeqList*L，inti，DataTypex)/*在順序表L位置i（0≤i≤size）前插入數(shù)據(jù)元素值x*//*插入成功返回1，插入失敗返回0*/{intj;if(L->size>=MaxSize){printf("順序表已滿無法插入！\n");return0;}elseif(i<0||i>L->size){printf("參數(shù)i不合法！\n");return0;}else{//此段程序有一處錯誤for(j=L->size；j>i；j--)L->list[j]=L->list[j];/*為插入做準備*/L->list[i]=x;/*插入*/L->size++;/*元素個數(shù)加1*/return1;}}intListDelete(SeqList*L，inti，DataType*x)/*刪除順序表L中位置i（0≤i≤size-1）數(shù)據(jù)元素值并存儲到參數(shù)x中*//*刪除成功返回1，刪除失敗返回0*/{intj;if(L->size<=0){printf("順序表已空無數(shù)據(jù)元素可刪！\n");return0;}elseif(i<0||i>L->size-1){printf("參數(shù)i不合法");return0;}else{//此段程序有一處錯誤*x=L->list[i];/*保存刪除元素到參數(shù)x中*/for(j=i+1；j<=L->size-1；j++)L->list[j]=L->list[j-1];/*依次前移*/L->size--;/*數(shù)據(jù)元素個數(shù)減1*/return1;}}intListGet(SeqListL，inti，DataType*x)/*取順序表L中第i個數(shù)據(jù)元素值存于x中，成功則返回1，失敗返回0*/{if(i<0||i>L.size-1){printf("參數(shù)i不合法！\n");return0;}else{*x=L.list[i];return1;}}voidmain(void){SeqListmyList;inti，x;ListInitiate(&myList);for(i=0；i<10；i++)ListInsert(&myList，i，i+1)；ListDelete(&myList，4，&x);for(i=0；i<ListLength(myList)；i++){ListGet(,i,&x)；//此段程序有一處錯誤printf("%"，x);}}四、實驗任務1.改正上述程序中錯誤（必作）。2.編寫合并函數(shù)，將兩個有序線性表合并為一種有序表并在主函數(shù)中加以測試（選作）。3.完畢實驗報告撰寫。

實驗二、鏈表實現(xiàn)及應用一、實驗目理解和掌握線性表鏈式存儲構造；掌握用C語言上機調試線性表基本辦法；掌握線性表基本操作：插入、刪除、查找以及線性表合并等運算在順序存儲構造和鏈接存儲構造上運算，以及對相應算法性能分析。二、實驗規(guī)定給定一段程序代碼，程序代碼所完畢功能為：（1）建立一種線性表；（2）依次輸入數(shù)據(jù)元素1,2,3,4,5,6,7,8,9,10；（3）刪除數(shù)據(jù)元素5；（4）依次顯示當前線性表中數(shù)據(jù)元素。假設該線性表數(shù)據(jù)元素個數(shù)在最壞狀況下不會超過100個，規(guī)定使用單鏈表。程序中有3處錯誤地方，有標記，屬于邏輯錯誤，對照書中代碼仔細分析后，規(guī)定同窗們修改錯誤代碼，上機調試并得到對的運營成果。三、程序代碼：#include<stdio.h>/*該文獻包括pringtf()等函數(shù)*/#include<stdlib.h>/*該文獻包括exit()等函數(shù)*/#include<malloc.h>/*該文獻包括malloc()等函數(shù)*/typedefintDataType;/*定義DataType為int*/typedefstructNode{DataTypedata;structNode*next;}SLNode;voidListInitiate(SLNode**head)/*初始化*/{/*如果有內存空間，申請頭結點空間并使頭指針head指向頭結點*/if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1);(*head)->next=NULL;/*置鏈尾標記NULL*/}intListLength(SLNode*head)/*單鏈表長度*/{SLNode*p=head;/*p指向首元結點*/intsize=0;/*size初始為0*/while(p->next!=NULL)/*循環(huán)計數(shù)*/{p=p->next;size++;}returnsize;}intListInsert(SLNode*head，inti，DataTypex)/*在帶頭結點單鏈表head數(shù)據(jù)元素ai（0≤i≤size）結點前*//*插入一種存儲數(shù)據(jù)元素x結點*/{SLNode*p，*q;intj;p=head；/*p指向首元結點*/j=-1;/*j初始為-1*/while(p->next!=NULL&&j<i-1)/*最后讓指針p指向數(shù)據(jù)元素ai-1結點*/{p=p->next;j++;}if(j!=i-1){printf("插入位置參數(shù)錯！");return0;}/*生成新結點由指針q批示*/if((q=(SLNode*)malloc(sizeof(SLNode)))==NULL)exit(1);q->data=x;//此段程序有一處錯誤p->next=q->next;/*給指針q->next賦值*/p->next=q;/*給指針p->next重新賦值*/return1;}intListDelete(SLNode*head，inti，DataType*x)/*刪除帶頭結點單鏈表head數(shù)據(jù)元素ai（0≤i≤size-1）結點*//*刪除結點數(shù)據(jù)元素域值由x帶回。刪除成功時返回1；失敗返回0*/{SLNode*p，*s;intj;p=head；/*p指向首元結點*/j=-1;/*j初始為-1*/while(p->next!=NULL&&p->next->next!=NULL&&j<i-1)/*最后讓指針p指向數(shù)據(jù)元素ai-1結點*/{p=p->next;j++;}if(j!=i-1){printf("插入位置參數(shù)錯！");return0;}//此段程序有一處錯誤s=p->next；/*指針s指向數(shù)據(jù)元素ai結點*/*x=s->data;/*把指針s所指結點數(shù)據(jù)元素域值賦予x*/p->next=s->next;/*把數(shù)據(jù)元素ai結點從單鏈表中刪除指*/free(s);/*釋放指針s所指結點內存空間*/return1;}intListGet(SLNode*head，inti，DataType*x)/*取數(shù)據(jù)元素ai和刪除函數(shù)類同，只是不刪除數(shù)據(jù)元素ai結點*/{SLNode*p;intj;p=head;j=-1;while(p->next!=NULL&&j<i){p=p->next;j++;}if(j!=i){printf("取元素位置參數(shù)錯！");return0;}//此段程序有一處錯誤*x=p->next;return1;}voidDestroy(SLNode**head){SLNode*p，*p1;p=*head;while(p!=NULL){p1=p;p=p->next;free(p1);}*head=NULL;}voidmain(void){SLNode*head;inti，x;ListInitiate(&head);/*初始化*/for(i=0；i<10；i++){if(ListInsert(head，i，i+1)==0)/*插入10個數(shù)據(jù)元素*/{printf("錯誤！\n");return;}}if(ListDelete(head，4，&x)==0)/*刪除數(shù)據(jù)元素5*/{printf("錯誤！\n");return;}for(i=0；i<ListLength(head)；i++){if(ListGet(head，i，&x)==0)/*取元素*/{printf("錯誤！\n");return;}elseprintf("%d"，x);/*顯示數(shù)據(jù)元素*/}Destroy(&head);}三、實驗任務1.改正上述程序中錯誤（必作）。2.編寫合并函數(shù)，將兩個有序單鏈表合并成一種有序單鏈表（選作）。3.完畢實驗報告撰寫。

實驗三、棧實現(xiàn)及應用一、實驗目1.掌握棧存儲表達和實現(xiàn)2.掌握?；静僮鲗崿F(xiàn)。3.掌握棧在解決實際問題中應用。二、實驗規(guī)定問題描述：編寫程序實現(xiàn)算術表達式求值，即驗證某算術表達式對的性，若對的，則計算該算術表達式值。重要功能描述如下：1、從鍵盤上輸入表達式。2、分析該表達式與否合法。3、若上述解決過程中沒有發(fā)現(xiàn)錯誤，則以為該表達式合法，計算并打印解決成果。三、重要功能函數(shù)參照程序中重要包括下面幾種功能函數(shù)：voidinitstack()：初始化堆棧intMake_str()：語法檢查intpush_operate(intoperate)：將操作碼壓入堆棧intpush_num(doublenum)：將操作數(shù)壓入堆棧intprocede(intoperate)：解決操作碼intchange_opnd(intoperate)：將字符型操作碼轉換成優(yōu)先級intpush_opnd(intoperate)：將操作碼壓入堆棧intpop_opnd()：將操作碼彈出堆棧intcaculate(intcur_opnd)：簡樸計算+，-，*，/doublepop_num()：彈出操作數(shù)四、實驗任務認真閱讀與理解實驗內容詳細規(guī)定，參照教材有關章節(jié)，結合實驗內容規(guī)定，編寫實驗程序并上機調試與測試，完畢實驗報告撰寫。

實驗四、隊列實現(xiàn)及應用一、實驗目1.掌握隊列存儲表達和實現(xiàn)。2.掌握隊列基本操作實現(xiàn)。3.掌握隊列在解決實際問題中應用。二、實驗規(guī)定運用隊列模仿服務臺前排隊現(xiàn)象問題。問題描述：某銀行有一種客戶辦理業(yè)務站，在單位時間內隨機地有客戶到達，設每位客戶業(yè)務辦理時間是某個范疇隨機值。設只有一種窗口，一位業(yè)務人員，規(guī)定程序模仿記錄在設定期間內，業(yè)務人員總空閑時間和客戶平均等待時間。假定模仿數(shù)據(jù)已按客戶到達先后順序依次存于某個文本數(shù)據(jù)文獻中，相應每位客戶有兩個數(shù)據(jù)：到達時間和需要辦理業(yè)務時間。三、實驗任務認真閱讀與理解實驗內容詳細規(guī)定，參照教材有關章節(jié)，結合實驗內容規(guī)定，編寫實驗程序并上機調試與測試，完畢實驗報告撰寫。

實驗五、二叉樹操作及應用實驗目掌握二叉樹定義、構造特性，以及各種存儲構造特點及使用范疇，各種遍歷算法。掌握用指針類型描述、訪問和解決二叉樹運算。掌握前序或中序非遞歸遍歷算法。實驗規(guī)定有如下二叉樹：∧∧AB∧C∧D∧E∧∧F∧∧G∧根程序代碼給出了該二叉樹鏈式存儲構造建立、前序、中序、后序遍歷算法，同步也給出了查詢“E”與否在二叉樹里代碼。代碼有三處錯誤，有標記，屬于邏輯錯誤，對照書中代碼仔細分析后，請修改了在電腦里運營。#include<stdlib.h>#include<stdio.h>typedefcharDataType;typedefstructNode{DataTypedata;/*數(shù)據(jù)域*/structNode*leftChild;/*左子樹指針*/structNode*rightChild;/*右子樹指針*/}BiTreeNode;/*結點構造體定義*//*初始化創(chuàng)立二叉樹頭結點*/voidInitiate(BiTreeNode**root){*root=(BiTreeNode*)malloc(sizeof(BiTreeNode));(*root)->leftChild=NULL;(*root)->rightChild=NULL;}voidDestroy(BiTreeNode**root){if((*root)!=NULL&&(*root)->leftChild!=NULL)Destroy(&(*root)->leftChild);if((*root)!=NULL&&(*root)->rightChild!=NULL)Destroy(&(*root)->rightChild);free(*root);}/*若當前結點curr非空，在curr左子樹插入元素值為x新結點*//*原curr所指結點左子樹成為新插入結點左子樹*//*若插入成功返回新插入結點指針，否則返回空指針*/BiTreeNode*InsertLeftNode(BiTreeNode*curr，DataTypex){BiTreeNode*s，*t;if(curr==NULL)returnNULL;t=curr->leftChild;/*保存原curr所指結點左子樹指針*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->leftChild=t;/*新插入結點左子樹為原curr左子樹*/s->rightChild=NULL;curr->leftChild=s;/*新結點成為curr左子樹*/returncurr->leftChild;/*返回新插入結點指針*/}/*若當前結點curr非空，在curr右子樹插入元素值為x新結點*//*原curr所指結點右子樹成為新插入結點右子樹*//*若插入成功返回新插入結點指針，否則返回空指針*/BiTreeNode*InsertRightNode(BiTreeNode*curr，DataTypex){BiTreeNode*s，*t;if(curr==NULL)returnNULL;t=curr->rightChild;/*保存原curr所指結點右子樹指針*/s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x;s->rightChild=t;/*新插入結點右子樹為原curr右子樹*/s->leftChild=NULL;curr->rightChild=s;/*新結點成為curr右子樹*/returncurr->rightChild;/*返回新插入結點指針*/}voidPreOrder(BiTreeNode*t，voidvisit(DataTypeitem))//使用visit(item)函數(shù)前序遍歷二叉樹t{if(t!=NULL){//此小段有一處錯誤visit(t->data);PreOrder(t->rightChild，visit);PreOrder(t->leftChild，visit);}}voidInOrder(BiTreeNode*t，voidvisit(DataTypeitem))//使用visit(item)函數(shù)中序遍歷二叉樹t{if(t!=NULL){//此小段有一處錯誤InOrder(t->leftChild，visit);InOrder(t->rightChild，visit);visit(t->data);}}voidPostOrder(BiTreeNode*t，voidvisit(DataTypeitem))//使用visit(item)函數(shù)后序遍歷二叉樹t{if(t!=NULL){//此小段有一處錯誤visit(t->data);PostOrder(t->leftChild，visit);PostOrder(t->rightChild，visit);}}voidVisit(DataTypeitem){printf("%c"，item);}BiTreeNode*Search(BiTreeNode*root，DataTypex)//需找元素x與否在二叉樹中{BiTreeNode*find=NULL;if(root!=NULL){if(root->data==x)find=root;else{find=Search(root->leftChild,x);if(find==NULL)find=Search(root->rightChild,x);}}returnfind;}voidmain(void){BiTreeNode*root，*p，*pp,*find;charx='E';Initiate(&root);p=InsertLeftNode(root，'A');p=InsertLeftNode(p，'B');p=InsertLeftNode(p，'D');p=InsertRightNode(p，'G');p=InsertRightNode(root->leftChild，'C');pp=p;InsertLeftNode(p，'E');InsertRightNode(pp，'F');printf("前序遍歷：");PreOrder(root->leftChild，Visit);printf("\n中序遍歷：");InOrder(root->leftChild，Visit);printf("\n后序遍歷：");PostOrder(root->leftChild，Visit);find=Search(root,x);if(find!=NULL)printf("\n數(shù)據(jù)元素%c在二叉樹中\(zhòng)n",x);elseprintf("\n數(shù)據(jù)元素%c不在二叉樹中\(zhòng)n",x);Destroy(&root);}實驗任務：1.改正程序錯誤（必作）。2.編寫二叉樹前序（或中序）非遞歸遍歷算法并進行測試（選作）。3.完畢實驗報告撰寫。

實驗六、圖遍歷操作及應用一、實驗目掌握有向圖和無向圖概念；掌握鄰接矩陣和鄰接鏈表建立圖存儲構造；掌握DFS及BFS對圖遍歷操作；理解圖構造在人工智能、工程等領域廣泛應用。實驗規(guī)定采用鄰接矩陣和鄰接鏈表作為圖存儲構造，完畢有向圖和無向圖DFS和BFS操作。本實驗給出了示例程序，其中共有4處錯誤，錯誤段均有標記，屬于邏輯錯誤。請認真理解程序，修改程序代碼，并在電腦上調試運營。DFS和BFS基本思想深度優(yōu)先搜索法DFS基本思想：從圖G中某個頂點Vo出發(fā)，一方面訪問Vo，然后選取一種與Vo相鄰且沒被訪問過頂點Vi訪問，再從Vi出發(fā)選取一種與Vi相鄰且沒被訪問過頂點Vj訪問，……依次繼續(xù)。如果當前被訪問過頂點所有鄰接頂點都已被訪問，則回退到已被訪問頂點序列中最后一種擁有未被訪問相鄰頂點頂點W，從W出發(fā)按同樣辦法向前遍歷。直到圖中所有頂點都被訪問。廣度優(yōu)先算法BFS基本思想：從圖G中某個頂點Vo出發(fā)，一方面訪問Vo，然后訪問與Vo相鄰所有未被訪問過頂點V1，V2，……，Vt；再依次訪問與V1，V2，……，Vt相鄰起且未被訪問過所有頂點。如此繼續(xù)，直到訪問完圖中所有頂點。V6V4V6V4V5V7V2V3V1V0Vo圖G示例鄰接矩陣作為存儲構造程序示例#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定義最大頂點數(shù)typedefstruct{charvexs[MaxVertexNum]；//頂點表intedges[MaxVertexNum][MaxVertexNum]；

//鄰接矩陣，可看作邊表intn,e；//圖中頂點數(shù)n和邊數(shù)e}MGraph；//用鄰接矩陣表達圖類型//=========建立鄰接矩陣=======voidCreatMGraph(MGraph*G){inti,j,k;chara;printf("InputVertexNum(n)andEdgesNum(e)：");scanf("%d,%d",&G->n,&G->e)；//輸入頂點數(shù)和邊數(shù)scanf("%c",&a)；printf("InputVertexstring:");for(i=0;i<G->n;i++){scanf("%c",&a);G->vexs[i]=a；//讀入頂點信息，建立頂點表}for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)G->edges[i][j]=0；//初始化鄰接矩陣printf("Inputedges,CreatAdjacencyMatrix\n");for(k=0;k<G->e;k++){//讀入e條邊，建立鄰接矩陣scanf("%d%d",&i,&j)；//輸入邊（Vi，Vj）頂點序號G->edges[i][j]=1；G->edges[j][i]=1；//若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句}}//=========定義標志向量，為全局變量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷遞歸算法======voidDFSM(MGraph*G,inti){//以Vi為出發(fā)點對鄰接矩陣表達圖G進行DFS搜索，鄰接矩陣是0，1矩陣intj;printf("%c",G->vexs[i])；//訪問頂點Vivisited[i]=TRUE；//置已訪問標志for(j=0;j<G->n;j++)//依次搜索Vi鄰接點if(G->edges[i][j]==1&&！visited[j])DFSM(G,j)；//（Vi，Vj）∈E，且Vj未訪問過，故Vj為新出發(fā)點}voidDFS(MGraph*G){\\此段代碼有一處錯誤inti;for(i=0;i<G->n;i++)visited[i]=FALSE；//標志向量初始化for(i=0;i<G->n;i++)if(!visited[i])//Vi未訪問過DFS(G,i)；//以Vi為源點開始DFS搜索}//===========BFS：廣度優(yōu)先遍歷=======voidBFS(MGraph*G,intk){//以Vk為源點對用鄰接矩陣表達圖G進行廣度優(yōu)先搜索inti,j,f=0,r=0;intcq[MaxVertexNum]；//定義隊列for(i=0;i<G->n;i++)visited[i]=FALSE；//標志向量初始化for(i=0;i<G->n;i++)cq[i]=-1；//隊列初始化printf("%c",G->vexs[k])；//訪問源點Vkvisited[k]=TRUE;cq[r]=k；//Vk已訪問，將其入隊。注意，事實上是將其序號入隊while(cq[f]!=-1){//隊非空則執(zhí)行i=cq[f]；f=f+1；//Vf出隊for(j=0;j<G->n;j++)//依次Vi鄰接點Vjif(G->edges[i][j]==1&&!visited[j]){//Vj未訪問\\如下三行代碼有一處錯誤printf("%c",G->vexs[j])；//訪問Vjvisited[j]=FALSE;

r=r+1；cq[r]=j；//訪問過Vj入隊}}}//==========main=====voidmain(){inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph))；//為圖G申請內存空間CreatMGraph(G)；//建立鄰接矩陣printf("PrintGraphDFS：");DFS(G)；//深度優(yōu)先遍歷printf("\n");printf("PrintGraphBFS：");BFS(G,3)；//以序號為3頂點開始廣度優(yōu)先遍歷printf("\n");}執(zhí)行順序：InputVertexNum(n)andEdgesNum(e)：8，9InputVertexstring：01234567Inputedges,CreatAdjacencyMatrix010213142526374756PrintGraphDFS：01374256PrintGraphBFS：31704256鄰接鏈表作為存儲構造程序示例#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50//定義最大頂點數(shù)typedefstructnode{//邊表結點intadjvex；//鄰接點域structnode*next；//鏈域}EdgeNode;typedefstructvnode{//頂點表結點charvertex；//頂點域EdgeNode*firstedge；//邊表頭指針}VertexNode;typedefVertexNodeAdjList[MaxVertexNum]；//AdjList是鄰接表類型typedefstruct{AdjListadjlist；//鄰接表intn,e；//圖中當前頂點數(shù)和邊數(shù)}ALGraph；//圖類型//=========建立圖鄰接表=======voidCreatALGraph(ALGraph*G){inti,j,k;chara;EdgeNode*s；//定義邊表結點printf("InputVertexNum(n)andEdgesNum(e)：");scanf("%d,%d",&G->n,&G->e)；//讀入頂點數(shù)和邊數(shù)scanf("%c",&a);printf("InputVertexstring:");for(i=0;i<G->n;i++)//建立邊表{scanf("%c",&a);G->adjlist[i].vertex=a；//讀入頂點信息G->adjlist[i].firstedge=NULL；//邊表置為空表}printf("Inputedges,CreatAdjacencyList\n");for(k=0;k<G->e;k++){//建立邊表scanf("%d%d",&i,&j)；//讀入邊（Vi，Vj）頂點對序號s=(EdgeNode*)malloc(sizeof(EdgeNode))；//生成邊表結點s->adjvex=j；//鄰接點序號為js->next=G->adjlist[i].firstedge;G->adjlist[i].firstedge=s；//將新結點*S插入頂點Vi邊表頭部s=(EdgeNode*)malloc(sizeof(EdgeNode))；s->adjvex=i；//鄰接點序號為is->next=G->adjlist[j].firstedge；G->adjlist[j].firstedge=s；//將新結點*S插入頂點Vj邊表頭部}}//=========定義標志向量，為全局變量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度優(yōu)先遍歷遞歸算法======voidDFSM(ALGraph*G,inti){//以Vi為出發(fā)點對鄰接鏈表表達圖G進行DFS搜索EdgeNode*p;printf("%c",G->adjlist[i].vertex)；//訪問頂點Vivisited[i]=TRUE；//標記Vi已訪問p=G->adjlist[i].firstedge；//取Vi邊表頭指針while(p){//依次搜索Vi鄰接點Vj，這里j=p->adjvex\\如下3行代碼有一處錯誤if(！visited[p->adjvex])//若Vj尚未被訪問DFS(G,p->adjvex)；//則以Vj為出發(fā)點向縱深搜索p=p->next；//找Vi下一種鄰接點}}voidDFS(ALGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE；//標志向量初始化for(i=0;i<G->n;i++)if(!visited[i])//Vi未訪問過

DFSM(G,i)；//以Vi為源點開始DFS搜索

}

//==========BFS：廣度優(yōu)先遍歷=========voidBFS(ALGraph*G,intk)

{//以Vk為源點對用鄰接鏈表表達圖G進行廣度優(yōu)先搜索inti,f=0,r=0;

EdgeNode*p;

intcq[MaxVertexNum]；//定義FIFO隊列

for(i=0;i<G->n;i++)visited[i]=FALSE；//標志向量初始化for(i=0;i<=G->n;i++)cq[i]=-1；//初始化標志向量printf("%c",G->adjlist[k].vertex)；//訪問源點Vkvisited[k]=TRUE;cq[r]=k；//Vk已訪問，將其入隊。注意，事實上是將其序號入隊while(cq[f]!=-1){隊列非空則執(zhí)行i=cq[f]；f=f+1；//Vi出隊p=G->adjlist[i].firstedge；//取Vi邊表頭指針while(p){//依次搜索Vi鄰接點Vj（令p->adjvex=j）if(!visited[p->adjvex]){//若Vj未訪問過printf("%c",G->adjlist[p->adjvex].vertex)；//訪問Vjvisited[p->adjvex]=TRUE;//