您当前的位置： 首页 > 学无止境 > 心得笔记 网站首页心得笔记

057第十章 结构体与共用体05(新版) 鏈表節點的刪除與插入

发布时间：2021-05-07 17:17:23编辑：雪饮阅读（）

 对链表结点的删除操作实现

對鏈表節點的刪除一般就考慮兩種情況，在鏈表邊界（兩邊，例如頭和尾）和不在鏈表邊界
那麽這裏針對上篇中的鏈表進行再加工實現如：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
 
#define LEN sizeof(struct student) // student结构的大小
 
struct student *creat();   // 创建链表
struct student *del( struct student *head, int num); // del函数用于删除结点, *head即链表
                                                      // 的头指针, num是要删除的结点num。
void print(struct student *head);   // 打印链表
 
struct student
{
      int num;
      float score;
      struct student *next;
};
 
int n;    // 全局变量，用来记录存放了多少数据。
 
void main()
{
      struct student *stu, *p;
      int n;
 
      stu = creat();
      p = stu;
      print( p );
 
      printf("Please enter the num to delete: ");
      scanf("%d", &n);
      print( del(p, n) );
     
      printf("\n\n");
      system("pause");
}
 
struct student *creat()
{
      struct student *head;
      struct student *p1, *p2;
 
      p1 = p2 = (struct student *)malloc(LEN); // LEN是student结构的大小
 
      printf("Please enter the num :");
      scanf("%d", &p1->num);
      printf("Please enter the score :");
      scanf("%f", &p1->score);
 
      head = NULL;    
      n = 0;   
     
      while( p1->num )
      {
            n++;
            if( 1 == n )
            {
                  head = p1;                
            }
            else
            {
                  p2->next = p1;
            }
 
            p2 = p1;
            p1 = (struct student *)malloc(LEN);
 
            printf("\nPlease enter the num :");
            scanf("%d", &p1->num);
            printf("Please enter the score :");
            scanf("%f", &p1->score);
      }
 
      p2->next = NULL;
 
      return head;
}
 
void print(struct student *head)
{
      struct student *p;
      printf("\nThere are %d records!\n\n", n);
 
      p = head;
      if( head )
      {
            do
            {
                  printf("学号为 %d 的成绩是: %f\n", p->num, p->score);
                  p = p->next;
            }while( p );
      }
}
 
struct student *del( struct student *head, int num)
{
      struct student *p1, *p2;
     
      if( NULL == head ) // 如果头结点指向NULL，这是一个空链表。纯属忽悠T_T
      {
            printf("\nThis list is null!\n");
            goto END;
      }
 
      p1 = head;
      while( p1->num != num && p1->next != NULL)
      {
            p2 = p1;
            p1 = p1->next;
      }
        //隨著上面的while循環p1不斷迭代為其下一個，則最後的p1中有可能就是其num等於待刪除的num
      if( num == p1->num )
      {
                  /*
                     当将要删除的结点位于头结点的时候
                     刪除了頭節點，則新的頭節點就是原來頭節點的下一個節點
                     */
            if( p1 == head )     
            {
                  head = p1->next;
            }
                     /*
                     一般情况:
                     刪除了某個節點，則該節點的前面節點就直接鏈接到該節點的後面節點
                     */
            else                 
            {
                  p2->next = p1->next;
            }
 
            printf("\nDelete No: %d succeed!\n", num);
            n = n-1; // n是作为一个全局变量，用来记录链表的数据数。
      }
      else
      {
            printf("%d not been found!\n", num);
      }
 
END:
      return head;
}
編譯並運行的結果如：
D:\cproject>gcc main.c -o m
 
D:\cproject>m.exe
Please enter the num :1
Please enter the score :11
 
Please enter the num :2
Please enter the score :22
 
Please enter the num :3
Please enter the score :33
 
Please enter the num :0
Please enter the score :0
 
There are 3 records!
 
学号为 1 的成绩是: 11.000000
学号为 2 的成绩是: 22.000000
学号为 3 的成绩是: 33.000000
Please enter the num to delete: 1
 
Delete No: 1 succeed!
 
There are 2 records!
 
学号为 2 的成绩是: 22.000000
学号为 3 的成绩是: 33.000000
 
 
请按任意键继续. . .
对链表的插入操作
对链表的插入是指将一个结点插入到一个已有的链表中。
 
为了能做到正确插入，必须解决两个问题：
 ① 怎样找到插入的位置；
 ② 怎样实现插入。
 
