复习题

定义一种数据类型设计那些内容?
- 如何存储数据
- 如何对数据操作(管理数据的函数)
什么是ADT
- ADT(Abstract Data Type)抽象数据类型，是对一种类型属性集和可以对该类型进行的操作的正式定义。ADT应该用一般语言表示，而不是某种特殊的计算机语言，而且不应该包含实现细节。
QueueIsEmpty()函数接受一个指向queue结构的指针作为参数，但是也可以将其编写成一个queue结构作为参数。这两种方式有什么优点。

1.传结构优点: 可以查看里面所有东西并且不会改变其中的内容.
缺点: 函数使用的是原始数据的副本。必须要有足够的空间取存放他。会浪费大量空间和时间
1. 传地址的优点: 快、迅速
  缺点: 可能会改变里面的数据，操作比较麻烦。不过可以const限定符解决问题

编程练习

1仿照书上的ADT main.h是书上的就不发了

#ifndef STACK_H_
#define STACK_H_
#include <stdbool.h>

#define TSIZE 40

typedef struct film
{
    char title[TSIZE];
    int rating;
} Item;

typedef struct node
{
    Item item;
    struct node * front;
    struct node * next;    //主要就是加个链接
} Node;

typedef Node * List;

/*函数原型*/

/*操作:                     初始化一个链表*/
/*前提条件:                  plist指向一个链表*/
/*后置条件:                 链表初始化为空*/
void InitializeList(List * plist);

/*操作:                     确定链表是否为空定义，plist指向一个已初始化的链表*/
/*后置条件:                 如果链表为空，该函数返回true;否则返回false*/
bool ListIsEmpty(const List * plist);

/*操作:                     确定链表是否已满，plist指向一个已初始化的链表*/
/*后置条件:                 如果链表已满，该函数返回真;否则返回假*/
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);

#endif

#include <stdio.h>
#include "tree.h"
#include <stdlib.h>
#include <string.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)
{
    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)
    {
        pnew->front = NULL;
        *plist = pnew;
    }
    else
    {
        pnew->front = scan;
        while (scan->next != NULL)
        {   
            scan = scan->next;
            pnew->front = scan;
        }
        scan->next = pnew;
    }

    return true;
}

void Traverse(const List * plist, void(*pfun)(Item item))
{
    Node * pnode = *plist;
    Node * rnode;

    while (pnode != NULL)
    {
        rnode = pnode;
        (*pfun)(pnode->item);
        pnode = pnode->next;
    }

    while (rnode != NULL)
    {
        (*pfun)(rnode->item);
        rnode = rnode->front;
    }
}

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;
}

不是递归

2

list.h

/**
 *  假设list.h(程序清单17.3)使用下面的list定义:
 *  typedef struct list
 *  {
 *      Node * head;
 *      Node * end;
 *  } List;
 *  重写list.c(程序清单17.5)中的函数以适应新的定义，并通过films.c(程序清单17.4)测试
 *  最终的代码.
*/
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h>

#define TSIZE 40

typedef struct film
{
    char title[TSIZE];
    int rating;
} Item;

typedef struct node
{
    Item item;
    struct node * next;
} Node;

typedef struct list
{
    Node * head;        /*指向队列首项的指针    */
    Node * end;         /*指向队列尾项的指针    */
} List;


/*函数原型*/

/*操作:                     初始化一个链表*/
/*前提条件:                  plist指向一个链表*/
/*后置条件:                 链表初始化为空*/
void InitializeList(List * plist);

/*操作:                     确定链表是否为空定义，plist指向一个已初始化的链表*/
/*后置条件:                 如果链表为空，该函数返回true;否则返回false*/
bool ListIsEmpty(const List * plist);

/*操作:                     确定链表是否已满，plist指向一个已初始化的链表*/
/*后置条件:                 如果链表已满，该函数返回真;否则返回假*/
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);

#endif

list.c

#include <stdio.h>
#include "lish.h"
#include <stdlib.h>
#include <string.h>

static void CopyToNode(Item * item, Node * pnode);
static void DeleteAllNodes(Node * head);
void InitializeList(List * plist)
{
    plist->head = plist->end = NULL;
}

bool ListIsEmpty(const List * plist)
{
    if (plist->head == 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)
{
    int count = 0;
    Node * pnode = plist->head;

    while (pnode != NULL)
    {
        count++;
        pnode = pnode->next;
    }
    
    return count;
}

bool AddItem( Item * item, List * plist)
{
    Node * pnew;
    pnew = (Node *) malloc(sizeof(Node));
    if (pnew == NULL)
        return false;
    
    CopyToNode(item, pnew);
    pnew->next = NULL;
    if (ListIsEmpty(plist))
        plist->head = pnew;
    else
        plist->end->next = pnew;
    plist->end = pnew;

    return true;
}

void Traverse(const List * plist, void(*pfun)(Item item))
{
    Node * pnode = plist->head;
    while (pnode != NULL)
    {
        (*pfun)(pnode->item);
        pnode = pnode->next;
    }
}

void EmptyTheList(List * plist)
{
    if (plist != NULL)
        DeleteAllNodes(plist->head);
    plist->head = NULL;
    plist->end = NULL;
}

static void DeleteAllNodes(Node * head)
{
    Node * pright;
    while (head != NULL)
    {
        pright = head->next;
        free(head);
        head = pright;
    }  
}



static void CopyToNode(Item * item, Node * pnode)
{
    pnode->item = *item;
}
//注意：感觉删除那里不得行，请大家教教

第17章高级数据表示

第17章高级数据表示

复习题

编程练习

1仿照书上的ADT main.h是书上的就不发了

2

推荐阅读更多精彩内容

第17章 高级数据表示

复习题

编程练习

1仿照书上的ADT main.h是书上的就不发了

2

推荐阅读更多精彩内容

第17章高级数据表示