《数据结构》实验二:线性表的实验
《数据结构》实验二:?????线性表实验 一..实验目的 ???? 巩固线性表的数据结构,学会线性表的应用。 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题可以作为选做题。 四.参考资料 ??? 实验教材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; }运行结果截图:
头文件代码: #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; } 源文件中的main函数:
#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; }运行结果截图:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |