q-next=C-next;C-next=q;//将摘下的结点q作为开始结点插入C表
}
//若pa表非空，则处理pa表
while
//若pb表非空，则处理pb表
while
return;
}
该算法的时间复杂度分析如下：
算法中有三个while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间复杂度O
2.14 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点，同时释放被删结点的空间，这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。
解：
要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点。由于为已知其是有序链表，则介于min 和max之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min结点中的最小结点的直接前趋结点p后，依次删除小于max的结点，直到第一个大于等于max结点q位置，然后将p结点的直接后继指针指向q结点。
算法如下：
void DeleteList
p-next=q;//将p结点的直接后继指针指向q结点
}
2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
解：
本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。
具体算法：
void DeleteList
else q=q-next;
p=p-next;
}
}
2.16 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点s的直接前趋结点。
解：
已知指向这个结点的指针是s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向s的直接前趋，然后用后删结点法，将结点s的直接前趋结点删除即可。
算法如下：
void DeleteNode
注意：
若单循环链表的长度等于1，则只要把表删空即可。
2.17 已知由单链表表示的线性表中，含有三类字符的数据元素，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
解：
要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。
算法如下：
//设已建立三个带头结点的空循环链表A，B，C且A、B、C分别是尾指针.
void DivideList
else if
else
}
}//结束
2.18 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。
解：
LocateNode运算的基本思想就是在双向链表中查找值为x的结点，具体方法与单链表中查找一样。找到结点p后给freq域的值加1。由于原来比p结点查找频度高的结点都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于p结点频度的结点q后，将p结点从原来的位置删除，并插入到q后就可以了。
算法如下：
//双向链表的存储结构
typedef struct dlistnodeDListNode;
typedef DListNode DLinkList;
void LocateNode
}
} |
