遼寧科技大學(xué) 《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書》(自動化tongxin)

1、數(shù)據(jù)結(jié)構(gòu)實(shí) 驗(yàn) 指 導(dǎo) 書 適用專業(yè)：自動化、電子、通信等目 次前 言3實(shí)驗(yàn)一 線性表的操作5實(shí)驗(yàn)二 棧和隊(duì)列的操作13實(shí)驗(yàn)三 圖算法18實(shí)驗(yàn)四 排序選擇20前 言數(shù)據(jù)結(jié)構(gòu)是計算機(jī)及相關(guān)專業(yè)的一門核心基礎(chǔ)課程，也是很多高校考研專業(yè)課之一。它主要介紹線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)三種邏輯結(jié)構(gòu)元素的存儲實(shí)現(xiàn)，在此基礎(chǔ)上介紹一些典型算法及時、空效率分析。這門課程的主要任務(wù)是培養(yǎng)學(xué)生的算法設(shè)計能力及良好的程序設(shè)計習(xí)慣。通過學(xué)習(xí)，要求學(xué)生能夠掌握典型算法的設(shè)計思想及程序?qū)崿F(xiàn)，能夠根據(jù)實(shí)際問題選取合適的存儲方案，設(shè)計出簡潔、高效、實(shí)用的算法，為后續(xù)課程的學(xué)習(xí)及軟件開發(fā)打下良好的基礎(chǔ)。學(xué)習(xí)這門課程，習(xí)題和實(shí)驗(yàn)是兩

2、個關(guān)鍵環(huán)節(jié)。學(xué)生理解算法，上機(jī)實(shí)驗(yàn)是最佳的途徑之一。因此，實(shí)驗(yàn)環(huán)節(jié)的好壞是學(xué)生能否學(xué)好數(shù)據(jù)結(jié)構(gòu)的關(guān)鍵。為了更好地配合學(xué)生實(shí)驗(yàn)，特編寫試驗(yàn)指導(dǎo)書。希望同學(xué)們在使用本實(shí)驗(yàn)指導(dǎo)書及進(jìn)行實(shí)驗(yàn)的過程中，能夠幫助我們不斷地發(fā)現(xiàn)問題，并提出建議，使數(shù)據(jù)結(jié)構(gòu)成為具有省內(nèi)一流水平的課程。一、實(shí)驗(yàn)?zāi)康?更好的理解算法的思想、培養(yǎng)編程能力。二、實(shí)驗(yàn)要求1、 每次實(shí)驗(yàn)前學(xué)生必須根據(jù)試驗(yàn)內(nèi)容認(rèn)真準(zhǔn)備實(shí)驗(yàn)程序及調(diào)試時所需的輸入數(shù)據(jù)。 2、在指導(dǎo)教師的幫助下能夠完成實(shí)驗(yàn)內(nèi)容，得出正確的實(shí)驗(yàn)結(jié)果。 3、實(shí)驗(yàn)結(jié)束后總結(jié)實(shí)驗(yàn)內(nèi)容、書寫實(shí)驗(yàn)報告。 4、遵守實(shí)驗(yàn)室規(guī)章制度、不缺席、按時上、下機(jī)。 5、實(shí)驗(yàn)學(xué)時內(nèi)必須做數(shù)據(jù)結(jié)構(gòu)的有關(guān)內(nèi)

3、容，不允許上網(wǎng)聊天或玩游戲，如發(fā)現(xiàn)上述現(xiàn)象，取消本次上機(jī)資格，平時成績扣10分。三、實(shí)驗(yàn)環(huán)境 VC+6.0四、說明 1、本實(shí)驗(yàn)的所有算法中元素類型可以根據(jù)實(shí)際需要選擇。 2、實(shí)驗(yàn)題目中帶者為較高要求，學(xué)生可自選；其余部分為基本內(nèi)容，應(yīng)盡量完成（至少完成70%，否則實(shí)驗(yàn)不合格）。 3、數(shù)據(jù)結(jié)構(gòu)是很多高校的碩士研究生入學(xué)考試的專業(yè)課之一，希望有志于考研的學(xué)生能夠在學(xué)習(xí)過程中注意各種算法的理解，以便為考研做一定的準(zhǔn)備。五、實(shí)驗(yàn)報告的書寫要求 1明確實(shí)驗(yàn)的目的及要求； 2記錄實(shí)驗(yàn)的輸入數(shù)據(jù)和輸出結(jié)果； 3說明實(shí)驗(yàn)中出現(xiàn)的問題和解決過程； 4寫出實(shí)驗(yàn)的體會和實(shí)驗(yàn)過程中沒能解決的問題；六、參考書目 數(shù)據(jù)結(jié)

