您现在的位置是：首页 >技术交流 >【数据结构】顺序表和链表（上）（附leetcode练习题）网站首页技术交流

【数据结构】顺序表和链表（上）（附leetcode练习题）

fighting小泽 2023-05-25 04:00:03
简介【数据结构】顺序表和链表（上）（附leetcode练习题）

☃️个人主页：fighting小泽
🌸作者简介：目前正在学习C语言和数据结构
🌼博客专栏：数据结构
🏵️欢迎关注：评论👊🏻点赞👍🏻留言💪🏻

文章目录

1.线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

为什么要这样存储呢？
因为有很多的列表需要依次展示我们的数据，比如微信联系人，成员列表。
那展示了以后还存在什么问题呢？
增删查改
但是存储这些数据又有一些很不一样的东西，它是什么呢？我们做个简单的比方： 线性表中最简单的存储方式是线性表，大家知不知道顺序表的本质是什么？顺序表的本质非常简单是一个数组，把数据存放到数组里。
大家知道数组的缺陷是什么吗？假设我们想要删除数组的某个元素，我们能不能把这块空间释放了？我们只能挪动数据覆盖。所以有一个非常好的结构叫链表，链表是一块一块的小空间，它们之间地址上没有关联，所以想要找到下一个空间的地址就得用一个指针，上一个空间里存放一个指向下一个空间的指针，这样就把它们链接起来了。当我们想删除某个元素的时候该怎么办?这个时候就简单了，我们把这个空间释放掉，上一个空间的指针指向下一个空间就可以了，不需要挪动数据。

所以不同的结构有不同的特点，就像公交车可以拉很多人，小轿车坐着很方便一样。
那既然顺序表，数组如此的不方便，我们还为什么要学习呢？
数组有一个它绝对的优势，是下标的随机访问，非常方便。比如二分查找能不能在链表上玩？不可以。包括后面我们学习排序，也是需要大量使用下标访问，因为它们的物理空间连续。

在这里插入图片描述

2.顺序表

2.1 概念及结构

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

顺序表一般可以分为：

  1. 静态顺序表：使用定长数组存储元素。
    在这里插入图片描述
  2. 动态顺序表：使用动态开辟的数组存储。
    在这里插入图片描述

2.2 静态顺序表

一般情况下我们想创建一个静态顺序表只需要一个数组还不行，还得告诉我们数组中有多少数据是有效数据,所以我们需要创建一个结构体，定义一个数组和它有效数据的个数

struct SeqList
{
	int arr[10];
	int size;
};

但是当前这种定义方式在实践中是不太好的，第一是因为它只能存放有限个数据，第二是它只能存放整形变量，所以我们可以对它进行改进：

用一个#define定义的宏来表示它存放的个数，用typedef对它的类型重命名。如果我们想进行修改，只需要改变#define定义的数值，或者改变typedef的类型。
由于结构体的名字太长了，我们也可以把它改成一个较短的名字。

#define N 10
typedef int SLDatatype;

typedef struct SeqList
{
	SLDatatype arr[N];
	int sz;
}SL;

这样就定义了一个静态的顺序表了，大家想想它有没有什么缺点？

做个简单的比方：如果我们定义了数组的大小是10，我们想存11个数据就存不下了，它的空间是固定的。假如我们给了10000个空间，我们想存10001个数据还是不够用。就算大多数情况够用了，但是我就存5个或者100个呢，空间是不是就浪费了。所以静态顺序表有一个特点，给小了不够用，给多了浪费。

所以一般情况下不推荐大家写静态的顺序表，推荐大家写动态的顺序表。

2.3 动态顺序表

静态顺序表只适用于确定知道需要存多少数据的场景，所以现实中基本都是使用动态顺序表，动态顺序表的实现其实跟我们的通讯录的实现差不多，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

动态的顺序表就是我们去malloc它的空间，空间满了后我们可以用realloc扩容，不够了扩就可以了，所以我们还要创建一个变量定义它的容量大小

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
  SLDataType* array;  // 指向动态开辟的数组
  size_t size ;       // 有效数据个数
  size_t capicity ;   // 容量空间的大小
}SeqList;

然后就是动态顺序表的初始化和增删查改了：

// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

2.4 动态顺序表的实现

我们同样需要创建三个文件夹来实现动态顺序表，SeqList.h头文件定义函数，SeqList.c文件对函数进行实现，test.c文件实现动态顺序表。

2.41顺序表的初始化和销毁

