链表（超详细--包教包会）

对单链表进行查找的思路为： 对单链表的结点依次扫描， 检测其数据域是否是我们所要查好的值， 若是返回该结点的指针， 否则返回 NULL。

因为在单链表的链域中包含了后继结点的存储地址， 所以当我们实现的时候， 只要知道该单链表的头指针，

即可依次对每个结点的数据域进行检测

例子：通过学号查找节点的信息

//查找链表的函数， 
//phead 指针是链表的表头指针， 
//name指针是要查找的人的姓名
//结点结构指针类型的函数（ 返回找到的结点指针）
struct STU * search_link(struct STU *phead,char *name)
{
   	//判断链表是否为空；
	//不为空通过比较找到此人信息
	//查无此人；
   struct STU *p; /*当前指针， 指向要与所查找的姓名比较的结点*/
   char *y; /*保存结点数据域内姓名的指针*/
   p= phead->pnext ;//后移一下节点
   while(p!=NULL) //节点不为空
   {
y=p->name;   // 相当于一个地址，赋给了指针;
    //（ name、 y 为指向的存储单元的值） /*把数据域里的姓名与
    //所要查找的姓名比较， 若相同则返回 0， 即条件成立*/
if(strcmp(y,name)==NULL) //输入的和原来的名字进行比较
{
	  printf("查到此人信息为：");
	  printf("%d %s\n",ph->num,ph->name);
  return(p); //返回与所要查找结点的地址
}
else 
  p=p->pnext;
   }
  if(p==NULL) //节点为空
    printf("没有查找到该数据!\n");
}

九、删除节点

 

例子：通过学生的学号删除节点

/*
==========================
 功能：删除指定节点
 phead 指针是链表的表头指针， 
 num 指针是要查找的人的学号
 返回：指向链表表头的指针
==========================
*/
struct STU * delet_link(struct STU *phead,int num)
{
	struct STU *ph=phead,*pf;
	if(ph==NULL)   //空链表
	{
		printf("此链表为空链表！\n");
	}
	else
	{
//ph指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下找
		while(ph->pnext!=NULL&&ph->num!=num)
		{
			pf=ph;        //保存当前节点的地址
			ph=ph->pnext;  //后移一个节点
		}
		if(ph->num==num)  //找到了
		{
			if(ph==phead)//如果要删除的节点是第一个节点
			{
//头指针指向第一个节点的后一个节点，也就是第二个节点。这样第一个节点就//不在链表中，即删除
				phead=ph->pnext;
			}
			else if(ph->pnext==NULL) //下个节点为空
			{
				pf->pnext =NULL;
			}
//如果是其它节点，则让原来指向当前节点的指针，指向它的下一个节点，完成//删除
			else
			{
				pf->pnext=ph->pnext;
			}
			printf("找到此人\n");
			free(ph);           //释放当前节点
			printf("删除成功!\n");	
		}
		else
		{
			printf("查无此人\n");
			ph=NULL;
		}
	}
	return phead;
}
int main()
{
	int n,num;
	struct STU *phead; //phead用来存放链表头结点的地址
	printf("输入节点个数：");
	scanf("%d",&n);
	phead=Create_link(n);  //创建链表，把链表的头结点地址给phead
    //这样phead就指向一个链表了，然后就可以把整个链表给确定了
	pri_link(phead);       //输出链表
	printf("输入要删除的学号：");
	scanf("%d",&num);
	phead=delet_link(phead,num); //删除结点
	pri_link(phead);         //输出结点
}

 例子：通过学生的姓名删除节点

