1、順序表實驗報告 一、 實驗內(nèi)容和目的實驗?zāi)康模赫莆枕樞虮淼慕ⅰ⒉檎?、插入和刪除操作。 掌握有序表的建立、合并、插入操作。實驗內(nèi)容：1. 順序表的建立 2. 順序表的遍歷 3. 順序表的元素查找 4. 順序表的元素插入 5. 順序表的元素刪除 6. 有序表的建立 7. 有序表的遍歷 8. 有序表的元素插入 9. 有序表的合并二、 實驗原理基本原理：通過連續(xù)的地址空間實現(xiàn)邏輯上和物理上連續(xù)的儲存的一系列元素。并在此基礎(chǔ)上進行元素的添加，查找，刪除操作。有序表的插入算法：元素插入之前的，先跟有序表中的逐個元素進行對比，以找到合適的插入位置。例如，已有有序表L，要向 L 中插入元素 18L=13,1

2、5,17,19,20,35,40第一步：將18與L1進行比較，18 L1，不是合適的插入位置。第二步：將18與L2進行比較，18L2，仍然不是不是的插入位置。重復(fù)上述步驟，知道找到18Ln，然后在 (n-1) 和n之間插入元素。（如果元素比有序表中的所有元素都要大，則把該元素放到有序表的最后）此例子中，Ln-1 = 17，Ln = 19插入元素之后的有序表L為：L=13,15,17,18,19,20,35,40仍然保持有序。重置光標的位置：程序接受兩種方式的輸入。一種是輸入數(shù)字后按回車，一種是利用空格間隔的連續(xù)幾個數(shù)字。然而，在使用后者輸入數(shù)字的時候，會出現(xiàn)提示輸出不正確的問題。（如圖） 這個

3、問題的原因簡單如下： 當程序輸出“請輸入第2個數(shù)字：”的時候，應(yīng)該等待用戶輸入；然而，在程序等待輸入第一個數(shù)字的時候，用戶輸入了五個數(shù)字。因此，程序輸出“輸入第2個提示以后”，程序發(fā)現(xiàn)仍然有數(shù)據(jù)沒有進行處理，因此把上次輸入但未處理的字符當成是用戶的輸入。所以沒讓用戶輸入數(shù)據(jù)就自動繼續(xù)執(zhí)行。 解決這個問題的思路： 每次輸出提示時，將光標移動到行首，因此，輸出提示的時候會自動覆蓋已經(jīng)輸出的提示信息。效果如下：具體的解決方法：#include / 將光標移動到行首void ResetCursor()HANDLE hOut;COORD cTarget;CONSOLE_SCREEN_BUFFER_INF

4、O info;int y = 0;hOut = GetStdHandle(STD_OUTPUT_HANDLE);GetConsoleScreenBufferInfo(hOut, &info);y = info.dwCursorPosition.Y;cTarget.X = 0;cTarget.Y = y;SetConsoleCursorPosition(hOut, cTarget);三、 程序流程圖四、 實現(xiàn)步驟4.1 創(chuàng)建順序表的實現(xiàn) 通過 scanf 函數(shù)從鍵盤中讀入數(shù)據(jù)，并通過scanf函數(shù)的返回值判斷用戶輸入的是數(shù)字還是非數(shù)字，作為判斷輸入結(jié)束的判斷。 如果讀入的是數(shù)字，向順序表結(jié)構(gòu)中的

5、數(shù)組添加該數(shù)字，并將順序表結(jié)構(gòu)的長度變量加一；如果讀入的是非數(shù)字，停止要求用戶輸入，順序表的創(chuàng)建結(jié)束。 4.2 順序表遍歷的實現(xiàn) 獲取順序表的長度L，通過一個for循環(huán)，對順序表的每一個元素進行相應(yīng)的操作。（演示程序中的是輸出操作） 4.3 順序表查找的實現(xiàn) 在遍歷的基礎(chǔ)上，對順序表中每個元素與輸入的元素進行對比，如果元素相等，則返回該元素的下標。如果整個順序表遍歷，均未發(fā)現(xiàn)與其相等的元素，則說明該元素不存在于該順序表中，返回錯誤信息。4.4 順序表插入的實現(xiàn) 由用戶輸入要插入的元素和插入的位置。執(zhí)行插入操作之前先對用戶輸入的位置信息有效性進行檢查。 如果用戶輸入的位置信息是有效的，則先把插入

6、位置以后的數(shù)據(jù)自后向前的方向進行后移，再把元素插入到順序表中。 如果用戶輸入的位置信息是無效的，則返回錯誤信息。 4.5 順序表刪除的實現(xiàn) 由用戶輸入要刪除的元素位置。先對位置信息進行有效性檢查。 如果用戶輸入的位置是有效的，則把刪除位置后面的元素從前至后的方向向前移動（要刪除元素會被下一個元素覆蓋，從而起到跟刪除等效的操作）。 如果用戶輸入的位置是無效的，則返回錯誤信息。 4.6 有序表的創(chuàng)建 見“實驗原理” 4.7 有序表的遍歷 同“順序表的遍歷” 4.8 有序表的元素插入 同“實驗原理” 4.9 有序表創(chuàng)建和合并操作 創(chuàng)建原理見“實驗原理” 合并操作：定義兩個指針p1，p2，分別指向有序

7、表L1和L2的元素。先通過p1和p2比較兩者的大小，把小的數(shù)字放到一個新的有序表中（新有序表的創(chuàng)建同樣遵循實驗原理中描述的算法），直到其中一個有序表的元素全部放到新的有序表里。然后，再把剩下有序表的元素依次放到新的有序表里面。五、 實驗結(jié)果5.1 程序主菜單5.2 順序表創(chuàng)建（接受兩種輸入方式）5.3 順序表遍歷輸出5.4 順序表查找（找到和沒找到的兩種情況）5.5 順序表元素插入5.6 順序表元素刪除5.7 有序表創(chuàng)建5.8 有序表遍歷輸出5.9 有序表元素插入5.10 創(chuàng)建有序表并合并第一步：創(chuàng)建第一個有序表第二步：創(chuàng)建第二個有序表第三步：合并兩個有序表六、 操作說明6.1 進入主菜單以后

8、，要演示順序表的操作（插入，查找，刪除）需要先建立順序表。在創(chuàng)建順序表以前選擇這些操作會有錯誤信息。（有序表也相同）6.2 創(chuàng)建有序表或者順序表時，結(jié)束的標記是非數(shù)字字符。即輸入非數(shù)字字符即可結(jié)束數(shù)據(jù)的輸入流程。6.3 程序?qū)Υ蟛糠值妮斎刖M行檢查。確保輸入數(shù)據(jù)的有效性。七、 附錄：代碼#include #include #include / 屏蔽VC+ 08 scanf 函數(shù)不安全的警告信息#pragma warning(disable:4996)#define MAXSIZE 100/ 順序表的最大元素個數(shù)#define OK 0/ 表示成功操作#define LIST_FULL -2/

9、表示順序表已滿#define INDEX_OUT_OF_RANGE -3/ 表示要操作的位置超出有效范圍typedef int ElemType;/ 順序表的元素類型typedef struct list ElemType elem MAXSIZE ;int length; SqList;/* 順序表基本操作的函數(shù)實現(xiàn)*/ 順序表的初始化void InitList(SqList *L)L-length = 0;/ 在順序表末尾添加新的元素int ListAppend(SqList *L, ElemType e)/ 添加元素之前先檢查順序表能否繼續(xù)添加元素if ( L-length = MAXS

