程序员经验分享-hwhale

Educoder C&C++线性表实训

2023-10-28

目录

第1关：顺序构建线性表

第2关：逆序构建线性表

第3关：排序构建线性表

第4关：查找元素

第5关：删除指定位置的结点

第6关：删除包含特定数据的结点

第7关：线性表长度

第8关：线性表应用一：栈

第9关：线性表应用二：队列

第10关：线性表应用三：集合

第1关：顺序构建线性表

任务描述

本关任务：补全 insertHead函数 ，按照数据输入的顺序构建一个线性表。即如果输入的3个结点数据分别为1、2、3，则构建的线性表包含3个结点，且从前往后的结点数据分别为1、2、3。

相关知识

线性表（linear list）是一种数据结构，是由 n 个具有相同特性的数据元素构成的序列。

线性表中元素的个数 n 即为线性表的长度，当 n = 0 时称为空表。线性表的相邻元素之间存在着序偶关系。

如用（ a[0] ，…… ，a[i-1] ，a[i] ，a[i+1] ，…… ，a[n-1] ）表示一个线性表，则称 a[i-1] 是 a[i] 的前驱，a[i+1] 是 a[i] 的后继。

线性表的特性

  • 线性表中必存在唯一的一个“第一元素”；

  • 线性表中必存在唯一的一个“最后元素” ；

  • 除最后一个元素之外，均有唯一的后继；

  • 除第一个元素之外，均有唯一的前驱。

线性表的一般操作

  • 将线性表变为空表；

  • 返回线性表的长度，即表中元素个数；

  • 获取线性表某位置的元素；

  • 定位某个元素在线性表中的位置；

  • 在线性表中插入一个元素；

  • 删除某个元素；

  • 判断线性表是否为空；

  • 遍历输出线性表的所有元素；

  • 线性表排序。

线性表的表示方法

线性表可以用链表来实现。链表是通过指针链接在一起的一组数据项（结点）。

链表的每个结点都是同类型的结构，该结构中一般包含两类信息：

  • 数据域，存储业务相关的数据（如财务系统的数据域为财务信息，车辆管理系统的业务信息为车辆信息）；

  • 指针域，用于构建结点的链接关系。单链表的实现只需要一个指针。

参考答案

#include "linearList.h"

node *insertTail(node *h, node *t)
{
    // 请在此添加代码，补全函数insertTail
    /********** Begin *********/
    if(h == NULL) // 空链表单独处理
    {
        t->next = NULL; // 链表尾指针置为NULL
        return t; // 返回第一个结点的地址（即链表头指针）
    }
    // 非空链表的情况
    node *p = h;
    // 让p指向最后一个结点
    while(p->next)
    {
        p = p->next;
    }
    p->next = t; // 让最后一个结点的指针域指向结点t
    t->next = NULL; // 链表尾指针置为NULL
    return h;  // 返回第一个结点的地址（即链表头指针）
    /********** End **********/
}

第2关：逆序构建线性表

任务描述

本关任务：补全 insertHead 函数，实现将一个结点插入到一个链表头部的功能。

相关知识

在介绍如何将一个结点插入到一个链表头部之前，我们先假设该链表头指针为 head，则 head 中存放着链表当前头结点的地址。

如果要将指针变量 t 指向的新结点插入到链表头部，其实只需要将原来的头结点的地址存入 t 指向结点的指针域（也就是让 t 指向结点的指针域指向原来的头结点），然后 t 指向的新结点就成了新的头结点了。那么，如何将原来的头结点的地址存入 t 指向结点的指针域？

t 指向结点的指针域可以用t->next访问，原来头结点的地址在 head 中，所以下面的语句可以实现这个功能：

t->next = head;

又由于新结点（ t 指向的结点）是新的头结点，其地址必须存入头指针 head 中，而 t 指向结点的地址存放在指针变量 t 中，所以下面的语句可以实现这个功能：

head = t;

参考答案 

#include "linearList.h"

node * insertHead(node *h, node *t)
{
    // 请在此添加代码，补全函数insertHead
    /********** Begin *********/
    t->next = h;
    return t;
    /********** End **********/
}

