1、12級軟件設計大作業題 目概念圖難度系數 0.7成 績 班 級 011213完成者1學號01121345姓名 楊英杰完成者2學 號01121278 姓 名 曹偉完成者3學號01121289姓名 趙漢卿完成日期2014.6.22（若是多人合作，填寫下面的內容，給出所有合作者的信息） 姓名：楊英杰主要完成的工作：線性表、棧和隊列、數組和串姓名：曹偉主要完成的工作：圖、索引、散列姓名：趙漢卿主要完成的工作：樹、緒論、算法設計與分析 一、軟件系統名稱完整線性表輸出。二、軟件分析與設計1、問題分析：線性表內容包含兩部分，分別是字母（表示下個鏈表）和數字。因此鏈表中節點 需要包含指向下一個節點或下個鏈表的

2、指針等多個數據類型。系統輸入：線性表名稱（字母）和線性表內容（數字） 。系統輸出：線性表（包括線性表名稱和線性表內容）。總功能：可在原有鏈表基礎上不斷添加數字或新鏈表，并顯示每個鏈表的內容及整體鏈表的內 容。2、測試樣例在程序輸入均含有提示，如果輸入錯誤，會導致重新輸入，不會直接退出程序。 輸入包含：輸入提示測試樣例預期結果請輸入需要添加的鏈表名稱（輸入END標）END退出C （已在線性表中的鏈表字母）顯布卜個輸入Sg或D或12 （任何/、是線性 表字母的輸入）輸入有誤，請重新輸入請輸入數字或新鏈表名稱（輸 入end結束）end退出132 （數字）或Q （未保存在線 性表中的鏈表字母）顯布卜個

3、輸入Ass或46s （小止常輸入）輸入有誤，請重新輸入3、全局變量包括：所有鏈表的指針和表示鏈表指針數目的數字變量；用語構成隊列的數組指 針和表示表示隊列的兩個變量front和rear。4、模塊分類創建鏈表模塊函數名稱：CreateList函數參數：鏈表名稱 name函數功能：生成鏈表返回值：鏈表頭指針偽代碼描述：定義頭指針；分配節點空間；節點數據初始化（鏈表名 =name）;返回頭指針初始化模塊函數名稱：InitList函數參數：無函數功能：鏈表初始化返回值：無偽代碼描述：在鏈表中原有鏈表中插入數字和鏈表；新鏈表的插入數字和鏈表；插入鏈表模塊函數名稱：AtLast函數參數：鏈表頭指針函數功能

4、：尋找鏈表中最后指針返回值：最后指針偽代碼描述：While （下一個節點指針不空） 指向下一個節點指針返回函數名稱：InsertNumber函數參數：鏈表頭指針，數字函數功能：鏈表中插入數字返回值：新節點指針偽代碼描述：尋找最后指針；分配節點空間；節點數據初始化；鏈表與節點鏈接返回節點指針函數名稱：InsertList函數參數：鏈表頭指針，要插入鏈表頭指針函數功能：鏈表中插入指針返回值：新鏈表頭指針偽代碼描述：尋找最后指針；分配節點空間；節點數據初始化原鏈表與節點連接節點與要插入鏈表頭指針鏈接返回節點指針數組隊列模塊函數名稱：Qinit函數參數：無函數功能：隊列初始化返回值：無偽代碼描述：fr

5、ont=rear=0函數名稱：push函數參數：指針函數功能：入隊列返回值：無偽代碼描述：指針進入數組front+函數名稱函數參數pop無出隊列函數功能： 返回值：無 偽代碼描述:rear+函數名稱：top函數參數：指針函數功能：返回隊列頭指針返回值：隊列頭指針偽代碼描述：返回隊列頭指針函數名稱：empty函數參數：無函數功能：判斷隊列是否空返回值：bool變量偽代碼描述：隊列空；返回true;Else 返回 false刪除模塊函數名稱：DeleteList函數參數：鏈表頭指針函數功能：釋放線性表空間返回值：無偽代碼描述：隊列初始化；頭指針入隊列While （隊列不空）出隊列并存儲隊首值指向下

6、一個節點If （節點為數字）釋放空間、else指針入隊列并釋放空間顯示模塊函數名稱：Show函數參數：無函數功能：輸出只有數值的完整線性表返回值：無偽代碼描述：顯示線性表字母輸出函數換行函數名稱：ShowL函數參數：指針函數功能：輸出鏈表內容返回值：無偽代碼描述：指向下一個節點If （節點為數字）輸出數字else遞歸調用函數，傳遞此節點指針函數名稱：ShowList函數參數：指針函數功能：輸出線性表內容返回值：無偽代碼描述：隊列初始化；頭指針入隊列While （隊列不空）出隊列并存儲隊首值顯示鏈表頭字母指向下一個節點If （節點為鏈表節點）顯示鏈表頭字母和，入隊列else顯示數字和，輸入模塊函

