數(shù)據(jù)結(jié)構(gòu)(C語言)課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)報(bào)告（2012 2013學(xué)年 第 1 學(xué)期） 計(jì)算機(jī)與信息工程學(xué)院2013年7月8日目 錄一. 課程設(shè)計(jì)的目的與要求（含設(shè)計(jì)指標(biāo)）2二. 方案實(shí)現(xiàn)與調(diào)試22.1 題目：航班查詢系統(tǒng)22.2題目：字符串操作42.3：二叉樹的運(yùn)算262.4二叉樹運(yùn)算18三課程設(shè)計(jì)分析與總結(jié)10四. 源程序清單102.1航班查詢系統(tǒng)102.2字符串操作182.3二叉樹運(yùn)算2192.4二叉樹運(yùn)算22設(shè)計(jì)日志25一. 課程設(shè)計(jì)的目的與要求（含設(shè)計(jì)指標(biāo)） 設(shè)計(jì)目的1、培養(yǎng)學(xué)生運(yùn)用算法與數(shù)據(jù)結(jié)構(gòu)的基本知識(shí)解決實(shí)際編程中的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和算法設(shè)計(jì)問題。2、培養(yǎng)學(xué)生獨(dú)立設(shè)計(jì)程序與解決問題的能力，培養(yǎng)學(xué)生團(tuán)隊(duì)

2、協(xié)作集成程序模塊及調(diào)試能力。3、培養(yǎng)學(xué)生初步的軟件設(shè)計(jì)及軟件測(cè)試的能力?；疽螅簩W(xué)生必須仔細(xì)閱讀數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)指導(dǎo)書，認(rèn)真主動(dòng)完成課程設(shè)計(jì)的要求。有問題及時(shí)主動(dòng)通過各種方式與教師聯(lián)系溝通。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課設(shè)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過程中不斷檢測(cè)自己的計(jì)劃完成情況，有困難及時(shí)向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要一周時(shí)間完成，一周中每天（按每周5天）上機(jī)調(diào)試程序時(shí)間不少于4小時(shí)，總共至少要上機(jī)調(diào)試程序15小時(shí)。根據(jù)設(shè)計(jì)報(bào)告要求編寫設(shè)計(jì)報(bào)告，主要內(nèi)容包括目的、意義、原理和實(shí)現(xiàn)方法簡介、過程分析及說明、實(shí)驗(yàn)結(jié)果情況說明、結(jié)論。每位同學(xué)必須有可運(yùn)行的程序，學(xué)生能清楚解

3、釋各自編寫的程序，并回答教師的提問，學(xué)生回答的問題和程序運(yùn)行的結(jié)果作為評(píng)分的主要衡量標(biāo)準(zhǔn)；（周三開始逐一檢查）。二. 方案實(shí)現(xiàn)與調(diào)試2.1 題目：航班查詢系統(tǒng) 2.1.1 題目內(nèi)容 飛機(jī)航班信息包括：航班號(hào)、起點(diǎn)站、終點(diǎn)站、起飛時(shí)間、到達(dá)時(shí)間、機(jī)型以及票價(jià)，實(shí)例如下：設(shè)計(jì)航班查詢系統(tǒng)要求能對(duì)飛機(jī)航班信息進(jìn)行增加、刪除、排序和查找?？砂春桨嗟暮桨嗵?hào)、起點(diǎn)站、終點(diǎn)站、起飛時(shí)間以及到達(dá)時(shí)間進(jìn)行查詢2.1.2算法描述及實(shí)驗(yàn)步驟 算法描述該航班查詢系統(tǒng)采用線性鏈表存儲(chǔ)。開始，創(chuàng)建鏈表。然后輸出提示操作選項(xiàng)，由用戶輸入所選項(xiàng)序號(hào)。執(zhí)行選項(xiàng)。當(dāng)?shù)谝淮尾僮鹘Y(jié)束后，提示是否繼續(xù)進(jìn)行操作，再有用戶決定。 流程圖

