开始学习时间：13:30
学习计划：
1. 看数据结构专业课题
2. 政治一章内容
3. 操作系统专业课题
4. 政治一章内容
5. 数学卷子写完
6. 背英语作文
总结
完成的还是比较不错的，重点还是应该放在数学和专业课的复习上，政治和英语带着看就行了。
需要补习的知识点
* 堆排序
* 段页式之类的基础知识
* 银行家算法
* 信号量相关
数据结构专业课涉及知识点
* 广义表
* 最小生成树(prim算法和kruskal算法 + 两种图的存储结构(邻接矩阵+邻接表))
* 基数排序(桶排序)
* Dijkstra算法求最短路径(类似Prim算法)
* 平衡二叉树
节点的平衡因子-1 0 1（该节点左子树和右子树的深度之差）
旋转（一言难尽）
* 堆排序
试着写了一下代码题，就尼玛离谱，这tm在考场上真的能写出复杂的算法不用debug？？？
// 排序合并两个链表，A 有序， B无序
// 2022第四题
#include <stdio.h>
typedef struct LinkNode{
int num;
struct LinkNode* next;
}LinkNode;
void print(LinkNode* A);
// 选择排序
void SelectSort(LinkNode* A){
LinkNode* i = A->next;
LinkNode* j;
int tmp;
while (i != NULL){
j = i->next;
while(j != NULL){
if (i->num > j->num){
tmp = i->num;
i->num = j->num;
j->num = tmp;
}
j = j->next;
}
//print(A);
i = i->next;
}
}
void add_and_sort(LinkNode* A, LinkNode* B){
LinkNode* before_i; // 临时节点 保持在i前面一格
LinkNode* tmp; // 临时节点
LinkNode* i, * j;
i = A->next;
j = B->next;
before_i = A;
while (i != NULL && j != NULL){
if (i->num < j->num){
before_i = before_i->next;
i = i->next;
continue;
}
// i > j
// 插入
tmp = j->next;
before_i->next = j;
before_i = j;
j->next = i;
j = tmp;
}
// 剩下的接队尾
while( j != NULL ){
before_i->next = j;
j = j->next;
before_i = before_i->next;
}
}
void print(LinkNode* A){
LinkNode* p = A->next;
while (p != NULL){
printf("%d ", p->num);
p = p->next;
}
printf("\n");
}
int main(){
LinkNode* L = new LinkNode; // 头结点
LinkNode* tmp;
tmp = new LinkNode;
tmp->num = 5;
tmp->next = NULL; // 结尾节点置空
L->next = tmp;
tmp = new LinkNode;
tmp->num = 41;
tmp->next = L->next;
L->next = tmp;
tmp = new LinkNode;
tmp->num = 12;
tmp->next = L->next;
L->next = tmp;
tmp = new LinkNode;
tmp->num = 15;
tmp->next = L->next;
L->next = tmp;
tmp = new LinkNode;
tmp->num = 61;
tmp->next = L->next;
L->next = tmp;
tmp = new LinkNode;
tmp->num = 9;
tmp->next = L->next;
L->next = tmp;
tmp = new LinkNode;
tmp->num = 16;
tmp->next = L->next;
L->next = tmp;
tmp = new LinkNode;
tmp->num = 19;
tmp->next = L->next;
L->next = tmp;
tmp = new LinkNode;
tmp->num = 21;
tmp->next = L->next;
L->next = tmp;
tmp = new LinkNode;
tmp->num = 62;
tmp->next = L->next;
L->next = tmp;
print(L);
LinkNode* B = new LinkNode; // 头结点
tmp = new LinkNode;
tmp->num = 6;
tmp->next = NULL; // 结尾节点置空
B->next = tmp;
tmp = new LinkNode;
tmp->num = 70;
tmp->next = B->next;
B->next = tmp;
tmp = new LinkNode;
tmp->num = 41;
tmp->next = B->next;
B->next = tmp;
tmp = new LinkNode;
tmp->num = 14;
tmp->next = B->next;
B->next = tmp;
print(B);
SelectSort(L);
print(L);
SelectSort(B);
print(B);
add_and_sort(L,B);
print(L);
return 0;
}
然后是2022第五题：
#include <stdio.h>
typedef struct BiTreeNode{
int val;
struct BiTreeNode* left;
struct BiTreeNode* right;
}BiTreeNode, *BiTree;
// 递归遍历
void InOrderTraverse(BiTree T){
if(T){
InOrderTraverse(T->left);
printf("%d ", T->val);
InOrderTraverse(T->right);
}
}
// 非递归找度为2的节点
// 使用先序遍历
int search_2_node(BiTree T){
int _count = 0;
BiTreeNode* a[1000] = {0}; //
BiTreeNode* tmp = T;
int p = -1;
p ++;
a[p] = T;
while (p != -1){
tmp = a[p];
p --;
printf("# %d ", tmp->val);
// 查看度是否为2
if (tmp->left != NULL && tmp->right!= NULL){
_count += 1;
}
// 将存在的子节点入栈
if (tmp->right != NULL){
p ++;
a[p] = tmp->right;
}
if (tmp->left != NULL){
p ++;
a[p] = tmp->left;
}
}
return _count;
}
int main(){
BiTree tree = new BiTreeNode;
tree->val = 1;
tree->left = new BiTreeNode;
tree->left->val = 2;
tree->right = NULL;
tree->left->left = new BiTreeNode;
tree->left->left->val = 3;
tree->left->left->left = NULL;
tree->left->left->right = NULL;
tree->left->right = new BiTreeNode;
tree->left->right->val = 4;
tree->left->right->left = new BiTreeNode;
tree->left->right->left->val = 5;
tree->left->right->right = new BiTreeNode;
tree->left->right->right->val = 6;
tree->left->right->right->left = NULL;
tree->left->right->right->right = NULL;
tree->left->right->left->left = NULL;
tree->left->right->left->right = new BiTreeNode;
tree->left->right->left->right->val = 7;
tree->left->right->left->right->left = NULL;
tree->left->right->left->right->right = NULL;
InOrderTraverse(tree);
printf("\n\n\n %d \n", search_2_node(tree));
return 0;
}
0 Comments latest
No comments.