单链表的基本操作！

心已赠人 2022-05-15 11:05 245阅读 0赞

假设以学生信息结构体作为链表节点，其中结构体成员包括三个元素，学号，成绩和一个结构体指针。前两个成员是节点存储的本身内容，而最后一个成员，定义为指向结构体的指针，是用来指向下一个节点的，因为只有指向下一个节点，才可以连成一串，形成所谓的链表。总的来说，链表中的每一个节点，应该包括两部分，即数据+指向下一节点的指针。

结构体如下：

struct student

\{long num;

float score;

struct student \* next;\};//最后一个成员就是指向下一个节点的指针

在编程前，我们必须要有一个整体的框架思路才能写出代码，所以，先走一遍逻辑思路吧！

##     1.建立链表 ##

建立链表是最简单的部分，其中主要重要一个void \* malloc(unsigned int size)函数，用来为节点开辟一个容量为size的区域。建立表的时候可以不断的去malloc，则不断的增加节点。片段代码如下：

#include <stdio.h>
    #include <malloc.h>
    #define len sizeof(struct student)
    #define  NULL 0
    struct student
    {
    	long int num;
    	float score;
    	struct student * next;
    };
    int n; //定义全局n，表示节点数
    /*****创建链表子函数开始*******/
    struct student * creat(void)
    {
    	n=0;
    	struct student *p1,*p2,*head;
    	head=NULL;//初始化头结点指针，使其指向空，表示当前链表没有节点
    	p1=p2=(struct student *)malloc(len);//开辟一个新节点区域，使得P1P2均指向该区域的首地址
    	scanf("%ld,%f",&p1->num,&p1->score);
    	while((p1->num)!=0)
    	{
    		n=n+1;//节点数加1
    		if(n==1)
    			head=p1;
    		else
    			p2->next=p1;//使得p2的next指针指向新区域的首地址（因为此时p1已经是新区域的首地址了）
    		p2=p1;          //下面p1就要指向新区域了，临走之前必须让p2来记录一下自己
    		p1=(struct student *)malloc(len);//在while循环中不断的创造新节点
    		scanf("%ld,%f",&p1->num,&p1->score);
    	}
    	p2->next=NULL;      //尾部指针为空，说明是表尾
    	return(head);
    }

可能对上面定义的三个指针有疑问.即head,\*p1,\*p2，下面分别介绍其作用：

作为一个链表必须要有头指针，即指向链表的首地址，它就是head,而为了访问下一结点，必须要另一个指针去移动，它就是p1,有人可能会说，那么定义这两个指针似乎不就够了么，还定义p3干什么。其实不然，试想想，p1是访问下一结点的，它会不断的往后走，去访问满足条件的节点（比如要插入一个节点，那么p1肯定要去找寻比这个要插入节点大，和小的值，从而找到具体的位置进行插入），而在这个过程中，并没有谁去记录p1走过的路程。例如，现在要插入一个新节点p0，p1去找呀找，p1找到了第二个节点，发现第二个节点比p0里的值小，于是它就朝向下一个节点，咦，发现第三个节点的值比p0所指值大（这里默认排序是由小到大），那么p1就找到了p0应该插入的地方，这时就可以让p1（第三个节点）去和p0（要插入的节点）连接。但是问题出来了，p0还需要和左边的第二个节点连接呀，这时候没有哪个指针是指向第二个节点的（更不可能让p1去退一步），这就需要p2去时刻跟在p1后面去记录它。

举个最通俗的例子，如果有10个小朋友手拉手按身高由小到大站在一起，现在来了一个新同学，他的个子经过比对，应该插入到第二个同学和第三个同学之间。那么，应该让第二个和第三个同学的手松开，然后第二个同学拉住新来的同学，第三个同学也拉着新来的同学，这样才可以在不影响队伍的情况下重新组建链表。这里head指向第一个同学，p1是去寻找满足条件的节点，它指向（找到）的是第三个同学,而p2指向的是第二个同学，这样新来的同学就被"夹在"p2和p1之间了。

##     2.输出链表 ##

这比建表还容易么不是，只需要让p1指向已经建立好的链表的头结点，然后不断的后移，输入每一个节点指向的单元内容即可。

