|
摘要 本章介紹了幾種基本的數(shù)據(jù)結(jié)構(gòu)，包括棧、隊列、鏈表以及有根樹，討論了使用指針的簡單數(shù)據(jù)結(jié)構(gòu)來表示動態(tài)集合。本章的內(nèi)容對于學(xué)過數(shù)據(jù)結(jié)構(gòu)的人來說，沒有什么難處，簡單的總結(jié)一下。 1、棧和隊列 棧和隊列都是動態(tài)集合，元素的出入是規(guī)定好的。棧規(guī)定元素是先進后出（FILO），隊列規(guī)定元素是先進先出（FIFO）。棧和隊列的實現(xiàn)可以采用數(shù)組和鏈表進行實現(xiàn)。在標(biāo)準(zhǔn)模塊庫STL中有具體的應(yīng)用，可以參考http://www./reference/。 棧的基本操作包括入棧push和出棧pop，棧有一個棧頂指針top，指向最新如棧的元素，入棧和出棧操作操作都是從棧頂端進行的。 隊列的基本操作包括入隊enqueue和出隊dequeue，隊列有隊頭head和隊尾tail指針。元素總是從隊頭出，從隊尾入。采用數(shù)組實現(xiàn)隊列時候，為了合理利用空間，可以采用循環(huán)實現(xiàn)隊列空間的有效利用。 關(guān)于棧和隊列的基本操作如下圖所示： 采用數(shù)組簡單實現(xiàn)一下棧和隊列，實現(xiàn)隊列時候，長度為n的數(shù)組最多可以含有n-1個元素，循環(huán)利用，這樣方便判斷隊列是空還是滿。程序如下所示： 1 //stack.c 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 6 typedef struct stack 7 { 8 int *s; 9 int stacksize; 10 int top; 11 }stack; 12 13 void init_stack(stack*s) 14 { 15 s->stacksize = 100; 16 s->s =(int*)malloc(sizeof(int)*s->stacksize); 17 s->top = -1; 18 } 19 int stack_empty(stack s) 20 { 21 return ((0 == s.stacksize) ? 1 : 0); 22 } 23 24 void push(stack *s,int x) 25 { 26 if(s->top == s->stacksize) 27 printf("up to overflow.\n"); 28 else 29 { 30 s->top++; 31 s->s[s->top] = x; 32 s->stacksize++; 33 } 34 } 35 void pop(stack *s) 36 { 37 if(0 == s->stacksize) 38 printf("down to overflow.\n"); 39 else 40 { 41 s->top--; 42 s->stacksize--; 43 } 44 } 45 int top(stack s) 46 { 47 return s.s[s.top]; 48 } 49 50 int main() 51 { 52 stack s; 53 init_stack(&s); 54 push(&s,19); 55 push(&s,23); 56 push(&s,34); 57 push(&s,76); 58 push(&s,65); 59 printf("top is:%d\n",top(s)); 60 pop(&s); 61 printf("top is:%d\n",top(s)); 62 }  1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef struct queue 5 { 6 int *q; 7 int queuesize; 8 int head; 9 int tail; 10 }queue; 11 12 void enqueue(queue* q,int x) 13 { 14 if(((q->tail+1) % q->queuesize) == q->head) 15 { 16 printf("queue is full.\n"); 17 } 18 else 19 { 20 q->q[q->tail] = x; 21 q->tail = (q->tail+1) % q->queuesize; 22 } 23 } 24 25 int dequeue(queue* q,int *value) 26 { 27 if(q->tail == q->head) 28 return -1; 29 else 30 { 31 *value = q->q[q->head]; 32 q->head = ((q->head++) % q->queuesize); 33 } 34 } 35 int main() 36 { 37 38 int value; 39 queue q; 40 q.queuesize=10; 41 q.q = (int*)malloc(sizeof(int)*q.queuesize); 42 q.head=0; 43 q.tail=0; 44 enqueue(&q,10); 45 enqueue(&q,30); 46 printf("head=%d\t tail=%d\n",q.head,q.tail); 47 if(dequeue(&q,&value) == -1) 48 printf("queue is empty.\n"); 49 else 50 printf("value=%d\n",value); 51 if(dequeue(&q,&value) == -1) 52 printf("queue is empty.\n"); 53 else 54 printf("value=%d\n",value); 55 if(dequeue(&q,&value) == -1) 56 printf("queue is empty.\n"); 57 else 58 printf("value=%d\n",value); 59 printf("head=%d\t tail=%d\n",q.head,q.tail); 60 enqueue(&q,10); 61 exit(0); 62 } 測試結(jié)果如下所示：
問題： （1）說明如何用兩個棧實現(xiàn)一個隊列，并分析有關(guān)隊列操作的運行時間。 解答：棧中的元素是先進后出，而隊列中的元素是先進先出?，F(xiàn)有棧s1和s2，s1中存放隊列中的結(jié)果，s2輔助轉(zhuǎn)換s1為隊列。入隊列操操作：當(dāng)一個元素入隊列時，先判斷s1是否為空，如果為空則新元素直接入s1，如果非空則將s1中所有元素出棧并存放到s2中，然后在將元素入s1中，最后將s2中所有元素出棧并入s1中。此時s1中存放的即是隊列入隊的順序。出隊操作：如果s1為空，則說明隊列為空，非空則s1出棧即可。入隊過程需要在s1和s2來回交換，運行時間為O(n)，出隊操作直接是s1出棧運行時間為O(1)。舉例說明轉(zhuǎn)換過程，如下圖示： 我采用C++語言實現(xiàn)整程序如下： 1 #include <iostream> 2 #include <stack> 3 #include <cstdlib> 4 using namespace std; 5 6 template <class T> 7 class MyQueue 8 { 9 public: 10 MyQueue(); 11 ~MyQueue(); 12 void enqueue(const T& data); 13 int queue_empty() const; 14 T dequeue(); 15 private: 16 stack<T>s1; 17 stack<T>s2; 18 }; 19 20 template<class T> 21 MyQueue<T>::MyQueue() 22 { 23 24 } 25 template<class T> 26 MyQueue<T>::~MyQueue() 27 { 28 29 } 30 template<class T> 31 void MyQueue<T>::enqueue(const T& data) 32 { 33 if(s1.empty()) 34 s1.push(data); 35 else 36 { 37 while(!s1.empty(d)) 38 { 39 s2.push(s1.top()); 40 s1.pop(); 41 } 42 s1.push(data); 43 } 44 while(!s2.empty()) 45 { 46 s1.push(s2.top()); 47 s2.pop(); 48 } 49 } 50 template<class T> 51 int MyQueue<T>::queue_empty() const 52 { 53 return (s1.empty()); 54 } 55 template<class T> 56 T MyQueue<T>::dequeue() 57 { 58 T ret; 59 if(!s1.empty()) 60 { 61 ret = s1.top(); 62 s1.pop(); 63 } 64 return ret; 65 66 } 67 68 int main() 69 { 70 MyQueue<int> myqueue; 71 myqueue.enqueue(10); 72 myqueue.enqueue(20); 73 myqueue.enqueue(30); 74 cout<< myqueue.dequeue()<<endl; 75 myqueue.enqueue(40); 76 cout<< myqueue.dequeue()<<endl; 77 cout<< myqueue.dequeue()<<endl; 78 myqueue.enqueue(50); 79 cout<< myqueue.dequeue()<<endl; 80 cout<< myqueue.dequeue()<<endl; 81 exit(0); 82 } （2）說明如何用兩個隊列實現(xiàn)一個棧，并分析有關(guān)棧操作的運行時間。 解答：類似上面的題目，隊列是先進先出，而棧是先進后出?，F(xiàn)有隊列q1和q2，q1中存放的是棧的結(jié)果，q2輔助q1轉(zhuǎn)換為棧。入棧操作：當(dāng)一個元素如棧時，先判斷q1是否為空，如果為空則該元素之間入隊列q1，如果非空則將q1中的所有元素出隊并入到q2中，然后將該元素入q1中，最后將q2中所有元素出隊并入q1中。此時q1中存放的就是棧的如棧順序。出棧操作：如果q1為空，則棧為空，否則直接q1出隊操作。入棧操作需要在隊列q1和q2直接來來回交換，運行時間為O(n)，出棧操作是隊列q1出隊操作，運行時間為O(1)。我用C++語言實現(xiàn)完整程序如下： 1 #include <iostream> 2 #include <stack> 3 #include <cstdlib> 4 using namespace std; 5 6 template <class T> 7 class MyQueue 8 { 9 public: 10 MyQueue(); 11 ~MyQueue(); 12 void enqueue(const T& data); 13 int queue_empty() const; 14 T dequeue(); 15 private: 16 stack<T>s1; 17 stack<T>s2; 18 }; 19 20 template<class T> 21 MyQueue<T>::MyQueue() 22 { 23 24 } 25 template<class T> 26 MyQueue<T>::~MyQueue() 27 { 28 29 } 30 template<class T> 31 void MyQueue<T>::enqueue(const T& data) 32 { 33 if(s1.empty()) 34 s1.push(data); 35 else 36 { 37 while(!s1.empty(d)) 38 { 39 s2.push(s1.top()); 40 s1.pop(); 41 } 42 s1.push(data); 43 } 44 while(!s2.empty()) 45 { 46 s1.push(s2.top()); 47 s2.pop(); 48 } 49 } 50 template<class T> 51 int MyQueue<T>::queue_empty() const 52 { 53 return (s1.empty()); 54 } 55 template<class T> 56 T MyQueue<T>::dequeue() 57 { 58 T ret; 59 if(!s1.empty()) 60 { 61 ret = s1.top(); 62 s1.pop(); 63 } 64 return ret; 65 66 } 67 68 int main() 69 { 70 MyQueue<int> myqueue; 71 myqueue.enqueue(10); 72 myqueue.enqueue(20); 73 myqueue.enqueue(30); 74 cout<< myqueue.dequeue()<<endl; 75 myqueue.enqueue(40); 76 cout<< myqueue.dequeue()<<endl; 77 cout<< myqueue.dequeue()<<endl; 78 myqueue.enqueue(50); 79 cout<< myqueue.dequeue()<<endl; 80 cout<< myqueue.dequeue()<<endl; 81 exit(0); 82 } 2、鏈表 鏈表與數(shù)組的區(qū)別是鏈表中的元素順序是有各對象中的指針決定的，相鄰元素之間在物理內(nèi)存上不一定相鄰。采用鏈表可以靈活地表示動態(tài)集合。鏈表有單鏈表和雙鏈表及循環(huán)鏈表。書中著重介紹了雙鏈表的概念及操作，雙鏈表L的每一個元素是一個對象，每個對象包含一個關(guān)鍵字和兩個指針：next和prev。鏈表的操作包括插入一個節(jié)點、刪除一個節(jié)點和查找一個節(jié)點，重點來說一下雙向鏈表的插入和刪除節(jié)點操作，圖例如下： 鏈表是最基本的數(shù)據(jù)結(jié)構(gòu)，凡是學(xué)計算機的必須的掌握的，在面試的時候經(jīng)常被問到，關(guān)于鏈表的實現(xiàn)，百度一下就知道了。在此可以討論一下與鏈表相關(guān)的練習(xí)題。 （1）在單鏈表上插入一個元素，要求時間復(fù)雜度為O(1)。 解答：一般情況在鏈表中插入一元素是在末尾插入的，這樣需要從頭遍歷一次鏈表，找到末尾，時間為O(n)。要在O(1)時間插入一個新節(jié)點，可以考慮每次在頭節(jié)點后面插入，即每次插入的節(jié)點成為鏈表的第一個節(jié)點。 （2）在單鏈表上刪除一個給定的節(jié)點p，要求時間復(fù)雜度為O(1)。 解答：一般情況刪除一個節(jié)點時候，我們需要找到該節(jié)點p的前驅(qū)節(jié)點q，需要對鏈表進行遍歷，運行時間為O(n-1)。我們可以考慮先將q的后繼節(jié)點s的值替換q節(jié)點值，然后刪除s即可。如下圖刪除節(jié)點q的操作過程：
（3）單鏈表逆置，不允許額外分配存儲空間，不允許遞歸，可以使用臨時變量，執(zhí)行時間為O(n)。 解答：這個題目在面試筆試中經(jīng)常碰到，基本思想上將指針逆置。如下圖所示： （4）遍歷單鏈表一次，找出鏈表中間節(jié)點。 解答：定義兩個指針p和q，初始都指向鏈表頭節(jié)點。然后開始向后遍歷，p每次移動2步，q移動一步，當(dāng)p到達(dá)末尾的時候，p正好到達(dá)了中間位置。 （5）用一個單鏈表L實現(xiàn)一個棧，要求push和pop的操作時間為O(1)。 解答：根據(jù)棧中元素先進后出的特點，可以在鏈表的頭部進行插入和刪除操作。 （6）用一個單鏈表L實現(xiàn)一個隊列，要求enqueue和dequeue的操作時間為O(1)。 解答：隊列中的元素是先進先出，在單鏈表結(jié)構(gòu)中增加一個尾指針，數(shù)據(jù)從尾部插入，從頭部刪除。 3、有根樹的表示 采用鏈表數(shù)據(jù)結(jié)構(gòu)來表示樹，書中先降二叉樹的鏈表表示法，然后拓展到分支數(shù)無限制的有根數(shù)。先來看看二叉樹的鏈表表示方法，用域p、left和right來存儲指向二叉樹T中的父親、左孩子和右孩子的指針。如下圖所示：
對于分支數(shù)目無限制的有根樹，采用左孩子、右兄弟的表示方法。這樣表示的樹的每個節(jié)點都包含有一個父親指針p，另外兩個指針： （1）left_child指向節(jié)點的最左孩子。 （2）right_sibling指向節(jié)點緊右邊的兄弟。 |
|
|
