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

056第十章 结构体与共用体04(新版) 單向鏈表

发布时间：2021-05-07 15:36:34编辑：雪饮阅读（）

 單向鏈表

链表是一种常见的基础数据结构，结构体指针在这里得到了充分的利用。链表可以动态的进行存储分配，也就是说，链表是一个功能极为强大的数组，他可以在节点中定义多种数据类型，还可以根据需要随意增添，删除，插入节点。链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。说到这里你应该就明白了，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，该元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。
作为有强大功能的链表，对他的操作当然有许多，比如：链表的创建，修改，删除，插入，输出，排序，反序，清空链表的元素，求链表的长度等等。
初学链表，一般从单向链表开始
 
根据下面的分析写一函数建立一个含有学生（学号，成绩）数据的单向动态链表。
（约定：我们约定学号不会为零，如果输入的学号为０，则表示建立链表的过程完成，该结点不应连接到链表中。）
原理大致如圖

則實現如:
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
//student结构的大小
#define LEN sizeof(struct student)
//全局变量，用来记录存放了多少数据。
int n;
struct student
{
      int num;
      float score;
      struct student *next;
};
//创建链表
struct student *creat()
{
      struct student *head;
        //p1臨時指針，p2尾指針
      struct student *p1, *p2;
 
      p1 = p2 = (struct student *)malloc(LEN); // LEN是student结构的大小
        printf("struct student size:%d \n",LEN);
      printf("Please enter the num :");
      scanf("%d", &p1->num);
      printf("Please enter the score :");
      scanf("%f", &p1->score);
 
      head = NULL;    
      n = 0;   
     
      while( 0 != p1->num )
      {
            n++;
                     //創建火車頭
            if( 1 == n )
            {
                  head = p1;                
            }
                     //創建鏈表尾部
            else
            {
                  p2->next = p1;
            }
 
            p2 = p1;
                     /*
                     本輪循環結束繼續創建下一個節點
                     malloc只有在原地址擴容的時候才發生地址變化
                     這裏p1不會覆蓋上面的head=p1和p2->next=p1以及p2=p1，因爲這三個接收的都是p1這個地址，除非修改p1這個地址上對應的數據被修改了才叫覆蓋
                     這點和php中a=5,b=&a,a=6時候對b的影響是不同的
                     因爲這裏p1本來就是存儲指針的，而下面這裏這個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( NULL != head )
      {
            do
            {
                  printf("学号为 %d 的成绩是: %f\n", p->num, p->score);
                  p = p->next;
            }while( NULL != p );
      }
}
void main()
{
      struct student *stu;
 
      stu = creat();
      print( stu );
 
      printf("\n\n");
        /*
        system("pause") 是暂停的意思，等待用户信号；不然控制台程序会一闪即过，你来不及看到执行结果。
        在這裏其實意義不大，但是既然小甲魚把他寫在了代碼裏，那麽應該是有他的'意義'
        這裏在控制臺中表現的效果如：”请按任意键继续. . .“
        */
      system("pause");
}
對於循環該鏈表創建過程細品：
第一次：
       p2和head都指向p1（循環外的p1），換句話，“p2指向head"
       產生一個新的p1（設爲p1_2）
第二次：
       p2->next指向p1(p1_2)，p2自身目前還是上一輪的p1即head
       p2指向p1(p1_2，相當於更新了p2)
       並產生一個新的p1（設爲p1_3）
第三次：
       p2->next指向p1(p1_3),p2自身目前還是上一輪的p1即p1_2
       p2指向p1(p1-3,相當於更新了p2)
       並產生一個新的p1（設爲p1_4）
經過了n輪....:
       最後一次沒有next，就把next置為null