AI 助理
备案控制台
开发者社区 大数据 文章 正文

《C语言及程序设计》实践参考——改造链表

2015-07-05 1001
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 返回：贺老师课程教学链接【项目3 - 改造链表】 下面是一个建立动态链表的程序。阅读程序，然后按要求改造程序。#include <iostream> using namespace std; #include <stdio.h>#include <malloc.h>#define N 5typedef struct

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

【项目3 - 改造链表】
下面是一个建立动态链表的程序。阅读程序，然后按要求改造程序。

#include  <iostream>  
using namespace std;  
#include <stdio.h>
#include <malloc.h>
#define N 5
typedef struct NODE
{
    int data;            //结点的数据
    struct NODE *next;  //指向下一结点
} Node;
Node *head=NULL;    //将链表头定义为全局变量，以便于后面操作
void make_list();   //建立链表
void out_list();    //输出链表

int main( )
{
    make_list();
    out_list();
    return 0;
}
void make_list()
{
    int n;
    Node *p;
    printf("输入若干正数（以0或一个负数结束）建立链表：" );
    scanf("%d", &n);
    while(n>0)   //输入若干正数建立链表，输入非正数时，建立过程结束
    {
        p=(Node*)malloc(sizeof(Node));  //新建结点
        p->data=n;
        p->next=head;  //新建的结点指向原先的链表头
        head=p;    //链表头赋值为新建的节点，这样，新结点总是链表头
        scanf("%d", &n);      //输入下一个数，准备建立下一个结点
    }
    return;
}
void out_list()
{
    Node *p=head;
    printf("链表中的数据为：\n");
    while(p!=NULL)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return;
}

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

[参考解答]

#include <stdio.h>
#include <malloc.h>
#define N 5
typedef struct NODE
{
    int data;            //结点的数据
    struct NODE *next;  //指向下一结点
} Node;
Node *head=NULL;
void make_list2();  //新结点始终在链表尾部
void out_list();    //输出链表

int main( )
{
    make_list2();
    out_list();
    return 0;
}
void make_list2()
{
    int n;
    Node *p,*q;  //p用于指向新建立的结点, q指向链表尾部
    printf("输入若干正数（以0或一个负数结束）建立链表：\n");
    scanf("%d", &n);
    while(n>0)
    {
        p=(Node*)malloc(sizeof(Node));
        p->data=n;
        p->next=NULL;
        if(head==NULL)
            head=p;
        else
            q->next=p;
        q=p;
        scanf("%d", &n);
    }
    return;
}
void out_list()
{
    Node *p=head;
    printf("链表中的数据为：\n");
    while(p!=NULL)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return;
}

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

#include <stdio.h>
#include <malloc.h>
#define N 5
typedef struct NODE
{
    int data;            //结点的数据
    struct NODE *next;  //指向下一结点
} Node;
Node *head=NULL;
void make_list2();  //新结点始终在链表尾部
void out_list();    //输出链表
void search(int x);  //查找是否有值为x的结点

int main( )
{
    int x;
    make_list2();
    out_list();
    scanf("%d", &x);  //测试中输入一个链表中有的数字
    search(x);
    scanf("%d", &x);  //测试中输入一个链表中没有的数字
    search(x);
    return 0;
}

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

void out_list()
{
    Node *p=head;
    printf("链表中的数据为：\n");
    while(p!=NULL)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return;
}

void search(int x)
{
    //查找是否有值为x的结点
    Node *p=head;
    while(p!=NULL&&p->data!=x)
    {
        p=p->next;
    }
    if(p!=NULL)  //退出上一层循环一定是因为p->data==x
        printf("在链表中有值为%d的结点\n", x);
    else
        printf("在链表中没有值为%d的结点\n", x);
    return;
}

补充：

这个版本的search，只判断是否找到，有兴趣的同学，可以实现能输出有几个的版本
void search(int x)还可以重定义为bool search(int x)，让main函数根据返回值输出结果
对应能输出有几个的版本，重定义为int search(int x)，返回值是存在的个数，为0没有找到

