赞
踩
博客主页:博客主页
欢迎大家点赞收藏关注留言,如有错误,敬请指正
共同学习,一起进步。
链表是一种物理存储上非连续,数据元素的逻辑顺序通过链表中的指针链接次序,实现的一种线性存储结构。
链表由一系列节点(链表中每一个元素称为节点)组成,节点在运行时动态生成(malloc),每个节点包括两个部分:
一个是存储数据元素的数据域
另一个是存储下一个节点地址的指针域
链表由一个个节点构成,每个节点一般采用结构体的形式组织,例如:
typedef struct student{
int num;
char name[20];
struct student *next;
}STU;
链表节点分为两个域
数据域:存放各种实际的数据,如:num、score等
指针域:存放下一节点的首地址,如:next等
创建 增 删 改 查
第一步:创建一个结点
第二步:创建第二个结点,并放在第一个结点的后面(第一个结点指针域保存第二个结点地址)
第三步:再次创建结点,找到原本链表中最后一个结点,接着将最后一个结点的指针域保存新节点的地址,以此类推。
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *next; }STU; void link_creat_head(STU **p_head,STU *p_new) { STU *p_mov = *p_head; if(*p_head == NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->next=NULL; } else //第二次及以后加入链表 { while(p_mov->next!=NULL) { p_mov=p_mov->next; //找到原有链表的最后一个节点 } p_mov->next = p_new; //将新申请的节点加入链表 p_new->next = NULL; } } int main() { STU *head = NULL,*p_new = NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i = 0; i < num;i++) { p_new = (STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); link_creat_head(&head,p_new); //将新节点加入链表 } }
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *next; }STU; void link_creat_head(STU **p_head,STU *p_new) { STU *p_mov = *p_head; if(*p_head == NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->next=NULL; } else //第二次及以后加入链表 { 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改变原本链表 p_mov = head; //当指针保存最后一个结点的指针域为NULL时,循环结束 while(p_mov!=NULL) { //先打印当前指针保存结点的指针域 printf("num=%d score=%d name:%s\n",p_mov->num,\ p_mov->score,p_mov->name); //指针后移,保存下一个结点的地址 p_mov = p_mov->next; } } int main() { STU *head = NULL,*p_new = NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i = 0; i < num;i++) { p_new = (STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); link_creat_head(&head,p_new); //将新节点加入链表 } link_print(head); }
执行结果:
重新定义一个指针q保存p指向结点的地址,然后p后移保存下一个结点的地址,然后释放q对应节点,以此类推,知道p位NULL
//链表的释放 void link_free(STU **p_head) { //定义一个指针变量保存头结点的地址 STU *pb=*p_head; while(*p_head!=NULL) { //先保存p_head指向的结点的地址 pb=*p_head; //p_head保存下一个结点地址 *p_head=(*p_head)->next; //释放结点并防止野指针 free(pb); pb = NULL; } }
先对比第一个结点的数据域是否是想要的数据,如果是直接返回,如果不是则继续查找下一个结点,如果达到最后一个结点都没有匹配的数据,则说明查找的数据不存在
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *next; }STU; void link_creat_head(STU **p_head,STU *p_new) { STU *p_mov = *p_head; if(*p_head == NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->next=NULL; } else //第二次及以后加入链表 { 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改变原本链表 p_mov = head; //当指针保存最后一个结点的指针域为NULL时,循环结束 while(p_mov!=NULL) { //先打印当前指针保存结点的指针域 printf("num=%d score=%d name:%s\n",p_mov->num,\ p_mov->score,p_mov->name); //指针后移,保存下一个结点的地址 p_mov = p_mov->next; } } //链表的释放 void link_free(STU **p_head) { //定义一个指针变量保存头结点的地址 STU *pb=*p_head; while(*p_head!=NULL) { //先保存p_head指向的结点的地址 pb=*p_head; //p_head保存下一个结点地址 *p_head=(*p_head)->next; //释放结点并防止野指针 free(pb); pb = NULL; } } //链表的查找 //按照学号查找 STU * link_search_num(STU *head,int num) { STU *p_mov; //定义的指针变量保存第一个结点的地址 p_mov=head; //当没有到达最后一个结点的指针域时循环继续 while(p_mov!=NULL) { //如果找到是当前结点的数据,则返回当前结点的地址 if(p_mov->num == num)//找到了 { return p_mov; } //如果没有找到,则继续对比下一个结点的指针域 p_mov=p_mov->next; } //当循环结束的时候还没有找到,说明要查找的数据不存在,返回NULL进行标识 return NULL;//没有找到 } //按照姓名查找 STU * link_search_name(STU *head,char *name) { STU *p_mov; p_mov=head; while(p_mov!=NULL) { if(strcmp(p_mov->name,name)==0)//找到了 { return p_mov; } p_mov=p_mov->next; } return NULL;//没有找到 } int main() { STU *head = NULL,*p_new = NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i = 0; i < num;i++) { p_new = (STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); link_creat_head(&head,p_new); //将新节点加入链表 } link_print(head); //查学号 #if 1 STU *pb; while(1) { printf("请输入您要查找学生的学号\n"); scanf("%d",&num); pb=link_search_num(head,num); if(pb!=NULL)//找到了 { printf("找到了 num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); } else { printf("没有找到您要查找的节点\n"); } } #endif //查姓名 #if 0 char name[32] = ""; while(1) { printf("请输入您要查找学生的姓名\n"); scanf("%s",name); pb=link_search_name(head,name); if(pb!=NULL)//找到了 { printf("找到了 num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); } else { printf("没有找到您要查找的节点\n"); } } #endif link_free(&head); }
执行结果:
如果链表位空,不需要删除
如果要删除的是第一个结点,则需要保存链表首地址的指针保存第一个结点的下一个结点的地址
如果删除的是中间结点,则找到中间结点的前一个结点,让前一个结点的指针域保存这个结点的后一个结点的地址
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *next; }STU; void link_creat_head(STU **p_head,STU *p_new) { STU *p_mov = *p_head; if(*p_head == NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->next=NULL; } else //第二次及以后加入链表 { 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改变原本链表 p_mov = head; //当指针保存最后一个结点的指针域为NULL时,循环结束 while(p_mov!=NULL) { //先打印当前指针保存结点的指针域 printf("num=%d score=%d name:%s\n",p_mov->num,\ p_mov->score,p_mov->name); //指针后移,保存下一个结点的地址 p_mov = p_mov->next; } } //链表的释放 void link_free(STU **p_head) { //定义一个指针变量保存头结点的地址 STU *pb=*p_head; while(*p_head!=NULL) { //先保存p_head指向的结点的地址 pb=*p_head; //p_head保存下一个结点地址 *p_head=(*p_head)->next; //释放结点并防止野指针 free(pb); pb = NULL; } } //链表结点的删除 void link_delete_num(STU **p_head,int num) { STU *pb,*pf; pb=pf=*p_head; if(*p_head == NULL)//链表为空,不用删 { printf("链表为空,没有您要删的节点");\ return ; } while(pb->num != num && pb->next !=NULL)//循环找,要删除的节点 { pf=pb; pb=pb->next; } if(pb->num == num)//找到了一个节点的num和num相同 { if(pb == *p_head)//要删除的节点是头节点 { //让保存头结点的指针保存后一个结点的地址 *p_head = pb->next; } else { //前一个结点的指针域保存要删除的后一个结点的地址 pf->next = pb->next; } //释放空间 free(pb); pb = NULL; } else//没有找到 { printf("没有您要删除的节点\n"); } } int main() { STU *head = NULL,*p_new = NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i = 0; i < num;i++) { p_new = (STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); link_creat_head(&head,p_new); //将新节点加入链表 } link_print(head); printf("请输入您要删除的节点的学号\n"); scanf("%d",&num); link_delete_num(&head,num); link_print(head); link_free(&head); }
执行结果:
链表中插入一个结点,按照原本链表的顺序插入,找到合适的位置
情况(按照从小到大):
如果链表没有结点,则新插入的就是第一个结点
如果新插入的结点的数值最小,则作为头结点
如果新插入的数值在中间位置,则找到前一个,然后插入到他们中间
如果新插入的结点的数值最大,则插入到最后
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *next; }STU; void link_creat_head(STU **p_head,STU *p_new) { STU *p_mov = *p_head; if(*p_head == NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->next=NULL; } else //第二次及以后加入链表 { 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改变原本链表 p_mov = head; //当指针保存最后一个结点的指针域为NULL时,循环结束 while(p_mov!=NULL) { //先打印当前指针保存结点的指针域 printf("num=%d score=%d name:%s\n",p_mov->num,\ p_mov->score,p_mov->name); //指针后移,保存下一个结点的地址 p_mov = p_mov->next; } } //链表的释放 void link_free(STU **p_head) { //定义一个指针变量保存头结点的地址 STU *pb=*p_head; while(*p_head!=NULL) { //先保存p_head指向的结点的地址 pb=*p_head; //p_head保存下一个结点地址 *p_head=(*p_head)->next; //释放结点并防止野指针 free(pb); pb = NULL; } } //链表的插入:按照学号的顺序插入 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; } } int main() { STU *head = NULL,*p_new = NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i = 0; i < num;i++) { p_new = (STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); link_creat_head(&head,p_new); //将新节点加入链表 } link_print(head); while(1) { printf("请输入您要插入的节点的 num score name\n"); p_new=(STU*)malloc(sizeof(STU));//申请一个新节点 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); link_insert_num(&head,p_new); link_print(head); } link_free(&head); }
执行结果:
如果链表为空,不需要排序
如果链表中只有一个结点,不需要排序
先将第一个结点与后面的所有结点一次对比数据域,只要比第一个结点的数据域小的,则交换位置,
交换之后,那新的第一个结点的数据域再与下一个结点再次比较,如果比他小,再次交换,以此类推
第一个结点确定,接下来再与第二个结点(后面所有的结点)对比,知道最后一个结点也确定
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *next; }STU; void link_creat_head(STU **p_head,STU *p_new) { STU *p_mov = *p_head; if(*p_head == NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->next=NULL; } else //第二次及以后加入链表 { 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改变原本链表 p_mov = head; //当指针保存最后一个结点的指针域为NULL时,循环结束 while(p_mov!=NULL) { //先打印当前指针保存结点的指针域 printf("num=%d score=%d name:%s\n",p_mov->num,\ p_mov->score,p_mov->name); //指针后移,保存下一个结点的地址 p_mov = p_mov->next; } } //链表的释放 void link_free(STU **p_head) { //定义一个指针变量保存头结点的地址 STU *pb=*p_head; while(*p_head!=NULL) { //先保存p_head指向的结点的地址 pb=*p_head; //p_head保存下一个结点地址 *p_head=(*p_head)->next; //释放结点并防止野指针 free(pb); pb = NULL; } } //链表的排序 void link_order(STU *head) { STU *pb,*pf,temp; pf=head; if(head==NULL) { printf("链表为空,不用排序\n"); return ; } if(head->next ==NULL) { printf("只有一个节点,不用排序\n"); return ; } while(pf->next !=NULL)//以pf指向的节点为基准节点, { pb=pf->next;//pb从基准元素的下个元素开始 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; } } int main() { STU *head = NULL,*p_new = NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i = 0; i < num;i++) { p_new = (STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); link_creat_head(&head,p_new); //将新节点加入链表 } link_print(head); printf("***************************\n"); link_order(head); link_print(head); link_free(&head); }
执行结果:
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *next; }STU; void link_creat_head(STU **p_head,STU *p_new) { STU *p_mov = *p_head; if(*p_head == NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->next=NULL; } else //第二次及以后加入链表 { 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改变原本链表 p_mov = head; //当指针保存最后一个结点的指针域为NULL时,循环结束 while(p_mov!=NULL) { //先打印当前指针保存结点的指针域 printf("num=%d score=%d name:%s\n",p_mov->num,\ p_mov->score,p_mov->name); //指针后移,保存下一个结点的地址 p_mov = p_mov->next; } } //链表的释放 void link_free(STU **p_head) { //定义一个指针变量保存头结点的地址 STU *pb=*p_head; while(*p_head!=NULL) { //先保存p_head指向的结点的地址 pb=*p_head; //p_head保存下一个结点地址 *p_head=(*p_head)->next; //释放结点并防止野指针 free(pb); pb = NULL; } } //链表逆序 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; } int main() { STU *head = NULL,*p_new = NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i = 0; i < num;i++) { p_new = (STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); link_creat_head(&head,p_new); //将新节点加入链表 } link_print(head); printf("***********************\n"); head = link_reverse(head); link_print(head); link_free(&head); }
执行结果:
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *front; //保存上一个结点的地址 struct student *next; //保存下一个结点的地址 }STU; void double_link_creat_head(STU **p_head,STU *p_new) { STU *p_mov=*p_head; if(*p_head==NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->front = NULL; p_new->next = NULL; } else //第二次及以后加入链表 { while(p_mov->next!=NULL) { p_mov=p_mov->next; //找到原有链表的最后一个节点 } p_mov->next = p_new; //将新申请的节点加入链表 p_new->front = p_mov; p_new->next = NULL; } } void double_link_print(STU *head) { STU *pb; pb=head; while(pb->next!=NULL) { printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); pb=pb->next; } printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); printf("***********************\n"); while(pb!=NULL) { printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); pb=pb->front; } } int main() { STU *head=NULL,*p_new=NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i=0;i<num;i++) { p_new=(STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); double_link_creat_head(&head,p_new); //将新节点加入链表 } double_link_print(head); }
执行结果:
如果链表为空,则不需要删除
如果删除第一个结点,则保存链表首地址的指针保存后一个结点的地址,并且让这个结点的front保存NULL
如果删除最后一个结点,只需要让最后一个结点的前一个结点的next保存NULL即可
如果删除中间结点,则让中间结点的前后两个结点的指针域分别保存对方的地址即可
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *front; //保存上一个结点的地址 struct student *next; //保存下一个结点的地址 }STU; void double_link_creat_head(STU **p_head,STU *p_new) { STU *p_mov=*p_head; if(*p_head==NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->front = NULL; p_new->next = NULL; } else //第二次及以后加入链表 { while(p_mov->next!=NULL) { p_mov=p_mov->next; //找到原有链表的最后一个节点 } p_mov->next = p_new; //将新申请的节点加入链表 p_new->front = p_mov; p_new->next = NULL; } } void double_link_print(STU *head) { STU *pb; pb=head; while(pb->next!=NULL) { printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); pb=pb->next; } printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); printf("***********************\n"); while(pb!=NULL) { printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); pb=pb->front; } } //双向链表的删除 void double_link_delete_num(STU **p_head,int num) { STU *pb,*pf; pb=*p_head; if(*p_head==NULL)//链表为空,不需要删除 { printf("链表为空,没有您要删除的节点\n"); return ; } while((pb->num != num) && (pb->next != NULL) ) { pb=pb->next; } if(pb->num == num)//找到了一个节点的num和num相同,删除pb指向的节点 { if(pb == *p_head)//找到的节点是头节点 { if((*p_head)->next==NULL)//只有一个节点的情况 { *p_head=pb->next; } else//有多个节点的情况 { *p_head = pb->next;//main函数中的head指向下个节点 (*p_head)->front=NULL; } } else//要删的节点是其他节点 { if(pb->next!=NULL)//删除中间节点 { pf=pb->front;//让pf指向找到的节点的前一个节点 pf->next=pb->next; //前一个结点的next保存后一个结点的地址 (pb->next)->front=pf; //后一个结点的front保存前一个结点的地址 } else//删除尾节点 { pf=pb->front; pf->next=NULL; } } free(pb);//释放找到的节点 } else//没找到 { printf("没有您要删除的节点\n"); } } int main() { STU *head=NULL,*p_new=NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i=0;i<num;i++) { p_new=(STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); double_link_creat_head(&head,p_new); //将新节点加入链表 } double_link_print(head); printf("请输入您要删除的节点的num\n"); scanf("%d",&num); double_link_delete_num(&head,num); double_link_print(head); }
执行结果:
#include <stdio.h> #include <stdlib.h> //定义结点结构体 typedef struct student { //数据域 int num; //学号 int score; //分数 char name[20]; //姓名 //指针域 struct student *front; //保存上一个结点的地址 struct student *next; //保存下一个结点的地址 }STU; void double_link_creat_head(STU **p_head,STU *p_new) { STU *p_mov=*p_head; if(*p_head==NULL) //当第一次加入链表为空时,head执行p_new { *p_head = p_new; p_new->front = NULL; p_new->next = NULL; } else //第二次及以后加入链表 { while(p_mov->next!=NULL) { p_mov=p_mov->next; //找到原有链表的最后一个节点 } p_mov->next = p_new; //将新申请的节点加入链表 p_new->front = p_mov; p_new->next = NULL; } } void double_link_print(STU *head) { STU *pb; pb=head; while(pb->next!=NULL) { printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); pb=pb->next; } printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); printf("***********************\n"); while(pb!=NULL) { printf("num=%d score=%d name:%s\n",pb->num,pb->score,pb->name); pb=pb->front; } } //双向链表的插入 void double_link_insert_num(STU **p_head,STU *p_new) { STU *pb,*pf; pb=*p_head; if(*p_head == NULL)//链表为空,新来的节点就是头节点 { *p_head=p_new; p_new->front=NULL; p_new->next=NULL; return ; } while((p_new->num >= pb->num) && (pb->next!=NULL) ) { pb=pb->next ; } if(p_new->num < pb->num)//找到了一个pb的num比新来的节点的num大,插在pb前边 { if(pb==*p_head)//找到的节点是头节点,插在头节点的前边 { p_new->next=*p_head; //新插入的结点的next保存之前头结点的地址 (*p_head)->front=p_new; //之前头结点的front保存新插入的结点的地址 p_new->front=NULL; //新插入的结点的front保存NULL *p_head=p_new; //让原本保存链表首地址的指针保存新插入结点的地址 } else { pf=pb->front;//pf指向 找到节点的前一个节点 p_new->next=pb; p_new->front=pf; pf->next=p_new; pb->front=p_new; } } else//所有pb指向节点的num都比p_new指向的节点的num小,插在最后 { pb->next=p_new; p_new->front=pb; p_new->next=NULL; } } int main() { STU *head=NULL,*p_new=NULL; int num,i; printf("请输入链表初始个数:\n"); scanf("%d",&num); for(i=0;i<num;i++) { p_new=(STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入学号、分数、名字:\n"); //给新节点赋值 scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); double_link_creat_head(&head,p_new); //将新节点加入链表 } double_link_print(head); printf("************************\n"); while(1) { p_new=(STU*)malloc(sizeof(STU));//申请一个新节点 printf("请输入您要插入的节点的num score name\n"); scanf("%d %d %s",&p_new->num,&p_new->score,p_new->name); double_link_insert_num(&head,p_new); double_link_print(head); } }
执行结果:
本篇主要记录链表的基础知识。
博客主页博客主页
欢迎大家点赞收藏关注留言。
如有错误,敬请指正。
注:本篇来自千峰教育公开课程,学习笔记。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。