C++ 实现静态单链表的实例

C++ 实现静态单链表的实例

利用数组实现的静态单链表，与严蔚敏书实现略有不同，不另设回收空间。有任何BUG或错误，希望各位朋友多多反馈~~感激不尽

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

/* Author : Moyiii

* Mail: lc09@vip.qq.com

* 静态链表实现，仅作学习之用，当然如果

* 你想拿去用，随你好啦。

*/

#include <iostream>

using namespace std;

#define MAX_LIST_SIZE 100

class Node

{

public:

int data;

int cur;

};

class SLinkList

{

public:

SLinkList();

//和普通的线性链表区别不是很大。除了两个分配

//和回收节点空间的函数，具体算法请参考课本或

//网络资料

int newNode();

bool deleteNode(int pos);

bool insertElem(int pos, int elem);

bool deleteElem(int pos);

int& getElem(int pos);

int getLength();

bool isEmpty();

void print();

void clear();

private:

int head;//这个可以不要，默认等于0

int space;

int length;

Node *elems;

};

SLinkList :: SLinkList()

{

// 0号位置为头几点，不可以更改，初始指向自己

// 从1~MAXLENGTH为可分配节点，最初由space管理

elems = new Node[MAX_LIST_SIZE];

if(!elems)

{

cout << "Malloc failed!" << endl;

}

head = space = length = 0;

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

{

elems[i].data = i;

elems[i].cur = i + 1;

}

elems[MAX_LIST_SIZE - 1].cur = 0;

elems[0].cur = 0;

space = 1;

}

//从space指向的备用节点链表中取下一个节点

int SLinkList :: newNode()

{

if(space == 0)

{

cout << "Space is full!" << endl;

return 0;

}

int pos = space;

space = elems[space].cur;

elems[pos].cur = 0;

return pos;

}

//回收节点空间

bool SLinkList :: deleteNode(int pos)

{

if(pos == 0)

{

cout << "Free space Error!" << endl;

return false;

}

elems[pos].cur = space;

space = pos;

return true;

}

//插入节点，思路类似，找到被删除节点的前一个节点

//然后更改指向

bool SLinkList :: insertElem(int pos, int elem)

{

if(length == MAX_LIST_SIZE)

{

cout << "Space is Full" << endl;

return false;

}

if(pos < 1 || pos > length + 1)

{

cout << "Insert Over Bound" << endl;

return false;

}

int index = head;

for(int i = 1; i <= pos - 1; ++i)

{

index = elems[index].cur;

}

int node = newNode();

if(node == 0)

{

cout << "Space malloc failed" << endl;

return false;

}

elems[node].data = elem;

elems[node].cur = elems[index].cur;

elems[index].cur = node;

length++;

return true;

}

//一回事，注意把删除的节点回收给space

bool SLinkList :: deleteElem(int pos)

{

if(pos < 1 || pos > length)

{

cout << "Delete Node over Bound!" << endl;

return false;

}

int index = head;

for(int i = 1; i <= pos - 1; ++i)

{

index = elems[index].cur;

}

int node = elems[index].cur;

elems[index].cur = elems[node].cur;

deleteNode(node);

length--;

return true;

}

void SLinkList :: print()

{

int index = elems[head].cur;

while(index != 0)

{

cout << elems[index].data << " ";

index = elems[index].cur;

}

cout << endl;

return;

}

int SLinkList :: getLength()

{

return length;

}

bool SLinkList :: isEmpty()

{

if(length == 0)

{

return true;

}

else

{

return false;

}

int& SLinkList :: getElem(int pos)

{

int index = head;

for(int i = 1; i <= pos; ++i)

{

index = elems[index].cur;

}

return elems[index].data;

}

void SLinkList :: clear()

{

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

{

elems[i].data = i;

elems[i].cur = i + 1;

}

elems[MAX_LIST_SIZE - 1].cur = 0;

elems[0].cur = 0;

space = 1;

}

int main()

{

//测试数据，测试插入删除空间是否溢出

SLinkList myList;

for(int i = 1; i <= 105; ++i)

{

myList.insertElem(1,i);

}

//myList.print();

for(int i = 1; i <= 105; ++i)

{

myList.deleteElem(1);

}

//myList.print();

//普通测试

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

{

myList.insertElem(1,i);

}

myList.print();

cout << "Length= " << myList.getLength() <<endl;

myList.deleteElem(5);

myList.print();

cout << "Length= " << myList.getLength() <<endl;

cout << myList.isEmpty() << endl;

int &elem = myList.getElem(3);

elem = 99;

myList.print();

myList.clear();

myList.print();

return 0;

}

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

C++ 实现静态单链表的实例

相关文章

快网idc优惠网

相关文章

微信

快网idc优惠网

QQ交流群