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

数据结构:实验二线性表综合实验④静态链表

程序员文章站 2022-06-06 14:06:19
...

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

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

三.实验报告
1.实验代码如下:

#include<iostream>
#include<string>
using namespace std;

const int Maxsize = 30;
template<typename T>
class Node {
public:
    T data;
    int next;      //存储指向下一个节点的数组下标
};
template <typename T>
class SLL {
public:
    SLL();//无参构造函数  
    SLL(T score[], int n);//带参构造函数  
    virtual ~SLL();//空的析构函数    
    void print();//遍历操作 
    T get(int i);//按位查找操作
    int Locate(T x);//按值查找操作
    void insert(int i, T x);//插入操作
    void Delete(int i);//删除操作
private:
    Node<T> node[Maxsize];//节点  
    int first;
    int avail;//指向空闲链的头指针  
    int length;//当前静态链表的长度
};
template<typename T>
SLL<T>::SLL(T score[], int n)
{
    length = 0;
    for (int i = 0; i<Maxsize; i++)
    {
        node[i].next = i + 1;
    }
    node[Maxsize - 1].next = -1;
    avail = 2;
    first = 1;
    node[first].next = -1;
    for (int j = n - 1; j >= 0; j--)
    {
        if (avail == -1)
        {
            break;
        }
        int s = avail;
        avail = node[avail].next;//空闲链的头指针后移  
        node[s].data = score[j];//将score[j]填入下标为S的节点  
        node[s].next = node[first].next;//将score[j]插到first后面  
        node[first].next = s;
        length++;
    }
}
template<class T>
SLL<T>::~SLL()
{
}
template<typename T>
void SLL<T>::print()
{
    int s = node[first].next;
    for (int i = 1; i <= length; i++)
    {
        cout << node[s].data << " ";
        s = node[s].next;
    }
}
template<typename T>
T SLL<T>::get(int i)
{
    if (i <= 0 || i>length) throw"位置非法";
    int p = first;
    for (int j = 0; j<i; j++)
    {
        p = node[p].next;
    }
    return node[p].data;
}
template<typename T>
int SLL<T>::Locate(T x)
{
    int count = 1;
    int p = first;
    while (node[p].next != -1)
    {
        p = node[p].next;
        if (node[p].data == x) return count;
        count++;
    }
    return -1;
}
template<typename T>
void SLL<T>::insert(int i, T x)
{
    if (i<0 || i>length) throw"位置非法";
    int p = first;
    for (int j = 1; j<i; j++)
    {
        p = node[p].next;   
    }
    int s = node[avail].next;
    node[avail].data = x;
    node[avail].next = node[p].next;
    node[p].next = avail;
    avail = s;
    length++;
}
template<typename T>
void SLL<T>::Delete(int i)
{
    if (i<0 || i>length + 1) throw"位置非法";
    int p = first;
    for (int j = 0; j<i; j++)
    {
        p = node[p].next;
    }
    int q = node[p].next;
    T e = node[p].data;
    node[p].next = node[q].next;
    node[q].next = avail;
    avail = q;
    length--;
}
void main()
{
    int score[5] = { 61, 71, 68, 45, 93 };
    SLL<int> student(score, 5);
    cout << "学生成绩:" ;
    student.print();
    cout << endl << "在位置3插入成绩63,结果如下:" ;
    student.insert(3,63);
    student.print();
    cout << endl << "在位置5删除成绩,删除后结果如下:" ;
    student.Delete(5);
    student.print();
    cout << endl << "位置2的成绩为:" << student.get(2);
    cout << endl << "成绩45所在位置为:" << student.Locate(45) ;
}

2.实验结果
数据结构:实验二线性表综合实验④静态链表

四.实验总结
通过静态链表建立一个由5个学生成绩的顺序表,学生成绩分别为66, 71, 68, 45, 93 ,对表在位置3插入63,插入后学生成绩为66, 71, 63,68, 45, 93 ,删除位置2的成绩71,删除后为66, 63, 68, 45, 93 .