數(shù)據(jù)結構線性表實驗報告

1、精選優(yōu)質文檔-傾情為你奉上數(shù)據(jù)結構實驗報告院系 應用科技學院 專業(yè) 電子信息工程 姓名 陳高雪 學號410 級 電信 班 2011 年 10 月 11日1.實驗目的1.掌握線性表的基本運算。2.掌握順序村存儲的概念，學會對順序存儲數(shù)據(jù)結構進行操作。3.加深對順序存儲數(shù)據(jù)結構的理解，逐步培養(yǎng)解決實際問題的編程能力。2.需求分析要求用c語言編寫一個演示程序，首先建立一個空表，然后根據(jù)用戶選擇，能夠在線性表的任意位置實現(xiàn)插入元素、刪除元素、初始化線性表、查找某一元素的在線性表中得位置。（1）建立線性表的功能l 輸入的形式和輸入的范圍：調用出入函數(shù)，輸入插入的位置和數(shù)值，用逗號隔開l 輸出的形式：調用

2、輸出函數(shù)，按順序輸出線性表所插入的值，以及所對應功能的值。（2）插入功能l 輸入的形式和輸入值的范圍：輸入一個表示位置的正整數(shù)和一個表示插入元素值的正整數(shù)，兩個正整數(shù)之間用逗號隔開，出入位置的和法取值范圍是1<size<size+1。l 輸出的形式：如果輸入的參數(shù)合法，則按順序顯示插入后的線性表，否則顯示錯誤。（3）刪除功能l 輸入的形式和輸入值的范圍：輸入一個表示刪除位置或要刪除的元素值的正整數(shù)，刪除位置或刪除元素值的取值范圍是1<sizee<size+1或線性表中的元素，否則顯示參數(shù)錯誤的信息。l 輸出的形式：如果輸入?yún)?shù)合法，則按順序顯示刪除后線性表中的各個元素值

3、，否則顯示參數(shù)錯誤的信息。（4）查找功能l 輸入的形式和輸入值的范圍：輸入一個要查找的元素值，元素值的合法取值范圍是正整數(shù)。l 輸出的形式：如果存在要查找的元素，則顯示要查找元素的位置，否則顯示參數(shù)錯誤信息。3.概要設計（1）為了實現(xiàn)上述程序功能，需要第一一個簡化的線性表抽象數(shù)據(jù)類型：Typedef struct LinearListInt *list;Int size;Int MAXSIZE;List; 基本操作：l 初始化線性表ListInit (L)操作前提：L是一個未初始化的線性表操作結果：將L初始化成一個空的線性表l 向空表指定位置插入元素 ListInsert (L)操作前提：L是

4、一個還有位置的線性表操作結果：將元素插入到指定位子并輸出線性表l 刪除指定元素值 ListDelete_1（L）操作前提：線性表L存在操作結果：將線性表中指定的元素值刪除，并輸出線性表l 刪除指定位置的元素值 ListDelete_2（L）操作前提：線性表L存在操作結果：將線性表中指定位置的元素值刪除，并輸出線性表l 查找線性表中的元素 ListFind（L）操作前提：線性表L存在操作結果：在線性表L中查找指定元素e，若存在該元素返回該元素在表中的位置，否則提示錯誤l 輸出線性表元素 OutputList(L)操作前提：線性表存在操作結果：輸出整線性表L的所有元素值（2）本程序共有6函數(shù)：l

5、主函數(shù)main()l 初始化線性表函數(shù)InitList()l 輸出函數(shù)OutputList()l 插入函數(shù)ListInsert()l 刪除函數(shù)ListDelete()l 查找函數(shù)ListFind()各函數(shù)的關系如下：l 主函數(shù)Main()調用初始化線性表函數(shù)InitList()、插入函數(shù)ListInsert()、刪除函數(shù)ListDelete()、查找函數(shù)ListFind()、查找函數(shù)ListFind()l 插入函數(shù)ListInsert()調用輸出函數(shù)OutputList(L)l 刪除函數(shù)ListDelete()調用輸出函數(shù)OutputList(L)l 查找函數(shù)ListFind()調用輸出函數(shù)O

6、utputList(L)（3）主函數(shù)的偽碼Main()定義一個字符參數(shù) ch;定義整形元素位置參數(shù) i；定義整形參數(shù)e,j=1;說明一個線性表L;循環(huán)做下面處理，直到讀入的為y時推出：根據(jù)具體選項，讀入需要的數(shù)據(jù)，做下面的選擇處理，知道循環(huán)結束：根據(jù)所選擇選項調用相關的函數(shù)進行處理，然后輸出處理后的線性表以及所要執(zhí)行的內(nèi)容。4.詳細設計采用線性表實現(xiàn)概要設計中的定義的抽象數(shù)據(jù)類型，有關數(shù)據(jù)數(shù)據(jù)類型和偽碼算法定義如下：（1）類型定義typedef struct LinearListint *list; int size;int MAXSIZE;List;（2）基本操作的偽碼算法l 初始化void

7、 InitList(List &L)構造一個空表L； 定義空表長度為0； 初始存儲空間的容量；l 插入操作void ListInsert(List &L, int i, int e)Int *p；判斷位置i是否合法 不合法返回空；判斷當前容量是否已滿申請一個新的基止newbase;L.list=newbase;增加存儲容量； 定義插入位置*q； p>=q; -p) *(p+1) = *p; 插入元素e；表長加1；l 刪除操作int ListDelete_1(List &L, int e, int &i)定義三個指針*p,*q,*m;P=L.list;循環(huán)做

8、下面處理If(*p=e);m=p;q=L.list+L.size-1;被刪除元素之后的元素左移；表長減1；continue;p+; i+; return 1；l 查找操作int ListFind(List L, int e) /*在順序線性表L中查找第1個值與e滿足compare()的元素的位序。 若找到，則返回其在L中的位序，否則返回0。*/定義第一元素的存儲位置為1；P=首元素的地址；While（i不能超過表長）+I;if (i <= L.size) return i; else return 0;5.使用說明程序名為實驗1.exe，程序執(zhí)行過程如下：運行程序顯示如下菜單：print

9、f("ttt -線 性 表- n");printf("nttt*");printf("nttt* 1-初 始 化 *");printf("nttt* 2-插入元數(shù)值 *");printf("nttt* 3-刪除指定元素值 *");printf("nttt* 4-刪除指定位置 *");printf("nttt* 5-查找線性表中的元素 *");printf("nttt* 6-輸出線性表元素 *");printf("nttt* 0

10、-退 出 *");printf("nttt*n");printf("請選擇菜單號(0-6): "); 用戶輸入06的數(shù)字，選擇執(zhí)行相應的功能。每執(zhí)行一次功能，就會顯示執(zhí)行的結果以及執(zhí)行后線性表的內(nèi)容。l 選擇0：提示是否退出程序，輸入y退出，輸入n返回菜單。l 選擇1：初始化線性表l 選擇2：提示“請輸入位置i和數(shù)值e：”，要求用戶輸入一個表示插入元素位置的和一個表示插入元素的正整數(shù)，兩個數(shù)之間用空格隔開。如果插入合法，按順序輸出線性表，否則提示錯誤！l 選擇3： 提示“請輸入要刪除的元素值e：”，要求用戶輸入一個表示刪除元素的正整數(shù)， 刪除元

11、素的合法范圍是正整數(shù)。如果輸入?yún)?shù)合法，按順序輸出線性表，否則提示錯誤！l 選擇4：提示“請輸入要刪除的指定位置i:”， 要求用戶輸入一個表示刪除位置的正整數(shù)， 刪除位置的合法范圍是1到當前線性表的長度。如果輸入?yún)?shù)合法，按順序輸出線性表，否則提示錯誤！l 選擇5：提示“請輸入線性表中要查找的元素e:”，要求用戶輸入一個要查找的元素值，元素的合法范圍是正整數(shù)。如果輸入元素值合法，輸出所查找元素值在線性表中的位置，否則提示錯誤！l 選擇6：直接輸出整個線性表。6.測試結果程序運行顯示一下菜單：-線 性 表- * 1-初 始 化 * 2-插入元數(shù)值 * 3-刪除指定元素值 * 4-刪除指定位置 *

12、 5-查找線性表中的元素 * 6-輸出線性表元素 * 0-退 出 *請選擇菜單號(0-6): （1）初始化操作：l 選擇1初始化線性表屏幕提示“初始化成功！”再次提示選擇菜單（2）插入操作：l 選擇2屏幕提示“請輸入位置i和數(shù)值e:”輸入1 1屏幕顯示輸出線性表元素:1 插入成功！屏幕顯示選擇菜單l 選擇2屏幕提示“請輸入位置i和數(shù)值e:”輸入2 2屏幕顯示輸出線性表元素:1 插入成功！屏幕顯示選擇菜單l 選擇2屏幕提示“請輸入位置i和數(shù)值e:”輸入3 3屏幕顯示輸出線性表元素:1 插入成功！屏幕顯示選擇菜單l 選擇2屏幕提示“請輸入位置i和數(shù)值e:”輸入5 5屏幕顯示插入位置錯誤！輸出線性表元素:1 屏幕顯示選擇菜單（3）刪除指定元素值操作：l 選擇3屏幕提示“請輸入要刪除的元素值e:” 輸入2后， 屏幕顯示輸出線性表：1 3刪除成功！再次顯示選擇菜單l 選擇4屏幕提示“請輸入要刪除的指定位置i:” 輸入1后， 屏幕顯示輸出線性表：3刪除成功！再次顯示選擇菜單（4）刪除指定位置元素操作：l 選擇4屏幕顯示“請輸入要刪除的指定位置i:”輸入2屏幕顯示刪除成功！輸出線性表元素有：1 3（5）查找操作：l 選擇5屏幕顯示“請輸入線性表中要查找的元素e:”輸入3，屏幕顯示該元數(shù)值在線