【Educoder作业】C&C++线性表实训

这篇具有很好参考价值的文章主要介绍了【Educoder作业】C&C++线性表实训。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【Educoder作业】C&C++线性表实训

第一次接触链表的话,可能会有疑惑。疑惑在于它到底比数组强在哪里。写完这次实训可能就会感受到,或者写了这10个题还是没有头绪,本篇结尾我们就稍微聊一聊。

T1 顺序构建线性表

这个题可以说是定了整个实训的基调,结构体里是包含了一个本身的数据 d a t a data data和一个指针 n e x t next next,我们就是用这两个东西来构建链表的。
同时,我们默认:最后一个元素的 n e x t next next N U L L NULL NULL

#include "linearList.h"

node *insertTail(node *h, node *t)
{
    // 请在此添加代码,补全函数insertTail
    /********** Begin *********/
	node *p = h;
	if (h == NULL) return t;
	while (p -> next != NULL) p = p -> next;
	p -> next = t;
	return h;

    /********** End **********/
}

T2 逆序构建线性表

这是容易的,因为我们构建的是单向链表。

#include "linearList.h"

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

    /********** End **********/
}

T3 排序构建线性表

想起来是比较容易的,我们考虑最后的情形:找到当前数据存放的位置,然后把当前数据塞进这个位置里。
那么,我们就同时需要 p → n e x t p\rightarrow next pnext p p p,在写 w h i l e while while的时候也就会麻烦一点。

#include "linearList.h"

node * insertSort(node *h, node *t)
{
    // 请在此添加代码,补全函数insertSort
    /********** Begin *********/
	node *p = h;
	if (h == NULL) return t;
	if (t -> data <= h -> data) return insertHead(h, t);
	if (h -> next == NULL) return insertTail(h, t);
	bool flag = false;
	while (p -> next -> data <= t -> data) {
		if (p -> next -> next == NULL) {
			flag = true;
			break;
		}
		p = p -> next;
	}
	if (flag) return insertTail(h, t);
	t -> next = p -> next;
	p -> next = t;
	return h;
    /********** End **********/
}

T4 查找元素

其实,知道了 T 3 T_3 T3怎么做,剩下的都比较容易了。
只需要从表头开始顺序枚举链表,然后查找即可。

#include "linearList.h"

node * search(node * h, int num)
{
    // 请在此添加代码,补全函数search
    /********** Begin *********/
	node *p = h;
	if (h == NULL) return NULL;
	while (p != NULL) {
		if (p -> data == num) return p;
		p = p -> next;
	}
	return NULL;
    /********** End **********/
}

T5 删除指定位置的结点

由于是删除指定位置,所以最后一步的情形一定是找到了这么一个 p p p,然后有 p → n e x t = p → n e x t → n e x t p\rightarrow next=p\rightarrow next\rightarrow next pnext=pnextnext,所以我们的 w h i l e while while也就会更复杂一点。

#include "linearList.h"

node * delAt(node * h, int i)
{
    // 请在此添加代码,补全函数delAt
    /********** Begin *********/
	node *p = h;
	if (!i) return h -> next;
	int cnt = 1;
	while (p -> next -> next != NULL) {
		if (cnt == i) {
			p -> next = p -> next -> next;
			return h;
		}
		cnt ++ ;
		p = p -> next;
	}
	p -> next = NULL;
	return h;
    /********** End **********/
}

T6 删除包含特定数据的结点

凡是这种删除的都会复杂一点,和 T 5 T_5 T5一样, w h i l e while while的判断会比较复杂。

#include "linearList.h"

node * delHas(node * h, int n)
{
    // 请在此添加代码,补全函数delHas
    /********** Begin *********/
	if (h -> data == n) return h -> next;
	node *p = h;
	while (p -> next -> next != NULL) {
		if (p -> next -> data == n) {
			p -> next = p -> next -> next;
			return h;
		}
		p = p -> next;
	}
	if (p -> next -> data == n) {
		p -> next = NULL;
		return h;
	}

    /********** End **********/
}

T7 线性表长度

这个就比较容易了,从表头开始遍历然后计数即可。

#include "linearList.h"

