線性表的順序結(jié)構(gòu)及其應(yīng)用

1、廣西工學(xué)院計(jì)算機(jī)學(xué)院 數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告書 實(shí)驗(yàn)一 線性表的順序表結(jié)構(gòu)及其應(yīng)用 學(xué)生姓名：李四 學(xué)號(hào)： 2012 班級(jí)： 計(jì) Y124 指導(dǎo)老師：王日鳳 專業(yè)： 計(jì)算機(jī)學(xué)院軟件學(xué)院 提交日期： 2013年 6 月 18 日 1實(shí)驗(yàn)?zāi)康?1）熟練掌握線性表的基本操作在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。 （2）用線性表的鏈?zhǔn)讲僮鲗?shí)現(xiàn)線性表的合并。 2. 實(shí)驗(yàn)內(nèi)容 1）要求用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。然后實(shí)現(xiàn)如下操作： 初始化線性表 建立一個(gè)含 n 個(gè)數(shù)據(jù)的線性表，用頭插法或尾插法。 查找：輸入一個(gè)數(shù)， 查找線性表， 若有，則輸出“查找成功” ，否則輸 出“無此數(shù)” （流程圖） 插入：輸入一個(gè)數(shù)和插入位置，實(shí)現(xiàn)插入操作，

2、并顯示插入成功。 刪除：輸入一個(gè)位置數(shù)，刪除該位置上的數(shù)，并顯示刪除成功。 （流程圖） 2）線性表的合并，已知兩個(gè)升序線性表，要求合并成一個(gè)新的升序線性表。 3實(shí)驗(yàn)要求 1） 上機(jī)前交實(shí)驗(yàn)源程序（紙質(zhì)版） ，由學(xué)習(xí)委員統(tǒng)一收好交老師（附上不交同學(xué)名 單）。 2） 用一切你能想到的辦法解決遇到的問題，培養(yǎng)解決問題的能力。 3）實(shí)驗(yàn)報(bào)告（于本周五下午） 報(bào)告內(nèi)容包括 ：實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)代碼、實(shí)驗(yàn)輸入輸出結(jié)果以及實(shí)驗(yàn) 體會(huì)供五部分。 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如下： #define LIST_INIT_SIZE 100;/ 存儲(chǔ)空間初始分配量 #define LISTINCREMENT 10;/

3、存儲(chǔ)空間分配增量 typedef struct LNode ElemType data; / 存儲(chǔ)空間基址 Struct LNode *next;/當(dāng)前長度 LNode, *LinkList; 3主要算法 3.1 順序存儲(chǔ)結(jié)構(gòu) (1)結(jié)構(gòu)定義： #include #include #include #include / 各頭文件 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAXSIZE 100 typedef int ElemType; / 定義宏參 / 定義靜態(tài)表存儲(chǔ)結(jié)構(gòu) typedef struct int elemM

