seo 服务/seo综合检测

学院

计算机科学与教育软件学院

年级、专业、班

网络161

姓名

卟咚君

学号

1606100***

实验课程名称

数据结构实验

成绩

实验项目名称

实验一 链式存储结构的基本操作

指导老师

**

一、实验目的

掌握线性的定义及基本操作，用链表实现：遍历、查找、插入、删除、翻转。

二、使用仪器、器材

微机一台

操作系统：WinXP

编程软件：C++

三、实验内容及原理

（1）用随机函数生成8个3位整数（100~999），把这些整数存于链表中；

（2）输出链表的内容；

（3）读入一个整数，查看该整数是否在表中，若在，输出其位置（首位置为1）；

（4）读入一个整数，以及要插入的位置，把该整数插入到链表中，输出链表的内容（要求判断输入的位置是否合理）；

（5）读入一个整数，若该整数在链表里，删除该整数，输出链表的内容；

（6）把链表的内容翻转，输出链表的内容。

思路：通过定义一个class类 ListNode，表示链表的结点；

      通过定义一个class类 SingleList ，表示链表，封装了对链表的各种操作：

void MakeEmpty();                       //清空链表

    int Length();                           //返回链表的长度

    int Find(Type item);                    //在链表中查询数据item,找到则返回相应链表结点的位置，否则返回-1

    bool Insert(Type item, int n );         //在位置n的结点前插入一个新结点，新结点的data值为item

    ListNode<Type>* Get(int pos);           //查询链表的第n个链表结点，返回链表结点的指针

    bool Remove(int n);                     //删除第n个链表结点

    void Rollback();                        //对链表的内容进行翻转

    void Print();                           //输出链表的内容

源代码：

#include<iostream>

#include<ctime>

#include<cmath>

using namespace std;

template<typename Type> class ListNode{

public:

    ListNode() :data(0), next(NULL){}

    ListNode(const Type item, ListNode<Type> *next = NULL) :data(item), next(next){}

    ~ListNode(){

        next = NULL;

    }

public:

    Type GetData();

    friend ostream& operator<< <Type>(ostream&, ListNode<Type>&);

    Type data;

    ListNode *next;

};

template<typename Type> Type ListNode<Type>::GetData(){

    return this->data;

}

template<typename Type> ostream& operator<<(ostream& os, ListNode<Type>& out){

    os << out.data;

    return os;

}

template<typename Type> class SingleList{

public:

    SingleList() :head(new ListNode<Type>()), len(0){}

    ~SingleList(){

        MakeEmpty();

        delete head;

    }

public:

    void MakeEmpty();                       //清空链表

    int Length();                           //返回链表的长度

    int Find(Type item);                    //在链表中查询数据item,找到则返回相应链表结点的位置，否则返回-1

    bool Insert(Type item, int n);         //在位置n的结点前插入一个新结点，新结点的data值为item

    ListNode<Type>* Get(int pos);           //查询链表的第n个链表结点，返回链表结点的指针

    bool Remove(int n);                     //删除第n个链表结点

    void Rollback();                        //对链表的内容进行翻转

    void Print();                           //输出链表的内容

private:

    ListNode<Type> *head;                   //链表的表头，不存储数据data

    int len;                                //链表的长度

};

template<typename Type> void SingleList<Type>::MakeEmpty(){  //清空链表

    ListNode<Type> *pdel;

    while (head->next != NULL){

        pdel = head->next;

        head->next = pdel->next;

        delete pdel;

    }

}

template<typename Type> int SingleList<Type>::Length(){ //返回链表的长度

    return len;

}

template<typename Type> int SingleList<Type>::Find(Type item){ //在链表中查询数据item,找到则返回相应链表结点的位置，否则返回-1

    int pos = 1;

    ListNode<Type> *pmove = head->next;

    while (pmove&&pmove->data != item){

        pmove = pmove->next;

        pos++;

    }

    if (pmove == NULL) pos = -1;

    return pos;

}

