通过阶段性的自习学习，我获得了许多的感悟与思考，受益匪浅。
首先，我的确是一个自控力不是很强的人;在线上学习时，也会有摸鱼的表现存在。对此，我认为自己应该加强自控能力。
学到的东西:
1.从寒假前就开始学习的dfs
深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索图、树等数据结构的算法，其解题思路一般包括以下几个关键步骤：
定义数据结构
- 图或树的表示：用邻接矩阵、邻接表等方式表示图，用节点和指针表示树。
- 辅助数据结构：常使用栈来辅助实现DFS，也可用递归调用栈，还可能用布尔数组记录节点访问状态。
确定递归函数和参数
- 递归函数：函数负责处理当前节点及递归访问相邻节点，参数一般包含当前节点、图或树的结构、访问标记数组等。
- 终止条件：到达目标节点或遍历完所有可达节点时，结束递归。如在树中到达叶子节点，或在图中所有相邻节点都已访问。
标记当前节点
- 访问标记：进入节点后，立刻标记为已访问，防止重复访问造成死循环，可用布尔数组或哈希表标记。
遍历相邻节点
- 寻找相邻节点：根据数据结构找到当前节点的相邻节点，如邻接矩阵中检查同行非零元素，邻接表中遍历链表。
- 递归调用：对未访问的相邻节点递归调用DFS函数，继续深入搜索。
收集结果或执行操作
- 收集信息：根据题目要求，在遍历过程中收集路径、节点值等信息，如求两点间路径，可在递归时记录经过节点。
- 执行操作：对每个节点或符合条件的节点执行特定操作，如计算节点权值和、判断节点是否满足条件等。
恢复状态（可选）
- 回溯处理：某些问题需在递归返回时恢复状态，如在求所有可能解的问题中，可能需撤销当前节点的某些修改，确保不影响其他搜索路径。
2.基本的栈操作
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义栈的结构体
typedef struct Stack {
int top;
int data[MAX_SIZE];
} Stack;
// 初始化栈
void initStack(Stack *s) {
s->top = -1;
}
// 判断栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}
// 入栈操作
int push(Stack *s, int value) {
if (s->top == MAX_SIZE - 1) {
printf("栈已满，无法入栈\n");
return 0;
}
s->data[++(s->top)] = value;
return 1;
}
// 出栈操作
int pop(Stack *s, int *value) {
if (isEmpty(s)) {
printf("栈为空，无法出栈\n");
return 0;
}
*value = s->data[(s->top)--];
return 1;
}
// 获取栈顶元素
int peek(Stack *s, int *value) {
if (isEmpty(s)) {
printf("栈为空，无法获取栈顶元素\n");
return 0;
}
*value = s->data[s->top];
return 1;
}
3.基本的链式结构
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
// 创建新节点
ListNode* createNode(int val) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (newNode == NULL) {
printf("内存分配失败\n");
return NULL;
}
newNode->val = val;
newNode->next = NULL;
return newNode;
}
// 在链表头部插入节点
ListNode* insertAtHead(ListNode* head, int val) {
ListNode* newNode = createNode(val);
newNode->next = head;
return newNode;
}
// 在链表尾部插入节点
ListNode* insertAtTail(ListNode* head, int val) {
ListNode* newNode = createNode(val);
if (head == NULL) {
return newNode;
}
ListNode* current = head;
while (current->next != NULL) {
current = current->next;
}
current->next = newNode;
return head;
}
// 删除指定值的节点
ListNode* deleteNode(ListNode* head, int val) {
ListNode* current = head;
ListNode* prev = NULL;
while (current != NULL && current->val != val) {
prev = current;
current = current->next;
}
if (current == NULL) {
return head;
}
if (prev == NULL) {
head = current->next;
} else {
prev->next = current->next;
}
free(current);
return head;
}
// 遍历链表
void traverseList(ListNode* head) {
ListNode* current = head;
while (current != NULL) {
printf("%d ", current->val);
current = current->next;
}
printf("\n");
}
// 释放链表内存
void freeList(ListNode* head) {
ListNode* current = head;
ListNode* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
}
4.01背包问题及相关拓展，如多重背包问题
#include<stdio.h>
#include<stdlib.h>
struct coin//定义金币结构体，包含质量m，价值v和单位价值rate
{
int m;
int v;
double rate;
};
//比较函数，用于qsort排序，qsort=quicksort（快速搜索）
int cmp(const void *a,const void *b)//cmp=compare
{
struct coin *c1=(struct coin *)a;//将void指针转化为具体类型的指针，例如:int *pa=(int *)a
struct coin *c2=(struct coin *)b;
//按单位价值排序
if(c2->rate>c1->rate)
{
return 1;//c2应该排在c1前面
}
else if(c2->rate<c1->rate)
{
return -1;//c1应排在c2前面
}
else
{
return 0;//相等时顺序不变
}
}
int main()
{
int n,t;
scanf("%d %d",&n,&t);//输入金币种类数n和背包容量t
struct coin coins[n];//创建金币数组
for(int i=0;i<n;i++)
{
scanf("%d %d",&coins[i].m,&coins[i].v);//输入每个金币的质量和价值
coins[i].rate=(double)coins[i].v/coins[i].m;//计算单位价值
}
//按单位价值降序排序金币数组
//调用qsort，对coins数组进行排序，每个元素大小为sizeof(struct coin)，使用cmp函数进行比较，排序后，数组按rate从高到低排列
qsort(coins,n,sizeof(struct coin),cmp);
double total=0.0;//总价值
int remain=t;//剩余背包容量
for(int i=0;i<n;i++)
{
if(remain<0)
{
break;//若背包已满，提前终止循环
}
struct coin c=coins[i];//当前处理的金币
if(c.m<=remain)//若当前金币可以全部装入
{
total+=c.v;//增加总价值
remain-=c.m;//减少剩余容量
}
else//若只能装入部分
{
total+=remain*c.rate;//按比例计算价值
remain=0;//背包容量用尽
}
}
printf("%.2lf\n",total);
return 0;
}
//qsort通过递归地将数组划分为较小的子数组，并对这些子数组进行排序，最终完成整个数组的排序
//qsort会选择一个基准元素，然后遍历数组，将大于等于基准的元素放在左边，小于基准的元素放在右边
//递归排序:对左右两部分分别递归调用qsort，知道每个子数组只有一个元素或为空
//qsort是一个原地排序算法，不需要额外的存储空间
//平均情况:O(n log n),其中n为数组长度
//最坏情况:O(n^2)(当每次选择的基准元素都是最最小或最大时)
在写题时，依赖题解是很大的一个不足之处，在这点上也反映了数学逻辑能力的不足，有时候一个题要写很多遍才会懂，但隔一下又不会写了。这也考验了对题目的举一反三的能力有待提高。
同时，我也意识到，求快、心急、不够专注是我无法高效率获取知识的原因。当一道题很久解不出来的时候，我总是会感到心烦意乱。甚至会去埋怨自己的不够聪明。但是慢慢的我意识到，想要让自己进步，必须让自己静下心来学习。不能急于求成，也不能只求量而不求质。
通过本阶段的学习，我看到了很多努力的伙伴。我能坚持下来也十分感谢学长学姐的监督，让我可以利用寒假的时光。我希望自己可以更加努力地朝目标前进，增加自主学习的能力，更好地利用自己的时间。
