算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計散列表的設(shè)計與實現(xiàn)教學計劃編制問題

1、* 實踐教學實踐教學 * 蘭州理工大學蘭州理工大學 計算機與通信學院 2015 年秋季學期 算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計課程設(shè)計 題 目: 散列表的設(shè)計與實現(xiàn) 教學計劃編制問題 專業(yè)班級：軟件工程二班 姓 名： 學 號： 指導教師： 成 績： 目目 錄錄 摘要摘要.3 一一. . 散列表的設(shè)計與實現(xiàn)散列表的設(shè)計與實現(xiàn) 1.采用類語言定義相關(guān)的數(shù)據(jù)類型.4 2. 算法設(shè)計.4 3.函數(shù)的調(diào)用關(guān)系圖.7 4.調(diào)試分析.8 6.源程序（帶注釋）.11 二教學計劃編制問題二教學計劃編制問題 1.采用類語言定義相關(guān)的數(shù)據(jù)類型.18 2.算法設(shè)計.19 3. 函數(shù)的調(diào)用關(guān)系圖.21 5. 測試結(jié)果

2、.22 6.源程序（帶注釋）.23 總結(jié).31 致致 謝謝.32 摘要摘要 1.1. 散列表的設(shè)計與實現(xiàn)散列表的設(shè)計與實現(xiàn) (1)(1)查找并顯示給定電話號碼的記錄查找并顯示給定電話號碼的記錄 (2)(2) 查找并顯示給定用戶名的記錄查找并顯示給定用戶名的記錄 (3)(3) 用散列表實現(xiàn)電話號碼查找系統(tǒng)用散列表實現(xiàn)電話號碼查找系統(tǒng) (4)(4) 以電話號碼和用戶名為關(guān)鍵字建立散列表以電話號碼和用戶名為關(guān)鍵字建立散列表 關(guān)鍵字：電話號碼關(guān)鍵字：電話號碼 用戶名用戶名 地址地址 查找查找 2.2.教學計劃編制問題教學計劃編制問題 （1)1)輸入?yún)?shù)：學期總數(shù)，一學期的學分上限，每門課的課程號輸入?yún)?/p>

3、數(shù)：學期總數(shù)，一學期的學分上限，每門課的課程號 （2)2)輸出參數(shù)：輸出提示信息輸出參數(shù)：輸出提示信息 （3)3)闡明了如何搞好教學管理，從而為提高教學質(zhì)量提供保證闡明了如何搞好教學管理，從而為提高教學質(zhì)量提供保證 （4)4)重視教學計劃的改革修訂工作，以確保教育教學質(zhì)量，提高教育教學水平。重視教學計劃的改革修訂工作，以確保教育教學質(zhì)量，提高教育教學水平。 （5)5)明確培養(yǎng)目標明確培養(yǎng)目標, ,注重學科設(shè)置的整體性、統(tǒng)一性和靈活性、全面性注重學科設(shè)置的整體性、統(tǒng)一性和靈活性、全面性, ,學分制學分制 改革有機結(jié)合改革有機結(jié)合 關(guān)鍵字：學期關(guān)鍵字：學期 學分學分 課程號課程號 教學計劃教學計劃

4、 管理管理 一一散列表的設(shè)計與實現(xiàn)散列表的設(shè)計與實現(xiàn)。設(shè)計散列表實現(xiàn)電話號碼查找系統(tǒng)?；疽?求： (1)設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址； (2) 從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立散列表； (3)采用雙散列法解決沖突； (4)查找并顯示給定電話號碼的記錄； (5) 查找并顯示給定用戶名的記錄。 1.1.采用類語言定義相關(guān)的數(shù)據(jù)類型采用類語言定義相關(guān)的數(shù)據(jù)類型 typedef int status; typedef char namax_size; typedef struct/記錄 na name; na tel; na add; record; typed

5、ef struct/哈希表 record *elemhashsize; /數(shù)據(jù)元素存儲基址 int count; /當前數(shù)據(jù)元素個數(shù) int size; /當前容量 hashtable 2.2.算法設(shè)計算法設(shè)計 初始化散列表算法： void inithashtable(hashtable ht,hashtable2 ht2) for(int i=0;ihashmaxsize;i+) strcpy(hti.hashname,0);/將哈希表 1 初始化為空 strcpy(ht2i.hashnum,0);/將哈希表 2 初始化為空 哈希函數(shù)算法： int hash1(na str)/哈希函數(shù) lo

