【C语言】超详细讲解顺序表的各种操作

快来打我* 2023-09-28 13:03 122阅读 0赞

**目录**

1.顺序表的定义

2.顺序表的特点

3.顺序表的定义

4.顺序表的常用操作的实现

4.1 顺序表的初始化

4.2 顺序表的建立

4.3 查找操作

1. 按位置查找

2.按值查找操作

4.4 插入操作

4.5 删除操作

4.6 输出表中的元素

5.顺序表的操作的完整程序代码

总结：

--------------------

## 1.顺序表的定义 ##

数据结构在内存中的表示通常有两种形式，一种是**顺序存储**，另一种是**链式存储**。线性表的顺序存储是指用一组地址**连续**的存储单元依次存储线性表的数据元素，我们把这种存储形式存储的线性表称为顺序表。

## 2.顺序表的特点 ##

1.顺序表的逻辑结构和物理结构是**一致**的。

2.顺序表中任意一个数据元素都可以**随机存取**，所以顺序表是一种随机存取的存储结构。

## 3.顺序表的定义 ##

#define MAXLEN 100 //定义MAXLEN
    typedef int DataType;
    typedef struct
    {
    	DataType data[MAXLEN];
    	int Length;
    }SeqList;

定义**MAXLEN**为100，表示**顺序表最大的存储空间** 利用宏方便对顺序表的大小进行修改

**利用typedef将DataType定义成int类型的数据**，如果顺序表存放的数据要修改成其他类型的，可以直接 利用typedef将DataType修改成我们想要的数据类型就可以了，这也**方便对顺序表进行修改**

顺序表SeqList是一个结构体类型，它有两个成员组成，data表示存储顺序表的数组，其长度MAXLEN表示顺序表中元素数目的最大值，**Length表示顺序表的实际长度**

**注意：C语言**的数组下标从0开始

## 4.顺序表的常用操作的实现 ##

### 4.1 顺序表的初始化 ###

顺序表的初始化就是要建立一个空表L，将L作为指针参数，将表L的实际长度设置为0 代码如下:

void InitList(SeqList* L)
    {
    	L->Length = 0;
    }

### 4.2 顺序表的建立 ###

对于初始化好的顺序表，我们要从键盘输入n个数，将这些数存在顺序表中，修改表场后建立顺序表L，代码如下：

void CreateList(SeqList* L,int n)
    {
    	int i = 0;
    	for (i = 0; i < n; i++)
    	{
    		scanf("%d", &L->data[i]);
    	}
    	L->Length = i;
    }

### 4.3 查找操作 ###

顺序表的查找分为按值和按序号查找，下面开始介绍这两种方法的实现，大家可以根据需求进行使用。

#### 1. 按位置查找 ####

按位置查找就是查找第i个位置的元素的值，在i无效时返回出错，有效时返回成功，并用指针x所指的变量传回第i个元素的值 代码如下：

int GetElem(SeqList* L, int i, DataType* x)
    {
    	if (i<1 || i>L->Length)
    	{
    		return 0;
    	}
    	else
    	{
    		*x = L->data[i - 1];
    		return 1;
    	}
    }

**注意：**在查找的时候要先判断i是不是合法的（是否为负数是否超过数组的最大下标值等），以及要考虑到i不是合法的数据时，要怎么处理。

#### 2.按值查找操作 ####

按值查找是指在顺序表中，查找与给指定值x相等的数据元素所在位置的下标。

**算法的设计思想**:首先令i等于0，然后从表的第一个位置开始逐个与给定值x进行判断，当i小于表长且与该位置的元素值与x的值不相等时i自加，直到循环结束为止。若i的值大于表长就是**查找失败**，就**返回0**；若**查找成功**就返回其位置，就是**i+1**（数组下标从0开始所以要加1）

代码如下：

int Locate(SeqList* L, DataType x)
    {
    	int i = 0;
    	while (i < L->Length && L->data[i] != x)
    	{
    		i++;
    	}
    	if (i > L->Length)
    	{
    		return 0;
    	}
    	else
    	{
    		return i + 1;
    	}
    }

### 4.4 插入操作 ###

线性表的插入是指在表的第i个位置上（因为C语言的下标是从0开始的，所以**插入位置下标为i-1**)插入一个值为x的元素，插入后使原表长增加1，称为表长度为n+1的表。

**顺序表的插入节点的步骤如下**：

1.将数组下标从第i个位置一直到最后一个位置的结点全部往后移，让出第i个位置

2.将新节点x插入第i个位置

3.修改表长

顺序表插入元素的过程如图所示：

![7254d468361d45e0b8e447fded035bb6.png][]

**要注意一下几点问题**：

1.首先要检查顺序表是否已满，在表满的情况下不能插入，否则会产生溢出错误