4、AXSIZE; / 定義數(shù)據(jù)類型 int length; / 記錄當(dāng)前長度 SqList; /=各函數(shù)聲明 =/ void InitList(SqList / 建立線性表 int ListLength(SqList L);/ 計(jì)算表的長度 int ListEmpty(SqList L); / 判斷表是否為空 int ListInsert(SqList / 插入數(shù)字 int search(SqList L); / 查找元素 int ListDelete(SqList / 刪除元素 void print(SqList L); / 輸出元素 void ListClear(SqList / 清空表 i

5、nt priorElem(SqList L,ElemType e); / 求前驅(qū) int NextElem(SqList L,ElemType e); / 求后驅(qū) void MergeList_Sq(SqList La,SqList Lb,SqList / 合并 void ListClear(SqList / 清空線性表 void ListSort(SqList / 元素排序 /=各函數(shù)聲明 =/ / 建立線性表 void InitList(SqList L.length=0; / 初始化長度為 printf( 初始化完成 !n ); printf( 請(qǐng)輸入你要儲(chǔ)存數(shù)據(jù)的長度： ); scan

6、f( %d, L.length=n; for (i=1;i=L.length;i+) / 依次賦值 printf(請(qǐng)輸入第個(gè)數(shù)據(jù)：,i); scanf( %d, printf( 輸入完成 !n ); printf( 新列表為： ); print(L); / 輸出函數(shù) printf( n ); / 計(jì)算線性表長度 int ListLength(SqList L) / 初始條件 : 線性表 L 已存在 / 操作結(jié)果 : 返回線性表的長度值 return L.length; / 判斷線性表是否為空 int ListEmpty(SqList L) / 初始條件 : 線性表 L 已存在 / 操作結(jié)果 :

7、 若長度為返回，否則返回 if (L.length=0) return 1; else return 0; / 插入數(shù)字 int ListInsert(SqList printf( 請(qǐng)輸入您要插入的位置： ); scanf( %d, if (iL.length) printf( 您要插入的位置獄界 ! ); printf( n ); return ERROR; if (L.lengthMAXSIZE) printf( 序表上溢： ); return ERROR; printf( 請(qǐng)輸入您要插入的數(shù)字： ); scanf( %d, q= for (p=p=q;-p) *(p+1)=*p; *q=

8、a; +L.length; printf( 插入成功 !n ); printf( 新列表為： ); print(L); printf( n ); / 查找數(shù)字 int search(SqList L) / 初始條件 : 線性表 L 已存在 / 操作結(jié)果 : 若查找成功返回和輸出位置，否則返回 int num,i; printf( 查找數(shù)字 !n ); printf( 請(qǐng)輸入你要查找的數(shù)字： ); scanf( %d, for (i=0;i=L.length;i+) if (num=L.elemi) printf( 查找成功！ n ); printf( 數(shù)據(jù)的位置為 : %d ,i); retu

9、rn 1; printf( 無此數(shù) !n ); printf( n ); return 0; / 元素定位 int locateElem(SqList L,ElemType e) / 初始條件 : 線性表 L 已存在 / 操作結(jié)果:若定位成功返回位置 i ，否則返回 int i; for (i=1;i=L.length;i+) if (e=L.elemi) return i; return 0; / 求元素前驅(qū) int priorElem(SqList L,ElemType e) / 初始條件 : 線性表 L 已存在 / 操作結(jié)果 : 若查找成功返回和輸出前驅(qū)元素，否則返回 int i,pre

10、; i=locateElem(L,e); if (i) if (i=1) printf( 這是第一個(gè)元素，沒有前驅(qū) !n ); return 0; else pre=L.elemi-1; printf(所查元素啲前驅(qū)為：%d ,e,pre); return 1; else printf( 表中無此元素 !n ); return 0; / 求元素后驅(qū) int NextElem(SqList L,ElemType e) / 初始條件 : 線性表 L 已存在 / 操作結(jié)果 : 若查找成功返回和輸出后驅(qū)元素，否則返回 int i,next; i=locateElem(L,e); if (i) if (

11、i=L.length) printf( 這是最后一個(gè)元素，沒有后驅(qū) !n ); return 0; else next=L.elemi+1; printf(所查元素啲后驅(qū)為：%d ,e,next); return 1; else printf( 表中無此元素 !n ); return 0; / 刪除元素 int ListDelete(SqList printf( 請(qǐng)輸入您要?jiǎng)h除的數(shù)字的位置數(shù)： ); scanf( %d, if (i+1L.length) printf(刪除失敗!n); return ERROR; p= q=L.elem+L.length; for (+p;p=q;+p) *(

12、p-1)=*p; -L.length; printf( 刪除成功 !n ); printf( 新列表為： ); print(L); printf( n ); / 輸出元素 void print(SqList L) / 初始條件 : 線性表 L 已存在 / 操作結(jié)果 : 輸出線性表中的所有元素 int i; for (i=1;i=L.length;i+) printf( %d ,L.elemi); return ; / 清空線性表 void ListClear(SqList for (i=1;i=L.length;i+) L.elemi= 0 ; L.length=0; return ; / 線

13、性表合并 void MergeList_Sq(SqList La,SqList Lb,SqList while (i=La.length else Lc.elemk+=Lb.elemj+; while (i=La.length) Lc.elemk+=La.elemi+; while (j=Lb.length) Lc.elemk+=Lb.elemj+; Lc.length=k-1; / 元素排序 void ListSort(SqList for (i=1;i=L.lengthi+) flag=0; for (j=0;jL.elemj+1) L.elem0=L.elemj; L.elemj=L.e

14、lemj+1; L.elemj+1=L.elem0; / 主函數(shù) void main() SqList L,La,Lb,Lc; ElemType e; int j, k; while (1) system( printf( printf( printf( cls ); / 清屏 ); ); ); nt* nt* 線性表的順序結(jié)構(gòu)及其應(yīng)用 nt*n printf( t * 1. 建立線性表 2. 插入數(shù)字 *n printf( t * 3. 查找數(shù)字 4. 刪除數(shù)字 * n printf( t * 5. 順序表長度 6. 順序表空否 * n printf( t * 7. 數(shù)據(jù)合并 8. 數(shù)字排序

15、 * n printf( t * 9. 清空序表 0. 返回 *n printf( t*n II printf( scanf( 請(qǐng)選擇選項(xiàng)( -9): ); %d, ); ); ); ); ); ); if (k10) printf( printf( printf( getch(); continue ; switch (k) case 1: 輸入有誤，請(qǐng)重新輸入 ! ); n ); nttt 按任意鍵進(jìn)行重新操作 ! ); InitList(L); printf( n ); printf( nttt 按任意鍵進(jìn)行重新操作 ! ); getch(); break ; case 2: print

16、f( 插入數(shù)字 !n ); ListInsert(L); printf( n ); printf( nttt 按任意鍵進(jìn)行重新操作 ! ); getch(); break ; case 3: printf( 你要查找的是 : 1. 元素的位置 2. 元素的前驅(qū) 3. 元素的后 驅(qū) n ); printf( 請(qǐng)選擇項(xiàng) : ); scanf( %d, if (j=1) search(L); if (j=2) printf( 請(qǐng)輸入查找元素： ); scanf( %d, priorElem(L,e); if (j=3) printf( 請(qǐng)輸入查找元素： ); scanf( %d, NextElem(

17、L,e); printf( n ); printf( nttt 按任意鍵進(jìn)行重新操作 ! ); getch(); break ; case 4: printf( 刪除數(shù)字 !n ); ListDelete(L); printf( n ); printf( nttt 按任意鍵進(jìn)行重新操作 ! ); getch(); break ; case 5: printf( 計(jì)算線性表的長度 ?n ); j=ListLength(L); printf( 線性表的長度為 :%d ,j); printf( n ); printf( nttt 按任意鍵進(jìn)行重新操作 ! ); getch(); break ; ca

18、se 6: printf( 判斷線性表是否為空 ?n ); j=ListEmpty(L); if (j=1) printf( 線性表為空 ! ); else printf( 線性表不為空 ! ); printf( n ); printf( nttt 按任意鍵進(jìn)行重新操作 ! ); getch(); break ; case 7: system( cls ); / 清屏 printf( La 和 Lb合并!n); printf(請(qǐng)輸入La的數(shù)據(jù)!n); InitList(La); printf( n ); printf(請(qǐng)輸入Lb的數(shù)據(jù)!n); InitList(Lb); printf( n )

19、; MergeList_Sq(La,Lb,Lc); printf( La和Lb合并成功!n); printf( La 和 Lb合并后為：)； print(Lc); printf( n )； printf( nttt 按任意鍵進(jìn)行重新操作 ! )； getch()； break； case 8： printf(數(shù)字排序!n); printf(排序前： )； print(L); printf(n ); ListSort(L); printf( 排序成功 !n ); printf( 排序后 ： ); print(L); printf( n ); printf( nttt 按任意鍵進(jìn)行重新操作 ! )

20、; getch(); break; case 9： printf( 你真確定要清空序表 ! 1.YES 2.NOn); printf( 請(qǐng)選擇項(xiàng) ： ); scanf( %d, if (j=1) ListClear(L); printf(清空序表成功呦 !n ); if (j=2) printf(n ); printf(nttt按任意鍵進(jìn)行重新操作 ! ); getch(); break; case 0： printf( 你真確定要退出 ! 1.YES 2.NOn); printf( 請(qǐng)選擇項(xiàng) ： ); scanf( %d, if (j=1) printf(nttt 再見，歡迎再次使用 !nnttt); exit(OVERFLOW); - 10 - if (j= printf( printf( getch(); break; 3.流程圖 n); nttt按任意鍵進(jìn)行重新操作!); 開始 存在返回 if語句 存在前驅(qū)返 回元素 順序表不為 空 輸入元素 if語句 不存在, 返回0 / / 存在后驅(qū)返回 兀素 返