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

1 * 實(shí)踐教學(xué)實(shí)踐教學(xué) * 蘭州理工大學(xué)蘭州理工大學(xué) 計(jì)算機(jī)與通信學(xué)院 2015 年秋季學(xué)期 算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì) 題 目: 散列表的設(shè)計(jì)與實(shí)現(xiàn) 教學(xué)計(jì)劃編制問題 專業(yè)班級：軟件工程二班 姓 名： 學(xué) 號： 指導(dǎo)教師： 成 績： 2 目目 錄錄 摘要摘要.3 一一. . 散列表的設(shè)計(jì)與實(shí)現(xiàn)散列表的設(shè)計(jì)與實(shí)現(xiàn) 1.采用類語言定義相關(guān)的數(shù)據(jù)類型.4 2. 算法設(shè)計(jì)4 3.函數(shù)的調(diào)用關(guān)系圖7 4.調(diào)試分析.8 6.源程序（帶注釋）.11 二教學(xué)計(jì)劃編制問題二教學(xué)計(jì)劃編制問題 1.采用類語言定義相關(guān)的數(shù)據(jù)類型.18 2.算法設(shè)計(jì).19 3. 函數(shù)的調(diào)用關(guān)系圖21 5. 測試結(jié)果22 6.源程序（帶注釋）.23 總結(jié).31 致致 謝謝.32 3 摘要摘要 1.1. 散列表的設(shè)計(jì)與實(shí)現(xiàn)散列表的設(shè)計(jì)與實(shí)現(xiàn) (1)(1)查找并顯示給定電話號碼的記錄查找并顯示給定電話號碼的記錄 (2)(2) 查找并顯示給定用戶名的記錄查找并顯示給定用戶名的記錄 (3)(3) 用散列表實(shí)現(xiàn)電話號碼查找系統(tǒng)用散列表實(shí)現(xiàn)電話號碼查找系統(tǒng) (4)(4) 以電話號碼和用戶名為關(guān)鍵字建立散列表以電話號碼和用戶名為關(guān)鍵字建立散列表 關(guān)鍵字：電話號碼關(guān)鍵字：電話號碼 用戶名用戶名 地址地址 查找查找 2.2.教學(xué)計(jì)劃編制問題教學(xué)計(jì)劃編制問題 （1)1)輸入?yún)?shù)：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號輸入?yún)?shù)：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號 （2)2)輸出參數(shù)：輸出提示信息輸出參數(shù)：輸出提示信息 （3)3)闡明了如何搞好教學(xué)管理，從而為提高教學(xué)質(zhì)量提供保證闡明了如何搞好教學(xué)管理，從而為提高教學(xué)質(zhì)量提供保證 （4)4)重視教學(xué)計(jì)劃的改革修訂工作，以確保教育教學(xué)質(zhì)量，提高教育教學(xué)水平。重視教學(xué)計(jì)劃的改革修訂工作，以確保教育教學(xué)質(zhì)量，提高教育教學(xué)水平。 （5)5)明確培養(yǎng)目標(biāo)明確培養(yǎng)目標(biāo), ,注重學(xué)科設(shè)置的整體性、統(tǒng)一性和靈活性、全面性注重學(xué)科設(shè)置的整體性、統(tǒng)一性和靈活性、全面性, ,學(xué)分制學(xué)分制 改革有機(jī)結(jié)合改革有機(jī)結(jié)合 關(guān)鍵字：學(xué)期關(guān)鍵字：學(xué)期 學(xué)分學(xué)分 課程號課程號 教學(xué)計(jì)劃教學(xué)計(jì)劃 管理管理 4 一一散列表的設(shè)計(jì)與實(shí)現(xiàn)散列表的設(shè)計(jì)與實(shí)現(xiàn)。設(shè)計(jì)散列表實(shí)現(xiàn)電話號碼查找系統(tǒng)?；疽?求： (1)設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號碼、用戶名、地址； (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; typedef struct/哈希表 record *elemhashsize; /數(shù)據(jù)元素存儲基址 int count; /當(dāng)前數(shù)據(jù)元素個(gè)數(shù) int size; /當(dāng)前容量 hashtable 2.2.算法設(shè)計(jì)算法設(shè)計(jì) 初始化散列表算法： void inithashtable(hashtable ht,hashtable2 ht2) for(int i=0;i=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; 14 return unsuccess; void bengettime(); void createhash1(hashtable* h,record* a)/建表，以人的姓名為關(guān)鍵字，建立相應(yīng)的散列 表 /若哈希地址沖突，進(jìn)行沖突處理 bengettime(); int i,p=-1,c,pp; for(i=0;ielempp!=null) pp=collision(p,c); if(ppelempp= /求得哈希地址，將信息存入 h-count+; printf(“第%d 個(gè)記錄沖突次數(shù)為%d。n“,i+1,c);/需要顯示沖突次數(shù)時(shí)輸出 printf(“n 建表完成!n 此哈希表容量為%d,當(dāng)前表內(nèi)存儲的記錄個(gè)數(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 15 printf(“姓 名：%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 createhash2(hashtable* h,record* a)/建表，以電話號碼為關(guān)鍵字，建立相應(yīng)的散列 表 /若哈希地址沖突，進(jìn)行沖突處理 bengettime(); int i,p=-1,c,pp; for(i=0;ielempp!=null) pp=collision(p,c); if(ppelempp= /求得哈希地址，將信息存入 h-count+; printf(“第%d 個(gè)記錄沖突次數(shù)為%d。n“,i+1,c);/需要顯示沖突次數(shù)時(shí)輸出 printf(“n 建表完成!n 此哈希表容量為%d,當(dāng)前表內(nèi)存儲的記錄個(gè)數(shù)為% d.n“,hashsize,h-count); bengettime(); void searchhash2(hashtable* h,int 16 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=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(“n 哈希表的設(shè)計(jì)與實(shí)現(xiàn) “); printf(“n 【1】. 添加用戶信息 “); printf(“n 【2】. 讀取所有用戶信息 17 “); 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 .進(jìn)行 5 操作前 請先輸出 3 “); printf(“n .進(jìn)行 6 操作前 請先輸出 4 “); printf(“n “); printf(“n“); printf(“請輸入一個(gè)任務(wù)選項(xiàng)“); 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; searchhash1(h,c); 18 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(“你輸錯(cuò)了，請重新輸入!“); printf(“n“); system(“pause“); return 0; display(f); 二教學(xué)計(jì)劃編制問題。二教學(xué)計(jì)劃編制問題。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每 學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長度和學(xué)分上限值均相等。每個(gè)專業(yè) 開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修 關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可 以沒有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué) 計(jì)劃編制程序?；疽螅?)輸入?yún)?shù)：學(xué)期總數(shù)，一學(xué)期的學(xué)分 上限，每門課的課程號(固定占 3 位的字母數(shù)字串，規(guī)定從 c01c12)、學(xué)分和直接先修課的課程號；2)輸出參數(shù)：輸出提示信 息，由用戶在鍵盤上輸入運(yùn)行程序中規(guī)定的命令來指定下列兩種編 排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使 19 課程盡可能地集中在前幾個(gè)學(xué)期中；3)若根據(jù)給定的條件問題無解， 則報(bào)告適當(dāng)?shù)男畔?，否則將教學(xué)計(jì)劃輸出到用戶指定的文件中。 1.1.采用類語言定義相關(guān)的數(shù)據(jù)類型采用類語言定義相關(guān)的數(shù)據(jù)類型 typedef int status; / status 是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如 ok 等 typedef int boolean; / boolean 是布爾類型,其值是 true 或 false #define max_name 10 /* 頂點(diǎn)字符串的最大長度*/ #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 enumdggraphkind; /* 有向圖,有向網(wǎng),無向圖,無向網(wǎng) */ typedef struct arcnode int adjvex; /* 該弧所指向的頂點(diǎn)的位置*/ struct arcnode *nextarc; /* 指向下一條弧的指針*/ infotype *info; /* 網(wǎng)的權(quán)值指針）*/ arcnode; /* 表結(jié)點(diǎn)*/ typedef struct vertextype data; /* 頂點(diǎn)信息*/ arcnode *firstarc; /* 第一個(gè)表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指 針*/ vnode,adjlistmax_vertex_num; /* 頭結(jié)點(diǎn)*/ typedef struct adjlist vertices,verticestwo; int vexnum,arcnum; /* 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)*/ int kind; /* 圖的種類標(biāo)志*/ algraph; 2.2.算法設(shè)計(jì)算法設(shè)計(jì) 1頭結(jié)點(diǎn)，表結(jié)點(diǎn)，鄰接表的定義 #define max_vertex_num 100 /最大課程總數(shù) typedef struct arcnode 20 int adjvex; struct arcnode *nextarc; arcnode; typedef struct vnode char name24; /課程名 int classid; /課程號 int credit; /課程的學(xué)分 int indegree; /該結(jié)點(diǎn)的入度 int state; /該節(jié)點(diǎn)的狀態(tài) arcnode *firstarc; /指向第一條依附該頂點(diǎn)的弧的 指針 vnode,adjlistmax_vextex_num; typedef struct adjlist vertices; int vexnum, arcnum; algraph; 鄰接表的基本操作： void creatgraph(algraph *); 創(chuàng)建鄰接表 void findindegree(algraph , int * ); 求一個(gè)結(jié)點(diǎn)的入度 void topologicalsort_1(algraph g,int numterm,int maxcredit); 拓?fù)渑判騺砭幣耪n程 void topologicalsort_2(algraph g,int numterm,int maxcredit); 2棧的定義： #define stack_init_size 100 /存儲空間的初時(shí)分配量 #define stackincrement 10 /存儲空間的分配增量 typedef int elemtype; typedef struct adjlist vertices; 21 int vexnum, 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)試過程中需要把輸入的信息保存到一個(gè)文件夾中，在老師的幫助下以及上網(wǎng)查找下， 最后解決了問題。解決問題參考代碼如下： #include #include using namespace std; int main() main() locatevex() creategraph() display() findindegree() clearstack() stackempty() f 22 int a; ofstream outfile(“d:fl.txt“,ios:out); if(!outfile) cerra; outfileadjvex=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 個(gè)頂點(diǎn)：n“,g.vexnum); for(i=0;iadjvex.data); p=p-nextarc; printf(“n“); void findindegree(algraph g,int indegree) /* 求頂點(diǎn)的入度，算法調(diào)用*/ int i; arcnode *p; for(i=0;iadjvex+; p=p-nextarc; typedef int selemtype; /* 棧類型*/ /*棧的順序存儲表示*/ #define stack_init_size 10 /* 存儲空間初始分配量*/ #define stackincrement 2 /* 存儲空間分配增量*/ typedef struct sqstack selemtype *base; /* 在棧構(gòu)造之前和銷毀之后，base 的值為 null */ selemtype *top; /* 棧頂指針*/ int stacksize; /* 當(dāng)前已分配的存儲空間，以元素為單位*/ sqstack; /* 順序棧*/ /* 順序棧的基本操作*/ status initstack(sqstack *s) /* 構(gòu)造一個(gè)空棧 s */ (*s).base=(selemtype *)malloc(stack_init_size*sizeof(selemtype); if(!(*s).base) exit(overflow); /* 存儲分配失敗*/ (*s).top=(*s).base; (*s).stacksize=stack_init_size; 27 return ok; void clearstack(sqstack *s) /清空棧的操作 s-top=s-base; status stackempty(sqstack s) /* 若棧 s 為空棧，則返回 true，否則返回 false */ if(s.top=s.base) return 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=(selemtype *)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) /* 有向圖 g 采用鄰接表存儲結(jié)構(gòu)。若 g 無回路,則輸出 g 的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷?28 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); /* 對各頂點(diǎn)求入度 indegree0vernum-1 */ initstack( /* 初始化棧*/ for(i=0;inextarc) /* 對 i 號頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減*/ k=p-adjvex; if(!(-indegreek) /* 若入度減為,則入棧*/ push( /coutxfsx) break; indegreei-; for(p=g.verticesi.firstarc;p;p=p-nextarc) /* 對 i 號頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減*/ k=p-adjvex; indegreek-; /* if(!(-indegreek) 若入度減為,則入棧 push( */ resultrtop=i; rtop+; 30 /保存本地文件 ofstream outfile(“課程文件.txt“,ios:out); outfile“第“qq“個(gè)“學(xué)期的課程為：“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(“教學(xué)計(jì)劃編制問題的數(shù)據(jù)模型為拓?fù)渑判?aov-網(wǎng)結(jié)構(gòu)。n“); printf(“.n“); printf(“以下為教學(xué)計(jì)劃編制問題的求解過程:n“); printf(“*n“); printf(“請輸入學(xué)期總數(shù):n“); printf(“*n“); scanf(“%d“, printf(“*n“); printf(“請輸入學(xué)期的學(xué)分上限:n“); printf(“*n“); scanf(“%d“, printf(“*n“); creategraph( topologicalsort(f); 31 總結(jié)總結(jié) 雖然在大一我們已經(jīng)學(xué)習(xí)了 c 語言，但是，直到本期我們才開設(shè)了數(shù)據(jù)結(jié)構(gòu)這一門課 程。這門課程讓我們對程序的原理有了系統(tǒng)的認(rèn)識。對以往模糊的經(jīng)驗(yàn)，起了總結(jié)提升的 作用。在學(xué)習(xí)了這門課程后，我們進(jìn)行了 2 個(gè)星期的課程設(shè)計(jì)，以實(shí)踐我們的學(xué)習(xí)內(nèi)容。 在這次課程設(shè)計(jì)中，我被分配到了散列表的設(shè)計(jì)與實(shí)現(xiàn)和教學(xué)計(jì)劃課程編制問題，開 始感覺很難，因?yàn)槲覐奈淳帉戇^如此復(fù)雜的程序。在多方查找資料并參考類似程序后，我 大體將程序的構(gòu)架描繪好了。一邊對照著網(wǎng)上的資料，一邊對程序進(jìn)行修改補(bǔ)充，然后根 據(jù)擬好的大綱進(jìn)行編制。期間，我與其它同學(xué)進(jìn)行了討論和探究，對程序的細(xì)節(jié)問題和應(yīng) 用方面進(jìn)行了探索，并解決了主要的問題，于是便著手寫具體的程序。 這次實(shí)驗(yàn)，我進(jìn)行了大量的資料查閱，包括向老師請求幫助解釋題目要求，對所學(xué)知 識進(jìn)行復(fù)習(xí)。通過這些努力，我對算法有了更深入的理解，對編程的步驟，有了具體的體 會(huì)。通過和同學(xué)的廣泛交流，我體會(huì)到了合作的必要性及合作的優(yōu)勢。更重要的是，這個(gè) 課題完全脫胎于實(shí)際問題，讓我對計(jì)算機(jī)行業(yè)，充滿了信心和自豪。 以往我們學(xué)的計(jì)算機(jī)知識一般停留在理論上，這讓我們不太理解計(jì)算機(jī)的應(yīng)用和前景， 而較少注重我們對算法的實(shí)踐鍛煉。而這一次的實(shí)習(xí)既需要