阶段性总结：
树的DFS存储一条路径采用定义一个栈的形式
图的DFS和BFS，存储一条路径 采用数组回溯法
文章目录
- 2018年
- 1.c语言程序设计部分
- 2. 数据结构程序设计部分
- 2019年
- 1.c语言程序设计部分
- 2. 数据结构程序设计部分
- 2020年
- 1.c语言程序设计部分
- 2. 数据结构程序设计部分
2018年
1.c语言程序设计部分
问题1:
思路分析：一个笨方法，假设录入数组是A数组，再创一个数组B，6行3列就够用了，然后遍历两遍A数组，将A数组的奇数放到B数组奇数行，A数组的偶数放到偶数行，最后输出一遍B数组即可，注意记录，最后存有数到哪一行，就输出到哪一行。
代码略
问题2:
从键盘输入一段长度不超过3000个字符的英文，单词之间使用一个或多个空格进行分割
这道题的关键点在于输入进空格啥的，scanf会吞空格，不能用，那就用getchar()
int main()
{
char str[3001];
char a;
int index=0;
while((a=getchar())!='#')
{
str[index++]=a;
}
str[index]='\0';
puts(str);
}
//在别的问题中我们可以把'#'改成EOF，手动结束
至于找最短和最长的单词，遍历一遍字符数组，记录四个量，一个是当前最长字符的长度，当前最短字符的长度，最长字符开始的下标，最短字符开始的下标，
如果不是空格，当前长度++，假如当前是空格，则比较当前长度和最大最小长度的关系，看看是否需要更新，更新就是记录下标和最长最短长度，如何更新下标，就是把当前的index，-当前记录的最大长度或最小长度记录更新，记录完之后，将当前长度置为0
这个代码略显复杂，先省略
问题三：
该问题主要考察单链表的操作
核心是:
1.有序的创建一个链表
2.找到链表的中间结点
具体思路：
插入链表操作，有序的将新结点，插入进当前的链表中。
输入n个链表，
通过找到链表的中间结点，找到链表前一半的最后一个结点，如果是偶数就是前一半的最后一个结点，如果是奇数，返回的就是中间结点，判断一下n是奇数还是偶数还是计算返回就行。
2. 数据结构程序设计部分
1.假设A、D表示入栈出栈，入栈出栈的操作序列可以表示为仅由A、D组成的字符序列否则为非法序列，例如ADDADAAD为非法序列。写出一个算法，判定所给的操作序列是否合法
(1)写出算法思想
(2)写出算法实现
问题分析:送分题
算法思想：
从左往右扫描一遍序列，字符为A，表示入栈，记录一个值sum，sum+1。假如字符为D，则sum减1，若sum的值在扫描过程中小于0，直接判定为非法字符，反之顺利的扫描了一遍，返回合法。
问题2 代码：
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
//先序遍历二叉树，看看是否结构相似
int isSimialrBiTree (BiTree T1,BiTree T2)
{
if(T1==NULL&&T2==NULL) return 1;
else if(T1==NULL||T2==NULL) return 0;
else //此时T1和T2都不为空
{
return isSimialrBiTree(T->lchild&&T->lchild)&&isSimialrBiTree(T->rchild&&T->rchild)
}
}
问题3:
问题分析：图的DFS逐层遍历，DFS如何逐层遍历？关键在于这个K，DFS递归传入K-1，而且这个k在每次调用的时候，就能保证，每一层中k是不一样，回退回到上一层，K又变回了上一层的k。
#define MAXSIZE 100
int visit[MAXSIZE]={0};
int DFS(Graph G, vertexType v, vertexType w, int k) {
if (v == w && k == 0) {
// 如果当前顶点就是目标顶点，并且路径长度正好为k（0表示已经到达），则返回1表示找到路径
return 1;
}
if (k < 0) {
// 如果k小于0，说明路径长度已经超过了要求，应该返回0表示未找到路径
return 0;
}
visit[v] = 1; // 标记当前顶点为已访问
ArcNode *p = G.vertices[v].firstArc; // 注意这里可能是vertices而不是vertice，具体取决于你的Graph结构体定义
while (p != NULL) {
if (visit[p->adjVex] == 0) {
// 如果邻接顶点未被访问过，则递归调用DFS
if (DFS(G, p->adjVex, w, k - 1)) {
// 如果递归调用返回1，表示找到了路径，直接返回1
return 1;
}
}
p = p->nextArc; // 继续遍历下一个邻接顶点
}
visit[v] = 0; // 恢复现场，标记当前顶点为未访问（如果需要回溯的话）
return 0; // 如果所有邻接顶点都被访问过或者没有找到路径，则返回0
}
2019年
1.c语言程序设计部分
1.一个数的平方的层次数等于该数自身的自然数被称为自守数，例如 55=25，2525=625，9376*9376=87909376，求10000以内的自守数。
void function()
{
for(int i=1;i<=10000;i++)
{
int x1=i;
int x2=i*i;
int flag=1; //1代表是自守数
while(x1)
{
int t1=x1%10;
int t2=x2%10;
if(t1!=t2)
{
flag=0;break;
}
x1/=10;
x2/=10;
}
if(flag==1)printf("%d ",i);
}
}
行标为0时，判断每一行前0个数，以此类推，根据行下标，确定判断几个数
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(a[i][j]!=0)
{
return 0;
}
}
}
return 1;
代码思路:
冒泡排序，通过消费项目标号，将结构体排序，然后根据相邻的相同标号，循环一遍消费项目即可统计消费项目号一致的项目。
2. 数据结构程序设计部分
问题1:
翻译题目,这道题要干什么？
首先是要求有序，并且保持递增或递减序列有序且序列最长，所以2，6不算一个序列，而是2，6，9
代码思路:
定义两个指针一个pre先指向开头，一个cur指向pre的next
定义一个flag ，flag=1为递增，flag=2为递减
首先pre与cur判断 pre指针移动之前设置一个tag=0，表示当前序列有只有一个flag值无需进行flag比较，若tag不是0，则需要比较flag，然后若不相同，则pre=pre->next,再重新进行比较
本题较为复杂，代码待整理
问题2:假设二叉树终止为x的结点不少于1个，采用二叉链表存储，编写算法，打印值为x的结点的所有祖先。
解法1:2015年软件工程程序设计题
用的下面的思路
所有祖先不就是DFS，路过的全部结点，思考这个问题，因为路径有多条，必须得先找到x点之后，往上走，才能找到该路径
用bool，中序遍历，先找到该点，如何在if(里面进行递归左子树和右子树)，if里面如果返回true，就打印当前的结点，并返回true，否则返回false
解法2(模版):
采用存储路径，找路径的方法，定义一个数组栈存储路径
这是一个存储DFS某条路径的模板，根据题目要求，确定这个路径是否符合要求
模版：
char stack[100];
int stacklength=0;
void DFS_x(BiTree T,char x)
{
if(T)
{
stack[stacklength++]=T->data;
if(T->data==x)
{
}
DFS_x(T->lchild, x);
DFS_x(T->rchild, x);
stacklength--;
}
}
补全题目:
char stack[100];
int stacklength=0;
void DFS_x(BiTree T,char x)
{
if(T)
{
stack[stacklength++]=T->data;
if(T->data==x)
{
for(int index =stacklength-2;index>=0;index--) //为什么-2？因为祖先不包括结点本身
{
printf("%c ",stack[index]);
}
}
DFS_x(T->lchild, x);
DFS_x(T->rchild, x);
stacklength--;
}
}
问题3:
判断一个无向图是否为连通图，以一个结点开始，记录一下访问结点的个数，若访问结点的个数小于总共结点的个数，则不连通，反之连通
//无向图的遍历，不需要遍历全部的表头，也不需要恢复现场
int visit[100];
int flag=0; //全局变量记录结点个数
void DFS_graph(ALGraph G,VertexType v)
{
visit[v]=1;
flag++;
ArcNode *p=G.vertices[v].firstArc;
while (p!=NULL) {
if(visit[p->adjvex]==0)DFS_graph(G, p->adjvex);
p=p->nextArc;
}
}
int function_DFS(ALGraph G,VertexType v)
{
DFS_graph(G, v);
printf("flag=%d\n",flag);
if(flag!=G.vexnum) return 0;
return 1;
}
2020年
1.c语言程序设计部分
问题1:
void jisuan()
{
int flag=0;
for(int i=1,x=1;;x=x*10)
{
flag++;
if(x!=1) i=i+x;
if(i%1221==0)
{
printf("需要%d个1",flag);
break;
}
}
}
问题2:
键盘输入，冒泡排序，两两比较做差
问题3:
先定义一个新的score结构体数组，过滤掉名次不在前6的，然后根据项目名冒泡排序，然后6个6个一输出
2. 数据结构程序设计部分
问题1:
因为无法得知链表的长度，不能用做差的方式去计算
定义两个指针 一个pre指向第一个元素，一个cur从第一个元素开始，向后移动m个位置，然后两个指针一起移动，当m指向NULL时，pre就指向了答案，这是链表找倒数的模版
问题2:
如何存储图的一条路径呢？
使用数组回溯法，
每次记录path[u]=v;意味着u的前驱是v,每次都记录下来这个
通过回溯的方法找到记录的路径
BFS使用数组回溯法记录，每次在更新visit的时候更新path
// 存储路径的函数
void printPath(int path[], int start, int end) {
if (end == start) {
printf("%d ", start);
} else {
printPath(path, start, path[end]); // 递归回溯
printf("%d ", end);
}
}
// BFS 寻找从顶点 S 到顶点 d 的最短路径
void BFS(ALGraph G, int S, int d) {
int visit[MAXVETEX] = {0}; // 初始化访问数组
int path[MAXVETEX]; // 记录路径的前驱节点
SqQueue Q;
Queue_Init(&Q);
Queue_En(&Q, S);
visit[S] = 1;
path[S] = -1; // 起点没有前驱节点
while (!Queue_Empty(Q)) { // 假设队列不为空，开始循环
int v;
Queue_De(&Q, &v); // 从队列中弹出表头，此时弹出的元素存放在v中
if (v == d) { // 如果找到目标节点，打印路径
printf("Path from %d to %d: ", S, d);
printPath(path, S, d);
printf("\n");
return; // 找到目标节点后直接退出
}
ArcNode *p = G.vertices[v].firstArc;
while (p != NULL) {
if (visit[p->adjvex] == 0) { // 没有被访问过
visit[p->adjvex] = 1; // 更新 visit 数组
path[p->adjvex] = v; // 记录前驱节点
Queue_En(&Q, p->adjvex); // 将该元素加入队列中
}
p = p->nextArc;
}
}
printf("No path found from %d to %d\n", S, d); // 如果找不到路径
}
int main() {
// 初始化图G和顶点S、d，根据实际情况填充图和顶点值
// ALGraph G;
// int S = 0; // 起点
// int d = 4; // 目标点
// BFS(G, S, d);
return 0;
}
DFS中使用数组回溯法
// 打印路径
void printPath(int path[], int start, int end) {
if (end == start) {
printf("%d ", start);
} else {
printPath(path, start, path[end]);
printf("%d ", end);
}
}
// DFS 实现
int DFS(Graph G, int v, int w) {
visit[v] = 1; // 标记当前节点 v 已访问
if (v == w) { // 找到目标节点
printPath(path, 0, w); // 打印路径
return 1; // 返回，表示找到路径
}
// 遍历邻接点
ArcNode *p = G.vertices[v].firstArc;
while (p != NULL) {
if (visit[p->adjvex] == 0) { // 如果邻接点没有被访问
path[p->adjvex] = v; // 记录前驱节点，p->adjvex 是从 v 来的
if (DFS(G, p->adjvex, w)) { // 递归 DFS 寻找路径
return 1; // 找到目标节点，直接返回
}
}
p = p->nextArc; // 继续检查下一个邻接点
}
visit[v] = 0; // 恢复现场，撤销对当前节点的访问标记
return 0; // 没有找到路径，返回 0
}
问题3：删除二叉排序树中所有结点值小于x的结点
如何删除二叉树的一个结点，没啥用这个代码，复习一下
void delete_fuc(BSTree &T) //后序遍历
{
if(T!=NULL)
{
delete_fuc(T->lchild);
delete_fuc(T->rchild);
free(T);
}
}
问题分析模版：
二叉树排序树某结点的删除关键在于将二叉树排序的右子树替换给左子树，并继续判断当前子树，大体上是中序遍历的
BiTree deleteNodesLessThanX(BiTree &T, int x) {
if (T == NULL) return NULL;
// 递归处理左子树
T->lchild = deleteNodesLessThanX(T->lchild, x);
// 如果当前节点小于x，删除该节点，右子树替代当前节点
if (T->data < x) {
BiTNode *temp = T; // 保存当前节点用于删除
T = T->rchild; // 将当前节点替换为右子树
free(temp); // 删除当前节点
// 继续处理新的根节点（即原右子树）
T = deleteNodesLessThanX(T, x);
} else {
// 递归处理右子树
T->rchild = deleteNodesLessThanX(T->rchild, x);
}
return T;
}
![[论文笔记]HERMES 3 TECHNICAL REPORT](https://img-blog.csdnimg.cn/img_convert/f6423071e7a9cc56b3723d63450694cd.png)
