本文使用c語言定義并實現list、queue、tree抽象數據類型，代碼有詳盡注釋，可以通過代碼熟悉原理并運用數據結構。

0.ADT基礎知識

類型包括兩類信息，屬性和操作。在編程時，根據編程問題匹配合適的數據類型。

定義一個新的數據類型，有三個步驟：

提供類型屬性和相關操作的抽象描述。描述不依賴于特定實現和特定編程語言。

開發一個實現ADT的編程接口。描述如何表示數據、描述實現ADT操作的函數，在c中，可以提供結構定義和操控該結構的函數原型。

編寫代碼實現接口。

1.list(鏈表)的實現

根據三個步驟，定義一個list：
1.建立抽象：

• 類型名：簡單鏈表。
• 類型屬性：可存儲一系列項。
• 類型操作：初始化鏈表為空、確定鏈表為空、確定鏈表已滿、確定鏈表中的項數、在鏈表末尾添加項、遍歷鏈表，處理鏈表中的項、清空鏈表。

2.建立接口：見list.h

建立接口后，可以使用這個接口編寫程序，而不必知道具體實現細節，見film3.c

3.實現接口：見list.c

1.1 list.h

/* list.h -- header file for a simple list type */ #ifndef LIST_H_ #define LIST_H_ #include <stdbool.h> /* C99 feature *//* 特定程序的聲明 */#define TSIZE 45 /* 存儲電影名的數組大小 */ struct film {char title[TSIZE];int rating; };/* 一般類型定義 */typedef struct film Item; /* 如果以后需要其他數據形式的鏈表，*/ /* 可以重新定義Item類型，不必更改其余的接口定義 */typedef struct node {Item item;struct node * next; } Node;/* 每一個鏈節叫做節點（Node） */typedef Node * List; /* 指向鏈表開始處的指針，List作為該類型的指針名*//* 函數原型 */ /* 前提條件：調用該函數前應具備的條件 */ /* 后置條件：執行完該函數后的情況 *//* 操作: 初始化一個鏈表 */ /* 前提條件: plist 指向一個鏈表 */ /* 后置條件: 鏈表初始化為空 */ void InitializeList(List * plist); /* 該函數的參數是指向鏈表的指針，*/ /* 如果函數想要修改一個參數，那么該參數的類型應該是指向相應類型的指針 */ /* 調用時InitializeList(&movies) *//* operation: 確定鏈表是否為空 */ /* plist 指向一個已初始化的鏈表 */ /* postconditions: 如果鏈表為空，函數返回true */ /* 否則返回false */ bool ListIsEmpty(const List *plist);/* operation: 確定鏈表是否已滿 */ /* plist points to an initialized list */ /* postconditions: function returns True if list is full */ /* and returns False otherwise */ bool ListIsFull(const List *plist);/* operation: 確定鏈表中的項數 */ /* plist points to an initialized list */ /* postconditions: 函數返回鏈表中的項數 */ unsigned int ListItemCount(const List *plist);/* operation: 在鏈表的末尾添加項 */ /* preconditions: item 是一個待添加至鏈表的項 */ /* plist 指向一個已初始化的鏈表 */ /* postconditions: 如果可以, 函數在鏈表末尾添加一個項 */ /* 且返回True; 否則返回False */ bool AddItem(Item item, List * plist);/* operation: 把函數作用于鏈表中的每一項 */ /* plist 指向一個已初始化的鏈表 */ /* pfun 指向一個函數，該函數接受一個 */ /* Item類型的參數，且無返回值 */ /* postcondition: pfun指向的函數作用于鏈表中的每個項一次 */ void Traverse (const List *plist, void (* pfun)(Item item) );/* operation: 釋放已分配的內存(如果有的話) */ /* plist points to an initialized list */ /* postconditions: 釋放了為鏈表分配的所有內存 */ /* 鏈表設置為空 */ void EmptyTheList(List * plist);#endif

1.2 list.c

