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

1、线性表

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

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

2、顺序表

2.1、概念及结构

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

 顺序表一般可以分为：静态顺序表和动态顺序表两种。

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

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

2.2、接口实现

        静态顺序表只适用于确定知道需要存多少数据的场景。但是静态顺序表的定长数组可能导致空间开大或者开小了，空间开大了会造成浪费，空间开小了会不够用。因此现实中大多使用动态顺序表，动态顺序表可以根据需要来动态开辟和分配空间大小。以下是一个实现动态顺序表的例子。

SeqList.h

#pragma once// SeqList.h#include #include #include typedef int SLDateType;typedef struct SeqList{SLDateType* a;int size;int capacity;}SeqList;// 对数据的管理:增删查改 void SeqListInit(SeqList* ps);void SeqListDestroy(SeqList* ps);void SeqListPrint(SeqList* ps);void SeqListPushBack(SeqList* ps, SLDateType x);void SeqListPushFront(SeqList* ps, SLDateType x);void SeqListPopFront(SeqList* ps);void SeqListPopBack(SeqList* ps);// 顺序表查找int SeqListFind(SeqList* ps, SLDateType x);// 顺序表在pos位置插入xvoid SeqListInsert(SeqList* ps, int pos, SLDateType x);// 顺序表删除pos位置的值void SeqListErase(SeqList* ps, int pos);

  SeqList.c  

#define _CRT_SECURE_NO_WARNINGS#include "SeqList.h"//初始化void SeqListInit(SeqList* ps) {ps->a = (SeqList*)malloc(sizeof(SeqList)*4);if (ps->a == NULL){perror("malloc failed");return;}ps->size = 0;ps->capacity = 4;}//清空数据void SeqListDestroy(SeqList* ps) {ps->size = 0;ps->capacity = 0;free(ps->a);ps->a = NULL;}//打印数据void SeqListPrint(SeqList* ps) {for (int i = 0; i size; i++) {printf("%d ", ps->a[i]);}printf("\n");}//// 检查是数据是否已经满void SLCheckCapacity(SeqList* ps) {if (ps->size == ps->capacity) {SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * (ps->capacity + 2));if(tmp==NULL){perror("realloc:");return;}ps->a = tmp;ps->capacity = ps->capacity + 2;}}//尾插void SeqListPushBack(SeqList* ps, SLDateType x) {SLCheckCapacity(ps);ps->a[ps->size] = x;ps->size++;}//头插void SeqListPushFront(SeqList* ps, SLDateType x) {SLCheckCapacity(ps);int end = ps->size - 1;while (end >= 0){ps->a[end+1] = ps->a[end];end--;}ps->a[0] = x;ps->size++;}//头删void SeqListPopFront(SeqList* ps) {assert(ps->size > 0);int begain = 0;while (begain size) {ps->a[begain] = ps->a[begain + 1];begain++;}ps->size--;}//尾删void SeqListPopBack(SeqList* ps) {assert(ps->size > 0);ps->size--;}// 顺序表查找int SeqListFind(SeqList* ps, SLDateType x) {assert(ps);for (int i = 0; i size; i++) {if (ps->a[i] == x) {return i;}}return -1;}// 顺序表在pos位置插入xvoid SeqListInsert(SeqList* ps, int pos, SLDateType x) {assert(ps);SLCheckCapacity(ps);assert(ps->size > pos && pos >= 0);int end = ps->size - 1;while (end >= pos) {ps->a[end + 1] = ps->a[end];end--;}ps->a[pos] = x;ps->size++;}// 顺序表删除pos位置的值void SeqListErase(SeqList* ps, int pos) {assert(ps);assert(pos >= 0 && pos size);int begain = pos;while (begain size) {ps->a[begain] = ps->a[begain + 1];begain++;}ps->size--;}

2.3、顺序表存在的一些问题

1.  在顺序表中间或者头部进行插入和删除操作，时间复杂度为O(N)
2. 增容需要申请新的空间，拷贝数据，释放就空间，会有不小的消耗
3. 增容一般是呈二倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再插入2个数据，后边无数据插入，这样也会导致浪费很多空间。

