第 17 章 高级数据表示（链表）

 1 /*---------------------------------
 2     list.h -- 简单链表类型的头文件
 3 ---------------------------------*/
 4 
 5 #ifndef LIST_H
 6 #define LIST_H
 7 
 8 #define TSIZE    45
 9 
10 typedef struct film
11 {
12     char title[TSIZE];
13     int rating;
14 } Item;
15 
16 typedef struct node
17 {
18     Item item;
19     struct node *next;
20 } Node;
21 
22 typedef struct list
23 {
24     Node *head;                //指向链表头的指针
25     unsigned int size;        //链表中的节点数
26 } List;
27 
28 
29 //初始化链表为空
30 void InitializeList(List *plist);
31 
32 //确定链表是否为空，链表为空返回true，否则返回false
33 bool ListIsEmpty(const List *plist);
34 
35 //确定链表是否已满
36 bool ListIsFull(const List *plist);
37 
38 //确定链表中的节点数
39 unsigned int ListItemCount(const List *plist);
40 
41 //在链表末尾添加项item，成功返回true，否则返回false
42 bool AddItem(Item item, List *plist);
43 
44 //声明函数指针 PFUN，作为 Tranverse() 函数的第二形参
45 typedef void (*PFUN)(Item);
46 
47 //把函数作用于链表的每一项
48 void Tranverse(const List *plist, PFUN pfun);
49 
50 //释放已分配的内存
51 void EmptyTheList(List *plist);
52 
53 #endif

list.h

  1 /*---------------------------------------------
  2     list.c -- 简单链表接口实现
  3 ---------------------------------------------*/
  4 
  5 #include <stdio.h>
  6 #include <stdlib.h>
  7 #include "list.h"
  8 
  9 //把一项拷贝到节点中；CopyToNode 是辅助函数，不是接口函数
 10 static void CopyToNode(Item item, Node *pnode)
 11 {
 12     pnode->item = item;        //拷贝结构
 13 }
 14 
 15 
 16 //接口函数
 17 
 18 void InitializeList(List *plist)
 19 {
 20     plist->head = NULL;
 21     plist->size = 0;
 22 }
 23 
 24 bool ListIsEmpty(const List *plist)
 25 {
 26     if (plist->head == NULL)
 27         return true;
 28     else
 29         return false;
 30 }
 31 
 32 bool ListIsFull(const List *plist)
 33 {
 34     bool full;
 35     Node *pnode = (Node*)malloc(sizeof(Node));
 36 
 37     if (pnode == NULL)        //查看对内存是否已满，判断链表状态
 38         full = true;
 39     else
 40     {
 41         full = false;
 42         free(pnode);
 43     }
 44 
 45     return full;
 46 }
 47 
 48 unsigned int ListItemCount(const List *plist)
 49 {
 50     return plist->size;
 51 }
 52 
 53 bool AddItem(Item item, List *plist)
 54 {
 55     Node *pnew = (Node*)malloc(sizeof(Node));
 56     if (pnew == NULL) return false;
 57 
 58     CopyToNode(item, pnew);
 59     pnew->next = NULL;
 60 
 61     Node *pscan = plist->head;
 62 
 63     if (pscan == NULL)
 64         plist->head = pscan = pnew;
 65     else
 66     {
 67         while (pscan->next != NULL)
 68             pscan = pscan->next;
 69 
 70         pscan->next = pnew;
 71     }
 72 
 73     ++(plist->size);
 74     return true;
 75 }
 76 
 77 void Tranverse(const List *plist, PFUN pfun)
 78 {
 79     Node *pnode = plist->head;        //指针的拷贝，不改变 plist->head 的值
 80     while (pnode != NULL)
 81     {
 82         (*pfun)(pnode->item);
 83         pnode = pnode->next;
 84     }
 85 }
 86 
 87 void EmptyTheList(List *plist)
 88 {
 89     Node *ptmp;
 90     Node *pscan = plist->head;
 91 
 92     while (pscan != NULL)
 93     {
 94         ptmp = pscan->next;
 95         free(pscan);
 96         pscan = ptmp;
 97     }
 98 
 99     plist->head = NULL;        //销毁内存，头指针置为NULL
100     plist->size = 0;        //销毁内存，节点数置为0
101 }

list.c

 1 /*------------------------------------------------
 2     films3.c -- 使用抽象数据类型(ADT)风格的链表
 3 ------------------------------------------------*/
 4 
 5 #include <stdio.h>
 6 #include <stdlib.h>        //提供 exit() 原型
 7 #include <string.h>
 8 #include "list.h"
 9 
10 void showmovies(Item item);
11 char* s_gets(char *st, int n);
12 
13 int main()
14 {
15     List movies;
16     Item temp;
17 
18     //初始化
19     InitializeList(&movies);
20     if (ListIsFull(&movies))
21     {
22         fprintf(stderr, "No memory available!\n");
23         exit(EXIT_FAILURE);
24     }
25 
26     //获取用户输入并存储
27     puts("Enter first movie title:");
28     while (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '\0')
29     {
30         fputs("Enter your rating <0-10>:\n", stdout);
31         scanf("%d", &temp.rating);
32         while (getchar() != '\n') continue;
33 
34         if (AddItem(temp, &movies) == false)
35         {
36             fprintf(stderr, "Problem allocating memory\n");
37             break;
38         }
39 
40         if (ListIsFull(&movies))
41         {
42             puts("The list is now full.");
43             break;
44         }
45 
46         puts("Enter next movie title (empty line to stop):");
47     }
48 
49     //显示
50     if (ListIsEmpty(&movies))
51         printf("No data entered.\n");
52     else
53     {
54         printf("Here is the movie list:\n");
55         Tranverse(&movies, showmovies);
56     }
57     printf("You entered %d movies.\n", ListItemCount(&movies));
58 
59     //清理
60     EmptyTheList(&movies);
61     printf("Bye!\n");
62 
63     return 0;
64 }
65 
66 void showmovies(Item item)
67 {
68     printf("Movie: %s Rating: %d\n", item.title, item.rating);
69 }
70 
71 char* s_gets(char *st, int n)
72 {
73     char *ret_val, *find;
74 
75     if (ret_val = fgets(st, n, stdin))
76     {
77         if (find = strchr(st, '\n'))
78             *find = '\0';
79         else
80             while (fgetc(stdin) != '\n') continue;
81     }
82 
83     return ret_val;
84 }

films3.c