復(fù)習(xí)題
-
定義一種數(shù)據(jù)類型設(shè)計那些內(nèi)容?
- 如何存儲數(shù)據(jù)
- 如何對數(shù)據(jù)操作(管理數(shù)據(jù)的函數(shù))
-
什么是ADT
- ADT(Abstract Data Type)抽象數(shù)據(jù)類型，是對一種類型屬性集和可以對該類型進(jìn)行的操作的正式定義瘪校。ADT應(yīng)該用一般語言表示澄暮，而不是某種特殊的計算機語言，而且不應(yīng)該包含實現(xiàn)細(xì)節(jié)。
-
QueueIsEmpty()函數(shù)接受一個指向queue結(jié)構(gòu)的指針作為參數(shù)赏寇，但是也可以將其編寫成一個queue結(jié)構(gòu)作為參數(shù)吉嫩。這兩種方式有什么優(yōu)點。
1.傳結(jié)構(gòu)優(yōu)點: 可以查看里面所有東西并且不會改變其中的內(nèi)容.
缺點: 函數(shù)使用的是原始數(shù)據(jù)的副本嗅定。必須要有足夠的空間取存放他自娩。會浪費大量空間和時間- 傳地址的優(yōu)點: 快、迅速
缺點: 可能會改變里面的數(shù)據(jù)渠退，操作比較麻煩忙迁。不過可以const限定符解決問題
- 傳地址的優(yōu)點: 快、迅速
編程練習(xí)
1仿照書上的ADT main.h是書上的就不發(fā)了
#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;
/*函數(shù)原型*/
/*操作: 初始化一個鏈表*/
/*前提條件: plist指向一個鏈表*/
/*后置條件: 鏈表初始化為空*/
void InitializeList(List * plist);
/*操作: 確定鏈表是否為空定義，plist指向一個已初始化的鏈表*/
/*后置條件: 如果鏈表為空碎乃，該函數(shù)返回true;否則返回false*/
bool ListIsEmpty(const List * plist);
/*操作: 確定鏈表是否已滿姊扔，plist指向一個已初始化的鏈表*/
/*后置條件: 如果鏈表已滿，該函數(shù)返回真;否則返回假*/
bool ListIsFull(const List * plist);
/*操作: 確定鏈表中的項數(shù)梅誓，plist指向一個已初始化的鏈表*/
/*后置條件: 該函數(shù)返回鏈表中的項數(shù)*/
unsigned int ListItemCount(const List * plist);
/*操作: 在鏈表末尾添加項*/
/*前提條件: item是一個待添加至鏈表的項,plist指向一個已經(jīng)初始化的鏈表*/
/*后置條件: 如果可以恰梢，該函數(shù)在鏈表末尾添加一個項，且返回true梗掰；否則返回false*/
bool AddItem( Item item, List * plist);
/*操作: 把函數(shù)作用域鏈表中的每一項*/
/* plist指向一個已初始化的鏈表*/
/* pfun指向一個函數(shù)嵌言，該函數(shù)接受一個Item類型的參數(shù)，且無返回值*/
/*后置條件: pfun指向的函數(shù)作用于鏈表中的每一項一次*/
void Traverse(const List * plist, void(*pfun)(Item item));
/*操作: 釋放已分配的內(nèi)存(如果有的話)*/
/* plist指向一個已初始化的鏈表*/
/*后置條件: 釋放了位鏈表分配的所有內(nèi)容及穗，鏈表設(shè)置位空*/
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
/**
* 假設(shè)list.h(程序清單17.3)使用下面的list定義:
* typedef struct list
* {
* Node * head;
* Node * end;
* } List;
* 重寫list.c(程序清單17.5)中的函數(shù)以適應(yīng)新的定義摧茴，并通過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;
/*函數(shù)原型*/
/*操作: 初始化一個鏈表*/
/*前提條件: plist指向一個鏈表*/
/*后置條件: 鏈表初始化為空*/
void InitializeList(List * plist);
/*操作: 確定鏈表是否為空定義，plist指向一個已初始化的鏈表*/
/*后置條件: 如果鏈表為空埂陆，該函數(shù)返回true;否則返回false*/
bool ListIsEmpty(const List * plist);
/*操作: 確定鏈表是否已滿苛白，plist指向一個已初始化的鏈表*/
/*后置條件: 如果鏈表已滿，該函數(shù)返回真;否則返回假*/
bool ListIsFull(const List * plist);
/*操作: 確定鏈表中的項數(shù)焚虱，plist指向一個已初始化的鏈表*/
/*后置條件: 該函數(shù)返回鏈表中的項數(shù)*/
unsigned int ListItemCount(const List * plist);
/*操作: 在鏈表末尾添加項*/
/*前提條件: item是一個待添加至鏈表的項,plist指向一個已經(jīng)初始化的鏈表*/
/*后置條件: 如果可以购裙，該函數(shù)在鏈表末尾添加一個項，且返回true鹃栽；否則返回false*/
bool AddItem( Item * item, List * plist);
/*操作: 把函數(shù)作用域鏈表中的每一項*/
/* plist指向一個已初始化的鏈表*/
/* pfun指向一個函數(shù)躏率，該函數(shù)接受一個Item類型的參數(shù)，且無返回值*/
/*后置條件: pfun指向的函數(shù)作用于鏈表中的每一項一次*/
void Traverse(const List * plist, void(*pfun)(Item item));
/*操作: 釋放已分配的內(nèi)存(如果有的話)*/
/* plist指向一個已初始化的鏈表*/
/*后置條件: 釋放了位鏈表分配的所有內(nèi)容谍咆，鏈表設(shè)置位空*/
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;
}
//注意：感覺刪除那里不得行禾锤，請大家教教
