- 链表是由结点构成的，关键是定义结点
- C语言程序设计上两大特例：①链表节点的定义②递归函数的定义。这两个违反了先定义再使用。
一、链表的分类
3.静态链表：各结点在程序中定义，不是临时开辟的（不是用malloc函数或者calloc函数动态开辟的空间），始终占着内存不放。
struct student
{
int number; //数据区域
struct student *next; // 指针区域
}; //定义结构体类型
int main()
{
struct student a,b,c,*head,*p; //定义结点、头指针、和进行遍历的指针
a.number=1;
b.number=2;
c.number=3;
head=&a;
a.next=&b;b.next=&c;c.next=NULL;
p=head;
do
{
printf("d",p->number); //进行遍历
p=p->next;
}
while(p!NULL);
}
二、链表的基本操作
4.动态链表的创建
（1）创建链表：从无到有建立起一个链表，即往空链表中一次插入若干结点，并保持结点之间的前驱和后继关系。顾名思义，链表就像一条铁环串成的链子，每个铁环是结点，连接下一个铁环，也可以理解为老师带领手拉手小朋友排队，头指针是老师，小朋友与小朋友之间拉着手。
第一次看的时候没有看懂，应该在纸上把链表的图画一画就可以明白。
struct num
{
int number;
struct num *next;
};
int icount; //全局变量标记结点的顺序
struct *create()
{
struct *pHead=NULL,*pEnd,*pNew;
icount=0;
pNew=pEnd=(struct*)malloc(sizeof(struct num));
scanf("%d",&pNew->number);
while(pNew->number!=0) //while(pNew->number>0)作用相同
{
icount++;
if(icount==1) //判断是否是第一次加入结点也可以用if(pHead==NULL)进行判断
{
pNew->next=pHead; //使指针指向为空，也可以pNew->next=NULL
pEnd=pNew;
pHead=pNew;
}
else
{
pNew->next=NULL;
pEnd->next=pNew;
pEnd=pNew;
}
pNew=(struct*)malloc(sizeof(struct num));//再次分配结点的内存空间，为下一个结点插入做准备
scanf("%d",&pNew->number);
}
free(pNew);
return pHead;
}
5.单链表的遍历输出
（2）检索操作：按给定的结点引导或检索条件，查找某个结点。如果找到指定的结点则称为检索成功；否则检索失败。自己理解是从链表的开头按照顺序一个一个检查，然后找到自己想要找到的结点，如果找到则检索成功，如果没找到就是检索失败。
void print(struct num *pHead)
{
struct num *pTemp;
int n=1; //表示链表中结点的序号
pTemp=pHead;
while(pTemp!=NULL)
{
printf("%d",pTemp->num);
pTemp=pTemp->next; //遍历的关键，移动临时指针到下一个结点
n++;
}
}
6.单链表的插入
（3）插入操作：在结点N(i)和N(i+1)之间插入一个新的结点N，使线性表的长度增加1，且N(i)和N(i+1)的逻辑关系发生变化：
插入前N(i)是N(i+1)的前驱，N(i+1)是N(i)的后继；插入后新的结点N成为N(i)的后继，N(i+1)的前驱。
插入原则：
①插入操作不应破坏原链接关系
②插入的结点应该在它该在的位置（按照顺序排好，如果不要求顺序，则可以任意插入）
实现方法：
应该有一个插入位置的查找子过程
共有3中插入情况：
①插入结点在链表最前端
struct num *Insert(struct num *pHead)
{
struct num *pNew;
pNew=(struct*)malloc(sizeof(struct num));
pNew->next=pHead; //新结点指针指向原来的首结点
pHead=pNew; //头指针指向新节点
icuont++; //增加链表节点数量
return pHead;
}
②插入节点在链表中间
struct num *Insert(struct num *pHead,int n)
{
struct num *p=pHead,*PNew; //两个指针，*P是插入结点的前一个结点
while(p&&p->number!=n) //查找要插入的位置
p=p->next; //下移到下一个结点处
pNew=(struct*)malloc(sizeof(struct num));
scanf("%d",&pNew->number);
pNew->next=p->next ; //新结点指向下一个结点
p->next=pNew; // 上一个结点指向新结点
icount++; //链表长度增加
return pHead;
}
③插入节点在链表尾端
struct num *Insert(struct num *pHead)
{
struct num *p=pHead,*pNew;
while(p&&p->next!=NULL)
p=p->next;
pNew=(struct*)malloc(sizeof(struct num));
scanf("%d",&pNew->number);
p->next=pNew; // 尾结点指向新结点
pNew->next=NULL; //新结点指向空指针，变为尾结点
icount++;
return pHead;
}
7.单链表的删除
（4）删除操作：删除结点N(i)后，使线性表的长度减1，且N(i-1)N(i)N(i+1)的逻辑关系发生变化：
删除前，N(i)是N(i+1)的前驱，N(i-1)的后继；删除后，N(i-1)成为N(i+1)的前驱，N(i+1)成为N(i-1)的后继。
删除的原则：
不改变原来排列的顺序，只是从链表中分离开来，撤销原来的链接关系。
两种情况：
①要删的结点是头指针所指的结点则直接操作；
②不是头结点，要依次往下找。另外考虑：空表和找不到要删除的结点
需要两个临时指针：
P1：判断指向的结点是不是要删除的结点（用于寻找）；
P2：始终指向P1前面的一个结点；
void Delete(struct num *pHead,int n)
{
int i;
struct num *pTemp; //临时指针，用于查找所要删除的结点
struct num *pPre; //表示要删除的结点前的结点
pTemp=pHead; //得到链表的头结点
for(i=1;i<n;i++)
{
pPre=pTemp; //pPre跟进pTemp
pTemp=pTemp->next; //pTemp前进下移到下一个结点
}
pPre->next=pTemp->next; // 将要删除的结点两边的结点链接
free(pTemp);
icount--; //减少链表中结点的个数
}
三、循环链表
单链表最后一个结点的指针指向NULL，循环链表的最后一个结点的指针指向链表头结点，首尾相连，形成数据链。
与单链表的不同点：
（1）链表的建立：单链表需要创建一个头结点，专门存放第一个结点的地址，单链表的尾指针的指针域指向NULL，；而循环链表的建立，不需要专门的头结点，让最后一个结点的指针域指向链表的头结点即可。
（2）链表表尾的判断：单链表判断结点是否为表尾结点，只需判断结点的指针域是否为NULL，如果是，则为尾结点，否则不是。而循环链表判断是否尾结点，则是判断该节点的指针域是否指向链表头结点。
四、双向链表
双向两链表也是基于单链表，单链表有一个头结点，一个尾结点，双链表有两个指针域，一个指向左边一个指向右边，
一个存储直接后继结点地址，一般称为右链域，一个存储直接前驱结点地址，一般成为左链域。
13.双向循环链表创建
struct num
{
int number;
struct num *rlink;
struct num *llink;
};
struct num *creat(int n)
{
struct num *p,*h,*s; //h代表头结点，S代表新结点，p则储存新结点的前驱
int i;
if(h=(struct*)malloc(sizeof(struct num))==NULL) //判断开辟空间是否成功
exit(0);
h->llink=NULL; //头结点初始化
h->rlink=NULL; //头结点初始化
p=h;
for(i=0;i<n;i++)
{
if(s=(struct*)malloc(sizeof(struct num))==NULL) //开辟新结点
exit(0);
p->rlink=s; //新结点前驱向右指向新结点
printf("请输入第%d个人的姓名",i+1);
scanf("%d",s->number); //输入新结点里的信息
s->llink=p; //新结点向左指向前驱
s->rlink=NULL; //新结点向右指向空
p=s; //将创建好的新结点作为下一个新结点的前驱
}
h->llink=s; //头结点向左指向最后一个结点
p->rlink=h; //最后一个结点向右指向头结点，连接完成
return(h);
}
14.双向链表查找
从表头结点往后依次比较各结点数据域的值，若是该特定值。则返回结点的指针，否则继续往后查，直到表尾
struct num *search(struct num *pHead,int n)
{
struct num *p; //行走指针，一个一个结点比较
int n; //要得到的那个数
p=pHead->rlink; //从第一个结点开始
while(p!=h) //当P走完一圈
{
y=p->number;
if(n==y) //进行比较
return(p);
else
p=p->rlink; //继续遍历
}
}
15.双向列表插入
双向链表插入结点和单链表插入结点方法基本相同，只是指针域要分左右，比如要在p，q之间插入结点s，只需把p右链域指向s，s的左链域指向p，s的右链域指向q，q的左链域指向s即可
void Intset(struct num *p)
{
int n;
struct num *s;
if(s=(struct*)malloc(sizeof(struct num))==NULL) //开辟空间
exit(0);
scanf("%d",&n);
s->number=n;
s->rlink=p->rlink; //将新结点的向右指向后一个结点
p->rlink=s; //前一个结点指向新结点
s->llink=p; //新结点指向前一个结点
(s->rlink)->llink=s; //后一个结点向左指向新结点
}
16.双链表的删除
双链表的删除和单链表的删除也类似，将要删除的链表跳过即可，需要注意的是在删除的时候分清左右链域
比如：s、p、q三个连续结点，要删除p，只需将s的右链域指向q，q的左链域指向s，并释放p结点就可以了
void del(struct num *p)
{
(p->rlink)->llink=p->llink;//要删除结点P的后继向左指向P的前驱
(p->llink)->rlink=p->rlink;//要删除结点P的前驱向右指向P的后继
free(p); //将P开辟的空间释放
}
以上是链表的一些操作，如果以上内容有错误，欢迎大家指出，谢谢大家