/* list.c -- 支持鏈表操作的函數 */ #include <stdio.h> #include <stdlib.h> #include "list.h"/* 局部函數原型 */ /* 該函數是實現的一部分，不是接口的一部分，*/ /* 使用static存儲類別說明符將其隱藏在list.c文件夾中 */ static void CopyToNode(Item item, Node * pnode);/* 接口函數 */ /* 把鏈表設置為空 */ void InitializeList(List * plist) {* plist = NULL; }/* 如果鏈表為空，返回true */ bool ListIsEmpty(const List * plist) {if (*plist == NULL)return true;elsereturn false; }/* 如果鏈表已滿，返回True */ bool ListIsFull(const List * plist) {Node * pt;bool full;/* 添加一個節點，分配一次內存 */pt = (Node *) malloc(sizeof(Node));if (pt == NULL)/* 系統把內存分配完了，此時表示鏈表滿了 */full = true;elsefull = 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; }/* 創建存儲項的節點 */ /* 并將其添加至由plist指向的鏈表末尾 */ 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; /* pnew 放在鏈表的開頭 */else{while (scan->next != NULL)scan = scan->next; /* 找到鏈表的末尾 */scan->next = pnew; /* 把pnew添加到鏈表的末尾 */}return true; }/* 訪問每個節點并執行pfun指向的函數 */ void Traverse (const List * plist, void (* pfun)(Item item) ) {Node * pnode = *plist; /* 設置鏈表的開始 */while (pnode != NULL){(*pfun)(pnode->item); /* 把函數應用于鏈表中的項 */pnode = pnode->next; /* 前進到下一項 */} }/* 釋放由malloc()分配的內存 */ /* 設置鏈表指針為 NULL */ 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; /* 拷貝結構 */ }

1.3 film3.c

使用接口編寫程序，但是不必知道具體的實現細節。

/* films3.c -- using an ADT-style linked list */ /* compile with list.c */ #include <stdio.h> #include <stdlib.h> /* prototype for exit() */ #include "list.h" /* defines List, Item */ 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,"No memory available! Bye!\n");exit(1);}/* 獲取用戶輸入并存儲 */puts("Enter first movie title:");while (s_gets(temp.title, TSIZE) != NULL && temp.title[0] != '\0'){puts("Enter your rating <0-10>:");scanf("%d", &temp.rating);while(getchar() != '\n')continue;if (AddItem(temp, &movies)==false){fprintf(stderr,"Problem allocating memory\n");break;}if (ListIsFull(&movies)){puts("The list is now full.");break;}puts("Enter next movie title (empty line to stop):");}/* 顯示 */if (ListIsEmpty(&movies))printf("No data entered. ");else{printf ("Here is the movie list:\n");Traverse(&movies, showmovies);}printf("You entered %d movies.\n", ListItemCount(&movies));/* 清理 */EmptyTheList(&movies);printf("Bye!\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) // 如果地址不是NULL,*find = '\0'; // 在此處放置一個空字符elsewhile (getchar() != '\n')continue; // 處理輸入行的剩余內容}return ret_val; }

2.queue(隊列)的實現

隊列是具有兩個特殊屬性的鏈表，1.新項只能添加到鏈表的末尾，2.只能從鏈表的開頭移除項。 先進先出的數據形式。

根據三個步驟，定義一個list：
1.建立抽象：

• 類型名：隊列。
• 類型屬性：可存儲一系列項。
• 類型操作：初始化隊列為空、確定隊列為空、確定隊列已滿、確定隊列中的項數、在隊列末尾添加項、在隊列開頭刪除或恢復項、清空隊列。

2.建立接口：見queue.h

3.實現接口：見queue.c

4.測試接口：見use_q.c

5.使用隊列：見mall.c

2.1 queue.h

