心双2024数据结构1006-1010题解-xiwwwix's blog

1006. 线性链表的插入与删除

实现线性链表的插入与删除操作，只需要补全插入和删除函数的定义
注意题目里还提到了head指向链表的首元结点，如果链表为空，head为NULL

插入操作中：
tar，val表示将存放新值val的节点插入到值为val的节点之后，保证链表如果不为空就一定有tar，如果有多个tar插在第一个后面，如果链表为空将head指向这个新的节点

删除操作中：
tar表示删除存放值为tar的节点（若有多个节点存放的值是tar，则删除第一个）
如果链表为空则忽略当前操作

思路

先看一眼主函数，发现已经定义了头结点

对于插入操作，因为无论如何都要插进去一个新节点，所以可以先创建一个new_node（C风格就用malloc，C++用new）
然后判断链表是否为空（也即head是否为NULL，在题目定义结构体的下面那行写了），如果为空则将head指向这个新的节点，如果不为空则从头结点开始遍历，直到找到值为tar的结点
对于删除操作，首先判断链表是否为空（还是head是否为NULL），链表为空则忽略
然后遍历链表直到找到值为tar的结点即可
因为是单向链表，所以需要维护两个结点，一个pre表示“前一个结点”，一个tmp表示“当前结点”，删除操作可以被分解成两个部分：
- 将pre结点的next指向tmp的next
- 删除tmp结点（C语言用free，C++使用delete，注意这两个不能混着使用）

顺带注意一下，根据主函数要求，插入和删除函数都需要返回的是头结点的指针

参考代码：


// 插入操作函数：在链表中找到值为 tar 的节点，并在其后插入一个新节点，值为 val
NODE* insertLinklist(NODE* head, int tar, int val) {
    // 创建一个新节点，并初始化它的值和指针
    NODE* new_node = new NODE;  // 动态分配内存
    new_node->data = val;       // 为新节点赋值
    new_node->next = nullptr;   // 新节点的 next 指针设为 nullptr，C语言写成 NULL

    // 如果链表为空（即 head 为 nullptr），则将新节点作为链表的头节点
    if (!head) {
        head = new_node;  // 新节点成为头节点
        return head;      // 返回更新后的链表
    }

    // 如果链表不为空，遍历链表，找到值为 tar 的节点
    NODE* tmp = head;
    while (tmp && tmp->data != tar) {
        tmp = tmp->next;  // 向下一个节点移动
    }

    // 如果找到了值为 tar 的节点，则将新节点插入到该节点后面
    if (tmp) {
        new_node->next = tmp->next;  // 新节点的 next 指向 tar 节点的下一个节点
        tmp->next = new_node;        // tar 节点的 next 指向新节点
    }

    // 返回链表的头节点
    return head;
}

// 删除操作函数：在链表中找到值为 tar 的第一个节点并删除它
NODE* deleteLinklist(NODE* head, int tar) {
    // 如果链表为空，直接返回（不做任何操作）
    if (!head) {
        return head;  // 返回空链表
    }

    // 如果要删除的节点是头节点，直接将头节点删除，并将链表头指向下一个节点
    if (head->data == tar) {
        NODE* temp = head;   // 暂存当前头节点的指针
        head = head->next;   // 将头节点移动到下一个节点
        delete temp;         // 释放之前头节点的内存
        return head;         // 返回更新后的链表
    }

    // 如果要删除的节点不是头节点，遍历链表
    NODE* tmp = head;
    NODE* pre = nullptr;  // 用来跟踪当前节点的前一个节点
    while (tmp && tmp->data != tar) {
        pre = tmp;         // 记录前一个节点
        tmp = tmp->next;   // 移动到下一个节点
    }

    // 如果找到了值为 tar 的节点，则将它从链表中删除
    if (tmp) {
        pre->next = tmp->next;  // 前一个节点的 next 指向要删除节点的下一个节点
        delete tmp;             // 释放要删除节点的内存
    }

    // 返回链表的头节点
    return head;
}

题目没给判题细节和数据范围，假设原链表长度为n，操作次数为q，最坏情况下每次插入或删除都在尾部，都需要遍历整个链表，时间复杂度O(nq)

1007. 环形双向链表的删除操作

主要有3个部分的操作：