void print(struct student * head)
    {
    struct student * p;
    printf("现在这%d个记录是：\n",n);
    p=head;
    if(head!=NULL)
    {
    	do 
    	{
    		printf("%ld%5.1f\n",p->num,p->score);
    		p=p->next;
    	} while (p!=NULL);
    }
    }

##        3.删除节点 ##

有必要说一下啊，这里程序默认的是链表按学号由小到大排列，所以进行后移的条件就是进行学号值的比较。并且如果学号为0，则退出对应的循环。

有几个特殊情况提前分析一下：

1.如果要删除的节点是头结点，则只需要将head指针指向第二个节点即可。

2.如果删除的节点是最后一个节点，则只需要让倒数第二个节点的next指针为空。

3.其余情况均为，将p2的next指针指向p1的next指针所指节点（即跳过那个要删除的节点）。

代码片段如下：

struct student * del(struct student * head,long number)
    {
      struct student * p1,* p2;
      if (head==NULL)
      { printf("\n It is empty!");goto end;}
      
        p1=head;
    	//当所输入的number（学号）不等于p1所指节点的num成员，且p1的下一个节点不为空
        while(number!=p1->num && p1->next!=NULL)
        {
    		p2=p1;      //p2为已经检查过的节点的定位，随着p1的后移，p2也在后移，但p2始终在p1前面一个位置
    		p1=p1->next;//p1后移
        } 
       if(number==p1->num)//找到了 
       {
         //分两种情况
    	 //当p1指向头节点的时候
    	   if (p1==head)
    	   {
    		   head=p1->next;//删除第一个节点(特殊情况)
    	   } 
    	   else
    	   {
    		   p2->next=p1->next;//正常情况下的删除
    	   }
    	   printf("已删除：%ld\n",number);
    	   n=n-1;
    
       }
       else
       {
    	   printf("没有找到%ld节点！",number);
       }
       end:
       return(head);

##     4.插入节点 ##

由于默认插入的顺序是按学号由小到大，则需要将插入节点单元里的学号与当前每个节点里的学号相比较，找到具体的位置进行插入：

1.若插入节点在最前面，则head指向插入节点（即待插入节点变为头结点），插入节点的next指针指向原链表的第一个节点。

2.若待插入节点在最后一个，则p1（p1此时肯定指向的是原链表的最后一个节点）的next指针指向待插入节点，而待插入节点的next指针为NULL，表示表尾。

3.除了上面两种特殊情况外，正常情况下应该是p2的next指针指向待插入节点，而待插入节点的next指针指向p1。

代码片段如下:

struct student *insert(struct student * head,struct student * stud)
     {
    	 struct student *p1,*p2,*p0;
    	 p1=head;//p1指向头结点开始寻找
    	 p0=stud;//p0指向待插入节点
    	if (head==NULL)
    	{
    		head=p0;p0->next=NULL;//空表，只返回待插入节点
    	} 
    	else
    	{
    		while((p0->num>p1->num) && (p1->next!=NULL))//按默认的由小到大的顺序去寻找待插入点的位置
    		{
               p2=p1;   //p1在后移之前p2去记录它的位置
    		   p1=p1->next;//p1后移
    		} 
    		//在while循环中，其实已经找到了待插入节点的临界位置，也就是说p0肯定是大于p1，而p1此时在后移一次就该大于p0了，
    		//所以赶紧让p2记录p1，p1后移，这样p0就夹在p2和p1之间了
    	     if (p0->num<=p1->num)//跨越了上面的临界位置，找到了p0的位置
    	     {
    			 if (head==p1)
    			 {
                   head=p0;p0->next=p1;//p1指向头结点(特殊情况)
    			 } 
    			 else                  //(正常情况)
    			 {
    				 p2->next=p0;
    				 p0->next=p1;
    			 }
    	     } 
    	     else                      //找不到比p0小的p1，说明p0的位置在最后一个
    	     {
    			 p1->next=p0;p0->next=NULL;//尾节点(特殊情况)
    	     }
    		 n=n+1;                     //节点加1
    		 return(head);              //返回链表头地址
    	}
    
     }

##         5.链表综合操作汇总，全代码如下： ##

#include <stdio.h>
    #include <malloc.h>
    #define len sizeof(struct student)
    #define  NULL 0
    struct student
    {
    	long int num;
    	float score;
    	struct student * next;
    };
    int n; //定义全局n，表示节点数
    /*****创建链表子函数开始*******/
    struct student * creat(void)
    {
    	n=0;
    	struct student *p1,*p2,*head;
    	head=NULL;//初始化头结点指针，使其指向空，表示当前链表没有节点
    	p1=p2=(struct student *)malloc(len);//开辟一个新节点区域，使得P1P2均指向该区域的首地址
    	scanf("%ld,%f",&p1->num,&p1->score);
    	while((p1->num)!=0)
    	{
    		n=n+1;//节点数加1
    		if(n==1)
    			head=p1;
    		else
    			p2->next=p1;//使得p2的next指针指向新区域的首地址（因为此时p1已经是新区域的首地址了）
    		p2=p1;          //下面p1就要指向新区域了，临走之前必须让p2来记录一下自己
    		p1=(struct student *)malloc(len);//在while循环中不断的创造新节点
    		scanf("%ld,%f",&p1->num,&p1->score);
    	}
    	p2->next=NULL;      //尾部指针为空，说明是表尾
    	return(head);
    }
    /***********输出链表函数**********************/
    
    void print(struct student * head)
    {
    struct student * p;
    printf("现在这%d个记录是：\n",n);
    p=head;
    if(head!=NULL)
    {
    	do 
    	{
    		printf("%ld%5.1f\n",p->num,p->score);
    		p=p->next;
    	} while (p!=NULL);
    }
    }
    /********删除节点函数开始*******************/
    struct student * del(struct student * head,long number)
    {
      struct student * p1,* p2;
      if (head==NULL)
      { printf("\n It is empty!");goto end;}
      
        p1=head;
    	//当所输入的number（学号）不等于p1所指节点的num成员，且p1的下一个节点不为空
        while(number!=p1->num && p1->next!=NULL)
        {
    		p2=p1;      //p2为已经检查过的节点的定位，随着p1的后移，p2也在后移，但p2始终在p1前面一个位置
    		p1=p1->next;//p1后移
        } 
       if(number==p1->num)//找到了 
       {
         //分两种情况
    	 //当p1指向头节点的时候
    	   if (p1==head)
    	   {
    		   head=p1->next;//删除第一个节点(特殊情况)
    	   } 
    	   else
    	   {
    		   p2->next=p1->next;//正常情况下的删除
    	   }
    	   printf("已删除：%ld\n",number);
    	   n=n-1;
    
       }
       else
       {
    	   printf("没有找到%ld节点！",number);
       }
       end:
       return(head);
    }
    /********插入节点函数开始**************/
     struct student *insert(struct student * head,struct student * stud)
     {
    	 struct student *p1,*p2,*p0;
    	 p1=head;//p1指向头结点开始寻找
    	 p0=stud;//p0指向待插入节点
    	if (head==NULL)
    	{
    		head=p0;p0->next=NULL;//空表，只返回待插入节点
    	} 
    	else
    	{
    		while((p0->num>p1->num) && (p1->next!=NULL))//按默认的由小到大的顺序去寻找待插入点的位置
    		{
               p2=p1;   //p1在后移之前p2去记录它的位置
    		   p1=p1->next;//p1后移
    		} 
    		//在while循环中，其实已经找到了待插入节点的临界位置，也就是说p0肯定是大于p1，而p1此时在后移一次就该大于p0了，
    		//所以赶紧让p2记录p1，p1后移，这样p0就夹在p2和p1之间了
    	     if (p0->num<=p1->num)//跨越了上面的临界位置，找到了p0的位置
    	     {
    			 if (head==p1)
    			 {
                   head=p0;p0->next=p1;//p1指向头结点(特殊情况)
    			 } 
    			 else                  //(正常情况)
    			 {
    				 p2->next=p0;
    				 p0->next=p1;
    			 }
    	     } 
    	     else                      //找不到比p0小的p1，说明p0的位置在最后一个
    	     {
    			 p1->next=p0;p0->next=NULL;//尾节点(特殊情况)
    	     }
    		 n=n+1;                     //节点加1
    		 return(head);              //返回链表头地址
    	}
    
     }
     /*************主函数开始***********************/
         void main()
    	 {
    		 struct student * head,* stu;
    		 long del_num;
    		 printf("输入记录:\n");
    		 head=creat();                           //建立链表，返回头指针
    		 print(head);                            //输出全部节点
    		 printf("\n输入要删除的节点号:");
    		 scanf("%ld",&del_num);  
    		 while(del_num!=0)                       //只要输入的节点号不是0，就可以一直进行删除节点操作
    		 { head=del(head,del_num);               //返回删除节点后链表的头指针
    		   print(head);
               printf("输入继续删除的节点,注意:\n若号码为0则结束删除功能:");
    		   scanf("%ld",&del_num);
    		 }
    		 printf("\n输入要插入的节点:");   
    		 stu=(struct student *)malloc(len);      //要插入节点必须要开辟新空间，
    		 scanf("%ld,%f",&stu->num,&stu->score);  //并且进行赋值
    		 while (stu->num!=0)    
    		 {
    			 head=insert(head,stu);              //只要输入的节点号不为0，就可以一直进行插入节点操作
    			 print(head);                        //并且执行的时候还是要不断进行空间的开辟
    			 printf("输入要插入的节点:");
    			 stu=(struct student *)malloc(len);
    			 scanf("%ld,%f",&stu->num,&stu->score);
    		 }
    		 
    	 }

发表评论取消回复

表情：

评论列表（有 0 条评论，245人围观）

还没有评论，来说两句吧...

相关阅读

相关单链表的基本操作

单链表的基本操作实验环境:visual studio2019 代码实现 include <stdio.h> include <stdlib.h>

╰+哭是因爲堅強的太久メ/ 2022年10月17日 04:24/ 0 赞/ 177 阅读

相关单链表基本操作总结

链表基本概念：链表：线性表的链式存储。数据域：存储数据信息。即数据。指针域：存放下一节点的位置信息。即该指针指向下一节点。单链表：每一个节点node：一个

绝地灬酷狼/ 2022年08月02日 00:16/ 0 赞/ 319 阅读

相关单链表的基本操作

2016年7月14日16:22:48 单链表的基本运算有: 1.单链表的创建; 2.单链表的插入; 3.

墨蓝/ 2022年07月16日 13:26/ 0 赞/ 215 阅读

相关单链表的基本操作

class Link\{ public int iData; public double dData; public Link nex

素颜马尾好姑娘i/ 2022年06月01日 08:22/ 0 赞/ 228 阅读

相关数据结构：单链表的基本操作

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。这组存储单元可以是连续的，也可以是不连续的。链表中的数据是以结点来表示的，一个结

快来打我*/ 2022年05月25日 03:55/ 0 赞/ 274 阅读

相关单链表的基本操作（3）：单链表实现栈

我们知道，栈是一种“后进先出”的数据结构，对栈的插入和删除操作都是在栈头位置进行的，这与在单链表的表头插入和删除元素的原理类似，因此可以用单向链表实现栈。单链表实现栈的

朱雀/ 2022年05月18日 03:12/ 0 赞/ 222 阅读

相关单链表的基本操作（2）

package parking; import java.util.Stack; / 链表 @

桃扇骨/ 2022年05月18日 03:09/ 0 赞/ 168 阅读

相关单链表的基本操作！

假设以学生信息结构体作为链表节点，其中结构体成员包括三个元素，学号，成绩和一个结构体指针。前两个成员是节点存储的本身内容，而最后一个成员，定义为指向结构体的指针，是用来

心已赠人/ 2022年05月15日 11:05/ 0 赞/ 246 阅读

相关 java单链表基本操作

public class ListNodeDemo { public static void main(String[] args) {

Myth丶恋晨/ 2022年01月22日 11:59/ 0 赞/ 243 阅读

相关单链表的基本操作

// 单链表.cpp : 单链表的相关操作（两种方法的建立、两种方法的查询、求长、打印、插入、删除、逆序反转）。 include "stdafx.h"

心已赠人/ 2021年06月24日 15:56/ 0 赞/ 477 阅读