一..实验目的
巩固线性表的数据结构,学会线性表的应用。
1.回顾线性表的逻辑结构,线性表的物理存储结构和常见操作。
2.学习运用线性表的知识来解决实际问题。
3.进一步巩固程序调试方法。
4.进一步巩固模板程序设计。
二.实验时间
准备时间为第2周到第4周,具体集中实验时间为第4周第2次课。2个学时。
三..实验内容
1.建立一个N个学生成绩的顺序表,对表进行插入、删除、查找等操作。分别输出结果。
要求如下:
1)用顺序表来实现。
#include<iostream> using namespace std; const int Maxsize=100; class score { public: score(){length=0;} score(int a[],int n); ~score(){ } int Locate(int x); void Insert(int i,int x); int Delete(int i); void Printlist(); private: int data[Maxsize]; int length; }; score::score(int a[],int n) { if(n>Maxsize) throw"参数非法"; for(int i=0;i<n;i++) data[i]=a[i]; length=n; } void score::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 score::Delete(int i) { if(length==0) throw"下溢"; if(i<1||i>length) throw"位置非法"; int x=data[i-1]; for(int j=i;j<length;j++) data[j-1]=data[j]; length--; return x; } int score::Locate(int x) { for(int i=0;i<length;i++) if(data[i]==x) return i+1; return 0; } void score::Printlist() { for(int i=0;i<length;i++) cout<<data[i]<<" "; cout<<endl; } void main() { int r[10]={83,85,74,71,67,73,66,84,100,99}; score L(r,10); cout<<"执行插入操作的前的数据为:"<<endl; L.Printlist(); try { L.Insert(4,55); } catch(char *s) { cout<<s<<endl; } int d; cout<<"执行插入操作后的数据为:"<<endl; L.Printlist(); cout<<"请输入所查询的位置"<<endl; cin>>d; cout<<"值为"<<d<<"的元素位置为:"; cout<<L.Locate(d)<<endl; cout<<"执行删除第一个元素操作,删除前数据为:"<<endl; L.Printlist(); try { L.Delete(1); } catch(char *s) { cout<<s<<endl; } cout<<"删除后的数据为:"<<endl; L.Printlist(); }
2)用单链表来实现。
#include<iostream> using namespace std; template<class score> struct Node { score data; Node<score> * next; }; template<class score> class Linklist { public: Linklist(); Linklist(score a[],int n); ~Linklist(); int Locate(score x); void Insert(int i,score x); score Delete(int i); void Printlist(); private: Node<score> * first; }; template<class score> Linklist<score>::Linklist() { first=new Node<score>; first->next=NULL; } template<class score> Linklist<score>::Linklist(score a[],int n) { Node<score> *r,*s; first=new Node<score>; r=first; for(int i=0;i<n;i++) { s=new Node<score>; s->data=a[i]; r->next=s;r=s; } r->next=NULL; } template<class score> Linklist<score>::~Linklist() { Node<score>*q=NULL; while(first!=NULL) { q=first; first=first->next; delete q; } } template<class score> void Linklist<score>::Insert(int i,score x) { Node<score>*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<score>;s->data=x; s->next=p->next;p->next=s; } } template<class score> score Linklist<score>::Delete(int i) { Node<score>*p=first,*q=NULL; score x; int 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; } } template<class score> int Linklist<score>::Locate(score x) { Node<score>*p=first->next; int count=1; while(p!=NULL) { if(p->data==x) return count; p=p->next; count++; } return 0; } template<class score> void Linklist<score>::Printlist() { Node<score>*p=first->next; while(p!=NULL) { cout<<p->data<<" "; p=p->next; } cout<<endl; } void main() { int r[10]={72,49,82,61,83,98,70,84}; Linklist<int>L(r,10); cout<<"执行插入操作前的数据为:"<<endl; L.Printlist(); try { L.Insert(3,89); } catch(char *s) { cout<<s<<endl; } cout<<"执行插入操作后的数据为:"<<endl; L.Printlist(); cout<<"输入要查找的元素"<<endl; int d; cin>>d; cout<<"值为"<<d<<"的元素的位置为:"; cout<<L.Locate(d)<<endl; cout<<"执行删除操作前的数据为:"<<endl; L.Printlist(); try { L.Delete(1); } catch(char *s) { cout<<s<<endl; } cout<<"执行删除操作后的数据为:"<<endl; L.Printlist(); }