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

图片 1图片 2

图片 3图片 4

 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
 1 /*------------------------
 2     queue.h -- Queue接口
 3 ------------------------*/
 4 
 5 #ifndef QUEUE_H
 6 #define QUEUE_H
 7 
 8 #define MAXQUEUE 10
 9 
10 typedef int Item;
11 
12 typedef struct node
13 {
14     Item item;
15     struct node *next;
16 } Node;
17 
18 typedef struct queue
19 {
20     Node *front;    //指向队列首项的指针
21     Node *rear;        //指向队列尾项的指针
22     int items;        //队列中的项数
23 } Queue;
24 
25 //初始化队列为空
26 void InitializeQueue(Queue *pq);
27 
28 //检查队列是否已满,已满返回true,否则返回false
29 bool QueueIsFull(const Queue *pq);
30 
31 //检查队列是否为空,为空返回true,否则返回false
32 bool QueueIsEmpty(const Queue *pq);
33 
34 //确定队列的项数
35 int QueueItemCount(const Queue *pq);
36 
37 //在队列末尾添加项:item是被添加在队列末尾的项
38 bool EnQueue(Item item, Queue *pq);
39 
40 //在队列开头删除项:队列不为空,队列首位item将被拷贝到*pitem中
41 bool DeQueue(Item *pitem, Queue *pq);
42 
43 //清空队列
44 void EmptyTheQueue(Queue *pq);
45 
46 #endif

list.h

queue.h

图片 5图片 6

图片 7图片 8

  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 }
 1 /*----------------------------
 2     queue.c -- Queue 实现
 3 ----------------------------*/
 4 
 5 #include <stdio.h>
 6 #include <stdlib.h>
 7 #include "queue.h"
 8 
 9 static void CopyToNode(const Item *pi, Node *pn)
10 {
11     pn->item = *pi;
12 }
13 
14 static void CopyToItem(const Node *pn, Item *pi)
15 {
16     *pi = pn->item;
17 }
18 
19 void InitializeQueue(Queue *pq)
20 {
21     pq->front = pq->rear = NULL;
22     pq->items = 0;
23 }
24 
25 bool QueueIsFull(const Queue *pq)
26 {
27     return pq->items == MAXQUEUE;
28 }
29 
30 bool QueueIsEmpty(const Queue *pq)
31 {
32     return pq->items == 0;
33 }
34 
35 int QueueItemCount(const Queue *pq)
36 {
37     return pq->items;
38 }
39 
40 bool EnQueue(Item item, Queue *pq)
41 {
42     if (QueueIsFull(pq)) return false;
43 
44     Node *pnew = (Node*)malloc(sizeof(Node));
45     if (pnew == NULL)
46     {
47         fprintf(stderr, "Unable to allocate memory!\n");
48         exit(EXIT_FAILURE);
49     }
50 
51     CopyToNode(&item, pnew);
52     pnew->next = NULL;
53 
54     if (QueueIsEmpty(pq))
55         pq->front = pnew;                //新添项位于队列头端
56     else
57         pq->rear->next = pnew;          //新添项链接到队列尾端
58 
59     pq->rear = pnew;                    //记录队列尾端的位置
60     ++(pq->items);                      //队列项数加1
61 
62     return true;
63 }
64 
65 bool DeQueue(Item *pitem, Queue *pq)
66 {
67     if (QueueIsEmpty(pq)) return false;
68 
69     CopyToItem(pq->front, pitem);
70 
71     Node *pt = pq->front;
72     pq->front = pt->next;
73     free(pt);
74     --(pq->items);
75 
76     if (QueueIsEmpty(pq)) pq->rear = NULL;
77 
78     return true;
79 }
80 
81 void EmptyTheQueue(Queue *pq)
82 {
83     Item dummy;
84     while (!QueueIsEmpty(pq)) DeQueue(&dummy, pq);
85 }

list.c

queue.c

图片 9图片 10

图片 11图片 12

 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 }
 1 /*---------------------------------------
 2     use_q.c -- 驱动程序测试 Queue 接口
 3 ---------------------------------------*/
 4 
 5 #include <stdio.h>
 6 #include "queue.h"
 7 
 8 int main()
 9 {
10     Queue line;
11     Item temp;
12     char ch;
13 
14     InitializeQueue(&line);
15 
16     puts("Testing the Queue interface. Type \"a\" to add a value, ");
17     puts("type \"d\" to delete a value, and type \"q\" to quit.");
18 
19     while ((ch = getchar()) != 'q')
20     {
21         if (ch != 'a' && ch != 'd') continue;    //忽略其他输出
22 
23         if (ch == 'a')        //add
24         {
25             printf("Integer to add: ");
26             scanf("%d", &temp);
27             
28             if (!QueueIsFull(&line))
29             {
30                 printf("Putting %d into queue\n", temp);
31                 EnQueue(temp, &line);
32             }
33             else
34                 puts("Queue is full!");
35         }
36         else                //delete
37         {
38             if (QueueIsEmpty(&line))
39                 puts("Nothing to delete!");
40             else
41             {
42                 DeQueue(&temp, &line);
43                 printf("Removing %d from queue\n", temp);
44             }
45         }
46 
47         printf("%d items in queue\n", QueueItemCount(&line));
48         puts("Type \"a\" to add, \"d\" to delete, \"q\" to quit;");
49     }
50 
51     EmptyTheQueue(&line);
52     puts("Bye!");
53 
54     return 0;
55 }

films3.c

use_q.c

图片 13

图片 14

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图