第一篇：湘潭大學 數(shù)據(jù)結構實驗5 實驗報告 源代碼 圖的應用
“數(shù)據(jù)結構和算法II”課程實驗報告
實驗名稱：圖及其應用
班級 姓名 學號 實驗日期： 實驗機時：2 學時 實驗成績：
-----------------一.實驗目的：
1.熟練掌握圖的兩種存儲結構(鄰接矩陣和鄰接表)的表示方法 2.掌握圖的基本運算及應用
3.加深對圖的理解，逐步培養(yǎng)解決實際問題的編程能力 二.實驗內容：（1）基本實驗內容：
采用鄰接表或鄰接矩陣方式存儲圖，實現(xiàn)圖的深度遍歷和廣度遍歷； 用廣度優(yōu)先搜索方法找出從一頂點到另一頂點邊數(shù)最少的路徑。三.程序及注釋：
#include “stdio.h” #include “l(fā)imits.h” //INT_MAX頭文件 #include “windows.h” //boolean頭文件 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 #define OVERFLOW-1 #define OK 1 #define ERROR 0 typedef int Status;typedef enum {DG,DN,UDG,UDN} GraphKind;typedef int VRType;typedef char VertexType;typedef char* InfoType;typedef int QElemType;//邊信息
typedef struct ArcCell{ VRType adj;//1或0表示是否鄰接,對帶權圖，則為權值類型 InfoType *info;}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//圖結構 typedef struct {
VertexType vexs[MAX_VERTEX_NUM];//定點向量 AdjMatrix arcs;
//鄰接矩陣，為一二維數(shù)組 //圖的當前頂點數(shù)和弧數(shù) int vexnum,arcnum;GraphKind kind;
//圖的種類標志
}MGraph;//輔助隊列
typedef struct QNode{ QElemType data;//數(shù)值域 struct QNode *next;//指針域
}QNode, *QueuePtr;typedef struct{ QueuePtr front;//隊頭 QueuePtr rear;//隊尾
}LinkQueue;//初始化隊列
Status InitQueue(LinkQueue &Q){
Q.front = Q.rear =(QueuePtr)malloc(sizeof(QNode));if(!Q.front){ printf(“內存分配失敗!”);exit(OVERFLOW);} Q.front->next = NULL;return OK;} //插入元素到隊尾
Status EnQueue(LinkQueue &Q,QElemType e){
QueuePtr p =(QueuePtr)malloc(sizeof(QNode));if(!p){printf(“n內存分配失敗!”);exit(OVERFLOW);} p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;} //隊列判空
Status QueueEmpty(LinkQueue Q){ return Q.front == Q.rear;} //銷毀隊列
Status DestroyQueue(LinkQueue &Q){
while(Q.front){Q.rear = Q.front->next;free(Q.front);Q.front = Q.rear;} return OK;} //刪除隊頭元素
Status DeQueue(LinkQueue &Q,QElemType &e){
if(QueueEmpty(Q)){printf(“n隊列為空！”);return ERROR;} QueuePtr p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear==p)Q.rear = Q.front;free(p);return OK;} //對頂點v定位，返回該頂點在數(shù)組的下標索引，若找不到則返回-1 int LocateVex(MGraph G,char v){
for(int i=0;i G.kind = UDN;printf(“輸入頂點個數(shù)和邊數(shù)(如：4,3):”);int vexnum,arcnum;scanf(“%d,%d”,&vexnum,&arcnum);G.vexnum=vexnum;G.arcnum=arcnum;//判斷是否超過頂點最大個數(shù) while(G.vexnum>MAX_VERTEX_NUM){printf(“最大頂點為20，重新輸入(如：4,3):”);scanf(“%d,%d”,&G.vexnum,&G.arcnum);} printf(“n依次輸入頂點向量值n”);int i;for(i=0;i //清空緩沖區(qū) fflush(stdin);printf(“第%d個:”,i+1);scanf(“%c”,&G.vexs[i]);} //初始化鄰接矩陣 for(i=0;i int values;printf(“n輸入依附兩個頂點的邊及其權值<如，a,b,1>n”);for(i=0;i printf(“第%d條：”,i+1);//清空緩沖區(qū) fflush(stdin);scanf(“%c,%c,%d”,&rear,&front,&values);int m,n;//定位兩頂點在vexs數(shù)組中的索引 m = LocateVex(G,rear);n = LocateVex(G,front);if(m==-1||n==-1){ printf(“輸入頂點或不在此圖中，請重新輸入！n”);i--;continue;} //賦予對應矩陣位置的權值，以及對稱弧的權值 G.arcs[m][n].adj = values;G.arcs[n][m].adj = values;} return OK;} //CreateUDG //矩陣輸出 void printArcs(MGraph G){ int i;printf(“ ”);//輸出第一行的頂點向量 for(i=0;i for(int j=0;j else printf(“ %d”,G.arcs[i][j].adj);}} printf(“ ∞”); printf(“n”);} //訪問頂點v輸出 Status printAdjVex(MGraph G,int v){ printf(“%c ”,G.vexs[v]);return OK;} //查找v頂點的第一個鄰接點 Status FirstAdjVex(MGraph G,int v){ //查找與頂點v的第一個鄰接點，找到后立即返回其索引，若找不到，則返回-1 for(int i=1;i return i;} return-1;} //查找基于v頂點的w鄰接點的下一個鄰接點 Status NextAdjVex(MGraph G,int v,int w){ //查找基于頂點v的w鄰接點的下一個鄰接點，找到之后立即返回其索引，若找不到，則返回-1 for(int i=w+1;i boolean visited[MAX_VERTEX_NUM];//函數(shù)指針變量 Status(* VisitFunc)(MGraph G,int v);//DFS,從第v個頂點出發(fā)遞歸深度優(yōu)先遍歷圖G void DFS(MGraph G,int v){ visited[v] = TRUE;//訪問第v個頂點 VisitFunc(G,v);for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w)){if(!visited[w]) DFS(G,w);}} //深度優(yōu)先遍歷 void DFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //將函數(shù)復制給全局的函數(shù)指針變量，待調用DFS時使用 VisitFunc = Visit;int v;//將訪問標記初始化為false for(v=0;v void BFSTraverse(MGraph G,Status(*Visit)(MGraph G,int v)){ //按廣度優(yōu)先非遞歸遍歷圖G，使用輔助隊列Q和訪問標志數(shù)組Visited int v;int u;//將訪問標記數(shù)組初始化為false for(v = 0;v //判斷頂點V是否被訪問 if(!visited[v]){//將第一次訪問的頂點對應的訪問標記數(shù)組位置賦值為TRUE visited[v] = TRUE;//輸出頂點v Visit(G,v);EnQueue(Q,v);while(!QueueEmpty(Q)){//按入隊序列取出頂點，便于查找此頂點的鄰接點 DeQueue(Q,u);//查找當前頂點鄰接點 for(int w=FirstAdjVex(G,u);w>=0;w = NextAdjVex(G,u,w)) if(!visited[w]){visited[w] =TRUE;Visit(G,w);EnQueue(Q,w);}}} //銷毀隊列 DestroyQueue(Q);} int main(){ printf(“====圖的創(chuàng)建及其應用====n”);//創(chuàng)建一個圖 MGraph G;CreateUDN(G);//用鄰接矩陣輸出圖 printf(“n圖的鄰接矩陣輸出如下:n”);printArcs(G);//深度優(yōu)先遍歷 printf(“n深度優(yōu)先遍歷序列:n”);DFSTraverse(G,printAdjVex);printf(“n”);//廣度優(yōu)先遍歷 } printf(“n廣度優(yōu)先遍歷序列:n”);BFSTraverse(G,printAdjVex);printf(“n”);四.運行結果： 五.實驗心得： 通過本次課程設計，對圖的概念有了一個新的認識，在學習離散數(shù)學的時候，總覺得圖是很抽象的東西，但是在學習了《數(shù)據(jù)結構與算法》這門課程之后，我慢慢地體會到了其中的奧妙，圖能夠在計算機中存在，首先要捕捉他有哪些具體化、數(shù)字化的信息，比如說權值、頂點個數(shù)等，這也就說明了想要把生活中的信息轉化到計算機中必須用數(shù)字來完整的構成一個信息庫，而圖的存在，又涉及到了頂點之間的聯(lián)系。圖分為有向圖和無向圖，而無向圖又是有向圖在權值雙向相等下的一種特例，如何能在計算機中表示一個雙向權值不同的圖，這就是一件很巧妙的事情。有了這次課程設計的經驗和教訓，我能夠很清楚的對自己定一個合適的水平。 目錄 前言..................................................................................................................2 概要設計..................................................................................................................3 1.1 數(shù)據(jù)結構設計...........................................................................................3 2.1 算法設計...................................................................................................3 2.1.1 建立鏈表的算法..............................................................................3 2.1.2 鏈表插入一個元素的算法..............................................................3 2.1.3 鏈表刪除一個元素的算法..............................................................3 3.1 ADT描述..................................................................................................4 4.1 詳細設計…………………………………………… ……………………………… 4 4.1.1 數(shù)據(jù)存儲結構……………………………… ……………………………… 4.4.1.2 主要偽代碼…… …………………… ……………………………………… 4 軟件測試..................................................................................................................7 心得體會................................................................................................................11 源代碼...................................................................................................................12 參考文獻………………………………………………………………………...21 前言 數(shù)據(jù)結構是計算機程序設計的重要理論技術基礎，它不僅是計算機學科的核心課程，而且已經成為其他理工專業(yè)的熱門選修課。 隨著計算機科學的技術和發(fā)展，計算機的功能和運算速度不斷地提高，其應用于信息處理的范圍日益擴大。與之相應的，計算機的加工處理對象也從簡單的數(shù)據(jù)發(fā)展到一般的符號，進而發(fā)展到更復雜的數(shù)據(jù)結構。數(shù)據(jù)結構是計算機程序設計的重要理論技術基礎，數(shù)據(jù)結構的表示和操作都涉及到算法，如何描述數(shù)據(jù)的結構和討論有關的算法，又涉及到程序設計語言。因此，它不僅是計算機學科的核心課程，而且已經成為其他理工專業(yè)的熱門選修課。我們通過對這門基礎課程的學習，要學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的數(shù)據(jù)選擇適合的邏輯結構，儲存結構及其相應的算法，并初步掌握算法時間分析和空間分析的技術。通過實際操作去了解數(shù)據(jù)結構原理，練習編寫代碼的能力，以及抽象能力。 從課程性質上講，“數(shù)據(jù)結構”是一門專業(yè)技術基礎課。它的要求是學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的數(shù)據(jù)選擇適當?shù)倪壿嫿Y構，存儲結構及相應的算法，并初步掌握算法的時間分析和空間分析的技術。另一方面，數(shù)據(jù)結構的學習過程也是復雜程序設計的訓練過程，要求編寫的程序結構清楚和正確易讀，符合軟件工程的規(guī)范。 概要設計 1.1 數(shù)據(jù)結構設計 采用鏈式儲存結構。typedef struct LNode{ ElemType data;struct LNode *next;}LNode,*LinkList;2.1 算法設計 2.1.1 建立鏈表的算法 （1）算法思想分析 首先從表尾到表頭逆向建立單鏈表,然后再建立的單鏈表基礎上進行對鏈表上的元素進行查詢,刪除,插入的操作。（2）要點描述 首先建立一個帶頭結點的單鏈表，通過申請內存，先建立一個空鏈表。然后結點的插入，建立一個有多個結點的鏈表。在進行查詢等操作。（3）時間和空間復雜度分析 程序的時間復雜度為O(n)。 2.1.2 鏈表插入一個元素的算法 （1）算法思想分析 要生成一個新數(shù)據(jù)域為X的結點，然后插入在單鏈表中。（2）要點描述 在鏈表中插入結點只需要修改指針。若要在第 i 個結點之前插入元素，修改的是第 i-1 個結點的指針。 （3）時間和空間復雜度分析 時間復雜度O(n)2.1.3 鏈表刪除一個元素的算法 （1）算法思想分析 要刪除一個結點，必須修改指針并且釋放空間。（2）要點描述 找到線性表中第i-1個結點，修改其指向后繼的指針。 （3）時間和空間復雜度分析 時間復雜度O(n) 3.1 ADT描述 ADT LinkList{ 數(shù)據(jù)對象：D={ e | e∈LNode } 數(shù)據(jù)關系：R1={ 基本操作： GreateList_L(&L, n) 操作結果：構造了一個長為n的數(shù)據(jù)鏈表 ListDelete_L(&L, i, &e) 初始條件：鏈表L已存在而且非空 操作結果：刪除L的第i個數(shù)據(jù)，并且用e返回其值 ListInsert_L(&L, i, e) 初始條件：鏈表L已存在 操作結果： 在L的第i個位置插入數(shù)據(jù)e GetElem(L, i, e) 初始條件：鏈表L已存在 操作結果：用e返回L中的第i個數(shù)據(jù) }ADT LinkList 4.1 詳細設計 4.1.1數(shù)據(jù)存儲結構設計 采用單鏈式線性表實現(xiàn) 4.1.2 主要偽代碼 Status GetElem(LinkList L, int i, ElemType *e){ int j=0;int d;LinkList p = L;while(p&&j } if(!p || j > i)return ERROR;printf(“您要查詢的元素是:n”);d=p->data;printf(“%d”,d);printf(“n”);} void InitList(LinkList *L){ *L =(LinkList)malloc(sizeof(struct LNode));if(!*L)exit(OVERFLOW);(*L)->next = NULL;} Status ListInsert(LinkList L, int i, ElemType e){ int j = 0;LinkList p = L, s;while(p && j < i-1){ p = p->next;j++;} if(!p|| j > i-1)return ERROR;s =(LinkList)malloc(sizeof(struct LNode));s->data = e;s->next = p->next;p->next = s;return OK;} Status ListDelete(LinkList L, int i, ElemType *e){ int j = 0;LinkList p = L, q;while(p->next && j < i-1){ p = p->next; j++;} if(!p->next || j > i-1)return ERROR;q = p->next;p->next = q->next;*e = q->data;free(q);return OK;} void ListTraverse(LinkList L, void(*vi)(ElemType)){ LinkList p = L->next;while(p){ vi(p->data);p = p->next;} printf(“n”);} void ListPrint(LinkList L){ LinkList p = L->next;while(p){ printf(“%d ”, p->data);p = p->next;} printf(“n”);} void printInt(int data){ printf(“%d ”, data);}.軟件測試 圖一(主界面) 圖二(插入學生信息) 圖三(顯示所有學生信息) 圖四(查詢個人信息) 圖五(統(tǒng)計信息) 圖六(修改信息) 圖七(保存數(shù)據(jù)) 圖八(刪除信息) 心得體會 通過本程序的設計，我對數(shù)據(jù)結構作了以下總結：要解決一道程序題必須先要認真捕捉改程序中的有用信息，找出解決方法。先規(guī)劃好，程序需要什么樣的數(shù)據(jù)結構，什么函數(shù)，對程序有什么要求。然后從整體把握對程序設計進行分工，相應地把程序分成若干模塊，具體實現(xiàn)各部分實行相應的功能。一個程序要順利地進行設計，一是要對程序的功能有全面的了解，如果漏了某些部分，都會使得這個程序調試不出來或者是令該程序沒有達到預想的效果。其次，在程序的編譯中，必須注重程序設計過程中的細節(jié)，像單鏈表的程序，就要理解鏈表的概念，理解鏈表的數(shù)據(jù)特點，要清楚知道數(shù)據(jù)域和指針域的作用，否則，很容易會浪費大量時間在檢測錯誤上面。要說到解題的思考方向，如果要總結成規(guī)律，我認為要靈活的進行方法的設計，通過不同的方法來實現(xiàn)不同的功能，如通過結點的插入來實現(xiàn)鏈表的創(chuàng)建。同時應該注意各種語句的選擇，要先預想好需要什么樣的語句來實現(xiàn)函數(shù)定義，盡量簡單快捷地完成，避免出錯。 要規(guī)范面向對象程序設計師的書寫協(xié)管，在這次課程設計中，我們再次感受到，規(guī)范的程序書寫，可以更好的進行后期的差錯補漏。還應該注意各種面向對象語言語法的運用，例如繼承的方法，都要嚴格按照語法來進行，否則很容易就會出現(xiàn)錯誤，甚至嚴重影響課程設計的進度。 源代碼 #include “stdio.h” #include “stdlib.h” #include “string.h” int shoudsave=0;// struct student { char num[10];//學號 char name[20]; char sex[4]; int cgrade; int mgrade; int egrade; int totle; int ave; char neartime[10];//最近更新時間 }; typedef struct node { struct student data; struct node *next;}Node,*Link; int menu(){ char m[3]; int n; printf(“ ************************歡迎進入學生成績管理系統(tǒng)******************************nn”); printf(“t歡迎使用本學生管理系統(tǒng)，本系統(tǒng)將為您提供歷史學生信息查詢，學生成績信息管理功能。n”); printf(“********************************************************************************”); printf(“t1輸入學生資料ttttt2刪除學生資料n”); printf(“t3查詢學生資料ttttt4修改學生資料n”); printf(“t5顯示學生資料ttttt6統(tǒng)計學生成績n”); printf(“t7保存學生資料n”); printf(“ttplease choose a operation(1-7):n”); printf(“*********************************************************************** *********n”); scanf(“%s”,m); n=atoi(m); return(n);} void printstart(){ printf(“---------n”);} void Wrong(){ printf(“n=====>提示:輸入錯誤!n”);} void Nofind(){ printf(“n=====>提示:沒有找到該學生!n”);} void printc()// 本函數(shù)用于輸出中文 { printf(“學號t 姓名 性別 英語成績 數(shù)據(jù)庫成績 數(shù)據(jù)結構成績 總分平均分n”);} void printe(Node *p)//本函數(shù)用于輸出英文 { printf(“%-12s%stt%st%dtt%dt%dt%dt %dn”,p->data.num,p->data.name,p->data.sex,p->data.egrade,p->data.mgrade,p->data.cgrade,p->data.totle,p->data.ave);} Node* Locate(Link l,char findmess[],char nameornum[])//該函數(shù)用于定位連表中符合要求的接點，并返回該指針 { Node *r; if(strcmp(nameornum,“num”)==0)//按學號查詢 { r=l->next; while(r!=NULL) { if(strcmp(r->data.num,findmess)==0) return r; r=r->next; } } else if(strcmp(nameornum,“name”)==0)//按姓名查詢 { r=l->next; while(r!=NULL) { if(strcmp(r->data.name,findmess)==0) return r; r=r->next; } } return 0;} void Add(Link l)//增加學生 { Node *p,*r,*s; char num[10]; r=l; s=l->next; while(r->next!=NULL) r=r->next;//將指針置于最末尾 while(1) { printf(“請你輸入學號(以'0'返回上一級菜單:)”); scanf(“%s”,num); if(strcmp(num,“0”)==0) break; while(s) { if(strcmp(s->data.num,num)==0) { printf(“=====>提示:學號為'%s'的學生已經存在,若要修改請你選擇'4 修改'!n”,num); printstart(); printc(); printe(s); printstart(); printf(“n”); return; } s=s->next; } p=(Node *)malloc(sizeof(Node)); strcpy(p->data.num,num); printf(“請你輸入姓名:”); scanf(“%s”,p->data.name); getchar(); printf(“請你輸入性別:”); scanf(“%s”,p->data.sex); getchar(); printf(“請你輸入數(shù)據(jù)結構成績:”); scanf(“%d”,&p->data.cgrade); getchar(); printf(“請你輸入數(shù)據(jù)庫成績:”); scanf(“%d”,&p->data.mgrade); getchar(); printf(“請你輸入英語成績:”); scanf(“%d”,&p->data.egrade); getchar(); p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade; p->data.ave=p->data.totle / 3; //信息輸入已經完成p->next=NULL; r->next=p; r=p; shoudsave=1; } } void Qur(Link l)//查詢學生 { char findmess[20]; Node *p; if(!l->next) { printf(“n=====>提示:沒有資料可以查詢!n”); return; } printf(“請你輸入要查找的學號:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { printf(“tttt查找結果n”); printstart(); printc(); printe(p); printstart(); } else Nofind();} void Del(Link l)//刪除 { Node *p,*r; char findmess[20]; if(!l->next) { printf(“n=====>提示:沒有資料可以刪除!n”); return; } printf(“n=====>確定進行刪除操作請按 1，按其他按鍵退出該操作nnnn”); if(menu()==1) { printf(“請你輸入要刪除的學號:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { r=l; while(r->next!=p) r=r->next; r->next=p->next; free(p); printf(“n=====>提示:該學生已經成功刪除!n”); shoudsave=1; } else Nofind(); } else exit;} void Modify(Link l)//修改函數(shù) { Node *p; char findmess[20]; if(!l->next) { printf(“n=====>提示:沒有資料可以修改!n”); return; } printf(“請你輸入要修改的學生學號:”); scanf(“%s”,findmess); p=Locate(l,findmess,“num”); if(p) { printf(“請你輸入新學號(原來是%s):”,p->data.num); scanf(“%s”,p->data.num); printf(“請你輸入新姓名(原來是%s):”,p->data.name); scanf(“%s”,p->data.name); getchar(); printf(“請你輸入新性別(原來是%s):”,p->data.sex); scanf(“%s”,p->data.sex); printf(“請你輸入新的數(shù)據(jù)結構成績(原來是%d分):”,p->data.cgrade); scanf(“%d”,&p->data.cgrade); getchar(); printf(“請你輸入新的數(shù)據(jù)庫成績(原來是%d分):”,p->data.mgrade); scanf(“%d”,&p->data.mgrade); getchar(); printf(“請你輸入新的英語成績(原來是%d分):”,p->data.egrade); scanf(“%d”,&p->data.egrade); p->data.totle=p->data.egrade+p->data.cgrade+p->data.mgrade; p->data.ave=p->data.totle/3; printf(“n=====>提示:資料修改成功!n”); shoudsave=1; } else Nofind(); } void Disp(Link l)//顯示函數(shù) { int count=0; Node *p; p=l->next; if(!p) { printf(“n=====>提示:沒有資料可以顯示!n”); return; } printf(“tttt顯示結果n”); printstart(); printc(); printf(“n”); while(p) { printe(p); p=p->next; } printstart(); printf(“n”);} void Tongji(Link l)//統(tǒng)計函數(shù) { Node *pm,*pe,*pc,*pt,*pa;//用于指向分數(shù)最高的接點 Node *r=l->next; if(!r) { printf(“n=====>提示:沒有資料可以統(tǒng)計!n”); return; } pm=pe=pc=pt=pa=r; while(r!=NULL) { if(r->data.cgrade>=pc->data.cgrade) pc=r; if(r->data.mgrade>=pm->data.mgrade) pm=r; if(r->data.egrade>=pe->data.egrade) pe=r; if(r->data.totle>=pt->data.totle) pt=r; if(r->data.ave>=pa->data.ave) pa=r; r=r->next; } printf(“------------------------------統(tǒng)計結果-n”); printf(“總分最高者:t%s %d分n”,pt->data.name,pt->data.totle); printf(“平均分最高者:t%s %d分n”,pa->data.name,pa->data.ave); printf(“英語最高者:t%s %d分n”,pe->data.name,pe->data.egrade); printf(“數(shù)據(jù)庫最高者:t%s %d分n”,pm->data.name,pm->data.mgrade); printf(“數(shù)據(jù)結構最高者:t%s %d分n”,pc->data.name,pc->data.cgrade); printstart();} void Save(Link l)//保存函數(shù) { FILE* fp; Node *p; int flag=1,count=0; fp=fopen(“c:student”,“wb”); if(fp==NULL) { printf(“n=====>提示:重新打開文件時發(fā)生錯誤!n”); exit(1); } p=l->next; while(p) { if(fwrite(p,sizeof(Node),1,fp)==1) { p=p->next; count++; } else { flag=0; break; } } if(flag) { printf(“n=====>提示:文件保存成功.(有%d條記錄已經保存.)n”,count); shoudsave=0; } fclose(fp);} void main(){ Link l;//連表 FILE *fp;//文件指針 char ch; char jian; int count=0; Node *p,*r; l=(Node*)malloc(sizeof(Node)); l->next=NULL; r=l; fp=fopen(“C:student”,“rb”); if(fp==NULL) { fp=fopen(“C:student”,“wb”); exit(0); } printf(“n=====>提示:文件已經打開,正在導入記錄......n”); while(!feof(fp)) { p=(Node*)malloc(sizeof(Node)); if(fread(p,sizeof(Node),1,fp))//將文件的內容放入接點中 { p->next=NULL; r->next=p; r=p;//將該接點掛入連中 count++; } } fclose(fp);//關閉文件 printf(“n=====>提示:記錄導入完畢,共導入%d條記錄.n”,count); for(;;) { switch(menu()) { case 1:Add(l);break;//增加學生 case 2:Del(l);break;//刪除學生 case 3:Qur(l);break;//查詢學生 case 4:Modify(l);break;//修改學生 case 5:Disp(l);break;//顯示學生 case 6:Tongji(l);break;//統(tǒng)計學生 case 7:Save(l);break;//保存學生 default: Wrong(); getchar(); break; } } } 參考文獻 《數(shù)據(jù)結構（C語言版）》----------------清華大學出版社 嚴蔚敏 吳偉民 編著 《C語言程序設計》------------------------中國鐵道出版社 丁峻嶺 余堅 編著 數(shù)據(jù)結構上機實驗六 實驗內容:圖的基本操作 實驗要求: 1)圖的遍歷與基本操作要作為函數(shù)被調用.2)把自己使用的圖結構明確的表達出來.3)基本上實現(xiàn)每個實驗題目的要求.分組要求：可單獨完成，也可兩人一組。 實驗目的: 1)熟悉C/C++基本編程,培養(yǎng)動手能力.2)通過實驗,加深對圖的理解.評分標準： 1)只完成第一和第二題，根據(jù)情況得4，5分； 2）完成前3題，根據(jù)情況得5至7分； 3）在2）基礎上，選做四）中題目，根據(jù)情況得8至10分。 題目: 一)建立一個無向圖+遍歷+插入 (1)以數(shù)組表示法作為存儲結構，從鍵盤依次輸入頂點數(shù)、弧數(shù)與各弧信息建立一個無向圖； (2)對（1）中生成的無向圖進行廣度優(yōu)先遍歷并打印結果； (3)向（1）中生成的無向圖插入一條新弧并打印結果； 二)建立一個有向圖+遍歷+插入+刪除 (1)以鄰接表作為圖的存儲結構，從鍵盤輸入圖的頂點與弧的信息建立一個有向圖； (2)對（1）中生成的有向圖進行深度優(yōu)先遍歷并打印結果； (3)在（1）中生成的有向圖中，分別插入與刪除一條弧并打印其結果； (4)在（1）中生成的有向圖中，分別插入與刪除一個頂點并打印結果； (5)在（1）中生成的有向圖中,各頂點的入度與出度并打印結果； 三）基本應用題 （1）編寫算法，判斷圖中指定的兩個頂點是否連通。 （2）編寫算法，判斷圖的連通性。如果不連通，求連通分量的個數(shù) （3）編寫算法，判斷圖中任意兩個頂點的連通性 （4）編寫算法，判斷圖中是否存在回路。 （5）實現(xiàn)圖的廣度優(yōu)先搜索算法。 四）高級應用題 （1）實現(xiàn)Prim算法 （2）實現(xiàn)Kruskal算法 （3）實現(xiàn)迪杰斯特拉算法 （4）實現(xiàn)拓撲排序算法 （5）實現(xiàn)關鍵路徑算法 數(shù)據(jù)結構實驗報告 專業(yè)班級： 指導老師：余臘生 姓 名： 學 號： 實驗一 單鏈表的基本操作的實現(xiàn) 一、實驗目的 掌握單鏈表的基本操作：建立、插入、刪除、查找等運算。 二、實驗儀器 安裝VC++的PC機。 三、實驗原理 利用線性表的特性以及其鏈式存儲結構特點對線性表進行相關操作。 四、實驗內容 程序中演示了單鏈表的創(chuàng)建、插入、刪除和查找。程序如下： #include scanf(“%d”,&x);while(x!=-1){ p=(NODE *)malloc(sizeof(NODE));p->data=x;p->next=head->next;head->next=p;scanf(“%d”,&x);} return(head);} /******************************************/ void Output(NODE *head){ NODE *p;p=head;printf(“Begin to dump the LinkList...n”);while(p->next!=NULL){ printf(“->%d”,p->next->data);p=p->next;} printf(“nThe LinkList ended!n”);} /******************************************/ int Listlen(NODE *head){ int i=0;NODE *p=head;while(p->next!=NULL){ i++;p=p->next;} return(i);} /******************************************/ int Get(NODE *head,int i){ int j=0;NODE *p=head;while(p->next&&j 五、數(shù)據(jù)記錄及處理 1、運行程序,輸入下面一組數(shù)據(jù): 93 94 12 13 20 14 鏈表順序：14 20 13 12 94 93 2、刪除第二個數(shù)據(jù)結點，在第一個位置插入數(shù)據(jù)20。 運行結果如下: 插入結果：14 13 12 94 93 刪除結果：20 14 13 12 94 93 運行結果截圖： 實驗二 棧和隊列的實現(xiàn) 一、目的和要求 1.理解隊列和棧的順序存儲結構和鏈式存儲結構。通過本實驗，熟悉隊列、棧的結構特點； 2.熟悉隊列、棧結構上的操作與算法的實現(xiàn)。 二、實驗內容 1.隊列的基本操作和應用。2.棧的基本操作和應用。 三、儀器、設備和材料 1.適合實驗要求的計算機系統(tǒng)。2.VＣ++編程平臺。 四、實驗原理 隊列與棧是一種操作受限制的線性表，在了解線性表的基本原理的基礎上，理解與完成此項實驗。 五、實驗步驟 1.采用隊列的順序存儲結構。 2.用菜單的形式完成隊列的建立，出隊，入隊等基本操作。3.采用棧的鏈式存儲結構。 4.用菜單的形式完成棧的出棧、入棧等基本操作。 六、程序算法 #include SElemType *top;}SqStack; SqStack InitStacka()//順序存儲實現(xiàn)棧的初始化 {SqStack S;S.base=(SElemType *)malloc(MAX*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;return(S);} void Pusha(SqStack &S,int x)//順序存儲實現(xiàn)棧的入棧操作 {if(S.top-S.base>=MAX)exit(OVERFLOW);*S.top++=x;} void Popa(SqStack &S)//順序存儲實現(xiàn)棧的出棧操作 {SElemType *p;int x;if(S.top==S.base)return;else {p=S.top;x=*--S.top;printf(“t刪除的棧頂元素是%dnt出棧操作完成后的棧為:n”,x);} } void printa(SqStack S)//輸出 {SElemType *p;p=S.base;printf(“t”);while(p!=S.top){printf(“%d ”,*(p++));} printf(“n”);} typedef struct SqNode {SElemType data;SqNode *Link;}*Sqptr,NODE;typedef struct {Sqptr top;}Stack; Stack InitStackb()//鏈式存儲實現(xiàn)棧的初始化 {Stack S;S.top=(Sqptr)malloc(sizeof(NODE));if(!S.top)exit(OVERFLOW);S.top->Link=NULL;return(S);} void Pushb(Stack &S,int x)//鏈式存儲實現(xiàn)棧的入棧操作 {Sqptr p;p=(Sqptr)malloc(sizeof(NODE));if(!p)return;p->data=x;p->Link=S.top->Link;S.top->Link=p;} void Popb(Stack &S)//鏈式存儲實現(xiàn)棧的出棧操作 {int x;Sqptr p;if(S.top->Link==NULL)return;else {p=S.top->Link; x=p->data; S.top->Link=p->Link; printf(“t刪除的棧頂元素是%dn”,x); free(p);} } typedef struct QNode {QElemType data;struct QNode *next;}*QueuePtr,QNode;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;LinkQueue InitQueue()//鏈式存儲實現(xiàn)隊列的初始化 {LinkQueue Q;Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL; return(Q);} void EnQueue(LinkQueue &Q,QElemType x)//鏈式存儲實現(xiàn)隊列的入隊 {QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=x;p->next=NULL;Q.rear->next=p;Q.rear=p;} void DeQueue(LinkQueue &Q)//鏈式存儲實現(xiàn)隊列的出隊 {int x;if(Q.front==Q.rear)return;QueuePtr p;p=Q.front->next;x=p->data;printf(“t刪除的隊頭元素是：%dn”,x);Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);return;} typedef struct {SElemType *base;int front,rear;}SqQueue;SqQueue InitQueueb()//順序存儲實現(xiàn)隊列的初始化 {SqQueue S;S.base=(SElemType *)malloc(MAX*sizeof(SElemType));if(!S.base)exit(OVERFLOW);S.front=S.rear=0;return(S);} void EnQueueb(SqQueue &S,int x) //順序存儲實現(xiàn)隊列的入隊 {if((S.rear+1)%MAX==S.front)return;S.base[S.rear]=x;S.rear=(S.rear+1)%MAX;} void DeQueueb(SqQueue &S)//順序存儲實現(xiàn)隊列的出隊 {int x;if(S.front==S.rear)return;x=S.base[S.front];S.front=(S.front+1)%MAX;printf(“t刪除的隊頭元素是:%dn”,x);} void main(){int choice;int n,x;printf(“nn”);printf(“t1.采用鏈式存儲實現(xiàn)棧的初始化、入棧、出棧操作n”);printf(“t2.采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作n”);printf(“t3.采用鏈式存儲實現(xiàn)隊列的初始化、入隊、出隊操作n”);printf(“t4.采用順序存儲實現(xiàn)隊列的初始化、入隊、出隊操作n”);printf(“t請選擇:”);scanf(“%d”,&choice);switch(choice){case 1:Stack Sa; printf(“t1.鏈式存儲實現(xiàn)棧的初始化n”); printf(“t2.鏈式存儲實現(xiàn)棧的入棧操作n”); printf(“t3.鏈式存儲實現(xiàn)棧的出棧操作n”); while(1){ printf(“t請選擇：”); scanf(“%d”,&n); switch(n) {case 1:Sa=InitStackb(); printf(“t鏈式存儲棧的初始化完成!n”);break; case 2:printf(“t以'0'結束n”);printf(“t”); scanf(“%d”,&x); while(x){ Pushb(Sa,x);scanf(“%d”,&x);} printf(“t鏈式存儲棧的入棧操作完成!n”);break; case 3:Popb(Sa);break;}}break; case 2:SqStack S; printf(“t1.順序存儲實現(xiàn)棧的初始化n”); printf(“t2.順序存儲實現(xiàn)棧的入棧操作n”); printf(“t3.順序存儲實現(xiàn)棧的出棧操作n”); while(1){ printf(“t請選擇:”); scanf(“%d”,&n); switch(n) { case 1:S=InitStacka(); printf(“t順序存儲棧的初始化完成!n”);break; case 2:printf(“t以'0'結束n”); printf(“t”); scanf(“%d”,&x); while(x){ Pusha(S,x); scanf(“%d”,&x);} printf(“t順序存儲棧的入棧操作完成!n”); printa(S);break; case 3:Popa(S); printa(S);break;}}break; case 3:LinkQueue Q; printf(“t1.鏈式存儲實現(xiàn)隊的初始化n”); printf(“t2.鏈式存儲實現(xiàn)隊的入棧操作n”); printf(“t3.鏈式存儲實現(xiàn)隊的出棧操作n”); while(1){ printf(“t請選擇：”); scanf(“%d”,&n); switch(n) { case 1:Q=InitQueue(); printf(“t鏈式存儲隊的初始化完成!n”);break; case 2:printf(“t以'0'結束n”);printf(“t”);scanf(“%d”,&x); while(x){ EnQueue(Q,x);scanf(“%d”,&x);} printf(“t鏈式存儲隊的入棧操作完成!n”);break; case 3:DeQueue(Q);break;}}break; case 4:SqQueue Sv; printf(“t1.順序存儲實現(xiàn)隊的初始化n”); printf(“t2.順序存儲實現(xiàn)隊的入棧操作n”); printf(“t3.順序存儲實現(xiàn)隊的出棧操作n”); while(1){ printf(“t請選擇：”); scanf(“%d”,&n); switch(n) {case 1:Sv=InitQueueb(); printf(“t鏈式存儲棧的初始化完成!n”);break; case 2:printf(“t以'0'結束n”);printf(“t”);scanf(“%d”,&x); while(x){ EnQueueb(Sv,x);scanf(“%d”,&x);} printf(“t鏈式存儲棧的入棧操作完成!n”);break; case 3: DeQueueb(Sv);break;}}break;} } 程序調試截圖： 1.采用鏈式存儲實現(xiàn)棧的初始化、入棧、出棧操作 2.采用順序存儲實現(xiàn)棧的初始化、入棧、出棧操作 3.采用鏈式存儲實現(xiàn)隊列的初始化、入隊、出隊操作 4.采用順序存儲實現(xiàn)隊列的初始化、入隊、出隊操作 七、心得體會 實踐才能出真知，在通過了上機操作后，才發(fā)現(xiàn)了許多在平時上理論課的時候沒有想到的方方面面，編寫程序時發(fā)現(xiàn)很多語法的錯誤，以及很多英語單詞的記不熟，記錯，程序函數(shù)錯用等等，我想需要在以后多多練習，才能逐步解決這些問題。實驗三 二叉樹的建立和遍歷 一、目的和要求 1、了解二叉樹的建立的方法及其遍歷的順序，熟悉二叉樹的三種遍歷 2、檢驗輸入的數(shù)據(jù)是否可以構成一顆二叉樹 二、實驗內容 1.二叉樹的建立和遍歷 三、儀器、設備和材料 1.適合實驗要求的計算機系統(tǒng)。2.VＣ++編程平臺。 四、實驗的描述和算法 1、實驗描述 二叉樹的建立首先要建立一個二叉鏈表的結構體，包含根節(jié)點和左右子樹。因為耳熟的每一個左右子樹又是一顆二叉樹，所以可以用遞歸的方法來建立其左右子樹。二叉樹的遍歷是一種把二叉樹的每一個節(jié)點訪問完并輸出的過程，遍歷時根結點與左右孩子的輸出順序構成了不同的遍歷方法，這個過程需要按照不同的遍歷的方法，先輸出根結點還是先輸出左右孩子，可以用選擇語句實現(xiàn)。 2、算法 #include //二叉樹結點類定義 { T data; //數(shù)據(jù)域 BinTreeNode //左子女、右子女域 BinTreeNode(T x=T(),BinTreeNode :data(x),leftChild(l),rightChild(r){} //可選擇參數(shù)的默認構造函數(shù) };//-----------template //非遞歸前序遍歷 { stack while(p!=NULL) { cout< data; //訪問根結點 S.push(p); p=p->leftChild; //遍歷指針進到左子女結點 } if(!S.empty()) //棧不空時退棧 { p=S.top(); S.pop(); p = p->rightChild; //遍歷指針進到右子女結點 } } } //--template //非遞歸中序遍歷 { stack while(p!=NULL) //遍歷指針未到最左下的結點，不空 { S.push(p); p=p->leftChild; } if(!S.empty()) //棧不空時退棧 { p=S.top(); S.pop(); cout< data; p=p->rightChild; } } while(p!=NULL ||!S.empty());} //----template while(p!= NULL ||!S.empty()) //左子樹經過結點加L進棧 { while(p!=NULL) { S.push(p);//首先將t和tag為入棧，遍歷左子樹 tag.push(0);//遍歷左子樹前的現(xiàn)場保護 p=p->leftChild; } while(!S.empty()&& tag.top()==1) { p=S.top(); S.pop(); tag.pop(); cout< data;//最后訪問根結點。 } if(!S.empty()) { tag.pop(); tag.push(1);//遍歷右子樹前的現(xiàn)場保護,修改棧頂tag為，遍歷右子樹 p=S.top(); // 取棧頂保存的指針 p=p->rightChild; } else break; } } template if(subTree!=NULL) //NULL是遞歸終止條件 { InOrder_1(subTree->leftChild);//中序遍歷根的左子樹 cout< //訪問根結點 InOrder_1(subTree->rightChild);//中序遍歷根的右子樹 } } template //遞歸結束條件 { cout< PreOrder_1(subTree->leftChild); //前序遍歷根的左子樹 PreOrder_1(subTree->rightChild); //前序遍歷根的右子樹 } } template if(subTree!=NULL) //NULL是遞歸終止條件 { PostOrder_1(subTree->leftChild);//后序遍歷根的左子樹 PostOrder_1(subTree->rightChild);//后序遍歷根的右子樹 cout< //訪問根結點 } } //------------template T item; cin>>item; if(item!=-1) { subTree = new BinTreeNode if(subTree == NULL) { cerr<<“存儲分配錯！”< exit(1); } subTree->data = item; CreateBinTree(subTree->leftChild);//遞歸建立左子樹 CreateBinTree(subTree->rightChild);//遞歸建立右子樹 } else subTree = NULL; //封閉指向空子樹的指針 } int main(){ BinTreeNode cout<<“先序遍歷二叉樹結果：”; PreOrder_1(Tree); cout< cout<<“后序遍歷二叉樹結果：”; PostOrder_1(Tree);cout< cout<<“非遞歸中序遍歷二叉樹結果：”;InOrder_2(Tree);cout< 3、實驗程序運行截圖 實驗四 散列法查找和排序 一、目的和要求 1.用散列法實現(xiàn)順序查找，折半查找。 二、儀器、設備和材料 1.適合實驗要求的計算機系統(tǒng)。2.VＣ++編程平臺。 三、實驗步驟 和程序 1、順序查找 #include #define NULLKEY 0 typedef int KeyType; /* 假設關鍵字為整型 */ typedef struct { KeyType key;}RecordType;typedef RecordType HashTable[m];int hash(KeyType k)/*除留余數(shù)法構造哈希函數(shù)*/ { int h;h = k%m;return h;} int HashSearch(HashTable ht, KeyType K)/*哈希查找*/ { int h0;int i;int hi;h0=hash(K);if(ht[h0].key==NULLKEY) return(-1);else if(ht[h0].key==K) return(h0); else /* 用線性探測再散列解決沖突 */ { for(i=1;i<=m-1;i++) { hi=(h0+i)% m; if(ht[hi].key==NULLKEY) return(-1); else if(ht[hi].key==K) return(hi); } return(-1); } } void main(){ int i,j;int n;int p;int hj;int k;int result;HashTable ht;for(i=0;i ht[i].key = NULLKEY;printf(“請輸入哈希表的元素個數(shù):”);scanf(“%d”,&n);for(i=1;i<=n;i++){ printf(“請輸入第%d個元素:”,i); fflush(stdin); scanf(“%d”,&p); j = hash(p); if(ht[j].key == NULLKEY) ht[j].key = p; else { for(i=1;i<=m-1;i++) { hj=(j+i)% m; if(ht[hj].key==NULLKEY) { ht[j].key = p; } i = m; } } } } printf(“請輸入要查找的元素:”);fflush(stdin);scanf(“%d”,&k);result = HashSearch(ht,k);if(result ==-1)printf(“未找到!n”);else printf(“元素位置為%dn”,result);system(“pause”);運行結果如下： 2、折半查找 #include printf(“你輸入的數(shù)不正確，請重新輸入:n”); printf(“你想在多少個數(shù)中進行折半查找，請輸入(1--20):”); scanf(“%d”,&n);} printf(“請你輸入一個整數(shù)a[1]:”);scanf(“%d”,&a[1]);i=2;while(i<=n){ printf(“請你輸入一個整數(shù)a[%d]:”,i); scanf(“%d”,&a[i]); i++;} printf(“n輸出表列n”);for(i=1;i<=n;i++){ printf(“%6d”,a[i]);} printf(“n”);printf(“請你輸入要查找的數(shù):”);scanf(“%d”,&num);flag=1;top=n;bottom=1;mid=(top+bottom)/2;while(flag){ printf(“top=%d，bottom=%d，mid=%d,a[i]=%dn”,top,bottom,mid,mid,a[mid]);if((num>a[top])||(num loc=-1; flag=0;} else if(a[mid]==num){ loc=mid; printf(“找到數(shù) %6d的位置%2dn”,num,loc); break;} else if(a[mid]>num){ top=mid-1; mid=(top+bottom)/2;} else if(a[mid] bottom=mid+1; mid=(top+bottom)/2;} } if(loc==-1){ printf(“%d這個數(shù)在表列中沒有找到。n”,num);} } 運行結果如下： 北京郵電大學信息與通信工程學院 數(shù)據(jù)結構實驗報告 實驗名稱： 實驗二——圖 學生姓名： 佘晨陽 班 級： 2014211117 班內序號： 20 學 號： 2014210491 日 期： 2015年12月05日 1．實驗要求 根據(jù)圖的抽象數(shù)據(jù)類型的定義，使用鄰接矩陣或鄰接表實現(xiàn)一個圖。圖的基本功能： 1、圖的建立 2、圖的銷毀 3、深度優(yōu)先遍歷圖 4、廣度優(yōu)先遍歷圖 5、使用普里姆算法生成最小生成樹 6、使用克魯斯卡爾算法生成最小生成樹 7、求指定頂點到其他各頂點的最短路徑 8、其他：比如連通性判斷等自定義操作 編寫測試main()函數(shù)測試圖的正確性 2.程序分析 本實驗要求掌握圖基本操作的實現(xiàn)方法，了解最小生成樹的思想和相關概念，了解最短路徑的思想和相關概念，學習使用圖解決實際問題的能力。 2.1 存儲結構 存儲結構：1.不帶權值的無向圖鄰接矩陣 2.帶權值的無向圖鄰接矩陣 3.帶權值的有向圖鄰接矩陣 1．不帶權值的無向圖鄰接矩陣 第1頁 北京郵電大學信息與通信工程學院 2帶權值的無向圖鄰接矩陣.3.帶權值的有向圖鄰接矩陣 [備注]： 1.在使用打印元素、BFS、DFS 采用無權值的無向圖鄰接矩陣存儲方式 2.在使用PRIM、KRUSKAL、3.在使用最短路徑的算法時采用具有權值的有向圖鄰接矩陣存儲方式 2.2 關鍵算法分析 第2頁 北京郵電大學信息與通信工程學院 一．圖的鄰接矩陣構造函數(shù)： 1.關鍵算法： template //帶權值的圖的構造函數(shù) { int i, j, k, height;f s1, s2;vnum = n;arcnum = e;for(k = 0;k < n;k++){ vertex[k] = a[k];} //初始化頂點 for(k = 0;k for(i = 0;i < n;i++) { arc[k][i] =-1; if(i == k)arc[k][i] = 0; //初始化權值的大小 } visited[k] = 0;} cout << endl;for(k = 0;k //初始化邊 { cout << “請輸入線性鏈接節(jié)點:”; cin >> s1 >> s2 >> height; arc[convert(s1)][convert(s2)] = height; arc[convert(s2)][convert(s1)] = arc[convert(s1)][convert(s2)];//采用無向圖帶權值的鄰接矩陣 } cout << endl;cout << “所得鄰接矩陣為：” << endl; for(k = 0;k for(i = 0;i < n;i++) { if(arc[k][i] ==-1) cout << “∞” << “ ”; else cout << arc[k][i] << “ ”; //打印鄰接矩陣的格式 } cout << endl; } cout << endl 2.算法的時間復雜度 第3頁 北京郵電大學信息與通信工程學院 有構造可知，初始化時其時間復雜度：O(n2) 二．深度優(yōu)先便利DFS: 1.關鍵算法 ①從某頂點v出發(fā)并訪問 ②訪問v的第一個未訪問的鄰接點w，訪問w的第一個未訪問的鄰接點u，…… ③若當前頂點的所有鄰接點都被訪問過，則回溯，從上一級頂點的下一個未訪問過的頂點開始深度優(yōu)先遍歷 ④直到所有和v路徑相通的頂點都被訪問到； 2.代碼圖解： 深度優(yōu)先遍歷示意圖 3.代碼詳解： template for(int j = 0;j < vnum;j++) //連通圖 if((visited[j] == 0)&&(arc[v][j] >= 1))DFS(j);//當存在回路時，則連通深一層遍歷 } 4.時間復雜度 時間復雜度：O(n2) 空間復雜度：棧的深度O(n) 輔助空間O(n) 第4頁 北京郵電大學信息與通信工程學院 三．廣度遍歷BFS 1.關鍵算法 ①訪問頂點v ②依次訪問v的所有未被訪問的鄰接點v1,v2,v3… ③分別從v1,v2,v3…出發(fā)依次訪問它們未被訪問的鄰接點 ④反復①②③，直到所有和v路徑相通的頂點都被訪問到； 2.代碼圖解 3.代碼詳解 1.初始化隊列Q 2.訪問頂點v，visited[v]=1 3.while(隊列非空) 3.1 v=隊頭元素出隊 3.2 訪問隊頭元素的所有未訪問的鄰接點 4.時間復雜度 時間復雜度：O(n2) 空間復雜度：輔助空間O(n) 四.最小生成樹——普里姆算法 1,關鍵思路 一般情況下，假設n個頂點分成兩個集合：U(包含已落在生成樹上的結點)和V-U(尚未落在生成樹上的頂點)，則在所有連通U中頂點和V-U中頂點的邊中選取權值最小的邊。主數(shù)據(jù)結構： 鄰接矩陣 輔助數(shù)據(jù)結構： int adjvex[MAXSIZE];// U集中的頂點序號 第5頁 北京郵電大學信息與通信工程學院 int lowcost[MAXSIZE]; // U?(V-U)的最小權值邊 2.代碼圖解 第6頁 北京郵電大學信息與通信工程學院 第7頁 北京郵電大學信息與通信工程學院 3;代碼詳解 template //輔助數(shù)組存儲所有到的V0邊 { adjvex[i] = 0;lowcost[i] = arc[0][i]; } lowcost[0] = 0;for(int j = 1;j < vnum;j++) //循環(huán)n-1次 { int k = Mininum(lowcost); //求下一個頂點 cout << vertex[adjvex[k]] << “->” << vertex[k] << endl; lowcost[k] = 0; //U=U+{Vk} for(int j = 0;j < vnum;j++) //設置輔助數(shù)組 { if((lowcost[j]!= 0 && arc[k][j] < lowcost[j])) { lowcost[j] = arc[k][j]; adjvex[j] = k; } } 第8頁 北京郵電大學信息與通信工程學院 } } 4,時間復雜度： 時間復雜度O(n2)，適合稠密圖 五.最小生成樹----克魯斯卡爾算法 1,關鍵思路 先構造一個只含n個頂點的子圖SG，然后從權值最小的邊開始，若它的添加不使SG中產生回路，則在SG上加上這條邊，如此重復，直至加上n-1條邊為止。2.代碼圖解： 3.代碼詳解 template //最小生成樹—kruskal算法 { cout<<“Krusal算法結果為：”< int k = 0, j = 0; while(k < vnum-1){ int m = vedgelist[j].fromv, n = vedgelist[j].endv; int sn1 = vset[m]; int sn2 = vset[n]; //兩個頂點分屬 第9頁 北京郵電大學信息與通信工程學院 不同的集合 if(sn1!= sn2) { cout << vertex[m] << “->” << vertex[n] << endl; k++; for(int i = 0;i < vnum;i++) { if(vset[i] == sn2) vset[i] = sn1; //集合sn2全部改成sn1 } } j++;} } 4.時間復雜度 時間復雜度O(nlogn)，適合稀疏圖 六．最短路徑——Dijkstra算法 1.關鍵代碼 ? 按路徑長度遞增的次序產生源點到其余各頂點的最短路徑。? 1)設置集合s存儲已求得的最短路徑的頂點，? 2)初始狀態(tài)：s=源點v ? 3)疊代算法： ? 直接與v相連的最近頂點vi,加入s ? 從v經過vi可以到達的頂點中最短的，加入s …… 2.代碼圖解 第10頁 北京郵電大學信息與通信工程學院 3.代碼詳解 emplate //關于最短路徑的初始化 { int v=convert(x); for(int i = 0;i < vnum;i++) //初始化路徑和點 { s[i]=0; disk[i] = arc[v][i]; if(disk[i]!= maxs)path[i] = v; else path[i] =-1;} s[v] = 1;disk[v] = 0;path[v]=-1;for(int i = 0;i < vnum;i++) //反復經過從該點到其他點的路徑 { if((v = FindMin())==-1)continue; s[v] = 1; for(int j = 0;j < vnum;j++) if(!s[j] &&(disk[j]>arc[v][j] + disk[v])) { 第11頁 北京郵電大學信息與通信工程學院 disk[j] = arc[v][j] + disk[v]; path[j] = v; } } Print(); //打印路徑長度和遍歷 } 4.時間復雜度 時間復雜度為：n^2 七．判斷連通圖算法 template { cout<<“該圖為連通圖！*******輸入成功！”< return false; } else { cout<<“該圖不為連通圖！*******請重新輸入”< return true; } } 時間復雜度：n^2 3.程序運行結果 1.測試主函數(shù)流程： 第12頁 北京郵電大學信息與通信工程學院 函數(shù)流程圖： 1.輸入圖的連接邊并打印 構造下面所示圖的鄰接矩陣： 第13頁 北京郵電大學信息與通信工程學院 2.判斷圖連通是否成功 3.BFS DFS PRIM算法的實現(xiàn) 第14頁 北京郵電大學信息與通信工程學院 4.克魯斯卡爾算法實現(xiàn)過程 4.有向圖鄰接矩陣的構建 第15頁 北京郵電大學信息與通信工程學院 插入V0位置后打印距離并開始回溯 總結 1.調試時出現(xiàn)的問題及解決的方法 問題一：prim算法中 解決方法：調整循環(huán)條件，修正函數(shù)體注意有無Next的區(qū)別 第16頁 北京郵電大學信息與通信工程學院 問題二：BFS和DFS同時在一個類里作用時會輸出錯誤 解決方案：每次BFS/DFS使用時都把visited數(shù)組初始化一遍 問題三：在最短路徑，經常出現(xiàn)了停止輸入的情況 解決方法：改return為continue，并修改打印算法 2.心得體會 通過本次實驗，基本熟練掌握了c++基本語句，尤其對圖的結構及應用有了較深了解；調試代碼時盡量做到完成一個代碼段調試一次，可以最快檢測出錯誤所在；類的封裝和調用，類的共有成員和私有成員的設置。 3.下一步的改進 第一，設置增加圖節(jié)點和邊的函數(shù) 第二，實現(xiàn)圖形化輸出圖的路徑的功能 第三，主函數(shù)設計簡單，不要過于累贅 4.程序中出現(xiàn)的亮點 1)利用dfs算法衍生生成判斷是否為連通圖的連通算法 2)采用graph類實現(xiàn)所有圖的所有算法，所需的數(shù)據(jù)類型均在私有成員內，封裝 3)利用convert函數(shù)采取象意輸入，采用ABCD的節(jié)點輸入方式而并非轉化成01234再輸入。 4)BFS中采用c++標準庫的。 5)打印鄰接矩陣時，打印出非鏈接的∞符號和與自身路徑的0距離 6)判斷圖為非連通圖后，提示輸入錯誤，重新輸入圖元素 第17頁第二篇：數(shù)據(jù)結構實驗報告(報告+C語言源代碼)
第三篇：數(shù)據(jù)結構上機實驗--圖
第四篇：中南大學 數(shù)據(jù)結構實驗報告
第五篇：數(shù)據(jù)結構 實驗一 圖[推薦]
點擊咨詢 