答是要 3.1线形表的基本概念 存结构顺序存储结构顺序表和链式存備结构链表 3.2顺序表 饭序表的定义 饭序表的数据类型定义 版序表的基本操作 3.3链表 单链表 静态链表 循环链表 双向链表 34广义表
内容提要 3.1 线形表的基本概念 • 存储结构:顺序存储结构(顺序表)和链式存储结构(链表) 3.2 顺序表 • 顺序表的定义 • 顺序表的数据类型定义 • 顺序表的基本操作 3.3 链表 • 单链表 • 静态链表 • 循环链表 • 双向链表 3.4 广义表
3线坐表的 线性表:B=(AR,A=白a=1,2,…,ny 只={a1,aN|i=2,3…n 起始元素:a 终止元素:a 数据元素的位序: 线性表的长度 空表:n为的的线性表 常见的操作 访问元素删除元素插入元素 查找元素排序合并拆分 存情结构:顺序存储结构顺序表 链式存角结构链表
3.1 线性表的基本概念 线性表：B=(A,R), A={ai |i=1,2,..,n}, R={<ai-1 ,ai>|i=2,3,…,n} 起始元素：a1 终止元素： an 数据元素的位序：i 线性表的长度：n 空表：n为0时的线性表 常见的操作： 存储结构：顺序存储结构(顺序表) 链式存储结构(链表) 访问元素 删除元素 插入元素 查找元素 排序 合并拆分
3.2所序表 版序表:用一组地址连续的存倍单元按线性表的元 素间的逻舞版序一次存放数据元素。它是一种随即存取 结构 数据元素的逻辑顺序与在内存中的存储顺序完全一致, 必需要额外存储数据元素之间的关系 顺序表的数据类型定义 #define maXsize 100 /*顺序表的最大长度* typedef struct i elemtype elem MAXSIE: /* ' elemtype可以根据实际需要而定* int len;/*顺序表当前的长度* ISQLIST;
3.2 顺序表 顺序表：用一组地址连续的存储单元按线性表的元 素间的逻辑顺序一次存放数据元素。它是一种随即存取 结构。 顺序表的数据类型定义： 数据元素的逻辑顺序与在内存中的存储顺序完全一致， 必需要额外存储数据元素之间的关系 #define MAXSIZE 100 /*顺序表的最大长度*/ typedef struct { elemtype elem[MAXSIZE]; /*elemtype可以根据实际需要而定*/ int len; /*顺序表当前的长度*/ }SQLIST;
1、顺序表的基本操作(创建 (1)线性表的创建 时间复亲度:Omn) void createsqlist(SQLIST*l) int i: printi(请输入元素个数in"): scanf("%d",&L→ylen) printf("请输入%d个元素n"); for(i=0;i<L≯len;i+) scanf(%od", &l>elemi]. key) 略去了其他数据项的输入*
顺序表(cont’d) 1、顺序表的基本操作(创建) void createsqlist(SQLIST *L) { int i; printf("请输入元素个数\n"); scanf("%d",&L→len); printf("请输入%d个元素\n"); for(i=0;i<L→len;i++) scanf("%d",&L→elem[i].key); /*略去了其他数据项的输入*/ } (1) 线性表的创建 时间复杂度：O(n)
1、顺序表的基本操作(查 (2) 版序查找 的间复亲度:O(n) f Sqsearch(SQLIST L,int aidkey t s int for(j=0水<Llen;j++) if(.elem[jl.key==aidkey) return J; return-1;
顺序表(cont’d) int Sqsearch(SQLIST L,int aidkey) { int j; for(j=0;j<L.len;j++) if(L.elem[j].key==aidkey) return j; return -1; } (2) 顺序查找 时间复杂度：O(n) 1、顺序表的基本操作(查找)