目录 线性表的辑结构删 2.顺序表 解3,链表 单 链表的存储结构 单链表的基本运算 环链表 双链表
目录 1.线性表的逻辑结构 2. 顺序表 3. 链表 单链表的存储结构 单链表的基本运算 循环链表 双链表
目录(续) 4,线性表的应用实例 顺序表的模板类定y及应用删 单链表的模板类定义及应用 线性表在多项式运算中的应用 5.小结
目录 (续) 顺序表的模板类定义及应用 单链表的模板类定义及应用 线性表在多项式运算中的应用 4. 线性表的应用实例 5. 小结
21线性表的逻辑结构 211线性表的基本概念 线性表是最基本、最常用的一种数据结构,它不仅有 着广泛的应用,而且也是其它数据结构的基础。线性表 的例子不胜枚举。例如,英文字母表(A,B,z)是 一个线性表,表中的每一个英文字母是一个数据元素, 又如,一副扑克牌的点数也是一个线性表:(2,3,4,5, 6,7,8,9,10,J,Q,K,A)。其中每一张牌的点数就是 个数据元素。在较为复杂的线性表中,数据元素可由 若千数据项组成,如学生成绩表中,每个学生的成绩情 况是一个数据元素,它由学号,姓名,各科成绩及平均 成绩等数据项组成
线性表是最基本、最常用的一种数据结构，它不仅有 着广泛的应用，而且也是其它数据结构的基础。线性表 的例子不胜枚举。例如，英文字母表（A, B, …, Z）是 一个线性表，表中的每一个英文字母是一个数据元素， 又如，一副扑克牌的点数也是一个线性表：（2, 3, 4, 5, 6, 7, 8, 9, 10 ,J, Q, K, A）。其中每一张牌的点数就是 一个数据元素。在较为复杂的线性表中，数据元素可由 若干数据项组成，如学生成绩表中，每个学生的成绩情 况是一个数据元素，它由学号，姓名，各科成绩及平均 成绩等数据项组成。 2.1 线性表的逻辑结构 2.1.1 线性表的基本概念
线性表( Linear list)是由n(n≥0)个具有 相同属性的数据元素a1a2…an组成的有限序列。 其中数据元素的个数n定义为表的长度。 当n=0时称为空表,常常将非空的线性表(n>0) 记作:(a1,a2,…,a;,…,an) 这里的数据元素a;(1sisn)只是一个抽象的符 号,其具体含义在不同情况下是不同的
线性表（Linear List）是由n（n0）个具有 相同属性的数据元素a1 ,a2 ,…,an组成的有限序列。 其中数据元素的个数n定义为表的长度。 当n=0时称为空表，常常将非空的线性表（n>0） 记作： （a 1，a 2，···，a i ，···，a n ） 这里的数据元素a i（1 i n）只是一个抽象的符 号，其具体含义在不同情况下是不同的
从线性表的定义可以看出其特点是 ()同一性:线性表中的所有数据元素属于同一数据 对象; (2)有穷性:线性表中的数据元素个数是有限的,其 数目就是表长; (3)有序性:线性表中相邻的数据元素间存在着序偶 关系<a1,a1
从线性表的定义可以看出其特点是： •⑴ 同一性：线性表中的所有数据元素属于同一数据 对象； ⑵ 有穷性：线性表中的数据元素个数是有限的，其 数目就是表长； ⑶ 有序性：线性表中相邻的数据元素间存在着序偶 关系
212线性表的抽象数据类型定义 ADT LinearList Typedef struct List L InitList(L, maxSize); 说明:构造空表L,即表的初始化 ListLength(L); 说明:求表L的长度 IsEmpty L; 说明:判断表L是否为空表 isFull(l); 说明:判断表L是否已“满 GetNode (L,i, e); 说明:取表L中的第个数据元素存入e
ADT LinearList{ Typedef struct List L; InitList(L,maxSize); 说明：构造空表L，即表的初始化 ListLength(L); 说明：求表L的长度 isEmpty(L); 说明：判断表L是否为空表 isFull(L) ; 说明：判断表L是否已“满” GetNode (L,i,e); 说明：取表L中的第i个数据元素存入e 2.1.2 线性表的抽象数据类型定义
LocateNode l, e; 说明:查找表L中值为e的数据元素 LocateNode(, e, low, up) 说明:在表L的loW-up范围内查找值为e的数据元素 InsertNode(L, e, i); 说明:在表L的第个位置插入值为e的新数据元素 InsertNode(L, e); 说明:值为e的数据元素插入到有序表L,保持有序 DeleteNode ( L, i, e); 说明:删除表中第个数据元素,被删元素值存入e ClearList L); 说明:将线性表L清空
LocateNode(L,e); 说明：查找表L中值为e的数据元素 LocateNode(L,e,low,up); 说明：在表L的low-up范围内查找值为e的数据元素 InsertNode (L,e,i); 说明：在表L的第i个位置插入值为e的新数据元素 InsertNode (L,e); 说明：值为e的数据元素插入到有序表L，保持有序 DeleteNode (L,i ,e); 说明：删除表L中第i个数据元素，被删元素值存入e ClearList (L); 说明：将线性表L清空 } ;
22顺序表221线性表的顺序存储结构 将个线性表存储到之斜地址 存地址 0 al Loc ai 计算机中,可以采用许 a Loc a2) 多不同的方法,其中既 简单又自然的是顺序存 白i Loc ai) 储方法:用一组地址连 续的存储单元依它们的 逻辑次序存储线性表的 各个数据元素,称作线 空 CC &a1 性表的顺序存储结构, 简称为顺序表。 图2.1顺序表的示意图
将一个线性表存储到 计算机中，可以采用许 多不同的方法，其中既 简单又自然的是顺序存 储方法：用一组地址连 续的存储单元依它们的 逻辑次序存储线性表的 各个数据元素，称作线 性表的顺序存储结构， 简称为顺序表。 2.2 顺序表 2.2.1线性表的顺序存储结构
设线性表L=(a1,a2;…,an),每个元素占用d个存 储单元,则线性表中第1个元素a的存储位置 Loc(a)和第个元素a的存储地址LOc(aj之间满足 关系: LoC(a +1=Loc(ai)+ d 因此,表中第个元素a的存储位置可通过下式计算: LOC(a=Loc(a1+(i-1)*d 其中,Loc(a1)是第一个元素的地址称为基地址
设线性表L = (a 1 , a 2 ,···, a n )，每个元素占用d个存 储单元，则线性表中第i+1个元素a i+1的存储位置 LOC(a i+1)和第i个元素a i的存储地址LOC(a i )之间满足 关系： LOC(a i+1) = LOC(a i ) + d 因此，表中第i个元素ai的存储位置可通过下式计算： LOC(a i ) = LOC(a 1 ) + (i -1) * d 其中，LOC(a1 )是第一个元素的地址称为基地址
顺序表的特点是 逻辑上相邻的元素其物理位置亦相邻。 222顺序表的基本运算 下面,我们先给出整数表的结构声明 Typedef struct int *elen;∥数据元素数组指针 int Size: ∥线性表中当前元素数目 int maxsize;∥初始化操作中为线性表分配的单元数 JslIst;
顺序表的特点是： 逻辑上相邻的元素其物理位置亦相邻。 2.2.2顺序表的基本运算 下面，我们先给出整数表的结构声明： Typedef struct { int *elem; // 数据元素数组指针 int Size; // 线性表中当前元素数目 int maxSize; // 初始化操作中为线性表分配的单元数 }sqList;