DS02线性表.ppt

第 2 章
线性表
本章主要内容
线性表的逻辑结构
线性表的顺序存储结构及运算实现
线性表的链式存储结构及运算实现
线性表的典型应用
本章重点难点
重点:
(1) 线性表ADT顺序存储实现中的基本操作及相关算法;
(2)ADT链式存储实现中基本操作及相关算法;
(3)双向链表的基本操作及相关算法;
(4)循环链表的特点、基本操作及相关算法。
难点:
线性表ATD的设计和实现,线性表ADT链式存储实现,包括双向链表、循环链表的基本操作和有关算法。
线性表的逻辑结构
线性表的定义
线性表的基本定义
线性表的定义
线性表是由n(n≥0)个数据元素组成的有限序列,其中n定义为线性表的长度,n=0时称为空表;记为:
A=(a1,a2,a3, ... ... , an)
对于非空线性表,有且仅有一个开始结点a1,有且仅有一个终端结点an;
除第一个与最后一个结点外,序列中任何一个结点ai,有一个直接前驱ai-1,有一个直接后继ai+1;
线性表的基本操作
线性表初始化:Init_List(L)
求线性表的长度:Length_List(L)
取表中元素:Get_Elem(L,i)
按值查找:Locate_List(L,x)
插入操作:Insert_List(L,i,x)
删除操作:Delete_List(L,i)
存储线性表,就是要保存至少两类信息:(1) 线性表中的数据元素;(2) 线性表中数据元素的顺序关系;
如何在计算机中存储线性表?
如何在计算机中实现线性表的
基本操作?
线性表的顺序存储结构及运算实现
顺序表
顺序表上的基本运算的实现
用一组地址连续的存储单元依次存放线性表中的数据元素。
a1 a2 … ai-1 ai … an
线性表的起始地址
称作线性表的基地址
线性表的顺序表示图示
以“存储位置相邻”表示有序对<ai-1,ai>时, ai-1和ai的地址关系如下:
LOC(ai) = LOC(ai-1) + C
C为一个数据元素所占存储量
所有数据元素的存储位置均取决于第一个数据元素的存储位置。
LOC(ai) = LOC(a1) + (i-1)×C
↑基地址
数据元素地址之间的关系