程序設(shè)計(jì)實(shí)習(xí)講義9

1、程序設(shè)計(jì)實(shí)習(xí)第九講鏈表和二叉樹(shù)http:/cpp2010鏈 表1) 鏈表的結(jié)構(gòu)和特點(diǎn)2) 單鏈表的操作：插入、刪除算法 單鏈表單鏈表的概念： 單鏈表（singly linked list)是一種簡(jiǎn)單的鏈表表示，也稱為線性鏈表。是由結(jié)點(diǎn)組成。 一個(gè)結(jié)點(diǎn)由兩個(gè)域組成： 數(shù)據(jù)域 指向下一結(jié)點(diǎn)的指針域特點(diǎn) 每個(gè)元素(表項(xiàng))由結(jié)點(diǎn)(Node)構(gòu)成。線性結(jié)構(gòu)結(jié)點(diǎn)可以不連續(xù)存儲(chǔ) 表可擴(kuò)充單鏈表中的插入與刪除 在一個(gè)線性單鏈表中插入結(jié)點(diǎn)的情況有三種帶表頭結(jié)點(diǎn)的單鏈表 表頭結(jié)點(diǎn)位于表的最前端，本身不帶數(shù)據(jù)，僅標(biāo)志表頭。 設(shè)置表頭結(jié)點(diǎn)的目的是統(tǒng)一空表與非空表的操作，簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。從帶表頭結(jié)點(diǎn)的單鏈表中刪除第

2、一個(gè)結(jié)點(diǎn)q = plink; plink = qlink; delete q; if ( plink = NULL ) last = p;帶表頭結(jié)點(diǎn)的單鏈表的實(shí)現(xiàn)/節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)struct LNode int data;struct LNode * next;/鏈表數(shù)據(jù)結(jié)構(gòu)struct LinkList LNode * pHead; /表頭指針LNode * pCurrent; /當(dāng)前節(jié)點(diǎn)指針int nLength; /表中節(jié)點(diǎn)數(shù)目（不含頭節(jié)點(diǎn)）; /每個(gè)該結(jié)構(gòu)的變量代表一張鏈表用來(lái)對(duì)鏈表進(jìn)行操作的函數(shù)：初始化（創(chuàng)建頭節(jié)點(diǎn)）:bool InitList ( LinkList * pThis )

