当前位置：首页 > ds >正文

数据结构：顺序表和链表

ds 2025/7/19 5:20:44

一，线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

逻辑结构：一定是线性的

物理结构：不一定是线性的

二，顺序表

1，概念与结构

概念：顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。

逻辑结构：线性的物理结构：线性的

顺序表和数组的关系：

2，分类

（1）静态顺序表

概念：使⽤定⻓数组存储元素

静态顺序表可能存在的问题：

空间给小了，空间不够用空间给大了，会造成空间浪费

（2）动态顺序表

区别：

（1）初始就给定数组固定大小：int arr[10]

（2）动态申请内存：int*arr

为什么要将int重命名：对于一个·大型项目中（有着大量代码），许多地方都要用到int，但是在顺序表中要进行增添删改查也许要将int改变，这样会影响其他的地方，所以我们这里将int重命名为SLDataType

typedef起别名

3，动态顺序表的实现

#pragma once
#include<stdio.h>
#include<stdlib.h>//顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;int size;      //有效数据个数int capacity;  //空间大小
}SL;

初始化

//初始化
void SLInit(SL* ps)//形参
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

这里要考虑的问题是函数传参

函数传参分为两种：

1，传值：形参是实参值的拷贝，形参的改变不会影响实参

2，传地址：形参就是实参，形参的改变也会影响实参

最简单的区分：&只要不看到这个符号，就是传值

因为这里我们要通过形参来改变实参，所以是传地址传参

扩容

void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//开辟空间SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity * sizeof(SLDataType));if (tmp == NULL)//检查开辟空间是否成功{perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}

要检查空间是否足够，空间不够（size==capacity）的时候就要增容

那么这里就会有许多问题亟待讨论了。

首先，增容增多大？这里我们肯定不能依次只增加一个空间这样频繁扩容，但也不能依次扩容太大，导致空间的浪费，所以我们就要找一个合适的倍数去扩大空间。

我们发现二倍，其实是最好的选择

销毁

void SLDesTroy(SL* ps);

void SLDesTroy(SL* ps)
{if (ps->arr)free(ps->arr);//释放这一块空间ps->arr = NULL;//将指针置空ps->size = ps->capacity = 0;
}

尾插

void SLPushBack(SL* ps, SLDataType x);

void SLPopBack(SL* ps,SLDataType x)
{//判断空间是否满了
if（ps->size==ps->capacity)
{int newCapacity=ps->capacity==0?4:2*ps->capacity;SLDataType* tmp=(SLDataType*)realloc(ps->arr,newCapacity*sizeof(SLDataType));if(tmp==NULL){perror("realloc fail!");exit(1);)ps->arr=tmp;ps->capacity=newCapacity;
}ps->arr[ps->size++]=x;
}

但是我们可以用上面的扩容函数，来缩减代码量

void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//判断空间是否满了SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}

头插

void SLPushFront(SL* ps, SLDataType x)
{////温柔的处理方式判断顺序表是否为空//if (ps == NULL)//{//	return;//}assert(ps);//等价于assert(ps != NULL)//判断空间是否满了SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;++ps->size;
}

思路：

1，先将每一个数据向后移动一位（此时大家可能会说万一空间满了越界了怎么办？这里大家仔细看我们数组地址和下标相差一个，所以到i=n+1处就不会在进行移动了）

2，数据移动完以后，头部位置会空出来一个位置，这个时候把这个位置空间给x

3，同时表长+1

尾删

void SLPopBack(SL* ps)
{//顺序表不为空assert(ps && ps->size);--ps->size;
}

指向size处指针--，完成尾删

时间复杂度：O（1）

头删

void SLPopFront(SL* ps)
{//顺序表不为空assert(ps && ps->size);for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

从数组首元素开始，把后面位置元素向前移动一位，同时size-1是最后一个元素的下标，i最多到size-2处，此时循环才能访问到最后一个元素并且不会越界。

所以此条件保证了所有元素都能被向前移动，并且数组不会越界。

指定位置之前插入数据

void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//确保不是空指针assert(pos >= 0 && pos <= ps->size);//确保pos合法，不会是负数也不会越界访问SLCheckCapacity(ps);//检查容量，防止缓冲区溢出for (int i = ps->size; i > pos; i--)//元素后移一位{ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;//在腾出的pos位置插入新元素++ps->size;//更新size大小
}

指定位置删除数据

void SLErase(SL* ps, int pos)
{assert(ps && ps->size);assert(pos >= 0 && pos < ps->size);for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}--ps->size;
}

和指定位置插入数据的思路类似，只不过这里是将pos之后的数据整体向前挪动一位

查找数据

int SLFind(SL* ps, SLDataType x)
{for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}//未找到return -1;
}

销毁数据

void SLDesTroy(SL* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}

将指针所指向的空间释放，同时把指针置空，size和capacity置为0

三，顺序表题

1，移除元素

题目描述：

题解思路：

双指针法

根据题目描述我们可以发现题目要求我们：移除值为val的元素，要求返回的最终最终有效数据个数k和以及数组中前k个元素不为val。

我们可以创建两个变量m和n用来指向数组。

（1）当nums[n]不等于val的时候，将nums[n]赋值给nums[m]，同时n和m都++

（2）当nums[n]！=val的时候，不用赋值，只需要n++

通过以上操作我们可以总结出两个指针的作用：n在前面探路，寻找val的值，同时m在后面站岗，用来保存非val的值。

最后再返回m的值，此时m保存的值就是非val的值

int removeElement(int* nums, int numsSize, int val){int m=0;int n=0;while(n<numsSize){if(nums[n]!=val){nums[m]=nums[n];m++;}n++;}return m;
}

2，删除有序数组中的重复项

题目描述：

题解思路：

双指针法

创建两个变量分别指向起始位置和下一个位置

（1）nums[right]==nums[left]的时候，只将right++

（2）nums[right]!=nums[left]的时候相当于发现一个新元素，++left先将指针前移动，检查是否需要交换；当left！=right的时候，表明需要交换，将新元素给到left处，同时right++

（3）最后返回left+1的长度

++left！=right可以避免不必要的自我复制

返回left+1是因为left是下标

int removeDuplicates(int* nums, int numsSize) 
{int left=0;int right=left+1;while(right<numsSize){if(nums[right]!=nums[left]&&++left!=right){nums[left]=nums[right];}++right;}return left+1;
}

3，合并两个有序数组

题目描述：

题解思路：

思路一：

先合并数组，再对其中一个数组nums1进行冒泡排序

#include <stdio.h>
#include <stdlib.h>void mergeSortedArrays(int arr1[], int m, int arr2[], int n, int result[]) {int i = 0, j = 0, k = 0;// 遍历两个数组，比较元素大小，将较小的放入结果数组while (i < m && j < n) {if (arr1[i] < arr2[j]) {result[k++] = arr1[i++];} else {result[k++] = arr2[j++];}}// 将剩余元素复制到结果数组while (i < m) {result[k++] = arr1[i++];}while (j < n) {result[k++] = arr2[j++];}
}

但是有一个问题，就是这个方法的时间复杂度较高为O( $n^{2}$ )