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

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

返回:贺老师课程教学链接


【项目 - 链表类】
动态链表也是程序设计中的一种非常有用的数据结构。可以说,是否能够理解有关操作的原理,决定了你是否有资格称为“科班”出身。在后续的专业基础课中,相关的内容还会从不同的角度,反复地认识,反复地实践。不过,在现阶段多些体验,也是很有必要的了。
(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;
}


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

[参考解答]


【项目-Josephus(约瑟夫环)问题】
n个小孩子围成一圈,从第一个小孩子开始顺时针方向数数字,到第m个小孩子离开,这样反反复复,最终只剩下一个小孩子,求第几个小孩子留下?
    提示:约瑟夫环即是一个首尾相连的链表,在建立好这个环以后,从头结点开始,每次间隔m孩子删除一个结点,直至只余下一个结点(删除了n-1个)。


    参考下面的代码,也可以自行设计类。

//链表结点kid,其中number为这个人的编号
struct kid
{
    int number;
    kid *next;
};

//约瑟夫环类
class joseph_ring
{
private:
    int n;//用于存放人数
    int m;//用于存放初始密码
    kid *head;//链表的头结点,初始化时指向1号孩子
public:
    joseph_ring(int nn, int mm);//创建nn个孩子,间隔为mm的约瑟夫环
    void show();//运算并输出的成员函数
};
//定义joseph_ring类中的成员函数
……
int main()
{
    int n,m;
    cout<<"n=";
    cin>>n;
    cout<<"m=";
    cin>>m;
    joseph_ring j(n,m);
    j.show();
    return 0;
}
[ 参考解答]

目录
相关文章
|
17天前
|
存储 C++
C++的list-map链表与映射表
```markdown C++ 中的`list`和`map`提供链表和映射表功能。`list`是双向链表,支持头尾插入删除(`push_front/push_back/pop_front/pop_back`),迭代器遍历及任意位置插入删除。`map`是键值对集合,自动按键排序,支持直接通过键来添加、修改和删除元素。两者均能使用范围for循环遍历,`map`的`count`函数用于统计键值出现次数。 ```
15 1
|
1月前
|
存储 C++
C++的list-map链表与映射表
这篇教程介绍了C++中`list`链表和`map`映射表的基本使用。`list`链表可通过`push_front()`、`push_back()`、`pop_front()`和`pop_back()`进行元素的添加和删除,使用迭代器遍历并支持在任意位置插入或删除元素。`map`是一个键值对的集合,元素自动按键值排序,可使用下标操作符或`insert()`函数插入元素,通过迭代器遍历并修改键值对,同时提供`count()`方法统计键值出现次数。教程中包含多个示例代码以帮助理解和学习。
18 2
|
18天前
|
Java C++ 开发者
如何根据项目需求选择使用C++还是Python进行内存管理?
【7月更文挑战第2天】如何根据项目需求选择使用C++还是Python进行内存管理?
18 0
|
1月前
|
C++ Python
UE C++ 链表
UE C++ 链表
|
2月前
|
算法 C++
c++算法学习笔记 (13) 链表
c++算法学习笔记 (13) 链表
|
1月前
|
C++ 容器
【C++进阶】深入STL之list:高效双向链表的使用技巧
【C++进阶】深入STL之list:高效双向链表的使用技巧
22 0
|
2月前
|
存储 C++ UED
【C++】飞机大战项目记录
通过上面的设计,我们实现来看飞机大战的主要功能
62 4
|
2月前
|
存储 安全 测试技术
【C++】string学习 — 手搓string类项目
C++ 的 string 类是 C++ 标准库中提供的一个用于处理字符串的类。它在 C++ 的历史中扮演了重要的角色,为字符串处理提供了更加方便、高效的方法。
36 0
【C++】string学习 — 手搓string类项目
|
2月前
|
C++
C++入门项目——通讯管理系统
C++入门项目——通讯管理系统
|
2月前
|
设计模式 存储 算法
C++从入门到精通:3.7阅读和理解开源项目——在实际项目中应用C++编程技巧和规范
C++从入门到精通:3.7阅读和理解开源项目——在实际项目中应用C++编程技巧和规范