Code Knight

Programming is so cool

隨筆 - 52, 文章 - 0, 評論 - 14, 引用 - 0

數據加載中……

一道面試題

最近面試遇到一道很懷念的題目，約瑟夫環，由于代碼較多沒有當時寫在卷上，說了說思路，下來用模板實現了一下，使用雙向循環鏈表，每到第五個kick out。
注：模板未考慮非常規自定義類型的淺拷貝問題；另外代碼沒有優化，delnode效率有提升空間，有興趣的改改看。

template<class T>
2

struct SNode
3

{
4

SNode(T dNode)
5

{
6

dData = dNode;
7

}
8

T dData;
9

SNode<T>* pNext;
10

SNode<T>* pPre;
11

};
12

template<class T>
14

class CDoubleList
15

{
16

public:
17

CDoubleList(T dDode);
18

~CDoubleList();
19

public:
20

bool AddNode(T dNode);
21

SNode<T>* DelNode(T dNode);
22

int GetSize(){return m_nListSize;}
23

void PrintList();
24

SNode<T>* GetHead(){return m_pHead;}
26

private:
27

SNode<T>* m_pHead;
28

SNode<T>* m_pTail;
29

int m_nListSize;
31

};
32

template<class T>
34

CDoubleList<T>::CDoubleList(T dHead):m_nListSize(0)
35

{
36

m_pHead = new SNode<T>(dHead);
37

if(!m_pHead)
38

{
39

// error
40

return;
41

}
42

m_pTail = m_pHead;
44

m_pHead->pPre = m_pTail;
45

m_pHead->pNext = m_pTail;
46

m_pTail->pPre = m_pHead;
47

m_pTail->pNext = m_pHead;
48

++m_nListSize;
50

}
51

template<class T>
53

CDoubleList<T>::~CDoubleList()
54

{
55

SNode<T>* pStart = m_pHead;
56

for(int i = 0; i < m_nListSize; ++i)
57

{
58

DelNode(pStart->dData);
59

}
60

}
61

template<class T>
63

bool CDoubleList<T>::AddNode(T dNode)
64

{
65

if(GetSize() < 1)
66

return false;
67

SNode<T>* pNewNode = new SNode<T>(dNode);
69

pNewNode->pPre = m_pTail;
70

pNewNode->pNext = m_pTail->pNext;
71

m_pTail->pNext = pNewNode;
72

pNewNode->pNext->pPre = pNewNode;
73

m_pTail = pNewNode;
75

++m_nListSize;
77

return true;
79

}
80

template <class T>
82

SNode<T>* CDoubleList<T>::DelNode(T dNode)
83

{
84

static SNode<T>* pNode = m_pHead;
85

// 遍歷，找到相同的刪除
86

for(int i = 0; i < m_nListSize; ++i)
87

{
88

if(pNode->dData == dNode)
89

{
90

if(pNode == m_pHead)
91

{
92

// 刪除頭，特殊處理
93

pNode->pPre->pNext = pNode->pNext;
94

pNode->pNext->pPre = pNode->pPre;
95

m_pTail = pNode->pPre;
97

SNode<T>* pNewNode = pNode->pNext;
99

delete pNode;
100

101

pNode = pNewNode;
102

103

m_pHead = pNode;
104

105

--m_nListSize;
106

return m_pHead;
107

}
108

else
109

{
110

pNode->pPre->pNext = pNode->pNext;
111

pNode->pNext->pPre = pNode->pPre;
112

113

SNode<T>* pNewNode = pNode->pNext;
114

delete pNode;
115

116

pNode = pNewNode;
117

118

--m_nListSize;
119

120

return pNode;
121

}
122

}
123

124

pNode = pNode->pNext;
125

}
126

127

return 0;
128

}
129

130

131

template <class T>
132

void CDoubleList<T>::PrintList()
133

{
134

SNode<T>* pNode = m_pHead;
135

for(int i = 0; i < m_nListSize; ++i)
136

{
137

cout<<pNode->dData<<endl;
138

139

pNode = pNode->pNext;
140

}
141

}

#include "list.h"

#include <iostream>

using namespace std;

void main()

{

CDoubleList<int> dList(1);

for(int i = 2; i < 10; ++i)

{

dList.AddNode(i);

}

dList.PrintList();

cout<<"begin do something

"<<endl;

SNode<int>* pStart= dList.GetHead();

while(dList.GetSize() != 1) // 數到第五個人出局

{

for(int i = 0; i < 4; ++i)

{

if(!pStart)

{

//error

}

pStart = pStart->pNext;

}

pStart = dList.DelNode(pStart->dData);

}

dList.PrintList();

cout<<"magic end

"<<endl;

getchar();

}

posted on 2010-04-12 15:55 Code Knight 閱讀(358) 評論(0) 編輯收藏引用所屬分類: C++與編程之道

只有注冊用戶登錄后才能發表評論。


相關文章: 一道面試題 total commader插件編寫 ZT-劍道與編程之道

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

Code Knight

一道面試題

導航

公告

常用鏈接

留言簿(5)

隨筆分類

隨筆檔案

技術鏈接

搜索

最新評論

閱讀排行榜

評論排行榜