单链表.cpp

用vc++编译的数据结构单链表源代码 供作数据结构实验用

#include "iomanip.h"
#include "stdlib.h"
#include "string.h"
struct student
{
char name[10];
short grade;
};
typedef student elemtype;
struct Lnode{
elemtype data;
Lnode *next;
};
bool operator==(const elemtype&r1,const elemtype &r2)
{return strcmp(r1.name,r2.name)==0;
}
bool operator<(const elemtype & r1,const elemtype & r2)
{return strcmp(r1.name,r2.name)==-1;
}
ostream & operator<<(ostream & ostr,const elemtype &r)
{ostr.setf(ios::left);
ostr<<setw(10)<<r.name<<setw(5)<<r.grade<<"   ";
return ostr;
}
istream & operator>>(istream &istr,elemtype &r)
{istr>>r.name>>r.grade;
return istr;
}
void initlist(Lnode *&HL)
{HL=NULL;
}
void clearlist(Lnode *&HL)
{Lnode *cp,*np;
cp=HL;
while(cp!=NULL)
{np=cp->next;
delete cp;
cp=np;
}
HL=NULL;
}
int listsize(Lnode *HL)
{Lnode *p=HL;
int i=0;
while(p!=NULL){
i++;
p=p->next;
}
return i;
}
bool listempty(Lnode *HL)
{return (HL==NULL);
}
elemtype getelem(Lnode *HL,int pos)
{
if(pos<1){
cerr<<"pos is out range!"<<endl;
exit(1);
}
Lnode *p=HL;
int i=0;
while(p!=NULL){
i++;
if(i==pos)break;
p=p->next;
}
if(p!=NULL)
return p->data;
else{
cerr<<"pos is out range!"<<endl;
exit(1);
}
}
void traverselist(Lnode *HL)
{Lnode *p=HL;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
bool findlist(Lnode *HL,elemtype &item)
{Lnode *p=HL;
while(p!=NULL)
if(p->data==item)
{
item=p->data;
return true;
}
else
p=p->next;
return false;
}
bool updatelist(Lnode *HL,const elemtype &item)
{Lnode *p=HL;
while(p!=NULL)
if(p->data==item)
break;
else
p=p->next;
if(p==NULL)
return false;
else{
p->data=item;
return true;
}
}
void insertlist(Lnode *&HL,const elemtype &item,int mark)
{Lnode *newptr;
newptr=new Lnode;
newptr->data=item;
if(mark>0){
newptr->next=HL;HL=newptr;
}
else if(mark<0){
if(HL==NULL){newptr->next=NULL;HL=newptr;}
else {
Lnode *p=HL;
while(p->next!=NULL)
p=p->next;
p->next=newptr;newptr->next=NULL;
}
}
else
{
Lnode *cp;
Lnode *ap;
ap=NULL;cp=HL;
while(cp!=NULL){
if(item<cp->data)break;
else{ap=cp;cp=cp->next;}
}
if(ap==NULL){newptr->next=HL;HL=newptr;}
else{newptr->next=cp;ap->next=newptr;}
}
}
bool deletelist(Lnode *&HL,elemtype &item,int mark)
{
if(HL==NULL) return false;
if(mark>0){
Lnode *p=HL;
item=HL->data;
HL=HL->next;
delete p;
return true;
}
else if(mark<0){
Lnode *cp=HL,*ap=NULL;
while(cp->next!=NULL){
ap=cp;cp=cp->next;
}
if(ap==NULL)HL=NULL;
else ap->next=cp->next;
item=cp->data;
delete cp;
return true;
}
else {
Lnode *cp=HL,*ap=NULL;
while(cp!=NULL)
if(cp->data==item) break;
else {ap=cp;cp=cp->next;}
if(cp==NULL) return false;
else {
if(ap==NULL) HL=HL->next;
else ap->next=cp->next;
item=cp->data;
delete cp;
return true;
}}}
void orderoutputlist(Lnode *HL,int mark)
{if(HL==NULL){cout<<"链表为空!"<<endl;return;}
Lnode *head=new Lnode; Lnode *cp=head,*ap=NULL;
head->data=HL->data;head->next=NULL;
for(Lnode *p=HL->next;p;p=p->next){
Lnode *q=new Lnode;
q->data=p->data;
while(cp)
{if(mark==1){
if(q->data<cp->data)break;
else {ap=cp;cp=cp->next;}
}
else{
if(cp->data<q->data)break;
else{ap=cp;cp=cp->next;}
}}
if(ap==NULL){q->next=head;head=q;}
else{
q->next=cp;ap->next=q;
}}
traverselist(head);
clearlist(head);
}
void main()
{Lnode *a;
initlist(a);
int i;
elemtype x;
cout<<"从键盘输入5个学生记录:";
for(i=0;i<5;i++)
{
cin>>x;
insertlist(a,x,-1);
}
cout<<"从键盘输入2个学生记录：";
cin>>x;insertlist(a,x,1);
cin>>x;insertlist(a,x,1);
traverselist(a);
orderoutputlist(a,1);
orderoutputlist(a,0);
cout<<"从键盘上输入一个待查学生的姓名:";
cin>>x.name;
if(findlist(a,x))cout<<x<<"查找成功!"<<endl;
else cout<<"查找失败"<<endl;
cout<<"从键盘上输入一个待更新的学生的记录："<<endl;
cin>>x;
if(updatelist(a,x)) cout<<"更新成功！"<<endl;
else cout<<"更新失败："<<endl;
traverselist(a);
if(deletelist(a,x,1))cout<<"delete success!"<<endl;
else cout<<"delete fail!"<<endl;
if(deletelist(a,x,-1))cout<<"delete success!"<<endl;
else cout<<"delete fail!"<<endl;
cout<<"从键盘上输入一个待删除学生的姓名：";
cin>>x.name;
if(deletelist(a,x,0)) cout<<"delete success!"<<endl;
else cout<<"delete fail!"<<endl;
traverselist(a);
}