7、數名稱：NoCreate函數參數：鏈表名稱 name函數功能：判斷隊列是否存在于線性表返回值：bool量偽代碼描述：數組中依次尋找If 找到 false無 返回true函數名稱：Input函數參數：無函數功能：輸入處理返回值：無偽代碼描述：ShowList輸出提示輸入（為字符串）While （輸入不結束）5、流程圖MainIf （輸入合理（為單一字母且已存在線性表）找到線性表中的該鏈表輸出提示輸入（為字符串）While （輸入不結束）If （輸入為新單一字母）新建鏈表并插入，并存儲如全局數組中Else if （為數字）字符串轉化為數字并加入原鏈表中Else提示輸入錯誤提示并重新輸入Else提示

8、輸入錯誤 提示并重新輸入創建鏈表初始化部分輸入鏈表完成輸入完成顯示線性表顯示只有數值的完整線性表三、運行環境codeblocks （建議編譯器為 gcc）。四、軟件使用說明軟件系統輸入以輸出和異常處理均在上述表格中得到。五、源代碼#include#include#include#includeusing namespace std;typedef struct nodebool isList;int number;node *nextNumber,*nextList;char listName;List;typedef struct nodehchar name;List *head;HLis

9、t;HList ListHead100;int Nlisthead=0;List *CreateList(char name);List *AtLast(List *head);List *InsertNumber(List *head,int number);List *InsertList(List *head1,List *head2);void InitList(List *head);void ShowList(List *head);void DeleteList(List *head);void Input();bool NoCreate(char name);void Show

10、();int main()List *head=CreateList(A);InitList(head);Input();Show();DeleteList(head);return 0;List *CreateList(char name) List *head;head=(List *)malloc(sizeof(List);head-listName=name;head-isList=true;head-nextNumber=head-nextList=NULL;return head;List *AtLast(List *head) while(head-nextNumber)head

11、=head-nextNumber; return head;List *InsertNumber(List *head,int number) head=AtLast(head);List *newNode=(List *)malloc(sizeof(List);newNode-isList=false;newNode-number=number;newNode-nextList=newNode-nextNumber=NULL;head-nextNumber=newNode;return newNode;List *InsertList(List *head1,List *head2) hea

12、d1=AtLast(head1);List *newNode=(List *)malloc(sizeof(List);newNode-isList=true;newNode-listName=head2-listName;newNode-nextNumber=NULL;newNode-nextList=head2;head1-nextNumber=newNode;return head2;void InitList(List *head)/A鏈表初始化InsertNumber(head,1);InsertNumber(head,2);InsertNumber(head,3);InsertNum

13、ber(head,4);InsertNumber(head,5);List *head1=CreateList(B);InsertList(head,head1);/B鏈表初始化InsertNumber(head1,7);InsertNumber(head1,8);InsertNumber(head1,9);List *head2=CreateList(C);InsertList(head1,head2);/C鏈表初始化InsertNumber(head2,10);存儲所有鏈表頭指針ListHead0.head=head;ListHead1.head=head1;ListHead2.head=

14、head2;ListH=A;ListH=B;ListH=C;Nlisthead=3;隊列定義及所有操作const int MAXQ=10000;List * ListQueueMAXQ;int front,rear;初始化(隊列清空)void Qinit()front=rear=0;/入隊列void push(List *head)if(frontMAXQ)ListQueuefront+=head;出隊列void pop()rear+;/返回隊首元素List *top()if(rear,temp-listName);temp=temp-ne

15、xtNumber;while(temp)if(temp-isList)printf(%c,temp-listName); push(temp-nextList);if(temp-nextNumber)printf(,);elseprintf(%d,temp-number);if(temp-nextNumber) printf(,);temp=temp-nextNumber;printf(n);判斷一個鏈表名稱是否已被創建bool NoCreate(char name)for(int i=0;i=A&temp10=Z&!temp11)for(int i=0;i=A&temp20=0&temp2jnextNumber;while(templ)if(temp1-isList)push(temp1-nextList);temp2=temp1-nextNumber; free(templ);temp1=temp2;void ShowL(List *head)List *temp=head-nextNumber;while(temp)if(temp-isList)Sho