3、链表

3.1、链表的概念和结构

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

• 如图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
• 现实中结点一般是从堆中申请出来的
• 从堆上申请的空间是按照一定的策略来分配的，两次申请的空间可能连续也可能不连续。
• 其中data中存储的为本节点中存储的数据
• next中存储的为下一个节点的地址

  3.2、链表的分类

  在实际中链表的结构非常多样，以下情况组合起来就有八种链表结构：

  1、单向或者双向

         

  2、带头或者不带头

  3、循环或者非循环

  4、无头单向非循环链表或者带头双向循环链表

  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际上更多是作为其他数据结构的子结构，如哈希桶，图的邻接表等。
  • 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。这个结构虽然结构复杂，但是代码实现后会发现结构会带来许多优势，实现反而会简单。

    3.3、链表的实现

    1、单链表：

            slist.h

    #pragma once// slist.h#include#include#includetypedef int SLTDateType;typedef struct SListNode{SLTDateType data;struct SListNode* next;}SListNode;// 动态申请一个节点SListNode* BuySListNode(SLTDateType x);// 单链表打印void SListPrint(SListNode* plist);// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x);// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x);// 单链表的尾删void SListPopBack(SListNode** pplist);// 单链表头删void SListPopFront(SListNode** pplist);// 单链表查找SListNode* SListFind(SListNode* plist, SLTDateType x);// 单链表在pos位置之后插入x// 分析思考为什么不在pos位置之前插入？void SListInsertAfter(SListNode* pos, SLTDateType x);// 单链表删除pos位置之后的值// 分析思考为什么不删除pos位置？void SListEraseAfter(SListNode* pos);// 在pos的前面插入void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x);// 删除pos位置void SLTErase(SListNode** pphead, SListNode* pos);void SLTDestroy(SListNode** pphead);

            slist.c

    #define _CRT_SECURE_NO_WARNINGS#include "slist.h"//动态申请节点SListNode* BuySListNode(SLTDateType x) {SListNode* datanode = (SListNode*)malloc(sizeof(SListNode));if (datanode == NULL) {perror("malloc");return NULL;}else {datanode->data = x;datanode->next = NULL;}return datanode;}//单链表打印void SListPrint(SListNode* plist) {assert(plist);SListNode* cur = plist;while (cur != NULL) {printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");}// 单链表尾插void SListPushBack(SListNode** pplist, SLTDateType x) {SListNode* newnode = BuySListNode(x);if (*pplist ==NULL) {*pplist = newnode;}else {SListNode* tail = *pplist;while (tail->next != NULL) {tail = tail->next;}tail->next = newnode;}}// 单链表的头插void SListPushFront(SListNode** pplist, SLTDateType x) {SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;}// 单链表的尾删void SListPopBack(SListNode** pplist) {assert(*pplist);if ((*pplist)->next == NULL) {free(*pplist);*pplist = NULL;}else {SListNode* tail = *pplist;while (tail->next->next != NULL) {tail = tail->next;}free(tail->next);tail->next = NULL;}}// 单链表头删void SListPopFront(SListNode** pplist) {assert(*pplist);SListNode* del = *pplist;*pplist = (*pplist)->next;free(del);del = NULL;}// 单链表查找SListNode* SListFind(SListNode* plist, SLTDateType x) {assert(plist);SListNode* cur = plist;while (cur != NULL) {if (cur->data == x) {return cur;}cur = cur->next;}return NULL;}// 单链表在pos位置之后插入xvoid SListInsertAfter(SListNode* pos, SLTDateType x) {assert(pos); SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;}// 单链表删除pos位置之后的值void SListEraseAfter(SListNode* pos) {assert(pos);assert(pos->next);SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;}// 在pos的前面插入void SLTInsert(SListNode** pphead, SListNode* pos, SLTDateType x) {assert(*pphead);assert(pos);if (*pphead == pos) {SListPushFront(pphead, x);}else {SListNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}SListNode* newnode = BuySListNode(x);prev->next = newnode;newnode->next = pos;}}// 删除pos位置void SLTErase(SListNode** pphead, SListNode* pos) {assert(*pphead);assert(pos);if (*pphead == pos) {SListPopFront(pphead);}else {SListNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}}void SLTDestroy(SListNode** pphead) {assert(*pphead);SListNode* del=NULL;while ((*pphead)->next) {del = (*pphead)->next;*pphead = (*pphead)->next;free(del);del = NULL;}}

    2、双链表

            DoubleLinkList.h

    #pragma once#include#include#include#include// 带头+双向+循环链表增删查改实现typedef int LTDataType;typedef struct ListNode{LTDataType data;struct ListNode* next;struct ListNode* prev;}ListNode;// 创建返回链表的头结点.ListNode* ListCreate();// 双向链表销毁void ListDestory(ListNode* pHead);// 双向链表打印void ListPrint(ListNode* pHead);// 双向链表尾插void ListPushBack(ListNode* pHead, LTDataType x);// 双向链表尾删void ListPopBack(ListNode* pHead);// 双向链表头插void ListPushFront(ListNode* pHead, LTDataType x);// 双向链表头删void ListPopFront(ListNode* pHead);// 双向链表查找ListNode* ListFind(ListNode* pHead, LTDataType x);// 双向链表在pos的前面进行插入void ListInsert(ListNode* pos, LTDataType x);// 双向链表删除pos位置的节点void ListErase(ListNode* pos);

            DoubleLinkL.c

    #define _CRT_SECURE_NO_WARNINGS#include"DoubleLinkList.h"//创建新结点ListNode* BuyList(LTDataType x) {ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL) {perror("BuyList");return NULL;}newnode->data = x;newnode->prev = NULL;newnode->next = NULL;return newnode;}// 创建返回链表的头结点.ListNode* ListCreate() {ListNode* phead = BuyList(-1);phead->prev = phead;phead->next = phead;return phead;}// 双向链表销毁void ListDestory(ListNode* pHead) {ListNode* tail = pHead->next;while (tail != pHead) {ListNode* next = tail->next;free(tail);tail = next;}}// 双向链表打印void ListPrint(ListNode* pHead) {assert(pHead);printf("guard");ListNode* tail = pHead->next;while (tail != pHead) {printf("%d", tail->data);tail = tail->next;}printf("\n");}// 双向链表尾插void ListPushBack(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* newnode = BuyList(x);ListNode* cur = pHead->prev;cur->next = newnode;newnode->prev = cur;newnode->next = pHead;pHead->prev = newnode;}bool LTEmpty(ListNode* phead){assert(phead);return phead->next == phead;}// 双向链表尾删void ListPopBack(ListNode* pHead) {assert(pHead);assert(!LTEmpty(pHead));ListNode* del = pHead->prev;ListNode* tail = del->prev;tail->next = pHead;pHead->prev = tail;free(del);del = NULL;}// 双向链表头插void ListPushFront(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* newnode = BuyList(x);ListNode* tail = pHead->next;pHead->next = newnode;newnode->prev = pHead;newnode->next = tail;tail->prev = newnode;}// 双向链表头删void ListPopFront(ListNode* pHead) {assert(pHead);assert(!LTEmpty(pHead));ListNode* del = pHead->next;ListNode* tail = del->next;free(del);del = NULL;pHead->next = tail;tail->prev= pHead;}// 双向链表查找ListNode* ListFind(ListNode* pHead, LTDataType x) {assert(pHead);ListNode* tail = pHead->next;while (tail != pHead) {if (tail->data == x) {return tail;}else {tail = tail->next;}}return NULL;}// 双向链表在pos的前面进行插入void ListInsert(ListNode* pos, LTDataType x) {assert(pos);ListNode* newnode=BuyList(x);ListNode* tail = pos->prev;tail->next = newnode;newnode->prev = tail;newnode->next = pos;pos->prev = newnode;}// 双向链表删除pos位置的节点void ListErase(ListNode* pos) {assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;free(pos);pos = NULL;prev->next = next;next->prev = prev;}

    4.顺序表和链表的区别

    顺序表和链表的区别

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