等级考基础数据结构.ppt

等级考基础数据结构
第一页，本课件共有113页
数据结构的研究对象
数据结构的研究内容：
非数值数据之间的结构关系，
及如何表示，如何存储，如何处理。
归纳为三部分：逻辑结构、存储结构和运算集合。
按= 0, i=0; i<=N; i ++) f=f+coef[i]*power[i];
return(f);
}
问题规模为n, 算法时间复杂度: O(n)
空间复杂度： O(N)
第十页，本课件共有113页
线性表
线性表是最简单、最常用的数据结构。
栈、队列、串是特殊的线性表，数组和广义表是线性表的扩展--线性结构
第十一页，本课件共有113页
线性表是n 个数据元素的有限序列，
通常记作（a1, a2, a3, …, an ）。
姓名 电话号码
蔡颖 63214444
陈红 63217777
刘建平 63216666
王小林 63218888
张力 63215555
...
2. 1 线性表的概念
例、英文字母表（A, B, C, D, E Z ）。 某单位的电话号码簿。
一 线性表的逻辑结构
第十二页，本课件共有113页
线性表的概念
设 A=（a1, a2, ... , ai -1, ai , ai+1, …, an ）是一线性表，
1） 同一线性表中的元素必须是同一类型的；
2） 在表中 ai-1 领先于ai ，ai 领先于ai+1 ，称ai-1 是ai 的前件，ai+1 是ai 的后件；
3） 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个前件，有且仅有一个后件；
4） 线性表中元素的个数n 称为线性表的长度，n=0 时称为空表；
第十三页，本课件共有113页
用一组连续的内存单元依次存放线性表的数据元素。
a1
a2
ai-1
ai
ai+1
an
线性表（a1,a2, a3, ... an ）
的顺序存储结构
用顺序存储结构存储的线性表——称为顺序表
线性表的顺序存储和实现
一 线性表的顺序存储结构
第十四页，本课件共有113页
线性表的顺序存储和实现
说明：
元素之间的逻辑关系，通过元素的存储顺序表示出来.
设线性表中每个数据元素占 t 个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：
Loc(ai ) = Loc( a1 )+ ( i – 1) t
其中Loc( a1 )基地址，随机存取
a1
a2
ai-1
ai
ai+1
an
t个单元
Loc( a1 )
Loc(ai )
第十五页，本课件共有113页
线性表的顺序存储和实现
插入位置 移动元素个数 1                             n 2                             n-1  i n-i+1  n 1 n+1 0
插入算法时间复杂度分析 算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与插入位置有关。
a1
a2
ai-1
ai
ai+1
an
0
1
i-1
i-2
n-1
.
.
第十六页，本课件共有113页
线性表的顺序存储和实现
由此可见在顺序表中插入一个元素 ，平均要移动表的一半元素。表长为n的顺序表，插入算法的时间复杂度为 O（n）
假设在线性表的任何位置插入元素的概率相同，即
pi= 1/(n+1)
设pi为在第i个元素之前插入元素的概率，在长度为n的顺序表中插入一个元素，所需移动元素个数数学期望值为：
第十七页，本课件共有113页
删除算法时间复杂度分析
假设在线性表的任何位置删除元素的概率相同，即