3、;銷毀整個(gè)鏈表，包括銷毀頭節(jié)點(diǎn)：bool DestroyList (LinkList * pThis);刪除全部節(jié)點(diǎn)，但頭節(jié)點(diǎn)保留：bool ClearList(LinkList * pThis);判斷鏈表是否為空：bool IsEmpty (LinkList * pThis);取鏈表長(zhǎng)度：int GetLength (LinkList * pThis);獲取指向第position個(gè)節(jié)點(diǎn)的指針(position從1開(kāi)始算)LNode * GetNode(LinkList * pThis, int position);取值為elem的第一個(gè)元素的位置(返回0則沒(méi)找到）int LocateElem

4、(LinkList * pThis,int elem);用來(lái)對(duì)鏈表進(jìn)行操作的函數(shù)：將第 position 個(gè)節(jié)點(diǎn)的值設(shè)為 newData bool SetNodeData(LinkList * pThis,int position, int newData);獲取第 position 個(gè)節(jié)點(diǎn)的值 bool GetNodeData(LinkList * pThis,int position, int &data);將一個(gè)值為data的節(jié)點(diǎn)插入到第beforeWhich個(gè)節(jié)點(diǎn)前面(beforeWhich的取值是 1 到 pThis-nLength + 1) bool InsertNode(Link

5、List * pThis,int beforeWhich, int data);刪除第position 個(gè)節(jié)點(diǎn)bool DeleteNode(LinkList * pThis,int position);使第一個(gè)節(jié)點(diǎn)成為當(dāng)前節(jié)點(diǎn)void Rewind(LinkList * pThis);取當(dāng)前節(jié)點(diǎn)的值，并移動(dòng)到下一個(gè)節(jié)點(diǎn)bool GetNextNodeData( LinkList * pThis, int * pData)/初始化，分配一個(gè)頭節(jié)點(diǎn)。bool InitList( LinkList * pThis ) if (!( pThis-pHead = new LNode) return f

6、alse;pThis-pHead-next = NULL;pThis-nLength = 0;pThis-pCurrent = pThis-pHead-next ;return true;/銷毀鏈表。bool DestroyList(LinkList * pThis) if (!ClearList( pThis) return false;delete pThis-pHead;return true;/使第個(gè)節(jié)點(diǎn)成為當(dāng)前節(jié)點(diǎn)void Rewind(LinkList * pThis)pThis-pCurrent = pThis-pHead-next ;/取當(dāng)前節(jié)點(diǎn)數(shù)據(jù)，并移動(dòng)到下一個(gè)節(jié)點(diǎn)bool

7、 GetNextNodeData( LinkList * pThis, int * pData)if( pThis-pCurrent = NULL )return false;* pData = pThis-pCurrent-data;pThis-pCurrent= pThis-pCurrent-next ;return true;/判斷鏈表是否為空。若為空，返回true，否則返回false。bool IsEmpty(LinkList * pThis) if ( pThis-pHead-next = NULL) return true;return false;/返回鏈表中 的 當(dāng)前節(jié)點(diǎn)數(shù)。i

8、nt GetLength(LinkList * pThis) return pThis-nLength;/將鏈表清空，釋放當(dāng)前所有節(jié)點(diǎn)(不包括頭節(jié)點(diǎn)）。bool ClearList(LinkList * pThis) if (pThis-pHead = NULL) return false;LNode *pTemp = NULL;while (pThis-pHead-next != NULL) pTemp = pThis-pHead-next; pThis-pHead-next = pTemp-next; delete pTemp;pThis-nLength = 0;return true;/

9、得到指定位置節(jié)點(diǎn)的數(shù)據(jù)。/節(jié)點(diǎn)索引從1到listLength。bool GetNodeData(LinkList * pThis,int position, int &data) LNode *pTemp = GetNode(pThis,position);if (!pTemp) return false;data = pTemp-data;return true;/將position指定的節(jié)點(diǎn)內(nèi)的數(shù)據(jù)設(shè)置為newData。/第一個(gè)有效節(jié)點(diǎn)的position為1。bool SetNodeData(LinkList * pThis,int position, int newData) LNode

10、 *pTemp = GetNode(pThis,position);if (! pTemp) return false;pTemp-data = newData;return true;/在鏈表中插入一個(gè)節(jié)點(diǎn)。/插入的位置由beforeWhich指定，新節(jié)點(diǎn)插入在beforeWhich之前/beforeWhich的取值在1到ListLength+1之間。bool InsertNode(LinkList * pThis,int beforeWhich, int data) if (beforeWhich (pThis-nLength + 1) return false;LNode *pTemp

11、= GetNode(pThis, beforeWhich - 1);if (!pTemp) return false;LNode *newNode = new LNode;newNode-data = data;newNode-next = pTemp-next;pTemp-next = newNode;pThis-nLength+;return true;/刪除一個(gè)指定的節(jié)點(diǎn) , 節(jié)點(diǎn)位置由position指定。/positon的值從1到listLength。/若鏈表為空或指定的節(jié)點(diǎn)不存在則返回false。bool DeleteNode(LinkList * pThis,int positi

12、on) if (position pThis-nLength) return false;LNode *pTemp = GetNode(pThis,position - 1);if (!pTemp) return false;LNode *pDel = NULL;pDel = pTemp-next;pTemp-next = pDel-next;delete pDel;pThis-nLength-;return true;/得到指定位置節(jié)點(diǎn)的指針。LNode * GetNode( LinkList * pThis,int position) LNode *pTemp = NULL;int cur

13、Pos = -1;pTemp = pThis-pHead;while (pTemp != NULL) curPos+; if (curPos = position) break; pTemp = pTemp-next;if (curPos != position) return 0;return pTemp;/定位與指定數(shù)據(jù)相等的數(shù)據(jù)節(jié)點(diǎn)。/如果在當(dāng)前鏈表中已經(jīng)存在該數(shù)據(jù)則返回該數(shù)據(jù)節(jié)點(diǎn)的位置。/若不存在這樣的節(jié)點(diǎn)則返回0。int LocateElem(LinkList * pThis,int elem) LNode *pTemp = NULL;int curIndex = 1;pTemp =

14、 pThis-pHead-next;while (pTemp != NULL) & (pTemp-data != elem) pTemp = pTemp-next; curIndex+;if (pTemp = NULL) return 0;return curIndex;int main()LinkList MyList; /要再使用一張鏈表，則可以定義 LinkList MyList2;InitList ( & MyList);InsertNode(& MyList, 1, 10); InsertNode( & MyList, 2, 20);InsertNode(& MyList, 3, 3

15、0); InsertNode(& MyList, 4, 40);cout GetLength(& MyList) endl;int dataTemp = 0;for (int i = 1; i = GetLength(& MyList); i+) GetNodeData(& MyList,i, &dataTemp); cout dataTemp endl;if (SetNodeData(& MyList,3, 50) cout DONEn; else cout Failedn;Rewind( & MyList);while (GetNextNodeData( & MyList,&dataTem

16、p)cout dataTemp endl;if (DeleteNode(& MyList,4) cout DONEn; else cout Failedn;for (i = 1; i = GetLength(& MyList); i+) GetNodeData(& MyList,i, &dataTemp);cout dataTemp endl;cout LocateElem(&MyList,40) endl;DeleteNode(&MyList,LocateElem( & MyList,50);DeleteNode(&MyList,LocateElem( & MyList,20);Rewind

17、( & MyList);while (GetNextNodeData( & MyList,&dataTemp)cout dataTemp data); / visit the node PreOrder (root-left, visit); / descend left PreOrder (root-right, visit); / descend right ABCDE FG IH則 Preorder(pa,PrintChar);輸出：ABDEGCFHIvoid PrintChar(char & c) coutleft, visit); visit(root-data); MiddleOr

18、der (root-right, visit); ABCDE FG IHDBGEACHFI后序遍歷void PostOrder (CharNode * root, void (*visit)( char & item) ) if (root) PostOrder (root-left, visit); PostOrder (root-right, visit); visit(root-data); ABCDE FG IHDGEBHIFCA二叉樹(shù)的刪除void DestroyTree( CharNode * root)if( root-left = NULL & root-right = NULL) delete root;return;if( root-left ) DestroyTree(root-left);if( root-right)Destr