2.检查插入位置的有效性，插入的有效范围是1<=i<=n+1(n是原来的表长)

3.注意数据移动的方向，必须从原线性表的最后一个结点开始往后移动

代码如下：

int InsElem(SeqList* L, int i, DataType x)
    {
    	int j = 0;
    	if (L->Length >= MAXLEN)
    	{
    		printf("顺序表已满！");
    		return -1;
    	}
    	if (i<1 || i>L->Length+1)
    	{
    		printf("插入位置出错");
    		return 0;
    	}
    	if (i == L->Length + 1) //插入位置为表尾时
    	{
    		L->data[i - 1] = x;
    		L->Length++;
    		return 1;
    	}
    	for (j = L->Length - 1; j >= i - 1; j--)//插入位置为表中时
    	{
    		L->data[j + 1] = L->data[j];
    	}
    	L->data[i = 1] = x;
    	L->Length++;
    	return 1;
    }

顺序表的插入操作大约需要移动一半的数据元素，时间复杂度为O(n).

### 4.5 删除操作 ###

线性表的删除操作是指将第i个元素（C语言数组下标从0开始，删除位置下标为i-1）从顺序表中去掉，删除后顺序表长度-1

**顺序表删除结点的步骤如下**：

1.将要删除的元素赋值给指针x所指的变量

2.将第i+1到最后一个结点依次顺序向前移动

3.顺序表长度-1，删除成功，并返回

删除操作过程图如下：

![c5d780778c7045659dada5a0f92215f2.png][]

代码如下：

int DelElem(SeqList* L, int i, DataType* x)
    {
    	int j = 0;
    	if (L->Length == 0)
    	{
    		printf("顺序表为空");
    		return 0;
    	}
    	if (i<1 || i>L->Length)
    	{
    		printf("不存在第i个元素");
    		return 0;
    	}
    	*x = L->data[i - 1];
    	for (j = 1; j < L->Length; j++)
    	{
    		L->data[j - 1] = L->data[j];
    	}
    	L->Length--;
    	return 1;
    }

删除操作的平均每次大概需要移动一半的元素，时间复杂度为O(n).

### 4.6 输出表中的元素 ###

输出顺序表的元素，就是遍历一次一维数组，然后把它打印出来 代码如下：

void DispList(SeqList* L)
    {
    	int i = 0;
    	for (i = 0; i < L->Length; i++)
    	{
    		printf("%d ", L->data[i]);
    	}
    }

## 5.顺序表的操作的完整程序代码 ##

上面是顺序表的基本操作函数，为了运行相关代码，还要设计好主函数，运用之前学过的循环和开关语句，实现反复实行各种操作的功能。为了方便可以写一个菜单显示各项功能选项。