4、開始初始化變量輸入操作選項(xiàng)判斷選項(xiàng)執(zhí)行操作輸出執(zhí)行結(jié)果判斷是否繼續(xù)操作結(jié)束是否2.1.3調(diào)試過程及實(shí)驗(yàn)結(jié)果 （1） 完成第一模塊：鏈表創(chuàng)建以及添加，編譯時(shí)出現(xiàn)警告：“warning c4091: typedef : ignored on left of struct fly when no variable is declared”，“typedef”時(shí)在結(jié)構(gòu)體后面定義一個(gè)變量名，所以只需在結(jié)構(gòu)體后面加一個(gè)變量名，或者是把結(jié)構(gòu)體的“typedef”去掉。運(yùn)行，結(jié)果提示錯(cuò)誤。重新檢查，發(fā)現(xiàn)調(diào)用的創(chuàng)建函數(shù)和添加函數(shù)位置放反了，修改錯(cuò)誤，運(yùn)行成功。 （2）完成其他模塊。在編寫排序模塊時(shí)，鏈表的排序不

5、懂，通過網(wǎng)上查找，用冒泡法，通過調(diào)換鏈表節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行排序。2.2題目：字符串操作 2.2.1題目內(nèi)容字符串采用數(shù)組存儲(chǔ)，建立兩個(gè)字符串string1和string2.輸出兩個(gè)字符串。將字符串string2的頭n個(gè)字符添加到string1的尾部，輸出結(jié)果 查找string3在串string1中的位置，若string3在string1中不存在，則插入string3在string1中的m位置上。輸出結(jié)果。2.2.2算法描述及實(shí)驗(yàn)步驟算法描述開始，輸入兩個(gè)字符串，然后將string2復(fù)制到string1后面。然后輸string3，判斷string3是否在string1內(nèi)，若存在，輸出找到；若不存在，

6、輸入插入位置，然后將string3插入string1中，輸出string1，結(jié)束。流程圖開始初始化變量輸入兩個(gè)字符串合并兩個(gè)字符串輸入字符串3判斷3是否存在1中輸出結(jié)果將3添加到1中結(jié)束是否2.2.3調(diào)試過程及實(shí)驗(yàn)結(jié)果（1）拷貝string3到string1時(shí)，因?yàn)橐苿?dòng)string1后面的字符，忘了加結(jié)束標(biāo)志，結(jié)果輸出亂碼。2.3：二叉樹的運(yùn)算2 2.3.1題目內(nèi)容 任務(wù) ：請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，把二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表。二叉樹用二叉鏈存儲(chǔ)，鏈接時(shí)用葉子結(jié)點(diǎn)的rchild 域存放指針。2.3.2算法描述及實(shí)驗(yàn)步驟 算法描述 該題采用線性鏈表存儲(chǔ)結(jié)構(gòu)。開始，創(chuàng)建二叉樹，鏈表。遍

7、歷整棵二叉樹，查找葉子節(jié) 點(diǎn)，當(dāng)找到是，將葉子節(jié)點(diǎn)放入鏈表當(dāng)中。輸出結(jié)果，結(jié)束。 流程圖開始初始化變量創(chuàng)建二叉樹創(chuàng)建鏈表輸入數(shù)據(jù)遍歷二叉樹判斷是否為葉子節(jié)點(diǎn)加入鏈表中輸出鏈表結(jié)束判斷是否結(jié)束是是否否2.3.3調(diào)試過程及實(shí)驗(yàn)結(jié)果2.4二叉樹運(yùn)算1 2.4.1題目內(nèi)容 任務(wù)：求二叉樹中指定兩個(gè)結(jié)點(diǎn)共同的最近祖先。2.4.2算法描述及實(shí)驗(yàn)步驟算法描述 開始，創(chuàng)建二叉樹。輸入要查找的兩個(gè)節(jié)點(diǎn)。判斷兩個(gè)節(jié)點(diǎn)位于根節(jié)點(diǎn)的哪一側(cè)，若位于兩側(cè)，這根節(jié)點(diǎn)為它們的最近共同祖先，否則用遞歸遍歷繼續(xù)判斷，查找。最后輸出結(jié)果，結(jié)束。流程圖開始初始化變量創(chuàng)建鏈表輸入查找的節(jié)點(diǎn)是否位于根節(jié)點(diǎn)的兩側(cè)往節(jié)點(diǎn)所在一側(cè)遍歷輸出結(jié)果

