数据结构2-线性表
目录
一、线性表介绍
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;
else
pHead3->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就是函数指针变量