【考研复习】24王道数据结构课后习题代码｜2.3线性表的链式表示

总结

• 删除结点：1、2、4
• 就地逆置：5、
• 合并链表
• 分解链表：10、11、
• 去除重复元素：12、
• 并集：14、15
• 循环链表：17、18、19、20
• 头插法、尾插法重点基础必掌握。
• 判断是否有环：21

01 递归删除结点

用函数递归调用删除结点。

void deletex(linklist &L,int x){if(L==NULL) return;lnode *p;if(L->data==x){p=L;L=L->next;free(p);deletex(L,x);}else deletex(L->next,x);
}

02 删除结点

注意删除结点的时候可能断链。

void deletex2(linklist &L,int x){lnode *p=L->next,*pre=L,*q;while(p){if(p->data==x){q=p;p=p->next;pre->next=p;free(q);}else{pre=p;p=p->next;}}
}

03 反向输出

利用函数调用的特性反向输出。

void r_print(linklist L){if(L!=NULL){r_print(L->next);cout<<(L->data)<<" ";}else return;
}
void r_ignore_node(linklist L){if(L->next!=NULL){r_print(L->next);}
}

04 删除最小值

1. 设置保留最小值的指针和其前驱
2. 每次更新最小值

void delete_min(linklist L){lnode *p=L->next,*pre=L;lnode *minp=p,*minpre=pre;while(p){if(p->data<minp->data){minp=p;minpre=pre;}else{p=p->next;pre=pre->next;}}minpre->next=minp->next; //删除最小值结点free(minp);
}

05 逆置

很重要的基础：头插法