第3关：排序构建线性表

任务描述

本关任务：补全 insertSort 函数，实现将一个结点按结点数据 data 从小到大的顺序插入到一个有序链表中。根据插入结点 data 的大小，插入点可能是链表头、尾或者中间某个位置。

相关知识

实现本关任务的关键分为两个步骤：

  • 一是找到插入点；

  • 二是插入结点。

参考答案

#include "linearList.h"

node * insertSort(node *h, node *t)
{
    // 请在此添加代码，补全函数insertSort
    /********** Begin *********/
    node *p = NULL, *q = h;  // 定位第一个插入点：链首
    // 查找插入点
    while(q && q->data < t->data)
    {// 两个指针并行后移
        p = q;
        q = q->next;
    }
    // 插入链首
    if(p == NULL)
    {
        t->next = h;
        return t;
    }
    // 插入链尾
    if(q == NULL)
    {
        p->next = t;
        t->next = NULL;
    }
    // 插入p、q之间
    t->next = q;
    p->next = t;
    return h;
    /********** End **********/
}

第4关：查找元素

任务描述

本关任务：补全 search 函数，实现在一个链表中搜索包含指定数据的结点。如果链表中有多个结点包含该数据，则返回第一个。

相关知识

遍历列表元素，在线性表中查找特定元素是线性表的常用操作之一。由于链表结点都是动态内存分配得到的，在内存中不是连续存储，没法使用二分法之类的算法来实现信息检索，但可以使用顺序查找的方法。顺序查找需要遍历整个链表，逐个检查每个结点是否满足条件。

参考答案

#include "linearList.h"

node * search(node * h, int num)
{
    // 请在此添加代码，补全函数search
    /********** Begin *********/
    while(h)
    {// h为真，即h指向的结点存在
        if(h->data == num)
        {
              return h;
        } 
        h = h->next;  // 将该结点的指针域赋值给h，h就指向了下一个结点
    }
    return NULL; // 没找到包含num的结点
    /********** End **********/
}

第5关：删除指定位置的结点

任务描述

本关任务：补全 delAt 函数，实现根据指定位置删除链表中对应的结点。

相关知识

删除链表结点

线性表的结点是有序号的，包含 n 个结点的线性表从链头到链尾的结点序号分别为0、1、…… 、n−1。删除线性表指定位置的操作也是常用的功能。

结点的删除可以根据结点位置的不同分为三种情况：删除链首结点、删除链尾结点、删除中间结点。

回答以下几个问题，解决本关问题就不难了：

  • 删除链首结点后，原来序号为1的结点成为新的链首结点，链表头指针也应该存储该结点的地址，该结点的地址原来存放在哪？

  • 删除链尾结点后，原来序号为n−2的结点成为新的链尾结点，该结点的指针域也应该置为“NULL”，表示链表的结束。怎么访问序号为n−2的结点的指针域？

  • 删除中间结点只需要将其前面结点的指针域修改为其后面结点的地址即可。例如删除序号为i的结点，需要将序号为i−1的结点的指针域修改为序号为i+1的结点地址。怎么访问序号为i−1的结点的指针域？序号为i+1的结点地址存放在哪？

参考答案

#include "linearList.h"

node * delAt(node * h, int i)
{
    // 请在此添加代码，补全函数delAt
    /********** Begin *********/
    // 序号非法，不删除
    if(i<0)
    {
        return h;
    }
    node *p = NULL, *q = h; // 定位删除结点，试图让q指向要删除结点，p指向其前面的结点
    for(int k = 0; k < i; k++)
    {
        if(q->next == NULL) // 后面没有结点了，序号非法
        {
            return h;
  	}
        p = q;
        q = q->next;
    }
    if(p) // p指向的结点存在，不是删除首结点
    {
        // 删除q指向的结点，让p指向结点的指针域指向q的后续结点
        p->next = q->next;
        // 释放空间
        delete q;
        return h;
    }
    else // 删除首结点
    {
        h = q->next; // 下一个结点成了首结点
        // 释放空间
        delete q;
        return h;
    }
    /********** End **********/
}

