一．.实验目的
巩固线性表的数据结构，学会线性表的应用。
1.回顾线性表的逻辑结构，线性表的物理存储结构和常见操作。
2.学习运用线性表的知识来解决实际问题。
3.进一步巩固程序调试方法。
4.进一步巩固模板程序设计。
二、实验内容
建立一个N个学生成绩的顺序表，对表进行插入、删除、查找等操作。分别输出结果。
要求如下：
1）用顺序表来实现。
2）用单链表来实现。
用顺序表储存学生成绩
头文件 SeqList.h
const int MaxSize=30;
template<class T>
class SeqList
{
public:
SeqList(){length=0;}
SeqList(T a[],int n);
~SeqList(){}
int Length(){return length;} //求线性表的长度
T Get(int i); //按位查找，查找第i个元素
int Locate(T x); //按值查找，查找值为x的元素序号
void Insert(int i,T x); //在第i个位置插入值为x的元素
T Delete(int i); //删除第i个元素
void PrintList(); //遍历操作，按序号一次输出元素
private:
T data[MaxSize]; //存放数据元素的数组
int length;
};SeqList.cpp
#include"SeqList.h"
#include<iomanip>
template<class T>
SeqList<T>::SeqList(T a[],int n)
{
if(n>MaxSize)throw"error";
for(int i=0;i<n;i++)
data[i]=a[i];
length=n;
}
template<class T>
void SeqList<T>::Insert(int i,T 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++;
}
template<class T>
T SeqList<T>::Delete(int i) //删除
{
if(length==0)throw"下溢";
if(i<1||i>length)throw"位置";
T x=data[i-1];
for(int j=i;j<length;j++)
data[j-1]=data[j];
length--;
return x;
}
template<class T>
T SeqList<T>::Get(int i) //按位查找
{
if(i<1&&i>length)throw"查找位置非法";
else return data[i-1];
}
template<class T>
int SeqList<T>::Locate(T x) //按值查找
{
for(int i=0;i<length;i++)
if(data[i]==x)return i+1;
return 0;
}
template<class T>
void SeqList<T>::PrintList() //遍历操作
{
for(int i=0;i<length;i++)
cout<<setw(4)<< data[i];
}Main.cpp
#include<iostream>
#include"SeqList.cpp"
using namespace std;
void main()
{
int score[5]={89,92,78,73,95};
SeqList<int>scoreList(score,5);
cout<<"原始数据为:";
scoreList.PrintList();
cout<<endl;
try
{
scoreList.Insert(4,55);
}
catch(char *s)
{
cout<<s<<endl;
}
cout<<"插入后的数据为:";
scoreList.PrintList();
cout<<endl;
cout<<"值为55的元素位置为:";
cout<<scoreList.Locate(55)<<endl;
cout<<"执行删除第二个元素操作，删除前的数据为:";
scoreList.PrintList();
cout<<endl;
try
{
scoreList.Delete(2);
}
catch(char *s)
{
cout<<s<<endl;
}
cout<<"删除后的数据为:";
scoreList.PrintList();
cout<<endl;
}
用单链表储存学生成绩
#include<iostream>
using namespace std;
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;
};
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;
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;
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,*q;
DataType x;
int count=0;
p=first;
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;
}
void main()
{
int score[5]={90,87,77,68,95};
LinkList<int> scoreList(score,5);
cout<<"链表数据为："<<endl;
cout<<"执行插入操作前数据为："<<endl;
scoreList.PrintList( );
try
{
scoreList.Insert(3,87);
}
catch (char *s)
{
cout<<s<<endl;
}
cout<<"执行插入操作后数据为："<<endl;
scoreList.PrintList( );
cout<<"值为87的元素位置为:";
cout<<scoreList.Locate(87)<<endl;
cout<<"执行删除操作前数据为："<<endl;
scoreList.PrintList( );
try
{
scoreList.Delete(4);
}
catch (char *s)
{
cout<<s<<endl;
}
cout<<"执行删除操作后数据为："<<endl;
scoreList.PrintList( );
}
顺序表和单链表的存储结构的比较：
顺序表是在逻辑和物理存储位置上相邻，用数组存储数据，顺序表的空间长度预先分配；
单链表的逻辑次序和物理次序不一定相同，元素之间的逻辑关系用指针表示。单链表的存储空间是动态存储的。
