顺序表@线性表

文章目录

0. 线性表概念

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

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

1. 顺序表概念及结构

🔑顺序表就是数组，在数组的基础上要求从头开始，要求数据挨着挨着连续存储，没有跳跃间隔。

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。

#defineN1000typedefint SLDataType;//静态顺序表typedefstructSeqList{
    SLDataType data[N];int size;//表示数组中存储多少个数据}SL;

静态顺序表的缺点：

❄️1. 如果满了，就无法再插入。
❄️2. 数组大小给多少合适？这个很难确定，N给小了不够用，N给大了浪费。

因此现实中我们基本都是使用动态顺序表，动态分配内存空间，所以下面我们实现动态顺序表。

1. 动态顺序表：使用动态开辟的数组存储。

typedefint SLDataType;//动态顺序表typedefstructSeqList{
    SLDataType* a;int size;//表示数组中存储多少个有效数据int capacity;//数组实际能存数据的容量}SL;

2. 顺序表的增删查改

函数接口 ——

SeqList.h

本文希望展现一套自然而然又理所当然的思路，都配了图，建议复制所有函数接口自己写自己调，感受会很好，至于完整代码也附在后面了。

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>//条件为真--没事，条件为假--终止程序typedefint SLDataType;//动态顺序表typedefstructSeqList{
    SLDataType* a;int size;//表示数组中存储多少个有效数据int capacity;//数组实际能存数据的容量}SL;//接口函数--命名风格跟着STL走，方便后续学习STLvoidSeqListInit(SL* ps);voidSeqListPrint(SL* ps);voidSeqListCeckCapacity(SL* ps);voidSeqListDestroy(SL* ps);//尾插voidSeqListPushBack(SL* ps, SLDataType x);//尾删voidSeqListPopBack(SL* ps);//头插voidSeqListPushFront(SL* ps, SLDataType x);//头删voidSeqListPopFront(SL* ps);//指定位置插入voidSeqListInsert(SL* ps,int pos,SLDataType x);//删除指定位置数据voidSeqListErase(SL* ps,int pos);//查找intSeqListFind(SL* ps, SLDataType x);//若找到--则返回下标//找不到--返回-1intSeqListFind(SL* ps, SLDataType x);

2.0 初始化、销毁、打印基本接口

2.0.1 初始化

初始化很有必要。开始时，顺序表中什么数据也没有，甚至也还没有为它动态申请一段空间。

因此，

ps->a

要置NULL，标识它是野指针。

ps->size

和

ps->capacity

都要置0，否则就是随机值了。

voidSeqListInit(SL* ps){assert(ps);
    ps->a =NULL;
    ps->size = ps->capacity =0;}

注意：为什么传的是这个顺序表的地址？这是因为函数传参，形参是实参的拷贝，形参的改变不会影响实参。

2.0.2 打印

我们要写一点，就打印出来验证一下正确性，就写一个打印函数，遍历即可很简单。

