数据结构线性表教案资料.ppt

数据结构---线性表什么是云计算?云计算定义云计算综述云计算体系特点云计算三种服务方式1.1什么是数据结构
1.2基本概念和术语
1.3抽象数据类型的表示与实现
1.4算法的描述和算法分析基本概念和术语

数据（Data)
数据元素（Dataelement）
数据项（Dataitem）
数据对象（DataObject）
数据结构（DataStructure）---带结构的数据元素的集合。包括数据的逻辑结构和数据的存储结构。
抽象数据类型
(AbstractDataType简称ADT)算法的描述和算法分析

一、算法（algorithm）
解决某一特定问题的具体步骤的描述，
是指令的有限序列。
有穷性、确定性、可行性、有输入、有输出
二、算法设计的原则三、算法分析
第二章
线性表
线性结构的基本特征为:2.1线性表的类型定义2.1
线性表的类型定义抽象数据类型线性表的定义如下：基本操作：InitList(&L)
结构销毁操作ListEmpty(L)ListEmpty(L)
ListLength(L)PriorElem(L,cur_e,&pre_e)
NextElem(L,cur_e,&next_e)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)利用上述定义的线性表操作
可以实现其它更复杂的操作假设:有两个集合A和B，分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。
现要求一个新的集合A＝A∪B。要求对线性表作如下操作：
扩大线性表LA，将存在于LB中而不存在于LA中的数据元素逐个插入到LA中去。1．从线性表LB中依次察看每个数据元素;GetElem(Lb,i,&e);//取Lb中第i个元素赋给e
if(!LocateElem(La,e,equal()))
ListInsert(La,++La_len,e);
//La中不存在和e相同的数据元素，则插入之已知一个允许包含重复元素的集合B，试构造一个不允许包含重复元素的集合A，使A中只包含B中所有值各不相同的数据元素。从集合B取出物件放入集合A
要求集合A中同样物件不能有两件以上voidunion(List&La,ListLb){

}//union若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即ai≥ai-1或ai≤ai-1(i=2,3,…,n)，则称该线性表为有序表(OrderedList)。例如：
（2，3，3，5，6，6，6，8，12）voidpurge(List&La,ListLb){
InitList(LA);La_len=ListLength(La);
Lb_len=ListLength(Lb);//求线性表的长度
for(i=1;i<=Lb_len;i++){

}
}//purge例2-3voidMergeList(ListLa,ListLb,List&Lc){
//本算法将非递减的有序表La和Lb归并为Lc

}//merge_list//La和Lb均非空，i=j=1,k=0
GetElem(La,i,ai);
GetElem(Lb,j,bj);
if(ai<=bj){//将ai插入到Lc中
ListInsert(Lc,++k,ai);++i;}
else{//将bj插入到Lc中
ListInsert(Lc,++k,bj);++j;}while(i<=La_len){//当La不空时
GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
}//插入La表中剩余元素2.2
线性表类型的实现
顺序映像最简单的一种顺序映象方法是：
令y的存储位置和x的存储位置相邻。用一组地址连续的存储单元
依次存放线性表中的数据元素
以“存储位置相邻”表示有序对<ai-1，ai>
即：LOC(ai)=LOC(ai-1)+C
C为一个数据元素所占存储量顺序映像的C语言描述线性表的基本操作在顺序表中的实现StatusInitList_Sq(SqList&L){
//构造一个空的线性表

}//InitList_SqintLocateElem_Sq(SqListL,ElemTypee,
Status(*compare)(ElemType,ElemType)){
//在顺序表中查询第一个满足判定条件的数据元素，
//若存在，则返回它的位序，否则返回0

}//LocateElem_Sq线性表操作
ListIns