数据结构课件线性表PPT学习教案

1、会计学1数据结构课件线性表数据结构课件线性表2第1页/共72页3第2页/共72页4第3页/共72页5第4页/共72页6第5页/共72页7第6页/共72页8第7页/共72页9第8页/共72页 因为表中各数据元素具有相同的属性，所以占用的存储空间也相同。假设线性表中每个数据元素占用 k 个存储单元，第 1 个数据元素的起始地址为 LOC (a1)，则：第 2 个数据元素的起始地址为：LOC (a2) = LOC (a1) + k 第 i 个数据元素的起始地址为：LOC (ai) = LOC (a1) + ( i-1 ) k( i = 1, 2, 3, , n ) 第 n 个数据元素的起始地址： L

2、OC (an) = LOC (a1) + ( n-1 ) k 定位公式10第9页/共72页11第10页/共72页12第11页/共72页13第12页/共72页14第13页/共72页15第14页/共72页ai空闲i(a) 输入新元素前空闲(b) 插入前，移出空位以后16第15页/共72页17第16页/共72页18第17页/共72页19nkniniiinsnkninninPE1111211) 1(11) 1(第18页/共72页20第19页/共72页空闲(a) 删除元素前空闲21第20页/共72页22(2) 算法编写第21页/共72页第22页/共72页 24第23页/共72页25第24页/共72页26

3、第25页/共72页27第26页/共72页28第27页/共72页29第28页/共72页30第29页/共72页31第30页/共72页32第31页/共72页33第32页/共72页34第33页/共72页35第34页/共72页36第35页/共72页37第36页/共72页38第37页/共72页第38页/共72页40第39页/共72页41第40页/共72页42第41页/共72页43第42页/共72页44第43页/共72页若单链表L为空,p的初值为”NULL”,算法中while循环未执行，则返回链表长度j为0若单链表L为非空表，算法中while循环执行次数为表长度n,故算法的时间复杂度为O(n).第44页/共

4、72页46第45页/共72页47第46页/共72页 48第47页/共72页49第48页/共72页50第49页/共72页51raiair第50页/共72页52第51页/共72页53第52页/共72页54第53页/共72页531155第54页/共72页56第55页/共72页merge_1第56页/共72页58第57页/共72页59第58页/共72页60第59页/共72页 (3) 头结点和头指针 在双向链表的第一个结点之前附加一个同结构的结点，称之为头结点。头结点的数据域可以不存储任何信息也可以存储如线性表的长度等类的附加信息；头结点的前向指针域prior存储指向最后一个结点的指针，后向指针域next存储指向第一个结点的指针。61 头指针为指向头结点的指针。第60页/共72页头结点的前向指针域指向链表的最后一个结点头结点的后向指针域指向链表的第一个结点前向指针域指向前一个结点后向指针域指向下一个结点最后一个结点的后向指针域指向链表的头结点62第61页/共72页63第62页/共72页64第63页/共72页65 (1) 双向链表的插入操作第64页/共72页66第65页/共72页67 (2) 双向链表的删除操作第66页/共72页68第