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

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

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

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

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

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

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

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

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

9、define error 1#define ok 0typedef int status; /給int一個別名statustypedef struct fly /定義結(jié)構(gòu)體char flynum6;char star10;char reach10;char startime6;char reachtime10;char type10;int price;typedef struct node /定義航班信息鏈表的機構(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; / 先建立一個帶頭結(jié)點的空鏈表 status listinsert(link &l ) /增加航班信息link p,s,r;s=l-next;r=l;p = ( link ) malloc ( sizeof ( node ) ); /生成新節(jié)點if(!p)printf(n空間分配失敗);return error;printf(n請輸入航班信息);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請輸入要刪除的航班號:);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) /按航班號查詢link p;char num10;printf(n請輸入要查找的航班號);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) /按起飛地點查詢link p;char num10;printf(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) /按到達地點查詢link p;char num10;printf(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) /按起飛時間查詢link p;char num10;pr

16、intf(n請輸入起飛時間:);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) /按到達時間查詢link p;char num10;printf(n請輸入到達時間:);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ù)進行排序；冒泡排序法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 航班號查詢 *);printf(n * 3 起飛時間查詢 *);printf(n * 4 到達時間查詢 *);printf(n * 5 起飛地點查詢 *);printf(n * 6 到達地點查詢 *);printf(n * 7 增加航班信息 *);printf(n * 8 刪除航班信息 *);printf(n

21、* 9 航班排序 *);printf(n * *);printf(n *);createlist(l); /創(chuàng)建鏈表printf(n |-航班號-|-起飛地點-|-到達地點-|-起飛時間-|-到達時間-|-飛機類型-|-票價-|);for(i=0;i100;i+) /用于多長操作printf(nn請輸入服務(wù)編號:);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請按任意鍵繼續(xù)操作! 退出請按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請輸入string1

23、:);scanf(%s,&string1);printf(n請輸入string2:);scanf(%s,&string2);printf(n請輸入拷貝數(shù)n:);scanf(%d,&i);p=strncat(string1,string2,i); /調(diào)用strncat函數(shù)，完成字符串的合并。printf(%s,p);printf(n請輸入string3:);scanf(%s,&string3);p=strstr(string1,string3); /查找string1中是否存在string3的片段if(p)printf(存在n);else /string3的插入printf(請輸入插入位置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二叉樹運算2#include #include typedef int telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild

25、;binode, *bitree;bitree root;/定義根結(jié)點 void insert_data(int x) /*生成二叉排序樹*/ bitree p,q,s;s=(bitree)malloc(sizeof(binode); /創(chuàng)建結(jié)點s-data=x; /結(jié)點賦值s-lchild=null;s-rchild=null;if(!root)root=s; elsep=root; while(p) /*如何接入二叉排序樹的適當(dāng)位置*/q=p;if(p-data=x) /相同結(jié)點不能重復(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; / 先建立一個帶頭結(jié)點的空鏈表 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é)點并利用指針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é)點個數(shù)，x存放結(jié)點值root=null; /*千萬別忘了賦初值給root!*/printf(請輸入數(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é)點printf(n now output data:n);l=l-rchild;while(l) /輸出從左到右葉子節(jié)點printf( %d ,l-data);l=l-rchild;2.4二叉樹運算#include #include typedef int telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild,*tag;binode, *bitree;bitree root;/定義根結(jié)點 void insert_data(int x) /*生成二叉排序樹*/ bitree p,q,s;s=(bitree)malloc(sizeof(binode); /創(chuàng)建結(jié)點s-data=x; /結(jié)點賦值s-lchild=null;s-rchild=null;if(!root)root=s; elsep=root; while(p) /*