第17章 高级数据表示
17.1 研究数据表示
假设要编写一个程序，让用户输入一年内看过的电影，存储影片的信息。
可以使用结构储存电影，用结构数组存储多部电影。
但给数组分配空间时，会出现分配空间过大浪费或者分配空间过小不够用的问题。
使用动态内存(malloc)分配可以解决这个问题。
17.2 从数组到链表
struct file {
char title[TSIZE];
int rating;
struct film * next;
}
struct file *head;
链表看起来是一个特殊的结构，他包含自己的数据，还有下一个结构的地址. 另外有一个单独的head指针来标识开头地址。
用户输入时可以先给第一个结构分配内存空间，然后将他的next的地址赋值为NULL（空，因为现在他后面没有结构了）
在给第二个结构分配内存，然后将第一个结构的next指针指向第二个元素，将第二个元素的next设置为空......
具体用法见示例：
17.2.1 使用链表
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h> #define TSIZE 45 //片名大小 struct film { char title[TSIZE]; int rating; struct film * next; //指向链表的下一个结构 }; char * s_gets(char * st, int n); int main(void) { struct film * head = NULL; struct film * prev = NULL, *current = NULL; char input[TSIZE]; puts("输入第一部电影的名字："); while (s_gets(input, TSIZE) != NULL && input[0] != '\0') { current = (struct film *) malloc(sizeof(struct film)); if (head == NULL) head = current; else prev->next = current; current->next = NULL; strcpy(current->title, input); puts("输入评分<0-10>:"); scanf("%d", ¤t->rating); while (getchar() != '\n') continue; puts("输入下一部电影名字(直接回车可退出）"); prev = current; } //显示电影 if (head == NULL) printf("无数据."); else { printf("电影列表如下：\n"); current = head; while (current != NULL) { printf("电影:%s 评分:%d\n", current->title, current->rating); current = current->next; } } //释放内存 current = head; while (head != NULL) //此处和书不同，书上运行出错。我认为这里应该判断head是否NULL而不是current是否为NULL { current = head; head =head->next; free(current); } printf("BYE\n"); return 0; } char * s_gets(char * st, int n) { char * ret_val; char * find; ret_val = fgets(st, n, stdin); if (ret_val) { find = strchr(st, '\n');//查找换行符 if (find) *find = '\0'; //将换行符换成'\0' else while (getchar() != '\n') //处理输入行剩余的字符 continue; } return ret_val; }
17.3 抽象数据类型（ADT,abstract data tye）
用更系统的方法定义数据类型：
类型特指两类信息：属性和操作。 //容易想到C++的类
17.3.1 建立抽象
17.3.2 建立接口
接口有两个部分：数据和操作
//下面是链表是具体实现
//list.h
#pragma once #include<stdbool.h> /*特定程序的声明*/ #define TSIZE 45 //存储电影名的数组大小 struct film { char title[TSIZE]; int rating; }; /*一般类型定义*/ typedef struct film Item; typedef struct node { Item item; struct node * next; }Node; typedef Node * List; /*函数原型*/ /*操作： 初始化一个链表 */ /*前提条件： plist指向一个链表 */ /*后置条件： 链表初始化为空 */ void InitializeList(List * plist); /*操作： 确定链表是否为空定义，plist指向一个已初始化的链表 */ /*后置条件： 如果链表为空，返回ture；否则返回false */ bool ListIsEmpty(const List * plist); /*操作： 确定链表是否已满，plist指向一个已初始化的链表 */ /*后置条件： 如果链表已满，返回true；否则返回false */ bool ListIsFull(const List * plist); /*操作： 确定链表中的项数，plist指向一个已初始化的链表 */ /*后置条件： 返回链表中的项数 */ unsigned int ListItemCount(const List *plist); /*操作： 在链表的末尾添加项 */ /*前提条件： item是一个待添加至链表的项，plist指向一个已初始化的链表 */ /*后置条件： 如果可以，执行添加操作，返回true；否则返回false */ bool AddItem(Item item, List * plist); /*操作： 把函数作用于链表的每一项 */ /* plist指向一个已初始化的链表 */ /* pfun指向一个函数，该函数接受一个Item类型参数，无返回值 */ /*后置条件： pfun指向的函数作用于链表的每一项一次 */ void Traverse(const List*plist, void(*pfun)(Item item)); /*操作： 释放已分配的内存（如果有的话） */ /* plist指向一个已初始化的链表 */ /*后置条件： 释放为链表分配的内存，链表设置为空 */ void EmptyTheList(List * plist);
//list.cpp
#include<stdio.h> #include<stdlib.h> #include"list.h" static void CopyToNode(Item item, Node * pnode); void InitializeList(List * plist) { *plist = NULL; } bool ListIsEmpty(const List * plist) { if (*plist == NULL) return true; else return false; } bool ListIsFull(const List * plist) { Node * pt; bool full; pt = (Node *)malloc(sizeof(Node)); if (pt == NULL) full = true; else full = false; free(pt); return full; } unsigned int ListItemCount(const List * plist) { unsigned int count = 0; Node * pnode = *plist; while (pnode != NULL) { ++count; pnode = pnode->next; } return count; } bool AddItem(Item item, List * plist) { Node * pnew; Node * scan = *plist; pnew = (Node *)malloc(sizeof(Node)); if (pnew == NULL) return false; CopyToNode(item, pnew); pnew->next = NULL; if (scan == NULL) *plist = pnew; else { while (scan->next != NULL) scan = scan->next; scan->next = pnew; } return true; } void Traverse(const List * plist, void(*pfun)(Item item)) { Node * pnode = *plist; while (pnode!= NULL) { (*pfun)(pnode->item); pnode = pnode->next; } } void EmptyTheList(List * plist) { Node * psave; while (*plist != NULL) { psave = (*plist)->next; free(*plist); *plist = psave; } } static void CopyToNode(Item item, Node * pnode) { pnode->item = item; }
film3.c
/*film3.c */ /*与list.c一起编译 */ #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> #include<string.h> #include"list.h" void showMovies(Item item); char * s_gets(char * st, int n); int main(void) { List movies; Item temp; /*初始化 */ InitializeList(&movies); if (ListIsFull(&movies)) { fprintf(stderr, "无可用内存，告辞。\n"); exit(1); } /*获取用户输入 并存储*/ puts("输入第一个电影名称："); while (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '\0') { puts("输入你的评分<0-10>:"); scanf("%d", &temp.rating); while (getchar() != '\n') continue; if (AddItem(temp, &movies) == false) { fprintf(stderr, "分配内存出错\n"); break; } if (ListIsFull(&movies)) { puts("列表满了."); break; } puts("输入下一步电影名称(回车结束程序)"); } /*显示*/ if (ListIsEmpty(&movies)) printf("列表为空"); else { printf("Here is the movie list:\n"); Traverse(&movies, showMovies); } printf("你输入了%d个电影\n", ListItemCount(&movies)); /*清理*/ EmptyTheList(&movies); printf("再见\n"); return 0; } void showMovies(Item item) { printf("Movie: %s Rating: %d\n", item.title, item.rating); } char * s_gets(char * st, int n) { char * ret_val; char * find; ret_val = fgets(st, n, stdin); if (ret_val) { find = strchr(st, '\n');//查找换行符 if (find) *find = '\0'; //将换行符换成'\0' else while (getchar() != '\n') //处理输入行剩余的字符 continue; } return ret_val; }
