顺序表和链表

在了解顺序表和链表之前，先来了解一下线性表，因为顺序表和链表都是一种线性表。

1.线性表

线性表是N个具有相同特性的数据元素的有限序列。

线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列和字符串。

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

2.顺序表

2.1概念及结构

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

注意：顺序表中的数据是从第一个位置开始，连续存储的。这和数组是不同的，数组中的数据可以在任意位置存放。

2.2顺序表的分类

1.静态顺序表（定长数组存储元素）

#define N 7
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType a[N];
    int size;
}SeqList;

** 2.动态开辟的数组（使用动态开辟的数组存储数据）**

typedef struct SeqList
{
    SLDataType* a;//动态开辟的数组
    int size;//数组中的数据个数
    int capacity;//数组的容量
}SeqList;

2.3接口的实现

静态顺序表只适用于知道需要存储多少数据的场景。静态顺序表的定长数组空间开大了容易造成浪费，开少了不够用。

所以在现实中实现顺序表的时候使用的基本上都是动态的顺序表，根据需要的内存动态分配空间，所以在实现接口的时候我们使用的是动态顺序表。

2.3.1顺序表初始化

void SeqListInit(SeqList* SL)
{
    assert(SL);
    SL->a = NULL;//数组先初始化为空，后面用动态内存开辟函数开辟空间
    SL->capacity = SL->size = 0;//容量和元素数量都初始化为0
}

2.3.2检查是否需要扩容

void CheckCapacity(SeqList* SL)
{
    assert(SL);
    //需要扩容的两种情况
    //1.size和capacity都为0
    //2.size == capacity 两种情况都可以用SL->size == SL->capacity来表示
    if (SL->capacity == SL->size)
    {
        //如果capacity为0 扩容为4个数据的空间  如果数组已满扩容为原来的二倍
        int newcapacity = SL->capacity == 0 ? 4 : SL->capacity * 2;
        //先开辟一片临时的空间，开辟成功之后再把地址赋给a
        SLDataType* tmp = (SLDataType*)realloc(SL->a, sizeof(SLDataType) * newcapacity);
        if (tmp == NULL)
        {
            printf("realloc fail\n");
            exit(-1);//退出程序
        }
        SL->a = tmp;
        SL->capacity = newcapacity;
    }
}

2.3.3顺序表的尾插

void SeqListPushBack(SeqList* SL, SLDataType x)
{
    assert(SL);
    CheckCapacity(SL);
    SL->a[SL->size] = x;
    SL->size++;
}

2.3.4顺序表的尾删

//温柔的检查版本
void SeqListPopBack(SeqList* SL)
{
    assert(SL);
    if (SL->size == 0)//顺序表中没有数据直接返回
        return;
    SL->size--;
}

//暴力的检查
void SeqListPopBack(SeqList* SL)
{
    assert(SL);
    assert(SL->size);//如果SL->size == 0 直接提示
    SL->size--;
}

2.3.5顺序表的头插

void SeqListPushFront(SeqList* SL, SLDataType x)
{
    assert(SL);
    CheckCapacity(SL);
    //进行头插时需要挪动数据
    int end = SL->size - 1;
    for (int i = end; i > 0; i--)
    {
        SL->a[end] = SL->a[end - 1];
    }//除了使用for循环之外，还可以使用while循环，
    //无论使用for循环还是while循环，都需要注意边界
    SL->a[SL->size] = x;
    SL->size++;
}

2.3.6顺序表的头删

void SeqListPopFront(SeqList* SL)
{
    assert(SL);
    assert(SL->size);
    int begin = 1;
    while (begin <= SL->size - 1)
    {
        SL->a[begin - 1] = SL->a[begin];
        begin++;
    }
    SL->size--;
}

2.3.7顺序表查找

//顺序表查找，返回下标
int SeqListFind(SeqList* SL, SLDataType x)
{
    assert(SL);
    for (int i = 0; i < SL->size; i++)
    {
        if (SL->a[i] == x)
            return i;
    }
    return -1;//没找到
}

