学习链表时遇到的问题
C++菜鸟求助：（用的是VS2005）【在.cpp文件中的template <class T>
void Chain<T>::Insert(int i, T x)函数中,函数结尾加上delete s;把动态分配的s释放就会报错?不添加的话程序是正确的；最近看了下内存管理，不明白为什么】
//Chain.h 声明类Chain
#ifndef CHAIN_H
#define CHAIN_H
//C++中struct和class的区别是：在struct中，缺省的访问级别是public，
//而在class中，缺省的访问级别是private，除此之外，struct和class
//是等价的！
template <class T>
struct Node
{
T data;
Node<T> *next;
};
template <class T>
class Chain
{
public:
Chain( ); //建立只有头结点的空链表
Chain(T a[ ], int n); //建立有n个元素的单链表
~Chain(); //析构函数
int Length(); //求单链表的长度
T Get(int i); //取单链表中第i个结点的元素值
int Locate(T x); //求单链表中值为x的元素序号
void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点
T Delete(int i); //在单链表中删除第i个结点
void PrintList( ); //遍历单链表，按序号依次输出各元素
private:
Node<T> *first; //单链表的头指针
};
#endif
//Chain.cpp
#include "Chain.h"
/*
*前置条件：单链表不存在
*输 入：无
*功 能：构建一个只有头结点的单链表
*输 出：无
*后置条件：构建一个只有头结点的单链表
*/
template<class T>
Chain<T>::Chain()
{
first=new Node<T>;
first->next=NULL;
}
/*
*前置条件：单链表不存在
*输 入：顺序表信息的数组形式a[],单链表长度n
*功 能：将数组a[]中元素建为长度为n的单链表
*输 出：无
*后置条件：构建一个单链表
*/
template<class T>
Chain<T>::Chain(T a[], int n)
{
first=new Node<T>;//生成头结点
Node<T>*r,*s;
r=first;//尾指针初始化
for(int i=0;i<n;i++)
{
s=new Node<T>;
s->data=a[i];//为每个数组元素建立一个结点
r->next=s;//插入到终端结点之后
r=s;//尾指针指向最后一个节点
}
r->next=NULL; //单链表建立完毕，将终端结点的指针域置空;其中r是指向
//终节点的指针
}
/*
*前置条件：无
*输 入：无
*功 能：释放动态分配的资源
*输 出：无
*后置条件：无
*/
template <class T>
Chain<T>:: ~Chain()
{
delete first;first=NULL;
}
/*
*前置条件：单链表存在
*输 入：查询元素位置i
*功 能：按位查找位置为i的元素并输出值
*输 出：查询元素的值
*后置条件：单链表不变
*/
template <class T>
T Chain<T>::Get(int i)
{
Node<T> *p; int j;
p=first->next; j=1;//或p=first;j=0;(因为有头结点，故第0个节点可以不查询)
while (p && j<i)
{
p=p->next; //检测指针p后移
j++;
}//如果查找成功，返回的是位置i的前置节点
if (!p) throw "位置不合适";
else return p->data;
}
/*
*前置条件：单链表存在
*输 入：查询元素值x
*功 能：按值查找值的元素并输出位置
*输 出：查询元素的位置
*后置条件：单链表不变
*/
template <class T>
int Chain<T>::Locate(T x)
{
Node<T> *p; int j;
p=first->next; j=1;
while(p&&p->data!=x)
{
p=p->next;
j++;
}
if(p)
return j;
else
throw "位置不对!";
}
/*
*前置条件：单链表存在
*输 入：插入元素x,插入位置i
*功 能：将元素x插入到单链表中位置i处
*输 出：无
*后置条件：单链表插入新元素
*/
template <class T>
void Chain<T>::Insert(int i, T x)
{
Node<T> *p;
int j;
p=first ; //工作指针p初始化
j=0;
while (p && j<i-1)
{
p=p->next; //检测指针p后移
j++;
}//如果位置正确的话，指针移到指向i-1的位置
if (!p) throw "位置";
else {
Node<T> *s;
s=new Node<T>;
s->data=x; //向内存申请一个结点s，其数据域为x
s->next=p->next; //将结点s插入到结点p之后
p->next=s;
//?为何不能用操作符，加入delete s;就会报错
}
}
/*
*前置条件：单链表存在
*输 入：无
*功 能：输出单链表长度
*输 出：单链表长度
*后置条件：单链表不变
*/
template <class T>
int Chain<T>::Length( )
{
Node <T> *p = first->next;//指向第一个数据节点
int i = 0;
while(p)
{
p = p->next;
i++;
}
return i;
}
/*
*前置条件：单链表存在
*输 入：要删除元素位置i
*功 能：删除单链表中位置为i的元素
*输 出：无
*后置条件：单链表删除元素
*/
template <class T>
T Chain<T>::Delete(int i)
{
Node<T> *p;
int j;
p=first;//工作指针p初始化
j=0;
while (p && j<i-1) //查找第i-1个结点
{
p=p->next;
j++;
}
if (!p || !p->next) throw "位置不正确"; //结点p不存在或结点p的后继结点不存在
else{
Node<T> *q;
int x;
q=p->next; x=q->data; //暂存被删结点
p->next=q->next; //摘链
delete q; q=NULL;
return x;
}
}
/*
*前置条件：单链表存在
*输 入：无
*功 能：单链表遍历
*输 出：输出所有元素
*后置条件：单链表不变
*/
template <class T>
void Chain<T>::PrintList( )//LinkListMain.cpp
#include <iostream> //引用输入输出流库函数的头文件
using namespace std;
#include "Chain.cpp" //引用单链表的类
void main( )
{
Chain <int> a;
cout<<"执行插入操作:"<<endl;
try
{
a.Insert(1,4);
a.Insert(2,5);
a.Insert(3,6);
}
catch(char* wrong)
{
cout << wrong; //如失败提示失败信息
}
cout<<"已经插入“4，5，6”"<<endl;
cout<<"单链表a的长度为:"<<endl;
cout<<a.Length()<<endl; //返回单链表长度
cout<<endl;
cout<<"单链表a的元素为:"<<endl;
a.PrintList(); //显示链表中所有元素 //显示链表中所有元素
cout<<endl;
cout<<"按位查找第二个元素:"<<endl;
cout<<"第二个元素为:";
cout<<a.Get(2)<<endl; //查找链表中第二个元素
cout<<endl;
cout<<"按值查找10"<<endl;
cout<<"值为10的元素位置为:";
try{
cout<<a.Locate(10)<<endl; }//查找元素5，并返回在单链表中位置
catch(char* wrong){
cout << wrong; //如失败提示失败信息
}
cout<<endl;
cout<<"执行删除4的操作"<<endl;
a.Delete(1); //删除元素4
cout<<"已删除成功，单链表a的长度为";
cout<<a.Length()<<endl;
cout<<endl;
cout<<"链表a中的元素为:"<<endl;
a.PrintList();
int r[ ]={1,2,3,4,5};
Chain <int> b(r,5); //根据数组创建单链表
cout<<"执行插入操作前单链表b为:"<<endl;
b.PrintList(); //输出单链表所有元素
cout<<"插入前单链表b的长度为:";
cout<<b.Length()<<endl;
try
{
b.Insert(3,8);
}
catch(char* wrong)
{
cout << wrong; //如失败提示失败信息
}
cout<<"执行插入操作后单链表b为:"<<endl;
b.PrintList(); //输出单链表b所有元素
cout<<"插入后单链表b的长度为:";
cout<<b.Length()<<endl;
cout<<endl;
try
{
if(a.Length()){
cout<<"执行删除第一个元素操作:"<<endl;
cout<<endl;
b.Delete(1); //删除b中第一个元素
cout<<"已删除成功，单链表b的长度为:";
cout<<b.Length()<<endl;
}
else{
cout<<"顺序表b长度为0"<<endl;
}
}
catch(char* wrong)
{
cout << wrong; //如失败提示失败信息
}
cout<<"执行插入操作后单链表b为:"<<endl;
b.PrintList(); //输出单链表所有元素
}
{
Node<T> *p;
p=first->next;
while (p)
{
cout<<p->data<<endl;
p=p->next;
}
cout<<endl;
}
