《C++语言基础》实践参考—— 链表类

返回：贺老师课程教学链接  项目要求

【项目 - 链表类】
动态链表也是程序设计中的一种非常有用的数据结构。可以说，是否能够理解有关操作的原理，决定了你是否有资格称为“科班”出身。在后续的专业基础课中，相关的内容还会从不同的角度，反复地认识，反复地实践。不过，在现阶段多些体验，也是很有必要的了。
（1）阅读下面的程序，回顾一下动态链表，阅读程序过程中，请用笔画一画形成链表的过程中指针值的变化。

#include <iostream>
using namespace std;
struct Student
{
    int num;
    double score;
    struct Student *next;
};
int main( )
{
    Student *head=NULL,*p,*q;
    //建立动态链表
    for(int i=0; i<3; i++)
    {
        p = new Student;
        cin>>p->num>>p->score;
        p->next=NULL;
        if (i==0) head=p;
        else q->next=p;
        q=p;
    }
    //输出动态链表
    p=head;
    while(p!=NULL)
    {
        cout<<p->num<<" "<<p->score<<endl;
        p=p->next;
    }
    return 0;
}

（2）请在下面已有代码的基础上完善程序，完成动态链表的简单操作，程序运行的截图供参考。 

class Student  //结点类
{
public:
    Student(int n,double s):num(n), score(s), next(NULL) {}
    ~Student();
    Student *next;   //指向下一个结点
    int num;
    double score;
};

class MyList  //链表类，其中的成员是学生
{
public:
    MyList() { head=NULL;     }
    MyList(int n,double s); //以Student(n,s)作为单结点的链表
    ~MyList();
    int display();  //输出链表，返回值为链表中的结点数
    void insert(int n,double s);  //插入：将Student(n,s)结点插入链表，该结点作为第一个结点
    void append(int n,double s);  //追加：将Student(n,s)结点插入链表，该结点作为最后一个结点
    void cat(MyList &il); //将链表il连接到当前对象的后面
    int length();  //返回链表中的结点数（另一种处理，可以将结点数，作为一个数据成员）
private:
    Student *head;   //链表的头结点
};
//以下为类成员函数的定义
……
//测试函数
int main()
{
    int n;
    double s;
    MyList head1;
    cout<<"input head1: "<<endl;  //输入head1链表
    for(int i=0; i<3; i++)
    {
        cin>>n>>s;
        head1.insert(n,s);  //通过“插入”的方式
    }
    cout<<"head1: "<<endl; //输出head1
    head1.display();

    MyList head2(1001,98.4);  //建立head2链表
    head2.append(1002,73.5);  //通过“追加”的方式增加结点
    head2.append(1003,92.8);
    head2.append(1004,99.7);
    cout<<"head2: "<<endl;   //输出head2
    head2.display();

    head2.cat(head1);   //把head1追加到head2后面
    cout<<"length of head2 after cat: "<<head2.length()<<endl;
    cout<<"head2 after cat: "<<endl;   //显示追加后的结果
    head2.display();
    return 0;
}

[参考解答]

#include<iostream>
using namespace std;

class Student  //结点类
{
public:
    Student(int n,double s)
    {
        num=n;
        score=s;
        next=NULL;
    }
    ~Student()
    {
        if(!next)
            delete next;
        next=NULL;
    };
    Student *next;   //指向下一个结点
    int num;
    double score;
};

class MyList  //链表类
{
public:
    MyList()
    {
        head=NULL;
    }
    MyList(int n,double s); //以Student(n,s)作为单结点的链表
    ~MyList();
    int display();  //输出链表，返回值为链表中的结点数
    void insert(int n,double s);  //插入：将Student(n,s)结点插入链表，该结点作为第一个结点
    void append(int n,double s);  //追加：将Student(n,s)结点插入链表，该结点作为最后一个结点
    void cat(MyList &il); //将链表il连接到当前对象的后面
    int length();  //返回链表中的结点数
private:
    Student *head;   //链表的头结点
};

MyList::MyList(int n,double s)
{
    head=new Student(n,s);
}

