数据结构第2章1

《数据结构第2章1》由会员分享，可在线阅读，更多相关《数据结构第2章1（7页珍藏版）》请在金锄头文库上搜索。

1、数据结构第2章1 线性结构的定义：若结构是非空有限集，则有且仅有一个开头结点和一个 终端结点，并且全部结点都最多只有一个直接前趋和一个直 接后继。 可表示为：(a1 , a2 , , an) 特点 只有一个首结点和尾结点； 特点 除首尾结点外，其他结点只有一个直接前驱和一个 直接后继。 简言之，线性结构反映结点间的规律关系是 一对一 (1:1) 的。 线性结构包括：线性表、堆栈、队列、字符串、数组 等，其中最典型、最常用的是- 线性表1 第2章 线性表2.1 线性表的基本概念 2.2 线性表的挨次表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例 2.1 线性表的基本概念1、线性表

2、它是一种最简洁的线性结构。是一种可以在任 意位置进行插入和删除数据元素操作的，由n(n0) 个相同类型数据元素a0, a1, , an-1组成的线性结 构。 线性表的规律结构： (a0, a1, ai-1,ai, ai+1 , an-1)数据元素线性起点 ai的直接前趋 ai的直接后继 线性终点 下标，是元素的 序号，表示元素 在表中的位置 n=0时称为 空表 n为元素总个数，即表 长。n0 例1 分析26 个英文字母组成的英文表是什么结构。( A, B, C, D, , Z) 分析： 数据元素都是同类型(字母), 元素间关系是线性的。 例2 分析同学状况登记表是什么结构。学号 姓名 性别 年

3、龄 班级 012021010622021003010704 012021010813 012021010906 012021011018 : 陈建武赵玉凤 王 泽 薛 荃 王 春 ： 男女 男 男 男 ： 1918 19 19 19 : 2021级电信0301班2021级电信0302班 2021级电信0303班 2021级电信0304班 2021级电信0305班 ： 分析：数据元素都是同类型(记录),元素间关系是线性的。 留意：同一线性表中的元素必定具有相同特性 ！5 2、线性表抽象数据类型它包括两个方面： 数据集合： a0, a1, , an-1 ai的数据类型为 DataType 操作集合

4、：(1)ListInitiate(L) 初始化线性表 (2)ListInsert(L,i,x) 插入数据元素 (3)ListLength(L) 求当前数据元素个数 (4)ListDelete(L,i,x) 删除数据元素 (5)ListGet(L,i,x) 取数据元素 等6 3、线性表的存储结构(1)挨次存储结构:它是使用一片地址连续的有限内存单 元空间存储数据元素的一种计算机存储数据方法。 特点：(任意两个在规律上相邻的数据元素在物理位置 上也必定相邻)规律上相邻的元素，物理上也相邻。 (2)链式存储结构:它是把数据元素和指针定义成一个 存储体，使用指针把发生联系的数据元素链接起来 的一种计算

5、机存储数据方法。 特点：任意两个在规律上相邻的数据元素在物理上不 肯定相邻，数据元素的规律次序是通过链中的指针 链接实现的。 2.2 线性表的挨次表示和实现一 、挨次表的存储结构 二、 挨次表的实现 三、 挨次表的运算效率分析 一、 挨次表的存储结构表示 可以利用数组Vn来实现 1、挨次表：用一组地址连续的存储单元依次存储线性表的各个数据元素。即采纳挨次存储结构的线性 表。它通常采纳静态数组实现数据元素的存储。 留意：在C语言中数组的下标是从0开头，即： Vn的有效范围是从 V0Vn-19 2、线性表挨次存储特点： (1) 规律上相邻的数据元素，其物理上也相邻； (2) 若已知表中首元素在存储

6、器中的位置，则其他元 素存放位置亦可求出(利用数组Vn的下标)。 设首元素a0的存放地址为LOC(a0)(称为首地址), 设每个元素占用存储空间(地址长度)为L字节， 则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a0 ) + L *i 对上述公式的解释如图所示10 3、线性表的挨次存储结构示意图地址 b=LOC(a0) 内容 a0 a1 ai ai+1 元素在表中的位序 L 0 1 i i+1 b+ Lb +iL b +(n-1)Lb +(MaxSize-1)L an-1 n-1空闲区 LOC ( ai ) =

7、 LOC( a0 ) + L *i11 4、用C语言描述 typedef struct DateType listMaxSize; int size; SeqList;/* MaxSize表示数组的最大元素个数，list表示挨次表 的数组名，size表示挨次表中当前存储的数据元素个 数，它必需满意size MaxSize,SeqList是该结构体 的名字。*/12 例1 设有一维数组M,下标的范围是0到9, 每个数组元素用相邻的5个字节存储。存储器 按字节编址，设存储数组元素M0的第一个字节的地址是98,则M3的第一个字节的 地址是多少？解：已知地址计算通式为： LOC(ai) = LOC(a

8、0) + L *i LOC( M3 ) = 98 + 5 3 =113 113 例2 用数组V来存放26个英文字母组成的线性表 (a,b,c,z),写出在挨次结构上生成和 显示该表的C语言程序。 char V30; void build() /*字母线性表的生成，即建表操作 */ int i; 核心语句： V0=a; 方法1 Vi= Vi-1+1; for( i=1; i=n-1; i+ ) 方法2 Vi=a+i; Vi=Vi-1+1; 方法3 Vi=97+i; 14 void display( ) /*字母线性表的显示，即读表操作*/ int i; for( i=0; i=n-1; i+ )

9、 printf( %c, vi ); printf( n ); void main(void) /*主函数，字母线性表的生成和输出*/ n=26; /* n是表长，是数据元素的个数，而不是V的实际下标*/ build( ); display( ); 执行结果： a b c d e f g h i j k l m n o p q r s t u v w x y z15 二、 挨次表的实现(或操作) 数据结构的基本运算： 修改、插入、删除、查找、排序 1) 修改 通过数组的下标便可访问某个特定元素并 修改之。 核心语句: Vi=x; 明显，挨次表修改操作的时间效率是 O(1) 2)插入 在线性表(

10、n个元素)的第i个位置前插入一个元素实现步骤： 将第n至第i 位的元素向后移动一个位置； 将要插入的元素写到第i个位置； 表长加1。 留意：事先应推断: 插入位置i 是否合法?表是否已满? for (j=n-1; j=i; j-) 核 / 元素后移一个位置 心 aj+1=a j ; / 插入x 语 a i =x; 句： / 表长加1 n+;17 在线性表的第i个位置前插入一个元素的示意图如下：1 2 3 4 插入25 5 12 1 1213 21 1321 24 28 30 42 77 23 4 5 6 7 8 2425 67 8 2830 42 77 9 3)删除 删除线性表的第i个位置上的

11、元素实现步骤： 将第i+1 至第n 位的元素向前移动一个位置； 表长减1。 留意：事先需要推断，删除位置i 是否合法? 核心语句： for ( j=i+1; j=n-1; j+ ) aj-1=aj; / 元素前移一个位置 / 表长减1 n-; 删除挨次表中某个指定的元素的示意图如下：1 2 3 4 5 6 7 8 12 13 21 24 25 28 1 2 3 4 5 6 7 8 12 13 21 24 28 30 42 77 3042 77 9 例：建立一个线性表，先依次输入数据元素1,2, 3,4,10,然后删除5,最终依次显示当前 线性表中的数据元素。假设该线性的数据元素个 数最坏状况下不会超过100个。 实现方法： 1、采纳直接编写一个主函数实现。 2、利用已设计实现的抽象数据类型模块。(存 放在头文件名为SeqList.h中，通过 #include “SeqList.h” ) 7Word版本