| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 602 人关注过本帖
标题:郁闷的链表
只看楼主 加入收藏
想你的天空
Rank: 2
等 级:新手上路
威 望:5
帖 子:610
专家分:0
注 册:2004-12-30
收藏
 问题点数:0 回复次数:4 
郁闷的链表

#include<iostream> #include<assert.h> using namespace std; template<class T> class Chain; template<class T> class ChainNode{ friend class Chain<T>; public: ChainNode(){} //ChainNode(const T& data_): data(data_){} private: T data; ChainNode<T> *next; }; template<class T> ostream& operator<<(ostream& out,const Chain<T>&x); template<class T> class Chain{ public: Chain(){} ~Chain();//链表析构函数,用于上述链表种所有节点 Chain<T>* CreateList(int len); bool IsEmpty(); int Length() const; //返回链表中元素的总数 bool Find(int k,T& x) const;//寻找链表中的第k个元素,并将其传送到x。如果不存在第k个元素,则返回false,否则返回true int Search(const T&x) const;//寻找x,如果发现x,则返回x的地址下标,如果x不在链表中,则返回0 Chain<T>& Insert(int k,const T& x);//在第k个元素之后插入x Chain<T>& Delete(int k);//把第k个元素取至x,然后从链表中删除第k个元素 void Output(ostream& outs) const; friend ostream& operator<< <>(ostream& out,const Chain<T>&x);//重载<<*/ private: ChainNode<T> *first,*last; }; //创建链表 template<class T> Chain<T>* Chain<T>::CreateList(int len) { ChainNode<T> *link,*s; int flag = 1; first = new ChainNode<T>; link = first; cout<<"输入"<<len<<"个元素:"<<endl; while(len-->0) { s = new ChainNode<T>; cout<<"input the numbers:"; cin>>link->data; //创建的数据 if(link->data == 0) flag = 0; link->next = s; link = s; } link->next = NULL; } //析构函数 template<class T> Chain<T>::~Chain() {//链表析构函数,用于删除上述链表种所有节点 ChainNode<T>* link; while(first) { link = first->next; delete first; first = link; } } template<class T> bool Chain<T>::IsEmpty() { if(first->next == NULL) return false; else return true; } template<class T> int Chain<T>::Length() const {//返回链表中元素的总数 ChainNode<T> *current = first; int len = 0; while(current!=NULL) { len++; current = current->next; } return len-1; }

template<class T> bool Chain<T>::Find(int k,T& x)const {//寻找链表中的第k个元素,并将其传送到x。如果不存在第k个元素,则返回false,否则返回true if(k<1) { cout<<"i值非法"<<endl; return false; } ChainNode<T> *current = first; int index = 1; while(index<k && current) { current = current->next; index++; } if(current) { x = current->data; return true; } return false; //不存在第k个元素 } //查找 template<class T> int Chain<T>::Search(const T&x) const {//寻找x,如果发现x,则返回x的地址下标 //如果x不在链表中,则返回0 ChainNode<T> *current = first; int index = 1; while(current && current->data!=x) { current = current->next; index++; } if(current) return index; return 0; } //删除 template<class T> Chain<T>& Chain<T>::Delete(int k) {//把第k个元素取至x,然后从链表中删除第k个元素 //如果不存在第k个元素,则引发异常OutOfBounds if(k<1 || !first) cout<<"不存在您要删除的元素!"<<endl; //throw OutOfBounds(); //不存在第k个元素 //p最终指向第k个节点 ChainNode<T> *p = first; //将p移动至第k个元素,并从链表中删除该元素 if( k==1) //p已经指向第k个元素 first = first->next; else { //用q指向第k-1个元素 ChainNode<T> *q = first; for(int index = 1;index<k-1 && q; index++) q = q->next; //if(!q || !q->next) // cout<<"不存在第k个元素"<<endl; //throw OutOfBounds();//不存在第k个元素 p = q->next; //存在第k个元素,p现在已经指向第k个节点了 q->next = p->next;//从链表中删除元素 } delete p; //释放p节点 return *this; } //插入 template<class T> Chain<T>& Chain<T>::Insert(int k,const T& x) { if(k<0) cout<<"插入位置非法"<<endl;//throw OutOfBounds(); ChainNode<T> *p = first; for(int index = 1; index<k && p;index++) p = p->next;

ChainNode<T> *y = new ChainNode<T>; y->data = x; if(p) { y->next = p->next; p->next = y; } else { y->next = first; first = y; return *this; } } //输出 template<class T> void Chain<T>::Output(ostream& outs) const { ChainNode<T> *current; for(current = first;current->next!=NULL;current = current->next) outs<< current->data <<" "; } //重载<< template<class T> ostream& operator<<(ostream& outs,const Chain<T>& x) { x.Output(outs); return outs; } int main() { Chain<int> L1,L2; int wantFind; L1.CreateList(4); if(L1.IsEmpty()) cout<<"链表非空"<<endl; else cout<<"链表是空的!"<<endl; cout<<"链表长度是:"<<L1.Length()<<endl; cout<<"原始链表是:"<<L1<<endl; cout<<"查找第2个元素。。。"<<endl; if(L1.Find(2,wantFind)) cout<<"找到了第2个元素! 第2个元素是:" <<wantFind<<endl; cout<<"查找元素5:"<<endl; cout<<"元素5是第"<<L1.Search(5)<<"个"<<endl; cout<<"删除元素2..."<<endl; L1.Delete(L1.Search(2));//把第k个元素取至x,然后从链表中删除第k个元素 cout<<"删除2后的链表是"<<L1<<endl; cout<<"在第3个元素之后插入9..."<<endl; L1.Insert(3,9); cout<<"插入9后的链表是"<<L1<<endl; system("pause"); return 0; } 这个链表类终于能正确运行了,但是运行完就出现异常 , 不知道是什么原因

