随笔 - 8  文章 - 26  trackbacks - 0
<2024年5月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

常用链接

留言簿(4)

随笔档案

文章分类

文章档案

相册

C++语言

搜索

  •  

最新评论

阅读排行榜

评论排行榜

单向带头结点循环链表实现
1
  1#ifndef LIST_H
  2#define LIST_H
  3#include <iostream>
  4//链表节点
  5template<class T>
  6class ListNode
  7{
  8public:
  9    ListNode(ListNode<T>* nextnode=0,const T &val=T())
 10    {
 11    data=val;
 12    next=nextnode;
 13    }
 14public:
 15T data;
 16    ListNode<T> *next;
 17
 18};
 19
 20//链表实现
 21template<class T>
 22class List
 23{
 24
 25public:
 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
 37private:
 38    ListNode<T>*front,*rear,*head;//头指针与尾指针
 39    int size;//链表元素节点数目
 40};
 41
 42
 43
 44
 45//---------------------------------------------------------------------
 46template<class T>
 47List<T>::~List()
 48{
 49Delete_All();
 50delete head;
 51
 52}
 53//---------------------------------------------------------------------
 54template<class T>
 55List<T>::List()
 56{
 57//构造头接点
 58head=new ListNode<T>();
 59front=rear=head;
 60head->next=head;
 61}
 62
 63//---------------------------------------------------------------------
 64template<class T>
 65void List<T>::Insert_Front(const T &e)
 66{
 67    ListNode<T> *NewNode=new ListNode<T>(0,e);
 68if(front->next==head)//如果链表为空
 69{
 70
 71front->next=NewNode;
 72NewNode->next=head;
 73rear=NewNode;
 74}
 75else//链表不为空
 76{
 77NewNode->next=front->next;
 78front->next=NewNode;
 79}
 80++size;
 81}
 82//---------------------------------------------------------------------
 83template<class T>
 84void List<T>::Insert_End(const T &e)
 85{
 86    ListNode<T> *NewNode=new ListNode<T>(0,e);
 87if(front->next==head)//如果链表为空
 88{
 89
 90front->next=NewNode;
 91NewNode->next=head;
 92rear=NewNode;
 93}
 94else//链表不为空
 95{
 96rear->next=NewNode;
 97NewNode->next=head;
 98rear=NewNode;
 99
100}
101++size;
102}
103//---------------------------------------------------------------------
104template<class T>
105ListNode<T>* List<T>::Find(const T &e)
106{
107head->data=e;
108ListNode<T> *move=front->next;
109while(move->data!=e)
110{
111move=move->next;
112}
113
114if(move==front) return NULL;
115else
116return move;
117}
118
119//---------------------------------------------------------------------
120template<class T>
121bool List<T>::Delete(const T &e)
122{
123head->data=e;
124ListNode<T> *move=front->next;
125ListNode<T> *pmove=head;
126while(move->data!=e)
127{
128    pmove=move;
129move=move->next;
130}
131if(move==head) return false;//未找到节点
132pmove->next=move->next;
133if(move==rear)//如果为尾节点则修改尾指针
134rear=pmove;
135delete move;
136return true;
137}
138
139//---------------------------------------------------------------------
140template<class T>
141void List<T>::OutPut()
142{
143ListNode<T> *move=front->next;
144while(move!=head)
145{
146cout<<move->data<<" ";
147move=move->next;
148}
149cout<<endl;
150}
151//---------------------------------------------------------------------
152template<class T>
153List<T>& List<T>::Delete_All()
154{
155ListNode<T> *movenext,*move=front->next;
156
157while(move!=head)
158{
159movenext=move->next;
160delete move;
161move=movenext;
162}
163front=rear=head;
164head->next=head;
165
166return *this;
167}
168//---------------------------------------------------------------------
169template<class T>
170bool List<T>::IsEmpty()
171{
172
173if(head->next=head) return true;
174else 
175return false;
176}
177#endif
posted on 2008-09-18 20:54 杨彬彬 阅读(1712) 评论(0)  编辑 收藏 引用 所属分类: 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Copyright ©2024 杨彬彬 Powered by: 博客园 模板提供：沪江博客