数据结构【顺序表】

目录

​

线性表

顺序表

概念与结构

分类

静态顺序表

动态顺序表

动态顺序表的实现

在头文件中创建结构体

初始化顺序表

销毁顺序表（可以留到后面再看）

尾插数据

申请空间

打印顺序表数据

头插数据

尾删除数据

头删除数据

在指定位置插入数据

在指定位置删除数据

查询数据

顺序表算法题

移除元素

删除有序数组中的重复项

合并两个有序数组

代码

---

线性表

++++1

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

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

线性表是具有相同特性的集合，就比如现实生活中的，水果有苹果，香蕉，西瓜等等....，这些都是水果类型的。线性表：顺序表、链表、栈、队列、字符串等等...

---

顺序表

概念与结构

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

逻辑结构：就像一家早餐店早上有很多人排队，排成一条线，这就是逻辑结构，都是线性的

顺序表也是数组，顺序表在物理结构不一定连续，在逻辑结构是连续的，

---

顺序表和数组的区别？ 顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝。

下面这张图，苍蝇馆子就像数组，米其林餐厅就像顺序表，一个普普通通的炒西蓝花，在米其林餐厅西蓝花+料汁+小饰品+摆盘就变成了绿野仙踪，

顺序表也是一样在数组的基础上加了（增加数据，删除数据，修改数据，查找数据）就变成了顺序表

---

分类

静态顺序表

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

静态数组只需要，定长数组，有效数据个数

静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费

静态顺序表不推荐用，如果要存放用户数据的话，当数据存满了，剩下的数据就会丢失。

---

动态顺序表

动态顺序表需要有效个数，空间的容量，a也可以说就是个数组

---

动态顺序表的实现

代码在文章最后

我们需要创建一个seqlist.h头文件，seqlist.c文件存放函数，还有一个.c的测试文件。

---

在头文件中创建结构体

把int 重命名为 data，这样方便修改类型，就不用一个一个修改了

---

初始化顺序表

我们要在头文件声明一下，这样的话我们可以方便查看有什么函数，就像我们看一本书，书有目录方便我们阅读。

---

初始化我们需要把arr赋值为NULL，有效个数和空间容量赋值为0就好了。

如果我们现在申请空间，会导致空间满了我们没法调整。

我们只需要添加数据的数据（申请/调整）空间就好了。

---

我们可以发现初始化成功了

---

销毁顺序表（可以留到后面再看）

这里我先讲顺序表销毁，也可以先往后看，最后再来看销毁。

我们申请空间用完了需要还，不然存在空间泄露。

---

if判断结构体里arr的有没有数据,有数据就free释放空间，有效个数和空间容量赋值为0。

arr没有数据的话，就是为NULL，就不释放空间了。

---

尾插数据

尾插数据我们只需要在size这个位置插入数据，然后++就可以了。

没有数据的话会在0下标位置插入数据，然后++。

---

这里有2个参数，第二个参数是要插入的数据

---

申请空间

空间容量 等于 有效个数，就说明空间不够，需要申请空间。

 申请空间2倍2倍增加，这样可以避免空间不够，或者空间给多了，2倍2倍增加可以小部分避免空间不够，或者空间给多了。

0乘任何数都得0。空间容量一开始就是0,我们需要先给个4。

这有2个临时的变量。

三目操作符这个，空间容量等于0,就给4，不等于0 就空间大小乘2。

然后realloc给 arr 申请空间 ，app得到的是字节，还需要乘类型大小，才能得到类型需要的空间。

if判断是不是等于NULL。是就报错然后退出，

不是就把创建的临时变量tab赋值给arr，

app赋值给koj空间容量。

---

---

在arr下标为size的位置插入数据。然后++。

---

我们可以看到，1,2,3,4都有了。

---

打印顺序表数据

---

i小于有效个数

---

我们可以看到1,2,3,4都打印出来了。

---

头插数据

---

这个就是把全部数据往后移动1位，然后在0下标插入数据

---

打印结果

---

尾删除数据

---

尾删除，我们只需要把size往后移动1位就行了

---

我们可以看到4没了。

头删除数据

---

就是把1下标到3下标往前移动1位，就行了。

---

我们发现1删除了

---

在指定位置插入数据

这里多了个参数，int a这个是要插入数据的下标，要把数据插入那个下标。

---

把a下标往后的数据，向后移动1位，然后在a下标位置插入数据。

---

我们可以发现在2下标位置，插入了99

---

在指定位置删除数据

int a是要删除的下标

---

把a下标位置后面的数据，向前移动1位

---

我们发现2删除了，2的下标是1

