結構體指針處理連結清單

7 用指針處理連結清單

7.1 連結清單概述

　　連結清單是一種常見的重要的資料結構。它是動态地進行存儲配置設定的一種結構。

　　連結清單有一個 頭指針 變量，它存放一個位址，該位址指向一個元素，連結清單中每一個元素稱為 結點，每個結點都應包括兩個部分，一為使用者需要用的實際資料，二為下一個結點的位址。可以看出，頭指針 head 指向第一個元素，第一個元素又指向第二個元素，。。。。直到最後一個元素，該元素不再指向其他元素，它稱為 表尾，它的位址部分放一個 NULL（表示 空位址）連結清單到此結束。

　　可以看到連結清單中各元素在記憶體中可以不是連續存放的，要找某一進制素，必須先找到上一個元素，根據它提供的下一進制素位址才能找到下一個元素。如果不提供 頭指針 head 則整個連結清單無法通路。

　　可以看到。這種連結清單的資料結構，必須利用指針變量才能實作，即一個結點中應包含一個指針變量，用它存放下一結點的位址。

　　前面介紹了結構體變量，用它作連結清單中的結點是最合适的，一個結構體變量包含若幹成員，這些成員可以是數值類型，字元類型，數組類型，也可以是指針類型，我們用這個指針類型成員來存放下一個結點的位址。例如可以設計這樣一個結構體類型：

　　struct student

　　{

　　　　int num;

　　　　float score;

　　　　struct student *next;

　　};

　　其中成員 num 和 score 用來存放結點中的有用資料（使用者需要用到的資料），next 是指針類型成員，它指向 struct student 類型資料（這是 next 所在結構體類型）。一個指針類型的成員既可以指向其他類型的結構體資料，也可以指向自己所在的結構體類型的資料。現在 next 是 struct student 類型中的一個成員，它又指向 struct student 類型的資料。用這種方法就可以建立連結清單。

　　請注意：隻是定義一個 struct student 類型，并未實際配置設定存儲空間，隻有定義了變量才配置設定記憶體單元。

7.2 簡單連結清單

　　下面通過一個例子來說明如何建立和輸出一個簡單連結清單

#include <stdio.h>

#include <stdlib.h>

#define NULL 0

struct student

{

　　long num;

　　float score;

　　struct student *next;

};

void main()

{

　　struct student a, b, c, *head, *p;

　　a.num = 99101; a.score = 89.5;

　　b.num = 99103; b.score = 90;

　　c.num = 99107; c.score = 85;//對結點的 num 和 score 成員指派

　　head = &a;//将結點 a 的起始位址賦給頭指針 head

　　a.next = &b;//将結點 b 的起始位址賦給 a 結點的 next 成員

　　b.next = &c;

　　c.next = NULL;// c 結點的 next 成員不存放其他結點位址

　　p = head;//使 p 指針指向 a 結點

　　do

　　{

　　　　printf("%ld %5.1f\n", p->num, p->score);// 輸出 p 指向的結點的資料

　　　　p = p->next;//使 p 指向下一結點

　　}while(p != NULL);//輸出完 c 結點後 p 的值為 NULL

　　system("pause");

}

運作結果

99101  89.5

99103  90.0

99107  85.0

7.3 處理動态連結清單所需的函數

　　（1）malloc 函數

　　void *malloc(unsigned int size);

　　作用是在記憶體的動态存儲區中配置設定一個長度為 size 的連接配接空間。些函數的值（即傳回值）是一個指向配置設定空間起始位址的指針（基類型為 void）。如果些函數未能成功地執行（例如記憶體空間不足）則傳回空指針 NULL。

　　（2）calloc 函數

　　void *calloc(unsigned n, unsigned size);

　　其作用是在記憶體的動态區存儲中配置設定 n 個長度為 size 的連續空間。函數傳回一個指向配置設定空間起始位址的指針，如果配置設定不成功，傳回 NULL。

　　用 calloc 函數可以為一維數組開辟動态存儲空間， n 為數組元素個數，每個元素長度為 size。　　

　　（3）free 函數

　　void free(void *p);

　　其作用是釋放由 p 指向的記憶體區，使這部分記憶體區能被其它變量使用， p 是最後一次調用 calloc 或 malloc 函數時傳回的值。free 函數無傳回值。

　　請注意：以前的C版本提供的 malloc 和 calloc 函數得到的是指向字元型資料的指針。ANSI C 提供的 malloc 和 calloc 函數規定為 void * 類型。

7.4 建立動态連結清單

　　所謂建立動态連結清單是指在程式執行過程中從無到有地建立起一個鍵表，即一個一個地開辟結點和輸入各結點資料，并建立起前後相鍊的關系。

　　

#include <stdio.h>

#include <stdlib.h>

#define NULL 0

#define LEN sizeof(struct student)

struct student

{

　　long num;

　　float score;

　　struct student *next;

};

struct student *create()

{

　　struct student *p1, *p2, *head;

　　int num;

　　float score;

　　int n = 0;

　　head = NULL;

　　p1 = p2 = (struct student *)malloc(LEN);

　　printf("please input num and score.\n");

　　scanf("%d,%f", &p1->num, &p1->score);

　　while(p1->num != 0)

　　{

　　　　n ++;

　　　　if(n == 1)

　　　　　　head = p1;

　　　　else

　　　　　　p2->next = p1;

　　　　p2 = p1;

　　　　p1 = (struct student *)malloc(sizeof(struct student));

　　　　printf("please input num and score.\n");

　　　　scanf("%d,%f", &p1->num, &p1->score);

　　}

　　p2->next = NULL;

　　return head;

}

void printlist(struct student *head)

{

　　struct student *p;

　　p = head;

　　if(head != NULL)

　　{

　　　　do

　　　　{

　　　　　　printf("num=%d score=%f\n", p->num, p->score);

　　　　　　p = p->next;

　　　　}while(p != NULL);

　　}

}

void main()

{

　　struct student *head;

　　head = create();

　　printlist(head);

　　system("pause");

}

以下是對連結清單的各種操作

列印連結清單

void printlist(struct student *head)

{

 struct student *p;

 p = head;

 if(head != NULL)

 {

  do

  {

   printf("num=%d score=%5.2f\n", p->num, p->score);

   p = p->next;

  } while (p != NULL);

 }

}

删除節點

struct student *delNode(struct student *head, int num)

{

 printf("delNode.\n");

 struct student *p1, *p2;

 if(head == NULL)

 {

  printf("The List is NULL.\n");

 }

 else

 {

  p1 = head;

  while(p1->next != NULL && p1->num != num)

  {

   p2 = p1;

   p1 = p1->next;

  }

  if(p1->num == num)

  {

   if(p1 == head)

    head = p1->next;

   else

    p2->next = p1->next;

  }

  else

   printf("Can not find list num.\n");

 }

 return head;

}

更新節點

struct student *update(struct student *head, int index, int num, float score)

{

 printf("update.\n");

 struct student *p;

 if(head == NULL)

 {

  printf("The List is NULL.\n");

 }

 else

 {

  p = head;

  while(p->next != NULL && p->num != index)

  {

   p = p->next;

  }

  if(p->num == index)

  {

   p->num = num;

   p->score = score;

  }

  else

   printf("Can not find list index.\n");

 }

 return head;

}

增加節點

struct student *add(struct student *head, int index, int num, float score)

{

 printf("add.\n");

 struct student *p1, *p2, *p3;

 if(head == NULL)

 {

  printf("The List is NULL.\n");

 }

 else

 {

  p1 = p2 = head;

  while(p1->next != NULL && p1->num != index)

  {

   p1 = p1->next;

   p2 = p1;

  }

  if(p1->num == index)

  {

   p3 = (struct student *)malloc(LEN);

   p3->num = num;

   p3->score = score;

   if(p2->next == NULL)

   {

    p2->next = p3;

    p3->next = NULL;

   }

   else

   {

    p3->next = p2->next;

    p2->next = p3;   

   }

  }

  else

   printf("Can not find list index.\n");

 }

 return head;

}