目录

一、线性表介绍

     1、线性结构

    2、线性表

二、线性表的顺序的表示和存储

        注意

        优点

        缺点

三、线性表的链式表示和存储

    单向链表

        1、不带头节点的单向链表

        2、带头节点的单向链表

        3、单向链表的使用

            1、单链表逆序，要在原基础上进行逆序

            2、找到链表的倒数第n个节点

            3、判断链表中是否存在环

            4、找出环形链表的入口节点

            5、合并两个有序链表，合并后保持有序性

            6、判断两个链表是否构成Y型链表，如果是，找出第一个公共节点

四、静态链表

五、循环链表

六、双向链表（双向循环链表）

七、Linux内核链表

    函数

八、通用链表

---

一、线性表介绍

     1、线性结构

        在数据元素存在非空有限集中：

            存在唯一的一个被称为“第一个”的数据元素

            存在唯一的一个被称为“最后一个”的数据元素

            除了第一个外，集合中每个数据元素都只有一个前趋元素

            除了最后一个外，集合中每个数据元素都只有一个后继元素

    2、线性表

        线性表是一个有n个数据元素的有限序列，同一个线性表中的元素必定有相同特性，元素之间存在序偶关系

        线性表中的元素个数n(n>=0)定义为该表的长度，当n==0时称为空表，非空表中每个数据元素都有一个确定的位置(下标)

        线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短

二、线性表的顺序的表示和存储

        线性表的存储使用一组连续内存来依次存储线性表中的数据元素。

        注意

            1、要时刻保持元素之间的连续性

            2、千万不要越界

        优点

            1、支持随机访问 

            2、查找、修改、排序效率比较高

            3、大块的连续内存不容易产生内存碎片

        缺点

            1、对元素插入、删除时效率很低

            2、大块内存对内存要求较高

三、线性表的链式表示和存储

        链式存储结构不要求内存位置物理上是连续的，因此元素可以存储在内存的任何位置（可以是连续的，也可以不连续）

        元素a[i]和a[i+1]之间的逻辑关系不是依靠相互位置，而是在元素中增加一个一个指向其后继元素的数据项(元素指针)，从而表示相互之间的逻辑关系，元素本身的数据+后继元素的地址 组成了存储映像，俗称 **节点**(node)

typedef struct Node
{TYPE data;          //  数据域  struct Node* next;  //  指针域
}Node;

        若干个节点通过指针域依次连接起来，形成的线性表结构称为链式表，简称链表，如果指针域中只有一个指向下一个节点的指针，这种链表称为单向链表。

    单向链表

        单向链表中必须要有一个指向第一个节点的指针，该指针称为头指针，被它指向的节点称为“头节点”，头节点可以存储、也可以不存储有效数据，如果不存储有效数据的话，那么头节点只是单纯地作为一个占位节点存在

        最后一个节点称为“尾节点”，尾节点的next指向空（NULL），作为结束标志

        1、不带头节点的单向链表

            定义：第一个节点中的数据域存储有效数据。

            注意：当需要对单链表的头指针发生修改时，例如头添加、头删除、插入等操作，参数需要传递头指针的地址(二级指针)，当进行删除时，需要获取到待删除节点的前趋节点，但是如果删除的位置刚好是第一个节点，它没有前趋节点，所以需要额外判断处理

        2、带头节点的单向链表

            定义：第一个节点中的数据域不存储有效数据，该头节点只是用于指向第一个有效数据的节点而存在，所以，由于头节点不会因为添加、插入、删除该改变，所以不需要传递二级指针

typedef struct List
{ListNode* head;     //  永远指向头节点 必须要有ListNode* tail;     //  尾指针，可以有 也可以没有size_t size;        //  数量 可以有 也可以没有
}List;

            注意：尾指针tail，能直接找到最后一个节点，但是在尾删除操作时，发挥不了作用，因为要找尾节点的前趋。

        3、单向链表的使用

            1、单链表逆序，要在原基础上进行逆序

#include <stdio.h>struct ListNode* ReverseList(struct ListNode* head ) {// 判断链表是否为空if(NULL == head || NULL == head->next)return head;// 初始化一个指向下一节点的指针，并让头节点指向空struct ListNode* prev = head;struct ListNode* newl = head->next;head->next = NULL;// 循环遍历，让下一个节点的next指针指向它的上一节点while(NULL != newl->next){struct ListNode* next = newl->next;newl->next = prev;prev = newl;newl = next;}// 最后，让最后一个节点指向上一节点，并将其设置为头节点输出newl->next = prev;head = newl;return head;
}

            2、找到链表的倒数第n个节点

#include <time.h>struct ListNode* FindKthToTail(struct ListNode* pHead, int k ) {// 判断链表是否为空if(NULL == pHead)return NULL;// 初始化两个新指针，一个用来计算链表的长度，一个来找地n个节点struct ListNode* fast = pHead;struct ListNode* low = pHead;int len = 0;// 遍历链表，得出链表的总长度while(k--){if(NULL == fast)return NULL;fast = fast->next;}// 遍历链表，找到第n个节点while(NULL != fast){fast = fast->next;low = low->next;}return low;
}

            3、判断链表中是否存在环

bool hasCycle(struct ListNode* head ) {// 判断链表是否为空if(NULL == head || NULL == head->next)return false;// 初始化快慢指针struct ListNode* fast = head;struct ListNode* low = head;// 让快指针一次走两步，让慢指针一次走一步// 如果快慢相遇就说明存在环// 如果不存在环，链表就一定会有指向空的节点// 当快指针遍历完链表，循环便会结束while(NULL != fast->next){fast = fast->next;if(NULL == fast->next)break;fast = fast->next;low = low->next;if(fast == low)return true;}return false;
}

            4、找出环形链表的入口节点

struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {// 判断链表是否为空if(NULL == pHead || NULL == pHead->next)return NULL;// 初始化快慢指针struct ListNode* fast = pHead;struct ListNode* low = pHead;// 快指针一次走两步，慢指针一次走一步// 链表头到环入口的距离=相遇点到环入口的距离+（k-1）圈环长度// 两个指针分别从链表头和相遇点出发，最后一定相遇于环入口while(NULL != fast->next){fast = fast->next;if(NULL == fast->next)break;fast = fast->next;low = low->next;if(fast == low){fast = pHead;while(fast != low){fast = fast->next;low = low->next;}return fast;}}return NULL;
}

            5、合并两个有序链表，合并后保持有序性

#include <math.h>struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {// 判断两个链表是否为空if (NULL == pHead1 && NULL == pHead2)return NULL;else if(NULL == pHead2)return pHead1;else if(NULL == pHead1)return pHead2;// 初始化新的链表存储struct ListNode* pHead3;// 比较两个链表的头节点大小if (pHead1->val < pHead2->val) {pHead3 = pHead1;pHead1 = pHead1->next;} else {pHead3 = pHead2;pHead2 = pHead2->next;}struct ListNode* pHead = pHead3;// 循环遍历，让比较小的值接到新链表的最后，直到一条链表被完全遍历while (NULL != pHead1 && NULL != pHead2) {if (pHead1->val < pHead2->val) {pHead3->next = pHead1;pHead1 = pHead1->next;} else {pHead3->next = pHead2;pHead2 = pHead2->next;}pHead3 = pHead3->next;}// 将另一条链表后面的所有节点接入新链表if(NULL == pHead1)pHead3->next = pHead2;elsepHead3->next = pHead1;return pHead;
}

            6、判断两个链表是否构成Y型链表，如果是，找出第一个公共节点

#include <stdbool.h>struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {// 判断链表是否为空if(NULL == pHead1 || NULL == pHead2)return NULL;// 初始化指针遍历链表struct ListNode* head1 = pHead1;struct ListNode* head2 = pHead2;bool f1=0,f2=0;// 让两条链表的指针同步遍历链表// 当指针遍历完一条链表之后，让它从另一条链表的头节点开始重新遍历，另一个指针也同样// 如果存在Y型，两指针就会相遇在入口位置// 如果不存在就会返回空指针while(head1 != head2){head1 = (head1 == NULL)?pHead2:head1->next;head2 = (head2 == NULL)?pHead1:head2->next;}return head1;
}

四、静态链表

        静态链表的节点存储在一段连续内存中，通过节点中称为游标的一个正整数来访问后继节点

typedef StaticNode
{TYPE data;      //  数据域int index;  //  游标
}StaticNode;int main()
{StaticNode arr[100] = {};arr[0].data = 1;arr[0].index = 5;arr[5].index = 3;arr[3].index = 8;arr[8].index = -1;
}

        在静态链表中进行插入、删除时，只需要修改游标的值即可不需要拷贝内存，也能达到链表的效果，但是也牺牲了随机访问节点的功能，而且链表的优点也有缺失。

        是给没有指针的编程语言提供一种操作单链表的方式。

五、循环链表

        循环链表的最后一个节点的next不再指向NULL，而是指向头节点。如果是单链表就称为单循环链表。

        循环链表的最大优点就是能够通过任意节点可以遍历整个链表。

六、双向链表（双向循环链表）

        所谓的双向链表就是链表节点中有两个指针域，一个指向前一个节点，叫做前趋指针（prev），另一个指向后一个节点，称为后继指针（next）。

        因此可以从后往前遍历链表，对于要访问链表后半部的节点的操作效率更高。

//  双向链表的节点结构
typedef struct ListNode
{struct ListNode* prev;      //  前趋TYPE data;struct ListNode* next;      //   后继
}ListNode;

        在双向链表的基础上，让最后一个节点的next指向头节点，让头节点的prev指向最后一个节点，构成了双向循环链表

七、Linux内核链表

        在普通的链表中，目前面临无法做到任何类型的数据都可以存储的问题。

        Linux内核链表是一种通用的双向循环链表，面对通用的问题，Linux内核链表的节点干脆不存储任何数据域，只有指针域，节点只负责串联起每个节点，不负责存储数据。

        如果要使用Linux内核链表时，把节点放入到数据中。

    函数

        目的：根据结构体中某个成员的地址，能够计算出所在结构体的首地址，从而用户在设计Linux内核链表的节点时，不需要一定放在在数据的首位成员，增加可用性

//  计算出结构体type的成员mem所在的地址距离第一个成员位置的字节数
#define offsetof(type,mem) \((unsigned long)(&(((type*)0)->mem)))//  根据结构成员mem的地址(ptr) 计算出它所在结构(type)变量的首地址
//  ptr要计算的某个节点的地址  type是ptr所在结构体名 mem是它的结构成员名
#define node_to_obj(ptr,type,mem) \((type*)((char*)ptr - offsetof(type,mem)))

八、通用链表

        Linux内核链表虽然设计很巧妙，但是不利于初学者使用，另一种通用的设计思路是借助void*的兼容性，来设计一种链表，称为通用链表，这种链表还需要借助回调函数。

//  定义了一个函数指针变量                返回值 (*函数指针变量名)(参数列表);void (*funcp)(int num1,int num2);
//  该函数指针的类型是                返回值 (*)(参数列表);  void (*)(int,int);
//  函数指针类型重定义                typedef 返回值 (*重定义后的类型名)(参数列表);typedef void (*fp)(int,int);
//  fp 就是 void (*)(int,int)这个函数指针类型 可以用来定义该类型的函数指针变量fp p;   //  p就是函数指针变量