C实现顺序表

桃扇骨 2021-11-09 05:01 297阅读 0赞

**1. 实验目的**

（1）掌握线性表的顺序存储结构；

（2）验证顺序表及其基本操作的实现；

（3）理解算法与程序的关系，能够将顺序表算法转换为对应的程序。

**2. 实验内容**

（1）建立含有若干个元素的顺序表；

（2）对已建立的顺序表实现插入、删除、查找等基本操作。

**3. 实验提示**

定义顺序表的数据类型——顺序表结构体SeqList，在SeqList基础上实现题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。简单起见，本实验假定线性表的数据元素为int型，要求学生：

（1）将实验程序调试通过后，用模板类改写；

（2）加入求线性表的长度等基本操作；

（3）重新给定测试数据，验证抛出异常机制。

**4. 实验程序**

#include <stdio.h> 
    #include <stdlib.h>
    #define MaxSize 100           /*假设顺序表最多存放100个元素*/
    typedef int DataType;          /*定义线性表的数据类型，假设为int型*/
    typedef struct
    {
    	DataType data[MaxSize];     /*存放数据元素的数组*/
    	int length;                 /*线性表的长度*/
    } SeqList;
    void InitList(SeqList *L)
    {
    	L->length = 0;
    }
    int CreatList(SeqList *L, DataType a[], int n)
    {
    	if (n > MaxSize) { printf("顺序表的空间不够，无法建立顺序表\n"); return 0; }
    	for (int i = 0; i < n; i++)
    		L->data[i] = a[i];
    	L->length = n;
    	return 1;
    }
    int Empty(SeqList *L) 
    {
    	if (L->length == 0)return 1;
    	else return 0;
    }
    int Length(SeqList *L)
    {
    	return L->length;
    }
    void PrintList(SeqList *L)
    {
    	for (int i = 0; i < L->length; i++)
    		printf("%d ", L->data[i]);       /*输出线性表的元素值，假设为int型*/
    }
    int Locate(SeqList *L, DataType x)
    {
    	for (int i = 0; i < L->length; i++)
    		if (L->data[i] == x) return i + 1;           /*返回序号*/
    	return 0;                               /*退出循环，说明查找失败*/
    }
    int Get(SeqList *L, int i, DataType *ptr) 
    {
    	if (i<1 || i>L->length) { printf("查找位置非法，查找失败\n"); return 0;}
    	else { *ptr = L->data[i - 1]; return 1;}
    }
    int Insert(SeqList *L, int i, DataType x)
    {
    	if (L->length >= MaxSize) { printf("上溢错误，插入失败\n"); return 0; }
    	if (i < 1 || i > L->length + 1) { printf("位置错误，插入失败\n"); return 0; }
    	for (int j = L->length; j >= i; j--)                   /*j表示元素序号*/
    		L->data[j] = L->data[j - 1];
    	L->data[i - 1] = x;
    	L->length++;
    	return 1;
    }
    int Delete(SeqList *L, int i, DataType *ptr)
    {
    	if (L->length == 0) { printf("下溢错误，删除失败\n"); return 0; }
    	if (i < 1 || i > L->length) { printf("位置错误，删除失败\n"); return 0; }
    	*ptr = L->data[i - 1];                       /*取出位置i的元素*/
    	for (int j = i; j < L->length; j++)              /* j表示元素所在数组下标*/
    		L->data[j - 1] = L->data[j];
    	L->length--;
    	return 1;
    }
    int main()
    {
    	int r[5] = { 1, 2, 3, 4, 5 }, i, x;
    	SeqList L;                         /*定义变量L为顺序表类型*/
    	CreatList(&L, r, 5);                     /*建立具有5个元素的顺序表*/
    	printf("当前线性表的数据为：");
    	PrintList(&L);                      /*输出当前线性表1 2 3 4 5*/
    	Insert(&L, 2, 8);                    /*在第2个位置插入值为8的元素*/
    	printf("执行插入操作后数据为：");
    	PrintList(&L);                     /*输出插入后的线性表1 8 2 3 4 5*/
    	printf("当前线性表的长度为：%d\n", Length(&L));    /*输出线性表的长度6*/
    	printf("请输入查找的元素值：");
    	scanf_s("%d", &x);
    	i = Locate(&L, x);
    	if (0 == i) printf("查找失败\n");
    	else printf("元素%d的位置为：%d\n", x, i);
    	printf("请输入查找第几个元素值：", &i);
    	scanf_s("%d", &i);
    	if (Get(&L, i, &x) == 1) printf("第%d个元素值是%d\n", i, x);
    	else printf("线性表中没有第%d个元素\n", i);
    	printf("请输入要删除第几个元素：");
    	scanf_s("%d", &i);
    	if (Delete(&L, i, &x) == 1) {                /*删除第i个元素*/
    		printf("删除第%d个元素是%d，删除后数据为：", i, x);
    		PrintList(&L);                         /*输出删除后的线性表*/
    	}
    	else printf("删除操作失败\n");
    	system("pause");
    	return 0;
    }

**5. 运行结果**

![20190804234709777.png][]

**6. 实验心得**

先将原有代码复制到编译器中编译出错，根据错误提示，我发现主函数中要调用到求顺序表长度函数、按位查找函数等，所以在原有的代码中加入了初始化顺序表函数、销毁顺序表函数、判空操作函数、求顺序表长度函数和按位查找函数。用Visual Studio2018编译时报错，系统建议用scanf\_s代替scanf更安全，修改完后就没有其它的错误了。

通过这次实验，我知道了顺序表是按顺序存储的，用了一维数组来存储数据，由于元素的序号和数组中存储该元素的下标之间具有一一对应关系，所以基本操作还是比较容易实现的。

[20190804234709777.png]: /images/20211109/3e1993635a05452da0a105bfe6b820aa.png