欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

第 17 章 高级数据表示(链表)

程序员文章站 2022-03-12 08:04:03
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 r ......
第 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
第 17 章 高级数据表示(链表)
  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
第 17 章 高级数据表示(链表)
 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

第 17 章 高级数据表示(链表)