10、IZE )return LIST_FULL;L-elem L-length = e;L-length+;return OK;/ 返回e 在順序表L 中的位置（如果e 不存在于順序表中，則返回0）int ListIndexOf(SqList L, ElemType e)int i, l;/ 獲得順序表L 的長度l = L.length;/ 如果順序表為空表，返回錯誤信息if (l = 0)return 0;for (i = 0; i = l)return 0;else return (i + 1);/ 向順序表某個特定的位置添加元素int ListInsert(SqList *L, int i,

11、 ElemType e)int k;/ 檢查i 的有效性，如果i 為無效值，則返回錯誤信息if (!(i = 1 & i length + 1)return INDEX_OUT_OF_RANGE;/ 檢查順序表能否繼續(xù)添加數(shù)據(jù)if (L-length = 100)return LIST_FULL;/ 將數(shù)據(jù)后移for ( k = L-length - 1; k = (i - 1); k- )L-elemk + 1 = L-elemk;L-elemi - 1 = e;L-length+;return OK;/ 刪除順序表中某個特定位置的元素int ListDelete(SqList *L, in

12、t i, ElemType *e)int k;/ 刪除前檢查位置的有效性if (!(i = 1 & i length)return INDEX_OUT_OF_RANGE;/ 刪除前將值賦給e*e = L-elemi - 1;/ 把刪除以后的數(shù)據(jù)全部向前移動for (k = i - 1; k length; k+)L-elemk = L-elemk + 1;L-length-;return OK;/* 具體功能的函數(shù)實現(xiàn)*/ 將光標移動到行首void ResetCursor()HANDLE hOut;COORD cTarget;CONSOLE_SCREEN_BUFFER_INFO info;in

13、t y = 0;hOut = GetStdHandle(STD_OUTPUT_HANDLE);GetConsoleScreenBufferInfo(hOut, &info);y = info.dwCursorPosition.Y;cTarget.X = 0;cTarget.Y = y;SetConsoleCursorPosition(hOut, cTarget);/ 從鍵盤輸入數(shù)據(jù)創(chuàng)建順序表void CreateSqList(SqList *L)ElemType e;/ 創(chuàng)建順序表之前先進行初始化操作InitList(L);/ 清屏system(cls);printf(請輸入要放到順序表中的數(shù)

14、字（輸入非數(shù)字字符結(jié)束輸入過程）n);printf(請輸入第%d 個數(shù)字：, L-length + 1);/ 當用戶輸入非數(shù)字時，scanf 函數(shù)無法讀入，返回0，因此可以作為判斷條件while ( scanf(%d, &e) != 0 ) / 如果ListAppend 返回順序表已滿的錯誤信息時，函數(shù)終止。if ( ListAppend(L, e) = LIST_FULL )printf(順序表已滿！n);system(pause);return; ResetCursor();printf(請輸入第%d 個數(shù)字：, L-length + 1);printf(n順序表創(chuàng)建成功！n);syste

15、m(pause);/ 以行的形式輸出順序表或者有序表void ListPrintSimple(SqList L)int i; for (i = 0; i 0)for (i = 1; i length + 1);/ 清空輸入緩沖區(qū)fflush(stdin);/ 檢查輸入數(shù)據(jù)的有效性if ( scanf(%d, &tmp) = 0 )printf(無效輸入！n);system(pause);return;/ 判斷輸入位置是否超出有效范圍if (tmp = 1 & tmp length + 1)printf(請輸入要插入的元素（只接受整數(shù)輸入）：);/ 檢查輸入數(shù)據(jù)的有效性if ( scanf(%d

16、, &i) = 0)printf(無效輸入！n);system(pause);return;k = ListInsert(L, tmp, i);/ 對ListInsert 函數(shù)的返回值進行分析switch (k)case INDEX_OUT_OF_RANGE:printf(插入位置超出有效范圍！n);break;case LIST_FULL:printf(順序表已滿，不能再向其中添加數(shù)據(jù)n);break;case OK:printf(成功向順序表添加元素：%dn, i);break;system(pause);return;else printf(插入位置超出有效范圍！n);system(pa

17、use);return;/ 從順序表中刪除某個特定位置的元素void Delete(SqList *L)int i, e;system(cls);printf(輸入要刪除的元素位置(1 %d)：, L-length);/ 檢查輸入數(shù)據(jù)的有效性if ( scanf(%d, &i) = 0)printf(無效輸入！n);system(pause);return;/ 檢查輸入數(shù)據(jù)的有效性if (i = 1 & i length)if (ListDelete(L, i, &e) = OK)printf(成功刪除元素：%dn, e);elseprintf(刪除元素失??！n);system(pause);

18、return;elseprintf(刪除位置超出有效范圍！n);system(pause);return;/ 利用有序表插入算法創(chuàng)建有序表int CreateSortedList(SqList *L)int i;ElemType e;/ 對有序表L 進行初始化操作InitList(L);printf(請輸入要放進有序表的元素（輸入非數(shù)字字符結(jié)束輸入）n);printf(請輸入第%d 個元素：, L-length + 1);while ( scanf(%d, &e) != 0 )/ 如果順序表已滿，輸出錯誤信息if (L-length = 100)return LIST_FULL;/ 如果是第一

19、個元素，則放到有序表的第一個位置if (L-length = 0)ListInsert(L, 1, e);else/ 輸入的元素與有序表中的元素進行大小比較，找到適合的插入位置for (i = 0; i length; i+)if (e elemi)ListInsert(L, i+1, e);break;/ 如果輸入的元素均大于有序表的所有元素，則放在有序表的最后if (i = L-length)ListInsert(L, i+1, e);/ 將光標移動到行首ResetCursor();printf(請輸入第%d 個元素：, L-length + 1);printf(n成功建立有序表！n);s

20、ystem(pause);return OK;/ 通過有序表插入算法創(chuàng)建兩個有序表，再對其進行合并操作void CreateAndUnion()SqList La, Lb;/ 兩個有序表SqList Lc;/ 存放合并以后的有序表int lenLa, lenLb;/ 記錄兩個有序表的長度ElemType *ptrA, *ptrB;/ 兩個指針，用于合并有序表檢索數(shù)據(jù)system(cls);printf(現(xiàn)在創(chuàng)建第一個有序表n);/ 如果第一個有序表創(chuàng)建失敗if (CreateSortedList(&La) != OK)printf(第一個有序表創(chuàng)建失敗，函數(shù)終止！n);system(pause

21、);return;fflush(stdin);printf(現(xiàn)在創(chuàng)建第二個有序表n);/ 如果第二個有序表創(chuàng)建失敗if (CreateSortedList(&Lb) != OK)printf(第二個有序表創(chuàng)建失敗，函數(shù)終止！n);system(pause);return;system(cls);printf(合并前的有序表：);printf(nLa: n);ListPrintSimple(La);printf(n);printf(Lb: n);ListPrintSimple(Lb);printf(n);/ 獲取兩個有序表的長度lenLa = La.length;lenLb = Lb.lengt

22、h;/ 如果合并后有序表大小超過100if (lenLa + lenLb 100)printf(合并后有序表大小超過100n);system(pause);return;/ Lc 初始化InitList(&Lc);/ 定位ptrA ptrB 指針ptrA = La.elem;ptrB = Lb.elem;while (ptrA - La.elem) lenLa) & (ptrB - Lb.elem) = *ptrB)ListAppend(&Lc, *ptrB);ptrB+;elseListAppend(&Lc, *ptrA);ptrA+;while (ptrA - La.elem) lenLa

