顺序表实验报告，附完整代码，运行结果截图（顺序表的增删改查）

一、实验目的

1.学会使用DEV C++的集成开发环境。

2.掌握线性表的顺序存储结构及其编程。

二、实验原理或意义

通过上机实验，加深对所学基本知识：线性表的顺序存储的掌握，为后面的全面学习奠定非常必要的基础。

三、实验重点

1.线性表的顺序存储

2.顺序表的编程操作。

四、实验难点

1.调试程序中的语法错误。

2.程序的编写。

五、实验方法（或技术）

上机实验时一边调试程序一边将实验报告上关于程序调试和运行结果的信息填写到实验报告上，实验完成时上交实验报告。

六、实验内容

1.顺序表的操作编程

（1）根据下列程序环境的设置，完成顺序表的初始化函数List ListInit(int size)的编写。

typedef int ListItem; /* 表元素类型 int */

typedef struct alist{

      int n; /* 表长 */          

      int maxsize;/* 数组上界 */

      ListItem *table;/* 存储表元素的数组 */

}Alist,*List;

（2）在第（1）题的基础上，void ListInsert(int k,ListItem x,List L)，实现在表L的第k 个位置插入 x。

（3）编写函数void PrintList(List L)实现输出顺序表中的元素。

（4）编写删除函数ListItem ListDelete(int k,List L)，实现在表L中删除位置k处的元素。

（5）编写查找函数ListItem  ListRetrieve(int k,List L)，实现返回线性表中第k处的元素。

（6）编写顺序表L的判空函数int ListEmpty(List L)和求顺序表长度的函数int ListLength(List L)。

（7）编写函数int  ListLocate(ListItem x,List L)，判断x位置。

（8）输入主函数对上面各个函数实现调用，并记录程序的运行结果。

2.回答问题：

（1）顺序表是存储结构还是逻辑结构？动态存储与静态存储有什么区别？程序中的顺序表是动态还是静态的存储？

答：（1）顺序表的存储方式一般使用数组，数组在物理上是连续的，故顺序表是逻辑结构；（2）动态存储是在程序执行过程中动态分配，静态存储是在程序的编译连接阶段就已经确定好的；（3）线性表根据实际情况的不同，可以用静态存储也可以动态存储，但本程序中为方便运行结果截图采用静态存储。

（2）顺序表的插入与删除的时间主要花在什么操作上？它们的时间复杂度分别是多少？

答：（1）顺序表的插入与删除主要花在移动元素操作上，移动的个数取决于插入删除的位置；（2）最好情况为查找元素在表头仅需一次，时间复杂度为O（1），最坏情况为找不到或者在表尾，时间复杂度为O(n)；最好情况为删除元素在表尾无需移动元素，时间复杂度为O（1），最坏情况为在表头，需要移动n-1次，时间复杂度为O(n)

七、实验报告要求内容

1.实验目的

（1）学会使用DEV C++的集成开发环境。

（2）掌握线性表的顺序存储结构及其编程。

2.实验要求

（1）理解顺序表的运行原理并利用代码实现顺序表的基本操作；

（2）熟练掌握编程软件的集成开发环境。

3.实验代码

#include<stdio.h>
 
#include<malloc.h>
 
#include<stdlib.h>
 
#define IntSize 115
 
typedef int ListItem; /* 表元素类型 int */
 
typedef struct alist {
 
int length; /* 表长 */
 
int Maxsize;/* 数组上限 */
 
ListItem* table;/* 存储表元素的数组 */
 
}Alist;
 
//初始化顺序表 
 
int InitList(Alist* L) {
 
L->Maxsize = 115;
 
L->length = 0;
 
L->table = (ListItem*)malloc(sizeof(ListItem) * IntSize);
 
if (!L->table) {
 
printf("内存申请失败！\n");
 
return 0;
 
}
 
printf("内存申请成功！\n");
 
return 1;
 
}
 
//销毁顺序表 
 
void DestroyList(Alist* L) {
 
free(L->table);
 
}
 
//判断顺序表是否为空 
 
int ListEmpty(Alist* L) {
 
if (L->length == 0)
 
printf("该顺序表为空\n");
 
else
 
printf("该顺序表非空\n");
 
}
 
//返回顺序表的长度 
 
int ListLength(Alist* L) {
 
printf("该顺序表的长度为%d\n", L->length);
 
}
 
//打印顺序表中的元素
 
void PrintList(Alist* L) {
 
printf("遍历顺序表：\n");
 
for (int i = 0; i < L->length; i++)
 
printf("%d ", L->table[i]);
 
printf("\n");
 
}
 
//从顺序表中查找第k个元素
 
ListItem ListRetrieve(int k, Alist* L) {
 
if (k<1 || k>L->length) {
 
return 0;
 
}
 
else {
 
printf("第%d位上的元素为%d\n", k, L->table[k - 1]);
 
}
 
}
 
//在位置k中插入元素x
 
int ListInsert(int k, ListItem x, Alist* L) {
 
int j;
 
k--;
 
for (j = L->length; j > k; j--) {
 
L->table[j] = L->table[j - 1];
 
}
 
printf("在第%d位插入%d\n", k + 1, x);
 
L->table[j] = x;
 
L->length++;
 
return 1;
 
}
 
//删除位置k上的元素
 
int ListDelete(int k, Alist* L) {
 
int j;
 
if (k<1 || k>L->length)
 
return 0;
 
k--;
 
for (j = k; j < L->length; j++)
 
L->table[j] = L->table[j + 1];
 
L->length--;
 
printf("已删除位置%d上的元素\n", k + 1);
 
return 1;
 
}
 
//查找顺序表中与x相同的元素的位置 
 
int ListLocate(ListItem x, Alist* L) {
 
int i;
 
for (i = 0; i < L->length; i++)
 
if (L->table[i] == x) {
 
printf("顺序表中%d的位置为%d", x, i + 1);
 
return 1;
 
}
 
printf("顺序表中没有%d", x);
 
}
 
int main() {
 
Alist L;
 
InitList(&L);
 
ListInsert(1, 0, &L);
 
ListInsert(2, 9, &L);
 
ListInsert(3, 1, &L);
 
ListInsert(4, 1, &L);
 
ListInsert(5, 5, &L);
 
PrintList(&L);
 
ListDelete(1, &L);
 
PrintList(&L);
 
ListRetrieve(2, &L);
 
ListEmpty(&L);
 
ListLength(&L);
 
ListLocate(0, &L);}

4.实验结果截图