实验一 顺序表 实验报告

顺序表实验报告

一、 实验内容和目的

实验目的：掌握顺序表的建立、查找、插入和删除操作。

掌握有序表的建立、合并、插入操作。

实验内容：1. 顺序表的建立

2. 顺序表的遍历

3. 顺序表的元素查找

4. 顺序表的元素插入

5. 顺序表的元素删除

6. 有序表的建立

7. 有序表的遍历

8. 有序表的元素插入

9. 有序表的合并

二、 实验原理

基本原理：

通过连续的地址空间实现逻辑上和物理上连续的储存的一系列元素。并在此基础上

进行元素的添加，查找，删除操作。

有序表的插入算法：

元素插入之前的，先跟有序表中的逐个元素进行对比，以找到合适的插入位置。

例如，已有有序表L，要向 L 中插入元素 18

L={13,15,17,19,20,35,40}

第一步：将18与L

1

进行比较，18 > L

1

，不是合适的插入位置。

第二步：将18与L

2

进行比较，18>L

2

，仍然不是不是的插入位置。

重复上述步骤，知道找到18≤Ln，然后在 (n-1) 和n之间插入元素。

（如果元素比有序表中的所有元素都要大，则把该元素放到有序表的最后）

此例子中，L

n-1

= 17，L

n

= 19

插入元素之后的有序表L为：

L

′

={13,15,17,18,19,20,35,40}

仍然保持有序。

重置光标的位置：

程序接受两种方式的输入。一种是输入数字后按回车，一种是利用空格间隔的连续

几个数字。然而，在使用后者输入数字的时候，会出现提示输出不正确的问题。（如图）

这个问题的原因简单如下：

当程序输出“请输入第2个数字：”的时候，应该等待用户输入；然而，在程序等

待输入第一个数字的时候，用户输入了五个数字。因此，程序输出“输入第2个提示以

后”，程序发现仍然有数据没有进行处理，因此把上次输入但未处理的字符当成是用户

的输入。所以没让用户输入数据就自动继续执行。

解决这个问题的思路：

每次输出提示时，将光标移动到行首，因此，输出提示的时候会自动覆盖已经输出

的提示信息。效果如下：

具体的解决方法：

#include

// 将光标移动到行首

void ResetCursor()

{

}

HANDLE hOut;

COORD cTarget;

CONSOLE_SCREEN_BUFFER_INFO info;

int y = 0;

hOut = GetStdHandle(STD_OUTPUT_HANDLE);

GetConsoleScreenBufferInfo(hOut, &info);

y = orPosition.Y;

cTarget.X = 0;

cTarget.Y = y;

SetConsoleCursorPosition(hOut, cTarget);

三、 程序流程图

四、 实现步骤

4.1 创建顺序表的实现

① 通过 scanf 函数从键盘中读入数据，并通过scanf函数的返回值判断用户输入

的是数字还是非数字，作为判断输入结束的判断。

② 如果读入的是数字，向顺序表结构中的数组添加该数字，并将顺序表结构的长

度变量加一；如果读入的是非数字，停止要求用户输入，顺序表的创建结束。

4.2 顺序表遍历的实现

获取顺序表的长度L，通过一个for循环，对顺序表的每一个元素进行相应的操作。

（演示程序中的是输出操作）

4.3 顺序表查找的实现

在遍历的基础上，对顺序表中每个元素与输入的元素进行对比，如果元素相等，

则返回该元素的下标。

如果整个顺序表遍历，均未发现与其相等的元素，则说明该元素不存在于该顺

序表中，返回错误信息。

4.4 顺序表插入的实现

由用户输入要插入的元素和插入的位置。执行插入操作之前先对用户输入的位

置信息有效性进行检查。

如果用户输入的位置信息是有效的，则先把插入位置以后的数据自后向前的方

向进行后移，再把元素插入到顺序表中。

如果用户输入的位置信息是无效的，则返回错误信息。

4.5 顺序表删除的实现

由用户输入要删除的元素位置。先对位置信息进行有效性检查。

如果用户输入的位置是有效的，则把删除位置后面的元素从前至后的方向向前

移动（要删除元素会被下一个元素覆盖，从而起到跟删除等效的操作）。

如果用户输入的位置是无效的，则返回错误信息。

4.6 有序表的创建

见“实验原理”

4.7 有序表的遍历

同“顺序表的遍历”

4.8 有序表的元素插入

同“实验原理”

4.9 有序表创建和合并操作

创建原理见“实验原理”

