《数据结构》实验二:线性表实验(1)
一..实验目的 要求如下: 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题可以作为选做题。 四.参考资料 实验教材P170到182. 五.实验报告 1.在博客中先写上实习目的和内容,画出主要操作运算算法图,然后分别上传程序代码。插入调试关键结果截图。 2.写一个博文,比较总结线性表的两种主要存储结果:顺序表和单链表。 实验2.1.1用顺序表实现建立一个N个学生成绩的顺序表,对表进行插入、删除、查找等操作 头文件代码: const int Maxsize=100; class ScoreTable{ public: ScoreTable(){length=0;} ScoreTable(int a[],int n); ~ScoreTable(){} void Insert(int i,int x); int Delete(int i); int Locate(int x); void PrintList(); private: int data[Maxsize];//存放数据元素的的数组 int length; };
#include<iostream> #include "seqtable.h" using namespace std; ScoreTable::ScoreTable(int a[],int n){ if(n>Maxsize) throw "参数非法"; for(int i=0;i<n;i++) data[i]=a[i]; length=n; } void ScoreTable::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 ScoreTable::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 ScoreTable::Locate(int x){ for(int i=0;i<length;i++) if(data[i]==x) return i+1; return 0; } void ScoreTable::PrintList(){ for(int i=0;i<length;i++) cout<<data[i]<<" "; cout<<endl; } int main(){ int a[5]={90,78,86,80,66}; ScoreTable st(a,5); cout<<"5个学生的成绩分别为:"<<endl; st.PrintList(); try{ st.Insert(2,99); } catch(char *s){ cout<<s<<endl; } cout<<"插入第六个同学的成绩后所有人的成绩:"<<endl; st.PrintList(); cout<<"分数为99的元素位置为:"; cout<<st.Locate(99)<<endl; cout<<"删除第一个同学的分数,删除前数据为:"<<endl; st.PrintList(); try{ st.Delete(1); } catch(char *s){ cout<<s<<endl; } cout<<"删除后所有人的成绩为:"<<endl; st.PrintList(); return 0; }
结果: 实验2.1.2单链表实现建立一个N个学生成绩的顺序表,对表进行插入、删除、查找等操作: 头文件代码: #ifndef LINKLIST_H_INCLUDED #define LINKLIST_H_INCLUDED template<class DataType> struct Node{ DataType data; Node<DataType> *next; }; template<class DataType> class LinkList{ public: LinkList(); LinkList(DataType a[],int n); ~LinkList(); int Locate(DataType x); void Insert(int i,DataType x); DataType Delete(int i); void PrintList(); private: Node<DataType> *first; //头指针 }; #endif // LINKLIST_H_INCLUDED
#include<iostream> #include"LinkList.h" using namespace std; template<class DataType> LinkList<DataType>::LinkList(){ first=new Node<DataType>; first->next=NULL; } template<class DataType> LinkList<DataType>::LinkList(DataType a[],int n){ Node<DataType> *r,*s; first=new Node<DataType>; r=first; for(int i=0;i<n;i++){ s=new Node<DataType>; s->data=a[i]; r->next=s; r=s; } r->next=NULL; } template<class DataType> LinkList<DataType>::~LinkList(){ Node<DataType> *q=NULL; while(first!=NULL){ q=first; first=first->next; delete q; } } template<class DataType> void LinkList<DataType>::Insert(int i,DataType x){ Node<DataType> *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<DataType>; s->data=x; s->next=p->next;p->next=s; } } template<class DataType> DataType LinkList<DataType>::Delete(int i){ Node<DataType> *p=first,*q=NULL; DataType 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 DataType> int LinkList<DataType>::Locate(DataType x){ Node<DataType> *p=first->next; int count=1; while(p!=NULL){ if(p->data==x) return count; p=p->next; count++; } return 0; } template<class DataType> void LinkList<DataType>::PrintList(){ Node<DataType> *p=first->next; while(p!=NULL){ cout<<p->data<<" "; p=p->next; } cout<<endl; }
#include <iostream> #include"LinkList_ScoTable.cpp" using namespace std; int main() { int r[5]={80,99,92,85}; LinkList<int>L(r,5); cout<<"5个学生的成绩分别为:"<<endl; L.PrintList(); try{ L.Insert(2,100); }catch(char *s){ cout<<s<<endl; } cout<<"插入第六个同学的成绩后成绩列表为:"<<endl; L.PrintList(); cout<<"分数为85的同学是第几位:"<<endl; cout<<L.Locate(85)<<endl; cout<<"删除第一个同学的分数,删除前数据为:"<<endl; L.PrintList(); try{ L.Delete(1); }catch(char *s){ cout<<s<<endl; } cout<<"删除后所有人的成绩为:"<<endl; L.PrintList(); return 0; } 结果: (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- angularjs中的隔离作用域理解以及绑定策略
- Haskell – Alpine Docker镜像内的主机名解析不起作用
- angularjs – 为什么$q.when在使用ngMock时包装第三方承诺时
- angularjs – 使用ng-class与函数调用 – 多次调用
- 在Docker中的链接容器上执行二进制文件
- Angular 2 – 输入掩码:输入框显示格式化值,而模型保留未格
- 业务运维实战:腾讯是怎么优化APP用户体验的?
- AngularJS – ngrepeat中的ngmodel没有更新(‘dotted’ngmo
- Shapeless是否使用反射并且在scala生成代码中使用是否安全?
- 这可能是分析“等级保护”中“安全审计”最细致的一篇文章