备案控制台
探索云世界
开发者社区 大数据 文章 正文

2014秋C++第19周 项目1参考 动态链表体验

2015-01-07 889
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 课程主页在http://blog.csdn.net/sxhelijian/article/details/39152703，课程资源在云学堂“贺老师课堂”同步展示，使用的帐号请到课程主页中查看。 【项目1 - 动态链表体验】下面是一个建立动态链表的程序。阅读程序，在草稿纸上画出链表建立的过程，借此学会如何建立链表。然后按要求改造程序。#include <iostream>u
课程主页在 http://blog.csdn.net/sxhelijian/article/details/39152703，课程资源在 云学堂“贺老师课堂”同步展示，使用的帐号请到课程主页中查看。 


【项目1 - 动态链表体验】

下面是一个建立动态链表的程序。阅读程序，在草稿纸上画出链表建立的过程，借此学会如何建立链表。然后按要求改造程序。 
#include  <iostream>
using namespace std;
struct Node
{
    int data;            //结点的数据
    struct Node *next;  //指向下一结点
};
Node *head=NULL;    //将链表头定义为全局变量，以便于后面操作
void make_list();   //建立链表
void out_list();    //输出链表
  
int main( )
{
    make_list();
    out_list();
    return 0;
}
void make_list()
{
    int n;
    Node *p;
    cout<<"输入若干正数（以0或一个负数结束）建立链表："
    cin>>n;
    while(n>0)   //输入若干正数建立链表，输入非正数时，建立过程结束
    {
        p=new Node;  //新建结点
        p->data=n;   
        p->next=head;  //新建的结点指向原先的链表头
        head=p;    //链表头赋值为新建的节点，这样，新结点总是链表头
        cin>>n;    //输入下一个数，准备建立下一个结点
    }
    return;
}
void out_list()
{
    Node *p=head;
    cout<<"链表中的数据为："<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return;
}

在上面的程序基础上定义下面的函数，实现相应的功能。

为简便起见，每编写一个函数，立刻在main函数中调用进行测试。
（1）编写make_list2()函数建立链表，使建立链表时，后输入的数据，将新输入的数字对应的结点放在链表末尾。若输入为3 5 2 9 4 7 0，建立的链表为：


（2）编写函数void search(int x)，输出链表中是否有值为x的结点。
（3）编写函数delete_first_node()，删除链表中的第一个结点。
（4）编写函数delete_node(int x)，删除结点值为x的结点。
（5）编写make_list3()函数建立链表，使建立链表时，使结点中的数据呈现升序。若输入为3 5 2 9 4 7 0，建立的链表为：

（6）编写函数void insert(int x)，将值为x的结点插入到由make_list3建立起来的有序链表中。

【参考解答】

　　（1）编写make_list2()函数建立链表，使建立链表时，后输入的数据，将新输入的数字对应的结点放在链表末尾。若输入为3 5 2 9 4 7 0，建立的链表为：

　　　　　

----参考解答----

#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
    int data;
    struct Node *next;
};
Node *head=NULL;
void make_list2();  //新结点始终在链表尾部
void out_list();
int main( )
{
    freopen("input.txt","r",stdin);
    make_list2();
    out_list();
    return 0;
}

void make_list2()
{
    int n;
    Node *p,*q;  //p用于指向新建立的结点, q指向链表尾部
    cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;
    cin>>n;
    while(n>0)
    {
        p=new Node;
        p->data=n;
        p->next=NULL;
        if(head==NULL)
            head=p;
        else
            q->next=p;
        q=p;
        cin>>n;
    }
    return;
}

//输出所有的节点
void out_list()
{
    Node *p=head;
    cout<<"链表中的数据为："<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return;
}

　　（ 2 ）编写函数 void search(int x) ，输出链表中是否有值为 x 的结点。

----参考解答----

#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
    int data;
    struct Node *next;
};
Node *head=NULL;
void make_list2();  //新结点始终在链表尾部
void out_list();
void search(int x);  //查找是否有值为x的结点
int main( )
{
    int x;
    freopen("input.txt","r",stdin);//调试中用重定向方便
    make_list2();
    out_list();
    cin>>x;  //测试中输入一个链表中有的数字
    search(x);
    cin>>x;  //测试中输入一个链表中没有的数字
    search(x);
    return 0;
}