第一部分，根据输入值构建环形双向链表
第二部分，获取输入值，这个值的结点在链表中不存在则输出-1，存在则删除所有相同值的结点
最后输出所有剩下的结点

难点：环形双向链表的具体实现；遍历时怎么删除所有和目标值相同的结点

对应到写代码的话，主要是要做这几件事：

定义链表结点，因为是双向的链表，所以需要定义pre和next两个指针
一个函数用来插入结点
用于删除的函数
（可选）将最后打印剩余结点的操作也封装成函数

插入：

在插入操作中，每次将新节点插入到当前链表的尾节点之后，并更新尾节点的next指针以及头节点的pre指针。
首先创建一个新节点，设置该节点的pre和next为NULL

如果链表为空（即链表只有头节点），将新节点插入到头节点后面，建立新节点与头节点的前后关系。
如果链表非空，找到链表的尾节点，将新节点插入到尾节点后面

删除：

注意维护一个flag用来判断有没有找到目标值

#include <bits/stdc++.h>
using namespace std;

// 定义链表节点结构
struct NODE {
    int data;       // 存储节点的值
    NODE* pre;      // 指向前驱节点
    NODE* next;     // 指向后继节点
};

// 创建节点的函数
NODE* createNode(int data) {
    NODE* p = (NODE*)malloc(sizeof(NODE));  // 分配节点的内存
    p->data = data;    // 设置节点的数据
    p->pre = NULL;     // 初始化前驱节点为空
    p->next = NULL;    // 初始化后继节点为空
    return p;
}

// 初始化链表的头节点
NODE* head = createNode(NULL);

// 插入节点到环形双向链表
void Insert(int num) {
    NODE* newNode = createNode(num);  // 创建新节点
    // 如果链表为空，插入到头节点之后
    if (head->next == head) {
        head->pre = newNode;
        head->next = newNode;
        newNode->pre = head;
        newNode->next = head;
    } else {
        // 插入到尾节点之后，保持环形结构
        NODE* lastNode = head->pre;
        head->pre = newNode;
        lastNode->next = newNode;
        newNode->next = head;
        newNode->pre = lastNode;
    }
}

// 删除链表中所有值为num的节点
void Delete(int num) {
    NODE* tmp = head->next;
    bool flag = false;  // 用于判断是否找到待删除节点
    while (tmp != head) {
        if (tmp->data == num) {
            flag = true;
            NODE* preNode = tmp->pre;
            NODE* nextNode = tmp->next;
            preNode->next = nextNode;  // 更新前驱节点的后继指针
            nextNode->pre = preNode;   // 更新后继节点的前驱指针
            NODE* toDelete = tmp;  // 保存待删除节点
            tmp = tmp->next;       // 继续遍历
            // free(toDelete);     // 如果需要释放内存，可取消注释
        } else {
            tmp = tmp->next;  // 如果当前节点不匹配，继续下一个节点
        }
    }
    // 如果没有找到任何待删除的节点，输出-1
    if (!flag) {
        printf("%d\n", -1);
    }
}

// 输出链表中剩余的所有节点
void printNodes(void) {
    NODE* tmp = head->next;
    while (tmp != head) {
        printf("%d ", tmp->data);  // 输出节点数据
        tmp = tmp->next;
    }
}

int main() {
    int num;
    bool flag = false;  // 控制插入和删除的状态
    // 初始化头节点的前驱和后继为自身，形成环形结构
    head->next = head;
    head->pre = head;

    while (cin >> num) {
        if (num == -1) {
            // 首次遇到-1，表示进入删除阶段
            if (!flag) {
                flag = true;
            } else {
                // 再次遇到-1，表示结束输入，输出剩余节点
                printNodes();
                break;
            }
        } else {
            // flag为false时，插入节点
            if (!flag) {
                Insert(num);
            } else {
                // flag为true时，执行删除操作
                Delete(num);
            }
        }
    }
    return 0;
}

1008. 线性表去重

C语言课上应该做过基本一样的题目

这题有三类做法：

1.（C语言课上同款）先排序，然后遍历，跳过重复的值，只输出不重复的

注意特判头或尾，这里代码的思路是先输出第一个数，从第二个数开始，只有该数与前一个数不相同时才输出

