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

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

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


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


目录
相关文章
|
4天前
|
设计模式 安全 编译器
【C++11】特殊类设计
【C++11】特殊类设计
24 10
|
9天前
|
C++
C++友元函数和友元类的使用
C++中的友元(friend)是一种机制,允许类或函数访问其他类的私有成员,以实现数据共享或特殊功能。友元分为两类:类友元和函数友元。类友元允许一个类访问另一个类的私有数据,而函数友元是非成员函数,可以直接访问类的私有成员。虽然提供了便利,但友元破坏了封装性,应谨慎使用。
40 9
|
4天前
|
存储 编译器 C语言
【C++基础 】类和对象(上)
【C++基础 】类和对象(上)
|
12天前
|
C++
【C++】string类的使用④(常量成员Member constants)
C++ `std::string` 的 `find_first_of`, `find_last_of`, `find_first_not_of`, `find_last_not_of` 函数分别用于从不同方向查找目标字符或子串。它们都返回匹配位置,未找到则返回 `npos`。`substr` 用于提取子字符串,`compare` 则提供更灵活的字符串比较。`npos` 是一个表示最大值的常量,用于标记未找到匹配的情况。示例代码展示了这些函数的实际应用,如替换元音、分割路径、查找非字母字符等。
|
12天前
|
编译器 C++
【C++】string类的使用④(字符串操作String operations )
这篇博客探讨了C++ STL中`std::string`的几个关键操作,如`c_str()`和`data()`,它们分别返回指向字符串的const char*指针,前者保证以&#39;\0&#39;结尾,后者不保证。`get_allocator()`返回内存分配器,通常不直接使用。`copy()`函数用于将字符串部分复制到字符数组,不添加&#39;\0&#39;。`find()`和`rfind()`用于向前和向后搜索子串或字符。`npos`是string类中的一个常量,表示找不到匹配项时的返回值。博客通过实例展示了这些函数的用法。
|
12天前
|
存储 C++
【C++】string类的使用③(非成员函数重载Non-member function overloads)
这篇文章探讨了C++中`std::string`的`replace`和`swap`函数以及非成员函数重载。`replace`提供了多种方式替换字符串中的部分内容,包括使用字符串、子串、字符、字符数组和填充字符。`swap`函数用于交换两个`string`对象的内容,成员函数版本效率更高。非成员函数重载包括`operator+`实现字符串连接,关系运算符(如`==`, `&lt;`等)用于比较字符串,以及`swap`非成员函数。此外,还介绍了`getline`函数,用于按指定分隔符从输入流中读取字符串。文章强调了非成员函数在特定情况下的作用,并给出了多个示例代码。
|
17天前
|
C++
【C++】日期类Date(详解)②
- `-=`通过复用`+=`实现,`Date operator-(int day)`则通过创建副本并调用`-=`。 - 前置`++`和后置`++`同样使用重载,类似地,前置`--`和后置`--`也复用了`+=`和`-=1`。 - 比较运算符重载如`&gt;`, `==`, `&lt;`, `&lt;=`, `!=`,通常只需实现两个,其他可通过复合逻辑得出。 - `Date`减`Date`返回天数,通过迭代较小日期直到与较大日期相等,记录步数和符号。 ``` 这是236个字符的摘要,符合240字符以内的要求,涵盖了日期类中运算符重载的主要实现。
|
12天前
|
C++
C++】string类的使用③(修改器Modifiers)
这篇博客探讨了C++ STL中`string`类的修改器和非成员函数重载。文章介绍了`operator+=`用于在字符串末尾追加内容,并展示了不同重载形式。`append`函数提供了更多追加选项,包括子串、字符数组、单个字符等。`push_back`和`pop_back`分别用于在末尾添加和移除一个字符。`assign`用于替换字符串内容,而`insert`允许在任意位置插入字符串或字符。最后,`erase`函数用于删除字符串中的部分内容。每个函数都配以代码示例和说明。
|
12天前
|
安全 编译器 C++
【C++】string类的使用②(元素获取Element access)
```markdown 探索C++ `string`方法:`clear()`保持容量不变使字符串变空;`empty()`检查长度是否为0;C++11的`shrink_to_fit()`尝试减少容量。`operator[]`和`at()`安全访问元素,越界时`at()`抛异常。`back()`和`front()`分别访问首尾元素。了解这些,轻松操作字符串!💡 ```
|
12天前
|
存储 编译器 Linux
【C++】string类的使用②(容量接口Capacity )
这篇博客探讨了C++ STL中string的容量接口和元素访问方法。`size()`和`length()`函数等价,返回字符串的长度;`capacity()`提供已分配的字节数,可能大于长度;`max_size()`给出理论最大长度;`reserve()`预分配空间,不改变内容;`resize()`改变字符串长度,可指定填充字符。这些接口用于优化内存管理和适应字符串操作需求。