本章讲述的是基本的数据结构,如栈、队列和链表。这些都是最最基本的数据结构,具体的就不再啰嗦。然后本章也没有什么需要特别注意的点,哦,有一个小节:指针和对象的实现,可以认真看一下,大概就是用其他的实现方式来代替指针和对象的实现,因为有些语言不支持指针和对象数据类型,那在实现这种链式的数据结构就无法表示,本节介绍的方法就是利用数组和数组下标来构造对象和指针,说白了,就是利用数组来表示链式对象。个人感觉意义不大,权当了解得了。
结合一些常见的笔试面试题,我就用3个习题来总结这一章吧。
1、习题10.1-6:说明如何用两个栈实现一个队列,并分析相关队列操作的运行时间。
两个栈实现一个队列和两个队列实现一个栈的思路都是一样的。
算法思路:
1)StackA和StackB,StackA作为存储栈,StackB作为辅助栈;
2)入队列操作:假如StackA中有元素,则首先将StackA中元素出栈放入StackB中,再把入队列元素放入StackA,然后再把StackB中的元素出栈放入StackA中
3)出队列操作:以上操作保证先入队列的元素先出,所以,直接从StackA中出栈即可。
如下直观的图示:
代码如下:
1 #include <iostream>
2 #include <stack>
3 #include <cstdlib>
4
5 using namespace std;
6
7 /************************************************************************/
8 /* 两个栈实现队列
9 /* 采用C++模板是实现
10 /************************************************************************/
11 template<class T>
12 class StackQueue
13 {
14 public:
15 StackQueue(){}
16 ~StackQueue(){}
17
18 void Enqueue(const T& elem);
19 T Dequeue();
20 bool Empty() const;
21
22 private:
23 stack<T> m_stackA;
24 stack<T> m_stackB;
25 };
26
27 template<class T>
28 void StackQueue<T>::Enqueue(const T& elem)
29 {
30 if (m_stackA.empty())
31 m_stackA.push(elem);
32 else {
33 while (!m_stackA.empty()) {
34 m_stackB.push(m_stackA.top());
35 m_stackA.pop();
36 }
37 m_stackA.push(elem);
38 }
39
40 while(!m_stackB.empty()) {
41 m_stackA.push(m_stackB.top());
42 m_stackB.pop();
43 }
44 }
45
46 template<class T>
47 T StackQueue<T>::Dequeue()
48 {
49 T retElem;
50 if (!m_stackA.empty()) {
51 retElem = m_stackA.top();
52 m_stackA.pop();
53 }
54 return retElem;
55 }
56
57 template<class T>
58 bool StackQueue<T>::Empty() const
59 {
60 if (m_stackA.empty())
61 return true;
62 else
63 return false;
64 }
65
66 // int main()
67 // {
68 // StackQueue<int> SQ;
69 // for (int i = 1; i <= 5; i ++) {
70 // SQ.Enqueue(i);
71 // }
72 //
73 // for (int i = 1; i <= 5; i ++) {
74 // cout << SQ.Dequeue();
75 // }
76 // return 0;
77 // }
2、习题10.1-7:说明如何用两个队列实现一个栈,并分析相关栈操作的运行时间。
该算法思路与上题一样,本处就不再赘述。直接贴代码吧:
1 #include <iostream>
2 #include <queue>
3
4 using namespace std;
5
6 /************************************************************************/
7 /* 两个队列实现一个栈
8 /* 使用C++模板的形式
9 /************************************************************************/
10 template<class T>
11 class QueueStack {
12 public:
13 QueueStack(){}
14 ~QueueStack(){}
15
16 void Push(const T& elem);
17 void Pop();
18 T Top() const;
19
20 private:
21 queue<T> m_queueA;
22 queue<T> m_queueB;
23 };
24
25 template<class T>
26 void QueueStack<T>::Push(const T& elem)
27 {
28 if (m_queueA.empty())
29 m_queueA.push(elem);
30 else {
31 while (!m_queueA.empty()) {
32 m_queueB.push(m_queueA.front());
33 m_queueA.pop();
34 }
35 m_queueA.push(elem);
36 }
37 while (!m_queueB.empty()) {
38 m_queueA.push(m_queueB.front());
39 m_queueB.pop();
40 }
41 }
42
43 template<class T>
44 void QueueStack<T>::Pop()
45 {
46 if (!m_queueA.empty())
47 m_queueA.pop();
48 }
49
50 template<class T>
51 T QueueStack<T>::Top() const
52 {
53 T nElem;
54 if (!m_queueA.empty())
55 nElem = m_queueA.front();
56 return nElem;
57 }
58
59 // int main()
60 // {
61 // QueueStack<int> QS;
62 // for (int i = 1; i <= 5; i ++) {
63 // QS.Push(i);
64 // }
65 //
66 // for (int i = 1; i <= 5; i ++) {
67 // cout << QS.Top();
68 // QS.Pop();
69 // }
70 // return 0;
71 // }
3、习题10.2-7:给出一个O(n)时间的非递归过程,实现对一个含n个元素的单链表的逆转,要求出存储链表本身所需空间外,该过程只能使用固定大小的存储空间。
由于限制了时间和空间,所以只能通过就地逆转来实现,结合单链表的特性,能想到的就是改变指针的指向,我们可以用三个指针来指向链表中的元素,使之满足这样的关系:p->q->r。也不太好描述,看下面一个图示吧:
代码如下:
1 #include <iostream>
2
3 using namespace std;
4
5 template<class T>
6 class Node
7 {
8 public:
9 template<class T> friend class SingleLink;
10
11 //Node(Node *pNext = NULL):m_pNext(pNext) {}
12 Node(T key = (T)0, Node *pNext = NULL):m_key(key), m_pNext(pNext) {}
13 ~Node(){}
14
15 private:
16 T m_key;
17 Node *m_pNext;
18 };
19
20 template<class T>
21 class SingleLink
22 {
23 public:
24 SingleLink(Node<T> *pHead = NULL):m_pHead(pHead) {}
25 ~SingleLink(){}
26
27 void Insert(const T& );
28 void Delete(const T& );
29
30 void Reverse();
31
32 void Print();
33
34 private:
35 Node<T> *m_pHead;
36 };
37
38 //有序地插入
39 template<class T>
40 void SingleLink<T>::Insert(const T& key)
41 {
42 Node<T> *pInsert = new Node<T>(key);
43 if (NULL == m_pHead)
44 m_pHead = pInsert;
45 else {
46 Node<T> *pTemp = m_pHead;
47 Node<T> *qTemp = NULL;
48 while (pTemp) {
49 if (pTemp->m_key <= key) {
50 qTemp = pTemp;
51 pTemp = pTemp->m_pNext;
52 }
53 else break;
54 }
55 pInsert->m_pNext = pTemp;
56 qTemp->m_pNext = pInsert;
57 }
58 }
59
60 template<class T>
61 void SingleLink<T>::Delete(const T& key)
62 {
63 if (NULL == m_pHead)
64 return;
65
66 if (m_pHead->m_key == key)
67 m_pHead = NULL;
68 else {
69 Node<T> *pTemp = m_pHead;
70 Node<T> *pDelete = m_pHead->m_pNext;
71 while (pDelete) {
72 if (pDelete->m_key != key) {
73 pTemp = pDelete;
74 pDelete = pDelete->m_pNext;
75 }
76 else {
77 pTemp->m_pNext = pDelete->m_pNext;
78 break;
79 }
80 }
81 }
82 }
83
84 template<class T>
85 void SingleLink<T>::Reverse()
86 {
87 //only one element
88 if (NULL == m_pHead || NULL == m_pHead->m_pNext)
89 return;
90
91 //p->q->r
92 Node<T> *p = NULL, *q = m_pHead, *r = NULL;
93 while (true) {
94 r = q->m_pNext;
95 q->m_pNext = p;
96
97 if (NULL == r) {
98 m_pHead = q;
99 break;
100 }
101 p = q;
102 q = r;
103 }
104 }
105
106 template<class T>
107 void SingleLink<T>::Print()
108 {
109 Node<T> *pTemp = m_pHead;
110 while (pTemp) {
111 cout << pTemp->m_key << " ";
112 pTemp = pTemp->m_pNext;
113 }
114 cout << endl;
115 }
116
117 int main()
118 {
119 SingleLink<int> SL;
120 for (int i = 1; i <= 5; i ++)
121 SL.Insert(i);
122 SL.Print();
123 SL.Insert(9);
124 SL.Insert(7);
125 SL.Print();
126 SL.Delete(7);
127 SL.Print();
128 SL.Delete(6);
129 SL.Print();
130 SL.Reverse();
131 SL.Print();
132 return 0;
133 }