/*
==========================
 功能：删除指定节点
 phead 指针是链表的表头指针， 
 name指针是要查找的人的学号
 返回：指向链表表头的指针
==========================
*/
struct STU * delet_link(struct STU *phead,char* name)
{
	struct STU *ph=phead,*pf;
	if(ph==NULL)   //空链表
	{
		printf("此链表为空链表！\n");
	}
	else
	{
//ph指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下找
		while(ph->pnext!=NULL&&strcmp(name,ph->name)!=0)
		{
			pf=ph;        //保存当前节点的地址
			ph=ph->pnext;  //后移一个节点
		}
		if(strcmp(name,ph->name)==0)  //找到了
		{
			if(ph==phead)//如果要删除的节点是第一个节点
			{
//头指针指向第一个节点的后一个节点，也就是第二个节点。这样第一个节点就//不在链表中，即删除
				phead=ph->pnext;
			}
			else if(ph->pnext==NULL) //下个节点为空
			{
				pf->pnext =NULL;
			}
//如果是其它节点，则让原来指向当前节点的指针，指向它的下一个节点，完成//删除
			else
			{
				pf->pnext=ph->pnext;
			}
			printf("找到此人\n");
			free(ph);           //释放当前节点
			printf("删除成功!\n");	
		}
		else
		{
			printf("查无此人\n");
			ph=NULL;
		}
	}
	return phead;
}
int main()
{
	int n,num;
	struct STU *phead; //phead用来存放链表头结点的地址
	printf("输入节点个数：");
	scanf("%d",&n);
	phead=Create_link(n);  //创建链表，把链表的头结点地址给phead
    //这样phead就指向一个链表了，然后就可以把整个链表给确定了
	pri_link(phead);       //输出链表
	printf("输入要删除的学号：");
	scanf("%d",&num);
	phead=delet_link(phead,num); //删除结点
	pri_link(phead);         //输出结点
}

十、插入节点

 

 

/*
==========================
 功能：插入指定节点的后面
 返回：指向链表表头的指针
==========================
*/
struct STU* insert_link(struct STU* phead)
{
	struct STU *ph,*pf,*p;
	ph=phead;
	p=(struct STU *)malloc(sizeof(struct STU));
	printf("输入插入的数据：");
	scanf("%d %s",&p->num,p->name);
	if(phead==NULL)
	{
		phead=p;     // 既是头结点，又是尾结点
		p->pnext ==NULL;  
	}
	else
	{
		while((p->num)>(ph->num)&&ph->pnext!=NULL)
		{
			pf=ph;        //保存当前节点的地址
			ph=ph->pnext;  //后移一个节点

		}
		if(ph==phead)//头节点插入
		{
			p->pnext=phead; // p->pnext 新插入的节点指向原来的头结点
			phead=p;//新插入的节点为新的头结点
		}
		else if(p->num<=ph->num)
		{
			pf->pnext=p;
			p->pnext=ph;
		}
		else
		{
			ph->pnext =p;
			p->pnext ==NULL;	
		}
	}
	return phead;
}

 十一、整体代码

#include<stdio.h>
#include<stdlib.h>

struct STU
{
	//数据域
	int num;
	char name[10];
	//指针域
	struct STU *pnext;//pnext指向下一个结点的指针
};
//p->pnext ;//p把指向结构体变量中的pnext成员本身
//函数声明
struct STU * Create_link(int n);
void pri_link(struct STU *phead);
struct STU * search_link(struct STU *phead,int num);
struct STU * delet_link(struct STU *phead,int num);
struct STU* insert_link(struct STU* phead);


int main()
{
	int n,num;
	struct STU *phead; //phead用来存放链表头结点的地址
	printf("输入节点个数：");
	scanf("%d",&n);
	phead=Create_link(n);  //创建链表，把链表的头结点地址给phead
    //这样phead就指向一个链表了，然后就可以把整个链表给确定了
	pri_link(phead);       //输出链表
	printf("输入要查找人的学号：");
	scanf("%d",&num);
	search_link(phead,num);    //查找结点
	printf("输入要删除的学号：");
	scanf("%d",&num);
	phead=delet_link(phead,num); //删除结点
	pri_link(phead);         //输出结点
	phead=insert_link(phead); //插入结点
	pri_link(phead);    //输出链表
	return 0;
}

