数据结构代码集训day8（适合考研、自学、期末和专升本）
习题来自B站up：白话拆解数据结构!
题目如下：
（1）在递增有序的单链表L中，删除值重复的结点
（2）使带头节点单链表的值递增有序
题1
和之前顺序表那题差不多，因为是有序的，所以值重复的必定挨着，首先要有一个指针来遍历链表，还需要一个指针在该指针的前面，一是用来比较相邻值的大小，而是充当前驱指向删除操作。
Linklist del_same(Linklist &L){
if (!L || !L->next) return L; // 边界条件判断
Lnode *p,*q; // 提到的俩指针
p=L->next;
q=p->next;
while(q){
if(p->data==q->data){
p->next=q->next; //删除操作
free(q);
q=p->next;
}
else{
p=p->next;
q=q->next;
}
}
return L;
}
实践：
完整代码如下：
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
// 单链表结构体定义
typedef struct Lnode{
int data;
Lnode *next;
}Lnode,*Linklist;
Linklist list_insertbytail(Linklist &L){
Lnode *s;
int x;
L = (Lnode*)malloc(sizeof(Lnode));
L->next = NULL;
Lnode *r = L;
cin >> x;
while(x!=9999){
s = (Lnode*)malloc(sizeof(Lnode));
s->data=x;
s->next=NULL;
r->next = s;
r=r->next;
cin >> x;
}
return L;
}
// 在递增有序的单链表L中，删除值重复的结点
Linklist del_same(Linklist &L){
if (!L || !L->next) return L;
Lnode *p,*q;
p=L->next;
q=p->next;
while(q){
if(p->data==q->data){
p->next=q->next;
free(q);
q=p->next;
}
else{
p=p->next;
q=q->next;
}
}
return L;
}
int main(){
Linklist L;
// list_insertbyhead(L);
list_insertbytail(L);
Lnode *p = L->next;
printf("origin list:");
while (p != NULL) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
del_same(L);
printf("new list:");
Lnode *q = L->next;
while (q != NULL) {
printf("%d-> ",q->data);
q = q->next;
}
printf("NULL");
return 0;
}题2
这个题需要借助直接插入排序的思想，将链表的第一个结点next域置为空，将第一个元素视为有序区，断开的链表视为无序区，每次将无序区的一个链表结点插入到有序区中。
具体来说在有序区和无序区各需要两个指针。有序区的两个指针：p用来遍历已排序部分，用于找到比 q->data 大或相等的节点，即插入位置；辅助指针s，指向 p 的前驱节点，用于在找到插入位置后，调整指针完成插入操作。无序区的两个指针：q为当前正在进行插入排序的节点（待插入的结点）；t用来暂存 q 的下一个节点，保证在当前节点 q插入完后，能够继续遍历链表。
Linklist sort_list(Linklist &L){
if (!L || !L->next || !L->next->next) return L;
Lnode *p,*q,*s;
p=L->next;
q=p->next;
p->next=NULL; // 分割有序区和无序区
while(q){
Lnode *t=q->next;
s=L;
p=L->next;
while (p && p->data < q->data) { // 寻找插入位置
s = p;
p = p->next;
}
q->next = p;
s->next=q;
q=t;
}
return L;
}
实践：
完整代码如下：
#include <iostream>
#include <cstdio>
#include <ctime>
using namespace std;
// 单链表结构体定义
typedef struct Lnode{
int data;
Lnode *next;
}Lnode,*Linklist;
Linklist list_insertbytail(Linklist &L){
Lnode *s;
int x;
L = (Lnode*)malloc(sizeof(Lnode));
L->next = NULL;
Lnode *r = L;
cin >> x;
while(x!=9999){
s = (Lnode*)malloc(sizeof(Lnode));
s->data=x;
s->next=NULL;
r->next = s;
r=r->next;
cin >> x;
}
return L;
}
// 使带头节点单链表递增有序
Linklist sort_list(Linklist &L){
if (!L || !L->next || !L->next->next) return L;
Lnode *p,*q,*s;
p=L->next;
q=p->next;
p->next=NULL;
while(q){
Lnode *t=q->next;
s=L;
p=L->next;
while (p && p->data < q->data) {
s = p;
p = p->next;
}
q->next = p;
s->next=q;
q=t;
}
return L;
}
int main(){
Linklist L;
// list_insertbyhead(L);
list_insertbytail(L);
Lnode *p = L->next;
printf("origin list:");
while (p != NULL) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
sort_list(L);
printf("new list:");
Lnode *q = L->next;
while (q != NULL) {
printf("%d-> ",q->data);
q = q->next;
}
printf("NULL");
return 0;
}