参考答案 Log,n T(n)=O()+T(n-1)=2*01)+T(n-2) (n1)*O(1)+T(1
参考答案： 1. (1) a b c d (2) ① ② ③ ④ 2. Log3 n 3. T(n)=O(1)+T(n-1) =2*O(1)+T(n-2) …… =(n-1)*O(1)+T(1) =n*O(1)=O(n)
第二章线性表 线性表的类型定义 线性表的顺序表示和实现 线性表的链式表示和实现 元多项式的表示和相加
第二章 线性表 • 线性表的类型定义 • 线性表的顺序表示和实现 • 线性表的链式表示和实现 • 一元多项式的表示和相加
21线性表的类型定义 线性结构的特点 除第二个元素没有直接前驱和最后个元素没有直接后继之 外,其它元素只有一个直接前驱和只有一个后继。 例:线性表、栈和队列、串。 线性表:n个数据元素的有限序列 al, a2,a3,. 其中:a可以是数、字符和记录等。 抽象数据结构类型线性表的定义 (除上述种基本操作之外,还可是:合并拆分和复制等) 例:A=(1,2,3)B= AUB=(2,3
2.1 线性表的类型定义 • 线性结构的特点： 除第一个元素没有直接前驱和最后一个元素没有直接后继之 外，其它元素只有一个直接前驱和只有一个后继。 例：线性表、栈和队列、串。 • 线性表：n个数据元素的有限序列。 （a1 , a2 ,a3 ,……,an） 其中：ai可以是数、字符和记录等。 • 抽象数据结构类型线性表的定义 （除上述11种基本操作之外，还可是：合并、拆分和复制等） 例：A=（1，2，3） B=（2，3，4，5） A∪B=（2，3）
22线性表的顺序表示和实现 线性表的顺序表示是指用组地址连续的存储单元依次存放数据 元素 元素的存储位置关系式 oc(a; =Loc(a,)+(i-1)* 由公式可见,线性表的顺序存储结构是种随机存取的存储结构 由于数组类型具有上述特性,所以,通常用数组来描述顺序存储 结构 线性表的基本操作 插入前:(a1,a2x-nat,an)表长:n 后:(a1a2,axa,an)表长n+1 (向后移动数据元素,以保证“位置相邻”来体现数据元素的 顺序关系
2.2 线性表的顺序表示和实现 • 线性表的顺序表示:是指用一组地址连续的存储单元依次存放数据 元素。 元素的存储位置关系式: Loc(ai )=Loc(a1 )+(i-1)*l 由公式可见，线性表的顺序存储结构是一种随机存取的存储结构。 由于数组类型具有上述特性，所以，通常用数组来描述顺序存储 结构。 • 线性表的基本操作: 插入: 前： （a1 ,a2 ,…,ai-1 ,ai ,…,an） 表长：n 后： （ a1 ,a2 ,…,ai-1 ,x,ai ,…,an ） 表长：n+1 （向后移动数据元素，以保证“位置相邻”来体现数据元素的 顺序关系。）
22线性表的顺序表示和实现 顺序表的存储结构 #define LIST INIT SIZE 100 #define LISTINCREAMenT 10 typedef struct t ElemType elem, nt length; int listsize: Sqli
2.2 线性表的顺序表示和实现 • 顺序表的存储结构 #define LIST_INIT_SIZE 100 #define LISTINCREAMENT 10 typedef struct { ElemType *elem; int length; int listsize; } SqList;