8、結(jié)束是否2.4.3調(diào)試過程及實(shí)驗(yàn)結(jié)果 調(diào)試過程 這道題的核心的內(nèi)容是找到要查找的兩個(gè)節(jié)點(diǎn)，然后再找共同祖先，所以我采用的一下方法： 創(chuàng)建的樹是事先排好序的，大于根節(jié)點(diǎn)的放在右邊，小于根節(jié)點(diǎn)的放左邊，相等輸不進(jìn)去。所以，通過判斷查找的節(jié)點(diǎn)位于根節(jié)點(diǎn)的那一邊，然后往那邊查找。當(dāng)兩節(jié)點(diǎn)位于上一節(jié)點(diǎn)兩側(cè)時(shí)，則上一節(jié)點(diǎn)為最近共同祖先。 運(yùn)行結(jié)果：三課程設(shè)計(jì)分析與總結(jié)1、這次課程設(shè)計(jì)為我們提供了一次實(shí)踐機(jī)會(huì)，讓我們用所學(xué)知識(shí)有所運(yùn)用。2、在這次課程設(shè)計(jì)上，鞏固了以前所學(xué)，并且查缺補(bǔ)漏；通過這次課程設(shè)計(jì)，有學(xué)習(xí)了許多新知識(shí)。四. 源程序清單2.1航班查詢系統(tǒng)#include#include#include#

9、define error 1#define ok 0typedef int status; /給int一個(gè)別名statustypedef struct fly /定義結(jié)構(gòu)體char flynum6;char star10;char reach10;char startime6;char reachtime10;char type10;int price;typedef struct node /定義航班信息鏈表的機(jī)構(gòu)體struct fly data; /數(shù)據(jù)域struct node *next; /指針域node,*link; void createlist(link &l) l = ( li

10、nk ) malloc ( sizeof ( node ) ); l-next = null; / 先建立一個(gè)帶頭結(jié)點(diǎn)的空鏈表 status listinsert(link &l ) /增加航班信息link p,s,r;s=l-next;r=l;p = ( link ) malloc ( sizeof ( node ) ); /生成新節(jié)點(diǎn)if(!p)printf(n空間分配失敗);return error;printf(n請(qǐng)輸入航班信息);scanf(%s%s%s%s%s%s%d,&p-data.flynum,&p-data.star,&p-data.reach,&p-data.startim

11、e,&p-data.reachtime,&p-data.type,&p-data.price); while(s!=null) /判斷該航班是否已經(jīng)安排了if(strcmp(p-data.flynum,s-data.flynum)=0)printf(n該航班已經(jīng)重復(fù));return error;s=s-next;while ( r-next!=null) /添加航班 r=r-next; p-next=r-next;r-next=p;return ok;status delete(link &l) /刪除航班信息link p,q;char num10;printf(n請(qǐng)輸入要?jiǎng)h除的航班號(hào):);s

12、canf(%s,&num);q=l;p=l-next;while(p-next!=null)if(strcmp(num,p-data.flynum)=0)break;q=q-next;p=p-next;q-next=p-next;free(p);return ok;void such_num(link l) /按航班號(hào)查詢link p;char num10;printf(n請(qǐng)輸入要查找的航班號(hào));scanf(%s,&num);p=l-next;while(p!=null)if(strcmp(num,p-data.flynum)=0)break;p=p-next;printf( %s ,p-da

13、ta.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data.type);printf( %d ,p-data.price);void such_star(link l) /按起飛地點(diǎn)查詢link p;char num10;printf(n請(qǐng)輸入起飛地點(diǎn):);scanf(%s,&num);p=l-next;while(p!=null)if(strcmp(num,p-data.st

14、ar)=0)break;p=p-next;printf( %s ,p-data.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data.type);printf( %d ,p-data.price);void such_reach(link l) /按到達(dá)地點(diǎn)查詢link p;char num10;printf(n請(qǐng)輸入到達(dá)地點(diǎn):);scanf(%s,&num);p=l-next