23、)ListAppend(&Lc, *ptrA);ptrA+;while (ptrB - Lb.elem) length = 100)printf(有序表已滿！n);system(pause);return;printf(請輸入要插入到有序表的元素：);/ 輸入的字符為非整數(shù)時if ( scanf(%d, &e) = 0 )printf(無效輸入！n);system(pause);return;/ 跟原有有序表中的元素逐個進行大小比較for (i = 0; i length; i+)if (e elemi)ListInsert(L, i+1, e);break;/ 如果從鍵盤讀入的元素均大于原有

24、序表中的元素/ 把新的元素放在有序表的最后if (i = L-length)ListInsert(L, L-length+1, e);printf(成功向有序表中插入元素%dn, e);system(pause);return;void main()char ch;int LStatus = 0, SLStatus = 0;/ 記錄順序表或有序表的建立狀態(tài)/ 避免在建立前進行遍歷操作引起錯誤SqList L, SL;while (1)system(cls);/ 清屏printf(n);printf( 順序表演示程序n);printf(nn);printf( 1. 建立順序表n);printf( 2. 遍歷順序表（輸出順序表）n);printf( 3. 查找順序表n);printf( 4. 順序表元素插入n);printf( 5. 順序表元素刪除n);printf(n);printf( 6. 有序表創(chuàng)建n);printf( 7. 有序表遍歷（有序表輸出）n);printf( 8. 有序表元素插入n);printf( 9. 創(chuàng)建有序表并進行合并n);printf(n);printf( Q. 退出程序nn);printf( 請選