数据结构基础——线性表

数据结构基础——线性表

小颜同学 Lv4

前言:
数据结构的概念:数据结构是指数据对象机器相互关系的构造方法。

数据结构S可以用一个二元组表示:S=(D,R)

D是数据结构中的数据的非空有限集合,R是定义在D上的关系的非空有限集合。

数据的存储结构:在数据结构中,结点及结点间的相互关系称为数据的逻辑结构。

数据结构可以按照逻辑结构的不同分为两大类:线性结构和非线性结构。其中非线性结构又可分为树形结构和图结构,而树形结构又可以分为树结构和二叉树结构。

1、常用数据结构

数组(静态数组、动态数组)、线性表、链表(单向链表、双向链表、循环链表)、队列、栈、树(二叉树、查找树、平衡树、线索树、堆)、图等的定义、存储和操作。Hash(存储地址计算,冲突处理)。

2、常用算法:

排序算法、查找算法、数值计算方法、字符串处理方法、数据压缩算法、递归算法、图的相关算法。算法与数据结构的关系、算法效率、算法设计、算法描述(流程图、伪代码、决策表)、算法的复杂性。

1.线性表的概念

线性表是最简单、最常用的一种数据结构,它是由相同类型的节点组成的有限序列

一个由n个结点a0,a1,…,an–1组成的线性表可记为(a0,a1,…,an–1)。

线性表的结点个数为线性表的长度, 长度为0的线性表称为空表

对于非空线性表,a0是线性表的第一个结点,an–1是线性表的最后一个结点。

线性表的结点构成一个序列,对序列中两相邻结点ai和ai+1,称ai是ai+1的前驱结点,ai+1是ai的后继结点。其中a0没有前驱结点,an–1没有后继结点。

线性表中结点之间的关系可由结点在线性表中的位置确定,通常用(ai,ai+1)(0≤i≤n–2)表示两个结点之间的先后关系。例如,如果两个线性表有相同的数据结点,但它们的结点在线性表中出现的顺序不同,则它们是两个不同的线性表。

线性表的结点可由若干成分组成,其中能唯一标识该结点的成分称为关键字,或简称键。

2.线性表的基本运算

线性表包含的结点个数可以动态增加或减少,可以在任何位置插入或删除结点。线性表常用的运算可分成几类,每类有若干种运算。

1)查找运算

在线性表中查找具有给定键值的结点。

2)插入运算

在线性表的第i(0≤i≤n–1)个结点的前面或后面插入一个新结点。

3)删除运算

删除线性表的第i(0≤i≤n–1)个结点。

4)其他运算

统计线性表中结点的个数;

输出线性表各结点的值;

复制线性表;

线性表分拆;

线性表合并;

线性表排序;

按某种规则整理线性表。

3.线性表的存储

线性表常用的存储方式有顺序存储链接存储

1)顺序存储

顺序存储是最简单的存储方式,通常用一个数组,从数组的第一个元素开始,将线性表的结点依次存储在数组中,即线性表的第i个结点存储在数组的第i(0≤i≤n–1)个元素中,用数组元素的顺序存储来体现线性表中结点的先后次序关系。

优点

能随机存储线性表中的任何一个结点。

缺点

1.数组的大小通常是固定的,不利于任意增加或减少线性表的结点个数

2.插入和删除线性表的结点时,要移动数组的其他元素,操作复杂。

2)链接存储

链接存储是用链表存储线性表(链表),最简单的是用单向链表,即从链表的第一个结点开始,将线性表的结点依次存储在链表的各结点中。链表的每个结点不但要存储线性表结点的信息,还要用一个域存储其后继结点的指针。单向链表通过链接指针来体现线性表中结点的先后次序关系。

优点

1.线性表每个结点的实际存储位置是任意的。

2.只要改变链表有关结点的后继指针就能完成插入或删除的操作,不需移动任何表单元。

缺点

1.每个结点增加了一个后继指针成分,要花费更多的存储空间。

2.不便随机访问线性表的任一结点。

4.线性表上的查找

线性表上的查找运算是指在线性表中找某个键值的结点。

根据线性表中的存储形式和线性表本身的性质差异,有多种查找算法,例如顺序查找、二分法查找、分块查找、散列查找等。其中二分法查找要求线性表是一个有序序列。

5.在线性表中插入新结点

1)顺序存储

设线性表结点的类型为整型,插入之前有n个结点,把值为x的新结点插在线性表的第i(0≤i≤n)个位置上。

完成插入主要有以下步骤:

1.检查插入要求的有关参数的合理性;

2.把原来的第n–1个结点至第i个结点依次往后移一个数组元素位置;

3.把新结点放在第i个位置上;

4.修正线性表的结点个数。

5.在具有n个结点的线性表上插入新结点,其时间主要花费在移动结点的循环上。若插入任一位置的概率相等,则在顺序存储线性表中插入一个新结点,平均移动次数为n/2

2)链接存储

在链接存储线性表中插入一个键值为x的新结点,分为以下4种情况:

1.在某指针p所指结点之后插入;

2.插在首结点之前,使待插入结点成为新的首结点;

3.接在线性表的末尾;

4.在有序链表中插入,使新的线性表仍然有序。

6.删除线性表的结点

1)顺序存储

在有n个结点的线性表中,删除第i(0≤i≤n–1)个结点。删除时应将第i+1个结点至第n–1个结点依次向前移一个数组元素位置,共移动n–i–1个结点。完成删除主要有以下几个步骤:

1.检查删除要求的有关参数的合理性;

2.把原来第i+1个表元至第n–1个结点依次向前移一个数组元素位置;修正线性表表元个数。

3.在具有n个结点的线性表上删除结点,其时间主要花费在移动表元的循环上。若删除任一表元的概率相等,则在顺序存储线性表中删除一个结点,平均移动次数为(n-1)/2.

2)链接存储

对于链表上删除指定的结点的删除运算,需要考虑几种情况:

1.链表为空链表,不执行删除操作;

2.要删除的结点恰为链表的首结点,应将链表头指针改为指向原首结点的后继指点;

3.其他情况,先要在链表中寻找要删除的结点,从链表首结点开始顺序寻找。若找到,执行删除操作,若直至链表末尾没有指定值的结点,则不执行删除操作。

完成删除由以下几个步骤组成:

如链表为空链表,则不执行删除操作;

若链表的首结点的值为指定值,更改链表的头指针为指向首结点的后继结点;

在链表中寻找指定值的结点;

将找到的结点删除。

  • 标题: 数据结构基础——线性表
  • 作者: 小颜同学
  • 创建于: 2022-09-05 20:16:02
  • 更新于: 2024-02-07 14:23:20
  • 链接: https://www.wy-studio.cn/2022/09/05/数据结构基础——线性表/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
 评论