第一篇:數據結構課程設計-全國鐵路交通咨詢模擬
數據庫課程設計
—全國鐵路咨詢系統
目錄
一.需求分析****************************************** 3
二.概要設計******************************************
三.儲存結構設計**************************************
四.詳細設計******************************************
五.用戶手冊******************************************
六.測試數據******************************************
七.心得體會****************************************** 8 11 17 18 26
一、需求分析
1、問題描述
由于不同目的的旅客對交通工具有不同的要求。例如,因公出差的旅客希望在旅途中 的時間盡可能短,出門旅游的游客則期望旅費盡可能省。編制一個全國城市間的交通咨詢程 序,為旅客提供兩種最優決策的交通咨詢。
根據鐵路的特征,數據的儲存需要使用圖的結構。每個城市之間有不同的車次,每個車次的始發站、路過車站和終點站都不一樣,所以兩個城市之間就有指向明確的邊,是一個有向圖;而由于車次的不一樣,所以發車時間,到站時間,價格等也會不一樣;所以每兩個點之間不止兩條邊,可能存在不同的多條邊。
2、功能需求
鐵路咨詢的對象是用戶,所以,需要一個對用戶友好的功能菜單,根據用戶可能需要的實際需求,功能菜單中可能會包括以下要點:
1:顯示所有車站信息
2: 顯示所有車次信息(包括時刻表)
3: 查詢車站信息
4: 查詢兩個城市之間的鐵路信息
5: 增加或刪除車站
6: 增加或刪除鐵路信息
7: 增加、刪除或修改時刻表、距離和價格
8:尋找兩城市間最省錢的一條路徑
9:尋找兩城市間最省時間的一條路徑 10:尋找兩城市間所有路徑(按費用從低到高排序輸出)
11:尋找兩城市間所有路徑(按所用時間從少到多排序輸出)
12:退出咨詢系統
圖的初始數據從文本中讀入,文本是老師給的標準數據。
3、輸入及輸出格式
(1):輸入格式:
A:圖的初始數據輸入
數據的初始化是需要從文本中讀入的,所以不需要有專門的文本輸入函數,只需要給出讀文本的函數input();使用input()函數從測試數據的三個文本中讀入數據,然后使用創建圖的函數CreateGraph()創建起整個圖。初始數據的讀入,分別是從station.txt中讀入每個城市站點的名稱的城市編號,從iinformation.txt中讀入每個城市間的鐵路信息,從railway.txt中讀入所有鐵路線的信息。
如:
以下從station.txt中節選部分
0 北京廣州石家莊鄭州武漢長沙
以下從information.txt中節選部分
出發城市編號 到達城市編號 車次 里程
費用
出發時刻
到達時刻
0
1000 287
62.5
0000
0246
0
1016 287
0060
0275
0
1001 137
23.5
0000
0117
0
1017 137
28.5
0060
0163
0
1002 1199 156.5 0000
1028
1008 1257 162.5 0000
1077
以下從railway.txt中節選部分
各條鐵路線上城市編號(此行可去掉)
京廣線 0 2 3 4 5 6 1
京九線 0 13 14 12
京滬線 0 8 9 10 11 7
隴海線 18 10 3 20 24 19
B:用戶要求輸入
用戶在使用本程序時,會要求用戶輸入各種數據,如城市編號id、抉擇選項y/n等;用戶只需要按照程序菜單的要求輸入即可。如城市編號id就是初始化數據(文本數據)中每個城市就有的編號,用戶在不知道城市編號之前先查看一下城市信息就可以清楚明了的知道城市id了。
(2):輸出格式
在系統的管理下,為了用戶的查詢方便,需要有多重輸出方式。如每條鐵路線上信息的輸出。這里面就包括了,在每條鐵路上所有車次信息,每個車次始發站信息、過站信息和終點站信息。
樣例如下:
蘭新線中有以下車次:
1005次列車運行情況:
出發城市
到達城市
車次
距離(km)出發時間
到達時間
費用(元)
蘭州
酒泉
1005
748
0:0
10:41
酒泉
烏魯木齊
1005
797
10:51 22:14
152.5
烏魯木齊
阿拉山口
1005
477
22:24
5:13
64.5
1013次列車運行情況:
出發城市
到達城市
車次
距離(km)出發時間
到達時間
費用(元)
阿拉山口
烏魯木齊
1013
477
0: 0
6:49
64.5
烏魯木齊
酒泉
1013
797
6:59
18:22
152.5
酒泉
蘭州
1013
748
18:32
5:13
對于每個城市信息的輸出,只需要輸出經過每個城市的鐵路新路即可,當然必須得輸出城市站點的id,方便用戶的查詢和管理
樣例如下:
城市編號
城市名稱
過站鐵路線
0
北京
京廣線
京九線
京滬線
廣州
京廣線
石家莊
京廣線
鄭州
京廣線
隴海線
武漢
京廣線
長沙
京廣線
株洲
京廣線
滬昆線
上海
京滬線
滬昆線
二、概要設計
1.數據特性分析
(1):整體結構分析
鐵路交通咨詢模擬系統管理的是全國的各個城市間的鐵路信息。對于整體的全
國鐵路信息來說,每一個城市站點就是一個頂點節點,城市與城市之間的每一個車
次信息就是一條有向邊。所有整個咨詢系統應該是一個有向圖結構。從A城市出發
到B城市,可能會有多個車次。
如下例:
出發城市
到達城市
車次
距離(km)出發時間
到達時間
費用(元)
北京
石家莊
1000
287
0: 0
4: 6
62.5
北京
石家莊
1016
287
1: 0
4:35
所以每兩個城市頂點之間就可能會有多條有向邊,所以這個圖也不會是 一個有
向簡單圖了。為了城市節點能夠動態的擴充和刪除不受影響,我對于頂點的儲存采
用鏈表結構不使用順序表結構,定義一個頂點鏈表類VertexList。這樣,雖然鏈表查
詢和其節點的刪除的時間復雜度受到了一定的影響,但這樣設計出來的鐵路網圖才
更具有一般性個實用性。對于查找的時間復雜度問題的解決,我在后面也會給出方案。
(2):城市頂點分析
對于每一城市來說,在全國的鐵路網中,它就是一個火車站節點。每一個火車,它都應該會有自己的名字,過站的鐵路線等。為了咨詢系統管理和維護的方便,在 文本數據中,我們就人為的給每一個城市都編上序號id,每一個不同id對應了一
個不同的城市節點。由于每個城市的id都是唯一的,所以在頂點的鏈表結構里面,完全可以定義一個哈希表haxi[n],對于haxi[i]來說,它存儲的就是id為i的城市
在內存中地址。這樣,頂點鏈表在哈希表的支持下,就能完美解決查找、添加、刪除的時間復雜度問題了。
在整個鐵路網中,每一個城市就是頂點,每一個頂點,就是應該有一個邊鏈表
用于儲存此城市能到達所有城市的各個不同車次的信息,也就是各個不同的邊。如:
出發城市編號 到達城市編號 車次 里程
費用
出發時刻
到達時刻
0
1000 287
62.5
0000
0246
0
1016 287
0060
0275
從上例我們可以看出,對于每個頂點的不同邊來說,每一個不同的邊就有一個獨有
的車次。所以這樣,對于邊的儲存,我們也可以采用哈希表結構。經觀察發現,每 一車次都大于1000,所以,哈希表的id=車次-1000;對于編號為a的城市節點haxi[k]
來說,它儲存的是為城市a中車次為:1000+k的一條邊,邊里面就有到達城市、出發和到達時間、費用、距離等等。
(3):邊數據分析
對于圖來講,邊就是一個邏輯結構,溝通頂點與頂點之間的關系。同時了,邊還有其物理特性。他需要儲存邊的權值等,它需要開辟儲存空間來存儲數
據。在鐵路網中,每兩個城市之間不同的車次信息就是一條不同的邊,所以,我需要把物理特性給單獨列出來,成為一個類LineInformation,用于表示邊
的物理信息。對于圖中抽象的邊,也需要定義一個類EdgeNode,用于溝通
圖中原本孤立的頂點,使之變成一個完整的圖
2.整體概要設計
前面,我提到了有頂點類station、頂點鏈表類VertexList、邊的物理類LineInformation和邊的邏輯類EdgeNode、火車線路類railway;對于整個完整的圖類來說,還有兩個主要的類沒有提及,那就是圖類RailwayNet和管理圖類的類management。當然對于圖中需要完成各個不同功能的時候,我還寫了許多的輔助類。如查找兩個車站之間所有路徑時需要用到的LinStack,當然還有LinStack的類的基石StackNode類。整個咨詢系統還有許多的結構體,這些結構體的功能我就不一一敘述了,詳細可見源代碼的注釋。下面我就列出各個類的關系圖
三.儲存結構設計
1、存儲結構的確定
數據結構的目的是有效組織和處理數據。為了有效組織和處理數據,先要分析多項式操作的特點和指針所占空間比例,然后確定最優的存儲結構。
1.鐵路網是由鐵路和火車站構成,每個火車站相當于一個定點,每新建一條鐵路就相當于新建定點之間的邊
2.車站之間可以任意到達,可直接相連,也可以間接相連,且怎么連接是不固定的。3.綜上所述,資源管理器的存儲結構采用樹形結構。
2、類的結構設計圖:
management類圖:
RailWay類圖:
VertexList類圖:
RailWay類圖:
LineInformation類圖:
EdgeNode結構圖:
Station類圖;
四、詳細設計
1.管理類management
class management{ private:
vector
void NextDisplay(EdgeNode* edge, LinStack
//私有的函數,以深度優先遍歷的方式尋找兩點之間的所有路徑
void DepthFirstSearchPath(vector
//私有函數,以Dijkastra算法尋找最節省時間的路徑
void ShortestCost(vector
void QuickSort(vector
};
VertexList & Vertex(){ return vertex;} vector
void InsertVertex(station* s);//在頂點v1和v2之間插入一條邊(邊的起點為v1,終點為v2)void InsertEdge(int v1, int v2, EdgeNode* & ed);//刪除編號為id的城市頂點 void DeleteVertex(int id);//刪除邊edge
void DeleteEdge(int v1, int v2);//創建一個鄰接表圖
void CreateGraph(RailwayNet & graph, vector
void display(RailwayNet & graph);//返回頂點v1和v2的第一條邊
EdgeNode* const GetFirstEdge(int v1, int v2);//獲取起點origin到終點terminal的最少費用
float GetShortestCost(int origin, int terminal, LineInformation & edge);//獲取邊路徑path中的用時
int GetPathTime(vector
float GetPathCost(vector
void GetAllPath(vector
//頂點鏈表類 class VertexList{ private:
station *head;//頭指針
int size;//鏈表的大小(元素的個數)
station* haxi[1000];//哈希表,內存有節點的地址(哈希表中的下標與對應城市節點的ID相等)public:
};VertexList();~VertexList();station* & GetHead(){ return head;} int & GetSize(){ return size;} //按照id從小到大的順序將city插入鏈表中 void insert(station* city);//刪除城市編號為id的節點 void Delete(int id);//根據城市的id獲取城市節點 station* GetVertex(int id);station** GetVertexHaxi(){ return haxi;} int IsVertexExist(int id);
4.頂點類
class station{ private:
int m_size;//邊鏈表的大小
EdgeNode* haxi[100];//以此車站為始發站的邊的哈希表(下標為:車次-1000)vector
station(string na, int i);//構造函數 station(const station & sta);//復制構造函數 void Delete();//刪除函數 //接口函數 station* prior;//指向上一個車站 station *next;//指向下一個車站 EdgeNode *head;//指向第一條邊節點 string m_name;int m_id;vector
};string & GetName(){ return m_name;} int & GetId(){ return m_id;} vector
LineInformation information;EdgeNode *next;//下一個邊結點 EdgeNode *prior;//上一個邊節點
};
6.邊物理類LineInformation
class LineInformation{ private:
int m_DepartId;//出發城市編號 int m_ArriveId;//到達城市編號 int m_TrainNumber;//車次 int m_distance;//車程 float m_cost;//費用 int m_DepartTime;//出發時間 int m_ArriveTime;//到達時間
//默認構造函數 int DepartId=0, int ArriveId=0,LineInformation(int DepartId = 0, int ArriveId = 0, int Train = 0, int distance =-1, //復制構造函數
LineInformation(const LineInformation & l);~LineInformation(){};LineInformation operator=(const LineInformation& e);//接口函數
int & GetDepartTime(){ return m_DepartTime;} int & GetArriveTime(){ return m_ArriveTime;} int & GetTrainNumber(){ return m_TrainNumber;} public: float cost = 0, int DepartTime =-1, int ArriveTime =-1);
};int & GetDepartId(){ return m_DepartId;} int & GetArriveId(){ return m_ArriveId;} int & GetDistance(){ return m_distance;} float & GetCost(){ return m_cost;}
7.火車線路類railway
class railway{ private:
};string m_name;//火車線名
vector
8.自定義棧類
template
};
template
//定義類LinStack
//數據元素 private: StackNode
//指針
//前視定義,否則友元無法定義
//模板類型為T
public: //構造函數1,用于構造頭結點
StackNode(StackNode
StackNode(const T& item, StackNode
};StackNode
//頭指針 //數據元素個數 //構造函數 public: LinStack(void);~LinStack(void);T Pop(void);
//析構函數 //入棧 //出棧 //取棧頂元素 //堆棧非空否 void Push(const T& item);T GetTop(void)const;
int NotEmpty(void)const;
bool IsInStack(T a);//判斷元素a是否在棧中 void Empty();//清空棧
int GetSize();//獲取棧中元素的個數 void display();//輸出棧中元素
五、用戶手冊
1.本程序運行在Windows操作系統下,VS2013,按F7編譯,F5運行。
2.在程序運行前有預設函數,最好選擇預設函數,然后進行測試。
3.在菜單中選擇你想進的功能,然后輸入前面的數字即可。
用戶菜單如下:
*****************************全國鐵路交通咨詢模擬**************************** 1: 顯示所有車站信息
2: 顯示所有車次信息(包括時刻表)
3: 查詢車站信息“
4: 查詢兩個城市之間的鐵路信息
5: 增加或刪除車站
6: 增加或刪除鐵路信息
7: 增加、刪除或修改時刻表、距離和價格
8: 尋找兩城市間最省錢的一條路徑
9: 尋找兩城市間最省時間的一條路徑
10:尋找兩城市間所有路徑(按費用從低到高排序輸出)
11:尋找兩城市間所有路徑(按所用時間從少到多排序輸出)
12: 退出咨詢系統”
*****************************************************************************"
六、測試數據
1.用戶菜單
在輸入指令一欄輸入你想要使用的功能的數字編號。如:輸入1 功能為:顯示所有車站信息
由于數據過多,這里只截取部分輸出
輸入指令:2 功能:查詢所有車次信息
數據量太大,也只截取部分輸出。
輸入指令:3 功能:查詢車站信息
車站信息有:
1.從此車站出發各個車次信息。2.從其他車站出發到達此車站的信息
輸入指令:4 功能:查詢兩個車站之間的信息
查詢的時候,是由先后順序的,先輸入的是出發城市,后輸入的到達城市
輸入指令:5 功能:增加或刪除車站
樣例1:增加成功
樣例2:增加失敗
錯誤原因:編號輸入錯誤 編號id為12:九龍
所以此編號已有城市占用,輸入錯誤
樣例3:刪除成功
現在可查詢廣州的信息
發現廣州此時已不存在,刪除成功
樣例4:刪除失敗
錯誤原因:id為31 的城市不存在
輸入指令:6 功能:增加或刪除鐵路信息
樣例1:增加失敗
失敗原因:id為1的城市已刪除,不能再城市1余城市6之間增加鐵路
樣例2:增加成功
此時新建鐵路狀態:還有鐵路線,沒有車次 注:想要鐵路線有火車運行,必須補充車次信息
樣例3:刪除成功
樣例4:刪除失敗
失敗原因:不存在從城市9到城市13的鐵路
輸入指令:7 功能:增加、刪除或修改時刻表、距離和價格
測試樣例:
可查詢修改后的價格 出發城市:6 株洲 到達城市:5 長沙
車次為:1022的信息中 價格:999 修改成功!
輸入指令:8 功能:尋找兩城市間最省錢的路勁
輸入指令:9 功能:尋找兩城市間最省時間的路勁
輸入指令:10 功能:尋找兩城市間所有路徑(按費用從低到高排序輸出)
數據過多,取前二十條顯示,我也只截取前一部分數據
輸入指令:11 功能:尋找兩城市間所有路徑(按所用時間從少到多排序輸出)
數據過多,取前二十條顯示,我也只截取前一部分數據
注:后面的測試時前面面修改后的結果,所以,計算的結果和初始化數據計算的結果可能會不一致,這是因為只是可能計算會用到我修改后的數據,所以存在不一致的問題。
七、心得體會
第二篇:數據結構課程設計校園導游咨詢
9、校園導游咨詢 問題描述:
設計一個校園導游程序,為來訪的客人提供各種信息查詢服務。基本要求:
⑴設計華東交通大學的校園平面圖,所含景點不少于10個。以圖中頂點表示校內各景點,⑵存放景點名稱、代號、簡介等信息;以邊表示路徑,存放路徑長度等相關信息。⑶為來訪客人提供圖中任意景點相關信息的查詢。⑷為來訪客人提供圖中任意景點的問路查詢,即查詢任意兩個景點之間的一條最短的簡單路徑。
#include
//最大頂點個數 #define INF 32767
//用32767表示∞ #include
//調用函數system改變字體顏色的頭文件
typedef int InfoType;#define MAXV 100
//最大頂點個數 //以下定義鄰接矩陣類型 typedef struct {
int no;
//頂點編號
InfoType info;
//頂點其他信息 } VertexType;
//頂點類型 typedef struct
//圖的定義 {
int edges[MAXV][MAXV];//鄰接矩陣
int vexnum,arcnum;
//頂點數,弧數
VertexType vexs[MAXV];//存放頂點信息 } MGraph;
void ecjtumap()//建立華東交通大學地圖
{ printf(“t|------------------------------|n”);printf(“t|
|n”);printf(“t|
|n”);printf(“t|
----------
|n”);printf(“t|
==============================| 國防生宿舍|
|n”);printf(“t|。
----------
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|
|南區四食堂|
----------
|n”);printf(“t|。
|南區禮堂 |
|n”);printf(“t|。
----------
|n”);printf(“t|。
。
|n”);printf(“t|。
。
|n”);printf(“t|。
--------。
|n”);printf(“t|
================| 校訓牌|。。。。
|n”);printf(“t|
=
--------
|n”);printf(“t|
=。
|n”);printf(“t|
=。
|n”);printf(“t|
--------
---------
|n”);printf(“t|----| 南區后門 |---------| 南區大門 |------------------------|n”);printf(“t|
--------
---------
|n”);printf(“t|
---------
|n”);printf(“t|-------------------------| 北區大門 |------------------------|n”);printf(“t|
--------
|n”);printf(“t|。
--------------
|n”);printf(“t|
===========================| 15棟綜合教學樓 |
|n”);printf(“t|
=
--------------
|n”);printf(“t|
=。
|n”);printf(“t|
=。
|n”);printf(“t|
=。
|n”);printf(“t|
=。
|n”);printf(“t|
=
----------
|n”);printf(“t|
===============================| 經管食堂 |
|n”);printf(“t|
=
----------
|n”);printf(“t|
=
=
|n”);printf(“t|
=
=
|n”);printf(“t|
-----------
=
|n”);printf(“t|
|軌道交通食堂|====================| 學生宿舍 |
|n”);printf(“t|
------------
|n”);printf(“t|
|n”);printf(“t|------------------------------|n”);printf(“n”);} void DispMat(MGraph g)
//輸出鄰接矩陣g,即輸出地圖各景點的圖的距離 { int i,j;for(i=0;i for(j=0;j if(g.edges[i][j]==INF) printf(“%3s”,“∞”);//這里分別用%3s和%3d控制輸出字符∞或數字寬度為3個字符 else printf(“%3d”,g.edges[i][j]);//這樣比較方便觀看景點的圖的鄰接矩陣g printf(“n”);} } void listmap()//建立 景點的相關信息的總瀏覽表 { printf(“t 華東交通大學景點一覽 nn”);printf(“t|--------|n”);printf(“t| 1:南區大門 |n”);printf(“t|--------|n”);printf(“t| 2:校訓牌 |n”);printf(“t|--------|n”);printf(“t| 3:圖書館 |n”);printf(“t|--------|n”);printf(“t| 4:南區一食堂 |n”);printf(“t|--------|n”);printf(“t| 5:孔目湖 |n”);printf(“t|--------|n”);printf(“t| 6:北區大門 |n”);printf(“t|--------|n”);printf(“t| 7:15棟教學樓 |n”);printf(“t|--------|n”);printf(“t| 8:北區食堂 |n”);printf(“t|--------|n”);printf(“t| 9:科技樓 |n”);printf(“t|--------|n”);printf(“t| 10:北區籃球場 |n”);printf(“t|--------|n”);} void introduce()//根據上面的瀏覽表,對應出相關信息 { int a=1;printf(“n”);printf(“請輸入要查看的景點:n”);printf(“輸入1~10的數字選擇景點,其他數字返回上一級n”);while(0 switch(a) {case 1:printf(“1:南區大門是進入華東交通大學南區的正門n”);break; case 2:printf(“2:校訓牌是激勵我們大學生積極向上n”);break; case 3:printf(“3:圖書館是給我們大學生豐富知識的海洋n”);break; case 4:printf(“4:南區一食堂是南區學生的吃飯的地方n”);break; case 5:printf(“5:孔目湖是華東交通大學最迷人的地方n”);break; case 6:printf(“6:北區大門是進入華東交通大學北區的正門n”);break; case 7:printf(“7:15棟教學樓是一棟綜合型的教學樓n”);break; case 8:printf(“8:北區食堂是北區學生吃飯的地方n”);break; case 9:printf(“9:科技樓是大學生上機做實驗的教學樓n”);break; case 10:printf(“10:北區籃球場是大學生鍛煉身體的地方n”);break; } } } void show_didian(int n)//根據算法求出的整型數,對應出地點//根據 xx算法求出的數字,轉化為文字描述 { switch(n){case 0:printf(“1.南區大門”);break;case 1:printf(“2.校訓牌”);break;case 2:printf(“3.圖書館 ”);break;case 3:printf(“4.南區一食堂”);break;case 4:printf(“5.孔目湖”);break;case 5:printf(“6.北區大門”);break;case 6:printf(“7.15棟教學樓”);break;case 7:printf(“8.北區食堂”);break;case 8:printf(“9.科技樓”);break;case 9:printf(“10.北區籃球場”);break;} } void ppath(int path[][MAXV],int i,int j)//求最短路徑經過的地點 { int k=path[i][j];if(k==-1)return;ppath(path,i,k);show_didian(k);printf(“->> ”);ppath(path,k,j);} void put_shortdistance(int x,int y,int A[][MAXV],int path[][MAXV],int n){ int i,j;for(i=0;i for(j=0;j if(A[i][j]==INF) { if(i!=j)printf(“從%d到%d沒有路徑n”,i,j); } else { if(i==x&&j==y) { printf(“最短路徑為:從--”); show_didian(i); printf(“--到--”); show_didian(j); printf(“--路徑為--:n”); show_didian(i);//輸出起點 printf(“->>”); ppath(path,i,j);//求最短路徑經過的中間路徑,若沒有則不輸出 show_didian(j);//輸出 終點 printf(“nt路徑長度為:%dn”,A[i][j]); } } } void shortdistance(MGraph g,int x,int y)//求最短路徑用的是弗洛伊德算法 { int A[MAXV][MAXV],path[MAXV][MAXV];//path為中間路徑不包括 起點 終點 int i,j,k,n=g.vexnum;for(i=0;i //給A數組置初值 for(j=0;j { A[i][j]=g.edges[i][j];path[i][j]=-1; } for(k=0;k //計算Ak { for(i=0;i for(j=0;j //這里的3個for循環 if(A[i][j]>(A[i][k]+A[k][j]))//所以時間復雜度O(n3) { A[i][j]=A[i][k]+A[k][j];path[i][j]=k; } } put_shortdistance(x,y,A,path,n);} void menu(MGraph g)//建立 菜單 頁面,可以無數次選擇菜單,當輸入5時退出系統 { int m=1,x=1,y=1;//m的菜單選擇的功能x,y分別表示從x到y的問路查詢 while(m!=5){ printf(“ttt|------------------------|n”); printf(“ttt|----------菜單----------|n”); printf(“ttt| 1:查看地圖 |n”); printf(“ttt| 2:地圖詳解 |n”); printf(“ttt| 3:景點一覽表 |n”); printf(“ttt| 4:問路查詢 |n”); printf(“ttt| 5:退出 |n”); printf(“ttt|------------------------|n”); printf(“請輸入1~5的數字n”); scanf(“%d”,&m); switch(m) {case 1:ecjtumap();break; case 2:listmap(); introduce();break; case 3:listmap(); introduce(); printf(“n”);break; case 4:listmap(); printf(“請輸入起點:”); scanf(“%d”,&x);x+=-1; printf(“請輸入終點:”); scanf(“%d”,&y);y+=-1; shortdistance(g,x,y);break; case 5:printf(“ttt感想使用本系統,歡迎下次繼續使用n”);break; } } } void main(){ system(“color 0a”);//輸出字體為綠色 int i,j;MGraph g;int A[MAXV][10]={ {INF, 1,INF,INF,INF, 1,INF,INF,INF,INF},{ 1,INF, 5, 6, 7,INF,INF,INF,INF,INF},{INF, 5,INF,INF, 2,INF,INF,INF,INF,INF},{INF, 6,INF,INF, 5,INF,INF,INF,INF,INF},{INF, 7, 2, 5,INF,INF,INF,INF,INF,INF},{ 1,INF,INF,INF,INF,INF, 3,INF, 5,INF},{INF,INF,INF,INF,INF, 3,INF, 2,INF,INF},{INF,INF,INF,INF,INF,INF, 2,INF, 8, 10},{INF,INF,INF,INF,INF, 5,INF, 8,INF, 2},{INF,INF,INF,INF,INF,INF,INF, 10, 2,INF}};g.vexnum=11;g.arcnum=11;for(i=0;i for(j=0;j g.edges[i][j]=A[i][j];printf(“n”);printf(“ttt華東交通大學導游咨詢系統n”);menu(g);//進入導游系統,執行菜單功能 } 數 據 結 構 課程設計報告 題 目: 一元多項式計算 專 業: 信息管理與信息系統 班 級: 2012級普本班 學 號: 201201011367 姓 名: 左帥帥 指導老師: 郝慎學 時 間: 一、課程設計題目分析 本課程設計要求利用C語言或C++編寫,本程序實現了一元多項式的加法、減法、乘法、除法運算等功能。 二、設計思路 本程序采用C語言來完成課程設計。 1、首先,利用順序存儲結構來構造兩個存儲多項式A(x)和 B(x)的結構。 2、然后把輸入,加,減,乘,除運算分成五個主要的模塊:實現多項式輸入模塊、實現加法的模塊、實現減法的模塊、實現乘法的模塊、實現除法的模塊。 3、然后各個模塊里面還要分成若干種情況來考慮并通過函數的嵌套調用來實現其功能,盡量減少程序運行時錯誤的出現。 4、最后編寫main()主函數以實現對多項式輸入輸出以及加、減、乘、除,調試程序并將不足的地方加以修改。 三、設計算法分析 1、相關函數說明: (1)定義數據結構類型為線性表的鏈式存儲結構類型變量 typedef struct Polynomial{} (2)其他功能函數 插入函數void Insert(Polyn p,Polyn h) 比較函數int compare(Polyn a,Polyn b) 建立一元多項式函數Polyn Create(Polyn head,int m) 求解并建立多項式a+b,Polyn Add(Polyn pa,Polyn pb) 求解并建立多項式a-b,Polyn Subtract(Polyn pa,Polyn pb)2 求解并建立多項式a*b,Polyn Multiply(Polyn pa,Polyn pb) 求解并建立多項式a/b,void Device(Polyn pa,Polyn pb) 輸出函數輸出多項式,void Print(Polyn P) 銷毀多項式函數釋放內存,void Destroy(Polyn p) 主函數,void main() 2、主程序的流程基函數調用說明(1)typedef struct Polynomial { float coef; int expn; struct Polynomial *next;} *Polyn,Polynomial; 在這個結構體變量中coef表示每一項前的系數,expn表示每一項的指數,polyn為結點指針類型,屬于抽象數據類型通常由用戶自行定義,Polynomial表示的是結構體中的數據對象名。 (2)當用戶輸入兩個一元多項式的系數和指數后,建立鏈表,存儲這兩個多項式,主要說明如下: Polyn CreatePolyn(Polyn head,int m)建立一個頭指針為head、項數為m的一元多項式 p=head=(Polyn)malloc(sizeof(struct Polynomial));為輸入的多項式申請足夠的存儲空間 p=(Polyn)malloc(sizeof(struct Polynomial));建立新結點以接收數據 Insert(p,head);調用Insert函數插入結點 這就建立一元多項式的關鍵步驟 (3)由于多項式的系數和指數都是隨即輸入的,所以根據要求需要對多項式按指數進行降冪排序。在這個程序模塊中,使用鏈表,根據對指數大小的比較,對各種情況進行處理,此處由于反復使用指針對各個結點進行定位,找到合適的位置再利用void Insert(Polyn p,Polyn h)進行插入操作。(4)加、減、乘、除、的算法實現: 在該程序中,最關鍵的一步是實現四則運算和輸出,由于加減算法原則是一樣,減法可通過系數為負的加法實現;對于乘除算法的大致流程都是:首先建立多項式a*b,a/b,然后使用鏈表存儲所求出的乘積,商和余數。這就實現了多項式計算模塊的主要功能。 (5)另一個子函數是輸出函數 PrintPolyn(); 輸出最終的結果,算法是將最后計算合并的鏈表逐個結點依次輸出,便得到整鏈表,也就是最后的計算式計算結果。由于考慮各個結點的指數情況不同,分別進行了判斷處理。 四、程序新點 通過多次寫程序,發現在程序在控制臺運行時總是黑色的,本次寫程序就想著改變一下,于是經過查資料利用system(“Color E0”);可以函數解決,這里“E0,”E是控制臺背景顏色,0是控制臺輸出字體顏色。 五、設計中遇到的問題及解決辦法 首先是,由于此次課程設計里使用指針使用比較多,自己在指針多的時候易腦子混亂出錯,對于此問題我是采取比較笨的辦法在稿紙上寫明白后開始進行 4 代碼編寫。 其次是,在寫除法模塊時比較復雜,自己通過查資料最后成功寫出除法模塊功能。 最后是,前期分析不足開始急于寫代碼,中途出現各種問題,算是給自己以后設計時的一個經驗吧。 六、測試(程序截圖) 1.數據輸入及主菜單 2.加法和減法模塊 3.乘法和除法模塊 七、總結 通過本次應用C語言設計一元多項式基本計算程序,使我更加鞏固了C語言程序設計的知識,以前對指針這一點使用是比較模糊,現在通過此次課程設計對指針理解的比較深刻了。而且對于數據結構的相關算法和函數的調用方面知識的加深。本次的課程設計,一方面提高了自己獨立思考處理問題的能力;另一方面使自己再設計開發程序方面有了一定的小經驗和想法,對自己以后學習其他語言程序設計奠定了一定的基礎。 八、指導老師評語及成績 附錄:(課程設計代碼) #include float coef;6 int expn; struct Polynomial *next;} *Polyn,Polynomial; //Polyn為結點指針類型 void Insert(Polyn p,Polyn h){ if(p->coef==0)free(p); //系數為0的話釋放結點 else { Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn { q1=q2;q2=q2->next;} if(q2&&p->expn==q2->expn)//將指數相同相合并 { q2->coef+=p->coef; free(p); if(!q2->coef)//系數為0的話釋放結點 { q1->next=q2->next;free(q2);} } else { p->next=q2;q1->next=p; }//指數為新時將結點插入 } 7 } //建立一個頭指針為head、項數為m的一元多項式 Polyn Create(Polyn head,int m){ int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial)); head->next=NULL; for(i=0;i { p=(Polyn)malloc(sizeof(struct Polynomial));//建立新結點以接收數據 printf(“請輸入第%d項的系數與指數:”,i+1); scanf(“%f %d”,&p->coef,&p->expn); Insert(p,head); //調用Insert函數插入結點 } return head;} //銷毀多項式p void Destroy(Polyn p){ Polyn q1,q2; q1=p->next;8 q2=q1->next; while(q1->next) { free(q1); q1=q2;//指針后移 q2=q2->next; } } //輸出多項式p int Print(Polyn P){ Polyn q=P->next; int flag=1;//項數計數器 if(!q)//若多項式為空,輸出0 { putchar('0'); printf(“n”); return; } while(q) { if(q->coef>0&&flag!=1)putchar('+');//系數大于0且不是第一項 9 if(q->coef!=1&&q->coef!=-1)//系數非1或-1的普通情況 { printf(“%g”,q->coef); if(q->expn==1)putchar('X'); else if(q->expn)printf(“X^%d”,q->expn); } else { if(q->coef==1){ if(!q->expn)putchar('1'); else if(q->expn==1)putchar('X'); else printf(“X^%d”,q->expn);} if(q->coef==-1){ if(!q->expn)printf(“-1”); else if(q->expn==1)printf(“-X”); else printf(“-X^%d”,q->expn);} } q=q->next; flag++; } printf(“n”);} int compare(Polyn a,Polyn b){ if(a&&b) { if(!b||a->expn>b->expn)return 1; else if(!a||a->expn else return 0; } else if(!a&&b)return-1;//a多項式已空,但b多項式非空 else return 1;//b多項式已空,但a多項式非空 } //求解并建立多項式a+b,返回其頭指針 Polyn Add(Polyn pa,Polyn pb){ Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點 11 hc->next=NULL; headc=hc; while(qa||qb){ qc=(Polyn)malloc(sizeof(struct Polynomial)); switch(compare(qa,qb)) { case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; case-1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break;12 } if(qc->coef!=0) { qc->next=hc->next; hc->next=qc; hc=qc; } else free(qc);//當相加系數為0時,釋放該結點 } return headc;} //求解并建立多項式a-b,返回其頭指針 Polyn Subtract(Polyn pa,Polyn pb){ Polyn h=pb; Polyn p=pb->next; Polyn pd; while(p)//將pb的系數取反 { p->coef*=-1;p=p->next;} pd=Add(pa,h); for(p=h->next;p;p=p->next) //恢復pb的系數 p->coef*=-1;13 return pd;} //求解并建立多項式a*b,返回其頭指針 Polyn Multiply(Polyn pa,Polyn pb){ Polyn hf,pf; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點 hf->next=NULL; for(;qa;qa=qa->next) { for(qb=pb->next;qb;qb=qb->next) { pf=(Polyn)malloc(sizeof(struct Polynomial)); pf->coef=qa->coef*qb->coef; pf->expn=qa->expn+qb->expn; Insert(pf,hf);//調用Insert函數以合并指數相同的項 } } return hf;} //求解并建立多項式a/b,返回其頭指針 void Device(Polyn pa,Polyn pb){ Polyn hf,pf,temp1,temp2; Polyn qa=pa->next; Polyn qb=pb->next; hf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點,存儲商 hf->next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點,存儲余數 pf->next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial)); temp1->next=NULL; temp2=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next=NULL; temp1=Add(temp1,pa); while(qa!=NULL&&qa->expn>=qb->expn) { temp2->next=(Polyn)malloc(sizeof(struct Polynomial)); temp2->next->coef=(qa->coef)/(qb->coef); temp2->next->expn=(qa->expn)-(qb->expn); Insert(temp2->next,hf); pa=Subtract(pa,Multiply(pb,temp2));15 qa=pa->next; temp2->next=NULL; } pf=Subtract(temp1,Multiply(hf,pb)); pb=temp1; printf(“商是:”); Print(hf); printf(“余數是:”); Print(pf);} void main(){ int choose=1;int m,n,flag=0;system(“Color E0”);Polyn pa=0,pb=0,pc,pd,pf;//定義各式的頭指針,pa與pb在使用前付初值NULL printf(“請輸入A(x)的項數:”);scanf(“%d”,&m);printf(“n”);pa=Create(pa,m);//建立多項式A printf(“n”);printf(“請輸入B(x)的項數:”);16 scanf(“%d”,&n);printf(“n”);pb=Create(pb,n);//建立多項式B printf(“n”);printf(“**********************************************n”);printf(“* 多項式操作菜單 printf(”**********************************************n“);printf(”tt 1.輸出操作n“);printf(”tt 2.加法操作n“);printf(”tt 3.減法操作n“);printf(”tt 4.乘法操作n“);printf(”tt 5.除法操作n“);printf(”tt 6.退出操作n“);printf(”**********************************************n“);while(choose){ printf(”執行操作:“); scanf(”%d“,&flag); switch(flag) { case 1: printf(”多項式A(x):“);Print(pa);*n”); printf(“多項式B(x):”);Print(pb); break; case 2: pc=Add(pa,pb); printf(“多項式A(x)+B(x):”);Print(pc); Destroy(pc);break; case 3: pd=Subtract(pa,pb); printf(“多項式A(x)-B(x):”);Print(pd); Destroy(pd);break; case 4: pf=Multiply(pa,pb); printf(“多項式A(x)*B(x):”); Print(pf); Destroy(pf); break; case 5: Device(pa,pb);18 break; case 6: exit(0); break; } } Destroy(pa); Destroy(pb);} 數據結構課程設計 1.赫夫曼編碼器 設計一個利用赫夫曼算法的編碼和譯碼系統,重復地顯示并處理以下項目,直到選擇退出為止。要求: 1)將權值數據存放在數據文件(文件名為data.txt,位于執行程序的當前目錄中) 2)初始化:鍵盤輸入字符集大小26、26個字符和26個權值(統計一篇英文文章中26個字母),建立哈夫曼樹; 3)編碼:利用建好的哈夫曼樹生成哈夫曼編碼; 4)輸出編碼(首先實現屏幕輸出,然后實現文件輸出); 5)界面優化設計。 代碼如下: #include typedef struct HTNode //結構體 { int Weight; char ch;int Parent,Lchild,Rchild;}HTNode;typedef char * * HCode; void Save(int n,HTNode *HT) //把權值保存到文件 { FILE * fp; int i; if((fp=fopen(“data.txt”,“wb”))==NULL) { printf(“cannot open filen”); return; } for(i=0;i if(fwrite(&HT[i].Weight,sizeof(struct HTNode),1,fp)!=1) printf(“file write errorn”); fclose(fp); system(“cls”); printf(“保存成功!”); } void Create_H(int n,int m,HTNode *HT) //建立赫夫曼樹,進行編碼 { int w,k,j;char c;for(k=1;k<=m;k++){ if(k<=n) { printf(“n請輸入權值和字符(用空格隔開): ”); scanf(“%d”,&w); scanf(“ %c”,&c);HT[k].ch=c; HT[k].Weight=w; } else HT[k].Weight=0; HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0;} int p1,p2,w1,w2; for(k=n+1;k<=m;k++){ p1=0;p2=0; w1=32767;w2=32767; for(j=1;j<=k-1;j++) { if(HT[j].Parent==0) { if(HT[j].Weight { w2=w1;p2=p1; w1=HT[j].Weight; p1=j; } else if(HT[j].Weight { w2=HT[j].Weight; p2=j; } } } HT[k].Lchild=p1;HT[k].Rchild=p2;HT[k].Weight=HT[p1].Weight+HT[p2].Weight; HT[p1].Parent=k;HT[p2].Parent=k; } printf(“輸入成功!”);} void Coding_H(int n,HTNode *HT) //對結點進行譯碼 { int k,sp,fp,p;char *cd;HCode HC; HC=(HCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char));cd[n-1]='
主站蜘蛛池模板:
中文字幕日韩人妻在线视频|
国产精品高潮呻吟av久久软件|
裸体丰满白嫩大尺度尤物|
国产欧美日韩国产高清|
久久精品久久久久观看99水蜜桃|
av无码国产在线看免费网站|
无码人妻精品一区二区蜜桃网站|
成年日韩片av在线网站|
顶级欧美熟妇高潮xxxxx|
四虎国产精品免费久久久|
精品国产乱码久久久久久影片|
久青草久青草视频在线观看|
日韩免费一区二区三区高清|
国色精品卡一卡2卡3卡4卡在线|
亚洲精品无码视频|
国产日韩一区二区三免费高清|
国产成熟女人性满足视频|
激情综合色五月丁香六月亚洲|
国精产品一区一区三区有限公司|
亚洲色一区二区三区四区|
青青草无码精品伊人久久蜜臀|
欧美午夜一区二区福利视频|
免费无码va一区二区三区|
日韩欧美偷拍高跟鞋精品一区|
亚洲v欧美v国产v在线观看|
av无码久久久久不卡蜜桃|
亚洲精品一区国产精品|
国产精品久久久久久52avav|
精品亚洲国产成人a片app|
国内精品国产成人国产三级|
18禁成人黄网站免费观看久久|
四川丰满妇女毛片四川话|
最近的中文字幕在线看视频|
9 9久热re在线精品视频|
中文字幕一区二区人妻电影|
国产精品自产拍高潮在线观看|
午夜精品一区二区三区免费视频|
久久久久亚洲av无码网站|
一区二区国产精品精华液|
日韩欧美亚洲一区swag|
人人妻人人澡人人爽曰本|
第三篇:2012數據結構課程設計
第四篇:數據結構課程設計