数据结构初阶--顺序表和链表

线性表

1️⃣ 线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表： 2️⃣ 顺序表、 3️⃣ 链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

注：

1️⃣线性的意思是数据以连线的方式存储

2️⃣顺序表本质上就是数组。但是在此之上，顺序表要求存储的数据必须是从头开始、连续紧挨着的，不能跳跃间隔

3️⃣链表是用指针把一块一块内存链接起来

图示：

顺序表在逻辑结构上是连续的，物理结构上也是连续的；
链表在逻辑结构上是连续的，但是在物理结构上不是连续的。

---

顺序表

概念及结构

顺序表是 用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。 顺序表的物理结构和逻辑结构是一致的。

---

插：创建程序的时候，命名尽量用英文。因为日后在工作中各个源文件链接的时候，中文会出现转换问题，引来不必要的麻烦

---

顺序表一般可以分为：

1. 静态顺序表：使用 定长数组存储。 特点是如果满了就不让插入。 缺点是空间给多大合适呢？很难确定。N给小了不够用，给大了浪费
2. 动态顺序表：使用 动态开辟的数组存储。

静态顺序表：

//静态的顺序表，并不实用
#define N 100//一发，动全身
struct SeqList//SeqList:顺序表
{
    int a[N];
    int size;//表示数组中存储了多少个数据
};

注：

用结构体的好处：不仅找到开辟的空间大小，还知道存储的数据个数
以后凡是涉及多个数据的，尽量考虑用结构体

缺点：

因为结构体中定义了数据类型为int,故后续想再插入其它类型的数据就不行了

改进一：可以修改存储的数据类型，插入其它类型的数据

#define N 100
typedef int SLDataType;//int重命名为SLDataType，即顺序表数据类型。以后想插入什么类型就把int改成什么类型
//例如插入double类型，即：typedef double SLDataType;
struct SeqList
{
    SLDataType a[N];
    int size;
};
void SeqListPushBack(struct SeqList* ps, int x);//SeqListPushBack,即顺序表尾部插入

缺点：

struct SeqList太长，不方便

改进二：将struct SeqList重命名为SL，方便使用

#define N 100
typedef int SLDataType;//int重命名为SLDataType，即顺序表数据类型
typedef struct SeqList
{
    SLDataType a[N];
    int size;
}SL;
void SeqListPushBack(SL* ps, int x);

动态顺序表：

//顺序表的动态存储
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType* array;       //把数组改成指针，意味着我们不再开辟一块固定大小的空间，而是指向一块空间
    int size;     //表示数组中存储了多少个数据
    int capacity;  //表示array指向的空间实际能够存数据的空间容量是多大
}SL;

接口函数：

//尾插
void SeqListPushBack(SL* ps, SeqDataType x);
//头插
void SeqListPushFront(SL* ps, SeqDataType x);
//头删
void SeqListPopFront(SL* ps);
//尾删
void SeqListPopBack(SL* ps);
//查找
int SeqListFind(SL* ps, SeqDataType x);
//修改
void SeqListModify(SL* ps, int pos, SeqDataType x);
//中间位置插入
void SeqListInsert(SL* ps, int pos, SeqDataType x);
//中间位置删除
void SeqListErase(SL* ps, int pos);
//初始化
void SeqListInit(SL *ps);
//销毁
void SeqListDestory(SL *ps);
//打印
void SeqListPrint(SL* ps);
//扩容
void SeqCheckCapacity(SL* ps);

注：这里接口函数取名是根据STL里的vector来取的，方便日后学习STL。

用处：

在通讯录中，我们输入了某个人的信息。那我们就可以调用所需要的接口函数，把这个信息插入到顺序表当中。顺便提一句，假如插入的信息数据类型是多样的，即结构体类型。那么我们就用 typedef 结构体名 Type;

接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开辟多了浪费，开辟少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

示例一：尾插

Seqlist.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
 
 
typedef int SeqDataType; //如果要修改则只需要修改这一处
 
typedef struct SeqList
{
    SeqDataType* a;
    int size;     //表示a中有多少个有效数据
    int capacity;  //表示a的空间到底有多大
}SL, SEQ;
 
//初始化
void SeqListInit(SL* ps);
//尾插
void SeqListPushBack(SL* ps, SeqDataType x);
//扩容
void SeqCheckCapacity(SeqList* ps);
//打印
void SeqListPrint(SL* ps);
//销毁
void SeqListDestory(SL* ps);