int listLength(node * h)
{
    // 请在此添加代码,补全函数listLength
    /********** Begin *********/
	int ans = 0;
	while (h != NULL) ans ++ , h = h -> next;
	return ans;

    /********** End **********/
}

T8 线性表应用一:栈

栈是一种数据结构,特点是 F I L O ( F i r s t   i n   L a s t   o u t ) FILO(First\ in\ Last\ out) FILO(First in Last out)
但是用链表实现栈显然是没什么必要的,篇尾我们会讨论这个问题。

#include "mstack.h"
// 函数empty:判断栈sk是否为空
// 参数:sk-栈
// 返回值:true-sk为空,false-sk不为空
bool empty(intStack sk)
{
    // 请在此添加代码,补全函数empty
    /********** Begin *********/
	return sk == NULL ? true : false;


    /********** End **********/
}
// 函数pop:弹栈
// 参数:sk-栈,传引用,弹栈可能会改变sk的值
// 返回值:弹栈的弹出的整数,如果栈空,返回-1
int pop(intStack &sk)
{
    // 请在此添加代码,补全函数pop
    /********** Begin *********/
	intStack p = sk;
	if (empty(sk)) return 0;
	if (p -> next == NULL) {
		int re = p -> data;
		sk = NULL;
		return re;
	}
	while (p -> next -> next != NULL) p = p -> next;
	int re = p -> next -> data;
	p -> next = NULL;
	return re;


    /********** End **********/
}
// 函数push:压栈,将整数n压入栈sk中
// 参数:sk-栈,传引用,压栈会改变sk的值,n-要压栈的整数
// 返回值:无,采用链表实现栈,只要还有内存,压栈都会成功
void push(intStack &sk, int n)
{
    // 请在此添加代码,补全函数push
    /********** Begin *********/
	intStack p = sk;
	if (empty(sk)) {
		sk = new node;
		sk -> data = n;
		sk -> next = NULL;
		return;
	}
	while (p -> next != NULL) p = p -> next;
	p -> next = new node;
	p -> next -> next = NULL;
	p -> next -> data = n;
    /********** End **********/
}

T9 线性表应用二:队列

队列的特点是 F I F O ( F i r s t   i n   F i r s t   o u t ) FIFO(First\ in\ First\ out) FIFO(First in First out)
实现起来用前面的函数,显然也是容易的。

#include "mqueue.h"

// 函数queueEmpty:判断队列iq是否为空
// 参数:iq-整数队列
// 返回值:true-队列iq为空,false-iq不为空
bool queueEmpty(intQueue iq)
{
    // 请在此添加代码,补全函数queueEmpty
    /********** Begin *********/ 
	return iq == NULL ? true : false;


    /********** 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 re = iq -> data;
	iq = delAt(iq, 0);
	return re;


    /********** End **********/
}

T10 线性表应用三:集合

集合是个很强大的数据结构,在 C + + C++ C++ S T L STL STL里也有集合,只不过那里的集合用的是红黑平衡树实现的,是一个很强大的数据结构。
这里的集合就很简单了,只能保证有序且不能重复,多余的操作复杂度都不能保证。

#include "mset.h"

// 函数unionSet:求集合a和b的并集
// 参数:a-集合,b-集合
// 返回值:集合(集合a和b的并集)
intSet unionSet(intSet a, intSet b)
{
    // 请在此添加代码,补全函数unionSet
    /********** Begin *********/
	node *re = NULL;
	node *p[2] = {a, b};
	// printList(p[0]), printList(p[1]);
	for (int i = 0; i < 2; i ++ ) {
		while (p[i] != NULL) {
			if (search(re, p[i] -> data) == NULL) {
				node *mdl = new node;
				mdl -> next = NULL, mdl -> data = p[i] -> data;
				re = insertSort(re, mdl);
			}
			p[i] = p[i] -> next;
		}
	}
	return re;
 
    /********** End **********/
}
// 函数intersection:求集合a和b的交集
// 参数:a-集合,b-集合
// 返回值:集合(集合a和b的交集)
intSet intersection(intSet a, intSet b)
{
    // 请在此添加代码,补全函数intersection
    /********** Begin *********/
	node *re = NULL;
	node *p = a;
	while (p != NULL) {
		if ((search(b, p -> data) != NULL) && (search(re, p -> data) == NULL)) {
			node *mdl = new node;
			mdl -> data = p -> data, mdl -> next = NULL;
			re = insertSort(re, mdl);
		}
		p = p -> next;
	}
	return re;
    /********** End **********/
}
// 函数addElement:在集合is中增加元素num
// 参数:is-集合,num-要增加的元素
// 返回值:无
void addElement(intSet &is, int num)
{
    // 请在此添加代码,补全函数addElement
    /********** Begin *********/
	node *t = new node;
	t -> next = NULL, t -> data = num;
	if (search(is, num) == NULL) is = insertSort(is, t);


    /********** End **********/
}

写完了整个实训,我们来聊一聊链表。很多人也跟笔者探讨过这个问题,观点大同小异——不理解这个链表有什么用。
这就涉及到复杂度的问题,这个我之后单独出一篇 B l o g Blog Blog聊一聊。
比如说,我们想在数组的某个特定位置访问第 i i i号元素,直接访问 A r r a y i Array_i Arrayi即可,是瞬间完成的,也就是 O ( 1 ) O(1) O(1)的。
但是链表不行,他需要从表头开始计数,直到计数器到达了 i i i,如果每次都是查找最后一个元素,那么这个操作就和表的长度有关,我们称之为 O ( n ) O(n) O(n)的。
现在,数组的表现是优秀的多的。
这时我们考虑插入往指定位置插入一个元素,数组的话需要把这个元素后边的每个元素都向后挪一个位置,复杂度就是 O ( n ) O(n) O(n)的,但是链表只需要改变他前一个元素的指针就可以完成这个操作。
这就是链表的意义,某些操作用链表完成会简单很多。
还有很多,比如动态分配空间这个事儿,链表也是很容易就能做到的。 C + + C++ C++里有一个 S T L STL STL叫动态数组 v e c t o r vector vector,使用的时候就是一个可以自动分配空间的数组,它的内部实现就是用指针+链表的思想实现的。
看到这,可能会有疑问:有没有一种数据结构能兼顾数组和链表的有点呢?既可以短时间访问元素,也可以短时间插入、删除元素?
当然是可以的,一些强大的数据结构很容易做到, s p l a y splay splay和非旋转 T r e a p Treap Treap为代表的平衡树就可以。
这里我们介绍容易理解的块状链表。
我们将一个长度为 n n n的数组分为 n \sqrt n n 个连续的块,显然每个块里都有 n \sqrt n n 个元素。每个块内是数组,块与块之间用链表的思想连接起来,这个数据结构就是块状链表。
比如查询:我们只需要从表头开始,一次跳 n \sqrt n n 个元素,如果发现了某个元素在某个块里,因为块是数组直接 O ( 1 ) O(1) O(1)即可,复杂度就是整体链表访问的复杂度 O ( n ) O(\sqrt n) O(n );比如插入一个元素,只需要找到了对应的块后,挪动块内的元素即可。因为在某个块里的插入一个元素,并不会影响其它块,因为块与块之间只链表连接的,所以复杂度也是 O ( n ) O(\sqrt n) O(n )的。
就聊这么多,其实每个数据结构总有它大放异彩的地方,即使它的作用只是引出一个更强大的数据结构。
写在篇尾不写在篇头,意义是读者又需要自取,大多数是不喜欢看这些引申东西的(小声文章来源地址https://www.toymoban.com/news/detail-564320.html

到了这里,关于【Educoder作业】C&C++线性表实训的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Educoder作业】C&C++结构实训

    学好结构体是学好对象的基础。 T1 有理数化简 知道结构体是干嘛的就能做了,注意一些地方的特判即可。 T2 有理数加法 没啥区别啊感觉,注意求 g c d gcd g c d 别弄错了,实在不行咱就直接用 C + + C++ C + + 里自带的。 T3 有理数平均数 这个题我们处理好 g c d gcd g c d 的同时,搞

    2024年02月11日
    浏览(42)
  • 【Educoder作业】C&C++数组实训

    数组是很好用的。作为一个最基本的数据结构,数组是构成高级结构的基础。简单点的比如列表的next和head指针,桶的下标,栈;复杂点的比如说线段树的节点,KD树的平面,我们都需要数组进行实现。 T1 销售波动统计 这个题目显然是容易的,注意不要从 i = = 0 i==0 i = = 0 开始

    2024年02月05日
    浏览(38)
  • CSS--头歌(educoder)实训作业题目及答案

    目录 CSS——基础知识 第1关: 初识CSS:丰富多彩的网页样式 第2关: CSS样式引入方式 CSS——基础选择器 第1关: CSS 元素选择器 第2关: CSS 类选择器 第3关: CSS id选择器 CSS——文本与字体样式 第1关: 字体颜色、类型与大小 第2关: 字体粗细与风格 第3关: 文本装饰与文本布局 CSS——

    2024年04月15日
    浏览(138)
  • JavaScript上部分--头歌(educoder)实训作业题目及答案

      目录 JS简介 第1关: JavaScript基础入门 第2关: JavaScript 与 HTML 第3关: JavaScript 变量 JS 数据类型 第1关: JavaScript 数据类型介绍 第2关: JavaScript 数据类型转换 JS运算符 第1关: 算术运算符 第2关: 比较和逻辑运算符 第3关: 条件和赋值运算符 第4关: 运算符的优先级和结合性 JS对象 第

    2024年02月08日
    浏览(34)
  • JavaScript下部分--头歌(educoder)实训作业题目及答案

    目录  JSON 第1关: JSON对象 第2关: JSON数组 第3关: JSON字符串 Math、日期和异常处理 第1关: Math类 第2关: Date类 第3关: JavaScript错误 HTML DOM——文档元素的操作(一) 第1关: 通过id获取文档元素 第2关: 通过类名获取文档元素 第3关: 通过标签名获取文档元素 第4关: html5中获取元素的

    2023年04月26日
    浏览(42)
  • JavaScript上部分--头歌(educoder)实训作业题目及答案 JS简介

      目录 JS简介 第1关: JavaScript基础入门 第2关: JavaScript 与 HTML 第3关: JavaScript 变量 JS 数据类型 第1关: JavaScript 数据类型介绍 第2关: JavaScript 数据类型转换 JS运算符 第1关: 算术运算符 第2关: 比较和逻辑运算符 第3关: 条件和赋值运算符 第4关: 运算符的优先级和结合性 JS对象 第

    2023年04月22日
    浏览(166)
  • 头歌(educoder)实训作业题目及答案分享 ——1-4 Java入门 - 分支结构

    📜个人简介 :  作者简介:大家好,我是Passenger.n✌️  支持一下:点赞👍+收藏🌟+留言📪 📣 系列专栏:java基础🍁 ✉️格言:花有重开日,人无再少年!🌞 万事开头难,既然迈开了这一步,那就坚持走下去! 这是我的第一篇博客,希望萌新看了有收获,大佬看了给指

    2024年02月06日
    浏览(105)
  • 头歌(educoder)实训作业题目及答案分享 ——1-7 Java入门-分支与循环练习

    📜个人简介 :  作者简介:大家好,我是Passenger.n✌️  支持一下:点赞👍+收藏🌟+留言📪 📣 系列专栏:java基础🍁 ✉️格言:花有重开日,人无再少年!🌞 万事开头难,既然迈开了这一步,那就坚持走下去! 这是我的第一篇博客,希望萌新看了有收获,大佬看了给指

    2024年02月04日
    浏览(83)
  • 头歌(educoder)实训作业题目及答案分享 ——1-3 Java入门 - 运算符和表达式

    📜个人简介 :  作者简介:大家好,我是Passenger.n  支持一下:点赞👍+收藏🌟+留言📪 📣 系列专栏:java基础🍁 ✉️格言:花有重开日,人无再少年!🌞 万事开头难,既然迈开了这一步,那就坚持走下去! 这是我新的一篇博客,希望萌新看了有收获,大佬看了给指路😝

    2024年02月07日
    浏览(141)
  • 【Educoder离散数学实训】关系基础

    题有点多,能聊的不多。有些题还是比较有价值的 就单独说几个题,代码放在最后。所有函数都改成自己写的了,没准比答案给的好读一点? T1 求给定集合的对角线关系(diagonal relation) 我觉得如果卡住的话,第一关会是一个大坎。 因为我们并不知道他到底在说啥,于是我

    2024年02月07日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包