while( q && q->data < max ) //找比max小的最后一个元素位置
{
q=q->next;
}
h=p->next;
p->next=q;//把断点链上
free(h);// 释放空间
}
--------------------------------------------------------------------------------
(答案及点评) 2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
2.15 解：
本题 可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。
第二种算法是将单链表按值的大小排序，排好后的结点按相同的删除。
具体算法略。
--------------------------------------------------------------------------------
(答案及点评) 2.16 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。
2.16 解：
已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的，把这个结点删除就可以了。
算法如下：
void DeleteNode( ListNode *s)
{
//删除单循环链表中指定结点的直接前趋结点
ListNode *p, *q;
p=s;
while( p->next->next!=s)
{
q=p; /
p=p->next;
}
q->next=s; //删除结点
free(p); //释放空间
}
--------------------------------------------------------------------------------
(答案及点评) 2.17 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
2.17 解：
要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。
算法如下：
//设已建立三个带头结点的空循环链表A,B,C.
//以下是
void DivideList( LinkList L, LinkList A, LinkList B, LinkList C)
{
ListNode *p=L->next, *q;
ListNode *a=A,
ListNode *b=B;
ListNode *c=C;
while ( p )
{
if ( p->data>='a' &&p->data<='z'|| p->data>='A' &&p->data<='Z')
{
q=p;//保存字母结点位置
p=p->next;//指向下一结点
a->next=q;//将字母结点链到A表中
q->next=A;// 形成循环链表
a=a->next; // 指向下一结点
}
else if( p->data>='0' && p->data<='9')
{// 分出数字结点
q=p;
p=p->next;
b->next=q;
q->next=B;
b=b->next;
}
else
{//分出其他字符结点
q=p;
p=p->next;
c->next=q;
q->next=C;
c=c->next;
}
}
}//结束
--------------------------------------------------------------------------------
(答案及点评) 2.18 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,s)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。
2.18 解：
给freq域的值加1比较容易。就是每次加1后需进行排序比较麻烦。我们可以这样考虑，每次访问一个值为x的结点后，从表头开始找，根据结点中的freq值，如果找到比它小的结点，就把当前结点摘下，插入到freq值比它小的结点前面，就完成排序了。
算法如下：
void LocateNode( LinkList L, DataType x)
{
ListNode *p, *q;
p=L->next;//带有头结点
q=L->next;
while( p )
{
if( p->data!=x) p=p->next;
else {
p->freq++;
break;
}
}
while ( q )
{
if( q->freq > p->freq) q=q->next;
else {
p->prior->next=p->next; //摘下当前结点
p->next=q; //插入到freq不大于它的结点前
p->prior=q->p
}
}
}
--------------------------------------------------------------------------------
第二章 线性表 复习要点
本章复习要点是：
线性表的逻辑结构特征、常见的线性表的六种基本运算，并可以根据这些基本运算组合得到更复杂的运算。
顺序表的特征、顺序表中结点地址的计算。
顺序表上实现的基本运算(算法)：主要是插入和删除的算法。顺序表的算法应该掌握。算法时间复杂度要记住。
单链表的特征、图形表示法。
单链表的各种算法实现，并能运用这些算法解决一些简单问题；
循环链表的特征、双链表的特征以及它们的主要算法实现。
可能出的题型有：填空题、简答题、应用题和算法题.
如：
在双链表中插入运算的时间复杂度为：(...)
A.O(1) B.O(n) C.O(lgn) D.O(nlgn)
请问头指针，开始结点和头结点的区别与联系。
关于单链表上进行排序的算法设计。 等等