[此贴子已经被作者于2005-9-10 9:55:10编辑过]

搜索更多相关主题的帖子: 链表 
2005-09-10 09:31
想你的天空
Rank: 2
等 级:新手上路
威 望:5
帖 子:610
专家分:0
注 册:2004-12-30
收藏
得分:0 
救命啊

2005-09-10 17:06
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
//////////////////////////////////////////////////////////
//
//    try it -:)
//
//////////////////////////////////////////////////////////
#include&lt;iostream&gt;
using namespace std;

template&lt;class T&gt;
class Chain;

template&lt;class T&gt;
class ChainNode
{
  friend class Chain&lt;T&gt;;
private:
  T data;
  ChainNode&lt;T&gt; * next;
public:
  ChainNode(const T data)
  {
    this-&gt;data = data;
    next = NULL;
  }
};

template&lt;class T&gt;
ostream &amp; operator&lt;&lt;(ostream &amp; out,const Chain&lt;T&gt;&amp;x);

template&lt;class T&gt;
class Chain
{
public:
  Chain(const int len);
  ~Chain(); //destructor
  Chain&lt;T&gt;* getMe(){return this;}
  bool isEmpty();
  int length() const; //length of the chain
   
  //get the data of index k in the chain,
  //when data exist, return true, otherwise return false   
  bool dataOfElementAt(int k, T &amp; x);
   
  //search data x, when it can be found return its index
  //otherwise return -1
  int  search(const T&amp;x);
   
  //insert the data in the chain of before index k   
  Chain&lt;T&gt;&amp; insertElementAt(int k,const T&amp; x);
   
  //remove the element at index k from the chain
  Chain&lt;T&gt;&amp; removeElementAt(int k);
   
  friend ostream&amp; operator&lt;&lt; &lt;&gt;(ostream&amp; out,const Chain&lt;T&gt;&amp;x); //overloading &lt;&lt;*/
private:
  ChainNode&lt;T&gt; *begin,*end;
  int size;

  //get the address of the element in the chain
  //according of its index in the chain
  ChainNode&lt;T&gt; * elementAt(int index);

  void output(ostream&amp; outs) const;
};

//constructor
template&lt;class T&gt;
Chain&lt;T&gt;::Chain(const int len)
{
  ChainNode&lt;T&gt; * last = NULL, * current = NULL;
  T data = 0;
  size = 0;
  cout&lt;&lt;"Please enter "&lt;&lt;len&lt;&lt;" datum:"&lt;&lt;endl;
  for(int i = 0; i&lt;len; i++)
  {
    cout&lt;&lt;"input the value:";
    cin&gt;&gt;data;  
    current = new ChainNode&lt;T&gt;(data); //create node through constructor
    if(last != NULL)
    last-&gt;next = current;
    last = current;
    if(i == 0)
      begin = current;
    if(i == len-1)
      end = current;
    size++;
  }
}

