#include "stdafx.h"
#include <stdio.h>
#include <iostream>
using namespace std;
//定义线性表类List
template <class T>
class List {
void clear(); //置空线性表
bool isEmpty(); //在表尾添加一个元素value,表的长度增1
bool insert(const int p, const T value); //在位置p上插入一个元素value,表的长度增1
bool delete1(const int p); //删除位置p上的元素,表的长度减 1
bool getPos(int &p, const T value); //查找值为value的元素并返回其位置
bool getValue(const int p, T& value); //把位置p的元素值返回到变量value中
bool setValue(const int p, const T value); //用value修改位置p的元素值
};
//定义结点类
template <class T> class Link{
public:
T data;
Link<T> * next;
};
//定义单链表类lnkList
template <class T>
class lnkList : public List<T>{
private:
Link<T> *head, *tail; //单链表的头、尾指针
Link<T> *setPos(const int p){ //返回第p个元素的指针值
int count=0;
if(p == -1)
{return head;} // i为-1则定位到头结点
else{
Link<T> *c=head->next; //c指向第一个结点
while(c != NULL && count<p)
{
c=c->next;
count++;
}
return c;}
}
public:
lnkList(){ //构造函数
head=tail=new Link<T>; //创建头结点,head和tail指向该头结点
head->next=NULL; //头结点的指针域为空
}
~lnkList(){ //析构函数
Link<T> * tmp;
while(head!=NULL){
tmp=head; //tmp指向当前结点
head=head->next; //head指向下一结点
delete tmp; //删除当前结点
}
}
bool creat()
{
if(head==NULL)
{
head=tail=new Link<T>;
head->next=NULL;
return true;
}
else
{
cout<<"表已存在,创建失败!"<<endl;
return false;
}
}
bool destroy()
{
if(head==NULL)
{
cout<<"表已不存在!"<<endl;
return false;
}
else
{
Link<T> * tmp;
while(head!=NULL)
{
tmp=head;
head=head->next;
delete tmp;
}
return true;
}
}
bool isEmpty(){ //判断链表是否为空
if(head->next==NULL)
{ return true;}
else
{ return false;}
}
void clear()
{
if(head->next==NULL)
{ cout<<"表已空,清除失败!"<<endl;}
else
{
Link<T> * tmp;
while(head!=NULL){
tmp=head; //tmp指向当前结点
head=head->next; //head指向下一结点
delete tmp; //删除当前结点
}
cout<<"清除成功!"<<endl;
}
}
bool delete1(const int i)
{
Link<T> *p,*q;
p=setPos(i-1);
if((p==NULL)||p==tail)
{
cout<<"非法删除点"<<endl;
return false;
}
q=p->next;
if(q==tail)
{
tail=p;
p->next=NULL;
delete q;
}
else if(q!=NULL)
{
p->next=q->next;
delete q;
}
return true;
}
int length(){
int count=0;
Link<T> *q;
q=head->next; //q指向第1结点
while(q!=NULL) {
count++;
q=q->next;
}
return count;
}
bool display()
{
Link<T> *p;
p=head->next;
if(p==NULL)
{
cout<<"表空!"<<endl;
return false;
}
else{
while(p!=NULL)
{
cout<<p->data<<" "<<endl;
p=p->next;
}
return true;
}
}
bool append(const T value){ //在表尾添加一个元素value,表的长度增1
Link<T> *q; //定义指针变量q
q = new Link<T>; //q指向新结点
q->data=value;
q->next=NULL;
tail->next=q; //将新结点链接在现在的尾结点之后
tail=q; //尾指针指向新结点
return true;
}
bool insert(const int p,const T value){ //在位置p上插入一个元素value,表的长度增1
Link<T> *b,*n;
if( (b=setPos(p-1)) == NULL){
cout << "不能往头结点前添加元素" << endl;
return false;
}
n = new Link<T>;
b->next = n;
n->data=value;
if(b==tail)
{ tail=n;}
return true;
}
bool getValue(const int p,T& value){ //返回位置p的value
Link<T> *m;
int count=0;
if(head->next==NULL)
{
cout<<"表空,查找失败!"<<endl;
return false;
}
m=head->next;
while(count<p)
{
m=m->next;
count++;
}
value=m->data;
return true;
}
bool getPos(int &p,const T value){ //查找值为value的元素,返回第一次出现的位置
Link<T> *m;
if(head->next==NULL)
{
cout<<"表空,无法定位!"<<endl;
return false;
}
m=head->next;
p=-1;
while(m!=NULL)
{
if(m->data==value)
{
p=p+1;
break;
}
m=m->next;
}
return true;
}
bool setValue(const int p, T& value)
{
Link<T> *m;
int count=0;
if(head->next==NULL)
{
cout<<"修改失败!"<<endl;
return false;
}
m=head->next;
while(count<p)
{
m=m->next;
count++;
}
m->data = value;
return true;
}
};
void main()
{
lnkList<char> lL;
bool ok;
int choice;
char value;
int p;
do {
cout<<"单链表程序,请选择(0退出,1清除,2显示,3表长,4插入,5追加,6删除,7查找,8修改,9定位,10创建,11销毁):";
cin>>choice;
switch (choice) {
case 0:
cout<<"再见!\n";
break;
case 1:
lL.clear();
break;
case 2:
ok=lL.display();
if(ok==false) cout<<"显示操作失败!"<<endl;
else cout<<"显示操作成功"<<endl;
break;
case 3:
cout<<"表长为"<<lL.length()<<endl;
break;
case 4:
cout<<"请输入位置:";cin>>p;
cout<<"请输入结点的值:";cin>>value;
ok=lL.insert(p,value);
if(ok==true) cout<<"插入成功!"<<endl;
else cout<<"插入失败!"<<endl;
break;
case 5:
cout<<"请输入结点的值:";
cin>>value;
ok=lL.append(value);
if(ok==true) cout<<"追加操作成功!"<<endl;
break;
case 6:
cout<<"请输入位置:";cin>>p;
ok=lL.delete1(p);
if(ok==true) cout<<"删除成功!"<<endl;
else cout<<"删除失败!"<<endl;
break;
case 7:
cout<<"请输入位置:"<<endl;cin>>p;
ok=lL.getValue(p,value);
if(ok==true) cout<<value<<endl;
else cout<<"查找失败!"<<endl;
break;
case 8:
cout<<"请输入位置:";cin>>p;
cout<<"请输入修改后的值:";cin>>value;
ok=lL.setValue(p,value);
if(ok==true) cout<<"修改成功"<<endl;
else cout<<"修改失败"<<endl;
break;
case 9:
cout<<"请输入需定位的值:"<<endl;
cin>>value;
ok=lL.getPos(p,value);
if(ok==true) cout<<p<<endl;
else cout<<"定位失败!"<<endl;
break;
case 10:
ok=lL.creat();
if(ok==true) cout<<"创建成功!"<<endl;
else cout<<"创建失败!"<<endl;
break;
case 11:
ok=lL.destroy();
if(ok==true) cout<<"销毁成功!"<<endl;
else cout<<"销毁失败!"<<endl;
break;
default: printf("选择错误!\n");
}
} while (choice != 0);
}
怎么回事呢?能否具体帮我指出,谢谢