 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》链表【讲解】 |
|
链表采用与顺序表截然不同的存储方式，不必占用连续的存储空间。链表的一个结点包含两部分，一部分是数据，另一部分是指示相邻结点的指针。链表的元素定位就依靠结点的指针来实现。链表的这种结构使得它的插入和删除操作变得方便了，因为不需要像顺序表那样移动元素。
链表的插入删除操作如何实现？ 以单链表为例对链表的插入和删除操作的算法做一下简单说明： 首先认识一下单链表，单链表是结点只有一个后继指针的链表。当结点位于表的最后一个位置的时候，该结点的后继设为空，单链表一般有一个头结点，头结点的后继指向表的第一个结点，如果头结点的后继为空则表为空。 1 插入操作： new->next=p->next; p->next=new; 其中p指向插入位置之前的结点，new是要插入结点的指针。如果插入的位置在表头也就是第一个位置，那么p指向单链表的头结点。 2 删除操作： p->next=p->next->next; 其中p指向删除位置之前的结点，如果删除的位置在表头，那么p指向单链表的头结点。 可见插入、删除两操作实为相同的两个步骤，即： a 查找指定位置的结点 b 修改指针 两者公共的定位操作： （在单链表中对任意结点的定位是一定要从头结点开始的，） p=head; /*head单链表的头指针*/ for(int j=0;p&&j<i;j++) { p=p->next; /*向后移动指针*/ } return p；/*要找的结点地址*/ 插入和删除操作的算法的实现如上面所述，下面来看一下算法的时间复杂度。 经过上面对算法的分析不难看出，长度为n的链表向位置i插入和删除操作算法的时间复杂度是花费在定位结点操作上的。当i在区间[1，length]取值时，语句p=p->next的频度是i-1，否则频度为n。所以插入和删除算法的复杂度为O(n). 前面分析了链表的插入删除操作的算法，分析过程用到单链表。单链表虽然体现了链表在插入和删除操作上的方便，但是它也有不足。 由于单链表只有一个后继指针，所以它的定位操作只能从头结点开始，于是单链表的定位操作就很不方便了。为了避免这点，另一种链表——循环链表应运而生了。 循环链表与单链表的不同在于循环链表的表尾的指针不再为空，而是指向第一个结点，这样整个表就闭合了。从任何结点出发都可以定位到表中所有结点。 尽管循环链表实现了任意位置对表中全部结点的定位，它在定位上还是有明显的缺陷。比如要从一个结点定位这结点的前驱时，就要遍历整个表，在解决类似问题上，循环链表在定位的缺陷就凸现出来了。 为了避免定位操作上的开销，引入了一种新链表——双重链表。双重链表的结点有两个指针，一个指向前驱，一个指向后继，从一个结点既可以向前也可以向后，这样双重链表的定位操作就非常灵活了。因此它的应用也比较广泛。但是，要清楚的认识到循环链表这种定位上的灵活是以结构变复杂为代价的。 思考问题： 为什么在链表中加入头结点？ 学习任务： 使用一个有头结点的单链表实现一个命令行编辑程序，要求能够接受字母a~z，并且支持插入、删除、和改写功能。 [07/10/25] |