4、構(gòu)-C語言描述-耿國華等 高等教育出版社DATA STRUCTURE WITH C+ William Ford,William Topp清華大學(xué)出版社（影印版）數(shù)據(jù)結(jié)構(gòu)（C語言描述） 嚴(yán)蔚敏 清華大學(xué)出版社實(shí)驗(yàn)一 線性表的操作實(shí)驗(yàn)類型：驗(yàn)證性 實(shí)驗(yàn)要求：必修實(shí)驗(yàn)學(xué)時： 2學(xué)時一、實(shí)驗(yàn)?zāi)康膮⒄战o定的順序表和鏈表的程序樣例，驗(yàn)證給出的線性表的常見算法線性表理解。二、實(shí)驗(yàn)要求1掌握順序表和鏈表的特點(diǎn)。掌握線性表的常見算法。2提交實(shí)驗(yàn)報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。三、實(shí)驗(yàn)內(nèi)容1.設(shè)計一個靜態(tài)數(shù)組存儲結(jié)構(gòu)的順序表，要求編程實(shí)現(xiàn)如

5、下任務(wù)：建立一個線性表，首先依次輸人數(shù)據(jù)元素1，2，3，10，然后刪除數(shù)據(jù)元素6，最后依次顯示當(dāng)前線性表中的數(shù)據(jù)元素。要求采用順序表實(shí)現(xiàn)，假設(shè)該順序表的數(shù)據(jù)元素個數(shù)在最壞情況下不會超過50個。2. 設(shè)計一個帶頭結(jié)點(diǎn)的單鏈表，要求：(1)生成一個整數(shù)線性表，實(shí)現(xiàn)將其分解成兩個鏈表，其中一個全部為奇數(shù)，另一個全部為偶數(shù)（盡量利用已知的存儲空間）。(2)設(shè)計一個測試主函數(shù)，實(shí)際運(yùn)行驗(yàn)證所設(shè)計單鏈表類的正確性。3.設(shè)計一個帶頭結(jié)點(diǎn)的循環(huán)鏈表，要求： (1)帶頭結(jié)點(diǎn)循環(huán)單鏈表的函數(shù)包括：取數(shù)據(jù)元素個數(shù)、插入、刪除、取數(shù)據(jù)元素. (2)設(shè)計一個測試主函數(shù)，實(shí)際運(yùn)行驗(yàn)證所設(shè)計循環(huán)單鏈表的正確性.*4.設(shè)計一

6、個單鏈表實(shí)現(xiàn)一元多項(xiàng)式求和問題。要求： （1）設(shè)計存儲結(jié)構(gòu)表示一元多項(xiàng)式； （2）設(shè)計算法實(shí)現(xiàn)一元多項(xiàng)式相加。 四、程序樣例1#include<iostream.h>const int MaxSize=50;typedef int datatype;typedef struct datatype dataMaxSize;int length;SeqList;void init(SeqList &L)L.length=0; void Insert(SeqList &L, int i, datatype x) int j; if (L.length>=MaxSiz

7、e) throw "溢出" if (i<1 | i>L.length+1) throw "位置不合法" for (j=L.length; j>=i; j-) L.dataj=L.dataj-1; /注意第j個元素存在數(shù)組下標(biāo)為j-1處 L.datai-1=x; L.length+;datatype Delete(SeqList &L,int i) int j;datatype x; if (L.length=0) cout<<"上溢" if (i<1 | i>L.length) cou

8、t<<"位置不合法" x=L.datai-1; for (j=i; j<L.length; j+) L.dataj-1=L.dataj; /注意第j個元素存在數(shù)組下標(biāo)為j-1處 L.length-; return x;void PrintList(SeqList &L)for(int i=0;i<L.length;i+)cout<<L.datai<<endl;void main()SeqList L;init(L);for(int i=1;i<=10;i+)Insert(L,i,i);PrintList(L);2

9、#include<iostream.h>#include<stdlib.h>typedef int datatype;typedef struct Node datatype data; struct Node *next; LNode,*Linklist;/*Linklist initlist()LNode * first;first=new LNode; first->next=NULL; return first;*/Linklist Creat_LinkList1() LNode *first;first=new LNode; first->next