15、;while(p!=null)if(strcmp(num,p-data.reach)=0)break;p=p-next;printf( %s ,p-data.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data.type);printf( %d ,p-data.price);void such_stime(link l) /按起飛時(shí)間查詢link p;char num10;pr

16、intf(n請(qǐng)輸入起飛時(shí)間:);scanf(%s,&num);p=l-next;while(p!=null)if(strcmp(num,p-data.startime)=0)break;p=p-next;printf( %s ,p-data.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data.type);printf( %d ,p-data.price);void such_

17、rtime(link l) /按到達(dá)時(shí)間查詢link p;char num10;printf(n請(qǐng)輸入到達(dá)時(shí)間:);scanf(%s,&num);p=l-next;while(p!=null)if(strcmp(num,p-data.reachtime)=0)break;p=p-next;printf( %s ,p-data.flynum);printf( %s ,p-data.star);printf( %s ,p-data.reach);printf( %s ,p-data.startime);printf( %s ,p-data.reachtime);printf( %s ,p-data

18、.type);printf( %d ,p-data.price);void show(link l) /顯示航班信息link p;printf(n以下為所有航班信息:);p=l;while(p-next!=null)p=p-next;printf(n %s ,p-data.flynum); printf( %s ,p-data.star); printf( %s ,p-data.reach); printf( %s ,p-data.startime); printf( %s ,p-data.reachtime); printf( %s ,p-data.type); printf( %d ,p-

19、data.price);printf(n);status sort(link l) /排序，通過交換數(shù)據(jù)進(jìn)行排序；冒泡排序法link p,q,s;s = ( link ) malloc ( sizeof ( node ) ); if(!s)printf(n空間分配失敗);return error;for(p=l-next;p!=null;p=p-next)for(q=p-next;q!=null;q=q-next)if(strcmp(p-data.startime,q-data.startime)0)s-data=p-data;p-data=q-data;q-data=s-data;show(

20、l);return ok;void main() / 主函數(shù)link l;int i,a;printf( |-歡迎使用航班查詢系統(tǒng)-|n);printf(n);printf(n *);printf(n * *);printf(n * 1 顯示所有航班信息 *);printf(n * 2 航班號(hào)查詢 *);printf(n * 3 起飛時(shí)間查詢 *);printf(n * 4 到達(dá)時(shí)間查詢 *);printf(n * 5 起飛地點(diǎn)查詢 *);printf(n * 6 到達(dá)地點(diǎn)查詢 *);printf(n * 7 增加航班信息 *);printf(n * 8 刪除航班信息 *);printf(n

21、* 9 航班排序 *);printf(n * *);printf(n *);createlist(l); /創(chuàng)建鏈表printf(n |-航班號(hào)-|-起飛地點(diǎn)-|-到達(dá)地點(diǎn)-|-起飛時(shí)間-|-到達(dá)時(shí)間-|-飛機(jī)類型-|-票價(jià)-|);for(i=0;i100;i+) /用于多長操作printf(nn請(qǐng)輸入服務(wù)編號(hào):);scanf(%d,&a);switch(a)case 1:show(l);break;case 2:such_num(l);break;case 3:such_stime(l);break;case 4: such_rtime(l); break;case 5:such_star(

22、l);break;case 6:such_reach(l);break;case 7:listinsert(l);break;case 8:delete(l);case 9:sort(l);break;default:printf(輸入無效);break;printf(n請(qǐng)按任意鍵繼續(xù)操作! 退出請(qǐng)按0n);scanf(%d,&a);if(a=0)break;2.2字符串操作#include#includevoid main()int i,m,len1,len3,j;char string1100,string2100,string3100;char *p;printf(n請(qǐng)輸入string1