/*
==========================
功能：创建n个节点的链表
返回：指向链表表头的指针
==========================
*/
struct STU * Create_link(int n)
{
	struct STU *phead,*p,*pf; // phead为头指针，p为后一结点的指针变量，
                          //pf为指向两相邻结点的前一结点的指针变量。
	int i;
	for(i=1;i<=n;i++)
	{
		printf("输入第%d个人的数据：",i);
       //分配了一个不存放有效数据的头结点
		p=(struct STU*)malloc(sizeof(struct STU));
		scanf("%d %s",&p->num,&p->name);
		if(i==1)    //只有一个结点
		{
			phead=p;  //节点总数是1，phead指向刚创建的节点p
			pf=p;
		}
		else
		{
			pf->pnext =p;   //指向下一个结点的首地址（新结点）
			pf=p;         //把p的地址留给pf,然后p产生新的结点
		}	
	}
	p->pnext=NULL;  //单向链表的最后一个节点要指向NULL
	return phead;    //返回创建链表的头指针
}


//输出链表中的数据
void pri_link(struct STU *phead)
{
	struct STU *ph=phead;    //phead->pnext等价于(*phead).pnext
	while(ph->pnext!=NULL)   //只要不是空链表，就输出链表中所有节点
	{                       //此时ph指向了第一个有效节点
		printf("%d  %s\n",ph->num,ph->name);//输出ph指向的数据域的数据
		ph=ph->pnext;  //移到下一个节点,不能写ph++
	}
	printf("%d  %s\n",ph->num,ph->name);
}


//通过学号查找学生的信息
struct STU * search_link(struct STU *phead,int num)
{
   	//判断链表是否为空；
	//不为空通过比较找到此人信息
	//查无此人；
  struct STU *ph=phead;
	if(ph==NULL) //空链表
	{
		printf("此链表为空链表！\n");
	}
	else
	{
//ph指向的节点不是所要查找的，并且它不是最后一个节点，就继续往下找
		while(ph->pnext!=NULL&&ph->num!=num)
		{
			ph=ph->pnext; //后移一个节点
		}
		if(ph->num==num) //找到了
		{
			printf("查到此人信息为：");
			printf("%d %s\n",ph->num,ph->name);
		}
		else
		{
			printf("查无此人\n");
			ph=NULL;
		}
	}
	return ph;
}


//删除节点

struct STU * delet_link(struct STU *phead,int num)
{
	struct STU *ph,*pf;
	ph=phead;
	if(ph==NULL)   //空链表
	{
		printf("此链表为空链表！\n");
		goto end;
	}
	else
	{
		//ph指向的节点不是所要删除的，并且它不是最后一个节点，就继续往下找
		while((ph->num!=num)&&(ph->pnext!=NULL))
		{
			pf=ph;        //保存当前节点的地址
			ph=ph->pnext;  //后移一个节点
		}
		if(ph->num==num)  //找到了
		{
			if(ph==phead)//如果要删除的节点是第一个节点
			{
				//头指针指向第一个节点的后一个节点，也就是第二个节点。
				//这样第一个节点就不在链表中，即删除
				phead=ph->pnext;
			}
			else if(ph->pnext==NULL) //最后一个结点
			{
				pf->pnext =NULL;
			}
			
			else
			{
				//如果是其它节点，则让原来指向当前节点的指针，
				//指向它的下一个节点，完成删除
				pf->pnext=ph->pnext; 
			}
			printf("找到此人\n");
			free(ph);           //释放当前节点,这上步不能少
			printf("删除成功!\n");	
		}
		else
		{
			printf("查无此人\n");
			ph=NULL;
		}
	}
end:
	return phead;
}

//插入节点
struct STU* insert_link(struct STU* phead)
{
	struct STU *ph,*pf,*p;
	ph=phead;
	p=(struct STU *)malloc(sizeof(struct STU));
	printf("输入插入的数据：");
	scanf("%d %s",&p->num,p->name);
	if(phead==NULL)  //头链表为空链表时
	{
		phead=p;
		p->pnext ==NULL;
	}
	else
	{
		while((p->num)>(ph->num)&&(ph->pnext!=NULL)) //查询p->num是否<=链表中某个结节
		{
			
			pf=ph;
			ph=ph->pnext;
		}
		if(ph==phead)		//在链表首插入
		{
			p->pnext=phead;
			phead=p;
		}
		else if((p->num)<=(ph->num)) //判断是否有符合条件的结点
		{
			pf->pnext=p;			//在两个结点中间插入结点
			p->pnext=ph;
		}
		else	//插入在尾结点
		{
			ph->pnext =p;
			p->pnext ==NULL;	
		}
	}
	return phead;
}