10、=NULL; /*空表*/LNode *s; datatype x; /*設(shè)數(shù)據(jù)元素的類型為int*/int n,i=0;cout<<"輸入n值 "<<endl; cin>>n;while (i<n) cin>>x; s=new LNode; s->data=x; s->next=first->next; first->next=s;i+; return first;void Insert(LNode *first, int i,datatype x)LNode *p,*s;p=first;int

11、 j=0;while(p&&j<i-1)p=p->next;j+;if(!p) cout<<"位置不合法！ "s=new LNode; /*申請、填裝結(jié)點(diǎn)*/ s->data=x; s->next=p->next; /*新結(jié)點(diǎn)插入在第i-1個結(jié)點(diǎn)的后面*/ p->next=s;datatype Delete(LNode *first, datatype x)LNode *p,*q;p=first;q=p->next;while(q&&q->data!=x)p=q;q=q->ne

12、xt;if(!q) cout<<"不存在元素 ！ " x=q->data; p->next=q->next; /*新結(jié)點(diǎn)插入在第i-1個結(jié)點(diǎn)的后面*/ delete q; return x;void huafen(Linklist &first,Linklist &first1)LNode *p,*q,*r;p=first;q=first->next;r=first1;while(p->next!=NULL)if(q->data)%2!=0)p=q;q=q->next;elsep->next=q-&

13、gt;next;r->next=q;r=q;q=p->next;void print(Linklist &first)LNode *p;p=first->next;while(p)cout<<" "<<p->data; p=p->next;void main()Linklist A,B;B=new LNode; B->next=NULL;A=Creat_LinkList1();print(A);cout<<endl;cout<<"the huafen result"

14、;huafen(A,B);print(A);cout<<endl;print(B);cout<<endl;3#include<iostream.h>#include<stdlib.h>typedef int datatype;typedef struct Node datatype data; struct Node *next; LNode,*CList;void initCList(CList &first)first=new LNode; first->next=first; /建立只有頭結(jié)點(diǎn)的空鏈表 datatype Get

15、(CList first,int i) LNode *p;int j; p=first->next; j=1; /或p=first; j=0; while (p && j<i) p=p->next; /工作指針p后移 j+; if (!p) cout<< "位置不合法" else return p->data; void Insert(CList &first, int i, datatype x) LNode *p,*s;int j; p=first ; j=0; /工作指針p初始化while (p &&

16、amp; j<i-1)p=p->next; /工作指針p后移j+;if (!p) cout<< "位置不合法"else s=new LNode; s->data=x; /向內(nèi)存申請一個結(jié)點(diǎn)s，其數(shù)據(jù)域?yàn)閤s->next=p->next; /將結(jié)點(diǎn)s插入到結(jié)點(diǎn)p之后p->next=s; datatype Delete(CList &first,int i) LNode *p,*q;int j;datatype x;p=first ; j=0; /工作指針p初始化 while (p && j<i-1)

17、 /查找第i-1個結(jié)點(diǎn) p=p->next; j+; if (!p| !p->next) cout<< "位置不合法" /結(jié)點(diǎn)p不存在或結(jié)點(diǎn)p的后繼結(jié)點(diǎn)不存在 else q=p->next; x=q->data; /暫存被刪結(jié)點(diǎn) p->next=q->next; /摘鏈 delete q; return x; int count(CList first) LNode *p;int j; p=first; j=0; while (p->next!=first) p=p->next; /工作指針p后移 j+; retu

18、rn j; void CreateCList( CList &first,datatype a, int n) LNode *s; int i=n-1;first=new LNode; first->next=first; /初始化一個空鏈表 /for (int i=n-1; i>=0; i-) while(i>=0) s=new LNode; s->data=ai; /為每個數(shù)組元素建立一個結(jié)點(diǎn) s->next=first->next; /插入到頭結(jié)點(diǎn)之后 first->next=s;i-; void print(CList &fir

19、st)LNode *p;p=first->next;while(p->next!=first)cout<<p->data<<" " p=p->next; cout<<p->data<<" " void main() CList C; int a6=15,12,54,65,9,23;int x,i,j;CreateCList(C,a,6);print(C);cout<<endl;j=count(C);cout<<j<<endl;cout<

