《数据结构》实验二：线性表实验

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

#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;
}

#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