史上最详细的改良顺序表讲解，看完不会你打我

时间：2021-03-01 01:09:06

目录

0.什么是顺序表

1.顺序表里结构体的定义

2.顺序表的初始化

3.顺序表的输入史上最详细的改良顺序表讲解，看完不会你打我

4.增加顺序表的长度

5.1顺序表的元素查找（按位查找）

5.2顺序表的元素查找（按值查找）在顺序表进行按值查找，大概只能通过遍历的方式，这也算是顺序表的缺点吧！

6.顺序表的元素插入

7.顺序表的元素删除

8.顺序表的打印

9.求顺序表的表长

10.顺序表的销毁

11.运行结果 

 12.全部代码
史上最详细的改良顺序表讲解，看完不会你打我

0.什么是顺序表

  • 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组
    上完成数据的增删查改。

  • 顺序表：可动态增长的数组，要求数据是连续存储的

1.顺序表里结构体的定义

typedef struct SList
{
	int length;
	int MaxSize;
	int* data;
}SList;

length为当前顺序表长度 MaxSize是顺序表最大长度 ，* data是定义顺序表中元素类型的数组指针

2.顺序表的初始化

#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<string.h>
#define InitSize 10

void InitSList(SList& L)
{
	L.data = (int*)malloc(sizeof(int) * InitSize);
	if (L.data == NULL)
	{
		printf("%s\n",strerror(errno));
	}
	L.length = 0;
	L.MaxSize = InitSize;
}

需要注意的是，malloc函数的返回的是无类型指针，在使用时一定要强制转换为所需要的类型。在使用malloc函数开辟的空间中，不能进行指针的移动，因为一旦移动之后可能出现申请的空间和释放空间大小的不匹配。

我们使用malloc函数申请大小为InitSize个字节的空间，成功申请会返回指向所申请空间的指针，如果申请失败会返回空指针NULL。

可能会空间开辟失败的情况，我们加上strerror函数。

strerror函数会返回错误码所对应的错误信息，返回值是一个指向描述错误的字符串的指针。

要使用它的话，必须包含errno.h这个头文件。

  • 每一个这样的错误码都对应着一个错误信息，sterror函数能把错误码所对应错误信息的首字符的地址返回。
  • 当C语言的库函数调用失败的时候，会将一个错误码存放在一个叫errno的变量中。
  • 当我们想知道调用库函数的时候发生了什么错误信息，就可以将errno中的错误码翻译成错误信息。

如图，当我们所要的空间太大，初始化失败时

史上最详细的改良顺序表讲解，看完不会你打我

 它会提示空间不够。

3.顺序表的输入

void WriteSList(SList& L)
{
	printf("请输入你要创建的顺序表的长度:>");
	scanf("%d", &L.length);
	printf("请输入你要创建的顺序表的元素:>");
	for (int j = 0; j < L.length; j++)
	{
		scanf("%d", &L.data[j]);
	}
}

这一部分没有什么好说的，我们先输入长度再将每个元素输入就行。

4.增加顺序表的长度

我们定义一个*p指针来指向原顺序表的地址，之后再使用malloc函数来开辟一块更大的空间，空间大小由我们来定义，再将*p指向的值，也就是原顺序表的内容挨个赋值给新的顺序表，最后将原来的空间删除即可。不要忘记让p指向空指针哦！

void IncreaseSize(SList& L)
{
	int len;
	int* p = L.data;
	printf("请输入你要增加的长度:>");
	scanf("%d", &len);
	L.data = (int*)malloc(sizeof(int) * (L.MaxSize+len));
	for (int i = 0; i < L.length; i++)
	{
		L.data[i] = p[i];
	}
	L.MaxSize = L.MaxSize + len;
	free(p);
    p=NULL;
}

5.1顺序表的元素查找（按位查找）

按位查找直接通过数组下标即可。 

bool GetElem(SList& L)
{
	int i;
	printf("你要找第几个元素:>");
	scanf("%d", &i);
	if (i<1 || i>L.length)
	{
		return false;
	}
	printf("第%d个元素是%d\n", i, L.data[i - 1]);
	return true;
}

布尔型（bool）变量的值只有 真 （true) 和假 （false）。一般将非零值看做true，将零值看做false。使用布尔型可以增加代码的可读性。

5.2顺序表的元素查找（按值查找）
在顺序表进行按值查找，大概只能通过遍历的方式，这也算是顺序表的缺点吧！

顺序表按值查找的时间复杂度为：O(n)，效率比较低。

void LocateElem(SList& L)
{
	int e, i, k=1;
	printf("请输入你要查找的元素:>");
	scanf("%d", &e);
	for (i = 0; i < L.length; i++)
	{
		if (e == L.data[i])
		{
			k = 0;	
			printf("找到了，是第%d个元素\n", i + 1);
			break;
		}
	}
	if (k)
	{
		printf("找不到该元素\n");
	}
}

6.顺序表的元素插入

将顺序表元素的插入类比成为我们排队，当有一个人想要插入一个中间的位置时，后面的人一定会因为插队的人而后移一位。倒数第二个人会到原先倒数第一人的位置，而原先倒数第一的那个人会后移一位，所以最后表长会加一。

需要判断的有两点：

1.顺序表的空间是否够用。

2.所插入的位置是否合法，有没有越界。

bool InsertSList(SList& L)
{
	int i, e;
	printf("请输入要插入的位置和元素:>");
	scanf("%d%d", &i, &e);
	if (i<1 || i>L.length)
	{
		return false;
	}
	if (L.length > L.MaxSize)
	{
		return false;
	}
	for (int j = L.length; j >= i; j--)
	{
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;
	L.length++;
	printf("插入的元素是%d,插入的位置是%d\n", e, i);
	return true;
}

我们同样使用布尔型，在以上两种情况时返回一个false值。

让插入位置之后的元素挨个后移，在腾出的位置插入要插入的元素，返回一个true值。

7.顺序表的元素删除

依旧可以用排队的例子来说，队伍中有一个人有事要走，那么他的位置就会空出来，这时候他后面的人就要挨个向前一位来补齐这个位置。当然，最后表长会减一。

bool DeleteSList(SList& L)
{
	int i,j,e;
	printf("请输入你要删除的元素位置:>");
	scanf("%d", &i);
	if (i<1 || i>L.length)
	{
		return false;
	}
	if (!L.data)
	{
		return false;
	}
	e = L.data[i-1];
	
	for (j = i; j <= L.length;j++)
	{
		L.data[j-1] = L.data[j];
	}
	L.length--;
	printf("删除的元素是%d，它的位置是%d\n",e, i);
	return true;
}

8.顺序表的打印

首先判断表是否为空表，是空表时返回一个false。

bool PrintSList(SList &L)
{
	if (!L.data)
	{
		return false;
	}
	printf("数组里的元素有:>");
	for (int i = 0; i < L.length; i++)
	{
		printf("%d ", L.data[i]);
	}
	printf("\n");
	return true;
}

9.求顺序表的表长

int GetLength(SList& L)
{
	if (L.length == 0)
	{
		return 0;
	}
		return L.length;
}

10.顺序表的销毁

getchar的使用是很关键的，用来接收前面的回车，如果不加的话之后的scanf将会直接被跳过。

就如上篇博客所说，malloc开辟的空间是在堆区的，这片空间需要程序员主动去释放，不然会导致内存泄露的问题。大家感兴趣可以看看上篇博客。

史上最详细的改良顺序表讲解，看完不会你打我

我眼中的‘C’——动态内存+柔型数组_陈大大陈的博客-CSDN博客

void DestroySList(SList& L)
{
	char c;
	getchar();
	printf("是否销毁顺序表(Y/N):>");
	scanf("%s", &c);
	if (c == 'Y')
	{
		L.length = 0;
		L.MaxSize = 0;
		free(L.data);
        L.data=NULL;
		printf("顺序表已销毁\n");
	}
}

11.运行结果 

史上最详细的改良顺序表讲解，看完不会你打我

 12.全部代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#include<string.h>
#define InitSize 10
typedef struct SList
{
	int length;
	int MaxSize;
	int* data;
}SList;
void InitSList(SList& L)
{
	L.data = (int*)malloc(sizeof(int) * InitSize);
	if (L.data == NULL)
	{
		perror("malloc");
	}
	L.length = 0;
	L.MaxSize = InitSize;
}
void WriteSList(SList& L)
{
	printf("请输入你要创建的顺序表的长度:>");
	scanf("%d", &L.length);
	printf("请输入你要创建的顺序表的元素:>");
	for (int j = 0; j < L.length; j++)
	{
		scanf("%d", &L.data[j]);
	}
}
void IncreaseSize(SList& L)
{
	int len;
	int* p = L.data;
	printf("请输入你要增加的长度:>");
	scanf("%d", &len);
	L.data = (int*)malloc(sizeof(int) * (L.MaxSize+len));
	for (int i = 0; i < L.length; i++)
	{
		L.data[i] = p[i];
	}
	L.MaxSize = L.MaxSize + len;
	free(p);
	p = NULL;
}
bool GetElem(SList& L)
{
	int i;
	printf("你要找第几个元素:>");
	scanf("%d", &i);
	if (i<1 || i>L.length)
	{
		return false;
	}
	printf("第%d个元素是%d\n", i, L.data[i - 1]);
	return true;
}
void LocateElem(SList& L)
{
	int e, i, k=1;
	printf("请输入你要查找的元素:>");
	scanf("%d", &e);
	for (i = 0; i < L.length; i++)
	{
		if (e == L.data[i])
		{
			k = 0;	
			printf("找到了，是第%d个元素\n", i + 1);
			break;
		}
	}
	if (k)
	{
		printf("找不到该元素\n");
	}
}
bool InsertSList(SList& L)
{
	int i, e;
	printf("请输入要插入的位置和元素:>");
	scanf("%d%d", &i, &e);
	if (i<1 || i>L.length)
	{
		return false;
	}
	if (L.length > L.MaxSize)
	{
		return false;
	}
	for (int j = L.length; j >= i; j--)
	{
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;
	L.length++;
	printf("插入的元素是%d,插入的位置是%d\n", e, i);
	return true;
}
bool DeleteSList(SList& L)
{
	int i,j,e;
	printf("请输入你要删除的元素位置:>");
	scanf("%d", &i);
	if (i<1 || i>L.length)
	{
		return false;
	}
	if (!L.data)
	{
		return false;
	}
	e = L.data[i-1];
	
	for (j = i; j <= L.length;j++)
	{
		L.data[j-1] = L.data[j];
	}
	L.length--;
	printf("删除的元素是%d，它的位置是%d\n",e, i);
	return true;
}
bool PrintSList(SList &L)
{
	if (!L.data)
	{
		return false;
	}
	printf("数组里的元素有:>");
	for (int i = 0; i < L.length; i++)
	{
		printf("%d ", L.data[i]);
	}
	printf("\n");
	return true;
}
int GetLength(SList& L)
{
	if (L.length == 0)
	{
		return 0;
	}
		return L.length;
}
void DestroySList(SList& L)
{
	char c;
	getchar();
	printf("是否销毁顺序表(Y/N):>");
	scanf("%s", &c);
	if (c == 'Y')
	{
		L.length = 0;
		L.MaxSize = 0;
		free(L.data);
		L.data = NULL;
		printf("顺序表已销毁\n");
	}
}
int main()
{
	SList L;
	InitSList(L);
	WriteSList(L);
	PrintSList(L);
	IncreaseSize(L);
	InsertSList(L);
	PrintSList(L);
	DeleteSList(L);
	PrintSList(L);
	GetElem(L);
	LocateElem(L);
	int len = GetLength(L);
	printf("顺序表的长度是%d\n", len);
	DestroySList(L);
	return 0;
}

 这篇博客旨在总结我自己阶段性的学习，要是能帮助到大家，那可真是三生有幸！如果觉得我写的不错的话还请点个赞和关注哦~我会持续输出编程的知识的！????????????

标签：

相关文章