资源描述：
《《数据结构》线性表的定义顺序表示和实现.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第1章绪论第2章线性表第3章栈和队列第4章串第6章树和二叉树第7章图第9章查找第10章排序目录1数据结构课程的起点：什么是线性结构？2线性结构的基本特征:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。线性结构是一个数据元素的有序（次序）集特点：一对一3第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例4（a1,a2,…ai-1，ai,ai＋1，…,an）
2、2.1线性表的逻辑结构线性表的定义：用数据元素的有限序列表示n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长。n≥0空表线性终点5（A,B,C,D,……,Z）学号姓名性别年龄班级012003010622陈建武男192003级电信0301班012003010704赵玉凤女182003级电信0302班012003010813王泽男192003级电信0303班012003010906薛荃男192003级电信0304班012003011018王春男
3、192003级电信0305班：：：：：例2分析学生情况登记表是什么结构。分析:数据元素都是同类型（字母），元素间关系是线性的。例1分析26个英文字母组成的英文表是什么结构。6“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含的数据项的个数都相等。×是指各元素具有相同的数据类型试判断下列叙述的正误：注意：同一线性表中的元素必定具有相同特性！分析：数据元素都是同类型（记录），元素间关系是线性的。7抽象数据类型线性表的定义如下：ADTList{数据对象：D＝{ai
4、ai∈ElemSet,i=1,
5、2,...,n,n≥0}数据关系：R1＝{
6、ai-1,ai∈D,i=2,...,n}基本操作：结构初始化操作结构销毁操作引用型操作加工型操作}ADTList8InitList(&L)操作结果：构造一个空的线性表L结构初始化操作结构销毁操作DestroyList(&L)初始条件：线性表L已存在操作结果：销毁线性表L引用型操作:ListEmpty(L)//判空ListLength(L)//表长PriorElem(L,cur_e,&pre_e)//前驱NextElem(L,cur_e,&next_
7、e)//后继9GetElem(L,i,&e)//读取LocateElem(L,e,compare())//查找ListTraverse(L,visit())//遍历加工型操作ClearList(&L)//清空PutElem(&L,i,&e)//改写ListInsert(&L,i,e)//插入ListDelete(&L,i,&e)//删除10例1：假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。即扩大线性表LA，将存在于线性表LB中而不
8、存在于线性表LA中的数据元素插入到线性表LA中去。操作步骤：1．从线性表LB中依次察看每个数据元素;2．依值在线性表LA中进行查访;GetElem(LB,i)→eLocateElem(LA,e,equal())3．若不存在，则插入之。ListInsert(LA,n+1,e)11GetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之voidunion
9、(List&La,ListLb){La_len=ListLength(La);//求线性表的长度Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){}}//union12集合B集合A从集合B取出物件放入集合A要求集合A中不能有同样物件因此，算法的策略应该和例1相同例2：已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。13voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListL
10、ength(Lb);}//unionGetElem(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal()))ListInsert(La,++La_len,e);//La中不存在//和e相同的数据元素，则插入之for(i=1;i<=Lb_len;i++){}InitList(La);//构造(空的)线性表LA14若线性表中的数据元素相互之间可以比较，并
