实验一顺序表实验报告

1、顺序表实验报告 一、 实验内容和目的实验目的：掌握顺序表的建立、查找、插入和删除操作。 掌握有序表的建立、合并、插入操作。实验内容：1. 顺序表的建立 2. 顺序表的遍历 3. 顺序表的元素查找 4. 顺序表的元素插入 5. 顺序表的元素删除 6. 有序表的建立 7. 有序表的遍历 8. 有序表的元素插入 9. 有序表的合并二、 实验原理基本原理：通过连续的地址空间实现逻辑上和物理上连续的储存的一系列元素。并在此基础上进行元素的添加，查找，删除操作。有序表的插入算法：元素插入之前的，先跟有序表中的逐个元素进行对比，以找到合适的插入位置。例如，已有有序表L，要向 L 中插入元素 18L=13,1

2、5,17,19,20,35,40第一步：将18与L1进行比较，18 L1，不是合适的插入位置。第二步：将18与L2进行比较，18L2，仍然不是不是的插入位置。重复上述步骤，知道找到18Ln，然后在 (n-1) 和n之间插入元素。（如果元素比有序表中的所有元素都要大，则把该元素放到有序表的最后）此例子中，Ln-1 = 17，Ln = 19插入元素之后的有序表L为：L=13,15,17,18,19,20,35,40仍然保持有序。重置光标的位置：程序接受两种方式的输入。一种是输入数字后按回车，一种是利用空格间隔的连续几个数字。然而，在使用后者输入数字的时候，会出现提示输出不正确的问题。（如图） 这个

3、问题的原因简单如下： 当程序输出“请输入第2个数字：”的时候，应该等待用户输入；然而，在程序等待输入第一个数字的时候，用户输入了五个数字。因此，程序输出“输入第2个提示以后”，程序发现仍然有数据没有进行处理，因此把上次输入但未处理的字符当成是用户的输入。所以没让用户输入数据就自动继续执行。 解决这个问题的思路： 每次输出提示时，将光标移动到行首，因此，输出提示的时候会自动覆盖已经输出的提示信息。效果如下：具体的解决方法：#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);三、 程序流程图四、 实现步骤4.1 创建顺序表的实现 通过 scanf 函数从键盘中读入数据，并通过scanf函数的返回值判断用户输入的是数字还是非数字，作为判断输入结束的判断。 如果读入的是数字，向顺序表结构中的

5、数组添加该数字，并将顺序表结构的长度变量加一；如果读入的是非数字，停止要求用户输入，顺序表的创建结束。 4.2 顺序表遍历的实现 获取顺序表的长度L，通过一个for循环，对顺序表的每一个元素进行相应的操作。（演示程序中的是输出操作） 4.3 顺序表查找的实现 在遍历的基础上，对顺序表中每个元素与输入的元素进行对比，如果元素相等，则返回该元素的下标。如果整个顺序表遍历，均未发现与其相等的元素，则说明该元素不存在于该顺序表中，返回错误信息。4.4 顺序表插入的实现 由用户输入要插入的元素和插入的位置。执行插入操作之前先对用户输入的位置信息有效性进行检查。 如果用户输入的位置信息是有效的，则先把插入

6、位置以后的数据自后向前的方向进行后移，再把元素插入到顺序表中。 如果用户输入的位置信息是无效的，则返回错误信息。 4.5 顺序表删除的实现 由用户输入要删除的元素位置。先对位置信息进行有效性检查。 如果用户输入的位置是有效的，则把删除位置后面的元素从前至后的方向向前移动（要删除元素会被下一个元素覆盖，从而起到跟删除等效的操作）。 如果用户输入的位置是无效的，则返回错误信息。 4.6 有序表的创建 见“实验原理” 4.7 有序表的遍历 同“顺序表的遍历” 4.8 有序表的元素插入 同“实验原理” 4.9 有序表创建和合并操作 创建原理见“实验原理” 合并操作：定义两个指针p1，p2，分别指向有序

7、表L1和L2的元素。先通过p1和p2比较两者的大小，把小的数字放到一个新的有序表中（新有序表的创建同样遵循实验原理中描述的算法），直到其中一个有序表的元素全部放到新的有序表里。然后，再把剩下有序表的元素依次放到新的有序表里面。五、 实验结果5.1 程序主菜单5.2 顺序表创建（接受两种输入方式）5.3 顺序表遍历输出5.4 顺序表查找（找到和没找到的两种情况）5.5 顺序表元素插入5.6 顺序表元素删除5.7 有序表创建5.8 有序表遍历输出5.9 有序表元素插入5.10 创建有序表并合并第一步：创建第一个有序表第二步：创建第二个有序表第三步：合并两个有序表六、 操作说明6.1 进入主菜单以后

