【正文】 1 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計論文 題目： ** 7 .建立二叉樹，層序、先序遍歷 14. 拓?fù)渑判? 姓名： 李東東 學(xué)號： 202010510212 班級： 11 計科（ 2） 班 指導(dǎo)教師： 李娟 徐星 2020 年 6 月 24 日 2 系統(tǒng) 開發(fā)目的 數(shù)據(jù)結(jié)構(gòu)旨在使讀者學(xué)會分析研究數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)的組織方法，以便選擇合適的數(shù) 據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，以及相應(yīng)的運算，把現(xiàn)實世界中的問題轉(zhuǎn)化為計算機內(nèi)部的表示和處理。 設(shè)計目的 進(jìn) 一步理解和掌握課堂上所學(xué)各種基本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和操作實現(xiàn)算法，以及它們在程序中的使用方法；掌握軟件設(shè)計的基本內(nèi)容和設(shè)計方法，并培養(yǎng)規(guī)范化軟件設(shè)計的能力； 將理論知識和實際結(jié)合起來，鍛煉分析解決實際問題的能力 。 設(shè)計要求 實現(xiàn)通訊錄的建立和輸出、通訊者的插入、刪除和查詢等幾種操作功能。 用單鏈表作存儲結(jié)構(gòu)；用菜單作為應(yīng)用程序的主要界面，主界面的主控菜單 如下 ： 通訊錄鏈表 ************************************ ************************************ 請選擇菜單號 0~5： *： 使用數(shù)字 0~5 來選擇菜單項，其他輸入 無效 ，并給出錯誤提示。 設(shè)計功能 程序運行后的功能有： （ 1）菜單選擇界面 （ 2）建立通訊錄記錄 （ 3）插入聯(lián)系人記錄 （ 4）查找聯(lián)系人記錄（名稱和編號查詢） （ 6）刪除聯(lián)系人記錄 （ 7）輸出 所有聯(lián)系人記錄 （ 8）退出程序 算法設(shè)計 系統(tǒng)流程圖 如圖所示： 開始 是否繼續(xù) 添加 主菜單 插入信息 查詢記錄 刪除記錄 輸出記錄 退出 添加各項信息 建立通訊鏈表 是否 已建表 是否 已建表 是否 已建表 是否 已建表 Y Y Y Y 添加各 項信息 插入成功 主菜單 查詢方式 按編號查找 按姓名查找 a b 是否 存在記錄 Y 確定刪除 Y 刪除成功 N N 查詢完畢 N N N N 成功輸出 是否退出 N 退出程序 結(jié)束 3 主函數(shù)設(shè)計 由于主函數(shù)設(shè)計的是菜單選擇項，所以在程序未退出的的情況下要實現(xiàn)循環(huán)運行，并且要考慮到未建立通訊錄鏈表的情況下其他功能無法實現(xiàn)的情況。故在實現(xiàn)循環(huán)運行的功能時定義一個變量 j=1，在選擇退出后再將 j 賦值為 0，要考慮判定是否建表的情況定義了一個全局變量 flag1=0，建鏈表后 flag1 賦值為 1。 為了達(dá)到選擇各功能 ,采用 switch 判定選擇項并跳轉(zhuǎn)入相應(yīng)功能函數(shù)。 判定是否建表語句 : if(flag1!=1) {printf(請先建立表 !)。 getchar()。 system(cls)。} 功能程序設(shè)計 為了達(dá)到程序各項功能的實現(xiàn)，以及滿足菜單選擇項的功能，對每個功能的實現(xiàn)分別用了不同函數(shù)，并且有用到函數(shù)的嵌套以減少代碼的重復(fù)。 建立通訊鏈表設(shè)計 要建立鏈表，首先要生成結(jié)點，因此，尾插法建立鏈表算法描述如下： （ 1）使鏈表的頭尾指針 head、 rear 指向新生成的頭結(jié)點（也就是尾結(jié)點）； （ 2）置結(jié)束標(biāo)志為 0（假）； （ 3） while(結(jié)束標(biāo)志不為真 ) ｛ P 指向新生成的結(jié)點； 讀入一個通訊者數(shù)據(jù)至新結(jié)點的數(shù)據(jù)域； 將新結(jié)點鏈到尾結(jié)點之后； 主函數(shù)設(shè)計 主函數(shù)設(shè)計 主函數(shù)設(shè)計 4 實現(xiàn)循環(huán)運行的功能時定義一個變量 j=1，在選擇退出后再將 j 賦值為 0，要考慮判定是否建表的情況定義了一個全局變量 flag1=0，建鏈表后 flag1 賦值為 1。 為了達(dá)到選擇各功能 ,采用 switch 判定選擇項并跳轉(zhuǎn)入相應(yīng)功能函數(shù)。 判定是否建表語句 : if(flag1!=1) {printf(請先建立表 !)。 getchar()。 system(cls)。} 建立通訊鏈表設(shè)計 要建立鏈表，首先要生成結(jié)點，因此，尾插法建立鏈表算法描述如下： （ 1）使鏈表的頭尾指針 head、 rear 指向新生成的頭結(jié)點（也就是尾結(jié)點）； （ 2）置結(jié)束標(biāo)志為 0（假）； （ 3） while(結(jié)束標(biāo)志不為真 ) ｛ P 指向新生成的結(jié)點； 讀入一個通訊者數(shù)據(jù)至新結(jié)點的數(shù)據(jù)域； 將新結(jié)點鏈到尾結(jié)點之后； 使尾指針指向新結(jié)點； 提示是否繼續(xù)建表，讀入一個結(jié)束的標(biāo)志； ｝ （ 4）尾結(jié)點的指針域置空置 NULL。 具體算法實現(xiàn)如下： /*******尾插法建立帶頭結(jié)點的通訊錄鏈表算法 *******/ LinkList CreateList(void) { LinkList head=(ListNode *)malloc(sizeof(ListNode))。 /*申請頭結(jié)點*/ ListNode *p,*rear。 char flag=39。y39。 //int flag=0。 /*結(jié)束標(biāo)志置 0*/ rear=head。 /*尾指針初始指向頭結(jié)點 */ while (flag==39。y39。) { 5 p=(ListNode *)malloc(sizeof(ListNode))。 /*申新結(jié)點 */ printf(編號 (4) 姓名 (8) 性別 電話 (11) 地址 (31)\n)。 printf(\n)。 printf(\n 添加的編號 :\n)。 scanf(%s,p)。 printf(\n 添加的姓名 :\n)。 scanf(%s,p)。 printf(\n 性別 :\n)。 scanf(%s,p)。 printf(\n 電話 :\n)。 scanf(%s,p)。 printf(\n 地址 :\n)。 scanf(%s,p)。 rearnext=p。 /*新結(jié)點連接到尾結(jié)點之后 */ rear=p。 /*尾指針指向新結(jié)點 */ printf(繼續(xù)建表 ?(y/n):)。 scanf(%s,amp。flag)。 } rearnext=NULL。 /*終端結(jié)點指針置空 */ return head。 /*返回鏈表頭指針 */ } 通訊者結(jié)點信息的插入 鏈表結(jié)點的插入，要求將一個通訊者記錄的數(shù)據(jù)結(jié)點按其編號的次序插入有序通訊表相應(yīng)位置，以保持通訊錄的有序性。插入的基本思想是：使用兩個指針變量 p1 和 p2分別指向當(dāng)前訪問過的結(jié)點和下一個結(jié)點，循環(huán)順序查找鏈表。尋找插入結(jié)點的位置，其中 p1指向待插入位置的前一個結(jié)點。具體實現(xiàn)算法如下： （ 1）用 p1 指向原鏈表頭結(jié)點， p2 指向 鏈表的第一個結(jié)點； （ 2） while(p2!=NULL amp。amp。 strcmp(p2,p)0) { p1=p2。 /*p1 指向剛訪問過的結(jié)點 */ p2=p2next。 /*p2 指向下一個結(jié)點 */ } (3)插入新結(jié)點。具體算法如下： /*********在通訊錄鏈表 head 中插入結(jié)點 ************/ 6 void InsertNode(LinkList head,ListNode *p) { ListNode *p1,*p2。 p1=head。 p2=p1next。 while(p2!=NULL amp。amp。 strcmp(p2,p)0) { p1=p2。 /*p1 指向剛訪問過的結(jié)點 */ p2=p2next。 /*p2 指向表的下一個結(jié)點 */ } p1next=p。 /*插入 p所指向的結(jié)點 */