山東建筑大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告

1、山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程設(shè)計(jì)說明書題 目： 基于逆鄰接表的有向圖基本操作的實(shí)現(xiàn)課 程：數(shù)據(jù)結(jié)構(gòu)院 （部）：計(jì)算機(jī)學(xué)院專 業(yè)：計(jì)科班 級(jí)：133學(xué)生姓名：潘含笑學(xué) 號(hào)：20131111092指導(dǎo)教師：李盛恩完成日期：2015.07.03山東建筑大學(xué)計(jì)算機(jī)學(xué)院課程設(shè)計(jì)說明書目 錄課程設(shè)計(jì)任務(wù)書I課程設(shè)計(jì)任務(wù)書II逆鄰接鏈表實(shí)現(xiàn)有向圖3一、問題描述3二、數(shù)據(jù)結(jié)構(gòu)3三、邏輯設(shè)計(jì)3四、編碼5五、測試數(shù)據(jù)14六、 測試情況16逆鄰接鏈表實(shí)現(xiàn)有向圖17一、問題描述17二、數(shù)據(jù)結(jié)構(gòu)17三、邏輯設(shè)計(jì)17四、編碼19五、測試數(shù)據(jù)27七、 測試情況29結(jié) 論30課程設(shè)計(jì)指導(dǎo)教師評(píng)語32山東建筑大學(xué)計(jì)算機(jī)

2、學(xué)院課程設(shè)計(jì)說明書山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目基于逆鄰接表的有向圖基本操作的實(shí)現(xiàn)已知技術(shù)參數(shù)和設(shè)計(jì)要求題目三、實(shí)現(xiàn)類NetWork，實(shí)現(xiàn)BFS、DFS、拓?fù)渑判?，并?shí)現(xiàn)采用逆鄰接表作為存儲(chǔ)結(jié)構(gòu)的有向圖，要繼承NetWork。逆鄰接表要使用STL提供的List和Vector等實(shí)現(xiàn)。設(shè)計(jì)內(nèi)容與步驟1、 設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)2、 設(shè)計(jì)算法3、 編寫程序，進(jìn)行調(diào)試4、 總結(jié)并進(jìn)行演示、講解設(shè)計(jì)工作計(jì)劃與進(jìn)度安排2015.6.172015.6.23，實(shí)現(xiàn)基類Network和有向圖Graph，實(shí)現(xiàn)逆鄰接鏈表的存儲(chǔ)結(jié)構(gòu)。2015.6.232015.7.1，編寫測試代碼。2015.7.120

3、15.7.3，改正一些錯(cuò)誤，完成實(shí)驗(yàn)。設(shè)計(jì)考核要求1、 考勤20%2、 課程設(shè)計(jì)說明書50%3、 成果展示30%指導(dǎo)教師（簽字）： 教研室主任（簽字）山東建筑大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院課程設(shè)計(jì)任務(wù)書設(shè)計(jì)題目雙向循環(huán)鏈表已知技術(shù)參數(shù)和設(shè)計(jì)要求實(shí)現(xiàn)雙向循環(huán)鏈表。設(shè)計(jì)內(nèi)容與步驟5、 設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)6、 設(shè)計(jì)算法7、 編寫程序，進(jìn)行調(diào)試8、 總結(jié)并進(jìn)行演示、講解設(shè)計(jì)工作計(jì)劃與進(jìn)度安排2015.4.222015.4.35，實(shí)現(xiàn)雙向循環(huán)鏈表2015.4.252015.4.29，編寫測試代碼。設(shè)計(jì)考核要求4、 考勤20%5、 課程設(shè)計(jì)說明書50%6、 成果展示30%指導(dǎo)教師（簽字）： 教研室主任（簽字）I山東建