MyList::~MyList()
{
    Student *p=head, *q;
    while (p != NULL)
    {
        q = p;
        p = p->next;
        delete q;
    }
    head = NULL;
}

int MyList::display()
{
    if(head==NULL)
    {
        cout<<"empty\n";
        return 0;
    }
    int cnt=0;
    Student *pt=head;
    while(pt)
    {
        ++cnt;
        cout<<pt->num<<", "<<pt->score<<endl;
        pt=pt->next;
    }
    return cnt;
}

void MyList::insert(int n, double s)
{
    Student * pt=new Student(n,s);
    pt->next =head;
    head=pt;
}

void MyList::append(int n,double s)
{
    Student * pt=new Student(n,s);
    if(head==NULL)
        head=pt;
    else
    {
        Student *pts=head;
        Student *pte=pts->next;
        while(pte)
        {
            pts=pte;
            pte=pts->next;
        }
        pts->next=pt;
    }
}

void MyList::cat(MyList& il)
{
    Student *pt=il.head;
    while(pt)
    {
        append(pt->num,pt->score);
        pt=pt->next;
    }
}

int MyList::length()
{
    int cnt=0;
    Student *pt=head;
    while(pt)
    {
        ++cnt;
        pt=pt->next ;
    }
    return cnt;
}

int main()
{
    int n;
    double s;
    MyList head1;
    cout<<"input head1: "<<endl;  //输入head1链表
    for(int i=0; i<3; i++)
    {
        cin>>n>>s;
        head1.insert(n,s);  //通过“插入”的方式
    }
    cout<<"head1: "<<endl; //输出head1
    head1.display();

    MyList head2(1001,98.4);  //建立head2链表
    head2.append(1002,73.5);  //通过“追加”的方式增加结点
    head2.append(1003,92.8);
    head2.append(1004,99.7);
    cout<<"head2: "<<endl;   //输出head2
    head2.display();

    head2.cat(head1);   //把head1追加到head2后面
    cout<<"length of head2 after cat: "<<head2.length()<<endl;
    cout<<"head2 after cat: "<<endl;   //显示追加后的结果
    head2.display();
    return 0;
}

[以下参考解答略]
（3）上面的结点，只处理包含包含学号和分数的学生信息。如何将之用于其他应用场合？结点类Students也可换作其他类。请设计建立一个动态链表，其中有5个结点，分别描述5个三角形，从头结点开始，逐个输出三角形的信息。

（4）上面的处理，仍然不够抽象，所以，只能就事论事地做，这是设计的大忌。实际上，结点的类型可以定义为以下模板类：

template <class T>
class Node
{
public:
	Node *next;
	T data;
};

这样，“一劳永逸”地解决了data的类型，只要在定义类时，对T进行实例化即可。在这里，T类型中也不需要涉及有关链表中指针的内容。
请按这种思路重写程序，为了测试，在main()函数中建立一个MyArray<double>型对象进行测试。另外，再建立一个MyArray<Triangle>型对象进行测试（Triangle为自定义三角形类）。

（5）本项目实现的是最简单的单向链表中的最基本的操作。从链表的类型上，还可以有双向链表（有头结点和尾结点，方便从前往后和从后往前的访问）、十字链表等，类似的方法可以构造二叉树、多叉树、图（例如，计算机网络结构可以抽象描述为图，社交网络中用户的关系也是图，顶有用的结构）。从操作角度，单链表在插入时，可以让结点保持有序；可以从链表中查找元素；很多的应用中涉及的算法需要借助于数据结构和算法的设计获得最佳的处理性能。关于这方面的内容不再以具体任务的形式给出，在后续的专业基础课中将会逐渐引出。另外，有程序设计基础，同学们是可以自己往前走一走，找相关的教材和书籍（数据结构、算法类）看一看，是否能依靠自己的力量往前走一走了。

时间： 2024-04-26 19:15:15

《C++语言基础》实践参考—— 链表类的相关文章

《C++语言基础》实践项目——链表类及其应用