template<typename Type> ListNode<Type>* SingleList<Type>::Get(int n){ //查询链表的第n个链表结点，返回链表结点的指针

    if (n <= 0 || n>len){

        cout << "请输入合法的数据下标" << endl;

        return NULL;

    }

    ListNode<Type> *pmove = head->next;

    int pos = 1;

    while (pos != n&&pmove){

        pmove = pmove->next;

        pos++;

    }

    return pmove;

}

template<typename Type> bool SingleList<Type>::Remove(int n){  //删除第n个链表结点

    if (n <= 0){

        cout << "请输入合理的下标位置" << endl;

        exit(1);

    }

    ListNode<Type> *pmove = head->next, *pdel;

    for (int i = 1; i<n&&pmove->next; i++){

        pmove = pmove->next;

    }

    if (pmove->next == NULL){

        cout << "查找到的下标超出链表" << endl;

        exit(1);

    }

    pdel = pmove->next;

    pmove->next = pdel->next;

    delete pdel;

    cout << "删除成功第" << n << "个链表结点成功" << endl;

    len--;

    return 1;

}

template<typename Type> bool SingleList<Type>::Insert(Type item, int n){  //在位置n的结点前插入一个新结点，新结点的data值为item

    if (n <= 0 || n>len + 1){

        cout << "请输入合理的下标位置" << endl;

        return 0;

    }

    ListNode<Type> *pmove = head;

    ListNode<Type> *pnode = new ListNode<Type>(item);

    for (int i = 1; i<n&&pmove; i++){

        pmove = pmove->next;

    }

    len++;

    pnode->next = pmove->next;

    pmove->next = pnode;

    cout << "在第" << n << "位插入" << item << "成功" << endl;

    return 1;

}

template<typename Type> void SingleList<Type>::Print(){  //输出链表的内容

    ListNode<Type> *pmove = head->next;

    cout << "head";

    while (pmove){

        cout << "--->" << pmove->data;

        pmove = pmove->next;

    }

    cout << "--->over" << endl;

}

template<typename Type> void SingleList<Type>::Rollback(){  //对链表的内容进行翻转

    for (int i = 1; i <= len / 2; i++){

        ListNode<Type> *node1 = Get(i);

        ListNode<Type> *node2 = Get(len - i + 1);

        Type num = node1->data;

        node1->data = node2->data;

        node2->data = num;

    }

    cout << "翻转成功" << endl;

}

int main(){

    time_t t;

    srand((unsigned)time(&t));  //由时间确定随机序列，执行一次

    SingleList<int> Slist;      //定义一个单链表

    for (int i = 1; i <= 8; i++){    //(1)随机函数生成100~999的数据存入单链表中

        Slist.Insert(rand() % 900 + 100, i);

    }

    Slist.Print();   //(2)输出链表的内容；

    bool flag;

    int num,pos;

    cout << "如果要判断一个数是否在链表中，请输入任意非零数进入判断，否则跳过该判断请输入0:";

    cin >> flag;

    while (flag){

        cout << "读入一个数据，判断是否在链表中:";  //(3)读入一个整数，查看该整数是否在表中，若在，输出其位置（首位置为1）；

        cin >> num;      //读入一个数据

        pos = Slist.Find(num);  //pos等于数据在链表中的位置

        if (pos != -1){    //pos若等于-1,则表示不在链表中

            cout << "该数据在链表中的第" << pos << "个链表结点的位置" << endl;

        }

        else{

            cout << "该数据不在链表中" << endl;

        }

        cout << "如果要判断一个数是否在链表中，请输入任意非零数进入判断，否则跳过该判断请输入0:";

        cin >> flag;

    }

    cout << "如果要插入一个数进入链表中，请输入任意非零数进入插入，否则跳过该次插入请输入0:";

    cin >> flag;

    while (flag){

        cout << "读入一个数据和一个插入的位置，插入到链表中:";  //（4）读入一个整数，以及要插入的位置，把该整数插入到链表中，输出链表的内容（要求判断输入的位置是否合理）；

        cin >> num >> pos;   //读入一个数据和要插入的位置

        Slist.Insert(num, pos);     //在单链表的第pos位置插入数据num，插入时会在函数Slist.Insert(num, pos)中判断插入的位置是否合理

        Slist.Print();   //输出单链表的数据

        cout << "如果要插入一个数进入链表中，请输入任意非零数进入插入，否则跳过该次插入请输入0:";

        cin >> flag;

    }

    cout << "如果要删除链表一个数据，请输入任意非零数进入删除，否则跳过该次删除请输入0:";

    cin >> flag;

    while (flag){

        cout << "读入一个数据，若在链表中则删除它:";  //（5）读入一个整数，若该整数在链表里，删除该整数，输出链表的内容；

        cin >> num;    //读入一个数据

        pos = Slist.Find(num);  //pos等于数据在链表中的位置

        if (pos != -1){   //若pos!=-1,则表示在链表中存在

            Slist.Remove(pos);   //删除对应pos位置的链表结点的数据

            Slist.Print();   //输出单链表的数据

        }//把链表的内容翻转，输出链表的内容。

        else{

            cout << "该数据不在链表中" << endl;

        }

        cout << "如果要删除链表一个数据，请输入任意非零数进入删除，否则跳过该次删除请输入0:";

        cin >> flag;

    }

    cout << "翻转后的数据:";  //（6）  Slist.Rollback();  //翻转链表

    Slist.Print();     //输出链表

    return 0;

}