/* queue.h -- interface for a queue */ #ifndef _QUEUE_H_ #define _QUEUE_H_ #include <stdbool.h>// 在這里插入Item類型的定義 // FOR EXAMPLE, //typedef int Item; // for use_q.c // OR typedef struct item {int gumption; int charisma;} Item; // OR (for mall.c) /**/typedef struct item{long arrive; // 一位顧客加入隊列的時間int processtime; // 該顧客咨詢時花費的時間} Item; /**/#define MAXQUEUE 10typedef struct node {Item item;struct node * next; } Node;typedef struct queue {Node * front; /* 指向隊列首項的指針 */Node * rear; /* 指向隊列尾項的指針 */int items; /* 隊列中的項數 */ } Queue;/* operation: 初始化隊列 */ /* 前提條件: pq 指向一個隊列 */ /* 后置條件: 隊列被初始化為空 */ void InitializeQueue(Queue * pq);/* operation: 檢查隊列是否已滿 */ /* precondition: pq 指向之前被初始化的隊列 */ /* postcondition: 如果隊列已滿則返回true，否則返回false */ bool QueueIsFull(const Queue * pq);/* operation: 檢查隊列是否為空 */ /* precondition: pq 指向之前被初始化的隊列 */ /* postcondition: 如果隊列為空則返回true，否則返回false */ bool QueueIsEmpty(const Queue *pq);/* operation: 確定隊列中的項數 */ /* precondition: pq points to previously initialized queue */ /* postcondition: 返回隊列中的項數 */ int QueueItemCount(const Queue * pq);/* operation: 在隊列末尾添加項 */ /* precondition: pq 指向之前被初始化的隊列 */ /* item是要被添加在隊列末尾的項 */ /* postcondition: 如果隊列不為空，item將被添加在隊列的末尾， */ /* 函數返回true； */ bool EnQueue(Item item, Queue * pq);/* operation: 從隊列的開頭刪除項 */ /* precondition: pq 指向之前被初始化的隊列 */ /* postcondition: 如果隊列不為空， */ /* 隊列首端的item將被拷貝到*pitem中， */ /* 并被刪除，且函數返回True */ /* 如果該操作使隊列為空， */ /* 則重置隊列為空 */ /* 如果隊列在操作前為空， */ /* 該函數返回false */ bool DeQueue(Item *pitem, Queue * pq);/* operation: 清空隊列 */ /* precondition: pq指向之前被初始化的隊列 */ /* postconditions: 隊列被清空 */ void EmptyTheQueue(Queue * pq);#endif

2.2 queue.c

/* queue.c -- the Queue type implementation*/ #include <stdio.h> #include <stdlib.h> #include "queue.h"/* local functions */ static void CopyToNode(Item item, Node * pn); static void CopyToItem(Node * pn, Item * pi);void InitializeQueue(Queue * pq) {pq->front = pq->rear = NULL;pq->items = 0; }bool QueueIsFull(const Queue * pq) {return pq->items == MAXQUEUE; }bool QueueIsEmpty(const Queue * pq) {return pq->items == 0; }int QueueItemCount(const Queue * pq) {return pq->items; }bool EnQueue(Item item, Queue * pq) {Node * pnew;if (QueueIsFull(pq))return false;pnew = (Node *) malloc( sizeof(Node));if (pnew == NULL)/*如果函數不能為節點分配內存，程序運行內存不足*/{fprintf(stderr,"Unable to allocate memory!\n");exit(1);}CopyToNode(item, pnew);pnew->next = NULL;if (QueueIsEmpty(pq))pq->front = pnew; /* 項位于隊列首端 */elsepq->rear->next = pnew; /* 鏈接到隊列尾端 */pq->rear = pnew; /* 記錄隊列尾端位置 */pq->items++; /* 隊列項數加1 */return true; }bool DeQueue(Item * pitem, Queue * pq) {Node * pt;if (QueueIsEmpty(pq))return false;CopyToItem(pq->front, pitem);pt = pq->front;pq->front = pq->front->next;/*重置首指針指向隊列中的下一個項*/free(pt);/*釋放空出的節點使用的內存空間*/pq->items--;if (pq->items == 0)//如果刪除的是最后一項pq->rear = NULL;//首指針和尾指針都置為NULLreturn true; }/* 清空隊列 */ void EmptyTheQueue(Queue * pq) {Item dummy;while (!QueueIsEmpty(pq))DeQueue(&dummy, pq); }/* Local functions */static void CopyToNode(Item item, Node * pn) {pn->item = item; }static void CopyToItem(Node * pn, Item * pi) {*pi = pn->item; }

2.3 use_q.c

