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

【数据结构】顺序表

news 2026/5/23 23:08:34

其他篇章【Linux专栏】

其他篇章【C语言专栏】

上期回顾【Linux】网络基础2—Socket编程预备

文章目录

前言
1.顺序表的概念及结构
- 常⻅的线性表
- 1.1线性表
2.顺序表分类
3.动态顺序表的实现

前言

在此之前我们先来了解一下什么是数据结构?
数据结构是由“数据”和“结构”两词组合⽽来。
什么是数据？
常⻅的数值1、2、3、4…、教务系统⾥保存的⽤⼾信息（姓名、性别、年龄、学历等等）、⽹⻚⾥⾁眼可以看到的信息（⽂字、图⽚、视频等等），这些都是数据.
什么是结构？
当我们想要使⽤⼤量使⽤同⼀类型的数据时，通过⼿动定义⼤量的独⽴的变量对于程序来说，可读性⾮常差，我们可以借助数组这样的数据结构将⼤量的数据组织在⼀起，结构也可以理解为组织数据的⽅式。

概念：数据结构是计算机存储、组织数据的⽅式。数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成，即数据由那部分构成，以什么⽅式构成，以及数据元素之间呈现的结构

数组是最基础的数据结构

1.顺序表的概念及结构

在了解顺序表之前，我们先来了解一下线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。

常⻅的线性表

顺序表、链表、栈、队列、字符串... 线性表

顺序表逻辑结构：连续
顺序表物理结构：不一定连续

1.1线性表

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

2.顺序表分类

静态顺序表：使⽤定⻓数组存储元素
缺陷：空间给少了不够用，给多了浪费
动态顺序表：

3.动态顺序表的实现

SeqList.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintSLdatatype;typedefstructSeqList{SLdatatype*arr;intsize;intcapacity;//空间容量}SL;//SL是对结构体SeqList的重命名//顺序表初始化voidSLInit(SL*ps);//打印顺序表voidSLPrint(SL*ps);//尾插voidSLPushBack(SL*ps,SLdatatype x);//头插voidSLPushFront(SL*ps,SLdatatype x);//尾删voidSLPopBack(SL*ps);//头删voidSLPopFront(SL*ps);

SeqList.c

#define_CRT_SECURE_NO_WARNINGS1#include"SeqList.h"//初始化voidSLInit(SL*ps){ps->arr=NULL;ps->size=0;ps->capacity=0;//空间容量}//打印// size是有效的数据个数voidSLPrint(SL*ps){for(inti=0;i<ps->size;i++){printf("%d ",ps->arr[i]);}printf("\n");}voidSLCheckCapacity(SL*ps){//检查顺序表容量是否已满intnewcapacity=ps->capacity==0?4:2*ps->capacity;//为真->则为四个字节的容量（int类型）；为假->则扩容原容量的2倍//用tmp接收realloc返回值（避免直接覆盖ps->arr,防止扩容失败丢失原地址）SLdatatype*tmp=(SLdatatype*)realloc(ps->arr,newcapacity*sizeof(SLdatatype));if(tmp==NULL){perror("realloc");exit(1);//非0表示程序异常终止}ps->arr=tmp;ps->capacity=newcapacity;}//尾插voidSLPushBack(SL*ps,SLdatatype x){assert(ps);//检查空间是否足够SLCheckCapacity(ps);//空间足够ps->arr[ps->size++]=x;}//头插voidSLPushFront(SL*ps,SLdatatype x){assert(ps);//检查空间是否足够SLCheckCapacity(ps);//空间足够for(inti=ps->size;i>0;i--){ps->arr[i]=ps->arr[i-1];//for循环，原数据全部向后移动一位}ps->arr[0]=x;//将要头插的数据插入到数组首位ps->size++;}//尾删voidSLPopBack(SL*ps){assert(ps&&ps->size);ps->size--;}//头删voidSLPopFront(SL*ps){assert(ps&&ps->size);for(inti=0;i<ps->size-1;i++){ps->arr[i]=ps->arr[i+1];//将所有元素向后移动一位}ps->size--;}

test.c

#define_CRT_SECURE_NO_WARNINGS1#include"SeqList.h"voidtest(){SL s;//s->结构体变量SLInit(&s);//只能传地址//尾插SLPushBack(&s,5);SLPushBack(&s,2);SLPushBack(&s,0);SLPushBack(&s,4);//打印SLPrint(&s);//5 2 0 4//头插SLPushFront(&s,8);SLPrint(&s);// 8 5 2 0 4//尾删SLPopBack(&s);SLPopBack(&s);SLPrint(&s);// 8 5 2//头删SLPopFront(&s);SLPrint(&s);//5 2}intmain(){test();}

运行结果：

注意：

为什么只能传地址呢?
1.传值时,ps是临时值的拷贝,SLInit 的参数是 SL* ps （指针），如果传值（比如传 s1而不是 &s1），会出现两个错误：
编译报错： SLInit(s) 中， s 是 SL 类型，而 SLInit 需要 SL* 类型（指针），类型不匹配，直接编译失败
退一步说，即使强行传值（比如错误写 SLInit((SL*)s1) ）， ps 会变成一个指向随机内存的野指针，执行 ps->arr = NULL 时会触发内存访问违规，程序直接崩溃。
2.调用时,实参s的整个结构体内容(包括垃圾值的arr/size/capacity)会被拷贝一份 ,赋值给形参ps,而在函数void SLPrint(SL* ps)内修改的是赋值后的形参ps,和实参无关系,在函数执行完之后,形参ps被销毁,实参依然是未初始化的垃圾值