链表
因为数组必须事先确定大小，不能实现动态申请、释放。而使用malloc动态内存分配也无法实现，malloc申请的空间，不能实现局部申请和释放，那么这种情况下，链表这种数据结构就出现了。
定义：
链表是一种物理存储上非连续，数据元素的逻辑顺序通过链表中的指针链接次序，实现的一种线性存储结构
特点：
链表由一系列节点(链表中每个元素称为节点)组成，节点在运行时动态生成malloc，每个节点包含两个部分
- 存储数据元素的数据域
- 存储下一个节点地址的指针域
链表的构成
链表由一个个节点构成，每个节点一般采用结构体的形式组织
typedef struct student{
int num;
char name[20];
struct student *next;
}STU;
数据域：存放各种实际的数据，如：num,score等
指针域：存放下一个节点的首地址，如:next
链表的操作
创建
typedef struct student{
//数据域
int num;
char name[20];
//指针域
struct student *next;
}STU;
void link_creat_head(STU **p_head,STU *p_new){
STU *p_mov=*p_head;
//当第一次加入链表为空时，head执行p_new
if(*p_head==NULL){
*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);
}
}
遍历
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_find(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;
}
return NULL;//没有找到
}
删除
void link_delete_num(STU **p_head,int num){
STU *pb,*pf;
pb=pf=*p_head;
if(*p_head==NULL){
//链表为空不需要删除
return ;
}
//循环找，要删除的节点
while(pb->num!=num&&pb->next!=NULL){
pf=pb;
pb=pb->next;
}
//找到了一个节点的num和num相同
if(pb->num==num){
if(pb==*p_head){
//要删除的节点是头节点
//让保存头节点的指针保存后一个节点的地址
*p_head=pb->next;
}else{
pf->next=pb->next;
}
free(pb);
pb=NULL;
}else{//没有找到
printf("没有找到删除的节点\n");
}
}
//调用
link_delete_num(&head,num);
插入节点
//按照学号的顺序插入
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大
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 *head){
STU *pd,*pf,temp;
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>pd->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;
}
}
逆序
//每次只移动一个，例如 1 3 5，以1为基准
//第一次 3 1 5
//第二次 5 3 1
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;
}
双向链表
1.jpg
2.jpg
创建
3.jpg
#include <stdio.h>
typedef struct student{
int num;
int socre;
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){
//第一次
*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;
}
}
int main(int argc, char *argv[])
{
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);
}
return 0;
}
删除
- 如果链表为空，则不需要删除
- 如果删除第一个节点，则保存链表首地址的指针保存后一个节点的地址，并且让这个节点的front保存NULL
- 如果删除最后一个节点，只需要让最后一个节点的前一个节点的next保存NULL即可
- 如果删除中间节点，则让中间节点的前后两个节点的指针域分别保存对方的地址即可
void double_link_delete_num(STU **p_head,int num){
STU *pb,*pf;
pb=*p_head;
if(*p_head==NULL){
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;
(pb->next)->front=pf;
}else{
//删除尾节点
pf=pb->front;
pf->next=NULL;
}
}
}else{
//没找到
}
}
插入
按照顺序插入节点
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大
if(pb==*p_head){
//找到是头节点，插在头节点的前边
//新插入的节点的next保存之前头节点的地址
p_new->next=*p_head;
//之前头节点的front保存新插入的节点的地址
(*p_head)->front=p_new;
//新插入的节点的front保存NULL
p_new->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;
}
}
网友评论