2.3.8顺序表在pos位置插入x

void SeqListInsert(SeqList* SL, int pos, SLDataType x)
{
    assert(SL);
    assert(pos >= 0);
    assert(pos <= SL->size);//尾插时为==
    Checkcapacity(SL);
    //挪动数据
    int end = SL->size - 1;
    for (int i = end; i >= pos; i--)
    {
        SL->a[end + 1] = SL->a[end];
    }
    SL->a[pos] = x;
    SL->size++;
}

2.3.9顺序表删除pos位置的值

void SeqListErases(SeqList* SL, int pos)
{
    assert(SL);
    assert(pos >= 0 && pos <= SL->size);
    int begin = pos + 1;
    while (begin <= SL->size - 1)
    {
        SL->a[begin - 1] = SL->a[begin];
        begin++;
    }
    SL->size--;
}

2.3.10顺序表销毁

void SeqListDestory(SeqList* SL)
{
    assert(SL);
    if (SL->a)
    {
        free(SL->a);
        SL->a = NULL;
        SL->capacity = SL->size = 0;
    }
}

2.3.11顺序表打印

void SeqListPrint(SeqList* SL)
{
    assert(SL);
    assert(SL->size);
    //直接进行遍历就行
    for (int i = 0; i < SL->size; i++)
    {
        printf("%d ", SL->a[SL->size]);
    }
    printf("\n");
}

2.4顺序表的问题及思考

问题：

• 中间/头部的插入和删除，需要挪动数据，时间复杂度为O(N)
• 增容需要重新申请空间，拷贝数据，释放旧的空间。会有不小的损耗
• 增容一般呈现二倍增长，势必会有一定的空间浪费

例如当容量为100时，满了之后扩容为200，但是我们只需要再插入5个数据，后面就没有数据插入了，就浪费了95个数据空间。

思考：

如何解决以上的问题？

改善方案：1.按需申请空间 2.头部或者中间的插入删除，不需要挪动数据

下面我们就来看看链表的结构。

3.链表

3.1链表的概念及结构

概念：链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。

先大致了解一下链表：

** 注意：**

• 链式结构在逻辑上是连续的，但是在物理上不一定是连续的
• 现实中的结点一般都是从堆上申请出来的
• 从堆上申请空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

3.2常见的两种链表结构

1.无头单向非循环链表

结构简单，一般不会单独用来存数据。实际中更多的是作为其他数据结构的子结构，如哈系统、图的邻接表等。

**2.带头双向循环链表 **

结构最为复杂，一般用在单独存放数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构有很多的优势，并且实现也很简单。

3.3无头单向非循环链表的实现

typedef int SLDataType;
typedef struct SListNode
{
    SLDataType data;
    struct SLListNode* next;
}SListNode;

3.3.1动态申请一个节点

