ch2线性表.ppt
《ch2线性表.ppt》由会员分享,可在线阅读,更多相关《ch2线性表.ppt(62页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第二章 线性表线性结构是一个数据元素的有序(次序)集。线性结构的特点:在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外,集合中的每个数据元素均只有一个前驱,称为直接前驱(Immediate Predecessor)。除最后一个外,集合中的每个数据元素均只有一个后继,称为直接后继( Immediate Successor)。2.1 线性表的类型定义一、定义:一个线性表是n个数据元素的有限序列niaaaa,21如例: 英文字母表(A,B,C,.Z)是一个线性表例:学号姓名年龄001张三18002李四19数据元素二、线性表的特征:v
2、元素个数n称为表长度,n=0,称为空表v1in时l ai的直接前驱是ai1,a1无直接前驱l ai的直接后继是ai1,an无直接后继v元素同构,且不能出现缺项三、线性表抽象数据类型的定义ADT List 数据对象数据对象: D= ai | aiElemSet , i = 1,2,.,n, n 0数据关系数据关系: R1= |a i1 ,a iD, i = 1,2,.,n 基本操作:& 符号说明函数参数是引用型InitList(&L)DestroyList(&L)ClearList(&L) ListEmpty(L)ListLength(L) GetElem(L, i , &e)PutElem(&
3、L, i, e)LocateElem(L , e)PriorElem(L , cur_e , &pre_e)NextElem(L , cur_e , &next_e)ListInsert(&L , i , e) ListDelete(&L , i , &e)ListTraverse(L, visit( ) 线性表初始化:线性表初始化: InitList(&L)InitList(&L); 构造一个空的线性表L,即表的初始化。 求线性表的长度:求线性表的长度:ListLength (L)ListLength (L); 返回线性表中数据元素的个数,即表长 。 取表中元素:取表中元素:GetElem(
4、L, i,&e)GetElem(L, i,&e); 取线性表L中的第i个结点,要求1iListLength(L) 插入操作:插入操作:ListInsert (&L, i, e)ListInsert (&L, i, e); 在线性表L的第i个位置上插入一个值为e的数据元素。(5)(5)删除操作:删除操作:ListDelete (&L, i ,&e)ListDelete (&L, i ,&e); 在线性表L中删除位序为 i 的数据元素。 按值查找:按值查找:LocateElem(L, e)LocateElem(L, e); 在L中查找值为e的结点,并返回该结点在L中的位置。若L中有多个结点的值和e
5、 e相同,则返回首次找到的结点位置;若L中没有结点的值为e e,则返回一个特殊值(如零)表示查找失败。课后思考:应用基本操作实现课后思考:应用基本操作实现删除线性表删除线性表LaLa中大于中大于e e的所有的所有数据元素:数据元素:DelElems(&L,e)DelElems(&L,e)CopyList(La,&Lb)/CopyList(La,&Lb)/应用基本操作:实现应用基本操作:实现CopyList(La,&Lb)CopyList(La,&Lb) InitList(Lb) InitList(Lb); LenA=ListLength(La);LenA=ListLength(La); for
6、(i=1;i=LenA;i+) for(i=1;i=LenA;i+) GetElem(La,i,e); GetElem(La,i,e); ListInsert(Lb,i,e); ListInsert(Lb,i,e); 课堂练习:课堂练习:应用基本操作实现应用基本操作实现CopyList(La,&Lb)CopyList(La,&Lb)例例1:1:设计求设计求 A = AA = AB B 的算法的算法l分析:建立线性表分析:建立线性表 La、Lb分别表示集合分别表示集合A和和B,将,将Lb中存中存在而在而La中不存在的元素中不存在的元素e插入插入 La中,因此,中,因此,本算法的基本操本算法的基本
7、操作是查找作是查找(比较比较)。算法算法思想思想: 1. 从从Lb中依次取得每个元素中依次取得每个元素e GetElem (Lb, i, e) 2. 判断该元素判断该元素e是否在是否在La中存在中存在 LocateElem (La, e) 3.若不存在,则将元素若不存在,则将元素e插入到插入到La中中 ListInsert (La, i, e)l基于基于逻辑逻辑结构的算法描述:结构的算法描述: void Union( &La , Lb) La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1; i=Lb_len; i+ +) GetElem(
8、Lb, i, e); if (!LocateElem(La, e) ListInsert(La, + +La_len, e); l例例2:巳知线性表:巳知线性表LA和线性表和线性表LB中的数据元素按值非递减中的数据元素按值非递减有序排列,现要求将有序排列,现要求将LA和和LB归并为一个新的线性表归并为一个新的线性表LC,且,且LC中的元素仍按值非递减有序排列。中的元素仍按值非递减有序排列。Init_List (LC) Length_List (LA)& Length_List (LB)判断:若i所指元素 j所指元素,则将i所指元素插入在LC的k+1前(即LC的表尾),且i、k的值分别+1;否则
9、,将j所指元素插入在LC的k+1前(即LC的表尾),且j、k的值分别+1;2.2 线性表的顺序表示和实现一、顺序表(Sequential List)1、定义:用一组地址连续的存储单元存放一个线性表叫2、元素地址计算方法:vLOC(ai)LOC(a1)+(i1)*LvLOC(ai+1)LOC(ai) Lv其中:l L 一个元素占用的存储单元个数l LOC(ai)线性表第i个元素的地址3、顺序表的特点:v实现逻辑上相邻物理地址相邻v实现随机存取4、顺序表的实现:可用C语言的一维数组实现a1a2an01n-112n内存V数组下标元素序号M-1#define List_Init_Size 100typ
10、edef int ElemType ; typedef ElemType ET;typedef struct ElemType *elem; /动态空间基址 int length; /实际元素个数 int listsize; /当前分配的存储容量 /(以sizeof(ElemType)为单位) SqList; 备用空间声明结构体类型, SqList 是顺序表的类型名动态申请和释放内存空间L.elem = (ElemType *)malloc(List_Init_Size*sizeof(ElemType); /申请内存free(L.elem); /释放内存typedef struct ElemT
11、ype *elem ; int length ; int listsize ;SqList ; int ListLength_Sq(SqList L) void ClearList_Sq(SqList &L) 访问顺序表L中第3个元素:L.elem2 e=L.elem2; L.elem2=8; GetElem_Sq(SqList L, int i, ElemType &e) 525L5 5个有效数据个有效数据25个元素存储空间L L表的基址(数组名)是表的基址(数组名)是 L.elemL.elem关于数据类型名StatusStatusStatus是是“状态状态”的意思,不是的意思,不是C C语
12、言中的关键字,其语言中的关键字,其目的是为了增强算法的目的是为了增强算法的“可读性可读性”typedef int Status;typedef int Status;StatusStatus型的数据范围是型的数据范围是: True: True、FalseFalse、OkOk、Error Error #define True 1 #define True 1 #define False 0#define False 0Status ListEmpty(SqList L)Status ListEmpty(SqList L)/判断线性表判断线性表L L是否为空表是否为空表 if ( L.length
13、 = =0)if ( L.length = =0) return True; return True; return False; return False; 顺序表基本操作的算法描述顺序表基本操作的算法描述/构造一个空的线性表构造一个空的线性表 L L#define List_Init_Size 10 /#define List_Init_Size 10 /存储空间的初始分配量存储空间的初始分配量#define ListIncrement 10 /#define ListIncrement 10 /存储空间的分配增量存储空间的分配增量Status Status InitList_Sq( Sq
14、List InitList_Sq( SqList & &L)L) L.elem=(ET L.elem=(ET * *) )mallocmalloc(List_Init_Size(List_Init_Size* *sizeofsizeof(ET);(ET); if if (L.elem = = NULL) (L.elem = = NULL) exitexit(OVERFLOW); (OVERFLOW); / /* *存储分配失败存储分配失败* */ / L.length=0; L.length=0; / /* * 空表的长度空表的长度 * */ / L.listsize=List_Init_Si
15、ze; L.listsize=List_Init_Size; / /* * 初始存储容量初始存储容量 * */ / returnreturn OK; OK; 添加(添加(1 1,3 3,5 5,7 7,9 9)之后的状态:)之后的状态:创建空表之后,表创建空表之后,表L L的状态如下:的状态如下:L.0 0101024 4 12 1 3 5 7 11 0 31010个元素存储空间个元素存储空间删除第删除第3 3个元素之后的状态:个元素之后的状态:4 41010L. 1 3 7 9 9 5 7 11 0 31010个元素存储空间个元素存储空间是随机数据也是随机数据也就是无效数据就是无效数据顺序表
16、的内存状态 问题:问题:在表的第在表的第1 1个位置插入个位置插入 6 6 之之后,表后,表L L的存储状态如何?的存储状态如何?问题:清空问题:清空L,L,即即 ClearList_Sq(L)ClearList_Sq(L)之后,表之后,表L L的存储状态如何?的存储状态如何?5 51010L. 1 3 5 7 9 5 7 11 0 31010个元素存储空间个元素存储空间添加(添加(1 1,3 3,5 5,7 7,9 9)之后的状态:)之后的状态:5 51010L. 1 3 5 7 91010个元素存储空间个元素存储空间创建空表之后,表创建空表之后,表L L的状态如下:的状态如下:L.0 01
17、0101010个元素存储空间个元素存储空间删除第删除第3 3和第和第4 4个元素之后的状态:个元素之后的状态:3 31010L. 1 3 91010个元素存储空间个元素存储空间将随机数据想将随机数据想象成空白象成空白顺序表的内存想象状态结论:凡是定义的结论:凡是定义的 或或 动态申动态申请的空间内,都想象为空白。请的空间内,都想象为空白。如如: : int x,A900; int x,A900; SqList L; SqList L; ElemType ElemType * *elem;elem;二、顺序表的插入操作 定义:顺序表的插入是指在第i个(1i n+1)元素之前插入一个新的数据元素x
18、,使长度为 n 的线性表niiaaaaa,1,21 变成长度为 n+1 的线性表niiaaxaaa,1,21 需将第i至第n共(ni1)个元素依次后移一个位置。内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x顺序表的插入操作顺序表的插入操作在顺序表在顺序表L L中第中第i i个位置上插入一个新的元素个位置上插入一个新的元素e e, ,形式参数为:形式参数为:&L ,i , e&L ,i , e ;算法步骤如下:算法步骤如下:(1)(1)对输入参数的安全性检查对输
19、入参数的安全性检查: : 插入位置插入位置 i i 应落应落在表长范围内,即:在表长范围内,即:1 1 i i L.length+1 L.length+1(2)(2)存储空间的处理:存储空间的处理:若原表的存储空间已满,应若原表的存储空间已满,应追加存储空间的分配;追加存储空间的分配;(3)(3)数据块的搬移:数据块的搬移:将表中从将表中从i i到到L.lengthL.length位置上位置上的所有元素依次往后移动一个位置;的所有元素依次往后移动一个位置;(4)(4)在第在第i i个位置上存储新的元素个位置上存储新的元素e,e,表长增,即表长增,即+L.lengthL.length 。注意:逻
20、辑位置(序号)注意:逻辑位置(序号)i i 对应的存储下标是对应的存储下标是i-1i-1。重新分配动态存储空间的函数重新分配动态存储空间的函数realloc(原动态区首址,字节数原动态区首址,字节数)其功能为:其功能为:(1)(1)申请申请新的动态存储空间新的动态存储空间( (成功或失败成功或失败););(2)(2)将原动态区的数据将原动态区的数据拷贝拷贝到新动态区到新动态区; ;(3)(3)释放释放原动态存储区原动态存储区; ;(4)(4)返回返回新存储区首地址(无类型)。新存储区首地址(无类型)。用途:当原动态存储区不够用时,追加动态存储用途:当原动态存储区不够用时,追加动态存储区;区;顺
21、序表的插入操作算法描述之一顺序表的插入操作算法描述之一Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) return ERROR; /i值不合法值不合法 if (L.length = L.listsize) /当前存储空间已满,增加分配当前存储空间已满,增加分配 p=(p=(ETET * *)realloc(L.elem,)realloc(L.elem,(L.listsize+ ListIncrement)(L.listsize+ ListIncrement)* *sizeof(sizeof(ETET) ););
22、if (p=NULL) exit(OVERFLOW); /存储分配失败存储分配失败 L.elem=p; /新的基地址新的基地址 L.listsize+=ListIncrement; /增加存储容量增加存储容量 for ( j=L.length ; j=i ; -j ) L.elemj=L.elemj-1; /移动元素移动元素 L.elemj=e ; /插入新元素插入新元素 +L.length ; /表长增表长增1 return OK; 基于存储结构进行算法实现Status ListInsert_Sq(SqList &L , int i , ET e) if ( iL.length+1) ret
23、urn ERROR; if (L.length = L.listsize) p=( p=(ETET * *)realloc(L.elem,)realloc(L.elem,(L.listsize+ ListIncrement)(L.listsize+ ListIncrement)* *sizeof(sizeof(ETET) );); if (p=NULL) exit(OVERFLOW); L.elem=p; L.listsize+=ListIncrement; q=&(L.elemi-1); /* q=L.elem+(i-1) 为插入位置为插入位置 */ for (p=&(L.elemL.len
24、gth-1); p=q; -p) *(p+1)=*p; /*移动元素移动元素*/ *q=e ; /*插入新元素插入新元素*/ +L.length ; /*表长增表长增1*/ return OK; 顺序表的插入操作算法描述之二顺序表的插入操作算法描述之二基于存储结构进行算法实现顺序表插入操作的算法评价顺序表插入操作的算法评价v设 Pi 是在第 i 个元素之前插入一个元素的概率,则在长度为n的线性表中插入一个元素时,所需移动的元素次数的平均次数为:11)1(niiinPEis nOnTninnEisnPnii112)1(1111则若认为三、顺序表的删除操作 定义:线性表的删除是指将第i(1i n)
25、个元素删除,使长度为n的线性表niiaaaaa,1,21 变成长度为n-1的线性表niiaaaaa,11,21 需将第i+1至第n共(ni)个元素依次前移一个位置。内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2 顺序表的删除操作顺序表的删除操作删除顺序表删除顺序表L L中第中第i i个位置上的元素,将删除的元素值赋给个位置上的元素,将删除的元素值赋给e e。形式参数为:形式参数为:&L, i, &e&L, i, &e 算法步骤如下:算法步骤如下:(1)(1)对输
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- ch2 线性
限制150内