合并操作：定义两个指针p1，p2，分别指向有序表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 进入主菜单以后，要演示顺序表的操作（插入，查找，删除）需要先建立顺序表。

在创建顺序表以前选择这些操作会有错误信息。（有序表也相同）

6.2 创建有序表或者顺序表时，结束的标记是非数字字符。即输入非数字字符即可结束

数据的输入流程。

6.3 程序对大部分的输入均进行检查。确保输入数据的有效性。

七、 附录：代码

#include

#include

#include

// 屏蔽VC++ 08 scanf 函数不安全的警告信息

#pragma warning(disable:4996)

#define MAXSIZE 100

#define OK 0

// 表示成功操作

// 表示顺序表已满 #define LIST_FULL -2

typedef int ElemType;

{

/** 顺序表基本操作的函数实现**/

// 顺序表的初始化

void InitList(SqList *L)

{

}

// 在顺序表末尾添加新的元素

int ListAppend(SqList *L, ElemType e)

{

}

return OK;

L->elem[ L->length ] = e;

L->length++;

// 添加元素之前先检查顺序表能否继续添加元素

if ( L->length >= MAXSIZE )

return LIST_FULL;

L->length = 0;

ElemType elem[ MAXSIZE ];

int length;

// 顺序表的元素类型

typedef struct list

// 顺序表的最大元素个数

#define INDEX_OUT_OF_RANGE -3 // 表示要操作的位置超出有效范围

} SqList;

// 返回e 在顺序表L 中的位置（如果e 不存在于顺序表中，则返回0）

int ListIndexOf(SqList L, ElemType e)

{

}

// 向顺序表某个特定的位置添加元素

int ListInsert(SqList *L, int i, ElemType e)

{

// 检查顺序表能否继续添加数据

if (L->length >= 100)

// 将数据后移

for ( k = L->length - 1; k >= (i - 1); k-- )

{

return LIST_FULL;

// 检查i 的有效性，如果i 为无效值，则返回错误信息

if (!(i >= 1 && i <= L->length + 1))

return INDEX_OUT_OF_RANGE;

int k;

// 如果没有找到与e 相等的元素

if (i >= l)

return 0;

return (i + 1);

else

for (i = 0; i < l; i++)

{

}

// 如果找到L 中与e 相等的元素，返回元素序号

if ( [i] == e )

{

}

break;

// 如果顺序表为空表，返回错误信息

if (l == 0)

return 0;

// 获得顺序表L 的长度

l = ;

int i, l;

}

}

L->elem[k + 1] = L->elem[k];

L->elem[i - 1] = e;

L->length++;

return OK;

// 删除顺序表中某个特定位置的元素

int ListDelete(SqList *L, int i, ElemType *e)

{

}

/** 具体功能的函数实现**/

// 将光标移动到行首

void ResetCursor()

{

GetConsoleScreenBufferInfo(hOut, &info);

hOut = GetStdHandle(STD_OUTPUT_HANDLE);

HANDLE hOut;

COORD cTarget;

CONSOLE_SCREEN_BUFFER_INFO info;

int y = 0;

L->length--;

return OK;

// 把删除以后的数据全部向前移动

for (k = i - 1; k < L->length; k++)

{

}

L->elem[k] = L->elem[k + 1];

// 删除前将值赋给e

*e = L->elem[i - 1];

// 删除前检查位置的有效性

if (!(i >= 1 && i <= L->length))

return INDEX_OUT_OF_RANGE;

int k;

}

y = orPosition.Y;

cTarget.X = 0;

cTarget.Y = y;

SetConsoleCursorPosition(hOut, cTarget);

// 从键盘输入数据创建顺序表

void CreateSqList(SqList *L)

{

}

// 以行的形式输出顺序表或者有序表

void ListPrintSimple(SqList L)

{

int i;

printf("n顺序表创建成功！n");

system("pause");

}

printf("请输入第%d 个数字：", L->length + 1);

ResetCursor();

// 当用户输入非数字时，scanf 函数无法读入，返回0，因此可以作为判断条件

while ( scanf("%d", &e) != 0 )

{

// 如果ListAppend 返回顺序表已满的错误信息时，函数终止。

if ( ListAppend(L, e) == LIST_FULL )

{

}

printf("顺序表已满！n");

system("pause");

return;

printf("请输入要放到顺序表中的数字（输入非数字字符结束输入过程）n");

printf("请输入第%d 个数字：", L->length + 1);

// 清屏

system("cls");

// 创建顺序表之前先进行初始化操作

InitList(L);

ElemType e;

}