/* use_q.c -- driver testing the Queue interface */ /* compile with queue.c */ #include <stdio.h> #include "queue.h" /* defines Queue, Item */int main(void) {Queue line;Item temp;char ch;InitializeQueue(&line);puts("Testing the Queue interface. Type a to add a value,");puts("type d to delete a value, and type q to quit.");while ((ch = getchar()) != 'q'){if (ch != 'a' && ch != 'd') /* ignore other input */continue;if ( ch == 'a'){printf("Integer to add: ");scanf("%d", &temp);if (!QueueIsFull(&line)){printf("Putting %d into queue\n", temp);EnQueue(temp,&line);}elseputs("Queue is full!");}else{if (QueueIsEmpty(&line))puts("Nothing to delete!");else{DeQueue(&temp,&line);printf("Removing %d from queue\n", temp);}}printf("%d items in queue\n", QueueItemCount(&line));puts("Type a to add, d to delete, q to quit:");}EmptyTheQueue(&line);puts("Bye!");return 0; }

2.4 mall.c

有一個提供快樂的攤位，顧客可以購買1分鐘、2分鐘或3分鐘的快樂。為確保交通順暢，每個攤位前排隊等待的顧客最多為10人。假設顧客隨機出現，并且他們花費的時間也是隨機選擇的(1\2\3分鐘)，那么該攤位平均每小時接待多少名顧客？每位顧客平均花多長時間？排隊等待的顧客平均有幾人？

// mall.c -- use the Queue interface // compile with queue.c #include <stdio.h> #include <stdlib.h> // for rand() and srand() #include <time.h> // for time() #include "queue.h" // change Item typedef #define MIN_PER_HR 60.0bool newcustomer(double x); // 是否有新顧客來? Item customertime(long when); // 設置顧客參數int main(void) {Queue line;Item temp; // 新的顧客數據int hours; // 模擬的小時數int perhour; // 每小時平均多少位顧客long cycle, cyclelimit; // 循環計數器、 計數器的上限long turnaways = 0; // 因隊列已滿被拒的顧客數量long customers = 0; // 加入隊列的顧客數量long served = 0; // 在模擬期間到訪過攤位的顧客數量long sum_line = 0; // 累計的隊列總長int wait_time = 0; // 從當前到攤位空閑所需時間double min_per_cust; // 顧客到來的平均時間long line_wait = 0; // 隊列累計的等待時間 InitializeQueue(&line);srand((unsigned int) time(0)); // rand()隨機初始化puts("Case Study: Sigmund Lander's Advice Booth");puts("Enter the number of simulation hours:");scanf("%d", &hours);cyclelimit = MIN_PER_HR * hours;puts("Enter the average number of customers per hour:");scanf("%d", &perhour);min_per_cust = MIN_PER_HR / perhour;for (cycle = 0; cycle < cyclelimit; cycle++)//每次迭代對應一分鐘的行為{if (newcustomer(min_per_cust))//如果1分鐘內有顧客到來{if (QueueIsFull(&line))turnaways++;//被拒的顧客數量else{customers++;temp = customertime(cycle);/*設置temp結構中的arrive和processtime成員*/EnQueue(temp, &line);}}if (wait_time <= 0 && !QueueIsEmpty(&line)){//如果隊列不為空且前面的顧客沒有咨詢，則刪除隊列首端的項DeQueue (&temp, &line);wait_time = temp.processtime;//該顧客咨詢時花費的時間line_wait += cycle - temp.arrive;//到目前為止，隊列中所有顧客的等待總時間served++;//咨詢過的顧客數量}if (wait_time > 0)//完成當前顧客的需求所需的時間大于0wait_time--;sum_line += QueueItemCount(&line);//目前為止統計的隊列長度}if (customers > 0){printf("customers accepted: %ld\n", customers);printf(" customers served: %ld\n", served);printf(" turnaways: %ld\n", turnaways);printf("average queue size: %.2f\n",(double) sum_line / cyclelimit);printf(" average wait time: %.2f minutes\n",(double) line_wait / served);}elseputs("No customers!");EmptyTheQueue(&line);puts("Bye!");return 0; }// x = 顧客到來的平均時間(單位：分鐘) // 如果1分鐘內有顧客到來，則返回true bool newcustomer(double x) {if (rand() * x / RAND_MAX < 1)return true;elsereturn false; }// when是顧客到來的時間 // 該函數返回一個Item結構，該顧客到達的時間設置成when // 咨詢時間設置為1 - 3的隨機值 Item customertime(long when) {Item cust;cust.processtime = rand() % 3 + 1;cust.arrive = when;return cust; }

