The solution to Implement a circular buffer of size N
17376 ワード
ええと、長い間引きずっていて、やる時間がありませんでした~最初は配列で実現しようと思っていましたが、テーマがよく見えませんでしたね.
チェーンテーブルの操作は描くことで、書くときは注意深く、特に前の変数が変わっていないことに注意し、一時的な変数を加えて保存します.
チェーンテーブルは挿入しやすく、削除します.配列はランダムアクセスです.両者を組み合わせて使うともっといいです.
チェーンテーブルの操作は描くことで、書くときは注意深く、特に前の変数が変わっていないことに注意し、一時的な変数を加えて保存します.
チェーンテーブルは挿入しやすく、削除します.配列はランダムアクセスです.両者を組み合わせて使うともっといいです.
1 #include <iostream>
2 #include <string>
3
4 using namespace std;
5
6 typedef unsigned int UINT;
7 typedef struct SingleNode
8 {
9 SingleNode():next(NULL){}
10 string data;
11 SingleNode * next;
12 }SingleNode;
13
14 class CircularBuffer
15 {
16 public:
17 CircularBuffer(UINT size):m_nBufferSize(size),m_nCurrentSize(0)
18 {
19 m_pHead = new SingleNode();
20 m_pTail = m_pHead;
21 }
22 ~CircularBuffer(){ Release();}
23 public:
24 bool Append(UINT num);
25 bool Remove(UINT num);
26 bool List();
27 private:
28 bool IsFull();
29 bool IsEmpty();
30 bool Release();
31 private:
32 UINT m_nBufferSize;
33 UINT m_nCurrentSize;
34 SingleNode * m_pHead;
35 SingleNode * m_pTail;
36 };
37 //
38 bool CircularBuffer::IsFull()
39 {
40 return m_nCurrentSize >= m_nBufferSize;
41 }
42 bool CircularBuffer::IsEmpty()
43 {
44 return !m_nCurrentSize;
45 }
46 bool CircularBuffer::Release()
47 {
48 if(NULL == m_pHead || NULL == m_pHead->next)
49 return true;
50 SingleNode * currentNode = m_pHead->next, *tempNode = NULL;
51 while(m_pHead != currentNode)
52 {
53 tempNode = currentNode->next;
54 delete currentNode;
55 currentNode = tempNode;
56 }
57 return true;
58 }
59 bool CircularBuffer::Append(UINT num)
60 {
61 for(int i = 0; i < num; i++)
62 {
63 SingleNode * newNode = new SingleNode();
64 cin >> newNode->data;
65 m_pTail->next = newNode;
66 m_pTail = newNode;
67 m_pTail->next = m_pHead;
68 if(IsFull())
69 {
70 SingleNode * tempNode = m_pHead->next;
71 m_pHead->next = tempNode->next;
72 delete tempNode;
73 }
74 else m_nCurrentSize ++;
75 }
76 return true;
77 }
78 bool CircularBuffer::Remove(UINT num)
79 {
80 SingleNode * tempNode;
81 for(int i = 0; i < num; i++)
82 {
83 tempNode = m_pHead->next;
84 if(m_pHead == tempNode) break;
85 m_pHead->next = tempNode->next;
86 delete tempNode;
87 m_nCurrentSize --;
88 }
89 if(IsEmpty())
90 {
91 m_pHead->next = NULL;
92 m_pTail = m_pHead;
93 }
94 return true;
95 }
96 bool CircularBuffer::List()
97 {
98 if(NULL == m_pHead || NULL == m_pHead->next)
99 return true;
100 SingleNode * tempNode = m_pHead->next;
101 while(m_pHead != tempNode)
102 {
103 cout << tempNode->data << endl;
104 tempNode = tempNode->next;
105 }
106 return true;
107 }
108 void parseCmd(CircularBuffer&cb)
109 {
110 char cmd;
111 UINT pram;
112 while(cin >> cmd)
113 {
114 switch(cmd)
115 {
116 case 'A':
117 cin >> pram;
118 cb.Append(pram);
119 break;
120 case 'R':
121 cin >> pram;
122 cb.Remove(pram);
123 break;
124 case 'L':
125 cb.List();
126 break;
127 case 'Q':
128 return;
129 default:break;
130 }
131 }
132 }
133 int main()
134 {
135 UINT size;
136 while(cin >> size)
137 {
138 CircularBuffer cb(size);
139 parseCmd(cb);
140 }
141 return 0;
142 }