第2章——线性表习题

（1）依次取两个链表的节点，把小的接过去，依次往后，直到一个链到尾部。把另一个链接上去就行了。

typedef struct Lnode { double num; Lnode *next; }Lnode,*LinkList; void ListMerge(LinkList a,LinkList b) //合并a、b有序链表并存到 a { LinkList p,q; LinkList la; p = a->next; q = b->next; la = a; while (p != NULL && q != NULL) { if (p->num < q->num) { la->next = p; la = p; p = p->next; } else if (p->next > q->next) { la->next = q; la = q; q = q->next; } else { la->next = p; la = p; p = p->next; LinkList t; //储存多余的节点 t = (Lnode *)malloc(sizeof(Lnode)); t = q; q = q->next; free(t); //把重复的节点的内存释放 } } la->next = p ? p : q; //p为空则把q接上，否则把 p 接上 free(b); //把 b 的头结点内存释放 }

（2）和上一个差不多，遇到相等的时候两个都连上去就行了。

typedef struct Lnode { double num; Lnode *next; }Lnode,*LinkList; void ListMerge(LinkList a,LinkList b) //合并a、b有序链表并存到 a { LinkList p,q; LinkList la; p = a->next; q = b->next; la = a; while (p != NULL && q != NULL) { if (p->num < q->num) { la->next = p; la = p; p = p->next; } else if (p->next > q->next) { la->next = q; la = q; q = q->next; } else //相等则都连上去 { la->next = p; la = p; la->next = q; la = q; p = p->next; q = q->next; } } la->next = p ? p : q; //p为空则把q接上，否则把 p 接上 free(b); //把 b 的头节点内存释放 }

（3）遇到相等接到 la 链上，否则释放内存。最后再用递归释放剩余节点的内存即可。

typedef struct Lnode { double num; Lnode *next; }Lnode,*LinkList; void Delete(LinkList L) //递归释放内存 { if (L == NULL) return; Delete(L->next); free(L); } void ListMerge(LinkList a,LinkList b) //合并a、b有序链表并存到 a { LinkList p,q,t; LinkList la; //用a链表的头指针 p = a->next; q = b->next; la = a; while (p != NULL && q != NULL) { if (p->num == q->num) { la->next = p; t = q; p = p->next; q = q->next; free(t); } else if (p->num < q->num) { t = p; p = p->next; free(t); } else { t = q; q = q->next; free(t); } } Delete(p); //释放剩余节点内存 Delete(q); }

（4）仍然跟上面思路差不多，还是一个个往后找，这次的链表重新开一个内存。

typedef struct Lnode { double num; Lnode *next; }Lnode,*LinkList; void ListInsert(LinkList L,LinkList p) //在L链表最后加入p { p->next = NULL; while (L->next == NULL) L = L->next; L->next = p; } void ListMerge(LinkList a,LinkList b) //合并a、b有序链表并存到 a { LinkList p,q; LinkList c; //差集的头指针 p = a->next; q = b->next; while (p != NULL && q != NULL) { if (p->num == q->num) { p = p->next; q = q->next; } else if (p->num < q->num) { ListInsert(c,p); p = p->next; } else { ListInsert(c,q); q = q->next; } } }

突然发现一个问题，我写的对不对也没法判断啊。。。。

还是写算法设计好了，不写代码了。

（5）这个比较简单，直接扫 a 链表即可，数值小于0的节点接到b上，大于0的节点接到c上。最后把a链表的头指针内存释放掉。

（6）用一个变量MAX表示结果，初始值为第一个节点的值，然后对链表遍历，依次更新MAX的值即可。（递归算法）

typedef struct LNode { int num; LNode *next; }LNode,*LinkList; void Query(LinkList L,int MAX,int &ant) /* 数据值大于MAX的存到ant中，ant初始化为0 */ { if (LinkList == NULL) return; if (L->num > MAX) ant++; Quety(L->next,MAX,ant); } （7）写一个递归函数，终止条件为该链的指针域指向空指针，终止时使头指针指向该节点，参数为上一个节点和当前节点。每次递归找下一个节点，然后把子节点的指针域指向父节点。 typedef struct LNode { int num; LNode *next; }LNode,*LinkList; void solve(LinkList &root,LinkList father,LinkList now) { if (now->next == NULL) { now->next = father; root->next = now; return; } solve(root,now,now->next); now->next = father; }

（8）从头结点开始遍历，找到第一个next节点的数值大于mink的节点。然后从该节点继续向后遍历，边指针后移边释放不满足条件的内存，直到节点的值小于maxk退出遍历。

（9）这个。。。。写代码吧：

typedef struct Lnode { data n; //data为随机数据类型 Lnode *prior,*next; }Lnode,*LinkList; void swap(LinkList a,LinkList b) { LinkList t; t = a; a = b; b = t; } void change(LinkList p) { p->prior->next = p->next->next; p->next->prior = p->prior->prior; p->prior->prior = p; p->next->next = p; swap(p->prior,p->next); }

（10）还是写代码吧。

思路：通过线性遍历，遇到等于item的元素使延迟长度 l++ ，后续不是item的元素前移 l 个位置覆盖之前的值即可。复杂度O（n）

typedef struct { int num; }Node; typedef struct { Node *Elem; int MAXSIZE; }LinkList; void Delete(LinkList &L,int item,int n) //目标元素item，长度n { int l = 0; //延迟长度 int i; for (i = 1 ; i <= n ; i++) { if (L.Elem[i].num == item) l++; else L.Elem[i-l] = L.Elem[i]; } n -= l; //重新计算顺序表长度 }