（3）编写函数delete_first_node()，删除链表中的第一个结点。
[参考解答]

#include <stdio.h>
#include <malloc.h>
#define N 5
typedef struct NODE
{
    int data;            //结点的数据
    struct NODE *next;  //指向下一结点
} Node;
Node *head=NULL;
void make_list2();  //新结点始终在链表尾部
void out_list();    //输出链表
void delete_first_node();  //删除第一个结点

int main( )
{
    make_list2();
    out_list();
    delete_first_node();
    out_list();
    return 0;
}

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

void out_list()
{
    Node *p=head;
    printf("链表中的数据为：\n");
    while(p!=NULL)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return;
}

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

（4）编写函数delete_node(int x)，删除结点值为x的结点。
[参考解答]

#include <stdio.h>
#include <malloc.h>
#define N 5
typedef struct NODE
{
    int data;            //结点的数据
    struct NODE *next;  //指向下一结点
} Node;
Node *head=NULL;
void make_list2();  //新结点始终在链表尾部
void out_list();    //输出链表
void delete_node(int x);  //删除第一个结点

int main( )
{
    make_list2();
    out_list();
    delete_node(3);
    out_list();
    return 0;
}

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

void out_list()
{
    Node *p=head;
    printf("链表中的数据为：\n");
    while(p!=NULL)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return;
}

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

为充分测试，该程序运行了4次，所用的测试输入数据分别为：
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 3 3 3 3 3 3 0

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

[参考解答]

#include <stdio.h>
#include <malloc.h>
#define N 5
typedef struct NODE
{
    int data;            //结点的数据
    struct NODE *next;  //指向下一结点
} Node;
Node *head=NULL;
void make_list3();  //建立有序链表，各结点由小到大
void out_list();    //输出链表

int main( )
{
    make_list3();
    out_list();
    return 0;
}

void make_list3()
{
    int n;
    Node *t,*p,*q;  //p用于指向新建立的结点, q指向链表尾部
    printf("输入若干正数（以0或一个负数结束）建立链表：\n");
    scanf("%d", &n);
    while(n>0)
    {
        t=(Node*)malloc(sizeof(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;
                }
            }
        }
        scanf("%d", &n);
    }
    return;
}

void out_list()
{
    Node *p=head;
    printf("链表中的数据为：\n");
    while(p!=NULL)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return;
}

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

#include <stdio.h>
#include <malloc.h>
#define N 5
typedef struct NODE
{
    int data;            //结点的数据
    struct NODE *next;  //指向下一结点
} Node;
Node *head=NULL;
void make_list3();  //建立有序链表，各结点由小到大
void out_list();    //输出链表
void insert(int x); //将值为x的结点插入到有序链表中，使仍有序

int main( )
{
    make_list3();
    out_list();
    insert(5);
    out_list();
    return 0;
}

void make_list3()
{
    int n;
    Node *t,*p,*q;  //p用于指向新建立的结点, q指向链表尾部
    printf("输入若干正数（以0或一个负数结束）建立链表：\n");
    scanf("%d", &n);
    while(n>0)
    {
        t=(Node*)malloc(sizeof(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;
                }
            }
        }
        scanf("%d", &n);
    }
    return;
}

void insert(int x) //将值为x的结点插入到有序链表中，使仍有序
{
    Node *t,*p,*q;  //p用于指向新建立的结点, q指向链表尾部
    t=(Node*)malloc(sizeof(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;
    printf("链表中的数据为：\n");
    while(p!=NULL)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return;
}

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

#include <stdio.h>
#include <malloc.h>
#define N 5
typedef struct NODE
{
    int data;            //结点的数据
    struct NODE *next;  //指向下一结点
} Node;
Node *head=NULL;
void make_list3();  //建立有序链表，各结点由小到大
void out_list();    //输出链表
void insert(int x); //将值为x的结点插入到有序链表中，使仍有序

int main( )
{
    make_list3();
    out_list();
    insert(5);
    out_list();
    return 0;
}

void make_list3()
{
    int n;
    printf("输入若干正数（以0或一个负数结束）建立链表：\n");
    scanf("%d", &n);
    while(n>0)
    {
        insert(n);
        scanf("%d", &n);
    }
    return;
}

void insert(int x) //将值为x的结点插入到有序链表中，使仍有序
{
    Node *t,*p,*q;  //p用于指向新建立的结点, q指向链表尾部
    t=(Node*)malloc(sizeof(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;
    printf("链表中的数据为：\n");
    while(p!=NULL)
    {
        printf("%d ", p->data);
        p=p->next;
    }
    printf("\n");
    return;
}
文章标签：
DataX
C语言
关键词：
C语言实践
C语言链表
链表c语言
C语言程序设计
链表程序设计
贺利坚
目录
相关文章
XIAZHI
|
2月前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践，体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案，包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例，帮助读者掌握C语言的基本语法和常用算法，提升编程能力。
XIAZHI
88 4
LuckiBit
|
15天前
|
存储 网络协议 编译器
【C语言】深入解析C语言结构体：定义、声明与高级应用实践
通过根据需求合理选择结构体定义和声明的放置位置，并灵活结合动态内存分配、内存优化和数据结构设计，可以显著提高代码的可维护性和运行效率。在实际开发中，建议遵循以下原则： - **模块化设计**：尽可能封装实现细节，减少模块间的耦合。 - **内存管理**：明确动态分配与释放的责任，防止资源泄漏。 - **优化顺序**：合理排列结构体成员以减少内存占用。
LuckiBit
83 14
LuckiBit
|
19天前
|
存储 算法 C语言
【C语言】深入浅出：C语言链表的全面解析
链表是一种重要的基础数据结构，适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现，以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
LuckiBit
144 6
众所周知
|
23天前
|
C语言 开发者
C语言中的模块化编程思想，介绍了模块化编程的概念、实现方式及其优势，强调了合理划分模块、明确接口、保持独立性和内聚性的实践技巧
本文深入探讨了C语言中的模块化编程思想，介绍了模块化编程的概念、实现方式及其优势，强调了合理划分模块、明确接口、保持独立性和内聚性的实践技巧，并通过案例分析展示了其应用，展望了未来的发展趋势，旨在帮助读者提升程序质量和开发效率。
众所周知
45 5
龙大吉
|
23天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
44 5
东方睿赢
|
23天前
|
存储 算法 C语言
用C语言开发游戏的实践过程，包括选择游戏类型、设计游戏框架、实现图形界面、游戏逻辑、调整游戏难度、添加音效音乐、性能优化、测试调试等内容
本文探讨了用C语言开发游戏的实践过程，包括选择游戏类型、设计游戏框架、实现图形界面、游戏逻辑、调整游戏难度、添加音效音乐、性能优化、测试调试等内容，旨在为开发者提供全面的指导和灵感。
东方睿赢
37 2
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
83 4
c的前世今生
|
2月前
|
存储 缓存 C语言
C语言：链表和数组有什么区别
C语言中，链表和数组是两种常用的数据结构。数组是一种线性结构，元素在内存中连续存储，通过下标访问，适合随机访问且大小固定的情况。链表由一系列不连续的节点组成，每个节点存储数据和指向下一个节点的指针，适用于频繁插入和删除操作的场景，链表的大小可以动态变化。
c的前世今生
34 2
石小浪♪
|
2月前
|
C语言
无头链表再封装方式实现 (C语言描述)
如何在C语言中实现无头链表的再封装，包括创建节点和链表、插入和删除操作、查找和打印链表以及销毁链表的函数。
石小浪♪
29 0
石小浪♪
|
2月前
|
C语言
C语言链式结构之有头单链表再封装写法
本文介绍了如何使用C语言对有头单链表进行封装，包括节点的创建、链表的初始化、数据的插入和删除，以及链表的打印等功能。
石小浪♪
21 1