4、筑大學(xué)計(jì)算機(jī)學(xué)院課程設(shè)計(jì)說明書逆鄰接鏈表實(shí)現(xiàn)有向圖215436一、問題描述12345611232345二、數(shù)據(jù)結(jié)構(gòu)三、邏輯設(shè)計(jì)1、總體思路先實(shí)現(xiàn)Network類，通過隊(duì)列實(shí)現(xiàn)BFS，通過堆棧實(shí)現(xiàn)DFS和拓?fù)渑判?。再?gòu)建Graph類，并繼承Network類實(shí)現(xiàn)以逆鄰接鏈表為存儲(chǔ)結(jié)構(gòu)的有向圖。2、模塊劃分（以圖示的方法給出各個(gè)函數(shù)的調(diào)用關(guān)系）Network類Initializepos虛函數(shù) Edges虛函數(shù)Begin虛函數(shù)BFS函數(shù)DFS函數(shù)Topological函數(shù)Deactivatepos虛函數(shù)Vertices虛函數(shù)Nextvertex虛函數(shù)Begin函數(shù)Out函數(shù)Deactivatepos函

5、數(shù)Initializepos函數(shù)Vertices函數(shù) Edges函數(shù)Nextvertex函數(shù)Graph類3、函數(shù)或類的具體定義和功能Network類：virtual int Begin(int i) = 0;/確定起始頂點(diǎn)virtual int Nextvertex(int i) = 0;/下一個(gè)頂點(diǎn)virtual int Edges()=0;/確定點(diǎn)virtual int Vertices()=0;/確定邊virtual void Initializepos(int i)=0;/讓迭代器等于鏈表的第i個(gè)頂點(diǎn)的第一個(gè)元素virtual void Deactivatepos(int i)=0;/

6、刪除迭代器指的元素void BFS(int v,int reach,int label,int a);/寬度遍歷void DFS(int v,int reach,int label,int a);/深度遍歷bool Topological(int v);/拓?fù)渑判騰irtual Network();/析構(gòu)函數(shù)Graph類：virtual Graph();/析構(gòu)函數(shù)int InDegree(int node);/入度int OutDegree(int node);/出度Graph& Add(int node1, int node2);/添加點(diǎn)Graph& Delete(int n

7、ode1, int node2);/刪除點(diǎn)int Begin(int i);/確定起始頂點(diǎn)int Nextvertex(int i);/下一個(gè)頂點(diǎn)int Edges() return e;/確定點(diǎn)int Vertices() return n;/確定邊void Initializepos(int i)pos=ali.begin(); /讓迭代器等于鏈表的第i個(gè)頂點(diǎn)的第一個(gè)元素void Deactivatepos(int i)ali.erase(pos);/刪除迭代器指的元素void Out();/輸出函數(shù)四、編碼/Network.h#include <iostream>#inclu

8、de<queue>#include<stack>#include <vector>using namespace std;class Network public:virtual int Begin(int i) = 0;virtual int Nextvertex(int i) = 0; virtual int Edges()=0; virtual int Vertices()=0; virtual void Initializepos(int i)=0;/讓迭代器等于鏈表的第i點(diǎn)的第一個(gè)元素 virtual void Deactivatepos(int

9、i)=0;/刪除迭代器指的元素void BFS(int v,int reach,int label,int a);/寬度遍歷void DFS(int v,int reach,int label,int a);/深度遍歷bool Topological(int v);/拓?fù)渑判?virtual Network();/Network.cpp#include "Network.h"void Network:BFS(int v,int reach,int label,int a)int n=Vertices(); /獲取n的值,有幾個(gè)頂點(diǎn)queue<int> Q; /創(chuàng)

10、建一個(gè)隊(duì)列int k=0; /定義一個(gè)k來使元素得到保存 reachv=label;/標(biāo)記點(diǎn) ak+=v;/用數(shù)組記錄BFS的遍歷順序 Q.push(v); /把一個(gè)元素加入隊(duì)列 while(!Q.empty() int x; x=Q.front(); /獲取隊(duì)列中的第一個(gè)元素 Q.pop(); /讓隊(duì)列中的第一個(gè)元素出隊(duì) for(int i=1;i<=n;i+) /尋找x的下一個(gè)節(jié)點(diǎn) int u=Begin(i); if(u=x)&&(!reachi)/因?yàn)槭悄驵徑渔湵?Q.push(i); reachi=label; ak+=i; /把標(biāo)記的元素放入遍歷數(shù)組 whil