SListNode* BuySListNode(SLDataType x)
{
    SLDataType* tmp = (SLDataType*)malloc(sizeof(SListNode));
    if (tmp == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    //也可以使用assert(tmp)
    SListNode* newnode = tmp;
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}

3.3.2单链表打印

void SListPrint(SListNode* plist)
{
    assert(plist);
    SListNode* cur = plist;
    while (cur->next != NULL)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

3.3.3单链表尾插

void SListPushBack(SListNode** pplist, SLDataType x)
{
    assert(pplist);
    SListNode* newnode = BuySListNode(x);
    if (*pplist == NULL)
    {
        *pplist = newnode;
    }
    else
    {
        SListNode* cur = *pplist;
        while (cur->next != NULL)
        {
            cur = cur->next;
        }
        cur->next = newnode;
    }
}

3.3.4单链表头插

void SListPushFront(SListNode** pplist, SLDataType x)
{
    assert(pplist);
    SListNode* newnode = BuySListNode(x);
    newnode->next = *pplist;
    *pplist = newnode;
}

3.3.5单链表尾删

void SListPopBack(SListNode** pplist)
{
    assert(pplist);
    assert(*pplist);
    //单个节点
    if ((*pplist)->next == NULL)
    {
        free(*pplist);
        *pplist = NULL;
    }
    //多个节点
    else
    {
        SListNode* cur = *pplist;
        while (cur->next->next)
        {
            cur = cur->next;
        }
        free(cur->next);
        cur->next = NULL;
    }
}

3.3.6单链表头删

void SListPopFront(SListNode** pplist)
{
    assert(pplist);
    assert(*pplist);
    SListNode* next = (*pplist)->next;
    free(*pplist);
    *pplist = next;
}

3.3.7单链表查找

SListNode* SListFind(SListNode* plist, SLDataType x)
{
    assert(plist);
    SListNode* cur = plist;
    while (cur)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

3.3.8单链表在pos位置之后插入x

void SListInsertAfter(SListNode* pos, SLDataType x)
{
    assert(pos);
    SListNode* newnode = BuySListNode(x);
    SListNode* next = pos->next;
    pos->next = newnode;
    newnode->next = next;
}

3.3.9单链表删除pos位置之后的节点

void SListEraseAfter(SListNode* pos)
{
    assert(pos);
    //pos后面没有节点
    if (pos->next == NULL)
        return;
    SListNode* next = pos->next->next;
    free(pos->next);
    pos->next = next;
}

3.4双向带头循环链表的实现

typedef int LTDataType;
typedef struct ListNode
{
    LTDataType data;
    struct ListNode* next;
    struct ListNode* prev;
}ListNode;

3.4.1创建返回链表的头节点

ListNode* ListCreate()
{
    ListNode* head = BuyListNode(-1);
    head->next = head;
    head->prev = head;
    return head;
}

3.4.2双向链表销毁

void ListDestory(ListNode* plist)
{
    ListNode* cur = plist->next;
    while (cur != plist)
    {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
}

3.4.3双向链表的打印

void ListPrint(ListNode* plist)
{
    assert(plist);
    ListNode* cur = plist->next;
    while (cur != plist)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

3.4.4双向链表尾插

void ListPushBack(ListNode* plist, LTDataType x)
{
    assert(plist);
    ListNode* newnode = BuyListNode(x);
    ListNode* tail = plist->prev;
    plist->prev = newnode;
    newnode->prev = tail;
    tail->next = newnode;
    newnode->next = plist;
}

3.4.5双向链表尾删

void ListPopBack(ListNode* plist)
{
    assert(plist);
    assert(plist->next != plist);
    ListNode* tail = plist->prev->prev;
    free(plist->prev);
    plist->prev = tail;
    tail->next = plist;
}

3.4.6双向链表头插

void ListPushFront(ListNode* plist, LTDataType x)
{
    assert(plist);
    ListNode* newnode = BuyListNode(x);
    ListNode* next = plist->next;
    plist->next = newnode;
    newnode->prev = plist;
    newnode->next = next;
}

3.4.7双向链表的头删

void ListPopFront(ListNode* plist)
{
    assert(plist);
    assert(plist->next != plist);
    ListNode* next = plist->next->next;
    free(plist->next);
    plist->next = next;
    next->prev = plist;
}

3.4.8双向链表查找

ListNode* ListFind(ListNode* plist, LTDataType x)
{
    assert(plist);
    ListNode* cur = plist->next;
    while (cur != plist)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}

3.4.9双向链表在pos前面进行插入

void ListInsert(ListNode* pos, LTDataType x)
{
    assert(pos);
    ListNode* newnode = BuyListNode(x);
    ListNode* prev = pos->prev;
    pos->prev = newnode;
    newnode->next = pos;
    prev->next = newnode;
    newnode->prev = prev;
}

3.4.10双向链表删除pos位置的节点

void ListErase(ListNode* pos)
{
    assert(pos);
    ListNode* next = pos->next;
    ListNode* prev = pos->prev;
    free(pos);
    prev->next = next;
    next->prev = prev;
}

顺序表和链表的内容到这里就结束了，喜欢的铁子们记得给个点赞，收藏+关注哦。