3.tree(二叉查找樹)的實現

訪問元素有兩種，隨機訪問：使用數組下標直接訪問該數組中的任意元素；順序訪問：對于鏈表而言，必須從鏈表首節點開始，逐個節點移動到要訪問的節點。
用數組可以實現二分查找，因為可以使用數組下標確定數組中任意部分的中點。但是鏈表只支持順序訪問，不提供跳至中間節點的方法，所以鏈表中不能使用二分查找。

有一種數據形式的需求，既支持頻繁插入和刪除項，又支持頻繁查找。此時需要二叉查找樹。

根據三個步驟，定義一個二叉樹：

該定義假設二叉樹不包含相同的項。

1.建立抽象：

類型名：二叉查找樹。

類型屬性：

• 二叉樹要么是空節點的集合(空樹)，要么是有一個根節點的節點集合。
• 每個節點都有兩個子樹，叫做左子樹和右子樹
• 每個子樹本身也是一個二叉樹，也可能是空樹
• 二叉查找樹是一個有序的二叉樹，每個節點包含一個項。
• 左子樹的所有項都在根節點項的前面，右子樹所有項都在根節點項的后面

類型操作：初始化樹為空、確定樹是否為空、確定樹是否已滿、確定樹中的項數、在樹中添加一個項、在樹中刪除一個項、在樹中查找一個項、在樹種訪問一個項、清空樹。

2.建立接口：見tree.h

3.實現接口：見tree.c

4.使用二叉樹：見petclub.c

3.1 tree.h

/* tree.h -- binary search tree 二叉查找樹 */ /* 樹中不允許有重復的項 */ #ifndef _TREE_H_ #define _TREE_H_ #include <stdbool.h>/* 根據情況重新定義Item */ #define SLEN 20 typedef struct item {char petname[SLEN];char petkind[SLEN]; } Item;#define MAXITEMS 10typedef struct trnode {Item item;struct trnode * left; /* 指向左分支的指針 */struct trnode * right; /* 指向右分支的指針 */ } Trnode;typedef struct tree {Trnode * root; /* 指向根節點的指針 */int size; /* 樹的項數 */ } Tree;/* 函數原型 *//* 操作: 把樹初始化為空 */ /* 前提條件: ptree 指向一個樹 */ /* 后置條件: 樹被初始化為空 */ void InitializeTree(Tree * ptree);/* operation: 確定樹是否為空 */ /* preconditions: ptree points to a tree */ /* postconditions: 如果樹為空，函數返回true */ /* 否則返回false */ bool TreeIsEmpty(const Tree * ptree);/* operation: 確定樹是否已滿 */ /* preconditions: ptree points to a tree */ /* postconditions: function returns true if tree is */ /* full and returns false otherwise */ bool TreeIsFull(const Tree * ptree);/* operation: 確定樹的項數 */ /* preconditions: ptree points to a tree */ /* postconditions: 返回樹的項數 */ int TreeItemCount(const Tree * ptree);/* operation: 在樹中添加一個項 */ /* preconditions: pi 是待添加項的地址 */ /* ptree 指向一個已初始化的樹 */ /* postconditions: 如果可以添加，該函數將在樹中添加一個項 */ /* 并返回true，否則返回false */ bool AddItem(const Item * pi, Tree * ptree);/* operation: 在樹中查找一個項 */ /* preconditions: pi指向一個項 */ /* ptree 指向一個已初始化的樹 */ /* postconditions: 如果在樹中找到指定項，該函數返回true */ /* 否則返回false */ bool InTree(const Item * pi, const Tree * ptree);/* operation: 從樹中刪除一個項 */ /* preconditions: pi 是刪除項的地址 */ /* ptree 指向一個已初始化的樹 */ /* postconditions: 如果在樹中成功刪除一個項，該函數返回true */ /* 否則返回false*/ bool DeleteItem(const Item * pi, Tree * ptree);/* operation: 把函數應用于樹中的每一項 */ /* preconditions: ptree 指向一個樹 */ /* pfun 指向一個函數 */ /* 該函數接受一個Item類型的參數，并無返回值 */ /* postcondition: pfun指向的這個函數為樹中的每一項執行一次 */ void Traverse (const Tree * ptree, void (* pfun)(Item item));/* operation: 刪除樹中的所有內容 */ /* preconditions: ptree指向一個已初始化的樹 */ /* postconditions: 樹為空 */ void DeleteAll(Tree * ptree);#endif