6、ng n; int m; n=fold(str);/先將用戶名進行折疊處理 m=n%hashsize; /折疊處理后的數(shù)，用除留余數(shù)法構(gòu)造哈希 函數(shù) return m; /并返回模值 int hash2(na str)/哈希函數(shù) long n; int m; n = atoi(str);/把字符串轉(zhuǎn)換成整型數(shù). m=n%hashsize; /用除留余數(shù)法構(gòu)造哈希函數(shù) return m; /并返回模值 整體散列算法： void sanlie(pnode temp) int i=0,j=0; while(strcmp(,0)!=0) j+; /計算當前表中 name 元素的個數(shù)

7、 while(ij)/該循環(huán)將各元素得到哈希地址后，將元素存儲到相應的哈希表中 hash1(); while(strlen(hashaddsnamekey.hashname) key=(key+1)%m;/線形探測法處理沖突 strcpy(hashaddsnamekey.hashname,); /將作為關(guān)鍵字的姓名存入哈希表 hash2(tempi.number); while(strlen(hashaddsnumkey2.hashnum) key2=(key2+1)%m;/線形探測法處理沖突 strcpy(hashaddsnumkey2.hashnum

8、,tempi.number); /將作為關(guān)鍵字的電話號碼存入哈希表 i+; 輸入各個記錄信息算法 void inputnode() /提示用戶輸入信息的同時將信息寫入文件 int i=1; char yn; pnode temp; openfile(1);/調(diào)用”打開文件”函數(shù) while(1) printf( 請輸入第%d個姓名:,i); scanf(%s,); printf( 請輸入第%d個電話號碼:,i); scanf(%s,temp.number); printf( 請輸入第%d個地址:,i); scanf(%s,temp.add); fprintf(fp,%15s

9、%15s %30sn,,temp.number,temp.add); printf( 是否繼續(xù)添加( y 繼續(xù) )?t); scanf(%s, if(yn!=y/當鍵入 y 或 y 時繼續(xù)輸入 i+; ; fclose(fp); 顯示記錄算法 void display() int i=0,j=1; pnode a; openfile(2);/以寫方式調(diào)用打開文件函數(shù) printf(n); printf( - - - - - - - - - - - - - - - - - - - - - - -n); printf( 序號 姓名 電話號碼 地址 nn); while(!feof

10、(fp)/當文件指針沒有指向文件末尾時循環(huán) fscanf(fp,%s%s%s, printf( %2dt%-15s%-15s %- 30sn,j+,,a.number,a.add); printf(nn); fclose(fp);/關(guān)閉文件 依靠散列的查找算法 int search1(char name15) /*關(guān)鍵字為姓名*/ hash1(name);/調(diào)用哈希函數(shù)求取哈希地址下標 while(strlen(hashaddsnamekey.hashname)!=0) if(strcmp(hashaddsnamekey.hashname,name)=0) return 1;/如果

11、輸入的關(guān)鍵字與哈希表中的關(guān)鍵字相等返回 1 else key=(key+1)%m;/*線性探測法處理沖突在下一位繼續(xù)查找 return -1;/如果未找到返回-1 3.3.函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖 4 4. .調(diào)試分析調(diào)試分析 a a、調(diào)試中遇到的問題及對問題的解決方法調(diào)試中遇到的問題及對問題的解決方法 在編寫算法時，遇到文件的具體操作，在從文件中讀取整條數(shù)據(jù)后，無法 直接與其他算法相關(guān)聯(lián)。 while(!feof(fp) fgets(temp,100,fp); for(j=0,i=0;j15;j+) if(tempj!= ) t1i=tempj;i+; t1i=0; for(j=16

12、,i=0;j31;j+) if(tempj!= ) t2i=tempj;i+; t2i=0; for(j=31,i=0;j63;j+) if(tempj!= ) t3i=tempj;i+; t3i=0; strcpy(,t1); strcpy(tempobjk.number,t2); strcpy(tempobjk.add,t3); k+; fclose(fp); 經(jīng)過查閱書籍及網(wǎng)絡(luò)資料，采取以上的方法解決問題 ，將從文件中讀取出 的一整行數(shù)據(jù)，經(jīng)過拆分后，將各段數(shù)據(jù)分別存入結(jié)構(gòu)體中的各個元素中 去，問題得以解決。 b b、算法的時間復雜度和空間復雜度算法的時間復雜度

13、和空間復雜度 空間復雜度 數(shù)據(jù)結(jié)構(gòu)定義 5% 散列部分 5% 顯示函數(shù) 5%查找部分5% 添加部分 10% 刪除部分 10% 處理函數(shù)30% 輸入函數(shù)部分 10% 主函數(shù) 10% 其他占：10% 時間復雜度 散列函數(shù)時, 輸入信息函數(shù), 顯示函數(shù),查找函數(shù)時間復雜度 o(n) 主函數(shù)，轉(zhuǎn)換函數(shù)時間復雜度 o(n2); 5.5.測試結(jié)果測試結(jié)果 （1）、程序初始運行結(jié)果：）、程序初始運行結(jié)果： （2）新建通訊錄：）新建通訊錄： （3）讀取用戶信息讀取用戶信息 （4）解決沖突解決沖突 （5）查找（號碼查找（號碼 用戶名用戶名 ） 6.6.源程序（帶注釋）源程序（帶注釋） typedef int s

14、tatus; typedef char namax_size; typedef struct/記錄 na name; na tel; na add; record; typedef struct/哈希表 record *elemhashsize; /數(shù)據(jù)元素存儲基址 int count; /當前數(shù)據(jù)元素個數(shù) int size; /當前容量 hashtable; status eq(na x,na y)/關(guān)鍵字比較，相等返回 success；否則返回 unsuccess if(strcmp(x,y)=0) return success; else return unsuccess; status

15、 num_ber; /記錄的個數(shù) void getin(record* a)/鍵盤輸入各人的信息 printf(輸入要添加的個數(shù)：n); scanf(%d, int i; for(i=0;inum_ber;i+) printf(請輸入第%d 個記錄的用戶名:n,i+1); scanf(%s,); printf(請輸入%d 個記錄的電話號碼:n,i+1); scanf(%s,ai.tel); printf(請輸入第%d 個記錄的地址:n,i+1); scanf(%s,ai.add); /gets(str2);? void showinformation(record* a)/顯示輸

16、入的用戶信息 int i; for( i=0;inum_ber;i+) printf(n 第%d 個用戶信息:n 姓 名：%sn 電話號碼：%sn 聯(lián)系地址：%sn,i+1,ai. name,ai.tel,ai.add); void cls(record* a) printf(*); system(cls); long fold(na s)/人名的折疊處理 char *p; long sum=0; na ss; strcpy(ss,s);/復制字符串，不改變原字符串的大小寫 strupr(ss);/將字符串 ss 轉(zhuǎn)換為大寫形式 p=ss; while(*p!=0) sum+=*p+; pri

17、ntf(nsum=%d,sum); return sum; int hash1(na str)/哈希函數(shù) long n; int m; n=fold(str);/先將用戶名進行折疊處理 m=n%hashsize; /折疊處理后的數(shù)，用除留余數(shù)法構(gòu)造哈希函數(shù) return m; /并返回模值 int hash2(na str)/哈希函數(shù) long n; int m; n = atoi(str);/把字符串轉(zhuǎn)換成整型數(shù). m=n%hashsize; /用除留余數(shù)法構(gòu)造哈希函數(shù) return m; /并返回模值 status collision(int p,int i=c/2+1; while(i=

18、0) return q; else i=c/2+1; else q=(p-i*i)%hashsize; c+; if(q=0) return q; else i=c/2+1; return unsuccess; void bengettime(); void createhash1(hashtable* h,record* a)/建表，以人的姓名為關(guān)鍵字，建立相應的散列 表 /若哈希地址沖突，進行沖突處理 bengettime(); int i,p=-1,c,pp; for(i=0;ielempp!=null) pp=collision(p,c); if(ppelempp= /求得哈希地址，將

19、信息存入 h-count+; printf(第%d 個記錄沖突次數(shù)為%d。n,i+1,c);/需要顯示沖突次數(shù)時輸出 printf(n 建表完成!n 此哈希表容量為%d,當前表內(nèi)存儲的記錄個數(shù)為% d.n,hashsize,h-count); bengettime(); void searchhash1(hashtable* h,int na str; printf(n 請輸入要查找記錄的姓名：n); scanf(%s,str); int p,pp; p=hash1(str); pp=p; while(h-elempp!=null) if(h-elempp!=null printf(姓 名：%

20、sn 電話號碼：%sn 聯(lián)系地址：%sn,h-elempp-name,h-elempp- tel,h-elempp-add); else printf(n 此人不存在，查找不成功!n); bengettime(); void bengettime() systemtime sys; getlocaltime( printf( %4d/%02d/%02d %02d:%02d:%02d.%03d n,sys.wyear,sys.wmonth,sys.wday,sys.whour,sys.wminute, sys.wsecond,sys.wmilliseconds); void createhash

21、2(hashtable* h,record* a)/建表，以電話號碼為關(guān)鍵字，建立相應的散列 表 /若哈希地址沖突，進行沖突處理 bengettime(); int i,p=-1,c,pp; for(i=0;ielempp!=null) pp=collision(p,c); if(ppelempp= /求得哈希地址，將信息存入 h-count+; printf(第%d 個記錄沖突次數(shù)為%d。n,i+1,c);/需要顯示沖突次數(shù)時輸出 printf(n 建表完成!n 此哈希表容量為%d,當前表內(nèi)存儲的記錄個數(shù)為% d.n,hashsize,h-count); bengettime(); void

22、 searchhash2(hashtable* h,int na tele; printf(n 請輸入要查找記錄的電話號碼：n); scanf(%s,tele); int p,pp; p=hash2(tele); pp=p; while(h-elempp!=null) if(h-elempp!=null printf(姓 名：%sn 電話號碼：%sn 聯(lián)系地址：%sn,h-elempp-name,h-elempp- tel,h-elempp-add); else printf(n 此人不存在，查找不成功!n); bengettime(); void save() file *fp; if(fp

23、=fopen(c:test.txt, w)=null) printf(nerror opening customet file); fclose(fp); int main(int argc, char* argv) int c,flag=1; hashtable *h; h=(hashtable*)malloc(len); for(int i=0;ielemi=null; h-size=hashsize; h-count=0; record amaxsize; while (1) printf(n ); printf(n 歡迎使用電話號碼查找系統(tǒng) ); printf(n ); printf(

24、n 哈希表的設(shè)計與實現(xiàn) ); printf(n 【1】. 添加用戶信息 ); printf(n 【2】. 讀取所有用戶信息 ); printf(n 【3】. 以姓名建立哈希表(再哈希法解決沖突) ); printf(n 【4】. 以電話號碼建立哈希表(再哈希法解決沖突) ); printf(n 【5】. 查找并顯示給定用戶名的記錄 ); printf(n 【6】. 查找并顯示給定電話號碼的記錄 ); printf(n 【7】. 清屏 ); printf(n 【8】. 保存 ); printf(n 【9】. 退出程序 ); printf(n 溫馨提示： ); printf(n .進行 5 操作前

25、 請先輸出 3 ); printf(n .進行 6 操作前 請先輸出 4 ); printf(n ); printf(n); printf(請輸入一個任務(wù)選項); printf(n); int num; scanf(%d, switch(num) case 1: getin(a); break; case 2: showinformation(a); break; case 3: createhash1(h,a); /* 以姓名建立哈希表 */ break; case 4: createhash2(h,a); /* 以電話號碼建立哈希表 */ break; case 5: c=0; searc

26、hhash1(h,c); break; case 6: c=0; searchhash2(h,c); break; case 7: cls(a); break; case 8: save(); break; case 9: return 0; break; default: printf(你輸錯了，請重新輸入!); printf(n); system(pause); return 0; display(f); 二教學計劃編制問題。二教學計劃編制問題。假設(shè)任何專業(yè)都有固定的學習年限，每 學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè) 開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須

27、滿足先修 關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可 以沒有。每門課恰好占一個學期。試在這樣的前提下設(shè)計一個教學 計劃編制程序。基本要求：1)輸入?yún)?shù)：學期總數(shù)，一學期的學分 上限，每門課的課程號(固定占 3 位的字母數(shù)字串，規(guī)定從 c01c12)、學分和直接先修課的課程號；2)輸出參數(shù)：輸出提示信 息，由用戶在鍵盤上輸入運行程序中規(guī)定的命令來指定下列兩種編 排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是使 課程盡可能地集中在前幾個學期中；3)若根據(jù)給定的條件問題無解， 則報告適當?shù)男畔?，否則將教學計劃輸出到用戶指定的文件中。 1.1.采用類語言定義相關(guān)的數(shù)據(jù)類型采用