void make_list2()
{
    int n;
    Node *p,*q;  //p用于指向新建立的结点, q指向链表尾部
    cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;
    cin>>n;
    while(n>0)
    {
        p=new Node;
        p->data=n;
        p->next=NULL;
        if(head==NULL)
            head=p;
        else
            q->next=p;
        q=p;
        cin>>n;
    }
    return;
}

//输出所有的节点
void out_list()
{
    Node *p=head;
    cout<<"链表中的数据为："<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return;
}

void search(int x)
{
    //查找是否有值为x的结点
    Node *p=head;
    while(p!=NULL&&p->data!=x)
    {
        p=p->next;
    }
    if(p!=NULL)  //退出上一层循环一定是因为p->data==x
        cout<<"在链表中有值为"<<x<<"的结点"<<endl;
    else
        cout<<"在链表中没有值为"<<x<<"的结点"<<endl;
    return;
}
//补充：这个版本的search，只判断是否找到，有兴趣的同学，可以实现能输出有几个的版本
//void search(int x)还可以重定义为bool search(int x)，让main函数根据返回值输出结果
//对应能输出有几个的版本，重定义为int search(int x)，返回值是存在的个数，为0没有找到

　　（ 3 ）编写函数 delete_first_node() ，删除链表中的第一个结点。

----参考解答----

#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
    int data;
    struct Node *next;
};
Node *head=NULL;
void make_list2();  //新结点始终在链表尾部
void out_list();
void delete_first_node();  //删除第一个结点
int main( )
{
    freopen("input.txt","r",stdin);//调试中用重定向方便
    make_list2();
    out_list();
    delete_first_node();
    out_list();
    return 0;
}

void make_list2()
{
    int n;
    Node *p,*q;  //p用于指向新建立的结点, q指向链表尾部
    cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;
    cin>>n;
    while(n>0)
    {
        p=new Node;
        p->data=n;
        p->next=NULL;
        if(head==NULL)
            head=p;
        else
            q->next=p;
        q=p;
        cin>>n;
    }
    return;
}

//输出所有的节点
void out_list()
{
    Node *p=head;
    cout<<"链表中的数据为："<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return;
}

void delete_first_node()
{
    Node *p=head;
    if (p!=NULL)
    {
        head = p->next;
        delete p;
        cout<<"删除了首结点."<<endl;
    }
    else
        {
            cout<<"空链表，不能删除."<<endl;
        }
    return;
}

　　（ 4 ）编写函数 delete_node(int x) ，删除结点值为 x 的结点。

----参考解答----

#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
    int data;
    struct Node *next;
};
Node *head=NULL;
void make_list2();  //新结点始终在链表尾部
void out_list();
void delete_node(int x);  //删除第一个结点
int main( )
{
    freopen("input.txt","r",stdin);//调试中用重定向方便
    make_list2();
    out_list();
    delete_node(3);
    out_list();
    return 0;
}

void make_list2()
{
    int n;
    Node *p,*q;  //p用于指向新建立的结点, q指向链表尾部
    cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;
    cin>>n;
    while(n>0)
    {
        p=new Node;
        p->data=n;
        p->next=NULL;
        if(head==NULL)
            head=p;
        else
            q->next=p;
        q=p;
        cin>>n;
    }
    return;
}

//输出所有的节点
void out_list()
{
    Node *p=head;
    cout<<"链表中的数据为："<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return;
}

void delete_node(int x)
{
    Node *p,*q;
    if (head==NULL)
    cout<<"空链表，不能删除";
    else
    {
       //要删除的恰是首结点（不排除连续有若干个结点值为x），
       while(head!=NULL&&head->data==x)
       {
           p=head;
           head=head->next;
           delete p;
       }
       if(head!=NULL)
       {
           p=head;
           q=p->next;
           while(q!=NULL)
           {
               if(q->data==x)//q就是该删除的结点
               {
                   p->next=q->next;
                   delete q;
               }
               else     //q不该删除，继续考察下一个
               {
                   p=q;
               }
               q=p->next;  //总是p的下一个结点
           }
       }
    }
    return;
}

为充分测试，该程序运行了5次，所用的测试输入数据分别为：

5 2 9 9 7 11 3 0

3 5 2 9 9 7 11 0

3 5 2 9 3 9 7 11 0

3 5 2 9 4 9 7 11 0

3 3 3 3 3 3 3 0


　　（5）编写make_list3()函数建立有序链表，使建立链表时，结点中的数据呈现升序。若输入为3 5 2 9 4 7 0，建立的链表为：

　　　　

----参考解答----

#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
    int data;
    struct Node *next;
};
Node *head=NULL;
void make_list3();  //建立有序链表，各结点由小到大
void out_list();
int main( )
{
    freopen("input.txt","r",stdin);//调试中用重定向方便
    make_list3();
    out_list();
    return 0;
}

void make_list3()
{
    int n;
    Node *t,*p,*q;  //p用于指向新建立的结点, q指向链表尾部
    cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;
    cin>>n;
    while(n>0)
    {
        t=new Node;
        t->data=n;
        t->next=NULL;
        if(head==NULL)   //是空链表，p作为第一个结点即可
            head=t;
        else             //插入p结点后，各结点应该保持有序
        {
            if(n<=head->data)  //新加入的结点应该为首结点
            {
                t->next=head;
                head=t;
            }
            //应该找到合适的位置后，将结点插入
            //此时，链表中至少已经有一个结点，且插入结点不是首结点
            else
            {
                p=head;
                q=p->next;   //p与q相邻，p更靠近q，插入位置将在p和q之间
                while(q!=NULL&&n>q->data)  //链表没有完且p结点比n小，一直往后找
                {
                    p=q;
                    q=p->next;
                }
                if(q==NULL) //q为null，作为最后一个结点直接插入到p后即可
                {
                    p->next = t;
                }
                else   //t插入到p和q之间
                {
                    t->next=q;
                    p->next=t;
                }
            }
       }
        cin>>n;
    }
    return;
}

//输出所有的节点
void out_list()
{
    Node *p=head;
    cout<<"链表中的数据为："<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return;
}

　　（ 6 ）编写函数 void insert(int x) ，将值为 x 的结点插入到由 make_list3 建立起来的有序链表中。

----参考解答1----

#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
    int data;
    struct Node *next;
};
Node *head=NULL;
void make_list3();  //建立有序链表，各结点由小到大
void out_list();
void insert(int x); //将值为x的结点插入到有序链表中，使仍有序
int main( )
{
    freopen("input.txt","r",stdin);//调试中用重定向方便
    make_list3();
    out_list();
    insert(15);
    out_list();
    return 0;
}

void make_list3()
{
    int n;
    Node *t,*p,*q;  //p用于指向新建立的结点, q指向链表尾部
    cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;
    cin>>n;
    while(n>0)
    {
        t=new Node;
        t->data=n;
        t->next=NULL;
        if(head==NULL)   //是空链表，p作为第一个结点即可
            head=t;
        else             //插入p结点后，各结点应该保持有序
        {
            if(n<=head->data)  //新加入的结点应该为首结点
            {
                t->next=head;
                head=t;
            }
            //应该找到合适的位置后，将结点插入
            //此时，链表中至少已经有一个结点，且插入结点不是首结点
            else
            {
                p=head;
                q=p->next;   //p与q相邻，p更靠近q，插入位置将在p和q之间
                while(q!=NULL&&n>q->data)  //链表没有完且p结点比n小，一直往后找
                {
                    p=q;
                    q=p->next;
                }
                if(q==NULL) //q为null，作为最后一个结点直接插入到p后即可
                {
                    p->next = t;
                }
                else   //t插入到p和q之间
                {
                    t->next=q;
                    p->next=t;
                }
            }
        }
        cin>>n;
    }
    return;
}