3.2 tree.c

/* tree.c -- tree support functions */ #include <string.h> #include <stdio.h> #include <stdlib.h> #include "tree.h"/* 局部數據類型 */ typedef struct pair {Trnode * parent;Trnode * child; } Pair;/* 局部函數的原型 */ static Trnode * MakeNode(const Item * pi); static bool ToLeft(const Item * i1, const Item * i2); static bool ToRight(const Item * i1, const Item * i2); static void AddNode (Trnode * new_node, Trnode * root); static void InOrder(const Trnode * root, void (* pfun)(Item item)); static Pair SeekItem(const Item * pi, const Tree * ptree); static void DeleteNode(Trnode **ptr); static void DeleteAllNodes(Trnode * ptr);/* 函數定義 */ void InitializeTree(Tree * ptree) {ptree->root = NULL;ptree->size = 0; }bool TreeIsEmpty(const Tree * ptree) {if (ptree->root == NULL)return true;elsereturn false; }bool TreeIsFull(const Tree * ptree) {if (ptree->size == MAXITEMS)return true;elsereturn false; }int TreeItemCount(const Tree * ptree) {return ptree->size; }bool AddItem(const Item * pi, Tree * ptree)/*在樹中添加一個項*/ {Trnode * new_node;if (TreeIsFull(ptree))/*首先檢查該樹是否有空間放下一個項*/{fprintf(stderr,"Tree is full\n");return false; /* 提前返回 */}if (SeekItem(pi, ptree).child != NULL){/*檢查該樹是否有該項，因為要求二叉樹中的項不能重復*/fprintf(stderr, "Attempted to add duplicate item\n");return false; /* 提前返回 */}new_node = MakeNode(pi); /* 指向新節點 */if (new_node == NULL){fprintf(stderr, "Couldn't create node\n");return false; /* 提前返回 */}/* 成功創建了一個新節點 */ptree->size++;/*找出應該把這個新節點放在樹中哪個位置*/if (ptree->root == NULL) /* 情況 1: 樹為空 */ptree->root = new_node; /* 新節點為樹的根節點 */else /* case 2: 樹不為空 */AddNode(new_node,ptree->root); /* 在樹中添加新節點 */return true; /* 成功返回 */ }/*在樹中查找一個項*/ bool InTree(const Item * pi, const Tree * ptree) {/*SeekItem函數返回一個結構，該函數可以與結構成員運算符一起使用*/return (SeekItem(pi, ptree).child == NULL) ? false : true; }bool DeleteItem(const Item * pi, Tree * ptree) {Pair look;/*SeekItem返回一個結構，*//*內含兩個指針，一個指針look.parent指向父節點，*//*一個指針look.child指向包含特定項的節點*/look = SeekItem(pi, ptree);if (look.child == NULL)/*表明未找到指定項*/return false;/*找到了指定項，分三種情況處理*//*第一種情況，該項在根節點中*/if (look.parent == NULL) /* 刪除根節點項 */DeleteNode(&ptree->root);/*第二種情況，待刪除節點是父節點的左子節點*/else if (look.parent->left == look.child)DeleteNode(&look.parent->left);/*第三種情況，待刪除節點是父節點的右子節點*/elseDeleteNode(&look.parent->right);ptree->size--;return true; }/*遍歷樹*/ void Traverse (const Tree * ptree, void (* pfun)(Item item)) {if (ptree != NULL)InOrder(ptree->root, pfun); }void DeleteAll(Tree * ptree) {if (ptree != NULL)DeleteAllNodes(ptree->root);/*釋放內存*//*處理Tree類型的結構，重置Tree類型結構成員，表明該樹為空*/ptree->root = NULL;ptree->size = 0; }/* local functions */ /*可以有不同的處理順序*/ static void InOrder(const Trnode * root, void (* pfun)(Item item)) {if (root != NULL){/*處理左子樹、處理項、處理右子樹*/InOrder(root->left, pfun);(*pfun)(root->item);InOrder(root->right, pfun);} }static void DeleteAllNodes(Trnode * root) {Trnode * pright;if (root != NULL){pright = root->right;/*存儲root->right，使其在釋放根節點后仍然可用*/DeleteAllNodes(root->left);free(root);DeleteAllNodes(pright);} }/*確定新節點的位置，添加新節點*/ static void AddNode (Trnode * new_node, Trnode * root) {/*如果新項應放在左子樹中，ToLeft()函數返回true*/if (ToLeft(&new_node->item, &root->item)){if (root->left == NULL) /* 空子樹 */root->left = new_node; /* 把節點添加到此處 */else/*把新項和左子節點中的項作比較，*//*以確定新項該放在該子節點的左子樹還是右子樹*/AddNode(new_node, root->left);/* 否則處理該子樹*/}/*如果新項應放在右子樹中，ToRight()函數返回true*/else if (ToRight(&new_node->item, &root->item)){if (root->right == NULL)root->right = new_node;elseAddNode(new_node, root->right);}else /* 不允許有重復項 */{fprintf(stderr,"location error in AddNode()\n");exit(1);} }/*ToLeft和ToRight函數依賴于Item類型的性質。*/ /*成員名按字母排序，如果名字相同，按其種類排序*/ /*如果種類相同，屬于重復項*/ static bool ToLeft(const Item * i1, const Item * i2) {int comp1;/*第一個字符串在第二個字符串前面，strcmp返回負數*//*兩個字符串相同，strcmp返回0*/if ((comp1 = strcmp(i1->petname, i2->petname)) < 0)return true;else if (comp1 == 0 &&strcmp(i1->petkind, i2->petkind) < 0 )return true;elsereturn false; }static bool ToRight(const Item * i1, const Item * i2) {int comp1;if ((comp1 = strcmp(i1->petname, i2->petname)) > 0)return true;else if (comp1 == 0 &&strcmp(i1->petkind, i2->petkind) > 0 )return true;elsereturn false; }/*處理動態內存分配和初始化節點*/ /*參數是指向新項的指針，返回值是指向新節點的指針*/ static Trnode * MakeNode(const Item * pi) {Trnode * new_node;new_node = (Trnode *) malloc(sizeof(Trnode));if (new_node != NULL){new_node->item = *pi;new_node->left = NULL;new_node->right = NULL;}return new_node; }/*查找特定項*/ /*返回的結構包含兩個指針，*/ /*一個指針指向包含項的節點，如果未找到指定項則為NULL*/ /*一個指針指向父節點(如果該節點為根節點，沒有父節點，則為NULL)*/ static Pair SeekItem(const Item * pi, const Tree * ptree) {Pair look;look.parent = NULL;/*開始時，設置look.child指向樹的根節點*/look.child = ptree->root;if (look.child == NULL)return look; /* 提前返回 */while (look.child != NULL){if (ToLeft(pi, &(look.child->item))){look.parent = look.child;look.child = look.child->left;//如果沒有找到匹配的項，look.child將被設置為NULL}else if (ToRight(pi, &(look.child->item))){look.parent = look.child;look.child = look.child->right;}else /* 如果前兩種情況都不滿足，則必定是相等的情況 */break; /* look.child 目標項的節點 */}return look; /* 成功返回 */ }static void DeleteNode(Trnode **ptr) /* ptr是指向待刪除節點指針的地址 */ /*那么*ptr就是把ptr地址里面的值取出來，就是指向待刪除節點的指針*/ /*要修改的指針本身是Trnode*類型，指向Trnode的指針*/ /*該函數的參數是該指針的地址，所以參數的類型是Trnode** */ {Trnode * temp;/*待刪除節點是沒有左子節點的節點*/if ( (*ptr)->left == NULL){temp = *ptr;*ptr = (*ptr)->right;free(temp);}/*沒有右子節點的節點*/else if ( (*ptr)->right == NULL){temp = *ptr;*ptr = (*ptr)->left;free(temp);}else /* 被刪除的節點有兩個子節點 */{/* 找到重新連接右子樹的位置 *//*沿左子樹的右支查找到第1個空位*/for (temp = (*ptr)->left; temp->right != NULL;temp = temp->right)continue;/*把待刪除節點的右子樹與該空位連接*/temp->right = (*ptr)->right;/*處理完之后重置待刪除節點的地址*//*重置之前先將*ptr存儲在temp中，釋放待刪除節點的內存*/temp = *ptr;*ptr =(*ptr)->left;free(temp); } }

