数据结构单链表的实现 数据结构之单链表基本运算的实现[15]

数据结构之单链表基本运算的实现[15]  

　　图 静态链表

　　静态链表在算法设计中也有比较广泛的应用 如前面所述的用顺序表求解约瑟夫问题 其每次出列都必须删除这个元素 我们知道顺序表删除元素需移动大量元素 利用静态链表的思想来求解约瑟夫问题时可以避免移动大量元素 读者可试着写出利用静态链表求解约瑟夫问题的算法并和例 的算法进行比较

　　【例 】假设有两个元素值递增有序的线性表A和B 均以带头结点的单链表作为存储结构 编写算法将A和B归并成一个按元素值递增有序排列的线性表C 并要求利用原线性表A和B的结点空间存放线性表C

　　算法思路 利用A B两表有序的特点 依次扫描A和B的元素 比较当前的元素的值 将当前值较小者摘下 插入到C表的尾部 如此直到一个单链表扫描完毕 然后将未完的那个单链表中余下部分连到C即可