11、e(u)/看后面是不是還有節(jié)點(diǎn) u=Nextvertex(i); if(u=x)&&(!reachi) Q.push(i); reachi=label; ak+=i; for(int i=v;i<n;i+) /輸出BFS的運(yùn)行結(jié)果 if(reachi=label) cout<<"執(zhí)行完BFS后第"<<i<<"個(gè)元素被標(biāo)記 "<<endl; else cout<<"執(zhí)行完BFS后第"<<i<<"個(gè)元素沒有被標(biāo)記 "

12、;<<endl; cout<<"從節(jié)點(diǎn)"<<v<<"開始BFS遍歷的順序是" for(int i=1;i<n;i+) /輸出BFS的遍歷順序 cout<<ai-1<<" " ; cout<<endl;void Network:DFS(int v,int reach,int label,int a)stack<int> S; /創(chuàng)建一個(gè)堆棧int n=Vertices(); /獲取n的值int k=0;S.push(v); /把元素v加

13、入堆棧 while(!S.empty() int x=S.top(); /獲取堆棧的棧頂元素 if(!reachx) /如果元素沒被標(biāo)記，就把元素標(biāo)記 reachx=label; ak+=x; S.pop(); /把堆棧的棧頂彈出 for(int i=1;i<=n;i+) /獲取節(jié)點(diǎn)的下一個(gè)元素 int u=Begin(i); if(u=x)&&(!reachi) S.push(i); /把元素加入堆棧 while(u) u=Nextvertex(i); if(u=x)&&(!reachi) S.push(i); else S.pop(); /如果被標(biāo)記元

14、素就彈出 for(int i=v;i<n;i+) /輸出DFS的運(yùn)行結(jié)果 if(reachi=label) cout<<"執(zhí)行完DFS后第"<<i<<"個(gè)元素被標(biāo)記 "<<endl; else cout<<"執(zhí)行完DFS后第"<<i<<"個(gè)元素沒有被標(biāo)記 "<<endl; cout<<"從節(jié)點(diǎn)1開始DFS遍歷的順序是" for(int i=1;i<n;i+) /輸出DFS的遍歷

15、順序 cout<<ai-1<<ends; ; cout<<endl;bool Network:Topological(int v)int n=Vertices(); /獲取n的值vector<int> a(n+1);stack<int> S; /創(chuàng)建一個(gè)堆棧for(int i=1;i<=n ;i+) /初始化數(shù)組a，使每個(gè)點(diǎn)的a等于0，用來記錄點(diǎn)的入度ai=0;for(int i=1;i<=n;i+) /遍歷整個(gè)鄰接鏈表，有入度的節(jié)點(diǎn)增加a的值 int x=Begin(i); while(x) ai+; x=Nextver

16、tex(i);/后面有元素，則入度加1 for( int i=1;i<=n;i+) /如果a=0，把元素加入堆棧if(ai=0) S.push(i);int k=1;while(!S.empty() int y; y=S.top(); /拿出第一個(gè)元素 S.pop(); vk+=y; /彈出獲取值的元素 for(int i=1;i<=n;i+) /遍歷整個(gè)鄰接鏈表，使有y的元素的入度減一 int u=Begin(i); if(u=y&&ai!=0) ai-; if(ai=0) S.push(i); /如果有入度等于0的元素，把元素加入堆棧 while(u) u=Ne

17、xtvertex(i); if(u=y&&ai!=0) ai-; if(ai=0) S.push(i); if(k=n+1)return true;elsereturn false;Network:Network() /Graph.h#include <iostream>#include <vector>#include <list>#include <algorithm>#include"Network.h"using namespace std;class Graph:public Networkpubli

18、c:Graph(int);virtual Graph();int InDegree(int node);int OutDegree(int node);Graph& Add(int node1, int node2);Graph& Delete(int node1, int node2); int Begin(int i); int Nextvertex(int i); int Edges() return e; int Vertices() return n; void Initializepos(int i)pos=ali.begin(); void Deactivatep

19、os(int i)ali.erase(pos);void Out();private:int n;int e;vector<list<int> > al;list<int>:iterator pos;/Graph.cpp#include "Graph.h"Graph:Graph(int num) e=0; /初始化邊，頂點(diǎn)n=num;al.resize(n+1); /開空間Graph:Graph() int Graph:InDegree(int node)return alnode.size();int Graph:OutDegree(i

20、nt node)list<int>:iterator q; /開鏈表的迭代器int i=0;for(int p=1;p<=n;p+)q=find(alp.begin(),alp.end(),node); if(q!=alp.end() i+; return i;Graph& Graph:Add(int node1, int node2)if(node1 < 1 | node1 > n | node2 < 1 | node2 > n) return *this;list<int>:iterator p;p = find(alnode2

21、.begin(), alnode2.end(), node1); /尋找有沒有node1if (p != alnode2.end() return *this; /如果有，返回elsealnode2.push_back(node1);e+;return *this;Graph& Graph:Delete(int node1, int node2)if(node1 < 1 | node1 > n | node2 < 1 | node2 > n) return *this;list<int>:iterator p;p = find(alnode2.beg

22、in(), alnode2.end(), node1);if (p =alnode2.end() return *this;elsealnode2.erase(p); /刪除要?jiǎng)h除的元素e-;return *this;void Graph:Out()for(int i = 1; i <=n; i+)list<int>:iterator p;cout<<"逆鄰接鏈表中第"<<i<<"行元素有"for(p = ali.begin(); p != ali.end(); p+) cout << *

23、p << ' 'cout <<endl;return;int Graph:Begin(int i) if(i<1|i>n) cout<<"無該點(diǎn)" Initializepos(i); if(pos=ali.end() return 0; else return *pos;int Graph:Nextvertex(int i) if(i<1|i>n) cout<<"無該點(diǎn)" pos+; if(pos!=ali.end() return *pos; else return

24、 0;五、測試數(shù)據(jù)#include"Graph.h"#include"Network.h"int b20;int b120;int c20;int a20;int a120;int main(void)int n=6;int label=2; Graph g(n); /創(chuàng)建對(duì)象 g.Add(1,4).Add(1,3).Add(2,4).Add(2,5).Add(3,4).Add(3,6).Add(4,6).Add(5,6); g.Out(); g.BFS(1,b,label,b1); cout<<endl; g.DFS(1,a,label,a

25、1); for(int i=1;i<=n;i+) cout<<"節(jié)點(diǎn)"<<i<<"的入度為：" cout<<g.InDegree(i)<<"," cout<<"節(jié)點(diǎn)"<<i<<"的出度為：" cout<<g.OutDegree(i)<<endl; g.Topological(c); /執(zhí)行拓?fù)渑判?for(int i=1;i<=n;i+) cout<<&

26、quot;拓?fù)渑判虻牡?quot;<<i<<"個(gè)元素是 "<<ci<<endl;cout<<endl;g.Delete(4,6);g.Out(); 6、 測試情況雙向循環(huán)鏈表1、 問題描述實(shí)現(xiàn)雙向循環(huán)鏈表。二、數(shù)據(jù)結(jié)構(gòu)a1a2a3a3 三、邏輯設(shè)計(jì)1、總體思路先構(gòu)造雙向循環(huán)鏈表的節(jié)點(diǎn)類，再逐步實(shí)現(xiàn)雙向循環(huán)鏈表的基本函數(shù)。2、模塊劃分（以圖示的方法給出各個(gè)函數(shù)的調(diào)用關(guān)系）DoubleCircularNode節(jié)點(diǎn)類DoubleCircular類DoubleCircular類DoubleCircular類DoubleCi

27、rcular類DoubleCircular類DoubleCircular類DoubleCircular類DoubleCircular類3、函數(shù)或類的具體定義和功能template<class T>class DoubleCircularpublic:DoubleCircular();/構(gòu)造函數(shù)DoubleCircular();/析構(gòu)函數(shù)bool IsEmpty() const;/判斷是否為空int length() const;/計(jì)算長度bool Find(int k,T& x) const;/判斷節(jié)點(diǎn)是否存在int Search(const T& x) const

28、;/查找節(jié)點(diǎn)DoubleCircular<T>& Insert(int k,const T& x);/插入節(jié)點(diǎn)DoubleCircular<T>& Delete(int k, T& x);/刪除節(jié)點(diǎn)void Output(ostream & out) const;/輸出函數(shù)private:DoubleCircularNode<T> *first;四、編碼/DoubleCircular.htemplate<class T>class DoubleCircularNode;#include<iostrea

29、m>using namespace std;template<class T>class DoubleCircularpublic:DoubleCircular();DoubleCircular();bool IsEmpty() const;int length() const;bool Find(int k,T& x) const;int Search(const T& x) const;DoubleCircular<T>& Insert(int k,const T& x);DoubleCircular<T>&

30、 Delete(int k, T& x);void Output(ostream & out) const;private:DoubleCircularNode<T> *first;template<class T>class DoubleCircularNode friend class DoubleCircular<T>private:T data;DoubleCircularNode<T> *left, *right;template<class T>class DoubleCircularIteratorpub

31、lic:T *Intialize(const DoubleCircular<T>& c)location = c.first->right;if(location)return &location->data;return 0;T *Next(const DoubleCircular<T>& c)if(!location) return 0;location =location->right;if (location->right!=c.first->right)return &location->da

32、ta;return 0;private:DoubleCircularNode<T> *location;class OutOfBounds public:OutOfBounds();virtual OutOfBounds();/DoubleCircular.cpp#include"DoubleCircular.h"#include<iostream>using namespace std;template <class T>DoubleCircular<T>:DoubleCircular()first = new Double

33、CircularNode<T>first->left = first;first->right = first;first=0;template <class T>DoubleCircular<T>:DoubleCircular()DoubleCircularNode<T> *next = first;/first->left->right = NULL;while(first)next = first->right;delete first;first = next;template <class T>

34、bool DoubleCircular<T>:IsEmpty() constif(first->right = first)return 1;return 0;template <class T>int DoubleCircular<T>:length() constint len = 0;DoubleCircularNode<T> *current = first->right;while(current != first)len+;current = current->right;return len;template &l

35、t;class T>DoubleCircular<T>& DoubleCircular<T>:Insert(int k, const T& x)int max=length();if(k < 0|k > max) throw OutOfBounds();DoubleCircularNode<T> *p = first;for(int index = 1; index < k && p; index+)p = p->right;if(!p) throw OutOfBounds();/插入Double

36、CircularNode<T> *y = new DoubleCircularNode<T>if(k)y->data = x;y->right = p->right;p->right = y;y->left = p;y->right->left = y;else/作為第一個(gè)元素插入y->right=y;y->left=y;return *this;template <class T>DoubleCircular<T>& DoubleCircular<T>:Delete(in

37、t k, T& x)int max = length();if(k < 1 | k > max)throw OutOfBounds();DoubleCircularNode<T> *q = first;for(int index=1; index <k-1 && q; index+)q = q->right;if(!q) throw OutOfBounds();q->left->right = q->right;q->right->left = q->left;x = q->data;dele

38、te q;return *this;template <class T>bool DoubleCircular<T>:Find(int k, T& x) constint max=length();if(k < 0) throw OutOfBounds();if(k > max) throw OutOfBounds();DoubleCircularNode<T> *current = first;int index = 1;/current的索引while(index < k-1 && current)current = current->right;index+;if(current)x = current->data;return true;return true;template <class T>int DoubleCircular<T>:Search(const T& x) constDoubleCircularNode<T> *current = first;/first->left->right =