第 17 章 高级数据表示(链表)
2018-12-04 07:12:01来源:博客园 阅读 ()
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 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 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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:7-45 找完数(20 分)
下一篇:整数编码
- 关于各种不同开发语言之间数据加密方法(DES,RSA等)的互通的 2020-06-07
- C++ 共用体 2020-06-05
- 数据结构—链表 2020-05-29
- Qt做Tcp数据传输 2020-05-26
- 图 2020-05-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash