【数据结构】顺序表与链表

1、线性表

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

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

线性表：

2、顺序表

**2.1概念及结构 **

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

顺序表一般可以分为：

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

#defint N 7
typedef int SLDataType;
typedef struct SeqList
{
    SLDataType array[N];//定长数组
    size_t size;        //有效数据个数
}SeqList;

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

typedef struct SeqList
{
    SLDataType* array;//指向动态开辟的数组
    size_t size;      //有效数据个数
    size_t capacity;  //容量空间大小
}SeqList;

3、链表

**3.1 ****链表的概念及结构 **

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

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

**3.2 **链表的分类

1. 单向或者双向

2. **带头或者不带头 **

3. **循环或者非循环 **

一共有八种链表结构，****虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了.

下面是对单链表的实现。

//无头，单项，非循环链表
typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next; 
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x)
{
    SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
    newnode->data = x;
    newnode->next = NULL;
    return newnode;
}
// 单链表打印
void SListPrint(SListNode* plist)
{
    while (plist)
    {
        printf("%d ", plist->data);
        plist = plist->next;
    }
}
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
    SListNode* head = *pplist;
    SListNode* newnode= BuySListNode(x);
    if (!( *pplist))
    {
        (*pplist) = newnode;
    }
    else
    {
        while ((*pplist)->next)
        {
            *pplist = (*pplist)->next;
        }
        (*pplist)->next = newnode;
    }
    *pplist = head;
}
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
    SListNode* newnode = BuySListNode(x);
    if (!(*pplist))
    {
        (*pplist) = newnode;
    }
    else
    {
        SListNode* head = newnode;
        newnode->next = (*pplist);
        (*pplist) = head;
    }
}
// 单链表的尾删
void SListPopBack(SListNode** pplist)
{
    SListNode* head = *pplist;
    assert(*pplist);
    while ((*pplist)->next->next)
    {
        *pplist = (*pplist)->next;
    }
    free((*pplist)->next);
    (*pplist)->next = NULL;
    (*pplist) = head;
}
// 单链表头删
void SListPopFront(SListNode** pplist)
{
    SListNode* head = (*pplist)->next;
    free((*pplist));
    (*pplist) = NULL;
    (*pplist) = head;
}

4、顺序表和链表的区别

不同点顺序表链表存储空间上物理上一定连续逻辑上连续，但物理上不一定连续随机访问支持O（1）不支持O（N）任意位置插入或删除可能需要搬移元素，效率低只需要修改指针指向插入动态顺序表，空间不够需要扩容没有容量的概念应用场景元素高校存储+频繁访问任意位置插入和删除频繁缓存利用率高低
**最后是双向带头链表增删查改的实现 **

ListNode* ListCreate(ListNode* plist)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->data = -1;
    newnode->next = newnode->prev = NULL;
    return newnode;
}
// 双向链表销毁
void ListDestory(ListNode* plist)
{
    while (plist)
    {
        ListNode* next = plist->next;
        plist->data=0;
        free(plist);
        plist = NULL;
        plist = next;
    }    
}
// 双向链表打印
void ListPrint(ListNode* plist)
{
    ListNode* next = plist->next;
    while (next != plist)
    {
        printf("%d ", next->data);
        next = next->next;
    }
    printf("\n");
}
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->next = plist;
    newnode->prev = plist->prev;
    plist->prev->next = newnode;
    plist->prev = newnode;
}
// 双向链表尾删
void ListPopBack(ListNode* plist)
{
    ListNode* tail = plist->prev;
    plist->prev = tail->prev;
    tail->prev->next = plist;
    free(tail);
}
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->next = plist->next;
    newnode->prev = plist;
    plist->next->prev = newnode;
    plist->next = newnode;
}
// 双向链表头删
void ListPopFront(ListNode* plist)
{
    ListNode* head = plist->next;
    plist->next = head->next;
    head->next->prev = plist;
    free(head);
}