单向带头结点循环链表实现

#ifndef LIST_H
2

#define LIST_H
3

#include <iostream>
4

//链表节点
5

template<class T>
6

class ListNode
7

{
8

public:
9

ListNode(ListNode<T>* nextnode=0,const T &val=T())
10

{
11

data=val;
12

next=nextnode;
13

}
14

public:
15

T data;
16

ListNode<T> *next;
17

};
19

//链表实现
21

template<class T>
22

class List
23

{
24

public:
26

List();
27

virtual ~List();
28

void Insert_Front(const T &e);//向表头插入节点
29

void Insert_End(const T &e);//向表尾插入节点
30

ListNode<T>* Find(const T &e);//查找指定节点
31

bool Delete(const T &e);//删除指定节点
32

List<T>& Delete_All();//删除除了头结点以外的所有节点
33

bool IsEmpty();//测试链表是否为空
34

bool Size() const {return size;}//返回链表中的节点数目
35

void OutPut();
36

private:
38

ListNode<T>*front,*rear,*head;//头指针与尾指针
39

int size;//链表元素节点数目
40

};
41

//---------------------------------------------------------------------
46

template<class T>
47

List<T>::~List()
48

{
49

Delete_All();
50

delete head;
51

}
53

//---------------------------------------------------------------------
54

template<class T>
55

List<T>::List()
56

{
57

//构造头接点
58

head=new ListNode<T>();
59

front=rear=head;
60

head->next=head;
61

}
62

//---------------------------------------------------------------------
64

template<class T>
65

void List<T>::Insert_Front(const T &e)
66

{
67

ListNode<T> *NewNode=new ListNode<T>(0,e);
68

if(front->next==head)//如果链表为空
69

{
70

front->next=NewNode;
72

NewNode->next=head;
73

rear=NewNode;
74

}
75

else//链表不为空
76

{
77

NewNode->next=front->next;
78

front->next=NewNode;
79

}
80

++size;
81

}
82

//---------------------------------------------------------------------
83

template<class T>
84

void List<T>::Insert_End(const T &e)
85

{
86

ListNode<T> *NewNode=new ListNode<T>(0,e);
87

if(front->next==head)//如果链表为空
88

{
89

front->next=NewNode;
91

NewNode->next=head;
92

rear=NewNode;
93

}
94

else//链表不为空
95

{
96

rear->next=NewNode;
97

NewNode->next=head;
98

rear=NewNode;
99

100

}
101

++size;
102

}
103

//---------------------------------------------------------------------
104

template<class T>
105

ListNode<T>* List<T>::Find(const T &e)
106

{
107

head->data=e;
108

ListNode<T> *move=front->next;
109

while(move->data!=e)
110

{
111

move=move->next;
112

}
113

114

if(move==front) return NULL;
115

else
116

return move;
117

}
118

119

//---------------------------------------------------------------------
120

template<class T>
121

bool List<T>::Delete(const T &e)
122

{
123

head->data=e;
124

ListNode<T> *move=front->next;
125

ListNode<T> *pmove=head;
126

while(move->data!=e)
127

{
128

pmove=move;
129

move=move->next;
130

}
131

if(move==head) return false;//未找到节点
132

pmove->next=move->next;
133

if(move==rear)//如果为尾节点则修改尾指针
134

rear=pmove;
135

delete move;
136

return true;
137

}
138

139

//---------------------------------------------------------------------
140

template<class T>
141

void List<T>::OutPut()
142

{
143

ListNode<T> *move=front->next;
144

while(move!=head)
145

{
146

cout<<move->data<<" ";
147

move=move->next;
148

}
149

cout<<endl;
150

}
151

//---------------------------------------------------------------------
152

template<class T>
153

List<T>& List<T>::Delete_All()
154

{
155

ListNode<T> *movenext,*move=front->next;
156

157

while(move!=head)
158

{
159

movenext=move->next;
160

delete move;
161

move=movenext;
162

}
163

front=rear=head;
164

head->next=head;
165

166

return *this;
167

}
168

//---------------------------------------------------------------------
169

template<class T>
170

bool List<T>::IsEmpty()
171

{
172

173

if(head->next=head) return true;
174

else
175

return false;
176

}
177

#endif

posted on 2008-09-18 20:54 杨彬彬阅读(1736) 评论(0) 编辑收藏引用所属分类: 数据结构

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: 循环队列实现数据结构栈简单实现（基于链表）栈结构简单实现（基于数组）单向带头结点循环链表实现关于红黑树（r-b树）的相关资料二叉搜索树实现二叉树实现最大高度优先左高树（HBLT）实现最大堆实现链表类---转载

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

常用链接

留言簿(4)

随笔档案

文章分类

文章档案

相册

C++语言

搜索

最新评论

阅读排行榜

评论排行榜