test.c：

 #include "SeqList.h"
 
//测试尾插
void TestSeqList1()
{
    SL s1;
    SeqListInit(&s1);//看解释2
 
    SeqListPushBack(&s1, 1);
    SeqListPushBack(&s1, 2);
    SeqListPushBack(&s1, 3);
    SeqListPushBack(&s1, 4);
    SeqListPushBack(&s1, 5);
    SeqListPrint(&s1); //1 2 3 4 5
    SeqListDestory(&s1);
 
}
 
int main()
{
    TestSeqList1();
    return 0;
}

SL.c

#include "SeqList.h"//
 
//对顺序表的初始化
void SeqListInit(SL *ps)//看解释1
{
    assert(ps);
 
    ps->a = NULL;
    ps->size = ps->capacity = 0;//看解释3
} 
//扩容
void SeqCheckCapacity(SL* ps)
{
    //如果没有空间或空间不足，则扩容
    if (ps->size == ps->capacity)//有两种情况：1.刚初始化，指针为空，size=capacity=0 2.size=capacity≠0
    {
        //int newcapacity = ps->capacity * 2; //这样会存在问题，当一开始插入数据时，capacity为0，乘2后还是为0
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //如果capacity等于0了,则开辟4个空间
        SeqDataType* newA = realloc(ps->a, sizeof(SeqDataType*) * newcapacity);//看解释8
        if (newA == NULL)//看解释9
        {
            printf("realloc fail\n");
            exit(-1);//看解释10
        }
 //程序能运行到这儿，说明realloc开辟空间成功
        ps->a = newA;//把刚开辟的空间给它
        ps->capacity = newcapacity;//把刚扩容的空间给它
 
    }
}
//尾插
void SeqListPushBack(SL* ps, SeqDataType x)
{
    assert(ps);
 
    //扩容函数，检查空间是否足够，如果满了则扩容，反之直接插入数据：
    SeqCheckCapacity(ps);//看解释6
    //插入数据：
    ps->a[ps->size] = x;//在有效个数后面放入要插入的数据x
    ps->size++;//插入一个数据后有效个数加1
 
}
//打印
void SeqListPrint(SL* ps)
{
    assert(ps);
    for (int i = 0; i < ps->size; ++i)
    {
        printf("%d ", ps->a[i]);
    }
}
//销毁
void SeqListDestory(SL* ps)
{
    free(ps->a);
    ps->a = NULL;//防止a成为野指针
    ps->capacity = ps->size = 0;
}

解释：

1️⃣如果void SeqListInit(SL *ps)初始化成功，则调用监视时，显示结果是这样的：

2️⃣ 对SeqListInit(&s1)，为何用&s1而不用s1?

s1是我们定义的一个结构体类型变量，如果用s1,那么对应的void SeqListInit(SL ps)中的ps,属于传值调用。然而函数调用后的形参ps不是实参s1,而是s1的临时拷贝，形参的改变无法影响实参。那我们后续搞的尾插，头插，头删...毫无意义

所以我们要改成传址调用，传址调用是形参通过实参传递的地址访问实参的空间，并在其空间进行修改

3️⃣为什么该项目中对结构体成员的访问都是用的->而不是.?

因为我们函数调用采用的是传址调用，所以要用->

4️⃣动态顺序表的尾插是怎么实现的？

下图举例，插入数据5

5️⃣动态顺序表尾插的三种情况：

• 整个顺序表都没有空间，处于刚初始化，空指针和无空间状态

• 空间不够，先扩容

• 空间足够，直接插入数据即可

6️⃣ 为什么会有SeqCheckCapacity(ps)？

因为接下来我们要在顺序表中插入数据，插入前就必须检查空间是否充足。如果充足，就数据就插入，否则要扩容再插入

7️⃣扩容时，我们不是扩一个插一个，效率低。而是一次扩现有容量空间的2倍

8️⃣这里用realloc的原因：

实际上，第一次进来的时候，指针变量为空指针、size=capacity=0。这时我们应该先开辟一块空间，再考虑之后的扩容。开辟空间，我们就需要用到malloc函数，而realloc是对已有空间扩容。但是，如果realloc指向的那块空间是空指针，那么realloc函数的功能等价于malloc函数，即开辟空间

9️⃣newA==NULL则表明上面的realloc分申请空间失败，返回NULL