欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

实验二 线性表综合实验(静态链表)

程序员文章站 2022-06-06 13:38:37
...

一.实验目的

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

.  实验内容

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



静态链表 源代码

#include <iostream>
#include<string>
using namespace std;
const int MaxSize = 10;

struct Student		//定义Student结构体
{
	string name;
	int Chinese;
	int Math;
	int English;
	int Sum;
};
ostream& operator << (ostream& os, const Student &ob)	//重载左移运算符,使其能直接输出自定义类型“Student”
{
	os << ob.name << "\t";
	os << ob.Chinese << "\t";
	os << ob.Math << "\t";
	os << ob.English << "\t";
	os << ob.Sum << "\t";
	return os;
}
template <class DataType>
struct SNode
{
	DataType data;
	int next;	//指针域(也称游标)
 };

template <class DataType>
class StaticLink
{
public:
	
	StaticLink(DataType a[], int n);
	~StaticLink();
	int Length();
	DataType Get(int index);
	int Locate(string x);
	void Insert(DataType x, int index);
	DataType Delete(int i);
	void PrintList();

private:
	int  first;  // 定义头指针
	int  avail;
	SNode<Student> SList[MaxSize];		//定义结点数组
	int length;

};

template <class DataType>
void StaticLink<DataType> ::PrintList()
{
	int s = first;
	cout << "-------------------------------------" << endl;
	cout << "姓名" << "\t" << "语文" << "\t" << "数学" << "\t" << "英语" << "\t" << "总分" << "\t" << endl;
	for (int i = 0; i <length; i++)
	{	
		s = SList[s].next;
		cout << SList[s].data  << endl;	
	}
	cout << "-------------------------------------" << endl;

}

template <class DataType>
int StaticLink<DataType>::Length()
{
	return length;
}
template <class DataType>
DataType StaticLink<DataType>::Get(int index)
{
	int s = first;
	for (int i= 0; i <index; i++)
	{
		s = SList[s].next;
	}
	return SList[s].data;
	
}

template <class DataType>
int StaticLink<DataType>::Locate(string x)
{
	int i = 1;
	int s = first;
	for (; i < length; i++)
	{
		s = SList[s].next;
		if (SList[s].data.name == x)
			break;
	}
	return i;
}

template <class DataType>
void StaticLink<DataType>::Insert(DataType x, int index)
{

	int s = first;
	for (int i = 1; i <index; i++)
	{
		s = SList[s].next;	
	}
	int i = avail;	//此i变量与循环变量i无关
	avail = SList[avail].next;
	SList[i].data = x;
	SList[i].next = SList[s].next;
	SList[s].next = i;
	SList[i].data.Sum = SList[i].data.Chinese + SList[i].data.Math + SList[i].data.English; //赋值Sum
	length++;
}


template <class DataType>
StaticLink<DataType>::StaticLink(DataType a[], int n)
{	
	avail = 1; first = 1; length = 0;	
	for (int i = 0; i < MaxSize; i++)		//初始化空间
	{
		SList[i].next= i + 1;
	}
	SList[MaxSize].next = -1;
	for (int i = n-1; i >=0; i--)	//逆向赋值,避免逆序输入
	{	
		int s = avail;
		avail = SList[avail].next;
		SList[s].data = a[i];
		SList[s].next = SList[first].next;
		SList[first].next = s;
		length++;
	}			
}


template <class DataType>
DataType StaticLink<DataType>::Delete(int i)
{
	int q = 1;
	int s = first;
	if (i<1 || i>length)		//判断输入位置是否异常
		throw "删除位置异常";
	else
	{	
		for (; q < i; q++)		//省略第一个条件
		{
			s = SList[s].next;
		}
		q = SList[s].next;
		DataType x = SList[q].data;
		SList[s].next = SList[q].next;
		SList[q].next = avail;
		avail = q;
		length--;
		return x;
	}

}

template <class DataType>
StaticLink <DataType>::~StaticLink()
{
	length = 0;
	cout << "链表已成功删除。" << endl;

}
int main()
{

	Student stu[MaxSize]; //最大容纳量
	int num;
	string TempName;
	cout << "请输入学生人数:";
	cin >> num;

	for (int i = 0; i < num; i++)
	{
		cout << "输入“break”退出输入" << endl;
		cout << "请输入第" << i + 1 << "名学生姓名:";
		cin >> TempName;
		if (TempName == "break")
		{
			num = i;
			break;
		}
		stu[i].name = TempName;
		cout << "请输入第" << i + 1 << "名学生语文成绩:";
		cin >> stu[i].Chinese;
		cout << "请输入第" << i + 1 << "名学生数学成绩:";
		cin >> stu[i].Math;
		cout << "请输入第" << i + 1 << "名学生英语成绩:";
		cin >> stu[i].English;
		stu[i].Sum = stu[i].Chinese + stu[i].Math + stu[i].English;
		cout << "-------------------------------------" << endl;
	}

	StaticLink<Student> demo(stu, num);
	demo.PrintList();
	cout << "链表总长为:";
	cout << demo.Length() << endl;
	cout << "-------------------------------------" << endl;

	cout << "查找第三名学生成绩:" << endl;
	cout << "-------------------------------------" << endl;
	cout << "姓名" << "\t" << "语文" << "\t" << "数学" << "\t" << "英语" << "\t" << "总分" << "\t" << endl;
	cout << demo.Get(3) << endl;
	cout << "-------------------------------------" << endl;

	cout << "查找姓名为“霜降”的位置:" << demo.Locate("霜降") << endl;
	cout << "-------------------------------------" << endl;

	cout << "在第二与第三间插入“秋分”同学的成绩" << endl;
	demo.Insert({ "秋分",95,86,93}, 3);
	demo.PrintList();
	cout << "链表总长为:";
	cout << demo.Length() << endl;
	cout << "-------------------------------------" << endl;
	cout << "删除第3位同学的成绩:" << demo.Delete(3).name<<endl;
	demo.PrintList();
	return 0;
}


实验截图:


输入:

实验二 线性表综合实验(静态链表)

输出:

实验二 线性表综合实验(静态链表)



实验总结与个人心得:

静态链表是用数组来表示单链表,用数组元素的下标来模拟单链表的指针。

因此静态链表里不存在指针。本想通过改写“祖传代码”来实现静态链表,后因改写幅度较大而放弃。

实现静态链表的关键是理解first、 avail在静态链表中的作用。

first是静态链表头指针,指向头结点,SList[first].next指向第一个元素。

avail是静态链表空闲指针,指向一个空结点,只要将avail赋值给新节点,然后将新节点插入到头结点后面,同时avail后移,即可完成添加操作。

int s = avail;

avail = SList[avail].next;
SList[s].data = a[i];
SList[s].next = SList[first].next;
SList[first].next = s;
length++;

头结点改为其他结点,就可以完成插入操作。

这种新节点插入到头结点后面的添加方式,类似于头插法;这种方式比较尴尬的是,会让数据逆序输入,导致逆序输出。

基于这点,我改写了循环条件,代码如下:

for (int i = n-1; i >=0; i--)//逆向赋值,避免逆序输入
{
int s = avail;
avail = SList[avail].next;
SList[s].data = a[i];
SList[s].next = SList[first].next;
SList[first].next = s;
length++;
}

由于结构发生改变,遍历静态链表的方式也发生改变,length为静态链表长度。代码如下:

int s = first;
for (int i= 0; i <length; i++)
{
s = SList[s].next;
}

存在的问题:

与上篇的双链表类似,过多的输入操作,而又没有对输入进行规范,容易因为误输入而导致程序崩溃,降低程序的健壮性。