刚看完数据结构,准备把主要数据结构实现一遍,下面是我写的单链表,大家看看怎么样??
主要是想大家指出一下不合理的问题,需要注意的方面..不胜感激
//MyList.h#ifndef MYLIST_H#define MYLIST_Htemplate<class T>class Node{ public: friend bool operator==(const Node<T>& lhs,const Node<T>& rhs); Node() { next=NULL; } Node(T rhs):val(rhs) { next=NULL; } T val; //结点的值 Node<T> *next; //指向下一个结点 };//定义结点类template<class T>class List{ public: List():head(NULL),length(0){} void InitList(); //初始化链表 void DestoryList(); //销毁链表 void ClearList(); //清除链表元素 bool ListEmpty(); //判断链表是否为空 int ListLength(); //返回链表长度 bool GetElem(int i,Node<T>& elem); //返回链表里的第i个数据元素 bool PriorElem(const Node<T>& cur,Node<T>& elem); //返回cur元素的前驱 bool NextElem(const Node<T>& cur,Node<T>& elem); //返回cur元素的后继 bool ListInsert(int i,T val); //在链表里的第i个数据元素前插入元素elem bool ListDelete(int i,Node<T>& elem); //删除链表里的第i个数据元素,用elem返回 void PrintList(); //输出链表的元素 private: Node<T> *head; //指向链表头结点 int length; //链表长度};//定义链表类#include "MyList.cpp"#endif//MyList.cpp#include "MyList.h"template<class T>bool operator==(const Node<T>& lhs,const Node<T>& rhs){ if(lhs.val==rhs.val) return true; else return false;}template<class T>void List<T>::InitList() //初始化链表{ head=new Node<T>(); }template<class T>void List<T>::DestoryList() //销毁链表{ ClearList(); delete head; head=NULL;}template<class T>void List<T>::ClearList() //清除链表元素{ Node<T> del_val; while(length>0) ListDelete(1,del_val);}template<class T>bool List<T>::ListEmpty() //判断链表是否为空{ if(head->next==NULL) return true; return false;}template<class T>int List<T>::ListLength() //返回链表长度{ return length;}template<class T>bool List<T>::GetElem(int i,Node<T>& elem) //返回链表里第i个数据元素{ if( i<1 || i>length ) { return false; } Node<T>* p=head; int cnt=0; while(cnt<i) { p=p->next; cnt++; } if(p) elem=*p; else return false; return true;}template<class T>bool List<T>::PriorElem(const Node<T>& cur,Node<T>& elem) //返回cur的前驱{ Node<T>* p=head; while(p!=NULL) { if(p->next) //防止对空链表操作 { if(*(p->next)==cur) { if(p!=head) { elem=*p; return true; } } } p=p->next; } return false;}template<class T>bool List<T>::NextElem(const Node<T>& cur,Node<T>& elem) //返回cur的后继{ Node<T>* p=head; while(p->next!=NULL) { if(*p==cur) { elem=*(p->next); return true; } p=p->next; } return false;}template<class T>bool List<T>::ListInsert(int i,T val) //在i位置之前插入数据元素elem{ if( i<1 || i>length+1 ) { return false; } Node<T>* p=head; int cnt=0; while(cnt<i-1) //找到第i-1个位置 { p=p->next; cnt++; } if(p) { Node<T>* pElem=new Node<T>(val); pElem->next=p->next; p->next=pElem; length++; return true; } return false;}template<class T>bool List<T>::ListDelete(int i,Node<T>& elem) //删除第i个位置的元素{ if( length<1 || i<1 || i>length ) { return false; } Node<T>* p=head; Node<T>* pre=NULL; int cnt=0; while(cnt<i) { if(cnt==i-1) //保存i-1位置元素的指针 pre=p; p=p->next; cnt++; } if(p && pre) { pre->next=p->next; elem=*p; delete p; length--; return true; } return false;}template<class T>void List<T>::PrintList() //打印链表数据元素{ Node<T>* p=head; while(p->next) { p=p->next; cout<<p->val<<" "; }}
//List.cpp
#include <iostream>
#include "MyList.h"
using namespace std;
int main()
{
List <int> list;
list.InitList();
Node <int> del;
for(int i=1;i <=10;i++)
{
list.ListInsert(i,i);
}
cout < <"当前链表长度：" < <list.ListLength() < <endl;
cout < <"打印链表：" < <endl;
list.PrintList();
cout < <"\n" < <list.ListEmpty() < <endl;
if(list.ListDelete(1,del))
cout < <"正在删除：" < <del.val < <endl;
cout < <"当前链表长度：" < <list.ListLength() < <endl;
cout < <"打印链表：" < <endl;
list.PrintList();
Node <int> val(4);
Node <int> ret;
if(list.PriorElem(val,ret))
cout < <"\n前驱是：" < <ret.val < <endl;
if(list.NextElem(val,ret))
cout < <"后继是：" < <ret.val < <endl;
list.ClearList();
cout < <"当前链表长度：" < <list.ListLength() < <endl;
list.DestoryList();
return 0;
}