void head(linklist &L){lnode *p=L->next,*r;L->next=NULL;while(p){r=p->next;      //记录下一结点p->next=L->next;L->next=p;p=r;}
}

06 链表递增排序

使用插入排序的思想，将头置空之后，扫描最小元素，然后使用尾插法插入头中。

void insert_sort(linklist &L){lnode *p=L->next,*r=p->next,*pre;p->next=NULL;p=r;while(p){r=p->next;pre=L;while(pre->next!=NULL&&pre->next->data<p->data){pre=pre->next;}p->next=pre->next;pre->next=p;p=r;}
}

07 删除区间值

见2题的删除代码，改下if语句即可。

void delete_x_m_n(linklist &L,int m, int n){lnode *p=L->next,*pre=L,*q;while(p){if(p->data<n&&p->data>m){q=p;p=p->next;pre->next=p;free(q);}else{pre=p;p=p->next;}}
}

08 找公共结点

linklist find_same_dot(linklist L1,linklist L2){linklist longlist, shortlist;int dist=0;int len1=length(L1),len2=length(L2);if(len1>len2){longlist=L1;shortlist=L2;dist=len1-len2;}else{longlist=L2;shortlist=L1;dist=len2-len1;}while(dist--) longlist=longlist->next;while(longlist){if(longlist->data==shortlist->data&&longlist->next->data==shortlist->next->data)return longlist;else{longlist=longlist->next;shortlist=shortlist->next;}}return NULL;
}

09 增序输出链表

见6题

void min_output(linklist L){while(L->next){lnode *pre=L,*p=L->next;lnode *minpre=pre, *minp=p;while(p){if(p->data<minp->data){minp=p;minpre=pre;}p=p->next;pre=pre->next;}cout<<minp->data<<" ";minpre->next=minp->next;free(minp);}
}

10 拆分链表–尾插

第一种方法是在A中直接删除。

linklist split_1_1(linklist &A){linklist B = (linklist)malloc(sizeof(lnode));B->next=NULL;lnode *p=A->next,*ra=A;lnode *rb=B,*q;while(p){//向后移一个ra=p;p=p->next;//从A中删除结点q=p;ra->next=p->next;p=p->next;//利用尾插法将结点插入B中rb->next=q;rb=rb->next;}ra->next=NULL;rb->next=NULL;return B;
}

第二种方法是把A的头拿下来，再选最小的排在A后。=尾插==

linklist split_1_2(linklist &A){linklist B = (linklist)malloc(sizeof(lnode));B->next=NULL;lnode *p=A->next,*ra=A;lnode *rb=B;//把表头摘下来A->next=NULL;while(p){//结点给Ara->next=p;ra=ra->next;p=p->next;//结点给Brb->next=p;rb=rb->next;p=p->next;}ra->next=NULL;rb->next=NULL;return B;
}

11 拆分链表–头插

第一种方法同上

linklist split_1_1(linklist &A){linklist B = (linklist)malloc(sizeof(lnode));B->next=NULL;lnode *p=A->next,*ra=A;lnode *rb=B,*q;while(p){//向后移一个ra=p;p=p->next;//从A中删除结点q=p;ra->next=p->next;p=p->next;//利用头插法将结点插入B中q=p->next;p->next=rb->next;rb->next=p;p=q;}ra->next=NULL;return B;
}

第二种方法同上

linklist split_2_1(linklist &A){linklist B = (linklist)malloc(sizeof(lnode));B->next=NULL;lnode *p=A->next,*ra=A;lnode *rb=B,*q;//把表头摘下来A->next=NULL;while(p){//结点给Ara->next=p;ra=ra->next;p=p->next;//结点给Bif(p){q=p->next;p->next=rb->next;rb->next=p;p=q;}}ra->next=NULL;//b是头插法所以最后指向是为NULLreturn B;
}

12 删除相同元素

简单代码，只不过要注意的p是要删除结点的前一个结点，判断的时候别判断错了。

void del_same(linklist &L){lnode *p=L->next,*q;if(p==NULL) return;while(p->next){q=p->next;if(p->data==q->data){p->next=q->next;free(q);}else{p=p->next;}}
}

13 合并链表

void merge(linklist &L1,linklist &L2)
{lnode *p1=L1->next,*p2=L2->next,*r;L1->next=NULL;while(p1&&p2){if(p1->data<=p2->data){r=p1->next;p1->next=L1->next;L1->next=p1;p1=r;}else{r=p2->next;p2->next=L1->next;L1->next=p2;p2=r;}}if(p1) p2=p1;while(p2){r=p2->next;p2->next=L1->next;L1->next=p2;p2=r;}free(L2);
}

14 生成含有公共元素的链表C

1. 两个链表分别遍历，比较值头插入C中

linklist merge_same(linklist &A,linklist &B){lnode *p=A->next,*q=B->next;lnode *r,*s;linklist C = (linklist)malloc(sizeof(lnode));r=C;while(p&&q){if(p->data<q->data){p=p->next;}else if(p->data>q->data){q=q->next;}else{s=(lnode *)malloc(sizeof(lnode *));s->data=p->data;r->next=s;r=r->next;p=p->next;q=q->next;}}r->next=NULL;return C;
}

15 求并集

1. 值不相同时分别删除A和B中的值
2. 相同时删除B中的值
3. 基础就是删除代码

void intersection(linklist &A,linklist &B){lnode *p=A->next,*q=B->next;lnode *r=A,*temp;while(p&&q){if(p->data<q->data){temp=p;p=p->next;free(temp);}else if(p->data>q->data){temp=q;q=q->next;free(temp);}else{//相等的时候保留A中相同元素r->next=p;r=r->next;p=p->next;//删除B中相同的元素temp=q;q=q->next;free(temp);}}while(p){temp=p;p=p->next;free(temp);}while(q){temp=q;q=q->next;free(temp);}r->next=NULL;
}

16 判断子序列

朴素kmp，也有所说bf的

bool simple_kmp(linklist &A,linklist &B){lnode *p=A->next,*q=B->next,*r=A->next;while(p&&q){if(p->data!=q->data){r=r->next;p=r;q=A->next;}else{p=p->next;q=q->next;}}if(q) return false;else return true;
}

17 判断循环链表是否对称

循环链表就方便了，能找前驱和后继，两个指针同时移动判断值即可。

bool symmetry(linklist L)
{lnode *p=L->next,*q=L->prior;while(p!=q&&q->next!=p){if(p->data==q->data){p=p->next;q=q->prior;}else return false;}return true;
}

18 两个循环链表链接

注意头尾即可

void add(linklist &h1,linklist &h2)
{lnode *p=h1->next,*q=h2->next;while(p->next!=h1){p=p->next;}while(q->next!=h2){q=q->next;}p->next=h2->next;//初始化的链表带头结点，若不带h2即可q->next=h1;
}

19 找最小结点并删除

1. 遍历链表每次输出最小结点然后删除即可
   相同代码见9题

void find_min(linklist &L){while(L->next!=L){lnode *pre=L,*p=L->next;lnode *minpre=pre, *minp=p;while(p!=L){if(p->data<minp->data){minp=p;minpre=pre;}p=p->next;pre=pre->next;}cout<<minp->data<<" ";minpre->next=minp->next;free(minp);}free(L);
}

21 判断单链表是否有环

1. 两步走总能相遇，按照这个作为遇到的条件找相遇点和入环结点。
   25题也是两步走。

lnode* findd(lnode *L)
{lnode *f=L,*s=L;while(s!=NULL&&f->next!=NULL){s=s->next;f=f->next->next;if(s->data==f->data) break; //可以直接设置指针，但是我初始化的有单链表为int a[15]={1,2,3,4,5,6,7,8,9,4,5,6,7,8,9};故用这种方法}if(s==NULL||f->next==NULL) return NULL;lnode *p=L,*q=s;while(p->data!=q->data){p=p->next;q=q->next;}return p;
}

22 【2009真题】找倒数第k个元素

1. 相当于用长度为k的尺子比着找，最右端到尾部的时候，最左端就是倒数第k个元素。

int findk(linklist &L, int k){lnode *p=L,*q=L;int count=0;while(p){if(count<k) count++;else q=q->next;p=p->next;}if(count<k) return 0;else cout<<"kth to last position: "<<q->data;return 1;
}

23 【2012真题】相同后缀找起始位置

1. 把尾部排齐：两个指针遍历链表，长度相同时找到相同时尾部对齐了
2. 排齐之后遍历两个链表找第一个不相同的位置，该位置的下一个位置就是相同后缀的位置

typedef struct lnode{int data;struct lnode *next;
}lnode,*linklist;
lnode * find_addr(linklist str1, linklist str2){lnode *p,*q;int m=length(str1);int n=length(str1);for(p=str1;m>n;m--) p=p->next;for(q=str2;m<n;n--) q=q->next;while (p->next!=NULL&&q->next!=NULL){p=p->next;q=q->next;}return p->next;
}

24 【2015真题】删除绝对值相同

要求时间复杂度尽可能高➡️空间换时间

1. 数组存查找状态：0表示绝对值未找到，1表示找到，第二次找到的同时删除该结点
2. 注意动态分配数组的使用（静态数组试了试内存超出，不知道是不是这个问题）

void same(linklist &L,int n)
{lnode *p=L;int *q;q=(int *)malloc(sizeof(int)*(n+1));for(int i=0;i<n+1;i++) *(q+i)=0;int s;lnode *f;while(p->next!=NULL){s=abs(p->next->data);if(*(q+s)==0) {*(q+s)=1;p=p->next;}else{f=p->next;p->next=f->next;free(f);}}free(q);
}

25 【2019真题】重新排列链表

1. 两步走找中间结点
2. 逆置后边链表：使用头插法
3. 看成两个链表进行插入
   21也是两步走

void change(linklist &L){lnode *p,*q,*r,*s;p=q=L;while (q->next){p=p->next;q=q->next;if(q->next) q=q->next;}q=p->next;  //p现在在中间结点p->next=NULL;  //把后半段摘下来，逆置之后分别遍历两个链表插入指定位置while (q)  //头插法实现原地逆置{r=q->next;  //暂存后继结点q->next=p->next;  //将q结点放在头结点p之后p->next=q;q=r;}s=L->next;  //插入点q=p->next;  //后半段数据点p->next=NULL;  while(q){r=q->next;q->next=s->next;s->next=q;s=q->next;q=r;}
}