目录
线性表
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表，链表，栈，队列，字符串........
线性表在逻辑上是线性结构，也就是说连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
顺序表
顺序表是用一段物理地址连续的存储单元一次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删改查。
概念及结构
静态顺序表：使用定长数组存储元素
#define N 7
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N]; 定长数组
size_t size; 有效的数据个数
};动态顺序表：使用动态开辟的数组存储元素
typedef struct SeqList
{
DataType* arr; //指向动态开辟的数组
size_t size; //有效的数据个数
size_t capicity; //容量空间的大小
}SeqList;现实中一般使用动态顺序表，静态顺序表大小固定，开辟后不可改变，容易造成丢失或不足。
使用动态可以创建一个小的数组，有需要时就开辟（按照2被的数据两进行开辟，能够有效的减少空间浪费，解决不足的问题，但是频繁的创建对程序的效率有影响）。
接口实现
#include"seqlist.h"
void SLprint(SL *psl)
{
assert(psl);
size_t i = 0;
printf("capacity == %u\n", psl->capacity);
printf("size == %u\n", psl->size);
for (i = 0; i < psl->size; i++)
{
printf("%d ", psl->arr[i]);
}
printf("\n");
}
void SLInit(SL * psl)
{
assert(psl);
psl->arr = NULL;
psl->size = 0;
psl->capacity = 0;
}
void SLDestoy(SL *psl)
{
assert(psl);
free(psl->arr);
psl->arr = NULL;
psl->size = 0;
psl->capacity = 0;
}
void CheckCapacity(SL* psl)
{
assert(psl);
if (psl->size == psl->capacity)
{
size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDataType * tmp = (SLDataType *)realloc(psl->arr, newcapacity*sizeof(size_t));
if (tmp == NULL)
{
perror("realloc capacity fail");
return;
}
else
{
psl->arr = tmp;
psl->capacity = newcapacity;
}
}
}
void SLPushBack(SL* psl, SLDataType x)
{
assert(psl);
CheckCapacity(psl);
psl->arr[psl->size] = x;
psl->size++;
}
void SLPopBack(SL* psl)
{
assert(psl);
assert(psl->size > 0);
psl->size--;
}
void SLPushFront(SL* psl, SLDataType x)
{
assert(psl);
CheckCapacity(psl);
int i = 0;
for (i = psl->size - 1; i >= 0; i--)
{
psl->arr[i + 1] = psl->arr[i];
}
psl->arr[0] = x;
psl->size++;
}
void SLPopFront(SL* psl)
{
assert(psl);
assert(psl->size > 0);
int i = 1;
for (i = 1; i < psl->size; i++)
{
psl->arr[i - 1] = psl->arr[i];
}
psl->size--;
}
void SLInSert(SL* psl, int num ,SLDataType x)
{
assert(psl);
CheckCapacity(psl);
assert(num <= psl->size);
int i = 0;
for (i = psl->size - 1; i >= num; i--)
{
psl->arr[i + 1] = psl->arr[i];
}
psl->arr[num] = x;
psl->size++;
}
void SLErase(SL* psl, int num)
{
assert(psl);
CheckCapacity(psl);
assert(num <= psl->size);
int i = 0;
for (i =num; i < psl->size; i++)
{
psl->arr[i] = psl->arr[i+1];
}
psl->size--;
}
int SLFind(SL *psl, SLDataType x)
{
assert(psl);
int i = 0;
int flag = -1;
for (i = 0; i < psl->size; i++)
{
if (psl->arr[i] == x)
{
flag = i;
break;
}
}
return flag;
}
void Findprint(int flag)
{
if (flag == -1)
{
printf("找不到\n");
}
else
{
printf("找到了，下标是%d\n", flag);
}
}数组相关题
顺序表的问题及思考
中间/头部的插入，时间复杂度是多少？
顺序表中，从中间/头部插入需要移动后面的全部数据，最坏的情况下时间复杂度为O（N）。
增容需要申请新的空间，拷贝数据，，释放旧空间，消耗不小。
增容是呈2倍增长，势必会浪费一部分空间。
链表
链表的概念及结构
链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
注意：
1、链表结构在逻辑上是连续的，但是在物理内存上不一定连续。
2、现实中节点一般是从堆上申请出来的（malloc）。
3、从堆上申请的空间，是按照一定的策略来分配，两次申请的空间可能连续，也可能不连续。
（节点之间的逻辑关系是由指针来决定，与物理内存分配的空间无关，内存地址大的空间，链表中也可以在前面）。
链表的分类
虽然链表的结构众多，但是最常用的就是两种
链表的实现
以下将实现无头单向非循环链表。
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLlistType;
typedef struct SLlistNode
{
SLlistType SLlistData;
struct SLlistNode *next;
}SLlistNode;
//申请一个动态节点
SLlistNode* BuySLListNode(SLlistType x)；
//头插
void SLListPushFront(SLlistNode ** pphead, SLlistType x);
//头删
void SLListPopFront(SLlistNode ** pphead);
//打印
void SLListPrint(SLlistNode * pphead);
//尾插
void SLListPushBack(SLlistNode** pphead, SLlistType x);
//尾删
void SLListPopBack(SLlistNode** pphead);
//查找
SLlistNode* SLListFind(SLlistNode *phead, SLlistType x);
//中间插入
void SLListInSert(SLlistNode **pphead, SLlistNode* pos, SLlistType x);
//中间删除
void SLListErase(SLlistNode **pphead, SLlistNode* pos);
//释放
void SLListDestory(SLlistNode **pphead);创建链表结构
typedef int SLlistType;//重新定义数据类型，作用是方便以后修改。
//定义了包含一个有符号整型与一个结构体类型指针的结构体结构，注意struct SLlistNode *next必须使用结构体类型来定义，不能使用typedef简化后的SLlistNode来定义，因为typedef定义是在指针之后生效。
typedef struct SLlistNode
{
SLlistType SLlistData;
struct SLlistNode *next;
}SLlistNode;申请一个动态节点
SLlistNode* BuySLListNode(SLlistType x)
{
SLlistNode *newnode = (SLlistNode *)malloc(sizeof(SLlistNode));
if (newnode != NULL)
{
newnode->SLlistData = x;
newnode->next = NULL;
}
else
{
assert(newnode);
}
return newnode;
}
分析：
1：SLlistNode *newnode = (SLlistNode *)malloc(sizeof(SLlistNode))，为什么使用指针，而不是直接创建一个结构体变量？
变量是存储在栈区中，当创建的函数运行完毕，结构体变量就会被销毁，所以不能创建变量，malloc开辟的空间是存在于堆区之中，程序运行期间一直存在，除非用free释放。
2：newnode->next = NULL，为什么将指针赋值为NULL，链表中NULL确定链表的结尾，为了避免链表内容较多出现bug，最好将每个节点的指针都指向NULL，需要时再修改。链表的打印
链表的打印主要分为两种情况，一种是链表有节点时，另一种是链表无节点。
有节点时，从头依次打印每个节点的值，该过程由临时创建的指针cur完成，每打印一个值cur移动到下个节点，直到cur的值为NULL时，停止移动。
无节点时，直接打印NULL，该过程是对cur进行判定，如果cur的值为NULL，就直接打印。
注意：因为要打印NULL，所以不用assert对phead进行判定。
//打印
void SLListPrint( SLlistNode * phead)
{
SLlistNode * cur = phead;
while (cur != NULL)
{
printf("%d->", cur->SLlistData);
cur = cur->next;
}
if (cur == NULL)
{
printf("NULL\n");
}
}头部的插入与删除
头部插入
链表的头部插入分为两种情况，分别是有节点插入与无节点插入。
有节点头部插入时，需要改变plist（plist是指向链表首节点的指针）的值，传递给头部插入函数的就是二级指针。
无头部节点时，plist为空，该过程plist=newnode即可，newnode->next指针默认为NULL，所以不需要修改。
//头插,不适用返回值，直接通过修改指针进行关联
void SLListPushFront(SLlistNode ** pphead,SLlistType x)
{
assert(pphead);//pphead始终指向plist所以，pphead恒不为空，必须对其断言。
SLlistNode * newnode = BuySLListNode(x);
assert(newnode);//判断空间开辟是否成功。
if (pphead == NULL)
{
*pphead = newnode;
}
else
{
newnode->next = *pphead;
*pphead = newnode;
}
}头部删除
头部删除有三种情况，多节点，单节点，无节点。
多节点时，将plist指向首节点后的节点，然后释放首节点。
单节点
无节点时不需要删除，可以通过断言判断。
注意：通过以上的分析，多节点和单节点删除的代码一样，程序可以简化。
//头删
void SLListPopFront(SLlistNode ** pphead)
{
assert(pphead);
if (*pphead == NULL)//温柔的检查
{
return;
}
else
{
SLlistNode * cur = *pphead;
assert(cur);
*pphead = (*pphead)->next;
free(cur);
}
}尾部的插入与删除
尾部的插入分为有节点和无节点两种。
无节点 时，*pphead=newnode；
注意:尾插最坏情况，时间复杂度O（N）。
//尾插
void SLListPushBack(SLlistNode** pphead,SLlistType x)
{
assert(pphead);
SLlistNode * cur = BuySLListNode(x);
assert(cur);
if (*pphead == NULL)
{
*pphead = cur;
}
else
{
SLlistNode*tmp = *pphead;
while (tmp->next != NULL)
{
tmp = tmp->next;
}
tmp->next = cur;
}
}尾删
尾删分为多节点，单节点，无节点
单节点删除的情况与多节点不同，单节点时cur->next指向NULL。
无节点时，对plist进行检测。
void SLListPopBack(SLlistNode** pphead)
{
assert(pphead);
if (*pphead == NULL)
{
return;
}
else
{
SLlistNode*cur = *pphead;
if (cur->next == NULL)
{
free(*pphead);
*pphead = NULL;
}
else
{
while (cur->next->next != NULL)
{
cur = cur->next;
}
free(cur->next);
cur->next = NULL;
}
}
}查找与中间部位的插入、删除
查找，原理就是遍历各节点的每一个元素，直到遍历指针为空时为止。
SLlistNode* SLListFind(SLlistNode *phead ,SLlistType x)
{
assert(phead);
while (phead != NULL&&x != phead->SLlistData)
{
phead = phead->next;
}
return phead;
}
中间部位删除
中间部位插入，是指给定节点地址，在该节点周边插入新节点，这样存在两种情况，该节点前还是该节点后，以下以该节点前为例。
节点前插入分为三种情况，中间插入，头部插入和无节点插入。
中间插入时，需要对链表进行遍历，找到pos指针前的指针。
头部节点插入时，prev与pos相同。
无节点插入，plist为NULL，此时直接调用头插函数。
void SLListInSert(SLlistNode **pphead, SLlistNode* pos, SLlistType x)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SLListPushFront(pphead,x);
}
else
{
SLlistNode*prev = *pphead;
assert(prev);
while ( prev->next != pos)
{
prev = prev->next;
assert(prev);//这里用来检查pos是否有效，当pos的地址不在链表中，prev的值必为空。
}
SLlistNode* newnode = BuySLListNode(x);
assert(newnode);
newnode->next = pos;
prev->next = newnode;
}
}中间部位的删除分为四种情况，中间位置，头位置，尾位置，无节点。
void SLListErase(SLlistNode **pphead, SLlistNode* pos)
{
assert(pphead);
assert(pos);
assert(*pphead);
SLlistNode*prev = *pphead;
if (prev == pos)
{
*pphead = pos->next;
}
else
{
while (prev ->next!= pos)
{
prev = prev->next;
assert(prev);
}
prev->next = pos->next;
}
free(pos);
}释放链表
void SLListDestory(SLlistNode **pphead)
{
assert(pphead);
assert(*pphead);
SLlistNode*prev = *pphead;
SLlistNode*cur = *pphead;
while (prev != NULL)
{
cur = prev->next;
free(prev);
prev = cur;
}
*pphead = NULL;
}链表的题目
题目1
思路1，原地删除，该思路是在原来的链表中，对值为val的节点进行删除，主要考虑的是首节点的值为val，以及非首节点的值为val两种情况，首节点的值为val时，不断的移动首节点，直到找到第一个值不为val的节点，非首节点的值为val时，该节点被释放，所以需要两个指针，cur进行释放，prev指针进行定位，当该节点值不为val时，两个指针同时向前移动一步。
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* cur = head, *prev = NULL;
while (cur)
{
if (head->val == val)
{
head = head->next;
free(cur);
cur = head;
}
else
{
if (cur->val == val)
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
else
{
prev = cur;
cur = cur->next;
}
}
}
return head;
}
int main()
{
struct ListNode *n1 = (struct ListNode *)malloc(sizeof(struct ListNode));
//struct ListNode *n2 = (struct ListNode *)malloc(sizeof(struct ListNode));
//struct ListNode *n3 = (struct ListNode *)malloc(sizeof(struct ListNode));
//struct ListNode *n4 = (struct ListNode *)malloc(sizeof(struct ListNode));
/*struct ListNode *n5 = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode *n6 = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode *n7 = (struct ListNode *)malloc(sizeof(struct ListNode));*/
n1->val = 1;
//n2->val = 7;
//n3->val = 7;
//n4->val = 7;
/*n5->val = 4;
n6->val = 5;
n7->val = 6;*/
n1->next = NULL;
//n2->next = n3;
//n3->next = n4;
//n4->next = NULL;
/*n5->next = n6;
n6->next = n7;
n7->next = NULL;*/
removeElements(n1, 2);
system("pause");
return 0;
}解法2，替换法
该思路从新创建一个指针，节点值不为val时链接到新指针上，实现比第一种解法简单，但是需要进行一次新头节点的链接，以及最后tail->next指针需要指向NULL。
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newhead = NULL;
struct ListNode* cur = head;
struct ListNode* tail = newhead;
while (cur != NULL)
{
if (cur->val == val)
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
else
{
if (newhead == NULL)
{
newhead = cur;
tail = newhead;
}
else
{
tail->next = cur;
tail = tail->next;
}
cur = cur->next;
}
}
if (tail != NULL)
{
tail->next = NULL;
}
return newhead;
}思路3 哨兵头替换，之前的替换中需要判断链表头节点的位置，代码冗余，使用哨兵头，可以简化这个步骤。
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
assert(guard);
guard->next = NULL;
struct ListNode* cur = head;
struct ListNode* tail = guard;
while (cur != NULL)
{
if (cur->val == val)
{
struct ListNode* next = cur->next;
free(cur);
cur = next;
}
else
{
tail->next = cur;
tail = tail->next;
cur = cur->next;
}
}
if (tail != NULL)
{
tail->next = NULL;
}
struct ListNode* newhead = guard->next;
free(guard);
return newhead;
}题目2
思路：合并聊表，如果将链表放在原有的链表中，还需要单独判断首节点，比较麻烦，所以最有效的做法是使用哨兵头。后续将值小的节点依次链接起来。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
struct ListNode* guard=(struct ListNode* )malloc(sizeof(struct ListNode));
struct ListNode* cur1=list1;
struct ListNode* cur2=list2;
struct ListNode* tail=guard;
while(cur1!=NULL&&cur2!=NULL)
{
if(cur1->val<cur2->val)
{
tail->next=cur1;
tail=tail->next;
cur1=cur1->next;
}
else
{
tail->next=cur2;
tail=tail->next;
cur2=cur2->next;
}
}
if(cur1==NULL)
{
tail->next=cur2;
}
if(cur2==NULL)
{
tail->next=cur1;
}
struct ListNode* newhead=guard->next;
free(guard);
return newhead;
}题目3
思路1就是头插，实现起来非常容易，现在用另一种方法实现，就是反转。
反转是指在不改变节点的情况下，将节点的指针反向链接。
反转需要注意的是，需要确定一个指针cur，由该指针来判断循环的执行。
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;//判断循环的执行
struct ListNode*prev = NULL;
struct ListNode* next = NULL;//作为cur指针移动的指向
while (cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}题目4
该题目是最直观的快慢指针题，快指针走两步，慢指针走一步，最后返回慢指针的值。
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode*fast=head;
struct ListNode*slow=head;
while(fast!=NULL&&fast->next!=NULL)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}题目5
思路：本体的解决思路首先设置两个哨兵头，一个哨兵头用来链接小于X的节点，另一个哨兵头用来链接大于X的节点。
假设一个链表， X为4。
lessguard作为小于x的哨兵头。
greaterguard作为大于x的节点的哨兵头。
在原链表中，cur进行判断，cur移动到下一个节点时，该节点的值与x相比，如果小于x，该节点连接到lessguard后，反之连接到greaterguard后。
需要注意的是，该题目有几个情况需要分析，
同时还要注意，最后将尾节点的next指针指向NULL。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x)
{
// write code here
ListNode* lessGuard =(ListNode* )malloc(sizeof(ListNode));
ListNode* lessTail =lessGuard;
lessGuard->next=NULL;
ListNode* greaterGuard = (ListNode* )malloc(sizeof(ListNode));
ListNode* greaterTail = greaterGuard;
greaterGuard->next=NULL;
ListNode* cur=pHead;
while(cur)
{
if(cur->val<x)
{
lessTail->next=cur;
lessTail=lessTail->next;
}
else
{
greaterTail->next=cur;
greaterTail=greaterTail->next;
}
cur=cur->next;
}
lessTail->next=greaterGuard->next;
greaterTail->next=NULL;
pHead=lessGuard->next;
free(lessGuard);
free(greaterGuard);
return pHead;
}
};题目6
判断回文结构就是看链表两端节点的值是否相等。
上图同一个链表中，蓝色箭头的指向的节点的值相等，绿色的也相等，这样的链表就是回文链表，那么如何判断一个回文链表呢？主要的方法是逆置。
思路有很多种：
第一种是将整个链表复制一份，然后将复制的链表逆置，再与原链表比较。
第二种是将整个链表的值复制进一个数组种，然后对数组的值进行判断，该方法最简单。
第三种就是将原链表的后半部分逆置，然后进行判断，以下的题解将使用这种思路。
该思路分为三步，一找到链表的开始逆置的节点，二将之后的链表逆置，三进行比较。
一、找到链表的开始逆置的节点，正常情况下，节点分为奇数和偶数两种。
上图红色箭头指向的节点就是开始逆置的节点，奇数个数节点的链表就是中间的节点，偶数个数的链表就是中间两个节点中靠后的一个，这里可以使用快慢指针实现。
ListNode* midcheck(ListNode* A)
{
ListNode* fast=A;
ListNode* slow=A;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
二、将之后的链表逆置。
ListNode* rever(ListNode* head)
{
ListNode* prev=NULL;
ListNode* cur=head;
while(cur)
{
ListNode* next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
return prev;
}
三、进行比较
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
// write code here
ListNode* mid=midcheck(A);
ListNode* newhead=rever(mid);
while(A&&newhead)
{
if(A->val!=newhead->val)
{
return false;
}
A=A->next;
newhead=newhead->next;
}
return true;
}
};完整代码
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
ListNode* midcheck(ListNode* A)
{
ListNode* fast=A;
ListNode* slow=A;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
ListNode* rever(ListNode* head)
{
ListNode* prev=NULL;
ListNode* cur=head;
while(cur)
{
ListNode* next=cur->next;
cur->next=prev;
prev=cur;
cur=next;
}
return prev;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A)
{
// write code here
ListNode* mid=midcheck(A);
ListNode* newhead=rever(mid);
while(A&&newhead)
{
if(A->val!=newhead->val)
{
return false;
}
A=A->next;
newhead=newhead->next;
}
return true;
}
};题目7
双向链表的实现
链表包含很多结构，具体情况可以参考前面，这里的链表指的是带头双向循环链表，双向带头循环链表结构上虽然比单链表复杂，但是使用比单链表简单很多，在插入与删除时降低了代码的难度。
双向循环链表的结构
双向链表的接口
Node* LTInit(Node* head);//创建链表的哨兵头创建双向链表结构
定义链表的结构，带头双向循环链表的结构中有两个指针，一个指针指向节点前一个节点，一个指针指向节点后一个节点。
typedef int LTDatatype;
typedef struct LTnode
{
struct LTnode*prev;
struct LTnode*next;
LTDatatype val;
}Node;值的类型最好重定义一下，方便链表存储的值类型改变时修改。
创建哨兵头
创建哨兵头时需要注意，哨兵头的prev指针和next指针一定要指向自己，这样做在增加节点时可以哨兵头的prev指针可以直接指向链表的尾部，同时创建会改变主函数传递的头节点，所以需要使用返回或者二级指针。
Node* LTInit(Node* head)//初始化哨兵头
{
head = (Node*)malloc(sizeof(Node));
assert(head);
head->prev = head;
head->next = head;
return head;
}链表的插入
链表的插入分为三种情况，头插，尾插，和任意位置，但无论哪一种插入，首先都需要开辟新的节点。
开辟新节点
因为malloc是在堆区开辟节点，所以开辟后断言一下，确定newnode没有问题。与初始化哨兵头不同，新节点的两个指针不需要指向自身，置空即可。最后用return将新节点的地址返回到上一函数。
Node* BuyNode(LTDatatype x)
{
Node* newnode = (Node *)malloc(sizeof(Node));
assert(newnode);
newnode->prev = NULL;
newnode->next = NULL;
newnode->val = x;
return newnode;
}头插
头插指在哨兵头后插入节点，该节点和哨兵头链接，头部插入不需要对链表进行遍历，所以时间复杂度为O（1）。
头插时分为通常插入与极端插入两种情况，通常插入时链表中有节点，新节点的next指针与后节点链接，而极端情况时链表中没有节点，新节点的next指针要与哨兵头链接。
在单链表中对上述两种情况需要分别判定，如果新节点后没有节点那么新节点的next指向NULL，如果有节点则指向节点，但在双向链表中则不需要进行判定，结构上的优势大大简化了代码。
在插入之前可以先创建两个临时指针变量prev,next，prev指向哨兵头，next指向首节点，因为双向链表是循环的，所以链表中没有节点时，prev与next指向哨兵头，有节点时，next指向首节点，所以链接的时候，只需要将新节点与这两个指针变量链接起来。
void LTPushFront(Node* head, LTDatatype x)
{
assert(head);
Node* newnode = BuyNode(x);
Node* prev = head;
Node* next = head->next;
prev->next = newnode;
newnode->prev = prev;
newnode->next = next;
next->prev = newnode;
}尾插
尾插就是在链表的最后一个节点之后插入，分为两种情况有节点和无节点。
在单链表中，在尾部插入节点必须要对整个链表进行遍历，最坏的情况下时间复杂度为O(n),但是在双向链表中，不需要遍历，找尾只需要guard->prev，另外单项链表尾插时要考虑是否是第一个节点，但是双向链表中，当链表中没有节点时，尾节点就是哨兵头，直接插入即可，大大减轻了代码的复杂程度。
void LTPushBack(Node* head, LTDatatype x)
{
assert(head);
Node* newnode = BuyNode(x);
Node* tail = head->prev;
tail->next = newnode;
newnode->prev = tail;
newnode->next = head;
head->prev = newnode;
}任意节点插入
是指在链表内任意节点之前插入一个节点，双向链表的任意节点插入与单项链表一样，需要对整个链表进行遍历，但与单向链表不同，不需要在链表中再次遍历，找到节点之前的节点。
双向链表的查找（遍历），该函数的目的主要是通过值找到对应的节点，存在找到与找不到两种情况，找到时返回节点地址，找不到时返回NULL，还有要注意的是，查找时从第一个节点开始，当被查找的地址等于哨兵头地址时结束。
Node* LTFind(Node * head,LTDatatype x)
{
assert(head);
Node * cur = head->next;
while (cur != head)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}任意节点插入
任意节点插入分为四种情况，头节点，尾节点，无节点，中间节点，在单链表中需要对不同的情况进行区分，但是双链表中只需要传递不同的参数即可，尾节点插入只要吧哨兵头作为参数，无节点时把哨兵头作为参数，在特定节点前插入时使用LTFind函数的返回值。
void LTInster(Node * pos, LTDatatype x)
{
Node * prev = pos->prev;
Node * newnode = BuyNode(x);
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
}修改
修改可以直接套用LTFind函数，改变函数的值。
void LTAmend(Node * pos, LTDatatype x)
{
pos->val = x;
}删除
删除分为头删，尾删，任意节点删除，在单链表中各部分都需要不同实现，但是双向链表中任意节点删除就可以替代全部的功能，需要注意的是被删除的位置pos需要使用者自行判定是否在链表中。
void LTErase(Node* pos)
{
assert(pos);
Node* prev = pos->prev;
Node* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}链表的释放
链表释放因该从首节点开始直到最后再释放哨兵头。
void LTDestory(Node * head)
{
Node *cur = head->next;
while (cur != head)
{
Node *next = cur->next;
free(cur);
cur = next;
}
free(head);
}