[计算机软件及应用]数据结构-线性表.pptVIP

一. 双向链表的构造 所谓双向链表是指链表的每一个结点中除了数据域以外设置两个指针域，其中之一指向结点的直接前驱结点，另外一个指向结点的直接后继结点。 链结点的实际构造可以形象地描述如下： llink data rlink 其中，data 为数据域 llink ,rlink 分别为指向该结点的直接前驱 与直接后继结点的指针域 2.5 双向链表及其操作 用类C 语言描述： struct binode { char data; …… …… struct binode *llink,rlink; }; struct binode binode; Struct binode *list, *p; list ^ ^ 二. 双向链表的插入 在带有头结点的非空双向循环链表中第一个数据域的内容为x 的链结点右边插入一个新结点。 需要做的工作： 1. 找到满足条件的结点。 2. 若找到，申请一个新的链结点。 3. 将新结点插到满足条件的结点后面。 item item item p 插入前 x q 插入后 插入 算法 { q=list-rlink; // q 初值时指向头结点的下一个结点 while (q!=list q-data!=x) q=q-rlink; // 寻找满足条件的链结点 if (q==list) { printf( “There is no this node !” ); return; } // 没有找到满足条件的结点 void INSERTD( struct binode *list, char x, char ch) } p=(struct binode *)malloc(sizeof(struct binode)); p-data=ch; q-rlink=p; (q-rlink)-llink=p; p-rlink=q-rlink; p-llink=q; … … p x item q 三. 双向链表的删除 功能：从带有头结点的非空双向循环链表中删 除第 一个数据域中内容为x 的链结点。 需要做的工作： 1. 找到满足条件的结点。 2. 若找到，删除并释放该结点。 list 删除前 删除后 删除 算法 { q=list-rlink // q初值时指向头结点的下一个结点 while (q!=list q-data!=x ) q=q-rlink; // 找满足条件的链结点 if (q==list) { printf( “There is no this node” ); return; } // 没有找到满足条件的结点 // void DELETED( struct binode *list, char x ) } free(q); // 释放被删除的结点的存储空间 // (q-rlink)-llink=q-llink; (q-llink)-rlink=q-rlink; … … x q 1. 有人说, 线性表的顺序存储结构比线性表的链式 存储结构的存储开销要少, 也有人说, 线性表的 链式存储结构比线性表的顺序存储结构的存储开 销要少, 你是如何看待这两种说法的? 2. 线性表可以采用顺序存储结构,也可以采用链式存 储结构,在实际问题中,应该根据什么原则来选择其 中最合适的一种存储结构? 3. 若频繁地对一个线性表进行插入与删除操作,该线 性表应该采用什么存储结构? 为什么? 思考 创建一线性链表， 将该链表中数据域值最小的那个结点移到链表的最前端。 显示移动前后线性链表的数据。 list 35 67 18 65 82 71 52 10 14 … … ^ list 35 67 18 65 82 71 52 10