//destructor
template&lt;class T&gt;
Chain&lt;T&gt;::~Chain()
{
  ChainNode&lt;T&gt; * temp = NULL;
  ChainNode&lt;T&gt; * current = begin;
  for(int i = 0; i&lt;size; i++)
  {
    temp = current-&gt;next;
    delete current;
    current = temp;
  }
  size = 0;
}

template&lt;class T&gt;
bool Chain&lt;T&gt;::isEmpty()
{
  return (size == 0);
}

template&lt;class T&gt;
int Chain&lt;T&gt;::length() const
{
  return size;
}

template&lt;class T&gt;
bool Chain&lt;T&gt;::dataOfElementAt(int k, T &amp; x)
{
  ChainNode&lt;T&gt; * p = elementAt(k);
  if(p == NULL)
  {  
    cout&lt;&lt;"sorry, it is a invalid index"&lt;&lt;endl;  
    return false;
  }
  x = p-&gt;data;
  return true;
}

template&lt;class T&gt;
ChainNode&lt;T&gt; * Chain&lt;T&gt;::elementAt(int index)
{
  ChainNode&lt;T&gt; * p = begin;
  int i = 0;
  if(index&lt;0 || index&gt;=size)
    return NULL;
  else if(index == 0)
    return p;
  while(i&lt;index)
  {
    p = p-&gt;next;
    i++;
  }
  return p;
}

template&lt;class T&gt;
int Chain&lt;T&gt;::search(const T&amp;x)
{
  int index = -1;
  T data = 0;
  for(int i = 0; i&lt;size; i++)
  {
    dataOfElementAt(i, data);
    if(data == x)
    {
      index = i;
      break;
    }
  }
  return index;
}


template&lt;class T&gt;
Chain&lt;T&gt;&amp; Chain&lt;T&gt;::removeElementAt(int k)
{
  if(k&lt;0 || k&gt;=size)  
    cout&lt;&lt;"invalid index, data not exist under this index!"&lt;&lt;endl;
  
  ChainNode&lt;T&gt; * left = NULL;
  ChainNode&lt;T&gt; * p = NULL;
  ChainNode&lt;T&gt; * right = NULL;

  if( k==0) //the first element
  {
    p = begin;
    begin = p-&gt;next;
    delete p;
    size--;
  }
  else if(k == size-1) // the last element
  {
    left = elementAt(k-1);
    end = left;
    p = left-&gt;next;
    delete p;
    size--;
  }
  else  // between the first element and the last element
  {
    left = elementAt(k-1);
    p = left-&gt;next;
    right = p-&gt;next;
    left-&gt;next = right;
    delete p;
    size--;
  }
  return *this;
}


template&lt;class T&gt;
Chain&lt;T&gt;&amp; Chain&lt;T&gt;::insertElementAt(int k,const T&amp; x)
{
  ChainNode&lt;T&gt; * left = NULL;
  ChainNode&lt;T&gt; * p = NULL;
  ChainNode&lt;T&gt; * right = NULL;

  if(k&lt;0 || k&gt;=size)
  {
    cout&lt;&lt;"invalid index"&lt;&lt;endl;
  }
  else
  {
    p = new ChainNode&lt;T&gt;(x);
    size++;
    if(k == 0)  // first element
    {
      p-&gt;next = begin;
      begin = p;
    }
    else
    {
      left = elementAt(k-1);
      right = left-&gt;next;
      p-&gt;next = right;
      left-&gt;next = p;
    }
  }
  return *this;
}


template&lt;class T&gt;
void Chain&lt;T&gt;::output(ostream&amp; outs) const
{
  ChainNode&lt;T&gt; *current;
  for(current = begin; current!=NULL; current = current-&gt;next)
    outs&lt;&lt; current-&gt;data &lt;&lt;" ";
}

//overloading&lt;&lt;
template&lt;class T&gt;
ostream&amp; operator&lt;&lt; (ostream&amp; outs,const Chain&lt;T&gt;&amp; x)
{
  x.output(outs);
  return outs;
}