第6关：删除包含特定数据的结点

任务描述

本关任务：补全 delHas 函数，实现删除链表中包含特定数据的结点，如果有多个这样的结点，只删除第一个。

删除链表的结点时，有时候不知道结点在哪，只知道结点数据的特征，如删除成绩低于60的学生结点、删除学号为20160903的学生等。

参考答案

#include "linearList.h"

node * delHas(node * h, int n)
{
    // 请在此添加代码，补全函数delHas
    /********** Begin *********/
    // 序号非法，不删除
    node *p = NULL, *q = h;  // p为要删除结点的前结点，q指向要删除结点
    while(q)
    {// h为真，即h指向的结点存在
        if(q->data == n)
            break; // 找到了
        if(q->next == NULL)  // 后面没有结点了，没有结点满足条件
            return h;  // 不删除，直接返回
        // 继续往后找，两个指针一起后移
        p = q;
        q = q->next;
    }
    // 删除q指向的结点
    if(p == NULL)  // 删除头结点
    {
        h = q->next;  // 下一个结点变成头结点
        delete q;  // 删除结点
        return h;
    }
    // 不是头结点
    p->next = q->next;  // 把q指向结点的指针域（q后面结点的地址）赋值给p指向结点的指针域
    return h;
    /********** End **********/
}

第7关：线性表长度

任务描述

本关任务：编写 listLength 函数来求线性表的长度。

相关知识

为了完成本关任务，你只需遍历线性表，并逐个对结点计数即可。

参考答案

#include "linearList.h"

int listLength(node * h)
{
    // 请在此添加代码，补全函数listLength
    /********** Begin *********/
    int n = 0;
    while(h)
    {
        n++;
        h = h->next;
    }
    return n;
    /********** End **********/
}

第8关：线性表应用一：栈

任务描述

本关任务：用前面已经实现的线性表来实现一个整数栈（栈里的数据是整数）。共需要补全三个函数（也是栈的基本功能）：判断栈空的 empty 函数、压栈的 push 函数和弹栈的 pop 函数。

相关知识

栈（ stack ）又名堆栈，是一种功能受限的线性表，具有先进后出的特性。

其限制为仅允许在线性表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。

  • 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；

  • 从一个栈删除元素又称作出栈、弹栈或退栈，它是把栈顶元素删除掉，使其下面的元素成为新的栈顶元素。

接下来首先声明结构类型：

// 定义结点结构
struct node
{
int data; // 数据域
node * next; // 指针域，指向下一个结点
};

typedef node * intStack; // 定义类型别名，intStack 即相当于 node*

定义 intStack 是为了使程序的可读性更好一些。因为本关是用线性表实现栈，而访问一个线性表其实只需要一个链表头指针就可以了，intStack 实际上就是node*类型，所以后面可以这样声明栈 sk 

intStack sk = NULL; // 声明栈 sk，并初始化为空栈（空线性表）

实际上 sk 就是一个node*类型的指针，用它可以访问一个线性表，也就可以看成一个栈了。

参考答案

#include "mstack.h"
// 函数empty：判断栈sk是否为空
// 参数：sk-栈
// 返回值：true-sk为空，false-sk不为空
bool empty(intStack sk)
{
    // 请在此添加代码，补全函数empty
    /********** Begin *********/
    return (listLength(sk) == 0);  // 链表长度为0，则栈为空
    /********** End **********/
}
// 函数pop：弹栈
// 参数：sk-栈，传引用，弹栈可能会改变sk的值
// 返回值：弹栈的弹出的整数，如果栈空，返回-1
int pop(intStack &sk)
{
    // 请在此添加代码，补全函数pop
    /********** Begin *********/
    if(empty(sk))  // 栈空，返回-1
        return -1;
    int n = sk->data;  // 获取栈顶结点(链首结点)的数据
    sk = delAt(sk,0);  // 删除首结点（弹栈，第一个结点出栈）
    return n;  // 返回弹栈数据
    /********** End **********/
}
// 函数push：压栈，将整数n压入栈sk中
// 参数：sk-栈，传引用，压栈会改变sk的值，n-要压栈的整数
// 返回值：无，采用链表实现栈，只要还有内存，压栈都会成功
void push(intStack &sk, int n)
{
    // 请在此添加代码，补全函数push
    /********** Begin *********/
    // 创建要压栈的结点
    node *p = new node;
    p->data = n;
    // 压栈（插入链首）
    sk = insertHead(sk,p);
    /********** End **********/
}

第9关：线性表应用二：队列

任务描述

本关任务：用前面已经实现的线性表来实现一个整数队列（队列里的数据是整数）。共需要补全三个函数（也是队列的基本功能）：判断队列空的 queueEmpty 函数、入列的 enQueue 函数和出列的 deQueue 函数。

相关知识

队列是一种功能受限的线性表，具有先进先出的特性。队列仅允许从一头出列（这一头称为队列头），从另外一头入列（队列尾）。

  • 入列操作是将结点插入到队列尾（该结点称为新的队列尾）；

  • 出列操作是从队列头删除头结点，并获取删除节点的数据（原头结点的后继结点为新的头结点）。

接下来首先声明结构类型：

// 定义结点结构
struct node
{
int data; // 数据域
node * next; // 指针域，指向下一个结点
};

typedef node * intQueue; // 定义类型别名，intQueue 即相当于 node*

定义 intQueue 是为了使程序的可读性更好一些。因为本关是用线性表实现队列，而访问一个线性表其实只需要一个链表头指针就可以了，intQueue 实际上就是node*类型，所以后面可以这样声明队列 iq 

intQueue iq = NULL; // 声明队列 iq，并初始化为空队列（空线性表）

实际上 iq 就是一个node*类型的指针，用它可以访问一个线性表，也就可以看成一个队列。

参考答案

#include "mqueue.h"

// 函数queueEmpty：判断队列iq是否为空
// 参数：iq-整数队列
// 返回值：true-队列iq为空，false-iq不为空
bool queueEmpty(intQueue iq)
{
    // 请在此添加代码，补全函数queueEmpty
    /********** Begin *********/ 
    return (iq==NULL);  // iq为NULL，则队列为空
    /********** End **********/
}
// 函数enQueue：将整数num入列到iq
// 参数：iq-整数队列，传引用，入列有可能改变队列头指针，num-入列的整数
// 返回值：无，只要还有内存，入列总会成功
void enQueue(intQueue &iq, int num)
{
    // 请在此添加代码，补全函数enQueue
    /********** Begin *********/
    // 准备结点
    node *t=new node;
    t->data=num;
    t->next=NULL;
    // 结点插入到尾部
    iq = insertTail(iq,t);
    /********** End **********/
}
// 函数deQueue：出列
// 参数：iq-整数队列，传引用，出列有可能改变队列头指针
// 返回值：出列结点的数据，如果队列为空，返回-1
int deQueue(intQueue &iq)
{
    // 请在此添加代码，补全函数deQueue
    /********** Begin *********/
    if(queueEmpty(iq))
        return -1;
    // 获取队列头结点的数据
    int n = iq->data;
    // 删除队列头结点（出列）
    iq = delAt(iq,0);
    // 返回出列数据
    return n;
    /********** End **********/
}

第10关：线性表应用三：集合

任务描述

本关任务：使用线性表实现集合的表示及操作。具体需要补全三个函数：计算集合并集的 unionSet 函数、计算集合交集的 intersection 函数和向集合中添加元素的 addElement 函数。

相关知识

集合

集合是数学中一个基本概念，它是集合论的研究对象。朴素集合论中，集合的定义就是“一堆东西”，集合里的“东西”，称为元素。

下面介绍几个集合的知识点：

  • 集合中的元素是无序的，对于任意的集合S1和S2，S1=S2当且仅当对于任意的对象a，都有若a∈S1，则a∈S2；若a∈S2，则a∈S1；

  • 集合中的元素互不相同，空集合是没有任何元素的集合；

  • 集合的并集定义为：A∪B=x∣x∈A或x∈B。例如，A={1，3，5}，B={1，2，5} ，则A∪B= {1，2，3，5} ；

  • 集合的交集定义为：A∩B=x∣x∈A且x∈B。例如， A= {1，3，5}，B={1，2，5} ，则A∩B= {1，5} 。

接下来首先声明结构类型：

// 定义结点结构
struct node
{
int data; // 数据域
node * next; // 指针域，指向下一个结点
};

typedef node * intSet; // 定义类型别名，intSet 即相当于 node*

上述结构类型的声明中定义 intSet 是为了使程序的可读性更好一些。因为本关是用线性表实现集合，而访问一个线性表其实只需要一个链表头指针就可以了， intSet 实际上就是node*类型，所以后面可以这样声明集合 a 

intSet a=NULL; // 声明集合 a，并初始化为空集合（空线性表）

参考答案 

#include "mset.h"

// 函数unionSet：求集合a和b的并集
// 参数：a-集合，b-集合
// 返回值：集合（集合a和b的并集）
intSet unionSet(intSet a, intSet b)
{
    // 请在此添加代码，补全函数unionSet
    /********** Begin *********/
    // 准备空集合
    intSet c=NULL;
    // 把a中每一个元素加入c中
    node *p=a;
    while(p)
    {
        addElement(c,p->data);
        p=p->next;
    }
    // 把b中每一个元素加入c中
    p=b;
    while(p)
    {
        addElement(c,p->data);
        p=p->next;
    }
    return c;
    /********** End **********/
}
// 函数intersection：求集合a和b的交集
// 参数：a-集合，b-集合
// 返回值：集合（集合a和b的交集）
intSet intersection(intSet a, intSet b)
{
    // 请在此添加代码，补全函数intersection
    /********** Begin *********/
    // 准备空集合
    intSet c=NULL;
    // 查看a中每一个元素
    node *p=a;
    while(p)
    {
        if(search(b,p->data))
        {// 也在b中，则选入集合c
            addElement(c,p->data);
        }
        p=p->next;
    }
    return c;
    /********** End **********/
}
// 函数addElement：在集合is中增加元素num
// 参数：is-集合，num-要增加的元素
// 返回值：无
void addElement(intSet &is, int num)
{
    // 请在此添加代码，补全函数addElement
    /********** Begin *********/
    // 首先确认num是否在is中
    node *p=search(is,num);
    if(p!=NULL)
        return;
    // 准备结点
    p=new node;
    p->data = num;
    p->next = NULL;
    is = insertHead(is,p);
    /********** End **********/
}

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

CC

c

链表

数据结构

1024程序员节

Educoder C&C++线性表实训 的相关文章

随机推荐

  • 理解智能合约

    链客 专为开发者而生 有问必答 此文章来自区块链技术社区 未经允许拒绝转载 0x00 前言 理解智能合约对理解区块链技术至关重要 我们先来看下什么是智能合约 智能合约是 1990s 年代由尼克萨博提出的理念 几乎与互联网同龄 由于缺少可信的

  • 用Rust实现23种设计模式之 模板方法模式

    关注我 学习Rust不迷路 模板方法模式是一种行为型设计模式 它定义了一个算法的骨架 将一些步骤的实现延迟到子类中 以下是模板方法模式的优点和使用场景 优点 提高代码复用性 模板方法模式通过将算法的通用部分放在父类中 可以在子类中复用这些通

  • 测试用例的设计方法及案例

    测试用例的设计方法 一 软件测试的生命周期 软件测试的流程是什么 二 如何描述一个BUG 三 测试用例的设计方法 3 1等价类 3 2边界值法 3 3因果图法 3 4场景设计法 3 5正交排列法 3 6错误猜测法 一 软件测试的生命周期 软

  • Microsoft Dynamics产品梳理

    目录 前言 一 Dynamics 365 Sales Customer Service Field Service Finance Operations 二 Dynamics GP Great Plains 三 Dynamics NAV N

  • Python3 goto 语句的使用

    熟悉 C 语言的小伙伴一定对 goto 语句不陌生 它可以在代码之间随意的跳来跳去 但是好多老鸟都告诫大家 不要使用 goto 因为 goto 会使你的代码逻辑变的极其混乱 但是有时候我们不得不用它 因为它太高效了 比如进入循环内部深层一个

  • 学生管理系统C语言

    include

  • Win10 隐藏远程桌面，连接栏

    https www cnblogs com tuhong p 13307579 html 快捷键 Ctrl Alt Home

  • Django 省、市、区 三级联动 及数据库的地址添加 !!!

    应用场景 淘宝 京东 等需要地址的地方 Models py模型 from django db import models Create your models here class Area models Model name models

  • Redis可视化工具RedisInsight

    今天是老苏居家隔离的第 39 天 周五抗原 周六 周日 周一每天两次抗原 上午一次 下午一次 没完没了的捅鼻子 感觉都要捅出鼻炎了 虽然小区早就是防范区了 但是一直处于提级管理中 还是不能出小区 也看不到任何松动的迹象 最近几天都在传 一人

  • R reason ‘拒绝访问‘的解决方案

    Win11系统 安装rms的时候报错 Error in loadNamespace j lt i 1L c lib loc libPaths versionCheck vI j namespace Matrix 1 5 4 1 is alr

  • 使用Thinkphp5.0 中 {include file="index/left" /} 引入模板 影响样式

    在使用Thinkphp 5 0框架开发后台的时候 需要在模板中引用公共头部 我使用 include file index header 的方式引用了公共头部 引用之后发现头部和页面顶端之间出现了间距 未引用之前 头部和页面顶端是没有间距的

  • Azure文件同步服务的创建和配置

    将Azure FileShare share1同步到Server Endpoint 在这没法添加 只能管理服务 选择 Create a resource 查找 azure file sync 注意 选择的Location 一定要与File服

  • PLY文件格式及其MATLAB读写操作

    PLY是一种电脑档案格式 全名为多边形档案 Polygon File Format 或 斯坦福三角形档案 Stanford Triangle Format 史丹佛大学的 The Digital Michelangelo Project计划采

  • Arduino实验三：伺服马达

    目录 前言 1 伺服马达 1 1 相关参数 1 2实物图 1 3连接线路图 1 4程序代码 1 5运行结果 前言 伺服马达和直流马达的区别 伺服马达有3条接入线 在输入信号的控制下 能够转动特定角度 其中三条线中 红色线接正极 棕色线接地

  • App常见内存泄漏以及解决方法

    如果是想认真学习的话 请先不要看以下内容 此记录只是为加深记忆 可能会有错误的地方 以免有误导 学习转载链接 https blog csdn net u014674558 article details 62234008 App常见内存泄漏

  • python怎么实现类似#define宏定义

    我怎么了 怎么突然问出这个问题 一时还认真的点进了论坛 面壁思过一下 python是解释性语言 不需要编译 define是预编译阶段起作用的 python没得必要 在c语言中 define在调试或者多平台兼容的时候很有用 特别是 defin

  • [内核文档系列] NMI 看门狗

    内核文档系列 NMI 看门狗 秦白衣 qinchenggang sict ac cn X86和X86 64体系结构均支持NMI看门狗 你的系统是不是会经常被锁住 Lock up 直至解锁 系统不再响应键盘 你希望帮助我们解决类似的问题吗 如

  • AttributeError: 'numpy.dtype' object has no attribute 'base_dtype'

    AttributeError numpy dtype object has no attribute base dtype 这个错误其实是有说keras版本有点高的问题 我调低了 Keras 2 0 2 具体他有没有影响 我没有验证 但是下

  • 机器学习K-均值——nonzero(clusterAssment[冒号,0].A==cent的一步步操作演示，看完你就明白了

    先准备测试数据 如下 上面都是准备数据 下面才是一步步的告诉你怎么生成我们要的数据 原文链接 https blog csdn net xinjieyuan article details 81477120

  • Educoder C&C++线性表实训

    目录 第1关 顺序构建线性表 第2关 逆序构建线性表 第3关 排序构建线性表 第4关 查找元素 第5关 删除指定位置的结点 第6关 删除包含特定数据的结点 第7关 线性表长度 第8关 线性表应用一 栈 第9关 线性表应用二 队列 第10关

热门标签