数据结构与算法(C#)入门 --- 线性表

时间:2024-01-14 19:37:14

线性表:

线性表是最简单,最基本,最常用的数据结构。线性表中的数据元素之间存在一对一的关系。即:除了第一个元素,其他元素前面有且只有一个元素;除了最后一个元素,其他元素后面有且只有一个元素。生活中的例子:糖葫芦。

数据结构与算法(C#)入门 --- 线性表

(图片来自网络,侵删)

分类:

根据数据存储结构的不同,大体上可以分为:顺序表,链式表。

顺序表:

在内存中用一块地址连续的空间存放线性表的数据元素,因此查找元素时非常方便。增加或删除元素时,需要移动剩下的元素。

链式表:

不强求用连续的内存空间存放线性表的数据元素。除了基本的数据元素,还有一个标识用于保存逻辑上相邻元素的地址信息。增加或删除元素时,不需要移动元素。

数据结构与算法(C#)入门 --- 线性表

如图所示,(node1-next)是头节点,(node4-next)是尾节点。node1的next指向node2,node2的next指向node3,node3的next指向node4。

LeetCode 练习:

LeetCode 是一个在线的刷题网站,建议上英文网站 https://leetcode.com/  点击 Problems,在右侧的 Topics 下选择 Linked List。这一步是依据 Topic 选择相应的题目,Linked List 代表了链表。下面我们做几道 Easy 类型的题目巩固一下基础。给出的示例代码不一定是最优解,请做完后阅读Discuss,参考别人的答案。

题目:876.Middle of the Linked List

描述:给定一个非空线性表,返回中间的节点开始的列表。如果中间节点有两个,返回第二个节点后开始的列表。

例如:给定 [1,2,3,4,5],返回 [3,4,5];给定 [1,2,3,4,5,6],返回 [4,5,6]

说明:第一次做题请选择对应的语言。如下图所示,选择了 C#:

数据结构与算法(C#)入门 --- 线性表

思考:

根据示例代码,目的是返回中间的节点。提供的ListNode结构,只有值val与下一个节点next,没有位置标识。

因此我们可以创建一个List集合,遍历head,放入List,然后直接返回中间的节点。参考代码如下:

数据结构与算法(C#)入门 --- 线性表

一般代码写完后,点击下面的 Run Code,初步检查没错后再点击 Submit

数据结构与算法(C#)入门 --- 线性表

代码的运行结果如下:

数据结构与算法(C#)入门 --- 线性表

可见运行速度还是可以的,只是使用的内存稍高一些。

题目:206. Reverse Linked List

描述:链表反转。

思路:相邻对象交换。参考代码如下:

数据结构与算法(C#)入门 --- 线性表