#include <bits/stdc++.h>

using namespace std;

int nums[1005];

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    sort(nums, nums + n);

    printf("%d ",nums[0]);

    for (int i = 1; i < n; ++i) {
        if (nums[i] != nums[i - 1]) {
            cout <<  nums[i] << " ";
        }
    }
    cout << endl;

    return 0;
}

复杂度O(nlogn)，瓶颈在排序

2.计数排序

如果发现一道题的复杂度瓶颈在于排序，而且元素的值域不大（小于1e7），就可以考虑使用计数排序
何为计数排序

简单来说，就是巧妙利用数组下标，比如说你现在的数组A = [1,1,3,2,1,2]，值域是1~3，那么你就可以开一个新的数组C，用C[i]表示A数组中数字i出现了几次，于是得到C = [0,3,2,1]（0开始索引）

然后，如果你想输出排序后的C数组，相当于只要遍历它，输出C[i]次i的值就可以了
例如i = 1时C[i] = 3，说明原数组中1出现了3次，需要输出3个1

而在这道题中，因为重复的数只要输出一遍，所以可以将刚刚的int数组C改成一个bool数组exist，用exist[i]表示原数组中是否出现过数字i，这样更省空间

设原数组长度为n，值域大小为m，时间复杂度O(n+m)。所以说，在值域不大的情况下，计数排序是一种好用的算法


#include <bits/stdc++.h>

using namespace std;

bool exist[105];

int main() {
	int n,num;
	cin>>n;
	for (int i = 0;i < n;i++) {
		cin>>num;
		exist[num] = true;
	}
	for (int j = 0;j<=101;j++) {
		if (exist[j]) {
			printf("%d ",j);
		}
	}
	return 0;
}

3.哈希表

和计数排序法思路大同小异，就是记录出现过的数字即可

1009. 线性表顺序查找

签到，直接遍历，题目有注明没有重复值，所以找到后直接输出并结束程序即可

#include <bits/stdc++.h>
using namespace std;

int nums[10005];

int main() {
	int n,v;
	cin>>n;
	for (int i = 0;i < n;i++) {
		cin>>nums[i];
	}
	cin>>v;
	for (int i = 0;i < n;i++) {
		if (nums[i] == v) {
			printf("%d",i);
			return 0;
		}
	}
	printf("%d",-1);
	return 0;
}

时间复杂度显然O(n)

1010. 线性表二分查找

笑点解析：数据比较水，上一题的代码cv大法也能过


#include <bits/stdc++.h>
using namespace std;

// 定义一个大小为 1000005 的数组，用于存储输入的数字
int nums[1000005];

int main() {
	int n, v;
	// 输入数组的大小 n
	cin >> n;
	// 输入 n 个数字存入数组 nums 中
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	// 输入要查找的目标值 v
	cin >> v;

	// 定义左右边界，l 为左边界，r 为右边界
	int l = 0, r = n - 1;

	// 开始进行二分查找，当左边界小于等于右边界时，继续查找
	while (l <= r) {
		// 计算中间位置，采用移位运算 (>>1) 以提高效率
		int mid = (l + r) >> 1;

		// 如果中间值小于目标值 v，则将左边界移动到 mid + 1，缩小查找范围
		if (nums[mid] < v) {
			l = mid + 1;
		}
		// 如果中间值等于目标值 v，输出 mid（即找到目标值所在的索引）
		else if (nums[mid] == v) {
			printf("%d", mid);
			return 0;  // 查找成功，程序退出
		}
		// 如果中间值大于目标值 v，则将右边界移动到 mid - 1，缩小查找范围
		else {
			r = mid - 1;
		}
	}

	// 如果未找到目标值 v，输出 -1 表示查找失败
	printf("%d", -1);
	return 0;
}

稍微提一句，int mid = (l + r) >> 1;这句代码不是特别好，一些题里l + r很大，可能达到int类型上限的话，就会遇到溢出问题
来自一位巨佬的比较好的写法：int mid = l + (r - l) / 2;

二分的写法其实有很多种，但无非就是l、r、mid怎么取，还有循环结束条件不同

个人比较喜欢这个，也觉得比较好记，记住while (l <= r)、l = mid + 1;、r = mid - 1;这三句就行