静态链表 C++
《数据结构》实验二:
线性表综合实验
一.实验目的
巩固线性表的数据结构的存储方法和相关操作,学会针对具体应用,使用线性表的相关知识来解决具体问题,巩固课堂学习。
二. 实验内容
1.建立一个由n个学生成绩的顺序表,n的大小由自己确定,每一个学生的成绩信息由自己确定,实现数据的对表进行插入、删除、查找等操作。分别输出结果。
这里用静态链表来实现。
//
// main.cpp
// 静态链表
//
// Created by 梁华建 on 2017/10/14.
// Copyright © 2017年 梁华建. All rights reserved.
//
#include <iostream>
const int MaxSize=100;
template <class DataType>
struct SNode
{
DataType data;
int next;
};
template <class DataType>
class StaticLink {
public:
public:
StaticLink() ; //无参构造函数 空的静态链表
StaticLink(DataType a[],int n); //有参构造函数,建立一个长度为n的静态链表
~StaticLink(){} //析构函数为空
int Length(){return length;} //求线性表的长度
DataType Get(int i); //按位查找,在线性表中查找第i个元素
int Locate(DataType x); //按值查找,在线性表中查找值位x的元素序号
void Insert(int i,DataType x);//插入操作,在线性表中第i个位置插入值为x的元素
void Delete(int i); //删除操作,删除线性表的第i个元素
void PrintList(); //遍历操作,按序号依次输出各元素
private:
SNode<DataType> data[MaxSize];//存放数据元素的数组
int length;
int avail;
int first;
};
//无参构造函数
template <class DataType>
StaticLink<DataType>::StaticLink()
{
avail=2;
length=0;
first=-1;
data[first].next=-1;
}
//有参构造
template <class DataType>
StaticLink<DataType>::StaticLink(DataType a[],int n)
{
length=0;
if (n<=0&&n>MaxSize) throw "输入的学生数量有误";
// 先初始化数组
for (int i=0; i<=MaxSize; i++) {
data[i].next=i+1;
}
//让数组头尾相接
data[MaxSize-1].next=-1;
first=0;avail=1;
data[first].next=-1;
// 头插法
for (int i=0; i<=n-1; i++) {
int d=avail; //d=1
avail=data[avail].next;//avail=2
data[d].data=a[i];
// 用于验证下标的值
// std::cout<<d<<" ";
// std::cout<<data[avail].next;
// std::cout<<data[first].next<<" ";
// std::cout<<avail<<" ";
data[d].next=data[first].next; //d插入到first后面
data[first].next=d;
length++;
}
}
//遍历函数
template <class DataType>
void StaticLink<DataType>::PrintList()
{
int index=data[first].next;
std::cout<<"此刻学生数量为"<<length<<"\n";
for (int i=0; i<length; i++) {
std::cout<<data[index].data<<" ";
index=data[index].next;
}
std::cout<<"\n";
}
//插入函数
template <class DataType>
void StaticLink<DataType>::Insert(int i, DataType x)
{
if (i<=0&&i>MaxSize) throw "插入位置错误";
int s=0;
int p=first;
for (int j=0;j<i-1; j++) {
p=data[p].next;} //找到要插入的地方
s=avail;
avail=data[avail].next; //把
data[s].data=x;
data[s].next=data[p].next;
data[p].next=s;
length++;
}
//删除函数
template <class DataType>
void StaticLink<DataType>::Delete(int i)
{
int p=first;
if (i<=0&&i>=MaxSize)throw "输入的i有误 无法删除";
//找到要删除的节点
for (int j=0; j<i-1; j++) {
p=data[p].next;
}
//摘链操作
int q=data[p].next;
// DataType T=data[p].data;
data[p].next=data[q].next;
data[q].next=avail;
avail=q;
length--;
}
//get函数
template<class DataType>
DataType StaticLink<DataType>::Get(int i)
{
if (i<=0&&i>=MaxSize)throw "输入的i有误 无法删除";
return data[i-1].data;
}
int main(int argc, const char * argv[]) {
int n=0;
std::cout<<"你要录入的学生数量为";
std::cin>>n;
int a[]={50,60,70,80};
StaticLink<int> Student(a,n);
std::cout<<"在第三个位置插入成绩为10的学生"<<"\n";
Student.Insert(3, 10);
std::cout<<"插入后遍历所有学生信息"<<"\n";
Student.PrintList();
std::cout<<"删除位置为3的学生"<<"\n";
Student.Delete(3);
std::cout<<"删除后遍历所有学生信息"<<"\n";
Student.PrintList();
std::cout<<"第三个学生的成绩为"<<Student.Get(3)<<"\n";
return 0;
}
实验总结:这次实验对于我来说真的很有难度,没做过这种静态链表操作,不是很了解他是如何进行录入学生信息操作,在网上查询资料又重新看了一下老师的PPT后才有点明白,这次代码打了差不多一个星期,不过现在回想起来静下心来理解还是可以做到的,这种新的建立数组方式。