实验二 线性表综合实验之《静态链表》

《数据结构》实验二：

线性表综合实验

一．实验目的

  巩固线性表的数据结构的存储方法和相关操作，学会针对具体应用，使用线性表的相关知识来解决具体问题。

二．实验时间

  准备时间为第3周到第4周，具体集中实验时间为第4周第2次课。2个学时。

三.实验内容

1.建立一个由n个学生成绩的顺序表，n的大小由自己确定，每一个学生的成绩信息由自己确定，实现数据的对表进行插入、删除、查找等操作。分别输出结果。

要求如下：

  1）用顺序表来实现。

  2）用单链表来实现。

  3）用双链表实现。

  4）用静态链表实现。

  5）用间接寻址实现。

分开写程序，可以一个方法分别写一博客文章上交作业。

 2.实现两个集合的相等判定、并、交和差运算。要求：

  1）自定义数据结构

  2）自先存储结构，并设计算法。在VC中实现。

以上三题，第1题必须完成。第2和第3题可以作为选做题。

四．实验报告

 1.在博客中先写上实习目的和内容，画出主要操作运算算法图，然后分别上传程序代码。插入调试关键结果截图。

 2.单独写一个博文，比较总结线性表的几种主要存储结构。

用静态链表实现

1、程序代码

#include<iostream>
using namespace std;
const int M=100;
struct SNode
{
	int data;
	int next;
};

class Student
{
	public:
		Student();
		Student(int a[],int n);
		int Get(int i);  //按位查找 
		void Insert(int i,int x);  //插入 
		int Delete(int i);   //删除 
		void PrintList();   //遍历 
	private:
		int first,avail; 
		SNode  SList[M];
};

Student::Student()
{
	first=0;avail=1;
	SList[0].next=-1;   
	for(int i=0;i<M;i++)
	{
		SList[i].next=i+1;
		SList[M-1].next=-1;
	}
}

Student::Student(int a[],int n)
{
	int p;
	if(n>M||a<=0)  throw"错误";
	first=0;avail=1;
	SList[0].next=avail;
	for(int i=0;i<M-1;i++)
	{
		SList[i].next=i+1;
		SList[M-1].next=-1;
	}
	for(int j=0;j<n;j++)
	{
		p=avail;
		SList[p].data=a[j]; 
		avail=SList[avail].next;
	}
	SList[p].next=-1;
}

int Student::Get(int i)  //按位查找 * 
{
	int p;
	int count;
	p=SList[first].next;count=1;
	while(p!=NULL&&count<i)
	{
		p=SList[p].next;
		count++;
	}
	if(p==-1) throw"位置";
	else return SList[p].data;
}

void Student::Insert(int i,int x)  //插入 
{ 
	int p,q,s,count=0;
	p=first;
	while(SList[p].next!=-1&&count<i-1)
	{
		p=SList[p].next;
		count++;
	}
	if(SList[p].next==-1) throw"位置";
	else
	{
	s=avail;
	avail=SList[avail].next;
	SList[s].data=x;
	SList[s].next=SList[p].next;
	SList[p].next=s;
    }
}

int Student::Delete(int i)   //删除 
{ 
    int x;
	int p,q,count=0;
	p=first;
	while(SList[p].next!=-1&&count<i-1)
	{
		p=SList[p].next;
		count++;
	}
	if(SList[p].next==-1) throw"位置";
	else
	{
	q=SList[p].next;
	x=SList[q].data;
	SList[p].next=SList[q].next;
	SList[q].next=avail;
	avail=q;
	return x;
    }
}

void Student::PrintList()
{
	int p;
	int i=0;
	p=SList[first].next;  
	while(p!=-1)
	{
		i=i+1;
		cout<<endl<<"\t\t\t第"<<i<<"个学生成绩"<<SList[p].data<<" ";
		p=SList[p].next;   
	}
	cout<<endl;	
}

int main()
{   
    int x,n,loc,len;
    cout<<"\t\t\t录入学生成绩信息"<<endl; 
    int j,b[M],s;
    cout<<"\t\t\t要录入人数：";
	cin>>n;
	for(j=0;j<n;j++)
	{
	cout<<"\t\t\t第";
	cout<<j+1;
	cout<<"位学生成绩:"; 
    cin>>b[j];
	}  	
    Student List(b,n);		
    while(1)
	{
	cout<<endl<<"\t\t\t\t静态链表"<<endl; 
	cout<<endl<<"\t\t\t学生的成绩信息"<<endl;
	cout<<"                 1.按位查找，取第i位学生成绩"<<endl;
	cout<<"                 2.插入学生信息"<<endl;
	cout<<"                 3.删除学生信息"<<endl;
	cout<<"                 4.输出各学生的成绩信息"<<endl; 
	cout<<"                 0.退出"<<endl;
	cout<<"\t\t\t请选择操作(0-4):";
	cin>>x;
	cout<<endl;
	if(x==0)
	break;
	switch(x)
	   {
		case 1:                                       //按位查找，第i个
			{
				cout<<"\t\t\t输入学生位置:";
				cin>>loc;
				n=List.Get(loc);
				cout<<"\t\t\t该学生的成绩为:"<<n<<endl;
				break; 
			}
		case 2:                                            //插入
			{
				cout<<"\t\t\t输入学生信息插入位置:";
				cin>>loc;
				cout<<"\t\t\t输入学生成绩:";
				cin>>n;
				List.Insert(loc,n);
				cout<<"\t\t\t插入成功!"<<endl;
				break;
			}
		case 3:                                             //删除
			{
				cout<<"\t\t\t输入删除的学生位置:";
				cin>>loc;
				cout<<"\t\t\t已删除的学生成绩:"<<List.Delete(loc)<<endl;
				cout<<"\t\t\t删除成功！"<<endl;
				break;
			}
		case 4:                                             //输出 
			{   
			    cout<<"\t\t\t输出各学生的成绩:"<<endl;
				List.PrintList();
				break;
			}
		default:
			{
				cout<<"\t\t\t请输入数字(0-4)！"<<endl;
			}
	   } 	
    }	
}	

2、调试截图

录入信息

按位查找

插入操作

删除操作