• 实验过程原始数据记录

1. 在程序这次运行中，生成的随机数通过rand() % 900 + 100，控制存入链表的数据在100~999之间。
2. 然后输出链表的内容。
3. 读入一个整数581，查看该整数是否在表中，程序运行表示存在在链表的第3个链表结点中
4. 读入一个整数588，查看该整数是否在表中，程序运行表示链表不存在该数据
5. 读入一个整数322，以及要插入的位置1，把该整数插入到链表中，输出链表的内容，并判断要求判断输入的位置。程序运行结果正确。插入表头成功。
6. 读入一个整数666，以及要插入的位置5，把该整数插入到链表中，输出链表的内容，并判断要求判断输入的位置。程序运行结果正确。插入表中间成功。
7. 读入一个整数888，以及要插入的位置11，把该整数插入到链表中，输出链表的内容，并判断要求判断输入的位置。程序运行结果正确。插入表尾成功。
8. 读入一个整数100，以及要插入的位置-1，把该整数插入到链表中，输出链表的内容，并判断要求判断输入的位置。程序运行结果正确，提示输入下标出错。
9. 读入一个整数100，以及要插入的位置100，把该整数插入到链表中，输出链表的内容，并判断要求判断输入的位置。程序运行结果正确，提示输入下标出错。
10. 读入一个整数822，若该整数在链表里，删除该整数，输出链表的内容；程序运行表示删除第2个链表结点（该数据所在的结点）。
11. 读入一个整数366，若该整数在链表里，删除该整数，输出链表的内容；程序运行表示链表中不存在该数据。
12. 把链表的内容翻转，输出链表的内容。翻转结果正确。

• 实验结果及分析

通过这次实验，掌握了线性表的链表的遍历、查找、插入、删除、翻转等基本操作。

通过定义一个class类 ListNode，表示链表的结点；通过定义一个class类 SingleList ，表示链表，封装了对链表的各种操作：在链表SingleList中，表头不存储数据，在SingleList插入数据，先判断是否插入的位置是否合理，合理则插入数据。由于表头不存储数据，所以所有的插入方式（表头插入，中间插入，表尾插入）都可归结成一种情况解决。而在删除的过程中，一开始删除数据后，忘记把链表的长度对应的减一，导致翻转的时候出错，已改正。删除的时候也是要要判断删除的位置是否合理，合理才删除。翻转的时候其实链表结点不变，只是按照链表中间对称的方式把头尾的内容进行交换，以达到翻转链表内容的效果。