《数据结构》线性表的定义顺序表示和实现.pptx

第1章绪论第2章线性表第3章栈和队列第4章串第6章树和二叉树第7章图第9章查找第10章排序目录

数据结构课程的起点：什么是线性结构？

集合中必存在唯一的一个“最后元素”除最后元素在外，均有唯一的后继；除第一元素之外，均有唯一的前驱。特点：一对一集合中必存在唯一的一个“第一元素”；线性结构是一个数据元素的有序（次序）集线性结构的基本特征:性表的逻辑结构线性表的顺序表示和实现线性表的链式表示和实现应用举例第2章线性表

（a1,a2,…ai-1，ai,ai＋1，…,an）2.1线性表的逻辑结构线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点

（A,B,C,D,……,Z）学号姓名性别年龄班级012003010622陈建武男192003级电信0301班012003010704赵玉凤女182003级电信0302班012003010813王泽男192003级电信0303班012003010906薛荃男192003级电信0304班012003011018王春男192003级电信0305班：：：：：例2分析学生情况登记表是什么结构。分析:数据元素都是同类型（字母），元素间关系是线性的。例1分析26个英文字母组成的英文表是什么结构。同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。是指各元素具有相同的数据类型注意：同一线性表中的元素必定具有相同特性！×试判断下列叙述的正误：分析：数据元素都是同类型（记录），元素间关系是线性的。0506

数据对象：抽象数据类型线性表的定义如下：ADTList{D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}基本操作：结构初始化操作结构销毁操作引用型操作加工型操作}ADTList

InitList(L)操作结果：构造一个空的线性表L结构初始化操作结构销毁操作ListEmpty(L)//判空ListLength(L)//表长PriorElem(L,cur_e,pre_e)//前驱NextElem(L,cur_e,next_e)//后继引用型操作:初始条件：线性表L已存在操作结果：销毁线性表LDestroyList(L)

GetElem(L,i,e)//读取LocateElem(L,e,compare())//查找ListTraverse(L,visit())//遍历加工型操作ClearList(L)//清空PutElem(L,i,e)//改写ListInsert(L,i,e)//插入ListDelete(L,i,e)//删除

例1：假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。即扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。操作步骤：1．从线性表LB中依次察看每个数据元素;2．依值在线性表LA中进行查访;GetElem(LB,i)→eLocateElem(LA,e,equal())3．若不存在，则插入之。ListInsert(LA,n+1,e)

GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之voidunion(ListLa,ListLb){La_len=ListLength(La);//求线性表的长度Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i++