---

查询数据

---

我们可以通过循环的方式查询，找到了返回下标

---

我们可以看到，返回的下标是2

---

顺序表算法题

移除元素

https://leetcode.cn/problems/remove-element/description/

int s1=0;int s2=0;while(s1<numsSize){if(nums[s1]==val){s1++;}else{nums[s2++]=nums[s1++];}}return s2;

删除有序数组中的重复项

 https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

int sl1=0;int sl2=0;while(sl1 < numsSize){if(nums[sl1]==nums[sl2]){sl1++;}else{sl2++;nums[sl2]=nums[sl1];}}return sl2+1;

合并两个有序数组

 https://leetcode.cn/problems/merge-sorted-array/description/

 int s1 = m-1;int s2 = n-1;int s3 = m + n - 1;while(s1>=0 && s2 >=0 ){if(nums1[s1]<nums2[s2]){nums1[s3--]=nums2[s2--];}else{nums1[s3--]=nums1[s1--];}}while(s2>=0){nums1[s3--]=nums2[s2--];}

代码

seqlist.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int data;
typedef struct sxb
{data* arr;int size;//有效个数int koj;//空间容量}SL;//给整个结构体命名SL//初始化顺序表
void csh(SL* r);
//销毁顺序表
void xiaoh(SL* r);
//尾插数据
void weic(SL* r,data x);
//打印
void day(SL* r);
//头插数据
void toc(SL* r,data x);
//尾删除
void weisc(SL* r);
//头删除
void tosc(SL* r);
//指定位置插入
void zhidcr(SL* r,int a,data x);
//在指定位置删除数据
void zhidsc(SL* r, int a);
//查询数据
int cxsj(SL* r, data x);

seqlist.c

#include"seqlist.h"
//初始化顺序表
void csh(SL* r)
{r->arr = NULL;r->size = 0;r->koj = 0;
}
//销毁顺序表
void xiaoh(SL* r)
{if (r->arr != NULL){free(r->arr);}r->koj = 0;r->size = 0;
}
//判断空间
void pdkoj(SL* r)
{if (r->koj == r->size){//三目操作符int app = r->koj == 0 ? 4 : r->koj * 2;//申请空间data* tab = (data*)realloc(r->arr, app * sizeof(data));if (tab == NULL){perror("realloc");exit(1);}//赋值r->arr = tab;r->koj = app;}
}//尾插数据
void weic(SL* r,data x)
{assert(r);//和r != NULL一样//判断空间够不够，不够（调整/开辟）空间pdkoj(r);//插入数据r->arr[r->size] = x;//size + 1r->size++;
}
//打印
void day(SL* r)
{assert(r);//和r != NULL一样//循环打印for (int i = 0; i < r->size; i++){printf("%d ", r->arr[i]);}
}
//头插数据
void toc(SL* r, data x)
{assert(r);pdkoj(r);//把全部数据，都往后移动1位for (int i = r->size; i > 0; i--){r->arr[i] = r->arr[i - 1];}//在0下标插入数据r->arr[0] = x;r->size++;
}//尾删除
void weisc(SL* r)
{assert(r);//把size向后移动1位r->size--;
}//头删除
void tosc(SL* r)
{assert(r);//把1下标 到 3下标往前移动1位for (int i = 0; i < r->size-1; i++){r->arr[i] = r->arr[i + 1];}//删除完size往后移动1位r->size--;
}
//指定位置插入
void zhidcr(SL* r,int a, data x)
{assert(r);pdkoj(r);//把a下标往后的数据移动1位for (int i = r->size; i > a; i--){r->arr[i] = r->arr[i - 1];}//在a下标的位置插入数据r->arr[a] = x;r->size++;
}
//指定位置删除数据
void zhidsc(SL* r, int a)
{assert(r);//把a下标位置后面的数据，向前移动1位for (int i = a; i < r->size-1; i++){r->arr[i] = r->arr[i + 1];}//size--r->size--;
}
//查询数据
int cxsj(SL* r, data x)
{assert(r);for (int i = 0; i < r->size; i++){if (r->arr[i] == x){//找到了返回下标return i;}}//没找到返回-1return -1;
}

测试.c文件

#include"seqlist.h"
void cs()
{SL add;//初始化csh(&add);//尾插weic(&add, 1);weic(&add, 2);weic(&add, 3);weic(&add, 4);//打印day(&add);//查询数据int q = cxsj(&add, 3);if (q < 0){printf("没有找到\n");}else{printf("找到了，下标是: %d", q);}//销毁xiaoh(&add);
}
int main()
{cs();return 0;