🎈今日心语:你所看到的惊艳,都曾被平庸所历练。
前言:继【时间复杂度和空间复杂】度之后,本章我们来介绍数据结构中的顺序表和链表,若觉得文章不错,希望支持一下博主👍,如果发现有问题也欢迎❀大家在评论区指正。
文章目录
1.线性表
线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储。
2.顺序表(数组)
2.1概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为静态顺序表和动态顺序表:
- 静态顺序表:使用定长数组存储元素。
- 缺陷:给小了不够用,给大了可能浪费,不实用。
- 动态顺序表:使用动态开辟的数组存储。
- 动态顺序表可根据我们的需要分配空间大小
- size 表示当前顺序表中已存放的数据个数
- capacity 表示顺序表总共能够存放的数据个数
2.2 动态顺序表的接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了,空间开多了浪费,开少了不够用。所以现实中基本都是使用动态顺序表,根据需要动态的分配空间大小,所以下面我们实现动态顺序表。
首先新建一个工程:
- SeqList.h(顺序表的类型定义、接口函数声明、引用的头文件)
- SeqList.c(顺序表接口函数的实现)
- Test.c(主函数、测试顺序表各个接口功能)
(1)初始化顺序表:
- 记得一定要加上断言,防止传进来的指针为空
- “->”在声明结构体指针时,访问结构体成员变量时使用。
- “.”在声明结构体时,访问结构体成员变量时使用。
void SLInit(SL* ps)//初始化顺序表 { assert(ps);//断言,为真执行,为假终止,报错 ps->a = NULL; //初始数据表为空 ->在声明结构体指针时,访问结构体成员变量时使用 ps->size = 0; //初始数据个数为0 ps->capacity = 0;//初始空间容量为0 }
(2)内存空间的释放(销毁)
void SLDestroy(SL* ps) { //if(ps->a !=NULL) assert(ps); if (ps->a) //为真说明内存开辟成功,需要释放置空 { free(ps->a); //释放,free报错往往是越界,或者是释放的地方不对,一般free的时候才会检查越界 ps->a = NULL; //置空 ps->size = ps->capacity = 0;//释放后进行初始化 } }
(3)检查容量,若满则扩容
size和capacity相等时,可能是还没有开辟空间(这时capacity和size为0),也可能是空间已满。为了方便,我们直接将已满的空间扩大2倍,所以还需要判断是哪种情况。
- realloc后面的参数是大小,前面的参数是需要进行扩容的空间。
- relloc返回的是新开空间的地址,需要用临时变量tmp接收地址。
void SLCheckCapacity(SL* ps)//检查,扩容 { assert(ps); //判断空间是否满,否则涉及到越界问题 //判断size和capacity是否相等,相等则满,或者还没开辟空间,因为开始时都初始化为0 if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果是0还没开辟空间,如果不是就直接扩为2倍 SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//扩容 ,realloc后面的参数是大小,前面的是需要扩容的空间//需要用临时变量tmp接收地址,因为relloc返回的是新开空间的地址 if (tmp == NULL)//判断扩容是否成功 { perror("relloc fail"); exit(-1); //-1异常终止程序,0代表正常终止 } ps->a = tmp; ps->capacity = newCapacity; } }
(4)顺序表尾插
size指向的位置刚好是最后一个元素的后一个元素,所以尾插时直接插到size指向的位置即可。
//尾插 时间复杂度O(1) void SLPushBack(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps);//检查容量 ps->a[ps->size] = x; ps->size++; }
- 写代码时应该边写边测,及时找到错误,否则后面很难找到。
(5)顺序表打印
size前面刚好是最后一个数据,所以这里 i < ps->size;
//打印函数 void SLPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; ++i) { printf("%d ", ps->a[i]); } printf("\n"); }
(6)顺序表尾删
- ps->a[ps->size - 1] = 0;将最后一个数据改为0,再size–,意义不大,因为print是以size为基础的,只会访问size前面的有效数据,再插入数据会将无效数据直接覆盖,所以直接ps-> size–;
- size–;当size=0时再进行会导致size出现负数,后面如果再尾插,插入到了不属于自己的空间,就是越界访问,所以我们前面必须进行检查,而如下“温柔的检查”很难让我们发现错误,所以使用assert(断言,“暴力的检查”)可以帮助我们及时发现错误。
//尾删 void SLPopBack(SL* ps) { //温柔的检查 //*if (ps->size == 0) //{ // return; //}*/ //暴力的检查(断言) assert(ps->size > 0);//会直接报错,为真继续走,为假结束 //ps->a[ps->size - 1] = 0;//将最后一个数据改为0,再size--,意义不大,因为print是以size为基础的,只会访问size前面的数据,再插入数据会将无效数据直接覆盖 ps->size--; }
如下图:暴力检查的好处是,当size=0时,再向下执行,会直接终止程序报错。若没有检查,size取到负值。
若不加入assert,程序会在size变为负值后进行尾插时报错。但是去掉SLDestroy(&sl);会发现程序不报错,说明程序在释放的时候才会检查出问题,但也有随机性,这时一般会报错free。
越界不一定报错,系统对越界的检查是一种抽查
- 越界读一般是检查不出来的
- 越界写如果是修改到标志位才会检查出来
(系统在数组末尾后设的有标志位,越界写时,恰好修改到标志位了,就会被检查出来)
(7)顺序表头插
要想头插,就得先将后面的数据从后依次向后挪动:
//头插 时间复杂度O(N) void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps);//检查容量 //挪动数据 int end = ps->size - 1;//size-1是最后一个元素的下标 while (end >= 0) { ps->a[end + 1] = ps->a[end]; --end; } ps->a[0] = x; ps->size++; }
(8)顺序表头删
//头删 void SLPopFront(SL* ps) { assert(ps); assert(ps->size>0); int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }
(9)在指定下标位置插入数据
//在pos位置插入数据 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0); assert(pos <= ps->size);//必须是连续存储 SLCheckCapacity(ps);//考虑到后面空间不够可能越界 int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; }
- 实现了此接口,同样可以进行头插和尾插,可以进行复用以改进顺序表头插和尾插的代码:
头插尾插代码改进
//头插O(N) void SLPushFront(SL* ps, SLDataType x) { //assert(ps); //SLCheckCapacity(ps); ////挪动数据 //int end = ps->size - 1;//size-1是最后一个元素的下标 //while (end >= 0) //{ // ps->a[end + 1] = ps->a[end]; // --end; //} //ps->a[0] = x; //ps->size++; SLInsert(ps, 0, x);//复用 }
//尾插O(1) void SLPushBack(SL* ps, SLDataType x) { /*assert(ps); SLCheckCapacity(ps); ps->a[ps->size] = x; ps->size++;*/ SLInsert(ps, ps->size, x);//复用 }
(10)删除指定下标位置数据
方法与头删类似,这里不作演示.
//删除pos位置数据 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0); assert(pos < ps->size); //assert(ps->size > 0); //挪动数据覆盖 int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; }
- 实现了此接口,同样可以进行头删和尾删,同样可以进行复用以改进顺序表头删和尾删的代码:
头删尾删代码改进:
//头删 void SLPopFront(SL* ps) { /*assert(ps); assert(ps->size>0); int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--;*/ SLErase(ps, 0);//复用 }
//尾删 void SLPopBack(SL* ps) { ////温柔的检查 ///*if (ps->size == 0) //{ // return; //}*/ ////暴力的检查(断言) //assert(ps->size > 0);//会直接报错,为真继续走,为假结束 ////ps->a[ps->size - 1] = 0;//将最后一个数据改为0,再size--,意义不大,因为print是以size为基础的,只会访问size前面的数据,再插入数据会将无效数据直接覆盖 //ps->size--; SLErase(ps, ps->size - 1);//复用 }
(11)查找,删除指定数据
- 查找数据初始代码:
//查找 int SLFind(SL* ps, SLDataType x) { assert(ps); for (int i = 0; i < ps->size; i++) { if (ps->a[i] == x) { return i;//查找到,并返回下标位置 } } return -1;////未找到,返回-1 }
- 测试,删除数据初始代码:
void TestSeqList6() { SL sl;//定义顺序表的结构 SLInit(&sl);//初始化,传给了SeqList.c中的函数,实参,传给形参,形参是实参的临时拷贝 SLPushBack(&sl, 1);//尾插数据 SLPushBack(&sl, 2);//尾插数据 SLPushBack(&sl, 3);//尾插数据 SLPushBack(&sl, 4);//尾插数据 SLPushBack(&sl, 5);//尾插数据 SLPushBack(&sl, 7);//尾插数据 SLPushBack(&sl, 8);//尾插数据 SLPushBack(&sl, 5);//尾插数据 SLPrint(&sl); int pos = SLFind(&sl, 5);//查找5 if (pos != -1)//为真,找到了 { SLErase(&sl, pos);//删除下标位置数据 } SLPrint(&sl); SLDestroy(&sl); } int main() { TestSeqList6(); return 0; }
如上图删除了指定的数据5,但是如果有几个相同的数据呢,想要删除前面的,中间的,结尾的或者全部的5该怎么办呢?
查找数据最终代码:
//查找改进,针对有重复数据 //加入参数 从begin起始位置开始查找 int SLFind(SL* ps, SLDataType x,int begin) { assert(ps); for (int i = begin; i < ps->size; i++) { if (ps->a[i] == x) { return i;//查找到,并返回下标位置 } } return -1;//未找到,返回-1 }
此时,测试,删除数据的代码也要进行略微改动。
测试,删除数据最终代码:
void TestSeqList6() { SL sl;//定义顺序表的结构 SLInit(&sl);//初始化,传给了SeqList.c中的函数,实参,传给形参,形参是实参的临时拷贝 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 7); SLPushBack(&sl, 8); SLPushBack(&sl, 5); SLPrint(&sl); /*int pos = SLFind(&sl, 5); if (pos != -1) { SLErase(&sl, pos); } SLPrint(&sl);*/ //原来代码 int pos = SLFind(&sl, 4,0);//从0开始查找 if (pos != -1) { SLErase(&sl, pos); } SLPrint(&sl); //删除所有的5 pos = SLFind(&sl, 5, 0); while (pos != -1) { SLErase(&sl, pos); pos = SLFind(&sl, 5, pos);//从删除5的位置继续往后找 } SLPrint(&sl); SLDestroy(&sl); } int main() { TestSeqList6(); return 0; }
(12)补充顺序表菜单
菜单一般在程序结束后写,方便调试。
给出简单菜单:
//菜单 void menu() { printf("********************************************\n"); printf("1、尾插数据 2、尾删数据\n"); printf("3、头插数据 2、头删数据\n"); printf("5、打印数据 -1、退出\n"); printf("********************************************\n"); } int main() { SL s;//定义顺序表 SLInit(&s);//初始化 int val = 0; int option = 0; do { menu(); printf("请输入你的操作:>"); scanf("%d", &option); switch (option) { case 1: printf("请依次输入你要尾插的数据,以-1结束"); scanf("%d", &val); while (val != -1) { SLPushBack(&s, val); scanf("%d", &val); } break; case 2: SLPopFront(&s); break; case 3: break; case 4: break; case 5: SLPrint(&s); break; default: break; } }while (option != -1); SLDestroy(&s); return 0; }
2.3源码:
SeqList.h文件
#pragma once//防止重复调用/包含 #include<stdio.h> #include<stdlib.h> #include<assert.h> //动态顺序表 --按需扩空间 typedef int SLDataType; //为方便维护修改数据类型,重定义顺序表的数据类型 typedef struct SeqList //多个数据定义为结构体, { SLDataType* a; //想到动态开辟内存函数malloc,定义一个指针,指向动态开辟的数组 int size; //有效数据个数 int capacity; //空间容量大小,满了relloc扩容 }SL;//typedef重定义 void SLPrint(SL* ps); //打印函数的声明 //void SeqListInit(SL s); //全称 void SLInit(SL* ps); //定义一个顺序表 void SLDestroy(SL* ps); //释放动态开辟的内存 void SLCheckCapacity(SL* ps); //检查,扩容 //尾插尾删 void SLPushBack(SL* ps, SLDataType x); void SLPopBack(SL* ps); //头插头删 void SLPushFront(SL* ps, SLDataType x); void SLPopFront(SL* ps); //在pos位置插入数据 void SLInsert(SL* ps, int pos, SLDataType x); //删除pos位置数据,删除指定位置的数据 void SLErase(SL* ps, int pos); ////查找数据,为实现删除指定数据 //int SLFind(SL* ps, SLDataType x); //查找改进,针对有重复数据 int SLFind(SL* ps, SLDataType x, int begin);
SeqList.c文件
#include"SeqList.h"//引用头文件 void SLInit(SL* ps) { assert(ps); //初始化 ps->a = NULL;//结构体指针用-> ps->size = 0; ps->capacity = 0; } //打印函数 void SLPrint(SL* ps) { assert(ps); for (int i = 0; i < ps->size; ++i) { printf("%d ", ps->a[i]); } printf("\n"); } void SLDestroy(SL* ps) { //if(ps->a !=NULL) assert(ps); if (ps->a) //为真说明内存开辟成功,需要释放置空 { free(ps->a); //释放,free报错往往是越界,或者是释放的地方不对,一般free的时候才会检查越界 ps->a = NULL; //置空 ps->size = ps->capacity = 0;//顺便修改他俩的值 } } void SLCheckCapacity(SL* ps)//检查,扩容 { assert(ps); //插入前得开空间,判断空间是否满,否则涉及到越界问题 //判断size和capacity是否相等,相等则满,或者还没开辟空间,因为开始时都初始化为0 if (ps->size == ps->capacity) { int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//如果是0还没开辟空间,如果不是就直接扩为2倍 //ps->a = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//扩容 ,realloc后面的参数是大小,前面的是需要扩容的空间//需要接收地址,因为relloc返回的是新开空间的地址 SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));//扩容 ,realloc后面的参数是大小,前面的是需要扩容的空间//需要用临时变量tmp接收地址,因为relloc返回的是新开空间的地址 if (tmp == NULL)//判断扩容是否成功 { perror("relloc fail"); exit(-1);//异常终止程序,0代表正常终止 } ps->a = tmp; ps->capacity = newCapacity; } } //尾插O(1) void SLPushBack(SL* ps, SLDataType x) { /*assert(ps); SLCheckCapacity(ps); ps->a[ps->size] = x; ps->size++;*/ SLInsert(ps, ps->size, x);//复用 } //尾删 void SLPopBack(SL* ps) { //温柔的检查 /*if (ps->size == 0) { return; }*/ //暴力的检查(断言) assert(ps->size > 0);//会直接报错,为真继续走,为假结束 //ps->a[ps->size - 1] = 0;//将最后一个数据改为0,再size--,意义不大,因为print是以size为基础的,只会访问size前面的数据,再插入数据会将无效数据直接覆盖 ps->size--; //SLErase(ps, ps->size - 1);//复用 } //头插O(N) void SLPushFront(SL* ps, SLDataType x) { //assert(ps); //SLCheckCapacity(ps); ////挪动数据 //int end = ps->size - 1;//size-1是最后一个元素的下标 //while (end >= 0) //{ // ps->a[end + 1] = ps->a[end]; // --end; //} //ps->a[0] = x; //ps->size++; SLInsert(ps, 0, x);//复用 } //头删 void SLPopFront(SL* ps) { /*assert(ps); assert(ps->size>0); int begin = 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--;*/ SLErase(ps, 0);//复用 } //在pos位置插入数据 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos >= 0); assert(pos <= ps->size);//必须是连续存储 SLCheckCapacity(ps);//考虑到后面空间不够可能越界 int end = ps->size - 1; while (end >= pos) { ps->a[end + 1] = ps->a[end]; end--; } ps->a[pos] = x; ps->size++; } //删除pos位置数据 void SLErase(SL* ps, int pos) { assert(ps); assert(pos >= 0); assert(pos < ps->size); //assert(ps->size > 0); //挪动数据覆盖 int begin = pos + 1; while (begin < ps->size) { ps->a[begin - 1] = ps->a[begin]; begin++; } ps->size--; } ////查找 //int SLFind(SL* ps, SLDataType x) //{ // assert(ps); // for (int i = 0; i < ps->size; i++) // { // if (ps->a[i] == x) // { // return i; // } // } // return -1; //} //查找改进,针对有重复数据 int SLFind(SL* ps, SLDataType x,int begin) { assert(ps); for (int i = begin; i < ps->size; i++) { if (ps->a[i] == x) { return i; } } return -1; }
test.c文件
在插入菜单前,main函数中调用的测试函数可以根据需要进行修改。
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" void TestSeqList1() { SL sl;//定义顺序表的结构 SLInit(& sl);//初始化,传给了SeqList.c中的函数,实参,传给形参,形参是实参的临时拷贝 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 5); SLPushBack(&sl, 5); SLPushBack(&sl, 5); SLPushBack(&sl, 5);//插入了9个数据,扩了两次容 SLPrint(&sl); SLDestroy(&sl); } void TestSeqList2() { SL sl;//定义顺序表的结构 SLInit(&sl);//初始化,传给了SeqList.c中的函数,实参,传给形参,形参是实参的临时拷贝 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPrint(&sl); SLPopBack(&sl); SLPrint(&sl); SLPopBack(&sl); SLPrint(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); SLPopBack(&sl); //SLPopBack(&sl);//越界调试,size--会导致size出现负数,后面如果再尾插,插入到了不属于自己的空间,就是越界访问 SLPrint(&sl); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLDestroy(&sl);//去掉不报错 } void TestSeqList3() { SL sl;//定义顺序表的结构 SLInit(&sl);//初始化,传给了SeqList.c中的函数,实参,传给形参,形参是实参的临时拷贝 SLPushFront(&sl, 1); SLPushFront(&sl, 2); SLPushFront(&sl, 3); SLPushFront(&sl, 4); SLPrint(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl); SLPopFront(&sl);//四个数据删除五次size为空,运行正常,可能没测试到位 SLPushBack(&sl, 10);//这时就出现了问题,发生了越界,free会报错 SLPrint(&sl); SLDestroy(&sl); } void TestSeqList4() { SL sl;//定义顺序表的结构 SLInit(&sl);//初始化,传给了SeqList.c中的函数,实参,传给形参,形参是实参的临时拷贝 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPrint(&sl); SLInsert(&sl, 2, 20);//第二个位置插入20 SLPrint(&sl); SLInsert(&sl, 5, 500);//相当于尾插,需要考虑复用 SLPrint(&sl); SLInsert(&sl, 0, 100);//相当于头插,需要考虑复用 SLPrint(&sl); SLDestroy(&sl); } void TestSeqList5() { SL sl;//定义顺序表的结构 SLInit(&sl);//初始化,传给了SeqList.c中的函数,实参,传给形参,形参是实参的临时拷贝 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPrint(&sl); SLErase(&sl, 2);//删除下标为2的值 SLPrint(&sl); SLErase(&sl, 2);//删除下标为2的值 SLPrint(&sl); SLErase(&sl, 0);//删除下标为2的值 SLPrint(&sl); SLDestroy(&sl); } void TestSeqList6() { SL sl;//定义顺序表的结构 SLInit(&sl);//初始化,传给了SeqList.c中的函数,实参,传给形参,形参是实参的临时拷贝 SLPushBack(&sl, 1); SLPushBack(&sl, 2); SLPushBack(&sl, 3); SLPushBack(&sl, 4); SLPushBack(&sl, 5); SLPushBack(&sl, 7); SLPushBack(&sl, 8); SLPushBack(&sl, 5); SLPrint(&sl); /*int pos = SLFind(&sl, 5); if (pos != -1) { SLErase(&sl, pos); } SLPrint(&sl);*/ int pos = SLFind(&sl, 4,0);//从0开始查找 if (pos != -1) { SLErase(&sl, pos); } SLPrint(&sl); //删除所有的5 pos = SLFind(&sl, 5, 0); while (pos != -1) { SLErase(&sl, pos); pos = SLFind(&sl, 5, pos);//从删除5的位置继续往后找 } SLPrint(&sl); SLDestroy(&sl); } //int main() //{ // //TestSeqList1(); // //TestSeqList2(); // //TestSeqList3(); // //TestSeqList4(); // //TestSeqList5(); // TestSeqList6(); // // //int* p1 = malloc(4); // //int* p2 = realloc(p1, 20); // //int* p3 = realloc(p2, 2000);//realloc原地扩容和异地扩容的演示 // // ////越界读基本不会被检查出来 // //int a[10] = { 0 }; // //printf("%d\n", a[10]); // //printf("%d\n", a[11]); // // // ////越界写,可能会被检查出来 // ////a[10] = 0;//检查出来 // //a[11] = 0;//未检查出来 // // // // return 0; //} //菜单 void menu() { printf("********************************************\n"); printf("1、尾插数据 2、尾删数据\n"); printf("3、头插数据 2、头删数据\n"); printf("5、打印数据 -1、退出\n"); printf("********************************************\n"); } int main() { SL s;//定义顺序表 SLInit(&s);//初始化 int val = 0; int option = 0; do { menu(); printf("请输入你的操作:>"); scanf("%d", &option); switch (option) { case 1: printf("请依次输入你要尾插的数据,以-1结束"); scanf("%d", &val); while (val != -1) { SLPushBack(&s, val); scanf("%d", &val); } break; case 2: SLPopFront(&s); break; case 3: break; case 4: break; case 5: SLPrint(&s); break; default: break; } }while (option != -1); SLDestroy(&s); return 0; }
结语:
这里本章内容就介绍完了, 希望以上内容对大家有所帮助👀,如有不足望指出🙏
前路漫漫!努力变强💪💪 吧!!