【文章內(nèi)容簡介】 front, *rear NodeT *prevPtr, *currPtr。 int size。 int position。 NodeT *newNode(const T amp。item,NodeT *ptrNext=NULL)。 void freeNode(NodeT *p)。 void copy(const LinkedListTamp。 L)。 public: LinkedList()。 LinkedList(const LinkedListT amp。L)。 ~LinkedList()。 LinkedListT amp。 operator = (const LinkedListT amp。L)。 int getSize() const。 bool isEmpty() const。 void reset(int pos = 0 void next()。 bool endOfList() const。 int currentPosition(void) const。 void insertFront(const T amp。item)。 void insertRear(const T amp。item)。 void insertAt(const T amp。item)。 void insertAfter(const T amp。item)。 T deleteFront()。 void deleteCurrent()。 Tamp。 data()。 const Tamp。 data() const void clear()。 }。 endif //LINKEDLIST_H C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 鏈表類應(yīng)用舉例 (例 97) ? 從鍵盤輸入 10個(gè)整數(shù)，用這些整數(shù)值作為結(jié)點(diǎn)數(shù)據(jù)，生成一個(gè)鏈表，按順序輸出鏈表中結(jié)點(diǎn)的數(shù)值。然后從鍵盤輸入一個(gè)待查找整數(shù)，在鏈表中查找該整數(shù)，若找到則刪除該整數(shù)所在的結(jié)點(diǎn)（如果出現(xiàn)多次，全部刪除），然后輸出刪除結(jié)點(diǎn)以后的鏈表。在程序結(jié)束之前清空鏈表。 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 37 鏈表類應(yīng)用舉例 (例 97) 順序訪問的線性群體 // include iostream include using namespace std。 int main() { LinkedListint list。 for (int i = 0。 i 10。 i++) { int item。 cin item。 (item)。 } cout List: 。 ()。 while (!()) { cout () 。 ()。 } cout endl。 int key。 cout Please enter some integer needed to be deleted: 。 cin key。 ()。 while (!()) { if (() == key) ()。 ()。 } cout List: 。 ()。 while (!()) { cout () 。 } cout endl。 return 0。 } C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 38 特殊的線性群體 ——棧 棧是只能從一端訪問的線性群體，可以訪問的這一端稱棧頂，另一端稱棧底。 an ┆ a2 a1 入棧 出棧 棧頂 棧底 特殊的線性群體——棧 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 39 棧的應(yīng)用舉例 ——表達(dá)式處理 b a / a/b+c*d (a) t1 + a/b+c*d t1=a/b (b) d c t1 * + a/b+c*d (c) t3 a/b+c*d t3=t1+t2 (e) t2 t1 + a/b+c*d t2=c*d (d) 特殊的線性群體——棧 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 40 棧的基本狀態(tài) ? ?？? – 棧中沒有元素 ? 棧滿 – 棧中元素個(gè)數(shù)達(dá)到上限 ? 一般狀態(tài) – 棧中有元素，但未達(dá)到棧滿狀態(tài) 特殊的線性群體——棧 棧頂 ┆ an ┆ a1 a0 入棧 出棧 數(shù)組下標(biāo) max n 1 0 一般狀態(tài) 棧頂 入棧 出棧 數(shù)組下標(biāo) 初始狀態(tài)（?？眨? max n 1 0 棧頂 amax ┆ an ┆ a1 a0 入棧 出棧 數(shù)組下標(biāo) max n 1 0 棧滿狀態(tài) 41 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 42 棧的基本操作 ? 初始化 ? 入棧 ? 出棧 ? 清空棧 ? 訪問棧頂元素 ? 檢測棧的狀態(tài)（滿、空） 特殊的線性群體——棧 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 43 棧類模板 (例 98) 特殊的線性群體——棧 // ifndef STACK_H define STACK_H include cassert template class T, int SIZE = 50 class Stack { private: T list[SIZE]。 int top。 public: Stack()。 void push(const T amp。item)。 T pop()。 void clear()。 const T amp。peek() const。 bool isEmpty() const。 bool isFull() const。 }。 //類的實(shí)現(xiàn)略 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 51 特殊的線性群體 ——隊(duì)列 隊(duì)列是只能向一端添加元素，從另一端刪除元素的線性群體 a1 a2 an1 an …… 隊(duì)頭 隊(duì)尾 入隊(duì) 出隊(duì) a0 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 52 隊(duì)列的基本狀態(tài) ? 隊(duì)空 – 隊(duì)列中沒有元素 ? 隊(duì)滿 – 隊(duì)列中元素個(gè)數(shù)達(dá)到上限 ? 一般狀態(tài) – 隊(duì)列中有元素，但未達(dá)到隊(duì)滿狀態(tài) 特殊的線性群體——隊(duì)列 a0 a1 an1 an ?? 隊(duì)頭 隊(duì)尾 入隊(duì) 出隊(duì) 數(shù)組下標(biāo) 0 1 n1 n max (一般狀態(tài) ) ?? 隊(duì)頭 隊(duì)尾 入隊(duì) 出隊(duì) 數(shù)組下標(biāo) 0 1 n1 n max (隊(duì)空狀態(tài) ) a0 a1 an1 an amax ?? 隊(duì)頭 隊(duì)尾 入隊(duì) 出隊(duì) 數(shù)組下標(biāo) 0 1 n1 n max (隊(duì)滿狀態(tài) ) 元素移動方向 元素移動方向 53 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 54 循環(huán)隊(duì)列 在想象中將數(shù)組彎曲成環(huán)形，元素出隊(duì)時(shí)，后繼元素不移動，每當(dāng)隊(duì)尾達(dá)到數(shù)組最后一個(gè)元素時(shí)，便再回到數(shù)組開頭。 特殊的線性群體——隊(duì)列 1 2 3 4 …… m1 m2 m3 0 am am+1 am+2 a3 隊(duì)頭 隊(duì)尾 a4 am2 am3 am1 隊(duì)滿狀態(tài) 元素個(gè)數(shù) =m 1 2 3 4 …… m1 m2 m3 0 隊(duì)尾 隊(duì)頭 隊(duì)空狀態(tài) 元素個(gè)數(shù) =0 隊(duì)尾 1 2 3 4 …… m1 m2 m3 0 a0 a1 a2 a3 隊(duì)頭 一般狀態(tài) 55 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 56 第三部分： 群 體數(shù)據(jù)的組織 ? 插入排序 ? 選擇排序 ? 交換排序 ? 順序查找 ? 折半查找 C++語言程序設(shè)計(jì) 清華大學(xué) 鄭莉 57 排序（ sorting） ? 排序 是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作，它的功能是將一個(gè) 數(shù)據(jù)元素 的任意序列，重新排列成一個(gè)按 關(guān)鍵字 有序的序列。 – 數(shù)據(jù)元素： 數(shù)據(jù)的基本單位。在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮。一個(gè)數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成。 – 關(guān)鍵字： 數(shù)據(jù)元素中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識（識別）一個(gè)數(shù)據(jù)元素。 ? 在排序過程中需要完成兩種基本操作： – 比較兩個(gè)數(shù)的大小 – 調(diào)整元素在序列中的位置 群體數(shù)據(jù)的組織