for (i = 0; i < ; i++)

{

}

// 一行输出个元素

if ((i + 1) % 10 == 0)

printf("n");

printf("%4d", [i]);

// 对顺序表进行遍历（输出整个顺序表）

void ListPrint(SqList L)

{

}

// 查找顺序表中的某一个元素的位置

void SearchList(SqList L)

{

int e, i;

}

else

{

}

printf("n 顺序表为空！n");

system("pause");

printf("n 顺序表所有项目已经输出完毕！n");

system("pause");

// 输出前先检查顺序表中是否含有数据

if (l > 0)

{

for (i = 1; i <= l; i++)

{

}

printf(" 第%2d 项：%dn", i, [i - 1]);

// 获取顺序表的长度

l = ;

// 先进行清屏

system("cls");

int i, l;

}

// 向顺序表中某个特定位置添加

void Insert(SqList *L)

{

// 检查输入数据的有效性

if ( scanf("%d", &tmp) == 0 )

// 清空输入缓冲区

fflush(stdin);

printf("请输入要插入的位置(1 ~ %d) ：", L->length + 1);

// 清屏

system("cls");

int i, tmp, k;

system("pause");

// 判断在顺序表中能否找到元素

if (i == 0)

{

}

else

{

}

printf("顺序表的第%d 个元素是%d n", i, e);

printf("在顺序表中找不到元素：%dn", e);

i = ListIndexOf(L, e);

// 如果输入的不是整数

if ( scanf("%d", &e) == 0)

{

}

printf("无效输入！n");

system("pause");

return;

printf("请输入要查找的元素（只接受整数）：");

// 清屏

system("cls");

{

}

// 判断输入位置是否超出有效范围

if (tmp >= 1 && tmp <= L->length + 1)

{

}

else

{

}

printf("插入位置超出有效范围！n");

system("pause");

return;

printf("请输入要插入的元素（只接受整数输入）：");

// 检查输入数据的有效性

if ( scanf("%d", &i) == 0)

{

}

k = ListInsert(L, tmp, i);

// 对ListInsert 函数的返回值进行分析

switch (k)

{

case INDEX_OUT_OF_RANGE:

}

system("pause");

return;

printf("插入位置超出有效范围！n");

break;

printf("顺序表已满，不能再向其中添加数据n");

break;

printf("成功向顺序表添加元素：%dn", i);

break;

printf("无效输入！n");

system("pause");

return;

printf("无效输入！n");

system("pause");

return;

case LIST_FULL:

case OK:

}

// 从顺序表中删除某个特定位置的元素

void Delete(SqList *L)

{

}

// 利用有序表插入算法创建有序表

int CreateSortedList(SqList *L)

}

else

{

}

printf("删除位置超出有效范围！n");

system("pause");

return;

system("pause");

return;

// 检查输入数据的有效性

if (i >= 1 && i <= L->length)

