Educoder C&C++线性表实训

目录

第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; // 链表尾指针置为NULLreturn t; // 返回第一个结点的地址（即链表头指针）}// 非空链表的情况node *p = h;// 让p指向最后一个结点while(p->next){p = p->next;}p->next = t; // 让最后一个结点的指针域指向结点tt->next = NULL; // 链表尾指针置为NULLreturn 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 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 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的值// 返回值：弹栈的弹出的整数，如果栈空，返回-1int pop(intStack &sk){// 请在此添加代码，补全函数pop/********** Begin *********/if(empty(sk))// 栈空，返回-1return -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-整数队列，传引用，出列有可能改变队列头指针// 返回值：出列结点的数据，如果队列为空，返回-1int 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中，则选入集合caddElement(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 **********/}