第2章顺序表及其应用.ppt

第2章 顺序表及其应用 ? 2.1 顺序表的基本概念 2.2 顺序表的基本运算实现 2.3 顺序表的基本运算性能分析 2.4 顺序表的应用1——查找问题 2.5 顺序表的应用2——排序问题 2.6 顺序表的应用3——字符处理问题 2.1 顺序表的基本概念 ? 2.1.1 顺序表的定义 2.1.2 顺序表的数据结构分析 2.1.3 顺序表的数据类型描述 ? 顺序表的定义 ? 顺序表是满足下列条件的一种数据： ⑴ 是有限个具有相同数据类型的数据元素的集合， D = { ai | i=1，2，…，n，n≥0 , ai为数据元素}； ⑵ 数据元素之间的关系R = { ai-1, ai | ai-1, ai∈D i=2，3，…，n，n≥0}； ⑶ 数据元素ai-1、 ai（i=2，3，…，n，n≥0）在存储器中占用相邻的物理存储区域。 2.1 顺序表的基本概念 2.1.1 顺序表的定义 ? 2.1.2 顺序表的数据结构分析 2.1.3 顺序表的数据类型描述 ? 顺序表的数据结构分析 ? 顺序表的逻辑结构 ? 顺序表的存储结构 ? 顺序表的运算集合 ? 顺序表的逻辑结构 ? 同一顺序表中所有数据元素的数据类型必须相同。 ? 顺序表中相邻的元素ai-1、ai间存在序偶关系，即对于非空的顺序表，ai-1是ai的唯一直接前驱，ai＋1是ai的唯一直接后继；而a1无前驱，an无后继 ? 顺序表属于线性逻辑结构。 ? 顺序表的存储结构 ? 数据元素ai-1、ai在存储器中占用相邻的物理存储区域 ? 若每个数据元素占用x个存储单元， 则数据元素ai 与ai-1所占存储空间首地址间的关系满足： Loc（ai）= Loc (ai-1) +x ? 顺序表数据元素ai的的存储位置与数据元素a1的存储地址（顺序表的首地址）间的关系为： Loc（ai）= Loc (a1) +(i-1)*x ? 是一种顺序存储结构 ? 顺序表的运算集合 （1）置空表SqLsetnull ( L ) 运算的结果是将顺序表L置成空表。 （2）求表长SqLlength ( L ) 运算结果是输出顺序表中数据元素的个数。 （3）按序号取元素SqLget (L ,i ) 当1≤i≤length (L)时，输出顺序表L中第i个数据元素。 ? 顺序表的运算集合 （4）按值查找（定位）SqLlocate ( L , x ) 当顺序表L中存在值为 x 的数据元素时，输出该元素在表中的位置。若表L中存在多个值为x 的数据元素，则依次输出它在表中的所有位置；当表中不存在值为x 的数据元素时，则输出一个特殊值。 （5）判表满SqLempty(L) 判断顺序表L中的数据元素是否足够多，以至于占满所规定存储空间。若表满，则输出1，否则输出0。 ? 顺序表的运算集合 （6）插入SqLinsert (L , i ,x) 在顺序表L中的第i位置插入值为x的数据元素，表长由n变为n+1。 （7）删除 SqLdelete (L , i ) 在顺序表L中删除第i个元素，表长由n变为n-1。 举出你所知道（了解）的顺序表的例子 2.1 顺序表的基本概念 2.1.1 顺序表的定义 2.1.2 顺序表的数据结构分析 ? 2.1.3 顺序表的数据类型描述 ? 顺序表的数据类型描述 ? 若已知顺序表的首地址，则顺序表中任一数据元素的地址都可通过 Loc（ai）= Loc (a1) +(i-1)*x 计算得出，这样任一数据元素都可随机存取。 ? 通常都用数组来描述顺序表的顺序存储。 ? 为随时了解顺序表当前数据元素的个数（表长），用分量last来记录最后一个数据元素在数组中的位置（下标）。 ＃define maxlen 100 typedef struct{ Datatype data[maxlen]; int last; } Sequenlist; 第2章 顺序表及其应用 2.1 顺序表的基本概念 ? 2.2 顺序表的基本运算实现 2.3 顺序表的基本运算性能分析