赵老师笔记----链表
一、链表的概念
链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构。
特点：链表由一系列节点（链表中每一个元素就称为节点）组成，节点在运行时动态生成（malloc），每个节点包括两部分：
一个是存储数据元素的数据域
一个是存储下一个节点地址的指针域
链表的构成：
链表由一个个节点构成，而每个节点一般用结构体的形式去组织：
typedef struct student
{
int num;
int score;
char name[20];//数据域
struct student *next;//指针域
}STU;
数据域：
int num;
int score;
char name[20];//数据域
指针域：
struct student *next;//指针域
二、链表的创建
void link_creat_head(STU **p_head,STU *p_new)
{
STU *p_mov=*p_head;
if(*p_head==NULL)//第一次加入链表为空时，p_head直接将p_new加入到链表中
{
*p_head=p_new;
p_new->next=NULL;
}
else//第二次及以后加入链表时，先要找到链表尾部，然后再加入p_new到尾部
{
while(p_mov->next!=NULL)
{
p_mov=p_mov->next;//找到原链表的最后一个节点
}
p_mov->next=p_new;//将新申请的节点加入链表
p_new->next=NULL;
}
}
三、链表的遍历
void link_print(STU *head)
{
STU *p_mov=head;
while(p_mov!=NULL)
{
printf("学号=%d、分数=%d、名字=%s\n",p_mov->num,p_mov->score,p_mov->name);
p_mov=p_mov->next;
}
}
四、链表的释放
void link_free(STU **head)
{
STU *p_mov=*head;
while(*head!=NULL)
{
p_mov=*head;
*head=(*head)->next;
free(p_mov);
}
}
五、链表节点的查找
STU * link_search_num(STU *head,int num)
{
STU *p_mov=head;
while(p_mov!=NULL)
{
if(p_mov->num==num)//找到了
{
return p_mov;
}
p_mov=p_mov->next;
}
return NULL;//没有找到
}
任务：查找姓名节点
STU * link_search_name(STU *head,char *name)
{
STU *p_mov=head;
while(p_mov!=NULL)
{
if(strcmp(p_mov->name,name)==0)//找到了
{
return p_mov;
}
p_mov=p_mov->next;
}
return NULL;//没有找到
}
六、链表节点的删除
void link_delete_num(STU **p_head,int num)
{
STU *pb,*pf;
pb=pf=*p_head;
if(*p_head==NULL)//链表为空，不用删
{
printf("链表为空，没有您要删的节点\n");
return;
}
while(pb->num!=num&&pb->next!=NULL)//循环找要删除的节点
{
pf=pb;
pb=pb->next;
}
if (pb->num==num)//找到了节点
{
if (pb==*p_head)//要删除的就是头节点
{
*p_head=pb->next;
}
else
{
pf->next=pb->next;
}
free(pb);
}
else
{
printf("没有找到您要删的节点\n");
}
}
任务：删除指定名字的节点
void link_delete_name(STU **p_head,char *name)
{
STU *pb,*pf;
pb=pf=*p_head;
if(*p_head==NULL)//链表为空，不用删
{
printf("链表为空，没有您要删的节点\n");
return;
}
while((strcmp(pb->name,name)!=0)&&pb->next!=NULL)//循环找要删除的节点
{
pf=pb;
pb=pb->next;
}
if ((strcmp(pb->name,name)==0))//找到了节点
{
if (pb==*p_head)//要删除的就是头节点
{
*p_head=pb->next;
}
else
{
pf->next=pb->next;
}
free(pb);
}
else
{
printf("没有找到您要删的节点\n");
}
}
七、向链表中插入一个节点
void link_insert_num(STU **p_head,STU *p_new)
{
STU *pb,*pf;
pb=pf=*p_head;
if(*p_head==NULL)//链表为空，直接插入到头结点后面就行
{
*p_head=p_new;
p_new->next=NULL;
return;
}
while((p_new->num>=pb->num)&&(pb->next!=NULL))
{
pf=pb;
pb=pb->next;
}
if (p_new->num<pb->num)//找到一个节点的num比新来的节点num大，插在pb的前面
{
if (pb==*p_head)//要删除的就是头节点
{
p_new->next=*p_head;
*p_head=p_new;
}
else
{
pf->next=p_new;
p_new->next=pb;
}
}
else//没有找到pb的num比p_new->num大的节点，直接插在最后
{
pb->next=p_new;
p_new->next=NULL;
}
}
八、链表的排序
如果链表无序，我们可编写一个排序函数，使得链表按照某成员变量排序
可利用冒泡排序，选择排序等方法
冒泡排序实现如下：
void link_order(STU **p_head)
{
STU *pb,*pf,temp;
pb=pf=*p_head;
if(*p_head==NULL)//链表为空，无需排序，提示
{
printf("链表为空，无需排序\n");
return;
}
if((*p_head)->next==NULL)//链表只有一个节点，也无需排序，提示
{
printf("只有一个节点，无需排序\n");
return;
}
while(pf->next!=NULL)//以pf指向的节点为基准节点
{
pb=pf->next;
while(pb!=NULL)
{
if(pf->num>pb->num)
{
temp=*pb;
*pb=*pf;
*pf=temp;//交换了数据域
temp.next=pb->next;
pb->next=pf->next;
pf->next=temp.next;//交换指针域
}
pb=pb->next;
}
pf=pf->next;
}
}
九、链表的逆序
STU *link_reverse(STU *head)
{
STU *pf,*pb,*r;
pf=head;
pb=pf->next;
while(pb!=NULL)
{
r=pb->next;
pb->next=pf;
pf=pb;
pb=r;
}
head->next=NULL;
head=pf;
return head;
}
十、单向循环链表
单向循环链表是另一种形式的链式存储结构。它的特点是单链表中最后一个结点的指针域指向头结点。
循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。
①单向循环链表的创建
void crclink_creat_head(STU **p_head,STU *p_new)
{
STU *p_mov=*p_head;
if(*p_head==NULL)//第一次加入链表为空时，p_head直接将p_new加入到链表中
{
*p_head=p_new;
p_new->next=*p_head;
}
else//第二次及以后加入链表时，先要找到链表尾部，然后再加入p_new到尾部
{
while(p_mov->next!=*p_head)
{
p_mov=p_mov->next;//找到原链表的最后一个节点
}
p_mov->next=p_new;//将新申请的节点加入链表
p_new->next=*p_head;
}
}
②单向循环链表的遍历
void crclink_print(STU *head)
{
STU *p_mov=head;
if (head==NULL)
{
return;
}
while(p_mov->next!=head)
{
printf("学号=%d、分数=%d、名字=%s\n",p_mov->num,p_mov->score,p_mov->name);
p_mov=p_mov->next;
}
printf("学号=%d、分数=%d、名字=%s\n",p_mov->num,p_mov->score,p_mov->name);
}
十一、双向链表
单链表有缺陷？？
单链表找后继节点容易，但无法找前驱节点
①定义双向链表
typedef struct student
{
int num;
int score;
char name[20];//数据域
struct student *next;//后继节点指针域
struct student *front;//前驱节点指针域
}STU;
②创建双向链表
void double_link_creat_head(STU **p_head,STU *p_new)
{
STU *p_mov=*p_head;
if(*p_head==NULL)//第一次加入链表为空时，p_head直接将p_new加入到链表中
{
*p_head=p_new;
p_new->next=NULL;
p_new->front=NULL;
}
else//第二次及以后加入链表时，先要找到链表尾部，然后再加入p_new到尾部
{
while(p_mov->next!=NULL)
{
p_mov=p_mov->next;//找到原链表的最后一个节点
}
p_mov->next=p_new;//将新申请的节点加入链表
p_new->next=NULL;
p_new->front=p_mov;
}
}
③双向链表的遍历
void double_link_print(STU *head)
{
STU *p_mov=head;
if(head==NULL)
{
return;
}
while(p_mov->next!=NULL)
{
printf("学号=%d、分数=%d、名字=%s\n",p_mov->num,p_mov->score,p_mov->name);
p_mov=p_mov->next;
}
printf("学号=%d、分数=%d、名字=%s\n",p_mov->num,p_mov->score,p_mov->name);
printf("=====================\n");
while(p_mov!=NULL)
{
printf("学号=%d、分数=%d、名字=%s\n",p_mov->num,p_mov->score,p_mov->name);
p_mov=p_mov->front;
}
}
④双向链表的删除
void double_link_delete_num(STU **p_head,int num)
{
STU *pb,*pf;
pb=pf=*p_head;
if(*p_head==NULL)//链表为空，不用删
{
printf("链表为空，没有您要删的节点\n");
return;
}
while(pb->num!=num&&pb->next!=NULL)//循环找要删除的节点
{
pf=pb;
pb=pb->next;
}
if (pb->num==num)//找到了节点
{
if (pb==*p_head)//要删除的就是头节点
{
if ((*p_head)->next==NULL)//只有一个节点
{
*p_head=pb->next;
}
else//多个节点，除了删除该节点，另外要使新的头结点的前驱为空
{
*p_head=pb->next;
(*p_head)->front=NULL;
}
}
else//要删除的是其他节点
{
if (pb->next==NULL)//删除的是尾节点
{
pf=pb->front;
pf->next=NULL;
}
else//删除的是中间节点
{
pf=pb->front;//找到前驱节点
pf->next=pb->next;
(pb->next)->front=pf;
}
}
free(pb);
}
else
{
printf("没有找到您要删的节点\n");
}
}
⑤双向链表的插入
void double_link_insert_num(STU **p_head,STU *p_new)
{
STU *pb,*pf;
pb=pf=*p_head;
if(*p_head==NULL)//链表为空，直接插入到头结点后面就行
{
*p_head=p_new;
p_new->next=NULL;
p_new->front=NULL;
return;
}
while((p_new->num>=pb->num)&&(pb->next!=NULL))
{
pb=pb->next;
}
if (p_new->num<pb->num)//找到一个节点的num比新来的节点num大，插在pb的前面
{
if (pb==*p_head)//要插入的位置就在头节点之前
{
p_new->next=*p_head;
(*p_head)->front=p_new;
p_new->front=NULL;
*p_head=p_new;
}
else
{
pf=pb->front;//得到原来的前驱
pf->next=p_new;
pb->front=p_new;
p_new->front=pf;
p_new->next=pb;
}
}
else//没有找到pb的num比p_new->num大的节点，直接插在最后
{
pb->next=p_new;
p_new->front=pb;
p_new->next=NULL;
}
}
