《数据结构》实验二：线性表实验
1.建立一个N个学生成绩的顺序表，对表进行插入、删除、查找等操作。分别输出结果。
要求如下：
1）用顺序表来实现。
2）用单链表来实现。
1）顺序表
N-S图（只是部分操作的N-S图）：
//linklist.h
#ifndef LINK_LIST_H
#define LINK_LIST_H
#include <iostream>
using namespace std;
const int MaxSize=20;
template <class T>
class SeqList
{
public:
SeqList(){length=0;}
SeqList(T a[],int n);
int Length(){return length;}
T Get(int i);
int Locate(T x);
void Insert(T x,int i);
T Delete(int i);
void Print();
private:
T data[MaxSize];
int length;
};
#endif
//linklist.cpp
#include "linklist.h"
template <class T>
void SeqList<T>::Print()
{
for(int i=0;i<length;i++)
cout<<data[i]<<" ";
cout<<endl;
}
template <class T>
SeqList<T>::SeqList(T a[],int n)
{
if(n>MaxSize) throw "参数非法";
for(int i=0;i<n;i++)
data[i]=a[i];
length=n;
}
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>::Insert(T x,int i)
{
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)
{
int x=data[i-1];
if(length==0) throw "下溢";
if(i<1||i>length) throw "位置";
for(int j=i;j<length;j++)
data[j-1]=data[j];
length--;
return x;
}
//main.cpp
#include "linklist.cpp"
void main()
{
int m,grade;
float a[10]={96,95,94,97,98,79,68,88,99,89};
SeqList<float> seqlist(a,10);
cout<<"学生成绩表如下：\n";
seqlist.Print();
cout<<"总共有"<<seqlist.Length()<<"个学生\n";
try
{
cout<<"你想获取第几个学生的成绩?\n请输入数字1到10：";
cin>>m;
cout<<seqlist.Get(m)<<endl;
}
catch(char*)
{
cout<<"获取有误！"<<endl;
}
cout<<"你想查询怎样的成绩在成绩表中的序号?(输出0表示该成绩不存在)\n请输入具体的成绩:";
cin>>m;
cout<<seqlist.Locate(m)<<endl;
try
{
cout<<"你想在成绩表中序号为几的位置上插入怎样的成绩？\n分别输入序号和成绩：";
cin>>m>>grade;
seqlist.Insert(grade,m);
cout<<"插入后的成绩表如下：\n";
seqlist.Print();
cout<<"此时成绩表中学生个数为："<<seqlist.Length()<<endl;
}
catch(char*)
{
cout<<"插入有误！"<<endl;
}
try
{
cout<<"你想删除成绩表中第几个学生的成绩\n请输入序号(1到11)：";
cin>>m;
seqlist.Delete(m);
cout<<"删除后的成绩表如下\n";
seqlist.Print();
cout<<"此时成绩表中学生个数为："<<seqlist.Length()<<endl;
}
catch(char*)
{
cout<<"删除有误！"<<endl;
}
}
程序结果：
2）单链表
N-S图（只是部分操作的N-S图）：
程序代码：
//1004.cpp
#include "LinkList.cpp"
void main()
{
int grade[]={92,91,93,97};
LinkList<int> linklist(grade,7);
cout<<"每个学生的成绩分别为：";
linklist.Print();
cout<<"学生个数："<<linklist.length()<<"个"<<endl;
cout<<"成绩表中94分位于第"<<linklist.Locate(94)<<"个位置上"<<endl;
try
{
cout<<"成绩表中第三个分数为：";
cout<<linklist.Get(3)<<endl;
cout<<"在成绩表中的第三个位置插入成绩92"<<endl;
cout<<"插入前：";
linklist.Print();
cout<<"插入后：";
linklist.Insert(3,92);
linklist.Print();
cout<<"把第五个成绩删除"<<endl;
cout<<"删除前：";
linklist.Print();
cout<<"删除的成绩为："<<linklist.Delete(5)<<endl;
cout<<"删除后：";
linklist.Print();
}
catch(double)
{
cout<<"获取的位置不存在！"<<endl;
exit(1);
}
catch(char*)
{
cout<<"删除的位置不存在！"<<endl;
exit(1);
}
catch(int)
{
cout<<"插入位置不存在！"<<endl;
exit(1);
}
}
//LinkList.cpp
#include "LinkList.h"
#include<stdlib.h>
template <class T>
LinkList<T>::LinkList()
{
first=new Node<T>;
first->next=NULL;
}
template <class T>
LinkList<T>::LinkList(T a[],int n)
{
first=new Node<T>;
Node<T>*r,*s;
r=first;
for(int i=0;i<n;i++)
{
s=new Node<T>;
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}
template <class T>
LinkList<T>::~LinkList()
{
while(first!=NULL)
{
Node<T>*q;
q=first;
first=first->next;
delete q;
}
}
template <class T>
int LinkList<T>::length()
{
Node<T>*p;
p=first->next;
int count=0;
while(p!=NULL)
{
p=p->next;
count++;
}
return count;
}
template <class T>
T LinkList<T>::Get(int i)
{
Node<T>*p=first->next;
int count=1;
while(p!=NULL&&count<i)
{
p=p->next;
count++;
}
if(p==NULL) throw 1.2;
return p->data;
}
template <class T>
int LinkList<T>::Locate(T x)
{
Node<T>*p=first->next;
int count=1;
while(p!=NULL)
{
if(p->data==x)return count;
p=p->next;
count++;
}
return 0;
}
template <class T>
void LinkList<T>::Insert(int i,T x)
{
int count=0;
Node<T>*p=first;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL) throw 1;
else
{
Node<T>*s=new Node<T>;
s->data=x;
s->next=p->next;
p->next=s;
}
}
template<class T>
T LinkList<T>::Delete(int i)
{
T x;
Node<T>*p=first,*q;
int count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL||p->next==NULL) throw "位置";
q=p->next;
x=q->data;
p->next=q->next;
delete q;
return x;
}
template <class T>
void LinkList<T>::Print()
{
Node<T>*p=first->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
//LinkList.h
#ifndef LINKLIST_H
#define LINKLIST_H
#include <iostream>
using namespace std;
template <class T>
class Node
{
public:
T data;
Node<T>*next;
};
template <class T>
class LinkList
{
public:
LinkList();
LinkList(T a[],int n);
~LinkList();
int length();
T Get(int i);
int Locate(T x);
void Insert(int i,T x);
T Delete(int i);
void Print();
private:
Node<T>*first;
};
#endif
程序结果：