20、<"輸入x值插入的位置i"<<endl;cin>>x>>i;Insert(C,i,x); print(C);說明： 1算法的定義可以以頭文件的方式存儲,主函數(shù)實(shí)現(xiàn)該頭文件的包含即可調(diào)用 2. 靜態(tài)數(shù)組存儲結(jié)構(gòu)的順序表定義，要求表中元素的最大個數(shù) 可以使用#define MAXSIZE 50 3程序的編寫可以使用C+語言中類的形式如順序表Const int MAXSIZE=50;typedef int DataType；class SeqList protected： DataType listMAXSIZE； /靜態(tài)數(shù)組定義 int

21、 size；/當(dāng)前元素個數(shù) public： SeqList(int max=0)；/構(gòu)造函數(shù) -SeqList(void)；/析構(gòu)函數(shù) int Size(void)const；/取當(dāng)前數(shù)據(jù)元素個數(shù) void Insert（coast DataType& item, int i）；/插入 DataType Delete（const int i ）；/刪除 DataType GetData（int i）const；/取數(shù)據(jù)元素 ； 4. 單鏈表是由一個一個的結(jié)點(diǎn)組成的，因此，要定義和實(shí)現(xiàn)單鏈表，必須先定義結(jié)點(diǎn)。 實(shí)驗(yàn)二 棧和隊(duì)列的操作實(shí)驗(yàn)類型：驗(yàn)證性 實(shí)驗(yàn)要求：必修實(shí)驗(yàn)學(xué)時： 2學(xué)時一、實(shí)

22、驗(yàn)?zāi)康?1掌握棧的存儲特點(diǎn)及基本操作的實(shí)現(xiàn)。 2掌握隊(duì)列的基本算法及其應(yīng)用算法的程序?qū)崿F(xiàn)。 3. 了解串的存儲特點(diǎn)及基本操作的實(shí)現(xiàn)。二、實(shí)驗(yàn)要求1掌握棧、隊(duì)列及串的特點(diǎn)及實(shí)現(xiàn)。2提交實(shí)驗(yàn)報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。三、實(shí)驗(yàn)內(nèi)容 1. 堆棧測試和應(yīng)用問題。要求： 設(shè)計一個主函數(shù)實(shí)現(xiàn)對順序棧相關(guān)算法進(jìn)行測試。測試方法為：依次把數(shù)據(jù)元素1,2,3,4,5入棧，然后彈出棧中的數(shù)據(jù)元素并在屏幕上顯示。 設(shè)計一個鏈?zhǔn)疥?duì)列代碼.測試方法為：依次把數(shù)據(jù)元素1,2,3,4,5入對列，然后出隊(duì)列中的數(shù)據(jù)元素并在屏幕上顯示.*3.編寫判斷

23、一個字符序列是否是回文的函數(shù)，要求使用棧和隊(duì)列.4設(shè)計串采用順序存儲結(jié)構(gòu)，一個姓名用串來表示，編寫函數(shù)實(shí)現(xiàn)姓名的逆置。如white John變成John white.*5. 設(shè)計一個帶頭結(jié)點(diǎn)的循環(huán)單鏈表類，實(shí)現(xiàn)約瑟夫環(huán)問題；問題描述：設(shè)編號為1,2,，n(n>0)個人按順時針方向圍坐-圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限值m從第一個人開始順時針方向自1起順序報數(shù)。報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1起順序報數(shù).如此下去，直到所有人全部出列為止。要求設(shè)計一個程序模擬此過程，并給出出列人的編號序列。 測試數(shù)據(jù)： n=

24、7,7個人的密碼依次為3,1,7,2,4,8,4 初始報數(shù)上限值m=20 四、程序樣例1#include<iostream.h>#include<stdlib.h>typedef int datatype; const int MAXSIZE=50; typedef struct datatype dataMAXSIZE; int top; SeqStack; void Init_SeqStack(SeqStack &s)s.top= -1; int Empty_SeqStack(SeqStack &s) if (s.top= -1) return 1;

25、 else return 0;void Push_SeqStack (SeqStack &s, datatype x) if (s.top=MAXSIZE-1) cout<<"棧滿"<<endl; /*棧滿不能入棧*/ else s.top+; s.datas.top=x; void Pop_SeqStack(SeqStack &s, datatype &x) if (Empty_SeqStack ( s ) ) cout<<"?？?quot;<<endl; /*?？詹荒艹鰲?*/ else

26、x=s.datas.top; s.top-; /*棧頂元素存入*x，返回*/ datatype Top_SeqStack(SeqStack s) if ( Empty_SeqStack ( s ) ) cout<<"?？?quot;<<endl; /*?？?/ else return (s.datas.top ); void main() SeqStack s;int x,i;Init_SeqStack(s);for( i=1;i<=10;i+)Push_SeqStack(s,i);/cout<<Top_SeqStack(s)<<

27、endl;for( i=1;i<=10;i+)Pop_SeqStack(s,x);cout<<" "<<x<<endl; 2 #include<iostream.h>#include<stdlib.h>typedef int datatype;typedef struct node datatype data; struct node *next; QNode; /*鏈隊(duì)結(jié)點(diǎn)的類型*/typedef struct QNode *front,*rear; LQueue; void Init_LQueue(LQu

28、eue &q) QNode *p; /*申請頭尾指針結(jié)點(diǎn)*/ p=new QNode; /*申請鏈隊(duì)頭結(jié)點(diǎn)*/ p->next=NULL; q.front=q.rear=p; void In_LQueue(LQueue &q , datatype x) QNode *p;p=new QNode; /*申請新結(jié)點(diǎn)*/ p->data=x; p->next=NULL; q.rear->next=p; q.rear=p; int Empty_LQueue( LQueue q) if (q.front=q.rear) return 1; else return

29、0; int Out_LQueue(LQueue &q , datatype &x) QNode *p;if (Empty_LQueue(q) ) cout<<"隊(duì)空"<<endl; /*隊(duì)空，出隊(duì)失敗*/ else p=q.front->next; q.front->next=p->next; x=p->data;/*隊(duì)頭元素放x中*/ delete p; if (q.front->next=NULL) q.rear=q.front; return 1; void main()LQueue q;Init

30、_LQueue(q);int i,x;for(i=1;i<10;i+)In_LQueue(q,i);cout<<Empty_LQueue(q)<<endl;Out_LQueue(q,x); Out_LQueue(q,x);cout<<" "<<x<<endl;3 void main()LQueue q;SeqStack s;Init_LQueue(q);Init_SeqStack(s);int i,flag=1;char a5="abba"char x,y;i=0;while(i<4

31、)/for(i=1;i<10;i+)In_LQueue(q,ai);Push_SeqStack(s,ai);i+;while(!Empty_LQueue(q)Out_LQueue(q,x); Pop_SeqStack(s,y);if(x!=y)flag=0;if(!flag) cout<<"不是回文"<<endl;else cout<<"是回文 "<<endl;4#include <string.h>#include <iostream.h>void ReverseName(c

32、har *name, char *newName)char *p;p = strchr(name, ' ');/p指在空格' '位置*p = '0'/把空格換為'0'，因此name的長度只包括名部分strcpy(newName, p+1);/指針p+1指示的是原姓名串name的姓部分strcat(newName, ",");/新姓名串newName等于姓+逗號strcat(newName, name);/新姓名串newName等于姓+逗號+名*p = ' '/恢復(fù)原姓名串name為開始時的狀態(tài)v

33、oid main(void)char name = "William Topp", newName30;ReverseName(name, newName);cout << "Name: "<< name << endl;cout << "ReverseName: "<< newName << endl;注意問題1重點(diǎn)理解棧、隊(duì)列和串的算法思想，能夠根據(jù)實(shí)際情況選擇合適的存儲結(jié)構(gòu)。 2棧、隊(duì)列的算法是后續(xù)實(shí)驗(yàn)的基礎(chǔ)（樹、圖、查找、排序等）。實(shí)驗(yàn)三 圖算法實(shí)驗(yàn)類型：

34、驗(yàn)證性 實(shí)驗(yàn)要求：必修實(shí)驗(yàn)學(xué)時： 2學(xué)時一、實(shí)驗(yàn)?zāi)康膮⒄战o定的圖類的程序樣例，驗(yàn)證給出的有關(guān)圖的常見算法，并實(shí)現(xiàn)有關(guān)的操作。二、實(shí)驗(yàn)要求1掌握圖的特點(diǎn)，利用圖的鄰接矩陣和鄰接表的存儲結(jié)構(gòu)實(shí)現(xiàn)圖的常見算法。2提交實(shí)驗(yàn)報告，報告內(nèi)容包括：目的、要求、算法描述、程序結(jié)構(gòu)、主要變量說明、程序清單、調(diào)試情況、設(shè)計技巧、心得體會。三、實(shí)驗(yàn)內(nèi)容 1. 設(shè)計圖的鄰接表或鄰接矩陣，并給出相應(yīng)測試程序的輸出結(jié)果。2. 根據(jù)1中內(nèi)容，編寫圖的深度或廣度優(yōu)先遍歷算法，并寫出測試結(jié)果*3.假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖G中從頂點(diǎn)u到頂點(diǎn)v的長度為l 的所有簡單路徑。四、程序樣例const int MaxV