我们可以先用指针变量p0指向待插入的结点，p1指向第一个结点。将p0->num与p1->num相比较，如果p0->num＞p1-> num ，此时将p1后移，并使p2指向刚才p1所指的结点。
具體實例如：
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
 
#define LEN sizeof(struct student) // student结构的大小
 
struct student *creat();   //创建链表
/*
del函数用于删除结点, *head即链表的头指针, num是要删除的结点num。
*/
struct student *del(struct student *head, int num);  
 /*
 第一个参数需要被插入的链表
 第二个参数待插入的结构的地址
 */
struct student *insert(struct student *head, struct student *stu_2); 
 
void print(struct student *head);   //打印链表
 
struct student
{
      int num;
      float score;
      struct student *next;
};
 
int n; //全局变量，用来记录存放了多少数据。
 
void main()
{
      struct student *stu, *p, stu_2;
      int n;
     
      stu = creat();
      p = stu;
      print( p );
     
      printf("\nPlease input the num to delete: ");
      scanf("%d", &n);
      print( del(p, n) );
 
      printf("\nPlease input the num to insert: ");
      scanf("%d", &stu_2.num);
      printf("Please input the score: ");
      scanf("%f", &stu_2.score);
 
      p = insert(stu, &stu_2);
      print( p );
 
 
     
 
      printf("\n\n");
      system("pause");
}
 
struct student *creat()
{
      struct student *head;
      struct student *p1, *p2;
     
      p1 = p2 = (struct student *)malloc(LEN); // LEN是student结构的大小
     
      printf("Please enter the num :");
      scanf("%d", &p1->num);
      printf("Please enter the score :");
      scanf("%f", &p1->score);
     
      head = NULL;    
      n = 0;   
     
      while( p1->num )
      {
            n++;
            if( 1 == n )
            {
                  head = p1;                
            }
            else
            {
                  p2->next = p1;
            }
           
            p2 = p1;
            p1 = (struct student *)malloc(LEN);
           
            printf("\nPlease enter the num :");
            scanf("%d", &p1->num);
            printf("Please enter the score :");
            scanf("%f", &p1->score);
      }
     
      p2->next = NULL;
     
      return head;
}
 
void print(struct student *head)
{
      struct student *p;
      printf("\nThere are %d records!\n\n", n);
     
      p = head;
      if( head )
      {
            do
            {
                  printf("学号为 %d 的成绩是: %f\n", p->num, p->score);
                  p = p->next;
            }while( p );
      }
}
 
struct student *del( struct student *head, int num)
{
      struct student *p1, *p2;
     
      if( NULL == head )
      {
            printf("\nThis list is null!\n");
            goto end;
      }
     
      p1 = head;
      while( p1->num != num && p1->next != NULL)
      {
            p2 = p1;
            p1 = p1->next;
      }
      if( num == p1->num )
      {
            if( p1 == head )
            {
                  head = p1->next;
            }
            else
            {
                  p2->next = p1->next;
            }
           
            printf("Delete No: %d succeed!\n", num);
            n = n-1;
      }
      else
      {
            printf("%d not been found!\n", num);
      }
     
end:
      return head;
}
 
struct student *insert(struct student *head, struct student *stu_2)
{
      struct student *p0, *p1, *p2;
     
      p1 = head;
      p0 = stu_2;
      if( NULL == head )
      {
            head = p0;
            p0->next = NULL;
      }
      else
      {
                 //两种情况推出while，一：
            while( (p0->num > p1->num) && (p1->next != NULL) )
            {
                  p2 = p1;
                  p1 = p1->next;
            }
            /*
                     經過上面的while循環之後最後一次p1的num也不能排除一定就大於等於p0的num，因爲也可能是p1->next!=null導致的
                     */
            if( p0->num <= p1->num )
            {
                             // p1是头结点，插入头部
                  if( head == p1 )  
                  {
                        head = p0; 
                  }
                             /*
                             普通情况，插入中间
                             經過上面的while循環迭代，p2每次為p1的前身，而p1每次為p1的next
                             所以這裏p2->next就是某兩個節點閒被插入新節點的位置
                             */
                  else              
                  {
                        p2->next = p0;
                  }
                             //無論新節點插入到什麽位置，則該新節點的下一個節點就是當前的p1節點[頭節點或者p1(p1=p1->next)]
                  p0->next = p1;
            }
            else   // p0的num最大，插入到末尾
            {
                  p1->next = p0;
                  p0->next = NULL;
            }
      }
 
      n = n+1;   // 由于插入了，所以增加了一位数据成员进入链表中。
     
      return head;
}
編譯並運行結果如：