23、:);scanf(%s,&string1);printf(n請(qǐng)輸入string2:);scanf(%s,&string2);printf(n請(qǐng)輸入拷貝數(shù)n:);scanf(%d,&i);p=strncat(string1,string2,i); /調(diào)用strncat函數(shù)，完成字符串的合并。printf(%s,p);printf(n請(qǐng)輸入string3:);scanf(%s,&string3);p=strstr(string1,string3); /查找string1中是否存在string3的片段if(p)printf(存在n);else /string3的插入printf(請(qǐng)輸入插入位置m:)

24、;scanf(%d,&m);len3=strlen(string3);len1=strlen(string1);for(i=len1-1;i=m-1;i-)string1i+len3=string1i;string1len1+len3=0;for(i=0,j=m-1;ilen3;i+,j+)string1j=string3i;printf(%sn,string1);2.3二叉樹運(yùn)算2#include #include typedef int telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild

25、;binode, *bitree;bitree root;/定義根結(jié)點(diǎn) void insert_data(int x) /*生成二叉排序樹*/ bitree p,q,s;s=(bitree)malloc(sizeof(binode); /創(chuàng)建結(jié)點(diǎn)s-data=x; /結(jié)點(diǎn)賦值s-lchild=null;s-rchild=null;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序樹的適當(dāng)位置*/q=p;if(p-data=x) /相同結(jié)點(diǎn)不能重復(fù)插入printf(data already exist! n);return;else if(xdata

26、)p=p-lchild; else p=p-rchild;if(xdata)q-lchild=s;else q-rchild=s;void createlist(bitree &l) l = ( bitree ) malloc ( sizeof ( binode ) ); l-rchild = null; / 先建立一個(gè)帶頭結(jié)點(diǎn)的空鏈表 int preordertraverse(bitree root,bitree &l)bitree n,p,r;r=l;n=root;if(!n) return 0;if(n-lchild=null & n-rchild=null) /判斷葉子結(jié)點(diǎn)并利用指針r

27、child生成單鏈表p=( bitree )malloc( sizeof ( binode ) );p-data=n-data;while ( r-rchild!=null) r=r-rchild; p-rchild=r-rchild;r-rchild=p;return 0;if(n-lchild)preordertraverse(n-lchild,l);if(n-rchild)preordertraverse(n-rchild,l);return 0;/*遞歸輸出二叉樹*/dlr( bitree root ) if (root !=null) /非空二叉樹 printf( %d ,root-

28、data); /訪問d dlr(root-lchild); /遞歸遍歷左子樹 dlr(root-rchild); /遞歸遍歷右子樹 return(0); void main() bitree l;int i=1,x; /i記錄結(jié)點(diǎn)個(gè)數(shù)，x存放結(jié)點(diǎn)值root=null; /*千萬別忘了賦初值給root!*/printf(請(qǐng)輸入數(shù)據(jù),-9999表示輸入結(jié)束n);doprintf(please input data %d:,i);i+;scanf(%d,&x); /*從鍵盤采集數(shù)據(jù)，以-9999表示輸入結(jié)束*/if(x=-9999) printf(nnow output data value:n);

29、 else insert_data(x); /*調(diào)用插入數(shù)據(jù)元素的函數(shù)*/while(x!=-9999);createlist(l); dlr(root); /遍歷二叉樹preordertraverse(root,l); /查找葉子節(jié)點(diǎn)printf(n now output data:n);l=l-rchild;while(l) /輸出從左到右葉子節(jié)點(diǎn)printf( %d ,l-data);l=l-rchild;2.4二叉樹運(yùn)算#include #include typedef int telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild,*tag;binode, *bitree;bitree root;/定義根結(jié)點(diǎn) void insert_data(int x) /*生成二叉排序樹*/ bitree p,q,s;s=(bitree)malloc(sizeof(binode); /創(chuàng)建結(jié)點(diǎn)s-data=x; /結(jié)點(diǎn)賦值s-lchild=null;s-rchild=null;if(!root)root=s; elsep=root; while(p) /*