void insert(int x) //将值为x的结点插入到有序链表中，使仍有序
{
    Node *t,*p,*q;  //p用于指向新建立的结点, q指向链表尾部
    t=new Node;
    t->data=x;
    t->next=NULL;
    if(head==NULL)   //是空链表，p作为第一个结点即可
        head=t;
    else             //插入p结点后，各结点应该保持有序
    {
        if(x<=head->data)  //新加入的结点应该为首结点
        {
            t->next=head;
            head=t;
        }
        //应该找到合适的位置后，将结点插入
        //此时，链表中至少已经有一个结点，且插入结点不是首结点
        else
        {
            p=head;
            q=p->next;   //p与q相邻，p更靠近q，插入位置将在p和q之间
            while(q!=NULL&&x>q->data)  //链表没有完且p结点比n小，一直往后找
            {
                p=q;
                q=p->next;
            }
            if(q==NULL) //q为null，作为最后一个结点直接插入到p后即可
            {
                p->next = t;
            }
            else   //t插入到p和q之间
            {
                t->next=q;
                p->next=t;
            }
        }
    }
    return;
}


//输出所有的节点
void out_list()
{
    Node *p=head;
    cout<<"链表中的数据为："<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return;
}

----参考解答2----

　　实际上，从程序整体上看，makelist3()可以直接调用insert(int x)实现，这样写出的程序合乎工程上的原则。这启示我们，用函数组织程序结构，应该成为一种意识。

#include <iostream>
#include <cstdio>
using namespace std;
struct Node
{
    int data;
    struct Node *next;
};
Node *head=NULL;
void make_list3();  //建立有序链表，各结点由小到大
void out_list();
void insert(int x); //将值为x的结点插入到有序链表中，使仍有序
int main( )
{
    freopen("input.txt","r",stdin);//调试中用重定向方便
    make_list3();
    out_list();
    insert(15);
    out_list();
    return 0;
}

void make_list3()
{
    int n;
    cout<<"输入若干正数（以0或一个负数结束）建立链表："<<endl;
    cin>>n;
    while(n>0)
    {
        insert(n);//调用insert，makelist简单得不得了
        cin>>n;
    }
    return;
}

void insert(int x) //将值为x的结点插入到有序链表中，使仍有序
{
    Node *t,*p,*q;  //p用于指向新建立的结点, q指向链表尾部
    t=new Node;
    t->data=x;
    t->next=NULL;
    if(head==NULL)   //是空链表，p作为第一个结点即可
        head=t;
    else             //插入p结点后，各结点应该保持有序
    {
        if(x<=head->data)  //新加入的结点应该为首结点
        {
            t->next=head;
            head=t;
        }
        //应该找到合适的位置后，将结点插入
        //此时，链表中至少已经有一个结点，且插入结点不是首结点
        else
        {
            p=head;
            q=p->next;   //p与q相邻，p更靠近q，插入位置将在p和q之间
            while(q!=NULL&&x>q->data)  //链表没有完且p结点比n小，一直往后找
            {
                p=q;
                q=p->next;
            }
            if(q==NULL) //q为null，作为最后一个结点直接插入到p后即可
            {
                p->next = t;
            }
            else   //t插入到p和q之间
            {
                t->next=q;
                p->next=t;
            }
        }
    }
    return;
}


//输出所有的节点
void out_list()
{
    Node *p=head;
    cout<<"链表中的数据为："<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
    return;
}







=================== 迂者 贺利坚 CSDN博客专栏=================
|==　IT学子成长指导专栏　专栏文章的分类目录（不定期更新）　==|
|==　C++ 课堂在线专栏　　贺利坚课程教学链接（分课程年级）　==|
|==　我写的书——《逆袭大学——传给IT学子的正能量》　　　　==|
===== 为IT菜鸟起飞铺跑道，和学生一起享受快乐和激情的大学 =====
文章标签：
C++
DataX
关键词：
C++项目
C++链表
C++参考
C++动态链表
C++项目参考
贺利坚
目录
相关文章
北飞的山羊
|
26天前
|
C++
【链表】还不会用C++实现链表？一文教会你各种链表的实现
【链表】还不会用C++实现链表？一文教会你各种链表的实现
北飞的山羊
29 0
泡沫o0
|
1月前
|
开发工具 C语言 C++
CMake构建大型C/C++项目：跨平台设计与高级应用（二）
CMake构建大型C/C++项目：跨平台设计与高级应用
泡沫o0
41 0
SarPro
|
11天前
|
存储 算法 Linux
【实战项目】网络编程：在Linux环境下基于opencv和socket的人脸识别系统--C++实现
【实战项目】网络编程：在Linux环境下基于opencv和socket的人脸识别系统--C++实现
SarPro
32 6
蓝易云
|
21天前
C/C++test两步完成CMake项目静态分析
通过将C/C++test集成到CMake项目中，并根据项目的需要进行配置，可以在两步内完成CMake项目的静态分析。这样可以帮助开发人员及时发现并修复潜在的代码问题，提高代码质量和可靠性。
蓝易云
8 0
凉开水白菜
|
21天前
|
存储 缓存 C++
C++链表常用的函数编写（增查删改）内附完整程序
C++链表常用的函数编写（增查删改）内附完整程序
凉开水白菜
23 0
泡沫o0
|
27天前
|
IDE 算法 编译器
快速掌握陌生C++项目的科学与心理学策略
快速掌握陌生C++项目的科学与心理学策略
泡沫o0
57 0
泡沫o0
|
27天前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
泡沫o0
36 0
泡沫o0
|
27天前
|
敏捷开发 安全 API
C/C++ 工程师面试：如何精彩展示你的项目经验并获得高分
C/C++ 工程师面试：如何精彩展示你的项目经验并获得高分
泡沫o0
71 0
泡沫o0
|
1月前
|
消息中间件 存储 算法
【C/C++ 泡沫精选面试题04】在实际项目中,多进程和多线程如何选择?
【C/C++ 泡沫精选面试题04】在实际项目中,多进程和多线程如何选择?
泡沫o0
43 1
泡沫o0
|
1月前
|
编译器 持续交付 项目管理
CMake构建大型C/C++项目：跨平台设计与高级应用（三）
CMake构建大型C/C++项目：跨平台设计与高级应用
泡沫o0
39 0

热门文章

最新文章

  • 1
    【C++ 17 新特性 文件管理】探索C++ Filesystem库：文件和目录操作的全面指南（一）
  • 2
    【C++ 函数调用操作符】探究C++中的函数调用操作符 基础到高级应用
  • 3
    C++ 智能指针与 JSON 处理：高级编程技巧与常见问题解析
  • 4
    【C++ 泛型编程 进阶篇】深入探究C++模板参数推导：从基础到高级
  • 5
    【C++ 泛型编程 高级篇】使用SFINAE和if constexpr灵活处理类型进行条件编译
  • 6
    从Proto到C++：探索Protocol Buffers的强大转换机制
  • 7
    【C++ 泛型编程 高级篇】C++模板元编程：使用模板特化 灵活提取嵌套类型与多容器兼容性
  • 8
    【C++ 17 新特性 文件管理】探索C++ Filesystem库：文件和目录操作的全面指南（二）
  • 9
    【C++ TypeName用法 】掌握C++中的TypeName：模板编程的瑞士军刀
  • 10
    【C/C++ 数据库 sqlite3】SQLite C语言API返回值深入解析
  • 1
    【C++】string类
    14
  • 2
    面向对象的C++题目以及解法2
    11
  • 3
    标准库中的string类（中）+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
    18
  • 4
    标准库中的string类（上）——“C++”
    10
  • 5
    自从学了C++之后，小雅兰就有对象了！！！（类与对象）（中）——“C++”
    16
  • 6
    自从学了C++之后，小雅兰就有对象了！！！（类与对象）（上）——“C++”
    18
  • 7
    C++编程之美：探索初始化之源、静态之恒、友情之桥与匿名之韵
    17
  • 8
    NumPy与其他语言（如C/C++）的接口实践
    17
  • 9
    [蓝桥杯 2023 省 B] 冶炼金属（c++)
    17
  • 10
    查找题（二分解法c++）
    19

    • 相关课程

    更多
  • C++ 入门教程开发文档
  • 面向运维的 python 脚本速成-1024程序员节创造营公益课
  • 场景实践- 新手玩转云计算-创建炫酷的简历网页
  • Serverless 赛题设置和解题思路解析
  • 全栈数据工程师养成攻略
  • 高级应用技能进阶

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce

    • 相关实验场景

    更多
  • 实验手册指导文档
  • 一键创建和部署高分电影推荐语音技能
  • 基于函数计算一键部署简易论坛
  • 1分钟部署经典小游戏
  • 搭建超级小班课网课系统
  • 函数计算进阶-IP查询工具开发
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）