数据结构课件非常详细 ch2.ppt

《数据结构课件非常详细 ch2.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性表线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素均只有一个后继2.1线性表的类型定义（P18-19）定义：一个线性表是n个数据元素的有限序列例英文字母表（A,B,C,…..Z)是一个线性表例数据元素特征：（P19）元素个数n—表长度，n=0空表1

2、序2.2线性表的顺序存储结构顺序表：定义：用一组地址连续的存储单元存放一个线性表叫~元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址LOC(a1)—起始地址，基地址特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现#defineLIST_INIT_SIZE100#defineLISTINCREMENT10Typedefstruct{ElemType*elem;intleng

3、th;intlistsize;}SqList;a1a2anbb+lb+（n-1）l12n内存存储地址元素序号b+(maxlen-1)l备用空间数据元素不是简单类型时,可定义结构体数组动态申请内存L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));插入定义：线性表的插入是指在第i（1in+1）个元素之前插入一个新的数据元素x，使长度为n的线性表变成长度为n+1的线性表需将第i至第n共（n-i+1)个元素后移算法Ch2_1.c内存a1a2aiai+1an01i-

4、1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1x算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：删除定义：线性表的删除是指将第i（1in）个元素删除，使长度为n的线性表变成长度为n-1的线性表需将第i+1至第n共（n-i)个元素前移算法Ch2_2.c内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存

5、a1a2ai+1V数组下标01i-1n-2in-112i元素序号i+1n-1nanai+2算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低合并顺序表已知顺序表La和Lb的顺序按值非递减排列，归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减排列基本操作是“复制”，设2个指针i和j，分别指向2个表当前处理的元素，当i不大于j时复制i所指元素到Lc中，否则复制j所指元素到Lc中Ch2_3.c顺

6、序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充2.3线性表的链式存储结构特点：用一组任意的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域指针域结点ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU

7、,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针实现typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LNode*h,*p;datanextp结点（*p）(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).nextp->next表示p指向结点的指针域生成一个新结点：p=(Li

8、nkList)malloc(sizeof(Lnode));系统回收p结点：free(p)线性链表定义：结点中只含一个指针域的链表叫~，也叫单链表头结点：在单链表第一个结点前附设一个结点叫~头结点指针域为空表示线性表为空ha1a2头结点an^…...h空表^单链表的基本运算查找：查找单链表中