计算机软件技术基础 软件基础之数据结构-线性表.ppt

* * 双向循环链表 在单向循环链表中，也存在检索前趋结点费时的问题（所需时间是O（n））。 双向循环链表，其存储结构：struct dnode{int data；struct dnode *prior，*next；}；typedef struct dnode DNODE； * * 双向循环链表结点结构priordatanext 指向后继结点 指针域 数据域 指向前趋结点 指针域 * * 双向循环链表表示形式 双向循环链表表示形式： 双循环链表为空的条件:head ?.prior = head ?.next = head 表示形式为:head head ... ... ^ ^ an a2 a1 * * 双向循环链表特点 适合于两个方向的移动。 找其前趋结点的时间复杂度是O（1）。 * * 4、链表结点及标识符 约定： 设指针p指向结点ai ， ? ai作为一个变量，其标识符为p*p由于p?是记录类型，它的分量分别表示为：数据域标识符为 p? .data后继结点指针域为 p?.nextpp p?.data p?.next ai ai * * 链表结点及各分量标识符(双链表) 约定： 设指针p指向结点ai ， ? ai作为一个变量，其标识符为p*pp?的分量分别表示为： 数据域标识符为 p? .data, 后继结点指针域为 p?.next ,前趋结点指针域为p? .prior。 p ai-1的标识符为: p?.prior,ai-1的数据域为: p?.prior ? .data ai+1的标识符为: p?.next,ai+1的数据域为: p?. next ? .data a i+1 ai a i-1 * * 链表存储结构的特点 插入、删除操作极为方便 数据非连续存放、顺序存取 逻辑上相邻，物理上不一定相邻 存储结构较复杂、需要额外的存储空间 结论： 链表存储结构适合于表中元素频繁变动的线性表。 * * 5、链表的动态生成 链表是一种动态存储结构。因此，建立链表的过程是动态生成的过程。 按链表结点建立的顺序、方向不同，分为两种方法： 从前往后的动态生成法 将元素插入链表的末尾 从后往前的动态生成法 总是将元素插到链表的第一个位置 * * 链表动态生成（方法一）从前往后 算法操作步骤： step1 初始化；头指针置NULL step2 输入结点数据非0循环1)、 使s指向新生成的结点，s-data = num2)、 若 head=NULL(第1个结点) ,head=s3)、 否则 p-next=s4) 、 指针p始终指向s ,p=s step3 结束循环,p-next =NULL, 返回头指针head。 heads ^ ... p a i ai-1 a2 a1 * * 链表的动态生成（方法二）从后往前 算法操作步骤： step1 初始化；头指针置NULL,线性表元素存于A[N]中,i=N-1 step2 i = 0 循环1) 使s指向新生成的结点，2) s-data = A[i] ,s-next = head3) 指针s始终指向头指针 head=s step3 结束循环, 返回头指针head。 head^ ... s ai-1 ai an ai-1 * * * * 相互关系描述 1）L的长度为n（n ?0），当n为0时，表示是空表； 2）每个元素（除了第1个和最后一个元素外），有唯一的前趋和后继； 3）线性表中各元素间存在着线性关系； 4）均匀性；各元素数据类型必须相同； 5）有序性；各元素是有序的，不可交换次序。 线性表：n（=0）个数据元素的有限序列。 * * 线性表的基本操作 线性表的主要操作有如下几种： 1．??? Initiate(L) 初始化：构造一个空的线性表L。 2．??? Insert(L,i,x) 插入：在给定的线性表L中，在第i个元素之前插入数据元素x。线性表L长度加1。 3．??? Delete(L,i) 删除：在给定的线性表L中，删除第i个元素。线性表L的长度减1。 4．??? Locate(L,x) 查找定位：对给定的值x，若线性表L中存在一个元素ai与之相等，则返回该元素在线性表中的位置的序号i，否则返回Null（空）。 5．??? Length(L) 求长度：对给定的线性表L，返回线性表L的数据元素的个数。 * * 6．??? Get(L,i) 存取：对给定的线性表L，返回第i（0≤i≤Length(L)-1）个数据元素，否则返回Null。 7．??? Traverse(L) 遍历：对给定的线性表L，依次输出L的每一个数据元素。 8．??? Copy(L,C) 复制：将给定