2线性表1.ppt

2 线性表 线性表 线性表的存储 顺序存储 顺序表 链式存储 链表 小结 顺序表中按位置读取元素十分方便，其时间代价为O(1)； 其余操作包括插入、删除和按内容查找的时间复杂度均为O(n)。 应用-跳舞链（Dancing Links） Dancing Links 分析 注意到p在删除时，左右指针未被清空是不符合正常程序的思想 (野指针问题) 但在这里，这样的野指针，却保证了在双向链表中的删除与恢复操作。 操作（2）的优雅之处就在于我们只要知道p，就可以恢复操作（1）。 Dancing Links之应用 那么如何利用操作(2)的性质 idea 1：注意到一些交互式的程序中，用户经常对于先前所做的操作进行撤消。 idea 2：注意到一类有哪些信誉好的足球投注网站问题中（例如N皇后问题）进行的试探-回溯，需要大量的删除与恢复的操作。 idea 1显然过于直白，对操作（2）的性质没有深入的认识。而idea 2则充分运用了操作(1)与操作(2)的互动性，在执行有哪些信誉好的足球投注网站的试探-回溯中，指针在数据结构内部被灵活地运用如同精巧的舞蹈(Dancing)。 因此这对基于双向链表(Links)的操作(1)与操作(2)在有哪些信誉好的足球投注网站技术上的互动应用，被Knuth定义为Dancing Links。 Dancing Links 更多的细节，参见 /~uno/papers/dancing-color.ps.gz 作 业 书面作业（下周一交）： 设计一个算法，删除一个顺序表中从第i个元素开始的k个元素。 设计一个非递归算法在O(n)时间内将一个含有n个元素的单链表逆置，要求其辅助空间为常量。 定义双向链表类，实现在某个元素之前插入一个元素的操作。 * 双链表及其结点类型的说明 template class T class Link { public: T data; // 用于保存结点元素的内容 LinkT * next; // 指向后继结点的指针 LinkT *prev; // 指向前驱结点的指针 // 给定值和前后指针的构造函数 Link(const T info, LinkT* preValue = NULL, LinkT* nextValue = NULL) { data = info; next = nextValue; prev = preValue; } // 给定前后指针的构造函数 Link(LinkT* preValue = NULL, LinkT* nextValue = NULL) { next = nextValue; prev = preValue; } } * 双链表的插入 如果要在p所指结点后插入一个新结点 执行new q开辟结点空间； 让该新结点的next填入p所指的后继地址； 新结点的prev填入p所指结点的后继的prev字段； new q; q-next = p- next; q-prev = p- next -prev; 把新结点的地址填入原p所指结点的next字段； 新结点后继结点的prev字段也应该回指新结点 p- next = q; q- next -prev = q; * ki-1 ki ki+1 p p?next ? q x q ? prev = p; q ? next = p ? next; p ?next ? prev = q; p ? next = q; 双链表插入示意 * 双链表的删除 如果要删除指针变量 p 所指的结点，只需修改该结点前驱的 next 字段和该结点后继的prev字段，即 p- prev - next = p- next; p- next - prev = p- prev; 然后把变量p变空，把p所指空间释放即可 p- next = NULL; p-prev = NULL; delete p; * ki-1 ki ki+1 p p? prev ? p? next ? p ? prev ? next = p ? next p ?next ? prev = p? prev prev next 双链表删除示意 * 循环链表(circularly linked list) 将单链表或者双链表的头尾结点链接起来，就是一个循环链表 不增加额外存储花销，却给不少操作带来了方便 从循环表中任一结点出发，都能访问到表中其他结点 * 几种链表比较 * 链表的边界条件 几个特殊点的处理 头指针处理 非循环链表尾结点的指针域保持为NULL 循环链表尾结点的指针回指头结点 链