for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; va.length++; }/*Insert_SqList*/
2．设 A=（a1，a2，?，am） 和 B=（b1，b2，?，bn）均为顺序表，试设计一个比较A，B大小的算法（请注意：在算法中，不要破坏原表A和B）。
【算法分析】比较顺序表A和B，并用返回值表示结果，值为1，表示A>B；值为-1，表示A 1）当两个顺序表可以互相比较时，若对应元素不等，则返回值为1或-1； 2）当两个顺序表可以互相比较的部分完全相同时，若表长也相同，则返回值为0；否则，哪个较长，哪个就较大 【算法源代码】 int ListComp(SqList A,SqList B) { for(i=1;i<=A.length&&i<=B.length;i++) if(A.elem[i]!=B.elem[i]) return A.elem[i]>B.elem[i]?1:-1; if(A.length==B.length) return 0; return A.length>B.length?1:-1; /*当两个顺序表可以互相比较的部分完全相同时，哪个较长，哪个就较大*/ }/*ListComp */ 3．已知指针 ha和 hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试设计一个算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。 【算法分析】 1）单链表ha的头结点作为连接后的链表的头结点，即hc=ha； 2）查找单链表ha的最后一个结点，由指针p指向，即p->next==NULL； 3）将单链表hb的首元结点（非头结点）连接在p之后，即p->next=hb->next； 4）回收单链表hb的头结点空间 【算法源代码】 void ListConcat(LinkList ha,LinkList hb,LinkList *hc) /*把链表hb接在ha后面形成链表hc*/ { *hc=ha; p=ha;/*由指针p指向ha的尾元结点*/ p=p->next; p->next=hb->next; free(hb); }/*ListConcat */ 4．试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT（L，i，b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。 【算法分析】 1）生成新结点存放元素b，由指针new指向； 2）将new插入在单链表的第i个元素的位置上：若i==1，new插在链表首部；否则查找第i-1个结点，由指针p指向，然后将new插在p之后。 【算法源代码】 void Insert(LinkList *L,int i,int b) { LinkList new; 5 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