voidSeqListPrint(SL* ps){assert(ps);int i =0;for(i =0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");}

2.0.3 销毁

现在我们写的是动态顺序表，那么

malloc

/

realloc

动态申请的空间，要记得释放，否则会发生内存泄漏。

关于此，可以复习一下这篇文章 动态内存函数，我顺便也复习了一下，发现有些东西用惯了之后，对于它们是怎么来的会有点淡忘。

voidSeqListDestroy(SL* ps){assert(ps);free(ps->a);
    ps->a =NULL;
    ps->size = ps->capacity =0;}

2.1 尾插尾删

2.1.1 扩容接口

🔑但凡插入数据就要考虑，空间够不够用是否需要增容的问题

voidSeqListCeckCapacity(SL* ps){assert(ps);if(ps->size == ps->capacity){//1.没有空间 —— 申请空间//2.空间不够 —— 扩容int newcapacity = ps->capacity ==0?4:2* ps->capacity;
        SLDataType* tmp =(SLDataType*)realloc(ps->a, newcapacity*sizeof(SLDataType));if(tmp ==NULL){printf("扩容失败\n");exit(-1);}
        ps->a = tmp;
        ps->capacity = newcapacity;}}

这里可能唯一要注意一下的，就是

realloc

函数，文档中如是写——

因此我们把 第一次申请空间 与 后期的调整空间 完美融合写在一起了，同时处理了没有空间和空间不够两种情况。

2.1.2 尾插

voidSeqListPushBack(SL* ps, SLDataType x){assert(ps);SeqListCheckCapacity(ps);
    ps->a[ps ->size]= x;
    ps->size++;}

2.1.3 尾删

🔑 删除数据就要考虑是不是删空了，没的删了，却还在调用这个函数，那就不对了

推荐直接断言暴力终止掉程序，毕竟，就是你用错了。

voidSeqListPopBack(SL* ps){assert(ps);assert(ps->size);//断言暴力终止掉程序。若出现删多了的情况，就蹦出窗口终止程序
    ps->size--;}

断言效果 ——

2.2 头插头删

2.2.1 头插

• 插入数据依然要考虑扩容问题
• 无论是头插还是头删，为了保证顺序表从开始位置连续，都需要挪动数据 —— 想好是从尾 还是 从头 开始挪动，保证数据不会被覆盖丢失。
• 画好图，时刻注意边界

voidSeqListPushFront(SL* ps, SLDataType x){assert(ps);SeqListCheckCapacity(ps);int end = ps->size -1;while(end >=0){
        ps->a[end +1]= ps->a[end];
        end--;}
    ps->a[0]= x;
    ps->size++;}

2.2.2 头删

• 删除数据依然要考虑删空时，越界访问的情况
• 画图注意边界

voidSeqListPushFront(SL* ps, SLDataType x){assert(ps);SeqListCheckCapacity(ps);int end = ps->size -1;while(end >=0){
        ps->a[end +1]= ps->a[end];
        end--;}
    ps->a[0]= x;
    ps->size++;}

2.3 指定位置插入、删除指定位置数据、查找

查找常和指定位置插入、指定位置删除搭配使用。

2.3.1 查找

//查找--找到了则返回x位置下标，没有找到则返回-1intSeqListFind(SL* ps, SLDataType x){int i =0;for(i =0; i < ps->size; i++){if(ps->a[i]== x){return i;}}return-1;}

2.3.2 指定位置插入

与头插完全类似

voidSeqListInsert(SL* ps,int pos, SLDataType x){assert(ps);SeqListCheckCapacity(ps);int end = ps->size -1;while(end >= pos){
        ps->a[end +1]= ps->a[end];
        end--;}
    ps->a[pos]= x;
    ps->size++;}

2.3.3 删除指定位置数据

与头删完全类似

voidSeqListErase(SL* ps,int pos){assert(ps);assert(ps->size);int start = pos +1;while(start < ps->size){
        ps->a[start -1]= ps->a[start];
        start++;}
    ps->size--;}

2.3.4 复用

有了指定位置插入和指定位置删除，就可以复用这些接口，完成头插头删尾插尾删 ——

//尾插voidSeqListPushBack(SL* ps, SLDataType x){SeqListInsert(ps, ps->size, x);}//尾删voidSeqListPopBack(SL* ps){SeqListErase(ps, ps->size -1);}//头插voidSeqListPushFront(SL* ps, SLDataType x){SeqListInsert(ps,0, x);}//头删voidSeqListPopFront(SL* ps){SeqListErase(ps,0);}

分分钟搞定。

3. 顺序表的问题及思考

• 顺序表优点 ——支持随机访问，方便做查找。
• 顺序表缺陷 ——

1. 空间不够需要增容，增容是要付出代价的。
2. 为了避免频繁扩容，我们基本都是按倍数去扩（扩2倍），可能会造成一定的空间浪费。
3. 顺序表要求数据从开始位置保持连续，那么中间和头部的插入，就需要挪动数据，时间复杂度为*O(N)*，效率不高。

针对顺序表的缺陷，引出了下一节 —— 链表

未完待续@边通书

附：源代码

SeqList.h

#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>//条件为真-没事，条件为假-终止程序typedefint SLDataType;//动态顺序表typedefstructSeqList{
    SLDataType* a;int size;//表示数组中存储多少个数据int capacity;//数组实际能存数据的容量}SL;//接口函数--命名风格跟着STL走，方便后续学习STLvoidSeqListInit(SL* ps);voidSeqListPrint(SL* ps);voidSeqListDestroy(SL* ps);voidSeqListCheckCapacity(SL* ps);//尾插voidSeqListPushBack(SL* ps, SLDataType x);//尾删voidSeqListPopBack(SL* ps);//头插voidSeqListPushFront(SL* ps, SLDataType x);//头删voidSeqListPopFront(SL* ps);//指定位置插入voidSeqListInsert(SL* ps,int pos, SLDataType x);//删除指定位置的数据voidSeqListErase(SL* ps,int pos);//查找--找到了则返回x位置下标，没有找到则返回-1intSeqListFind(SL* ps, SLDataType x);

SeqList.c

#define_CRT_SECURE_NO_WARNINGS1#include"SeqList.h"voidSeqListInit(SL* ps){assert(ps);
    ps->a =NULL;
    ps->size = ps->capacity =0;}voidSeqListPrint(SL* ps){assert(ps);int i =0;for(i =0; i < ps->size; i++){printf("%d ", ps->a[i]);}printf("\n");}voidSeqListDestroy(SL* ps){assert(ps);free(ps->a);
    ps->a =NULL;}voidSeqListCheckCapacity(SL* ps){assert(ps);if(ps->size == ps->capacity){int newcapacity =(ps->capacity ==0)?4: ps->capacity *2;
        SLDataType* tmp =(SLDataType*)realloc(ps->a,sizeof(SLDataType)*newcapacity);if(tmp ==NULL){printf("realloc failed\n");exit(-1);}
        ps->a = tmp;
        ps->capacity = newcapacity;}}voidSeqListPushBack(SL* ps, SLDataType x){SeqListInsert(ps, ps->size, x);//assert(ps);//SeqListCheckCapacity(ps);//ps->a[ps->size] = x;//ps->size++;}voidSeqListPopBack(SL* ps){SeqListErase(ps, ps->size -1);//assert(ps);//assert(ps->size);//ps->size--;}voidSeqListPushFront(SL* ps, SLDataType x){SeqListInsert(ps,0, x);/*assert(ps);
    SeqListCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0)
    {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;*/}voidSeqListPopFront(SL* ps){SeqListErase(ps,0);//assert(ps);//assert(ps->size);//int start = 1;//while (start < ps->size)//{//    ps->a[start - 1] = ps->a[start];//    start++;//}//ps->size--;}voidSeqListInsert(SL* ps,int pos, SLDataType x){assert(ps);SeqListCheckCapacity(ps);int end = ps->size -1;while(end >= pos){
        ps->a[end +1]= ps->a[end];
        end--;}
    ps->a[pos]= x;
    ps->size++;}voidSeqListErase(SL* ps,int pos){assert(ps);assert(ps->size);int start = pos +1;while(start < ps->size ){
        ps->a[start -1]= ps->a[start];
        start++;}
    ps->size--;}intSeqListFind(SL* ps, SLDataType x){assert(ps);int i =0;for(i =0; i < ps->size; i++){if(ps->a[i]== x)return i;}return-1;}

