數(shù)據結構課程設計任務書

1、數(shù)據結構課程設計任務書04級電氣信息類專業(yè)信息科學與技術學院2005年12月數(shù)據結構課程設計任務書一、 課程設計目的上機實習是對學生的一種全面綜合訓練，是與課堂聽講、自學和練習相輔相成的必不可少的一個教學環(huán)節(jié)。實習題是軟件設計的綜合訓練，包括問題分析、總體結構設計、用戶界面設計、程序設計基本技能和技巧以至一整套軟件工作規(guī)范的訓練和科學作風的培養(yǎng)。希望通過本次課程設計，使學生能夠獨立地完成從問題分析到文檔撰寫一整套的軟件設計過程，達到學以致用的目的。二、 課程設計內容課題一 運動會分數(shù)統(tǒng)計任務：參加運動會有n個學校，學校編號為1n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1m，女子m

2、+1m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些項目取前五名或前三名由學生自己設定。（m<=20,n<=20）功能要求：1) 可以輸入各個項目的前三名或前五名的成績；2) 能統(tǒng)計各學校總分；3) 可以按學校編號、學?？偡?、男女團體總分排序輸出；4) 可以按學校編號查詢學校某個項目的情況；5) 可以按項目編號查詢取得前三或前五名的學校。課題二 航空訂票系統(tǒng)任務：航空客運定票的業(yè)務活動包括：查詢航線、客票預定和辦理退票等。試設計一個航空客運定票系統(tǒng)，以使上述業(yè)務可以借助計算機來完成。功能要求：1) 錄入：可以錄入

3、航班情況（數(shù)據可以存儲在一個數(shù)據文件中，數(shù)據結構、具體數(shù)據自定）2) 查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；3) 訂票：（訂票情況可以存在一個數(shù)據文件中，結構自己設定）可以訂票，如果該航班已經無票，可以提供相關可選擇航班；4) 退票： 可退票，退票后修改相關數(shù)據文件；5) 客戶資料：有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號；6) 修改航班信息：當航班信息改變可以修改航班數(shù)據文件。課題三 文章編輯功能要求：1 輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁

4、文章，每行最多不超過80個字符，共N行；1) 分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；2) 統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；3) 刪除某一子串，并將后面的字符前移。存儲結構使用線性表，分別用幾個子函數(shù)實現(xiàn)相應的功能；輸入數(shù)據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。2輸出形式：1) 分行輸出用戶輸入的各行字符；2) 分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字數(shù)"3) 輸出刪除某一字符串后的文章；課題四 Joseph環(huán)任務：編號是1，2，,n的n個

5、人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設計一個程序來求出出列順序。功能要求：利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。課題五 猴子選大王任務：一堆猴子都有編號，編號是1，2，3 .m ,這群猴子（m個）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。功能要求

6、：1. 輸入數(shù)據：輸入m,n m,n 為整數(shù)，n<m2. 輸出形式：中文提示按照m個猴子，數(shù)n 個數(shù)的方法，輸出為大王的猴子是幾號 ，建立一個函數(shù)來實現(xiàn)此功能。三、課程設計要求1. 問題分析和任務定義。2. 軟件設計。3. 編碼實現(xiàn)。4. 軟件測試。5. 通過驗收，提交課程設計報告和電子文檔（包括已編譯的程序和課程設計報告）。四、考核與成績評定1課程設計階段的表現(xiàn)10%2 課程設計報告（含報告的規(guī)范、文字圖表的質量等） 40%3 程序上機檢查 50%五、注意事項1. 課程設計期間不遲到，不早退，有特殊情況要事先請假，并經有關老師批準方能有效，無故缺席者作曠課處理。2. 課程設計期間應按進

7、度，自覺進行有關內容的預習和復習，按照任務要求，認真設計獨立思考，全面完成設計任務。3. 進入機房，應遵守機房規(guī)定的各項制度。六、參考教材1. 嚴蔚敏等 數(shù)據結構（C語言版） 清華大學出版社 2. 嚴蔚敏等 數(shù)據結構題集（ C語言版） 清華大學出版社 3. 鄭人杰等 實用軟件工程（第二版） 清華大學出版社 4. 其他有關C或C+教材或資料 七、課程設計報告樣本實習報告示例：1.3題 集合的并、交和差運算實習報告題目：編制一個演示集合的并、交和差運算的程序班級：計算機95（1） 姓名：丁一 學號：954211 完成日期：一、需求分析1本演示程序中，集合的元素限定為小寫字母字符a.z，集合的大小n

8、<27。集合輸入的形式為一個以“回車符”為結束標志的字符串，串中字符順序不限，且允許出現(xiàn)重復字符或非法字符，程序應能自動濾去。輸出的運算結果字符串中將不含重復字符或非法字符。2演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運算命令；相應的輸入數(shù)據（濾去輸入中非法字符）和運算結果顯示在其后。3程序執(zhí)行的命令包括：1）構造集合1；2）構造集合2；3）求并集；4）求交集；5）求差集；6）結束。“構造集合1”和“構造集合2”時，需以字符串的形式鍵入集合元素。4測試數(shù)據（1）Set1=”magazine”， Set2=”paper”，

9、 Set1Set2=”aegimnprz”， Set1Set2=”ae”， Set1-Set2=”gimnz”；（2）Set1=”012oper4a6tion89”， Set2=”error data”， Set1Set2=”adeinoprt”， Set1Set2=”aeort”， Set1-Set2=”inp”。二、概要設計為實現(xiàn)上述程序功能，應以有序鏈表表示集合。為此，需要兩個抽象數(shù)據類型：有序表和集合。1有序表的抽象數(shù)據類型定義為：ADT OrderedList 數(shù)據對象：D= 數(shù)據關系：R1 基本操作： InitList(&L) 操作結果：構造一個空的有序表L。 Destro

10、yList(&L) 初始條件：有序表L已存在。 操作結果：銷毀有序表L。 ListLength(L) 初始條件：有序表L已存在。 操作結果：返回有序表L的長度。 ListEmpty(L) 初始條件：有序表L已存在。 操作結果：若有序表L為空表，則返回True，否則返回False。 GetElem(L，pos) 初始條件：有序表L已存在。 操作結果：若，則返回表中第pos個數(shù)據元素。 LocateElem(L，e，&q) 初始條件：有序表L已存在。 操作結果：若有序表L中存在元素e，則q指示L中第一個值為e的元素的位置，并返回函數(shù)值True；否則q指示第一個大于e的元素的前驅的位

11、置，并返回函數(shù)值False Append(&L，e) 初始條件：有序表L已存在。 操作結果：在有序表L的末尾插入元素e。 InsertAfter(&L，q，e) 初始條件：有序表L已存在，q指示L中一個元素。 操作結果：在有序表L中q指示的元素之后插入元素e。 ListTraverse(q，visit() 初始條件：有序表L已存在，q指示L中一個元素。 操作結果：依次對L中q指示的元素開始的每個元素調用函數(shù)visit()。 ADT OrderedList 2集合的抽象數(shù)據類型定義為：ADT Set數(shù)據對象：D= |為小寫英文字母且互不相同，數(shù)據關系：R1 基本操作： Creat

12、eSet(&T，Str) 初始條件：Str為字符串。 操作結果：生成一個由Str中小寫字母構成的集合T。 DestroySet(&T) 初始條件：集合T已存在。 操作結果：銷毀集合T的結構。 Union(&T，S1，S2) 初始條件：集合S1和S2存在。 操作結果：生成一個由S1和S2的并集構成的集合T。 Intersection（&T，S1，S2） 初始條件：集合S1和S2存在。 操作結果：生成一個由S1和S2的交集構成的集合T。 Difference（&T，S1，S2） 初始條件：集合S1和S2存在。 操作結果：生成一個由S1和S2的差集構成的集合T

13、。 PrintSet（T） 初始條件：集合T已存在。 操作結果：按字母次序順序顯示集合T的全部元素。ADT Set3. 本程序包含四個模塊：1） 主程序模塊：void main( ) 初始化； do 接受命令； 處理命令； while (“命令”退出”)；2) 集合單元模塊實現(xiàn)集合的抽象數(shù)據類型；3）有序表單元模塊實現(xiàn)有序表的抽象數(shù)據類型；4）結點結構單元模塊定義有序表的結點結構。各模塊之間的調用關系如下：三、詳細設計1元素類型、結點類型和指針類型typedef char ElemType ； /元素類型typedef struct NodeType ElemType data； NodeTy

