一个小小的数据结构程序
源代码在线查看： 单链表的运算.cpp
//-------------------实验三、单链表的运算-------------------------
#include
#include
using namespace std;
//----------------------------------------------------------------
class node{ //结点类定义
public:
string nodevalue;
node *next;
node():next(NULL){} //构造函数
node(const string item,node *nextnode=NULL):nodevalue(item),next(nextnode){}
};//---------------------------------------------------------------
class L{ //单链表类声明
node *head; //结点成员
static int length;
public:
L(); //构造函数
bool isListEmpty(); //判空成员函数
int ListLength(); //求表长成员函数
void DispList(); //打印单链表函数
node* GetElem(int pos); //根据位置找结点
int LocateElem(string elem); //查找元素在表中第一次出现的位置
void ListInsert(string &elem,int pos);//在表中插入一个结点
int ListDelete(int pos); //删除一个结点
void ListDelete(string &elm); //重载删除函数
~L(){} //析构函数
};//---------------------------------------------------------------
int L::length=0; //初始化表长
L::L(){ //单链表的构造函数定义
node *p,*curr;
string tmp;
cout cin>>tmp;
if(tmp=="0"){
length=0;
head=NULL;
}
else{
head=new node(tmp);
length=1;
p=head;
while(1){
cin>>tmp;
if(tmp=="0"){
p->next=NULL;
break;
}
else{
curr=new node(tmp);
p->next=curr;
p=curr;
length++;
}
}
p->next=NULL;
}
}//---------------------------------------------------------------
bool L::isListEmpty(){ //单链表判空函数声明
if(length==0)
return 1;
else
return 0;
}//---------------------------------------------------------------
int L::ListLength(){ //求表长
return length;
}//---------------------------------------------------------------
void L::DispList(){ //显示单链表
node *curr;
curr=head;
cout if(this->isListEmpty())
cout else{
for(int i=1;i cout curr=curr->next;
}
cout }
}//---------------------------------------------------------------
node* L::GetElem(int pos){ //根据位置查找，返回结点指针
node *curr;
curr=head;
if(pos>length)
return NULL;
else{
for(int i=1;i curr=curr->next;
return curr;
}
}//---------------------------------------------------------------
int L::LocateElem(string elem){ //根据元素查找位置，返回元素的序号
node *curr;int n=1;
curr=head;
while(curr!=NULL&&curr->nodevalue!=elem){
curr=curr->next;
n++;
}
if(curr==NULL)
return(0);
else
return(n);
}//---------------------------------------------------------------
void L::ListInsert(string &elem,int pos){ //将elem插入到表的第pos处
node *curr,*s;
int j=1;
if(pos==1){ //插入到头结点
curr=new node(elem,head);
head=curr;
length++;
}
else if(pos-1==length){ //插入到尾结点
curr=this->GetElem(pos-1);
curr->next=new node(elem);
length++;
}
else if(pos>1&&pos curr=head;
while(j curr=curr->next;
j++;
}
s=new node(elem);
s->next=curr->next;
curr->next=s;
length++;
}
else
cout
}//---------------------------------------------------------------
int L::ListDelete(int pos){ //删除第pos个元素，根据返回值判断是否成功
node *curr,*s;
int j=0;
curr=this->GetElem(pos-1);
if((curr->next==NULL)||(j>pos-1))
return 0;
if(pos==1&&(length>1)){ //删除头结点
s=head;
head=head->next;
free(s);
length--;
return 1;
}
else if(pos==length&&(length>1)){ //删除尾结点
s=curr->next;
curr->next=NULL;
free(s);
length--;
return 1;
}
else if(length==1){
free(head);
length=0;
}
else{ //删除普通结点
s=curr->next;
curr->next=s->next;
free(s);
length--;
return 1;
}
}//---------------------------------------------------------------
void L::ListDelete(string &elm){ //删除元素elm
int j=1;
j=this->LocateElem(elm);
if(j!=0){
cout this->ListDelete(j);
}
}//---------------------------------------------------------------
int menu1(){ //根菜单
int i=0;
cout cout cout cout cin>>i;
cout if((i5))
menu1();
else
return(i);
};//---------------------------------------------------------------
int menu2(){ //删除操作选择菜单
int j;
cout cout cout cout cin>>j;
cout return j;
}//---------------------------------------------------------------
int menu3(){ //查找操作选择菜单
int k;
cout cout cout cout cin>>k;
cout return k;
}//---------------------------------------------------------------
void main(){//----------------------主函数------------------------
int i;string elem;
L list;
list.DispList();
loop:
i=menu1();
if(i==1){ //插入
int pos;
cout cin>>elem>>pos;
list.ListInsert(elem,pos);
list.DispList();
goto loop;
}
else if(i==2){ //删除
int returnvalue;
returnvalue=menu2();
if(returnvalue==1){ //删除指定位置的元素
int pos;
cout cin>>pos;
if(pos>list.ListLength())
cout else{
cout list.ListDelete(pos);
cout list.DispList();
}
goto loop;
}
else if(returnvalue==2){ //删除指定元素
string elm;
cout cin>>elm;
cout list.ListDelete(elm);
cout list.DispList();
goto loop;
}
else if(returnvalue==3)
goto loop;
}
else if(i==3){ //查找
int returnvalue;
returnvalue=menu3();
if(returnvalue==1){ //查找指定位置的元素
int pos;
cout cin>>pos;
if(list.GetElem(pos)==NULL)
cout else
cout goto loop;
}
else if(returnvalue==2){ //查找指定元素
string elm;
cout cin>>elm;
if(list.LocateElem(elm)==0)
cout else{
cout }
goto loop;
}
else if(returnvalue==3) //返回根菜单
goto loop;
}
else if(i==4){ //打印单链表
list.DispList();
goto loop;
}
else if(i==5){ //退出程序
exit(0);
getchar();
}
else
goto loop;
}//---------------------------------------------------------------