首先就是初始化我们的顺序表的初始化：
注意：由于我们要改变顺序表，所以我们要传顺序表的地址过去。
我们对它进行初始化只需要把每个变量置为空即可。

void SeqListInit(SL* psl)
{
	psl->a = NULL;
	psl->sz = 0;
	psl->capicity = 0;
}

上面只是一种方法，其实还有一种更好的方法，我们可以先开辟一点空间，不一定开特别大，开小一点就行，当空间不够了我们再重新开辟空间

void SeqListInit(SL* psl)
{
	assert(psl);
	SLDatatype* tmp = (SLDatatype*)malloc(N * sizeof(SLDatatype));
	if (tmp == NULL)
	{
		perror("SL_malloc");
		return;
	}
	psl->a = tmp;
	psl->sz = 0;
	psl->capicity = N;
}

由于顺序表是我们动态开辟的空间，所以结束时我们要把它释放掉，否则会出现内存泄漏。同时还有可能访问到这块空间，所以我们要把指向它的指针置空。

void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->sz = 0;
	psl->capicity = 0;
}

2.42检查顺序表的容量

当我们对顺序表增加元素的时候要确保顺序表的容量是足够大的，如果不够，我们可以把它的容量扩大两倍。而判断顺序表容量满的方式就是看它的有效变量size和容量capicity是否相等

void CheckCapicity(SL* psl)
{
	assert(psl);
	if (psl->capicity == psl->sz)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, 2 * psl->capicity * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("SL_realloc");
			return;
		}
		psl->a = tmp;
		psl->capicity *= 2;
	}
}

2.43顺序表的尾插和头插

我们想在尾部插入一个元素特别特别简单，从下标的角度数据个数就是最后一个元素的下标加1，我们只需要在size的位置放数据，然后再size++ 即可，注意判断顺序表的容量

void SLPushBack(SL* psl,SLDatatype x)
{
	assert(psl);
	CheckCapicity(psl);
	psl->a[psl->sz] = x;
	psl->sz++;
}

而我们想进行头部插入，只能从后向前每一个元素向后移动一位，在头部存放我们想存放的数据，然后size++即可。

void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	CheckCapicity(psl);
	for (int i = psl->sz; i > 0; i--)
	{
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[0] = x;
	psl->sz++;
}

2.44打印顺序表的元素

打印其实也非常简单，因为顺序表本质上是一个数组，打印数组的每一个元素即可，我们也可以打印出它的size和capicity。

void SLPrint(SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->sz; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("
sz=%d
", psl->sz);
	printf("capicity=%d
", psl->capicity);
}

现在让我们来测试刚刚的头插和尾插
在这里插入图片描述

2.45顺序表的尾删和头删

我们想进行顺序表的尾删该怎样做呢？把最后一位赋值为0，赋值为-1？要是它本身就是0或-1该怎么办？其实有一种简单的方法，我们直接把size 减1就可以了，之后又新元素再把它覆盖就行了

void SLPopBack(SL* psl)
{
	assert(psl->sz > 0);
	psl->sz -= 1;
}

我们想进行头删时，也是把每一个元素向前移动一位，然后size减1即可

void SLPopFront(SL* psl)
{
	assert(psl->sz > 0);
	for (int i = 0; i < psl->sz - 1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->sz--;
}

测试一下：

在这里插入图片描述

2.46顺序表的随机插入和删除

我们想要在任意位置插入元素，只需要将此位置和之后的元素都向后移动一位，然后在这个位置插入元素，然后size加1即可。注意pos的值要在范围之内。

void SLInsert(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos > 0 && pos <= psl->sz);
	CheckCapicity(psl);
	for (int i = psl->sz; i > pos-1; i--)
	{
		psl->a[i] = psl->a[i-1];
	}
	psl->a[pos-1] = x;
	psl->sz++;
}

删除也是将这个位置后的元素都向前移动一位，然后size减1。注意pos的值要在范围之内。

void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(pos > 0 && pos < psl->sz);
	CheckCapicity(psl);
	for (int i = pos - 1; i < psl->sz-1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->sz--;
}

我们前面的头插头删，尾插尾删也可以使用这两个函数，只需要改成特定的位置就行。
在这里插入图片描述

2.47顺序表的修改

修改也非常简单，只需要将这个位置的元素修改即可，不够要注意位置的范围要合理

void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos > 0 && pos < psl->sz);
	psl->a[pos - 1] = x;
}

在这里插入图片描述

3.整体代码

3.1SeqList.h代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

#define N 4
typedef int SLDatatype;

//typedef struct SeqList
//{
//	SLDatatype arr[N];
//	int sz;
//}SL;