14、pe *next； NodeType, *LinkType； /結點類型，指針類型status MakeNode(LinkType &p，ElemType e)/分配由p指向的數(shù)據元素為e、后繼為“空”的結點，并返回TRUE，/ 若分配失敗，則返回FALSEP = (LinkType)malloc(sizeof(NodeType);if (!p) return FALSE;p-> data = e；p->next = NULL；return TRUE；void FreeNode(LinkType &p)/釋放p所指結點LinkType Copy ( LinkType

15、 p)/復制生成和指針p所指結點有同值元素的新結點并返回，/若分配空間失敗，則返回空指針。新結點的指針域為NULLs = (LinkType)malloc(sizeof(NodeType)；if (!s) return NULL；s->data = p -> data； s->next = NULL； return s;ElemType Elem(LinkType p)/若指針p！ NULL，則返回p所指結點的數(shù)據元素，否則返回#LinkType SuccNode(LinkType p)/若指針p！NULL，則返回指向p所指結點的后繼元素的指針，/否則返回NULL2.根據有序

16、表的基本操作的特點，有序表采用有序鏈表實現(xiàn)。鏈表設頭、尾兩個指針和表長數(shù)據域，并附設頭結點，頭結點的數(shù)據域沒有實在意義。typedef struct LinkType head，tail； /分別指向線性鏈表的頭結點和尾結點int size； / 指示鏈表當前的長度 Orderedlist； / 有序鏈表類型有序鏈表的基本操作設置如下：bool InitList(OrderedList &L)； /構造一個帶頭結點的空的有序鏈表L，并返回TRUE； / 若分配空間失敗，則令L.head為NULL，并返回FALSEvoid DestroyList(OrderedList &L)；

17、 / 銷毀有序鏈表Lbool ListEmpty(OrderedList L)； /若L不存在或為“空表”，則返回TRUE，否則返回FALSEint ListLength(OrderedList L)； /返回鏈表的長度LinkType GetElemPos(OrderedList L, int pos)；/ 若L存在且0<pos<L.size1，則返回指向第pos個元素的指針，/否則返回NULLbool LocateElem (OrderedList L，ElemType e，LinkType &q)；/ 若有序鏈表L存在且表中存在元素e，則q指示L中第一個值為e的/結點

18、的位置，并返回TRUE；否則q指示第一個大于e的元素的前驅的/位置，并返回FALSEvoid Append (OrderedList &L， LinkType s)；/ 在已存在的有序鏈表L的末尾插入指針s所指結點void InsertAfter(OrderList &L，LinkType q， LinkType s )；/ 在已存在的有序鏈表L中q所指示的結點之后插入指針s所指結點void ListTraverse(LinkType p, status(*visit)(LinkType q)；/從p(p！NULL )指示的結點開始，依次對每個結點調用函數(shù)visit其中部分操作

19、的偽碼算法如下：BOOL InitList(OrderedList &L)if(MakeNode(head,' ') / 頭結點的虛設元素為空格符 L.tail = L.head；L.size = 0；return TRUE;else L.head =NULL； return FALSE；/InitListvoid DestroyList(OrderedList &L)p = L.head；while(p)q = p； p = SuccNode(p)；FreeNode(q)；L.head = L.tail = NULL； /DestroylistLinkType

20、 GetElemPos(OrderedList L，int pos) if(! L.head | pos<1 | pos>L.size) return NULL; else if ( pos = = L.size ) return L.tail ； else p = L.head->next；k=1； while ( p && k<pos) p=SuccNode(p)； k+； return p； /GetElemPosstatus LocateElem( OrderedList L， ElemType e， LinkType &p) if (

21、L.head ) pre = L.head ； p =pre->next； /pre 指向*p的前驅，p指向第一個元素結點while ( p &&p->data<e )pre = p； p = SuccNode(p)；if ( p&&p->data= =e) return TRUE；else p=pre；return FALSE；else return FALSE；/LocateElemvoid Append (OrderedList &L，LinkType s) if ( L.head && s) if ( L.

22、tail != L.head ) L.tail->next = s ；else L.head->next = s；L.tail=s；L.size+； /Appendvoid InsertAfter(OrderList &L，LinkType q，LinkType s ) if ( L.head && q && s ) s->next = q->next；q-> next= s；if (L.tail= =q)L.tail = s； L.size+； /InsertAftervoid ListTraverse(Link Type

23、 p，status(*visit)(LinkType) while(p) visit(p)； p=SuccNode(p)；/ ListTraverse3. 集合Set 利用有序鏈表類型OrderedList 來實現(xiàn)，定義為有序集OrderedSet：typedef OrderedList OrderedSet；集合類型的基本操作的類C偽碼描述如下：void CreateSet( OrderedSet & T, char *s)/生成由串s中小寫字母構成的集合T，IsLower是小寫字母判別函數(shù)if（InitList（T） /構造空集T for (i=1； i<=length(s)

24、； i+)if (islower(si) &&! LocateElem(T，si，p)/ 過濾重復元素并按字母次序大小插入if（MakeNode(q，si)）InsertAfter(T，p，q)；/ CreateSetvoid DestroySet (OrderedSet & T)/銷毀集合T的結構DestroyList(T)；/ DestroyListvoid Union(OrderedSet &T，OrderedSet S1， OrderedSet S2 )/求已建成的集合S1和S2的并集T，即：S1.Head!=NULL 且 S2.head!= NULLi

25、f（InitList(T)）p1=GetElemPos(S1，1)； P2=GetElemPos(S2，1)； while(p1 &&p2) c1= Elem(p1)； c2= Elem(p2)；if(c1<=c2) Append(T，Copy(p1)； p1=SuccNode(p1)；if(c1= =c2) p2=SuccNode(p2)； else Append(T，Copy(p2)；p2=SuccNode(p2)；while (p1) Append(T，Copy(p1)；p1=SuccNode(p1)；while (p2) Append(T，Copy(p2)；p2=

26、SuccNode(p2)；/Unionvoid Intersection(OrderedSet &T，OrderedSet S1，OrderedSet S2) /求集合S1和S2的交集Tif (!InitList(T) T.head=NULL；else p1=GetElemPos(S1，1)；p2=GetElemPos(S2，1)；while (p1&&p2) c1=Elem(p1)；c2=Elem(p2)；if (c1<c2) p1= SuccNode(p1)；else if (c1>c2) p2=SuccNode(p2)；else /c1= =c2App

27、end(T，Copy(p1)；p1= SuccNode(p1)；p2=SuccNode(p2)；/else/while/else/Intersectionvoid Difference(OrderedSet &T，OrderedSet S1，OrderedSet S2 )/求集合S1和S2的差集Tif (!InitList(T) T.head=NULL；else p1=GetElemPos(S1，1)；p1=GetElemPos(S2，1)；while (p1&&p2) c1=Elem(p1)；c2=Elem(p2)；if (c1<c2) Append(T，Cop

28、y(p1)；p1= SuccNode(p1)；else if (c1>c2) p2=SuccNode(p2)；else / c1= =c2 p1= SuccNode(p1)；p2=SuccNode(p2)； /whilewhile (p1) Append(T，Copy(p1)；p1= SuccNode(p1)；/else/Differencevoid WriteSetElem(LinkType p)/顯示集合的一個元素printf(',')；writeElem (Elem (p)；/WriteSetElemvoid PrintSet(OrderedSet T)/顯示集合的

29、全部元素p=GetElemPos(T，1)；printf('')；if(p)WriteElem(Elem(p)；p=SuccNode(p)；ListTraverse(p，WriteSetElem)；printf('')；/PrintSet4.主函數(shù)和其他函數(shù)的偽碼算法void main()/主函數(shù)Initialization()；/初始化do ReadCommand(cmd)；/讀入一個操作命令符Interpret(cmd)； /解釋執(zhí)行操作命令符 while(cmd !='q'&&cmd !='Q')；/main

30、void Initialization() /系統(tǒng)初始化Clrscr()； /清屏在屏幕上方顯示操作命令清單：MakeSet1-1 MakeSet2-2 Union-u Intersaction-i Difference-d Quit-q；在屏幕下方顯示操作命令提示框；CreateSet（Set1， “ ”）； PrintSet（Set1）； /構造并顯示空集Set1CreateSet（Set2， “ ”）； PrintSet（Set1）； /構造并顯示空集Set2 /Initializationvoid ReadCommand(char crmd)/讀入操作命令符顯示鍵入操作命令符的提示信息

31、；do cmd=getche( )；while （cmd1,2,u,U,i,I,d,D,q,Q）)；void Interpret( char cmd) /解釋執(zhí)行操作命令cmd switch (cmd) case 1：顯示以串的形式鍵入集合元素的提示信息； scanf（v）；/讀入集合元素到串變量v CreateSet(Set1, v)； PrintSet（Set1）；/構造并顯示有序集Set1 break； case 2： 顯示以串的形式鍵入集合元素的提示信息； scanf（v）；/讀入集合元素到串變量v CreateSet(Set2, v)； PrintSet（Set2）；/構造并顯示有序

32、集Set2 case u，U：Union（Set3, Set1, Set2）； 有序集Set1和Set2的并集Set3 PrintSet（Set3）； /顯示并集Set3 DestroyList（Set3）； /銷毀并集Set3 break； case i，I：Intersaction（Set3，Set1，Set2）； /求有序集Set1和Set2的交集Set3 PrintSet（Set3）； DestroyList（Set3）； break； case d,D：Difference（Set3，Set1，Set2）； /求有序集Set1和Set2的差集Set3 PrintSet（Set3）；

33、DestroyList（Set3）； /Interpret5. 函數(shù)的調用關系圖反映了演示程序的層次結構：四、調試分析1由于對集合的三種運算的算法推敲不足，在有序鏈表類型的早期版本未設置尾指針和Append操作，導致算法低效。2剛開始時曾忽略了一些變量參數(shù)的標識“&”，使調試程序時費時不少。今后應重視確定參數(shù)的變量和賦值屬性的區(qū)分和標識。3本程序的模塊劃分比較合理，且盡可能將指針的操作封裝在結點和鏈表的兩個模塊中，致使集合模塊的調試比較順利。反之，如此劃分的模塊并非完全合理，因為在實現(xiàn)集合操作的編碼中仍然需要判別指針是否為空。按理，兩個鏈表的并、交和差的操作也應封裝在鏈表的模塊中，而在

34、集合的模塊中，只要進行相應的應用即可。4算法的時空分析1）由于有序表采用帶頭結點的有序單鏈表，并增設尾指針和表的長度兩個標識，各種操作的算法時間復雜度比較合理。InitList，ListEmpty，ListLength，Append和InsertAfter以及確定鏈表中第一個結點和之后一個結點的位置都是O(1)的，DestroyList，LocateElem和TraverseList及確定鏈表中間結點的位置等則是O(n)的，n為鏈表長度。2）基于有序鏈表實現(xiàn)的有序集的各種運算和操作的時間復雜度分析如下：構造有序集算法CreateSet讀入n個元素，逐個用LocateElem判定不在當前集合中及確定插入位置后，才用InsertAfter插入到有序集中，所以時間復雜度是O()。求并集算法Union利用集合的“有序性”將兩個集合的m+n個元素不重復地依次利用Append插入到當前并集的末尾，故可在O(m+n)時間內完成?？蓪η蠼患惴↖ntersection和求差集算法Difference作類似地分析，它們也是O(m+n