返回:贺老师课程教学链接 [项目 - 链表类]动态链表也是程序设计中的一种非常有用的数据结构.可以说,是否能够理解有关操作的原理,决定了你是否有资格称为"科班"出身.在后续的专业基础课中,相关的内容还会从不同的角度,反复地认识,反复地实践.不过,在现阶段多些体验,也是很有必要的了.(1)阅读下面的程序,回顾一下动态链表,阅读程序过程中,请用笔画一画形成链表的过程中指针值的变化. #include <iostream> using namespace std; struct

C++实践参考——时间类

[项目 - 时间类]阅读.运行程序后,按要求扩充类的功能 #include <iostream> using namespace std; class Time { public: void set_time( ); void show_time( ); private: bool is_time(int, int, int); //这个成员函数设置为私有的,是合适的,请品味 int hour; int minute; int sec; }; void Time::set_time( ) {

《C++语言基础》实践参考——分数类中的运算符重载

返回:贺老师课程教学链接 [项目3-分数类中的运算符重载] (1)实现分数类中的运算符重载,在分数类中可以完成分数的加减乘除(运算后再化简).比较(6种关系)的运算.可以在第4周分数类代码的基础上开始工作. class CFraction { private: int nume; // 分子 int deno; // 分母 public: //构造函数及运算符重载的函数声明 }; //重载函数的实现及用于测试的main()函数 [参考解答] #include <iostream> #inclu

《C++语言基础》实践参考——复数类中的运算符重载（续）

返回:贺老师课程教学链接 项目要求 [项目1-复数类中的运算符重载(续)]在复数类中的运算符重载基础上(1)再定义一目运算符 -,-c相当于0-c.(2)定义Complex类中的<<和>>运算符的重载,实现输入和输出,改造原程序中对运算结果显示方式,使程序读起来更自然.[参考解答] #include <iostream> using namespace std; class Complex { public: Complex() { real=0; imag=0; }

《C++语言基础》实践参考——友元类

返回:贺老师课程教学链接 [项目5-友元类]定义下面两个类的成员函数(为体验友元类,实际上本例并不一定是一个好的设计,将两个类的合并为一个DateTime,日期.时间都处理更好) class Date; //对Date类的提前引用声明 class Time { public: Time(int,int,int); void add_a_second(Date &); //增加1秒,1秒后可能会到了下一天,乃到下一月.下一年 void display(Date &); //显示时间,格式:月

《C++语言基础》实践参考——三角形类1

返回:贺老师课程教学链接 [项目1 - 三角形类1]下面设计一个三角形类,请给出各成员函数的定义  #include<iostream> #include<Cmath> using namespace std; class Triangle { public: void setABC(double x, double y, double z);//置三边的值,注意要能成三角形 void getABC(double *x, double *y, double *z);//取三边的值

《C++语言基础》实践参考——三角形类2

返回:贺老师课程教学链接 [项目2 - 三角形类2]程序功能同项目1,main()函数如下,请重新定义Triangle类,其中逻辑特别简单的set和get成员函数,要处理为内置成员函数,直接在类内定义. int main() { Triangle tri1; //定义三角形类的一个实例(对象) double x,y,z; cout<<"请输入三角形的三边:"; cin>>x>>y>>z; tri1.setA(x); tri1.setB(y

《C++语言基础》实践参考——Time类中的运算符重载

返回:贺老师课程教学链接 [项目2-Time类中的运算符重载]实现Time类中的运算符重载. class CTime { private: unsigned short int hour; // 时 unsigned short int minute; // 分 unsigned short int second; // 秒 public: CTime(int h=0,int m=0,int s=0); void setTime(int h,int m,int s); void display(

《C++语言基础》实践参考——三角形类的构造函数

返回:贺老师课程教学链接 [项目1-三角形类的构造函数] 设计三角形类,通过增加构造函数,使对象在定义时能够进行初始化,可以由下面的类声明开始,需要自己实现相关的成员函数,以及增加要求的构造函数 class Triangle { public: double perimeter();//计算三角形的周长 double area();//计算并返回三角形的面积 void showMessage(); private: double a,b,c; //三边为私有成员数据 }; void Triang