当前位置:文档之家› 数据结构实验指导书源代码

数据结构实验指导书源代码

实验一线性表的链式存储结构一、实验目的:1.掌握线性表的链式存储结构。

2.熟练地利用链式存储结构实现线性表的基本操作。

3.能熟练地掌握链式存储结构中算法的实现。

二、实验内容:1.用头插法或尾插法建立带头结点的单链表。

2.实现单链表上的插入、删除、查找、修改、计数、输出等基本操作。

三、实验要求:1. 根据实验内容编写程序,上机调试、得出正确的运行程序。

2. 写出实验报告(包括源程序和运行结果)。

四、实验学时:2学时五、实验步骤:1.进入编程环境,建立一新文件;2. 参考以下相关内容,编写程序,观察并分析输出结果。

①定义单链表的数据类型,然后将头插法和尾插法、插入、删除、查找、修改、计数、输出等基本操作都定义成子函数的形式,最后在主函数中调用它,并将每一种操作前后的结果输出,以查看每一种操作的效果。

②部分参考程序//单链表的建立(头插法),插入,删除,查找、修改、计数、输出#include<iostream.h>#define elemtype intstruct link{ elemtype data;//元素类型link *next;//指针类型,存放下一个元素地址};//头插法建立带头结点的单链表link *hcreat(){ link s,p;elemtype i;cout<<”输入多个结点数值(用空格分隔),为0时算法结束”;cin>>i;p=new link;p->next=NULL;while(i) //当输入的数据不为0时,循环建单链表{s=new link;s->data=i;s->next=p->next;p->next=s;cin>>i;}return p;}//输出单链表void print(1ink *head){1ink *p;p=head->next;while(p->next!=NULL){cout<<p->data<<”->”;//输出表中非最后一个元素p=p->next;}cout<<p->data;//输出表中最后一个元素cout<<endl;}∥在单链表head中查找值为x的结点Link *Locate(1ink *head,elemtype x){Link *p;p=head->next;while((p!=NULL)&&(p->data!=x))p=p->next;return p;}//在head为头指针的单链表中,删除值为x的结点void deletel(1ink *head,elemtype x){1ink *p,*q;q=head;p=head->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;}If(p==NULL) cout<<“要删除的结点不存在”;elseq->next=p ->next;}}//在头指针head所指的单链表中,在值为x的结点之后插入值为y的结点void insert(1ink *head,elemtype x,elemtype y){link *p,*s;s=new link;s->data=y;if(head->next==NULL) //链表为空{head->next=s;s->next=NULL:}p=Locate(head,x);//调用查找算法‘if(p==NULL)cout<<”插入位置非法”:else(s->next=p->next;p->next=s;}}//将单链表p中所有值为x的元素修改成yvoid change(1ink *p,elemtype x,elemtype y){link *q;q=p->next;while(q!=NULL){ if(q->data==x) q->data=y;q=q->next;}}void count(1ink *h) //统计单链表中结点个数{1ink *p;int n=0;p=h->next;while(p!=NULL){n++;p=p->next;}return n;}void main()elemtype x,y;link *p,*q;p=hcreat();//头插法建立链表print(p);//输出刚建立的单链表cout<<”请输入要删除的元素”;cin>>y;deletel(p,y);print(p);//输出删除后的结果cout<<”请输入插入位置的元素值(将待插元素插入到它的后面)”;cin>>x;cout<<”请输入待插元素值”;cin>>y;insert(p,x,y);print(p);//输出插入后的结果cout<<”请输入要修改前、后的元素值”;cin>>x>>y;change(p,x,y);print(p);cout<<”请输入要查找的元素值”;cin>>x;q=Locate(p,x);if(q==NULL)cout<<x<<”不在表中,找不到!”<<endl;else cout<<x<<”在表中,已找到!”<<endl;n=count(p);cout<<”链表中结点个数为:”<<n<<endl:}//单链表的建立(尾插法)、插入、删除、查找、修改、计数、输出#include<iostream.h>#define elemtype intstruct link{ elemtype data;//元素类型link *next;//指针类型,存放下-个元素地址};//尾插法建立带头结点的单链表link *rcreat(){link *s,*p,*r;elemtype i;cout<<”输入多个结点数值(用空格分隔),为0时算法结束”;p=r=new link;p->next=NULL;while(i){s=new link;s->data=i;r->next=s;r=s;cin>>i;}r->next=NULL;return p;}//输出单链表void print(1ink *head){link *p;p=head->next;while(p->next!=NULL){cout<<p->data<<"->”; //输出表中非最后一个元素p=p->next;)cout<<p->data;//输出表中最后一个元素cout<<endl;}link *Locate(1ink *head,int x) ∥在单链表中查找第x个结点{link *p;p=head;int j=0;while((p!=NULL)&&(j<x)){p=p->next; j++;}return p;}void delete I(1ink *head,elemtype x)//在head为头指针的单链表中,删除值为x的结点{link *p, *q;q=head;p=head->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;)if(p==NULL)cout<<”要删除的结点不存在“;else{q->next=p->next;delete(p);} }void insert(1ink *head,int x,elemtype y)//在头指针head所指单链表中,在第x个结点之后插入值为y的结点{link *p,*s;s=new link;s->data=y;if(head->next==NULL)//链表为空{head->next=s;s->next=NULL:}p=Locate(head,x);//调用查找算法if(p==NULL)cout<<”插入位置非法”;else{s->next=p->next;p->next=s;}}void change(1ink *p,elemtype x,elemtype y){∥将单链表P中所有值为x的元素改成值为ylink *q;q=p->next;while(q!=NULL){if(q->data==x)q->data=y;q=q->next;}}void count(1ink *h) //统计单链表中结点个数(1ink *p;int n=0;p=h->next;while(p!=NULL){n++;p=p->next;}retum n;}void main(){ int n;link p,q;p=rcreat();//尾插法建立链表print(p);//输出刚建立的单链表cout<<”请输入要删除的元素”;cin>>y;deletel(p,y);print(p);//输出删除后的结果cout<<”请输入插入位置”;cin>>x;cout<<”请输入待插元素值”;cin>>y;insert(p,x,y);print(p);//输出插入后的结果cout<<”请输入修改前、后的元素值”;cin>>x>>y;change(p,x,y);print(p);cout<<“请输入要查找的元素值”;cin>>x;q=Locate(p ,x);if(q==NULL)cout<<x<<”不在表中,找不到!”<<endl;else cout<<x<<”在表中,已找到!”<<endl;n=count(p);cout<<”链表中结点个数为:”<<n<endl;}六、选作实验试设计一元多项式相加(链式存储)的加法运算。

A(X)=7+3X+9X8+5X9B(X)=8X+22X7-9X81.建立一元多项式;2.输出相应的一元多项式;3.相加操作的实现。

相关主题