【正文】 The genral stf(1mpoyidvc,uh)0jb。5wT 仲 愷 農(nóng) 業(yè) 工 程 學(xué) 院 課 程 設(shè) 計(jì) 報(bào) 告 課程名稱 ： 數(shù) 據(jù) 結(jié) 構(gòu) 院（系） ： 專 業(yè) ： 班 級 ： 學(xué) 號 ： 姓 名 ： 指導(dǎo)老師 ： The genral stf(1mpoyidvc,uh)0jb。5wT 目 錄 1順序表 ............................................................ 1 2鏈表 .............................................................. 6 3棧和隊(duì)列 ......................................................... 12 4樹和二叉樹 ....................................................... 18 5圖 ............................................................... 24 6查找和排序 ....................................................... 29 課程設(shè)計(jì)總結(jié) ...................................................... 33 參 考 文 獻(xiàn) .................................................... 33 The genral stf(1mpoyidvc,uh)0jb。5wT 1 順序表 2 題 設(shè)線性表存于 A[1..size]的前 num 各分量中，且遞增有序。請?jiān)O(shè)計(jì)一個(gè)算法，將 x 插入到線性表的適當(dāng)位置上，以保持線性表的有序性。 一、 數(shù)據(jù)結(jié)構(gòu)說明 線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。 假設(shè)線性表的每個(gè)元素需占用 L個(gè)存儲單元，并以所占的第一個(gè)單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第 i+1 個(gè)數(shù)據(jù)元素的存儲位置 LOC(ai+1)和第 i 個(gè)數(shù)據(jù)元素的存儲位置 LOC(ai)之間滿足下列關(guān)系： LOC(ai+1)=LOC(ai)+L 一般來說，線性表的第 i個(gè)數(shù)據(jù)元素 ai 的存儲位置為 LOC(ai) = LOC(a1)+(i1) * L 式中 LOC(a1)是線性表的第一個(gè)數(shù)據(jù)元素 a1的存儲位置，通常稱做線性表的起始位置或基地址。 線性表的這種機(jī)內(nèi)表示稱做線性表的順序存儲結(jié)構(gòu)或順序映象 (Sequential Mapping)，反之，稱這種存儲結(jié)構(gòu)的線性表為順 序表。 它的特點(diǎn)是，為表中相鄰的元素 ai和 ai+1賦以相鄰的存儲位置 LOC(ai)和 LOC(ai+1)。換句話說，以元素在計(jì)算機(jī)內(nèi) “ 物理位置相鄰 ” 來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。 順序表存儲結(jié)構(gòu) ： 用一段地址連續(xù)的存儲單元依次存儲線性表中的數(shù)據(jù)元素 圖 1 順序表存續(xù)結(jié)構(gòu)示意圖 二、 順序表 的 存儲結(jié)構(gòu) 設(shè)計(jì) typedef struct { ElemType *data。//存儲空間基址 int length。//當(dāng)前長度 int size。//當(dāng)前分配的存儲容量 (以 sizeof(ElemType))為單位 }SqList。 a1 ?? a1i ai a1i? ?? an 空閑 The genral stf(1mpoyidvc,uh)0jb。5wT2 三、算法設(shè)計(jì)（程序流程圖） 圖 2 順序表課程設(shè)計(jì)流程圖 四、詳細(xì)設(shè)計(jì) include include include /* exit() */ include define LIST_INIT_SIZE 100/*線性表存儲空間的初始分配量 */ define LISTINCREMENT 2/*線性表存儲空間的分配增量 */ typedef int ElemType。 typedef struct { ElemType *data。//存儲空間基址 int length。//當(dāng)前長度 int size。//當(dāng)前分配的存儲容量 (以 sizeof(ElemType))為單位 開始 有序順序表 L1 元素 e2 輸入數(shù)據(jù)賦給 e2 把 e2 插入有序順序表L1 的適當(dāng)位置 輸出有序順序表 L1 結(jié)束 The genral stf(1mpoyidvc,uh)0jb。5wT3 }SqList。 /*函數(shù)結(jié)果狀態(tài)代碼 */ define TRUE 1 define FALSE 0 define OK 1 define ERROR 0 define INFEASIBLE 1 define OVERFLOW 2/*因?yàn)樵? 中已定義 OVERFLOW 的值為 3,故去掉此行 */ typedef int Status。/*Status 是函數(shù)的類型 ,其值是函數(shù)結(jié)果狀態(tài)代碼，如 OK 等 */ typedef int Boolean。/*Boolean 是布爾類型 ,其值是 TRUE 或 FALSE*/ Status InitList(SqList amp。L) { /*操作結(jié)果：構(gòu)造一個(gè)空的順序線性表 */ =(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType))。 if(! ) exit(OVERFLOW)。/*存儲分配失敗 */ =0。/*空表長度為 0*/ =LIST_INIT_SIZE。/*初始存儲容量 */ return OK。 } Status InsertOrderList(SqList amp。L,ElemType x) { //順序表 L 中的元素依值遞增有序，本算法將 x 插入其中適當(dāng)位置 //以保持其有序性。入口斷言： 0== int i,j。 if(==) return (OVERFLOW)。 else { i=。 while(i=0amp。amp。x[i]) i。 for(j=。j=i+1。j) [j+1]=[j]。 The genral stf(1mpoyidvc,uh)0jb。5wT4 [i+1]=x。 ++。 return OK。 } } Status ListTraverse(SqList L) { /*初始條件：順序線性表 L已存在 */ /*操作結(jié)果：依次對 L 的每個(gè)數(shù)據(jù)元素訪問并輸出 */ ElemType *p。 int i。 p=。 for(i=1。i=。i++) printf(%d , *p++)。 printf(\n)。 return OK。 } void main() { SqList L1。 ElemType e1,e2。 int i,n。 printf(順序表 第 2 題 \n)。 InitList(L1)。//初 始化順序表 printf(給順序表長度賦值 n=)。 scanf(%d,amp。n)。//通過鍵盤輸入為順序表長度賦值 printf(輸入元素 :\n)。 for(i=1。i=n。i++) { The genral stf(1mpoyidvc,uh)0jb。5wT scanf(%d,amp。e1)。//通過鍵盤輸入為 e 賦值 InsertOrderList(L1,e1)。//調(diào)用 InsertOrderList 函數(shù)，在 L 中遞增插入新的數(shù)據(jù)元素e1 } printf(有序遞增順序表為 :)。 ListTraverse(L1)。//依次對 L 的每 個(gè)數(shù)據(jù)元素訪問并輸出 printf(輸入一個(gè)元素并把它插入表中 \n)。 scanf(%d,amp。e2)。 InsertOrderList(L1,e2)。//調(diào)用 InsertOrderList 函數(shù)，在有序遞增順序表 L 中有序插入新的數(shù)據(jù)元素 e2 printf(新有序遞增順序表為 :)。 ListTraverse(L1)。//依次對 L 的每個(gè)數(shù)據(jù)元素訪問并輸出