new=(LinkList*)malloc(sizeof(LNode)); new->data=b; if(i==1)
{/*插入在链表头部*/ New->next=*L; *L=new; } else
{ /*插入在第i个元素的位置*/ p=*L;
while(--i>1) p=p->next;
new->next=p->next;p->next=new; }
}/*Insert */
5．已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值大于 mink且小于 maxk的元素（若表中存在这样的元素），同时释放被删结点空间（注意：mink和maxk是给定的两个参变量。它们的值可以和表中的元素相同，也可以不同）。 【算法分析】
1）查找最后一个不大于mink的元素结点，由指针p指向；
2）如果还有比mink更大的元素，查找第一个不小于maxk的元素，由指针q指向； 3）p->next=q，即删除表中所有值大于 mink且小于 maxk的元素。 【算法源代码】
void Delete_Between(LinkList *L,int mink,int maxk) {
p=*L;
while(p->next->data<=mink) p=p->next; /*p是最后一个不大于mink的元素*/ if(p->next) /*如果还有比mink更大的元素*/ {
q=p->next;
while(q->data
}/*Delete_Between */
6．已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间。 【算法分析】
1）初始化指针p和q，分别指向链表中相邻的两个元素； 2）当p->next不为空时，做如下处理：
①若相邻两元素不相等时，p和q都向后推一步； ②否则，当相邻元素相等时，删除多余元素。 【算法源代码】
void Delete_Equal(LinkList *L) {
p=(*L)->next;q=p->next; /*p和q指向相邻的两个元素*/ while(p->next) {
if(p->data!=q->data) /*若相邻两元素不相等时，p和q都向后推一步*/ {
p=p->next; q=p->next;
6
} else {
while(q->data==p->data) /*当相邻元素相等时删除多余元素*/ {
r=q;
q=q->next; free(r); }
p->next=q;p=q;q=p->next; }/*else*/ }/*while*/
}/*Delete_Equal */
7．试设计一个算法，对带头结点的单链表实现就地逆置。 【算法分析】
1）空表或长度为1的表，不做任何处理； 2）表长大于2时，做如下处理：
①首先将整个链表一分为二，即从链表的第一元素结点处断开； ②逐个地把剩余链表的当前元素q插入到链表的头部。 【算法源代码】
void LinkList_reverse(LinkList L) { if(!L->next||!L->next->next) return; p=L->next; q=p->next; s=q->next;
p->next=NULL; /*从链表的第一元素结点处断开*/ while(s->next) {q->next=p;p=q;
q=s;s=s->next; /*把L的元素逐个插入新表表头*/ }
q->next=p;s->next=q;L->next=s; }/*LinkList_reverse*/
8．设线性表A=（a1，a2，?，am） 和 B=（b1，b2，?，bn），试设计一个按下列规则合并A，B为线性表C的算法，即使得
C=（a1，b1，?，am，bm，bm+1 ，?，bn ）当 m≤n时； 或者
C=（a1，b1，?，an，bn，an+1 ，?，am ）当m＞n时。
线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。 【算法分析】
1）初始化指针p指向链表A的当前元素，指针q指向链表B的当前元素； 2）当链表A和B均为结束时，做如下处理： ①将B的元素插入
②若A非空，将A的元素插入 ③指针p和q同时后移 【算法源代码】
void merge1(LinkList A,LinkList B,LinkList *C) {p=A->next;q=B->next;*C=A; while(p&&q)
{ s=p->next;p->next=q; /*将B的元素插入*/ if(s)
{ t=q->next;
q->next=s; /*若A非空，将A的元素插入*/ }
7
p=s;q=t; /*指针p和q同时后移*/ }/*while*/ }/*merge1 */
9．假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请设计一个算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即 A表和B表）的结点空间构造C表。
【算法分析】按从小到大的顺序依次把A和B的元素插入新表的头部pc处，最后处理A或B的剩余元素。 【算法源代码】
void reverse_merge(LinkList A,LinkList B,LinkList *C) { LinkList pa,pb,pre;
pa=A->next;pb=B->next; /*pa和pb分别指向A和B的当前元素*/ pre=NULL; while(pa||pb)
{ if(pa->data
{ pc=pb;q=pb->next;pb->next=pre;pb=q; } pre=pc; } *C=A;
A->next=pc; /*构造新表头*/ }/*reverse_merge*/
10．已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。 【算法分析】先从B和C中找出共有元素，记为same，再在A中从当前位置开始， 凡小于same的元素均保留(存到新的位置)，等于same的就跳过，到大于same时就再找下一个same。 【算法源代码】
void SqList_Intersect_Delete(SqList *A,SqList B,SqList C)
{i=0;j=0;k=0;m=0; /*i指示A中元素原来的位置，m为移动后的位置*/ while(i<(*A).length&&j else if(B.elem[j]>C.elem[k]) k++; else{ same=B.elem[j]; /*找到了相同元素same*/ while(B.elem[j]==same) j++; while(C.elem[k]==same) k++; /*j和k后移到新的元素*/ while(i<(*A).length&&(*A).elem[i] (*A).elem[m++]=(*A).elem[i++]; /*需保留的元素移动到新位置*/ while(i<(*A).length&&(*A).elem[i]==same) i++; /*跳过相同的元素*/ } }/*while*/ while(i<(*A).length) (*A).elem[m++]=(*A).elem[i++]; /*A的剩余元素重新存储*/ (*A).length=m; }/* SqList_Intersect_Delete*/ 11．设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。 【算法分析】本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开始，将各结点依次插入到有序 8 链表中。 【算法源代码】 void InsertSort (LinkList la) {if(la->next!=NULL) /*链表不为空表*/ {p=la->next->next; /*p指向第一结点的后继*/ la->next->next=NULL; /*直接插入原则认为第一元素有序，然后从第二元素起依次插入*/ while(p!=NULL) {r=p->next;/*暂存p的后继*/ q=la; while(q->next!=NULL&&q->next->data 12．设有一个双向循环链表，每个结点中除有 prior，data和 next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE（L，X）的操作后，被访问的结点（元素值等于X的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的 LOCATE操作的算法。 【算法分析】 1）在双向链表中查找数据值为x的结点，由指针p指向，若找不到，直接返回，否则执行第2步； 2）修改x结点的访问频度freq，并将结点从链表上摘下； 3）顺结点的前驱链查找该结点的位置，即找到一个结点的访问频度大于x结点的访问频度，由指针q指向；若q和p不是相邻结点，调整位置，把p插在q之后。 【算法源代码】 DuLNode * Locate_DuList(DuLinkList *L,int x) { p=(*L)->next; while(p.data!=x&&p!= (*L)) p=p->next; if(p==(*L)) return NULL; /*没找到x结点*/ p->freq++; p->pre->next=p->next;p->next->pre=p->pre; /*将x结点从链表上摘下*/ q=p->pre; while(q->freq<=p->freq&&p!= (*L)) q=q->pre; /*查找插入位置*/ if(q!=p->pre) /*将x结点插入*/ {q->next->pre=p;p->next=q->next; q->next=p;p->pre=q; /*调整位置*/ } return p; }/*Locate_DuList */ 13．已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。 【算法分析】留下三个链表中公共数据，首先查找两表A和B中公共数据，再去C中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O（m+n+p），在查找每个链表时，指针不能回溯。 【算法源代码】 9 LinkList Common(LinkList A, LinkList B, LinkList C) {pa=A->next;pb=B->next; pc=C->next; /*pa，pb和pc是工作指针*/ pre=A; while(pa && pb && pc) /*当三表均不空时，查找共同元素*/ { while(pa && pb) if(pa->data else if(pa->data> pb->data)pb=pb->next; else if (pa && pb) /*处理A和B表元素值相等的结点*/ {while(pc && pc->data {if(pc->data>pa->data) /*处理pa结点，后移指针*/ {u=pa;pa=pa->next;free(u);} else {if(pre==A) /*结果表中第一个结点*/ { pre->next=pa;pre=pa;pa=pa->next} else if(pre->data==pa->data) /*重复结点不链入A表*/ {u=pa;pa=pa->next;free(u);} else {pre->next=pa;pre=pa;pa=pa->next;}/*将新结点链入A表 */ pb=pb->next;pc=pc->next; /* 链表的工作指针后移*/ } } else if(pa==NULL)pre->next=NULL; /*若A表已结束，置A表表尾*/ else /*处理原A表未到尾而B或C到尾的情况*/ {pre->next=NULL; /*置A表表尾标记*/ while(pa!=NULL) /*删除原A表剩余元素。*/ {u=pa;pa=pa->next;free(u);} } } 14．设 head为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数在单链表中是无序的。编一函数，将 head链中结点分成一个奇数链和一个偶数链，分别由p，q指向，每个链中的数据按由小到大排列。程序中不得使用malloc申请空间。 【算法分析】本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用malloc申请空间，这就是要利用原链表空间，随着原链表的分解，新建链表随之排序。 【算法源代码】 discreat(LinkList p, LinkList q, LinkList head) { p=NULL; q=NULL;/*p和q链表初始化为空表*/ s=head; while(s!=NULL) {r=s->next; /*暂存s的后继*/ if(s->data%2==0) /*处理偶数*/ if (p==NULL) {p=s;p->next=NULL;} /*第一个偶数结点*/ else { pre=p; if(pre->data>s->data) {s->next=pre;p=s;}/*插入当前最小值结点*/ else {while (pre->next!=NULL) if (pre->next->data s->next=pre->next; /*链入结点*/ 10