//struct SeqList
//{
//	int arr[10];
//	int sz;
//};
typedef struct SeqList
{
	SLDatatype* a;
	int sz;
	int capicity;
}SL;

void SeqListInit(SL* psl);

void CheckCapicity(SL* psl);

void SLPushBack(SL* psl,SLDatatype x);//尾插

void SLPopBack(SL* psl);//尾删

void SLPrint(SL* psl);

void SLDestroy(SL* psl);

void SLPushFront(SL* psl, SLDatatype x);//头插

void SLPopFront(SL* psl);//头删

int SLFind(SL* psl, SLDatatype x);

void SLInsert(SL* psl, int pos, SLDatatype x);

void SLErase(SL* psl, int pos);

void SLModify(SL* psl, int pos, SLDatatype x);

3.2SeqList.c代码

#include"SeqList.h"

void SeqListInit(SL* psl)
{
	assert(psl);
	SLDatatype* tmp = (SLDatatype*)malloc(N * sizeof(SLDatatype));
	if (tmp == NULL)
	{
		perror("SL_malloc");
		return;
	}
	psl->a = tmp;
	psl->sz = 0;
	psl->capicity = N;
}

void CheckCapicity(SL* psl)
{
	assert(psl);
	if (psl->capicity == psl->sz)
	{
		SLDatatype* tmp = (SLDatatype*)realloc(psl->a, 2 * psl->capicity * sizeof(SLDatatype));
		if (tmp == NULL)
		{
			perror("SL_realloc");
			return;
		}
		psl->a = tmp;
		psl->capicity *= 2;
	}

}

void SLPushBack(SL* psl,SLDatatype x)
{
	assert(psl);
	CheckCapicity(psl);
	psl->a[psl->sz] = x;
	psl->sz++;
}

void SLPopBack(SL* psl)
{
	assert(psl->sz > 0);
	psl->sz -= 1;
}

void SLPrint(SL* psl)
{
	assert(psl);
	for (int i = 0; i < psl->sz; i++)
	{
		printf("%d ", psl->a[i]);
	}
	printf("
sz=%d
", psl->sz);
	printf("capicity=%d
", psl->capicity);
}

void SLDestroy(SL* psl)
{
	assert(psl);
	free(psl->a);
	psl->a = NULL;
	psl->sz = 0;
	psl->capicity = 0;
}

void SLPushFront(SL* psl, SLDatatype x)
{
	assert(psl);
	CheckCapicity(psl);
	for (int i = psl->sz; i > 0; i--)
	{
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[0] = x;
	psl->sz++;
}

void SLPopFront(SL* psl)
{
	assert(psl->sz > 0);
	for (int i = 0; i < psl->sz - 1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->sz--;
}

int SLFind(SL* psl, SLDatatype x)
{
	assert(psl);
	for (int i = 0; i < psl->sz; i++)
	{
		if (psl->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SLInsert(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos > 0 && pos <= psl->sz);
	CheckCapicity(psl);
	for (int i = psl->sz; i > pos-1; i--)
	{
		psl->a[i] = psl->a[i-1];
	}
	psl->a[pos-1] = x;
	psl->sz++;
}

void SLErase(SL* psl, int pos)
{
	assert(psl);
	assert(pos > 0 && pos < psl->sz);
	CheckCapicity(psl);
	for (int i = pos - 1; i < psl->sz-1; i++)
	{
		psl->a[i] = psl->a[i + 1];
	}
	psl->sz--;
}

void SLModify(SL* psl, int pos, SLDatatype x)
{
	assert(psl);
	assert(pos > 0 && pos < psl->sz);
	psl->a[pos - 1] = x;

}

4.leetcode练习题

力扣26，删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

我们可以通过利用双指针的方法来解决这道题，我们定义两个指针同时指向第二个元素，快指针向前遍历，如果两个指针指向的内容相同，快指针加1，慢指针不变。如果两个指针指向的内容不同，就将快指针的值赋值给慢指针，两个指针同时加1，最后返回慢指针的个数就可以了。

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) {
        return 0;
    }
    int fast = 1, slow = 1;
    while (fast < numsSize) {
        if (nums[fast] != nums[fast - 1]) {
            nums[slow] = nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}

5.结尾

这些就是我给大家分享的关于顺序表的知识啦，希望我们都能有所收获!
先赞后看,养成习惯！！^ _ ^
码字不易，大家的支持就是我坚持下去的动力，点赞后不要忘了关注我哦！

如有错误，还请您批评改正(｡ì _ í｡)

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