35、ertexNum=10; /*最大頂點(diǎn)數(shù)設(shè)為100*/ typedef char VertexType; /*頂點(diǎn)類型設(shè)為字符型*/ typedef int EdgeType; /*邊的權(quán)值設(shè)為整型*/ typedef struct VertexType vexsMaxVertexNum; /*頂點(diǎn)表*/ EdgeType edgesMaxVertexNumMaxVertexNum; /*鄰接矩陣，即邊表*/ int n,e; /*頂點(diǎn)數(shù)和邊數(shù)*/ Mgraph; /*Maragh是以鄰接矩陣存儲的圖類型*/ / 建立一個圖的鄰接矩陣存儲的算法如下： void CreateMGraph(Mgr

36、aph &G) /*建立有向圖G的鄰接矩陣存儲*/ int i,j,k,w; char ch; cout<<"請輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)數(shù),邊數(shù)):n"<<endl; cin>>G.n>>G.e;/*輸入頂點(diǎn)數(shù)和邊數(shù)*/ cout<<"請輸入頂點(diǎn)信息(輸入格式為:頂點(diǎn)號 ):n"<<endl; for (i=0;i<G.n;i+) cin>>G.vexsi; /*輸入頂點(diǎn)信息，建立頂點(diǎn)表*/ for (i=0;i<G.n;i+) for (j

37、=0;j<G.n;j+) G.edgesij=0; /*初始化鄰接矩陣*/ cout<<"請輸入每條邊對應(yīng)的兩個頂點(diǎn)的序號(輸入格式為:i,j):n"<<endl; for (k=0;k<G.e;k+) cin>>i>>j; /*輸入e條邊，建立鄰接矩陣*/ G.edgesij=1; /*若加入G->edgesji=1;，*/ /*則為無向圖的鄰接矩陣存儲建立*/ for (i=0;i<G.n;i+) for (j=0;j<G.n;j+) cout<<" "<

38、<G.edgesij; cout<<endl; void BFSM(Mgraph G,int k) /*以Vi為出發(fā)點(diǎn)，對鄰接矩陣存儲的圖G進(jìn)行BFS搜索*/ int i,j; LQueue Q; Init_LQueue(Q); int visitedMaxVertexNum; cout<<"visit vertex:V%cn"<<G.vexsk<<endl; /*訪問原點(diǎn)Vk*/ visitedk=1; In_LQueue(Q,k); /*原點(diǎn)Vk入隊(duì)列*/ while (!Empty_LQueue(Q) Out_LQ

39、ueue(Q,i); /*Vi出隊(duì)列*/ for (j=0;j<G.n;j+) /*依次搜索Vi的鄰接點(diǎn)Vj*/ if (G.edgesij=1 && !visitedj) /*若Vj未訪問*/ cout<<"visit vertex:V%cn"<<G.vexsj<<endl; /*訪問Vj */ visitedj=1; In_LQueue(Q,j); /*訪問過的Vj入隊(duì)列*/ /*BFSM*/ void BFSTraverseAL(Mgraph &G) /*廣度優(yōu)先遍歷以鄰接矩陣存儲的圖G*/ int i

40、; int visitedMaxVertexNum; for (i=0;i<G.n;i+) visitedi=0; /*標(biāo)志向量初始化*/ for (i=0;i<G.n;i+) if (!visitedi) BFSM(G,i); /* vi未訪問過，從vi開始BFS搜索*/ /*BFSTraverseAL*/void main()Mgraph g;CreateMGraph(g);BFSTraverseAL(g);實(shí)驗(yàn)四 排序選擇實(shí)驗(yàn)類型：綜合性 實(shí)驗(yàn)要求：必修實(shí)驗(yàn)學(xué)時： 2學(xué)時一、實(shí)驗(yàn)?zāi)康?掌握常見的排序算法的思想及其適用條件。掌握常見的排序算法的程序?qū)崿F(xiàn)。二、實(shí)驗(yàn)要求1掌握各種查找算法的特點(diǎn)，測