{

if (ListDelete(L, i, &e) == OK)

{

}

else

{

}

printf("删除元素失败！n");

printf("成功删除元素：%dn", e);

// 检查输入数据的有效性

if ( scanf("%d", &i) == 0)

{

}

printf("无效输入！n");

system("pause");

return;

printf("输入要删除的元素位置(1 ~ %d)：", L->length);

system("cls");

int i, e;

{

printf("请输入第%d 个元素：", L->length + 1);

// 将光标移动到行首

ResetCursor();

}

// 如果输入的元素均大于有序表的所有元素，则放在有序表的最后

if (i == L->length)

{

}

ListInsert(L, i+1, e);

// 如果是第一个元素，则放到有序表的第一个位置

if (L->length == 0)

{

}

else

{

// 输入的元素与有序表中的元素进行大小比较，找到适合的插入位置

for (i = 0; i < L->length; i++)

{

}

if (e <= L->elem[i])

{

}

ListInsert(L, i+1, e);

break;

ListInsert(L, 1, e);

while ( scanf("%d", &e) != 0 )

{

// 如果顺序表已满，输出错误信息

if (L->length >= 100)

return LIST_FULL;

printf("请输入要放进有序表的元素（输入非数字字符结束输入）n");

printf("请输入第%d 个元素：", L->length + 1);

// 对有序表L 进行初始化操作

InitList(L);

int i;

ElemType e;

}

}

printf("n成功建立有序表！n");

system("pause");

return OK;

// 通过有序表插入算法创建两个有序表，再对其进行合并操作

void CreateAndUnion()

{

printf("合并前的有序表：");

printf("nLa: n");

ListPrintSimple(La);

printf("n");

system("cls");

// 如果第二个有序表创建失败

if (CreateSortedList(&Lb) != OK)

{

}

printf("第二个有序表创建失败，函数终止！n");

system("pause");

return;

fflush(stdin);

printf("现在创建第二个有序表n");

// 如果第一个有序表创建失败

if (CreateSortedList(&La) != OK)

{

}

printf("第一个有序表创建失败，函数终止！n");

system("pause");

return;

system("cls");

printf("现在创建第一个有序表n");

SqList La, Lb;

SqList Lc;

// 两个有序表

// 存放合并以后的有序表

// 记录两个有序表的长度 int lenLa, lenLb;

ElemType *ptrA, *ptrB; // 两个指针，用于合并有序表检索数据

printf("Lb: n");

ListPrintSimple(Lb);

printf("n");

// 获取两个有序表的长度

lenLa = ;

lenLb = ;

// 如果合并后有序表大小超过100

if (lenLa + lenLb > 100)

{

}

// Lc 初始化

InitList(&Lc);

// 定位ptrA ptrB 指针

ptrA = ;

ptrB = ;

while (((ptrA - ) < lenLa) && ((ptrB - ) < lenLb))

{

}

while ((ptrA - ) < lenLa)

{

}

while ((ptrB - ) < lenLb)

ListAppend(&Lc, *ptrA);

ptrA++;

if (*ptrA >= *ptrB)

{

}

else

{

}

ListAppend(&Lc, *ptrA);

ptrA++;

ListAppend(&Lc, *ptrB);

ptrB++;

printf("合并后有序表大小超过100n");

system("pause");

return;

}

{

}

printf("n");

printf("合并后的有序表：n");

ListPrintSimple(Lc);

printf("n");

system("pause");

ListAppend(&Lc, *ptrB);

ptrB++;

void SqListInsert(SqList *L)

{

// 跟原有有序表中的元素逐个进行大小比较

for (i = 0; i < L->length; i++)

{

if (e <= L->elem[i])

{

ListInsert(L, i+1, e);

// 输入的字符为非整数时

if ( scanf("%d", &e) == 0 )

{

}

printf("无效输入！n");

system("pause");

return;

printf("请输入要插入到有序表的元素：");

// 插入数据前检查有序表是否已满

if (L->length >= 100)

{

}

printf("有序表已满！n");

system("pause");

return;

// 清屏

system("cls");

int e, i;

}

}

}

break;

// 如果从键盘读入的元素均大于原有序表中的元素

// 把新的元素放在有序表的最后

if (i >= L->length)

{

}

printf("成功向有序表中插入元素%dn", e);

system("pause");

return;

ListInsert(L, L->length+1, e);

void main()

{

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");

while (1)

{

system("cls"); // 清屏

SqList L, SL;

char ch;

int LStatus = 0, SLStatus = 0;

// 记录顺序表或有序表的建立状态

// 避免在建立前进行遍历操作引起错误

printf(" 请选择：");

// 清除输入缓冲区，避免后面scanf 函数无法读入字符

fflush(stdin);

scanf("%c", &ch);

switch (ch)

{

case '1':

CreateSqList(&L);

LStatus = 1;

break;

if (LStatus == 1)

{

}

else

{

}

break;

if (LStatus == 1)

{

}

else

{

}

break;

if (LStatus == 1)

{

}

else

{

}

printf("进行顺序表的插入操作之前需要建立顺序表n");

system("pause");

Insert(&L);

printf("顺序表进行查找之前需要建立顺序表n");

system("pause");

SearchList(L);

printf("对顺序表进行遍历输出之前需要建立顺序表n");

system("pause");

ListPrint(L);

case '2':

case '3':

case '4':

break;

if (LStatus == 1)

{

}

else

{

}

break;

system("cls");

CreateSortedList(&SL);

SLStatus = 1;

break;

if (SLStatus == 1)

{

}

else

{

}

break;

if (SLStatus == 1)

{

}

else

{

}

break;

CreateAndUnion();

break;

printf("对有序表进行插入操作之前需要建立有序表n");

system("pause");

SqListInsert(&SL);

printf("对有序表进行遍历输出之前需要建立有序表n");

system("pause");

ListPrint(SL);

printf("进行顺序表的删除操作之前需要建立顺序表n");

system("pause");

Delete(&L);

case '5':

case '6':

case '7':

case '8':

case '9':

case 'q':

case 'Q':

}

}

}

exit(0);

printf("无效输入n");

system("pause");

break;

default: