目录：
链表是个优秀的结构，没有容量概念，可以在任意位置增加删除数据，这个博客，我准备花大量篇幅去总结链表（特别是单链表），同时也总结一下顺序表（顺序表和我们以前写的通讯录动态版类似，一般采用数组存储的方法，在数组上完成数据的增删查改）
一、线性表的概念
线性表的定义：由n个数据元素组成具有相同特性的有限序列。
常见的线性表：顺序表、链表、栈、队列、字符串等等。
线性表的概念：线性表在逻辑上是线性结构，也就是说它是一条直线，它的物理结构并不一定是连续的，线性表在物理上存储时，通常以数组和链表的形式存储。
二、顺序表
顺序表的定义：
顺序表是一段物理地址连续的存储单元，是一种用来依次存储数据的线性结构
1.静态顺序表：使用定常数组存储元素
#define N 7//方便改变数组大小 typedef int SLDatatype; typedef struct SLD { SLDatatype arr[N];//定长数组 size_t size;//有效数据的个数 }SeqList;//顺序表
2.动态顺序表：使用动态开辟的数组存储元素（空间不够就可以扩容）
typedef int SLDatatype; typedef struct SLD { SLDatatype* p;//指向动态开辟的数组 size_t size;//有效数据的个数 size_t capicity;//表示容量空间的大小 }SeqList;//顺序表
三、链表
3.1 链表的概念
链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
注意:
链式结构在逻辑上是连续的，但是在物理上不一定连续。
现实中的节点一般都是从堆上申请出来的
从堆上申请的空间是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。
3.2 链表的分类
链表的结构非常多，结合起来有8种：
1、单向或者双向
2、带头或者不带头
3、循环或者不循环
实际中常用的两种结构是：
无头单向非循环链表 ：
结构简单，一般不会单独存数据。其他数据的子结构，如哈希桶、图的领接表等等。
带头双向循环链表：
结构最复杂，一般可以单独存数据。实际中使用的链表数据结构，都是带头双向循环链表。
3.3 无头+单向+非循环链表的实现
头文件里的函数声明
// slist.h typedef 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 void SListInsertAfter(SListNode* pos, SLTDateType x); // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos); // 单链表的销毁 void SListDestroy(SListNode** pplist);
下面将是各个函数的实现
// slist.c #include "SList.h" //动态申请一个结点 SListNode* BuySListNode(SLTDateType x) { //在堆上开辟一个存放指针的变量，并给它初始化 SListNode* node = (SListNode*)malloc(sizeof(SListNode)); node->data = x; node->next = NULL; return node;//返回指针 } //单链表打印 void SListPrint(SListNode* plist) { //定义一个指针，指针指向头指针 SListNode* cur = plist; //遍历指针，不是空就循环 while (cur) { printf("%d->", cur->data); cur = cur->next; } //cur指向空 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 SListPopBack(SListNode** pplist) { //定义两个指针 SListNode* prev = NULL;//当前位置的指针 SListNode* tail = *pplist;//尾结点的指针 // 1.空、只有一个节点 // 2.两个及以上的节点 if (tail == NULL || tail->next == NULL) { //给空间释放 free(tail); *pplist = NULL; } else { //遍历链表，找到尾指针 while (tail->next) { prev = tail; tail = tail->next; } free(tail); tail = NULL; //让最后一个结点指向空 prev->next = NULL; } } //单链表头插法 void SListPushFront(SListNode** pplist, SLTDateType x) { //这个指针是空就报错 assert(pplist); // 1.空 // 2.非空 SListNode* newnode = BuySListNode(x); if (*pplist == NULL)//pplist指针指向的是空 { *pplist = newnode; } else { //在*pplist指针指向的那个结点前面头插一个结点 newnode->next = *pplist; //*pplist指针重新指向头结点 *pplist = newnode; } } //单链表头删 void SListPopFront(SListNode** pplist) { // 1.空 // 2.一个 // 3.两个及以上 SListNode* first = *pplist;//定义一个头指针，它为空就返回， if (first == NULL) { return; } else if (first->next == NULL)//只有一个结点，就释放空间，然后置空 { free(first); *pplist = NULL; } else { //两个以上结点 SListNode* next = first->next;//把头指针的下一个结点位置存起来 free(first);//释放头指针 *pplist = next;//让首指针重新指向头指针 } } 单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x) { SListNode* cur = plist; while (cur) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } // 单链表在pos位置之后插入x void SListInsertAfter(SListNode* pos, SLTDateType x)//用单链表查找，找到值x的位置，返回的指针给pos { assert(pos); SListNode* next = pos->next;//next指针存放pos之后的节点 SListNode* newnode = BuySListNode(x);//开辟一个新结点 pos->next = newnode;//在pos后面插入新开辟的结点 newnode->next = next;//让新结点连接上next指向的那个结点 } // 单链表删除pos位置之后的值 void SListEraseAfter(SListNode* pos)//用单链表查找，找到值x的位置，返回的指针给pos { assert(pos); // pos next nextnext SListNode* next = pos->next; if (next != NULL) { SListNode* nextnext = next->next; free(next); pos->next = nextnext; } } // 单链表的销毁 void SListDestroy(SListNode** pplist) { SListNode* cur = *pplist; while (cur) { *pplist = cur->next; free(cur); cur = *pplist; } }
3.4 带头+双向+循环链表的实现
头文件里的函数声明
#define _CRT_SECURE_NO_WARNINGS 1 #pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> // 带头+双向+循环链表增删查改实现 typedef int LTDataType; typedef struct ListNode { LTDataType data; struct ListNode* next; struct ListNode* prev; }ListNode; //创建新结点 ListNode* ListNodes(LTDataType x); //双向链表初始化 ListNode* ListInit(); // 双向链表销毁 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); //求链表有多少数据 int listsize(ListNode* phead); // 双向链表查找 ListNode* ListFind(ListNode* phead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos);
函数的定义实现
// 创建新节点 ListNode* ListNodes(LTDataType x) { ListNode* head = (ListNode*)malloc(sizeof(ListNode)); if (head == NULL) { perror("malloc fail"); exit(-1); } head->data = x; head->next = NULL; head->prev = NULL; return head; } //链表初始化 ListNode* ListInit() { ListNode* phead = ListNodes(-1); phead->next = phead; phead->prev = phead; return phead; } // 双向链表尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* newnode = ListNodes(x);//创建一个新节点 ListNode* tail = phead->prev; newnode->data = x; //双向链表尾插 tail->next = newnode; newnode->next = phead; newnode->prev = tail; phead->prev = newnode; } // 双向链表尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != NULL); ListNode* tail = phead->prev; ListNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; } // 双向链表头插 void ListPushFront(ListNode* phead, LTDataType x) { ListNode* next = phead->next; ListNode* newnode = ListNodes(x); phead->next = newnode; newnode->prev = phead; newnode->next = next; next->prev = newnode; } // 双向链表头删 void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != NULL); ListNode* node = phead->next; phead->next = node->next; node->next->prev = phead; free(node); } //求链表有多少数据 int listsize(ListNode* phead) { int size = 0; assert(phead); ListNode* cur = phead->next; while (cur != phead) { size++; cur = cur->next; } return size; } // 双向链表查找 ListNode* ListFind(ListNode* phead, LTDataType x) { ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x) { ListNode* newnode = ListNodes(x); ListNode* prevnode = pos->prev; prevnode->next = newnode; newnode->prev = prevnode; newnode->next = pos; pos->prev = newnode; } // 双向链表删除pos位置的节点 void ListErase(ListNode* pos) { assert(pos); ListNode* nodeprev = pos->prev; ListNode* nodenext = pos->next; free(pos); nodeprev->next = nodenext; nodenext->prev = nodeprev; } // 双向链表打印 void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { printf("%d<=>", cur->data); cur = cur->next; } } // 双向链表销毁 void ListDestory(ListNode* phead) { //断言指针指针不为NULL assert(phead); ListNode* cur = phead;//定义一个指针 //断开循环链表 phead->prev->next = NULL; while (cur) { ListNode* Next = cur->next; free(cur); cur = Next; } }
四、顺序表和链表的区别和联系
补充： 高速缓存利用率
先要对存储器的层次结构有一定了解
如图：
数据是存在内存中的，CPU要访问数据，它不会去内存直接访问数据。看数据在不在缓存，在缓存，数据就命中（cpu访问数据时，数据恰好在缓存里），不在缓存，访问不命中（cpu访问数据，不会把4个字节加载到缓存，它会把一长段的数据加载到缓存）
注意：CPU访问数据第一次不命中，第二次一定命中