#define _CRT_SECURE_NO_WARNINGS 1
    #include<stdio.h>
    #define MAXLEN 100 //定义MAXLEN
    typedef int DataType;
    typedef struct
    {
    	DataType data[MAXLEN];
    	int Length;
    }SeqList;
    
    
    void InitList(SeqList* L)
    {
    	L->Length = 0;
    }
    void CreateList(SeqList* L,int n)
    {
    	int i = 0;
    	for (i = 0; i < n; i++)
    	{
    		scanf("%d", &L->data[i]);
    	}
    	L->Length = i;
    }
    
    int GetElem(SeqList* L, int i, DataType* x)
    {
    	if (i<1 || i>L->Length)
    	{
    		return 0;
    	}
    	else
    	{
    		*x = L->data[i - 1];
    		return 1;
    	}
    }
    int Locate(SeqList* L, DataType x)
    {
    	int i = 0;
    	while (i < L->Length && L->data[i] != x)
    	{
    		i++;
    	}
    	if (i > L->Length)
    	{
    		return 0;
    	}
    	else
    	{
    		return i + 1;
    	}
    }
    
    int InsElem(SeqList* L, int i, DataType x)
    {
    	int j = 0;
    	if (L->Length >= MAXLEN)
    	{
    		printf("顺序表已满！");
    		return -1;
    	}
    	if (i<1 || i>L->Length+1)
    	{
    		printf("插入位置出错");
    		return 0;
    	}
    	if (i == L->Length + 1) //插入位置为表尾时
    	{
    		L->data[i - 1] = x;
    		L->Length++;
    		return 1;
    	}
    	for (j = L->Length - 1; j >= i - 1; j--)//插入位置为表中时
    	{
    		L->data[j + 1] = L->data[j];
    	}
    	L->data[i = 1] = x;
    	L->Length++;
    	return 1;
    }
    
    int DelElem(SeqList* L, int i, DataType* x)
    {
    	int j = 0;
    	if (L->Length == 0)
    	{
    		printf("顺序表为空");
    		return 0;
    	}
    	if (i<1 || i>L->Length)
    	{
    		printf("不存在第i个元素");
    		return 0;
    	}
    	*x = L->data[i - 1];
    	for (j = 1; j < L->Length; j++)
    	{
    		L->data[j - 1] = L->data[j];
    	}
    	L->Length--;
    	return 1;
    }
    void DispList(SeqList* L)
    {
    	int i = 0;
    	for (i = 0; i < L->Length; i++)
    	{
    		printf("%d ", L->data[i]);
    	}
    }
    void  Menu()
    {
    	printf("                  顺序表的各种操作\n");
    	printf("==================================================\n");
    	printf("|              1——建立顺序表                   |\n");
    	printf("|              2——插入元素                     |\n");
    	printf("|              3——删除元素                     |\n");
    	printf("|              4——按位置查找元素               |\n");
    	printf("|              5——按元素值查找其在表中位置     |\n");
    	printf("|              6——求顺序表的长度               |\n");
    	printf("|              0——返回                         |\n");
    	printf("==================================================\n");
    	printf("请输入菜单号（0-6）:");
    }
    int main()
    {
    	SeqList L;
    	DataType x;
    	int n, i, loc;
    	char  ch1, ch2, a;
    	ch1 = 'y';
    	while (ch1 == 'y' || ch1 == 'Y')
    	{
    		Menu();
    		scanf("%c", &ch2);
    		getchar();
    		switch (ch2)
    		{
    		case  '1':
    			InitList(&L);
    			printf("请输入建立线性表的个数：");
    			scanf("%d", &n);
    			CreateList(&L, n);
    			printf("建立的线性表为:");
    			DispList(&L);
    			break;
    		case  '2':
    			printf("请输入要插入的位置：");
    			scanf("%d", &i);
    			printf("请输入要插入的元素值：");
    			scanf("%d", &x);
    			if (InsElem(&L, i, x))
    			{
    				printf("已成功在第%d的位置上插入%d，插入后的线性表为：\n", i, x);
    				DispList(&L);
    			}
    			else
    				printf("输入插入的参数错误!");
    			break;
    		case  '3':
    			printf("请输入要删除元素的位置：");
    			scanf("%d", &i);
    			if (DelElem(&L, i, &x))
    			{
    				printf("已成功在第%d的位置上删除%d，删除后的线性表为：\n", i, x);
    				DispList(&L);
    			}
    			else
    				printf("\n输入删除的参数错误!");
    			break;
    		case  '4':
    			printf("请输入要查看表中元素位置(从1开始)：");
    			scanf("%d", &i);
    			if (GetElem(&L, i, &x))
    				printf("当前线性表第%d个元素的值为：%d", i, x);
    			else
    				printf("输入的位置错误!");
    			break;
    		case  '5':
    			printf("请输入要查找的元素值为：");
    			scanf("%d", &x);
    			loc = Locate(&L, x);
    			if (loc)
    				printf("查找元素值为%d的位置为：%d", x, loc);
    			else
    				printf("该表中无此元素!");
    			break;
    		case  '6':
    			printf("当前线性表的长度为：%d", L.Length);
    			break;
    		case  '0':
    			ch1 = 'n'; 
    			break;
    		default:
    			printf("输入有误，请输入0-4进行选择！");
    		}
    		if (ch2 != '0')
    		{
    			printf("\n按回车键继续，按任意键返回主菜单！\n");
    			a = getchar();
    			if (a != '\xA')
    			{
    				getchar(); ch1 = 'n';
    			}
    		}
    	}
    }

代码执行效果如图所示：

![1774fa2e32ad4f0d8c8c761c726e7b4e.png][]

图片大小有限就不功能就不一一列举出来了。感兴趣的可以自己去试着写一下

## 总结： ##

顺序存储结构的**优点**是节省存储空间，顺序表结构简单便于随机访问表中任意的数据元素；**缺点**是插入和删除操作需要移动大量的数据元素，特别是当顺序表的而数据元素含有复杂信息是，移动工作量大、程序执行效率低。另外，顺序表的存储空间是连续且预先分配，若顺序表的长度变化较大时，难以预估顺序表的长度，可能会造成空间的浪费，也可能会导致数据溢出。（水平有限，若有错误，还请指正，谢谢！！）

[7254d468361d45e0b8e447fded035bb6.png]: https://img-blog.csdnimg.cn/7254d468361d45e0b8e447fded035bb6.png
[c5d780778c7045659dada5a0f92215f2.png]: https://img-blog.csdnimg.cn/c5d780778c7045659dada5a0f92215f2.png
[1774fa2e32ad4f0d8c8c761c726e7b4e.png]: https://img-blog.csdnimg.cn/1774fa2e32ad4f0d8c8c761c726e7b4e.png