数据结构课件第2章线性表.ppt

1、123456789 因为表中各数据元素具有相因为表中各数据元素具有相同的属性，所以占用的存储空间同的属性，所以占用的存储空间也相同。假设线性表中每个数据也相同。假设线性表中每个数据元素占用元素占用 k 个存储单元，第个存储单元，第 1 个个数据元素的起始地址为数据元素的起始地址为 LOC(a1)，则：则：第第 2 个数据元素的起始地址为：个数据元素的起始地址为：LOC(a2)=LOC(a1)+k 第第 i 个数据元素的起始地址为：个数据元素的起始地址为：LOC(ai)=LOC(a1)+(i-1)k(i=1,2,3,n)第第 n 个数据元素的起始地址：个数据元素的起始地址：LOC(an)=LOC

2、(a1)+(n-1)k 定位公式定位公式101112131415ai空闲空闲i(a)输入新元素前输入新元素前空闲空闲(b)插入前，移出空位以后插入前，移出空位以后16171819nkniniiinsnkninninPE1111211)1(11)1(20空闲空闲(a)删除元素前删除元素前空闲空闲2122(2)算法编写算法编写 2425262728293031323334353637384041424344若单链表若单链表L L为空为空,p,p的初值为的初值为”NULL”,NULL”,算法中算法中whilewhile循环未执行，循环未执行，则返回链表长度则返回链表长度j j为为0 0若单链表若单链

3、表L L为非空表，算法中为非空表，算法中whilewhile循环执行次数为表长循环执行次数为表长度度n,n,故算法的时间复杂度为故算法的时间复杂度为O(nO(n).).4647 48495051raiair52535453115556LinkList merge_1(LinkList LA,LinkList LB)/此算法将两个采用头指针的循环单链表首尾连接起来此算法将两个采用头指针的循环单链表首尾连接起来 Node *p,*q;p=LA;q=LB;merge_1585960 (3)头结点和头指针头结点和头指针 在双向链表的第一个结点之前附加一个在双向链表的第一个结点之前附加一个同结构同结构的

4、结点，称之的结点，称之为为头结点头结点。头结点的数据域可以不存储任何信息也可以存储如线。头结点的数据域可以不存储任何信息也可以存储如线性表的长度等类的附加信息；头结点的前向指针域性表的长度等类的附加信息；头结点的前向指针域prior存储指向存储指向最后一个结点的指针，后向指针域最后一个结点的指针，后向指针域next存储指向第一个结点的指针。存储指向第一个结点的指针。61 头指针头指针为指向头结点的指针。为指向头结点的指针。头结点的前向指针域指向链表的最后一个结点头结点的前向指针域指向链表的最后一个结点头结点的后向指针域指向链表的第一个结点头结点的后向指针域指向链表的第一个结点前向指针域指向前一个结点前向指针域指向前一个结点后向指针域指向下一个结点后向指针域指向下一个结点最后一个结点的后向指针域指向链表的头结点最后一个结点的后向指针域指向链表的头结点62636465 (1)双向链表的插入操作双向链表的插入操作6667 (2)双向链表的删除操作双向链表的删除操作68697071 1.空间性能的比较空间性能的比较72 2.时间性能的比较时间性能的比较