test.c

关于测试文件，就是随写随测，把每种情况都测到，这里主要是增容呀，删空时的越界访问呀，还有就是基本的逻辑，把我自己的贴出来

#define_CRT_SECURE_NO_WARNINGS1#include"SeqList.h"//测试尾插尾删voidTestSeqList1(){
    SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPushBack(&sl,5);SeqListPrint(&sl);SeqListPopBack(&sl);SeqListPopBack(&sl);SeqListPopBack(&sl);SeqListPopBack(&sl);//SeqListPopBack(&sl);//SeqListPopBack(&sl);SeqListPrint(&sl);SeqListDestroy(&sl);}//测试头插头删voidTestSeqList2(){
    SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPushBack(&sl,5);SeqListPrint(&sl);SeqListPushFront(&sl,0);SeqListPushFront(&sl,-1);SeqListPushFront(&sl,-2);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPopFront(&sl);SeqListPrint(&sl);printf("%d\n",SeqListFind(&sl,3));SeqListDestroy(&sl);}//测试指定位置的插入删除voidTestSeqList3(){
    SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPushBack(&sl,5);SeqListInsert(&sl,2,30);SeqListInsert(&sl,0,0);SeqListInsert(&sl, sl.size,80);SeqListPrint(&sl);//配合使用int pos =SeqListFind(&sl,4);if(pos !=-1){SeqListInsert(&sl, pos,40);}SeqListPrint(&sl);SeqListDestroy(&sl);}//复用SeqListInsert测试头插尾插voidTestSeqList4(){
    SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPushBack(&sl,5);SeqListPushFront(&sl,1);SeqListPushFront(&sl,2);SeqListPushFront(&sl,3);SeqListPushFront(&sl,4);SeqListPushFront(&sl,5);SeqListPrint(&sl);SeqListPopFront(&sl);SeqListPopFront(&sl);SeqListPopBack(&sl);SeqListPopBack(&sl);SeqListPrint(&sl);//假如我要删3int pos =SeqListFind(&sl,3);if(pos !=-1){SeqListErase(&sl, pos);}SeqListPrint(&sl);SeqListDestroy(&sl);}intmain(){//TestSeqList1();//TestSeqList2();//TestSeqList3();TestSeqList4();return0;}