int main()
{
  Chain&lt;int&gt; L1(4);
  int wantFind;
  
  if(L1.isEmpty())  
    cout&lt;&lt;"The chain is empty!"&lt;&lt;endl;
  else
    cout&lt;&lt;"The chain is not empty"&lt;&lt;endl;
  cout&lt;&lt;"The length of chain is: "&lt;&lt;L1.length()&lt;&lt;endl;
  cout&lt;&lt;"The original chain is: "&lt;&lt;L1&lt;&lt;endl;
  cout&lt;&lt;"Searching the element of index 2¡£¡£¡£"&lt;&lt;endl;
  if(L1.dataOfElementAt(2,wantFind))  
    cout&lt;&lt;"found! the element of index 2: " &lt;&lt;wantFind&lt;&lt;endl;
  cout&lt;&lt;"searching index in chain of Data 5:"&lt;&lt;endl;
  cout&lt;&lt;"Data 5 locating in chain of index "&lt;&lt;L1.search(5)&lt;&lt;endl;
  cout&lt;&lt;"Removing data 2..."&lt;&lt;endl;
  L1.removeElementAt(L1.search(2));
  cout&lt;&lt;"After removing of data 2, now the chain is "&lt;&lt;L1&lt;&lt;endl;
   
  cout&lt;&lt;"insert data 9 before index 3 in chain..."&lt;&lt;endl;
  L1.insertElementAt(3,9);  
  cout&lt;&lt;"After inserting of data 9, now the chain is "&lt;&lt;L1&lt;&lt;endl;  
  
  system("pause");
  return 0;
}


自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-10 20:33
想你的天空
Rank: 2
等 级:新手上路
威 望:5
帖 子:610
专家分:0
注 册:2004-12-30
收藏
得分:0 
开大侠, 能指出问题的本质所在吗?
              偶不知道从何开起啊,    是什么引起的呢

2005-09-11 12:45
kai
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:52
帖 子:3450
专家分:59
注 册:2004-4-25
收藏
得分:0 
// 你的程序中有四个地方有误,
// 一处是那个CreateList
//另一处是那个IsEmpty
//为了配合IsEmpty 正常工作,那个构造函数也要作改动
// 还有就是在 main() 里面,那个判断为空后的处理有逻辑问题

// 改动1
template&lt;class T&gt;
Chain&lt;T&gt;* Chain&lt;T&gt;::CreateList(int len)
{
    ChainNode&lt;T&gt; *link,*s;
  //int flag = 1;
    first = new ChainNode&lt;T&gt;;
    link = first;
    cout&lt;&lt;"ÊäÈë"&lt;&lt;len&lt;&lt;"¸öÔªËØ:"&lt;&lt;endl;
    while(len--&gt;0)
    {
        s = new ChainNode&lt;T&gt;;
        cout&lt;&lt;"input the numbers:";
        cin&gt;&gt;link-&gt;data;  //´´½¨µÄÊý¾Ý
        //if(link-&gt;data == 0)
        //    flag = 0;
        link-&gt;next = s;
        last = link;
        link = s;
    }
    last-&gt;next = NULL;

    return this;
}

// 改动2
template&lt;class T&gt;
bool Chain&lt;T&gt;::IsEmpty()            
{
    if(first == NULL)      
        return true;
    else
        return false;
}

// 改动3
Chain(){first = NULL; last = NULL;}

//改动4

在main() 中
if(L1.IsEmpty())  
        cout&lt;&lt;"The chain is empty"&lt;&lt;endl;
    else
        cout&lt;&lt;"The chain is not empty"&lt;&lt;endl;

// 主要的原因还是那个 create 函数出错。
另外提一点建议,作为OOP程序,一般变量名和函数名开始字母小写。
所以在我的程序中都改为小写了, 如 isEmpty
还有 index 0 作为第一个元素的 index 这在程序界也是一个惯例。

自由,民主,平等,博爱,进步.
中华民国,我的祖国,中华民国万岁!中华民国加油!
本人自愿加入中国国民党,为人的自由性,独立性和平等性而奋斗!
2005-09-11 17:35
快速回复:郁闷的链表
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.021098 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved