有头链表（注意：头结点有的地方是全局变量）
初学者学自于大话数据结构，不足及错误的地方请读者提出来，谢谢。
可加 qq1366963396交流。
一.创造链表
1.构建链表节点
struct Node
{
int data;//数据域
Node* next;//指针域
}
2.创建链表节点
Node* creatNode(int data)
{
Node* new=(Node*)malloc(sizeof(Node));//申请内存
new->data=data;
new->next=NULL;
return new;//new可能会冲突，换个变量也可以
}
3.整表创建（头插法）
void creatListHead(Node* head1,int n)
{
head1->next = NULL;
srand(time(NULL));
for (int i = 0; i < n; i++)
{
Node* p = (Node*)malloc(sizeof(Node));
p->data = rand() % 100 + 1;
p->next = head1->next;
head1->next = p;
}
}
4.创建链表(尾插法)
void creatListHeatTail(Node* head2, int n)
{
head2->next = NULL;
Node* r = head2;//记录尾部节点
srand(time(NULL));
for (int i = 0; i < n; i++)
{
Node* p = (Node*)malloc(sizeof(Node));
p->data=rand() % 100 + 1;
r->next = p;
r = p;
}
r->next = NULL;
}
二.单链表的读取
Node* GetItem(int i)//获取第i个节点，遍历
{
Node* p=head.next;
int j=1;//计数
while(p&&j<=i)
{
if(j==i)
return p;
p=p->next;
j++;
}
return NULL；
}
三，打印链表数据
void print()//遍历打印
{
Node* p=head.next;
while(p)
{
printf("%d ","p->data");
p=p->next;
}
}
四.插入
1.头插法
void add(Node* new)
{
new->next=head.next;//原来头节点指向的节点现在由新节点指向
head.next=new;头结点指向新节点
//不可以交换，会使得head.next被new覆盖掉,等价于new->next=new
}
2.插入到任意节点前面
bool NodeInsert(int i,Node* newNode)
{
int j=1;
Node* p=head.next;
if(i==j)//若插入到头结点后
add(newNode);//调用头插法
else
{
while(p&&j<i)//找到前驱结点
{
if(j==i-1)
break;
p=p->next;
j++;
}
if(!p||j>i)
return false;
newNode->next=p->next;//插入
p->next=newNode;
}
优化：
void add(Node* newNode,int i)
{
Node* p =&head;
int j = 1;
while (p&&j<i)
{
++j;
p = p->next;
}
newNode->next = p->next;
p->next = newNode;
}
3.尾插法
void tailAdd(Node* newNode)
{
Node* p =&head;//
while (p->next)//判断指针是否为空，也就是判断是否是最后一个节点
{
p = p->next;
}
p->next = newNode;
newNode->next = NULL;
}
五.删除
1.删除第i个节点
void deleteNode(int i)
{
Node* p = &head;
int j = 1;
while (p&&j<i)//找到删除的前一个节点p
{
++j;
p = p->next;
}
p->next = p->next->next;
}
2.整表删除
void deleteList(Node* head)
{
Node* p = head->next;
Node* q;
while (p)
{
q = p->next;//下一个节点
free(p);//释放当前节点
p = q;移到下一个节点
}
}
静态链表（数组描述的链表）：
让数组的元素都是由两个数据域组成，data和cur，数组的每个元素都对应一个data和一个cur。数据域data，用来存放数据元素，也就是通常我们要处理的数据；而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，把cur叫做游标
对数组第一个和最后一个元素做特殊处理，不存数据。通常把未被使用的数组元素称为备用链表。
//数组第一个元素的cur用来存放备用链表第一个节点的下标
//数组最后一个元素的cur用来存放第一个插入元素的下标，相当于头结点
struct StaticList
{
int data;//数据
int cur;//游标
};
StaticList staticList[MAXSIZE];
初始化状态代码
void InitList(StaticList staticList[MAXSIZE])
{
int i;
for (i = 0; i < MAXSIZE - 1; i++)
staticList[i].cur = i + 1;
staticList[MAXSIZE - 1].cur = 0;
}
例：圆圈代表数据域
下标为0的存放备用链表的第一个节点的下标，也就是未被使用的下表为4的数组元素；
下表为3的cur为0，因为下一位置数据为空
下标为5也就是最后一个元素的cur存第一个有值元素的下标，也就是1
一.静态链表插入
下表为4原来未被使用，先把新数据放在这里，其cur为5。要把新数据插在第2个节点前面，先把第2个节点之前的节点的cur赋值为4，再把插入的节点的cur赋值为2，这样就实现了不移动元素，却实现了插入数据的操作。
//若备用链表非空，则返回分配的节点下表，否则返回0
int Malloc_SLL(StaticList staticList[MAXSIZE])
{
int i = staticList[0].cur;//当前第一个元素的cur就是要返回的第一个备用空闲的下标
if (staticList[0].cur)
staticList[0].cur = staticList[i].cur;//由于要拿出一个分量来使用了，所以要把它的 //下一个分量用来做备用
return i;
}
void ListInsert(StaticList staticList[MAXSIZE], int i, int e)
{
int j, k, l;
k = MAXSIZE - 1;//最后一个元素的下标
j = Malloc_SLL(staticList);//获取空闲分量的下标
if (j)
{
staticList[j].data = e;//将数据赋值给空闲分量
for (l = 1; l < i; l++)//找到第i个元素之前的下标
{
k = staticList[k].cur;
}
staticList[j].cur = staticList[k].cur;//把第i个元素之前的节点的cur赋给插入节点的cur
staticList[k].cur =j;//把新节点的下标赋给第i个元素之前的cur
}
}
二.静态链表删除（删除后数据还在，只是用户不需要这个数据，下次malloc时该节点可以用）
//将下标为k的空闲节点回收到备用链表
void Free_SSL(StaticList staticList[MAXSIZE], int k)
{
staticList[k].cur = staticList[0].cur;//把第一个元素cur值赋给要删除的节点的cur
staticList[0].cur = k;//删除的节点下标赋值给第一个下标的cur，下次malloc时优先考虑该节点
}
void ListDelete(StaticList staticList[MAXSIZE],int i)
{
int j, k;
k = MAXSIZE - 1;
for (j = 1; j < i; j++)
{
k = staticList[k].cur;
}
j = staticList[k].cur;
staticList[k].cur = staticList[j].cur;
Free_SSL(staticList, j);
}
三.求长度
int ListLength(StaticList staticList[MAXSIZE])
{
int j = 0;
int i = staticList[MAXSIZE - 1].cur;
while (i)
{
i = staticList[i].cur;
j++;
}
return j;
}
静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。尽管不一定用得上，但这样的思考方式是非常巧妙的，应该理解其思想，以备不时之需。
单向循环链表
1.创建循环链表（带头节点）
node* CreatCycleList1(node* h,node* r)
{
node* p= h;//h为普通带头节点链表
while (p->next)
{
p = p->next;
}
r = p;//找到尾节点
r->next = h;//指向头结点
return r;
}
//打印单向循环链表
void PrintCycleList(node* rear)
{
node* p = rear->next->next;//第一个节点
if (rear == p)
{
printf("该链表是空链表\n");
}
while (p != rear->next)//当p不指向头结点
{
printf("%d ", p->data);
p = p->next;
}
}
将单链表终端节点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为但循环链表，简称循环链表。循环链表一定要头结点。
//与单链表差异：
循环的判断结束条件：原来是p->next是否为空，现在是其是否等于头结点。
优化：
不用头指针，用指向终端节点的尾指针，此时查找开始节点和终端节点都很方便，
若尾指针记为rear，则头结点为rear->next，第一个节点为rear->next->next。
要将两个循环链表合并成一个链表，有了尾指针就非常方便
如下：
void MergeCycleList(node* rearA, node* rearB)
{
node* p = (node*)malloc(sizeof(node));
p= rearB->next;//p保存B链表头结点
rearB->next = rearA->next;//rearB指向A的头结点
rearA->next=p->next;//rearA指向B的第一个节点
free(p);//释放p
}
例：约瑟夫环（后文有双向循环链表实现方法）
思路：
1.建立无头节点的单向循环链表
2.找到起始位置
3.找到要删除的节点并删除
4.移动指针到下一次起点
//部分代码
void solve(node* q, int m)//q是起始位置
{
node* p = q;
node* r;//r来保存删除节点的前一节点
while (p->next != p)//剩一个节点
{
for (int i = 1; i <= m - 1; i++)
{
r = p;//前一节点
p = p->next;
}
r->next = p->next;//删除系欸但
printf("%d ", p->data);
free(p);
p = r->next;//取下一报数起点
}
printf("%d\n", p->data);
}
双向循环链表
1.创建
//创建空链表
void CreatNULLList(dulNode* h)
{
h->next=h;
h->prior = h;
}
//添加节点（尾插法）
void addNode(dulNode* h,dulNode* newNode)
{
dulNode* p = h;
while (p->next!=h)//找到尾节点
{
p = p->next;
}
p->next = newNode;//尾节点指向新节点
newNode->prior = p;
newNode->next = h;
h->prior = newNode;
}
2.添加节点（任意位置）
//获取节点（根据序号）
dulNode* GetNode(dulNode* h, int i)//返回第i个位置的节点
{
int j = 0;
dulNode* p = h;
while (j < i&&p->next!=h)
{
p = p->next;
j++;
}
return p;
}
void InsertNode(dulNode* h, dulNode* newNode,int i)
{
dulNode* p = GetNode(h,i-1);//获取前一节点
newNode->prior = p;//第一步
newNode->next = p->next;
p->next->prior = newNode;
p->next = newNode;//第四步
}
3.删除节点（根据位置）
void DeleteNode(dulNode* h,int i)
{
dulNode* p = GetNode(h, i);//找到要删除的节点
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
}
例：用双向循环链表实现约瑟夫问题（前文有单向循环链表实现方法）
void solve(node* q, int m)//q为起始位置
{
node* p = q;
node* r;
while (p->next != p)
{
for (int i = 1; i <= m - 1; i++)
{
r = p;
p = p->next;
}
r->next = p->next;
p->next->prior = r;//删除与单项循环链表有区别
printf("%d ", p->data);
free(p);
p = r->next;
}
printf("%d", p->data);
}