3.3 petclub.c

/* petclub.c -- use a binary search tree */ #include <stdio.h> #include <string.h> #include <ctype.h> #include "tree.h"char menu(void); void addpet(Tree * pt); void droppet(Tree * pt); void showpets(const Tree * pt); void findpet(const Tree * pt); void printitem(Item item); void uppercase(char * str); char * s_gets(char * st, int n);int main(void) {Tree pets;char choice;InitializeTree(&pets);while ((choice = menu()) != 'q'){switch (choice){case 'a' : addpet(&pets);break;case 'l' : showpets(&pets);break;case 'f' : findpet(&pets);break;case 'n' : printf("%d pets in club\n",TreeItemCount(&pets));break;case 'd' : droppet(&pets);break;default : puts("Switching error");}}DeleteAll(&pets);puts("Bye.");return 0; }char menu(void) {int ch;puts("Nerfville Pet Club Membership Program");puts("Enter the letter corresponding to your choice:");puts("a) add a pet l) show list of pets");puts("n) number of pets f) find pets");puts("d) delete a pet q) quit");while ((ch = getchar()) != EOF){while (getchar() != '\n') /* 處理輸入行的剩余內容 */continue;ch = tolower(ch);if (strchr("alrfndq",ch) == NULL)puts("Please enter an a, l, f, n, d, or q:");elsebreak;}if (ch == EOF) /* 使程序退出 */ch = 'q';return ch; }void addpet(Tree * pt) {Item temp;if (TreeIsFull(pt))puts("No room in the club!");else{puts("Please enter name of pet:");s_gets(temp.petname,SLEN);puts("Please enter pet kind:");s_gets(temp.petkind,SLEN);uppercase(temp.petname);uppercase(temp.petkind);AddItem(&temp, pt);} }void showpets(const Tree * pt) {if (TreeIsEmpty(pt))puts("No entries!");elseTraverse(pt, printitem); }void printitem(Item item) {printf("Pet: %-19s Kind: %-19s\n", item.petname,item.petkind); }void findpet(const Tree * pt) {Item temp;if (TreeIsEmpty(pt)){puts("No entries!");return; /* quit function if tree is empty */}puts("Please enter name of pet you wish to find:");s_gets(temp.petname, SLEN);puts("Please enter pet kind:");s_gets(temp.petkind, SLEN);uppercase(temp.petname);uppercase(temp.petkind);printf("%s the %s ", temp.petname, temp.petkind);if (InTree(&temp, pt))printf("is a member.\n");elseprintf("is not a member.\n"); }void droppet(Tree * pt) {Item temp;if (TreeIsEmpty(pt)){puts("No entries!");return; /* quit function if tree is empty */}puts("Please enter name of pet you wish to delete:");s_gets(temp.petname, SLEN);puts("Please enter pet kind:");s_gets(temp.petkind, SLEN);uppercase(temp.petname);uppercase(temp.petkind);printf("%s the %s ", temp.petname, temp.petkind);if (DeleteItem(&temp, pt))printf("is dropped from the club.\n");elseprintf("is not a member.\n"); }void uppercase(char * str) {while (*str){*str = toupper(*str);str++;} } 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) // 如果地址不是 NULL,*find = '\0'; // 在此處放置一個空字符elsewhile (getchar() != '\n')continue; // 處理輸入行的剩余內容}return ret_val; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的c语言 数据结构 list、queue、tree抽象数据类型的定义与实现 详尽代码和注释的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。