8、，要演示顺序表的操作（插入，查找，删除）需要先建立顺序表。在创建顺序表以前选择这些操作会有错误信息。（有序表也相同）6.2 创建有序表或者顺序表时，结束的标记是非数字字符。即输入非数字字符即可结束数据的输入流程。6.3 程序对大部分的输入均进行检查。确保输入数据的有效性。七、 附录：代码#include #include #include / 屏蔽VC+ 08 scanf 函数不安全的警告信息#pragma warning(disable:4996)#define MAXSIZE 100/ 顺序表的最大元素个数#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;/* 顺序表基本操作的函数实现*/ 顺序表的初始化void InitList(SqList *L)L-length = 0;/ 在顺序表末尾添加新的元素int ListAppend(SqList *L, ElemType e)/ 添加元素之前先检查顺序表能否继续添加元素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;/ 检查顺序表能否继续添加数据if (L-length = 100)return LIST_FULL;/ 将数据后移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;/ 把删除以后的数据全部向前移动for (k = i - 1; k length; k+)L-elemk = L-elemk + 1;L-length-;return OK;/* 具体功能的函数实现*/ 将光标移动到行首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);/ 从键盘输入数据创建顺序表void CreateSqList(SqList *L)ElemType e;/ 创建顺序表之前先进行初始化操作InitList(L);/ 清屏system(cls);printf(请输入要放到顺序表中的数

14、字（输入非数字字符结束输入过程）n);printf(请输入第%d 个数字：, L-length + 1);/ 当用户输入非数字时，scanf 函数无法读入，返回0，因此可以作为判断条件while ( scanf(%d, &e) != 0 ) / 如果ListAppend 返回顺序表已满的错误信息时，函数终止。if ( ListAppend(L, e) = LIST_FULL )printf(顺序表已满！n);system(pause);return; ResetCursor();printf(请输入第%d 个数字：, L-length + 1);printf(n顺序表创建成功！n);syste

15、m(pause);/ 以行的形式输出顺序表或者有序表void ListPrintSimple(SqList L)int i; for (i = 0; i 0)for (i = 1; i length + 1);/ 清空输入缓冲区fflush(stdin);/ 检查输入数据的有效性if ( scanf(%d, &tmp) = 0 )printf(无效输入！n);system(pause);return;/ 判断输入位置是否超出有效范围if (tmp = 1 & tmp length + 1)printf(请输入要插入的元素（只接受整数输入）：);/ 检查输入数据的有效性if ( scanf(%d

16、, &i) = 0)printf(无效输入！n);system(pause);return;k = ListInsert(L, tmp, i);/ 对ListInsert 函数的返回值进行分析switch (k)case INDEX_OUT_OF_RANGE:printf(插入位置超出有效范围！n);break;case LIST_FULL:printf(顺序表已满，不能再向其中添加数据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);/ 检查输入数据的有效性if ( scanf(%d, &i) = 0)printf(无效输入！n);system(pause);return;/ 检查输入数据的有效性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;/ 利用有序表插入算法创建有序表int CreateSortedList(SqList *L)int i;ElemType e;/ 对有序表L 进行初始化操作InitList(L);printf(请输入要放进有序表的元素（输入非数字字符结束输入）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;/ 通过有序表插入算法创建两个有序表，再对其进行合并操作void CreateAndUnion()SqList La, Lb;/ 两个有序表SqList Lc;/ 存放合并以后的有序表int lenLa, lenLb;/ 记录两个有序表的长度ElemType *ptrA, *ptrB;/ 两个指针，用于合并有序表检索数据system(cls);printf(现在创建第一个有序表n);/ 如果第一个有序表创建失败if (CreateSortedList(&La) != OK)printf(第一个有序表创建失败，函数终止！n);system(pause

21、);return;fflush(stdin);printf(现在创建第二个有序表n);/ 如果第二个有序表创建失败if (CreateSortedList(&Lb) != OK)printf(第二个有序表创建失败，函数终止！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(请输入要插入到有序表的元素：);/ 输入的字符为非整数时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;/ 记录顺序表或有序表的建立状态/ 避免在建立前进行遍历操作引起错误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. 有序表创建n);printf( 7. 有序表遍历（有序表输出）n);printf( 8. 有序表元素插入n);printf( 9. 创建有序表并进行合并n);printf(n);printf( Q. 退出程序nn);printf( 请选