C primer plus 学习笔记第17章高级数据表示-阿里云开发者社区

第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", &current->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;
}