一.实验目的
巩固线性表的数据结构,学会线性表的应用。
1.回顾线性表的逻辑结构,线性表的物理存储结构和常见操作。
2.学习运用线性表的知识来解决实际问题。
3.进一步巩固程序调试方法。
4.进一步巩固模板程序设计。
二.实验时间
准备时间为第2周到第4周,具体集中实验时间为第4周第2次课。2个学时。
三.实验内容
1.建立一个N个学生成绩的顺序表,对表进行插入、删除、查找等操作。分别输出结果。
要求如下:
1)用顺序表来实现。
2)用单链表来实现。
2.解决约瑟夫问题
设有编号为1,2,3,n的n(n>0)个人围在一起,每人持有一个密码m,从第一个人开始报数,报到m时停止报数,报m的人出圈,再从下一个人开始重新报数,报到m时停止报数,报m的人出圈,……直到的所有人出圈为止。当给定n和m后,输出出圈的次序。
要求如下:自定义数据结构,确定存储方法,并设计算法。在主程序中输入n和m后,输出结果。
3.实现两个集合的相等判定、并、交和差运算。要求:
1)自定义数据结构
2)自先存储结构,并设计算法。在VC中实现。
以上三题,第1题必须完成。第2和第3题可以作为选做题。
三.实验结果
实验2.1.1
#include<iostream.h> const int MaxSize=100; class SeqList { public: SeqList(){length=0;} SeqList(int a[],int n); ~SeqList(){} void Insert(int i,int x); int Delete(int i); int Get(int i); int Locate(int x); void PrintList(); private: int data[MaxSize]; int length; }; SeqList::SeqList(int a[],int n) { if(n>MaxSize) throw"参数非法"; for(int i=0;i<n;i++) data[i]=a[i]; length=n; } void SeqList::Insert(int i,int x) { if(length>=MaxSize) throw"上溢"; if(i<1||i>length+1) throw"位置非法"; for(int j=length;j>=i;j--) data[j]=data[j-1]; data[i-1]=x; length++; } int SeqList::Delete(int i) { if(length==0) throw"下溢"; if(i<1||i>length+1) throw"位置非法"; int x=data[i-1]; for(int j=i;j<length;j++) data[j-1]=data[j]; length--; return x; } int SeqList::Get(int i) { if(i<1 && i>length) throw"查找位置非法"; else return data[i-1]; } int SeqList::Locate(int x) { for(int i=0;i<length;i++) if(data[i]==x) return i+1; return 0; } void SeqList::PrintList() { for(int i=0;i<length;i++) cout<<data[i]<<" "; cout<<endl; } void main() { int score[5],n,m,s; for(int i=0;i<5;i++) { cout<<"请输入第"<<i+1<<"个学生的成绩:"; cin>>score[i]; } SeqList L(score,5); cout<<"执行插入操作前的数据为:"<<endl; L.PrintList(); cout<<"请插入数据:"; cin>>n; cout<<"插入数据的位置为:"; cin>>m; L.Insert(m,n); cout<<"执行插入操作后的数据为:"<<endl; L.PrintList(); cout<<"请输入需要查找数据的位置:"; cin>>m; cout<<L.Get(m)<<endl; cout<<"请输入需要查找的数据值:"; cin>>s; cout<<L.Locate(s)<<endl; cout<<"请输入需要删除的数据的位置:"; cin>>m; L.Delete(m); cout<<"执行删除操作后的数据为:"<<endl; L.PrintList(); }
实验2.1.2
#include<iostream.h> struct Node { int data; Node *next; }; class LinkList { public: LinkList(); LinkList(int a[],int n); ~LinkList(); int Locate(int x); void Insert(int i,int x); int Delete(int i); void PrintList(); private: Node *first; }; LinkList::LinkList() { first=new Node; first->next=NULL; } LinkList::LinkList(int a[],int n) { Node *r,*s; first=new Node; r=first; for(int i=0;i<n;i++) { s=new Node; s->data=a[i]; r->next=s;r=s; } r->next=NULL; } LinkList::~LinkList() { Node *q=NULL; while(first!=NULL) { q=first; first=first->next; delete q; } } void LinkList::Insert(int i,int x) { Node *p=first,*s=NULL; int count=0; while(p!=NULL && count<i-1) { p=p->next; count++; } if(p==NULL) throw"位置"; else { s=new Node;s->data=x; s->next=p->next;p->next=s; } } int LinkList::Delete(int i) { Node *p=first,*q=NULL; int x,count=0; while(p!=NULL && count<i-1) { p=p->next; count++; } if(p==NULL||p->next==NULL) throw"位置"; else { q=p->next;x=q->data; p->next=q->next; delete q; return x; } } int LinkList::Locate(int x) { Node *p=first->next; int count=1; while(p!=NULL) { if(p->data==x) return count; p=p->next; count++; } return 0; } void LinkList::PrintList() { Node *p=first->next; while(p!=NULL) { cout<<p->data<<" "; p=p->next; } cout<<endl; } void main() { int score[5]={98,60,85,77,90}; LinkList L(score,5); cout<<"执行插入操作前的数据为:"<<endl; L.PrintList(); L.Insert(1,100); cout<<"执行插入操作后的数据为:"<<endl; L.PrintList(); cout<<"值为100的元素的位置为:"; cout<<L.Locate(60)<<endl; cout<<"执行删除操作前的数据为:"<<endl; L.PrintList(); L.Delete(6); cout<<"执行删除操作后的数据为:"<<endl; L.PrintList(); }
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|