28、類語言定義相關(guān)的數(shù)據(jù)類型 typedef int status; / status 是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如 ok 等 typedef int boolean; / boolean 是布爾類型,其值是 true 或 false #define max_name 10 /* 頂點字符串的最大長度*/ #define maxclass 100 int z=0; int x=0; int xqzs,q=1,xfsx; typedef int infotype; typedef char vertextypemax_name; /* 字符串類型*/ /* 圖的鄰接表存儲表示*/ #de

29、fine max_vertex_num 100 typedef enumdggraphkind; /* 有向圖,有向網(wǎng),無向圖,無向網(wǎng) */ typedef struct arcnode int adjvex; /* 該弧所指向的頂點的位置*/ struct arcnode *nextarc; /* 指向下一條弧的指針*/ infotype *info; /* 網(wǎng)的權(quán)值指針）*/ arcnode; /* 表結(jié)點*/ typedef struct vertextype data; /* 頂點信息*/ arcnode *firstarc; /* 第一個表結(jié)點的地址,指向第一條依附該頂點的弧的指 針

30、*/ vnode,adjlistmax_vertex_num; /* 頭結(jié)點*/ typedef struct adjlist vertices,verticestwo; int vexnum,arcnum; /* 圖的當前頂點數(shù)和弧數(shù)*/ int kind; /* 圖的種類標志*/ algraph; 2.2.算法設(shè)計算法設(shè)計 1頭結(jié)點，表結(jié)點，鄰接表的定義 #define max_vertex_num 100 /最大課程總數(shù) typedef struct arcnode int adjvex; struct arcnode *nextarc; arcnode; typedef struct

31、vnode char name24; /課程名 int classid; /課程號 int credit; /課程的學分 int indegree; /該結(jié)點的入度 int state; /該節(jié)點的狀態(tài) arcnode *firstarc; /指向第一條依附該頂點的弧的 指針 vnode,adjlistmax_vextex_num; typedef struct adjlist vertices; int vexnum, arcnum; algraph; 鄰接表的基本操作： void creatgraph(algraph *); 創(chuàng)建鄰接表 void findindegree(algraph

32、, int * ); 求一個結(jié)點的入度 void topologicalsort_1(algraph g,int numterm,int maxcredit); 拓撲排序來編排課程 void topologicalsort_2(algraph g,int numterm,int maxcredit); 2棧的定義： #define stack_init_size 100 /存儲空間的初時分配量 #define stackincrement 10 /存儲空間的分配增量 typedef int elemtype; typedef struct adjlist vertices; int vexnu

33、m, arcnum; algraph; 基本操作： void initstack (sqstack *s); 棧的初始化 int stackempty(sqstack s); 判斷棧是否為空 void push(sqstack *s, int ); 入棧操作 int pop(sqstack *s, int *e); 出棧操作 int sort(sqstack *s,int *t); 3.3.函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖 4. .調(diào)試分析調(diào)試分析 a.在調(diào)試過程中需要把輸入的信息保存到一個文件夾中，在老師的幫助下以及上網(wǎng)查找下， 最后解決了問題。解決問題參考代碼如下： #include #i

34、nclude using namespace std; int main() main() locatevex() creategraph() display() findindegree() clearstack() stackempty() f int a; ofstream outfile(d:fl.txt,ios:out); if(!outfile) cerropen error!endl; exit(1); for(int i=0;ia; outfileaendl; outfile.close(); cout處理完畢，請打開文件查看結(jié)果！endl; return 0; b.b.對于有

35、 n 個定點，e 條邊的 aov 網(wǎng)而言，拓撲排序算法中掃描表，將入度為 0 的頂點表， 棧的時間復雜度為 o（n），若為有向無回路，每個頂點進出棧各一次，共循環(huán) e 次，所以 整個算法復雜度為 o（n+e）。 5.5.測試結(jié)果測試結(jié)果 程序初始運行結(jié)果：程序初始運行結(jié)果： 6.6.源程序（帶注釋）源程序（帶注釋） using namespace std; / 函數(shù)結(jié)果狀態(tài)代碼 #define true 1 #define false 0 #define ok 1 #define error 0 #define infeasible -1 typedef int status; / statu

36、s 是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如 ok 等 typedef int boolean; / boolean 是布爾類型,其值是 true 或 false #define max_name 10 /* 頂點字符串的最大長度*/ #define maxclass 100 int z=0; int x=0; int xqzs,q=1,xfsx; typedef int infotype; typedef char vertextypemax_name; /* 字符串類型*/ /* 圖的鄰接表存儲表示*/ #define max_vertex_num 100 typedef enumdggr

37、aphkind; /* 有向圖,有向網(wǎng),無向圖,無向網(wǎng) */ typedef struct arcnode int adjvex; /* 該弧所指向的頂點的位置*/ struct arcnode *nextarc; /* 指向下一條弧的指針*/ infotype *info; /* 網(wǎng)的權(quán)值指針）*/ arcnode; /* 表結(jié)點*/ typedef struct vertextype data; /* 頂點信息*/ arcnode *firstarc; /* 第一個表結(jié)點的地址,指向第一條依附該頂點的弧的指針*/ vnode,adjlistmax_vertex_num; /* 頭結(jié)點*/

38、typedef struct adjlist vertices,verticestwo; int vexnum,arcnum; /* 圖的當前頂點數(shù)和弧數(shù)*/ int kind; /* 圖的種類標志*/ algraph; /* 圖的鄰接表存儲的基本操作*/ int locatevex(algraph g,vertextype u) /* 初始條件: 圖 g 存在,u 和 g 中頂點有相同特征*/ /* 操作結(jié)果: 若 g 中存在頂點 u,則返回該頂點在圖中位置;否則返回-1 */ int i; for(i=0;ig.vexnum;+i) if(strcmp(u,g.verticesi.data

39、)=0) return i; return -1; status creategraph(algraph *g) /* 采用鄰接表存儲結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的圖 g(用一個函數(shù)構(gòu)造種圖) */ int i,j,k; vertextype va,vb; arcnode *p; printf(*n); printf(請輸入教學計劃的課程數(shù):n ); printf(*n); scanf(%d, printf(*n); printf(請輸入拓撲排序所形成的課程先修關(guān)系的邊數(shù): n); printf(*n); scanf(%d, printf(*n); printf(請輸入%d 個課程的代表值(%d 個

40、字符):n,(*g).vexnum,max_name); printf(*n); for(i=0;i(*g).vexnum;+i) /* 構(gòu)造頂點向量*/ scanf(%s,(*g).verticesi.data); (*g).verticesi.firstarc=null; printf(請輸入%d 個課程的學分值(%d 個字符):n,(*g).vexnum,max_name); for(i=0;i(*g).vexnum;+i) /* 構(gòu)造頂點向量*/ scanf(%s,(*g).verticestwoi.data); printf(*n); printf(請順序輸入每條弧(邊)的弧尾和弧頭

41、(以空格作為間隔):n); printf(*n); for(k=0;kadjvex=j; p-info=null; /* 圖*/ p-nextarc=(*g).verticesi.firstarc; /* 插在表頭*/ (*g).verticesi.firstarc=p; return ok; void display(algraph g) /* 輸出圖的鄰接矩陣 g */ int i; arcnode *p; switch(g.kind) case dg: printf(有向圖n); printf(%d 個頂點：n,g.vexnum); for(i=0;ig.vexnum;+i) print

42、f(%s ,g.verticesi.data); printf(n%d 條弧(邊):n,g.arcnum); for(i=0;iadjvex.data); p=p-nextarc; printf(n); void findindegree(algraph g,int indegree) /* 求頂點的入度，算法調(diào)用*/ int i; arcnode *p; for(i=0;ig.vexnum;i+) indegreei=0; /* 賦初值*/ for(i=0;iadjvex+; p=p-nextarc; typedef int selemtype; /* 棧類型*/ /*棧的順序存儲表示*/

43、#define stack_init_size 10 /* 存儲空間初始分配量*/ #define stackincrement 2 /* 存儲空間分配增量*/ typedef struct sqstack selemtype *base; /* 在棧構(gòu)造之前和銷毀之后，base 的值為 null */ selemtype *top; /* 棧頂指針*/ int stacksize; /* 當前已分配的存儲空間，以元素為單位*/ sqstack; /* 順序棧*/ /* 順序棧的基本操作*/ status initstack(sqstack *s) /* 構(gòu)造一個空棧 s */ (*s).ba

44、se=(selemtype *)malloc(stack_init_size*sizeof(selemtype); if(!(*s).base) exit(overflow); /* 存儲分配失敗*/ (*s).top=(*s).base; (*s).stacksize=stack_init_size; return ok; void clearstack(sqstack *s) /清空棧的操作 s-top=s-base; status stackempty(sqstack s) /* 若棧 s 為空棧，則返回 true，否則返回 false */ if(s.top=s.base) retur

45、n true; else return false; status pop(sqstack *s,selemtype *e) /* 若棧不空，則刪除 s 的棧頂元素，用 e 返回其值，并返回 ok；否則返回 error */ if(*s).top=(*s).base) return error; *e=*-(*s).top; return ok; status push(sqstack *s,selemtype e) /* 插入元素 e 為新的棧頂元素*/ if(*s).top-(*s).base=(*s).stacksize) /* 棧滿，追加存儲空間*/ (*s).base=(selemt

46、ype *)realloc(*s).base,(*s).stacksize+stackincrement)*sizeof (selemtype); if(!(*s).base) exit(overflow); /* 存儲分配失敗*/ (*s).top=(*s).base+(*s).stacksize; (*s).stacksize+=stackincrement; *(*s).top)+=e; return ok; typedef int pathonemaxclass; typedef int pathtwomaxclass; status topologicalsort(algraph g

47、) /* 有向圖 g 采用鄰接表存儲結(jié)構(gòu)。若 g 無回路,則輸出 g 的頂點的一個拓撲序列并返回 ok, */ /* 否則返回 error。*/ int i,k,j=0,count,indegreemax_vertex_num; bool has=false; sqstack s; pathone a; pathtwo b; arcnode *p; findindegree(g,indegree); /* 對各頂點求入度 indegree0.vernum-1 */ initstack( /* 初始化棧*/ for(i=0;ig.vexnum;+i) /* 建零入度頂點棧 s */ if(!in

48、degreei) push( /cout*g.verticesi.datanextarc) /* 對 i 號頂點的每個鄰接點的入度減*/ k=p-adjvex; if(!(-indegreek) /* 若入度減為,則入棧*/ push( /cout*g.verticesi.dataendl; if(countg.vexnum) printf(此有向圖有回路n); return error; else printf(為一個拓撲序列。n); has=true; findindegree(g,indegree); /* 對各頂點求入度 indegree0.vernum-1 */ clearstack

49、( cout=課程計劃如下 =endl; int qq=1; /學期數(shù) int xxf; while(qq=xqzs) int result20; int rtop=0; int nn=0; int ccount=0; / 學期學分計算 xxf=0; for(i=0;ixfsx) break; indegreei-; for(p=g.verticesi.firstarc;p;p=p-nextarc) /* 對 i 號頂點的每個鄰接點的入度減*/ k=p-adjvex; indegreek-; /* if(!(-indegreek) 若入度減為,則入棧 push( */ resultrtop=i

50、; rtop+; /保存本地文件 ofstream outfile(課程文件.txt,ios:out); outfile第qq個學期的課程為：endl; for(nn=0;nnrtop;nn+) outfile課程g.verticesresultnn.dataendl; qq+; outfile.close(); cout處理完畢，請打開文件查看結(jié)果！endl; return ok; void main() algraph f; printf(.n); printf(教學計劃編制問題的數(shù)據(jù)模型為拓撲排序 aov-網(wǎng)結(jié)構(gòu)。n); printf(.n); printf(以下為教學計劃編制問題的求解過程:n); printf(*n); printf(請輸入學期總數(shù):n); printf(*n); scanf(%d, printf(*n); printf(請輸入學期的學