刚看完数据结构,准备把主要数据结构实现一遍,下面是我写的单链表,大家看看怎么样??
主要是想大家指出一下不合理的问题,需要注意的方面..不胜感激
- C/C++ code
//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- C/C++ code
//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<<" "; }}
- C/C++ code
//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;
}
[解决办法]
楼主，我告诉你个秘密，你不要告诉别人啊！
CSDN上的所有高手看了你的代码，都会微微一笑，然后想起自己年轻的时候也经常犯傻。
我没笑，因为我还年轻。
因为本人没学过C++，没学过数据结构，没学过算法，没学过模板。
所以看到楼主竟然用模板实现链表，很佩服，很不服气，所以才来吹牛，我说的话楼主不要往心里去。
你写的很烂。
1.你想知道自己写的好不好，不如去和stl中的list比较一下。
如果第1条是废话。那么我就说点具体的。
2.为什么返回值是bool？也许你希望在某种情况下，判断操作有没有正确执行。但假如有很多步操作，我都要确保它们执行完成，那么我是不是要写很多的if，else？你把你写的链表给客户用，客户会因为你的链表而增加大量的冗余代码。
3.GetElem PriorElem NextElem ， 这三个函数，以及所有有“返回值”的函数，都存在同样一个问题：客户必须知道你写的链表的内部节点的结构。一个很恰当的比方：你去超市买东西，进去的时候，你把你的手提包存在存包点，买完东西回来发现，你必须把一个特定的“盒子”，交给存包点，存包点把你的包放进盒子，在把盒子交给你。而且更加疯狂的是，这个盒子还必须“自备”。你希望客户知道你的链表的节点的结构，这样方便你返回，方便你查找，但是客户可不这么认为，客户认为，我存进去的数据是什么，那么返回的就是什么，存int型数据，返回的竟然是一个Node类型的数据？思维怪异。
4.为什么初始化的时候要加一个节点进去？为什么链表中有一个节点，而链表的长度依然为0？如果是头节点，那么为什么需要头节点？数据结构的书可不要学死了。
几点建议：
将list设为node的友元，node的所有数据成员，所有成员函数均为private。
该返回bool的返回bool，该返回元素值的返回元素值，像insert某某，不如干脆不返回。
如果希望某些操作有某些保障，那么不要用返回值来确定操作是否完成，而应该在操作没有正确完成时---抛出异常。（and stay away from exit()!!!!!）
将没必要的诸如：GetHead， GetTail之类完全删除，因为这个操作竟然返回私有成员的地址，你主动破坏封装？
多注意细节没什么不好，多注意效率没什么不好，但是你首先要把事情做对，然后再做好。
你的list的接口我都看了，具体实现我只看了一点点。因为我觉得你很认真好学，所以我才说上面一堆废话。你用模板写，狠好，我100多号同学，知道什么是模板的寥寥无几，像我就啥都不懂，更别说用模板写容器了。所以，你要做业内人士，就一定要走出“思维怪异”的怪圈，拥抱面向对象思想。
[解决办法]
两句话送给楼主：
一句是我学长说的：“C++,MFC,数据结构，算法，这些都是基础呀。”
一句是侯捷说的：“勿在浮沙筑高台。”
[解决办法]
如果需要用带头节点的链表，头节点不要去new，直接把Node<T> *head;改成Node<T> head;。如果需要带尾节点的链表，也作同样的修改。
不要让你的公开函数返回T类型和基本类型（bool，int）之外的任何类型，因为那些类型跟这个类的使用者无关，只跟设计者也就是你有关。
不要把只在链表内部使用的Node类型定义在跟List平等的地位上，它只是在List内部使用，定义成List的一个私有的内部类型，或者象23楼说的那样也好。
另外，搞笑的是，你的Node的成员既然都是public的，为什么还会在里面有个friend声明呢？你可能根本没有去想friend是干什么的。
祝你进步！
[解决办法]
LZ的编程风格与注释的好习惯还是十分值得称赞的，23楼的建议还是挺中肯的。用面向对象的思想编程，没有数据抽象的过程应该不能称的上是面向对象。没有很好的进行数据抽象，类的封装不合理，这可能是一个漫长的过程，另关键字friend用的让人摸不着头脑，先搞明白自己想要实现的功能。祝LZ进步。