966，967吉大数据结构笔记

2023-12-27 22:18
文章标签 数据结构 笔记 966 吉大 967

本文主要是介绍966，967吉大数据结构笔记，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数据结构

辅导书本无非王道数据结构和天勤，如果你把这两本书看了好几遍，可以看一下数据结构1800，这本书非常不错，它长下面这样子，时间充裕的话就看，紧张的话就直接刷真题吧。
1800题

由于这本书题量过大，建议只看链表，树，图这三个章节，这三个章节侧重选择题和编码题，一些填空题可以忽略，吉大不考这类题型，如果你时间充裕那上面的请自动忽略。还有最重要的一点就是真题，这个务必要过几遍，达到看到题就会做的水准，差不多就130+的水平，吉大的题目不难，很多都是原题，还有以下的一些题型。

顺便一提，今年树和图的算法大题一个都没考。。。。。全是链表还有千年没命过题的文件操作，只能说吉大命题太诡异了。大家务必要重温一下文件操作，很多东西要复习全面，基于去年没考树图代码题，今年考的可能性很大，请大家务必注意，链表大题也不要丢下，也可能杀个回马枪，总之，复习要全面吧。
以下的代码仅供参考，所以部分代码没有备注，每个人的代码习惯不一样，所以大家重点注意的是命题风格以及题型。

以下的所有题型来源于1800题，王道，天勤以及历年真题。

链表题

这里我只写几种常见的类型，还有更多请把王道课后习题多做几遍

//链表的插入排序
void insert(Linklist &L){Lnode *p = L->next;  //如果你看了王道或者天勤应该知道我定义的结构体Lnode *pre;Lnode *r = p->next;p->next = NULL;p=r;while(p!=NULL){r = p->next; //记录下一节点pre = L;while(pre->next != NULL && pre->next->data < p->data)pre = pre->next;   //找到插入位置p->next = pre->next;   // 这行和下面一行都是插入操作pre->next = p;p = r;    //向前推进一个节点}
}

树变形

1，改进的层序遍历（非递归实现计算树的深度以及宽度）

void level(BTNode *p){int front,rear,level = 0,length = 0;int count = 0,width = 1,cursor;  //这里width为宽度，level为深度BTNode *q;if(p != NULL){rear = (reat+1)%maxsize;que[rear] = p;cursor = rear;while(front != rear){front = (front+1)%maxsize;count ++;q = que[front];if(q->lchild != NULL){rear = (rear+1)%maxsize;que[rear] = q->lchild;}if(q->rchild != NULL){rear = (rear+1)%maxsize;que[rear] = q->rchild;}if(front == cursor){  //是否扫描完一层cursor = rear;  //将下一层的最后一个节点赋值给扫描器level ++;    //层数+1width = count > width ? count : width;  //取最大宽度count = 0;   //重新计算下一层}}}
}

图算法

邻接矩阵的图遍历算法

首先，需要我们掌握图的结构体

typedef struct{char data;char info;
} vertexType;
typedef struct {int edges[maxsize][maxsize]int vnums,enums;vertexType vex[maxsize]
}mGraph

基于邻接矩阵的非递归深度优选遍历

void DFS_Nonrecursion(mGraph *G, int visit[], int stackVT){int stack[maxsize];int top = -1;int i,j,curVT;stack[++top] = stackVT;while(top != -1){curVT = stack[top--];cout<<G->vex[curVT].data;for( i = G->vnums-1; i>0; i--){if(G->edges[curVT][i] == 1 && visit[i] == 0){stack[++top] = i;visit[i] = 1;}}}
}

基于邻接矩阵的广度优先遍历

void BFS(mGraph *G, int visit[], int startVT){int i,queue[maxsize],front=0,rear = 0,vertex;queue[++rear] = startVT;while(front != rear){front = (front+1)%maxsize;vertex = queue[front];cout<<G->vex[vertex].data;for(i = 0; i<G->nums;i++){if(G->edges[vertex][i] == 1 && visit[i] == 0){rear = (rear+1) % maxsize;queue[rear] = i;visit[i] = 1;}}}
}

基于邻接矩阵的深度优先遍历（递归）

void DFS(mGraph *G, int visit[], int startVT){int j;cout<<G->vex[startVT].data;for(j = 0; j<G->vnums; j++){if(G->edges[starVT][j] == 1 && visit[j] == 0){visit[j] = 1;DFS(G,visit,j);}}
}

判断图是否有回路（邻接矩阵，有向图）

int flag = 0;
void IsCircle(int n, int v){if(flag == 1)return;   //回路for(int i = 0; i<n; i++){if(visit[i] == 0 && a[v][i] == 1){visit[i] = 1;IsCircle(n,i);visit[i] = 0;}else if(a[v][i] == 1 && v!= i) flag = 1;}
}

书上有拓扑排序的解决方案，邻接表的实现（有向图）天勤
下面是无向图回路的判断（连通图）

void DFS(AGraph *G, int v, int &flag){ArcNode *p;if(visit[v] == 1){flag = 1;return;}visit[v] = 1;p = G->adjlist[v].firstArc;while(p!=NULL){DFS(G, p->adjvex,flag);p = p->nextarc;}
}至此完毕
如果是非连通图
for(i = 0; i<G->n; i++)if(visit[i] == 0)DFS(G,i,flag);
总结下来：
类型时间复杂度空间复杂度
邻接矩阵o(n^2)o(n^2)
邻接表o(n+e)o(n)

后序非递归模板

为了区分同一节点的两次出栈，设置flag。
flag = 1，表示第一次出栈，只遍历完左子树，该节点不能访问
flag = 0， 表示第二次出栈，遍历完右子树，可以访问

typedef struct element{BTNode * ptr;int flag;
}element;

void postorder(BTNode *bt){int top = -1;element *s[maxsize];while(bt != NULL || top != -1){while(bt != NULL){top ++;s[top].ptr = bt;s[top].flag = 1;bt = bt->lchild;}// 标记一while(top != -1 && s[top].flag == 2){//标记二bt = s[top--].ptr;visit[bt->data);}if(top!=-1){s[top].flag = 2;bt = s[top].ptr->rchild;}}
}以上是后序非递归的模板
后序非递归模板可用于根节点到某一节点的路径（在标记一处写代码），也可以求公共祖先（标记二），也可以交换左右子树

求p,q节点的最近公共祖先

BTNode *CommonAncester(BTNode *bt, BTNode*p, BTNode *q){if(bt == NULL || bt == p || bt == q ) return bt;BTNode *left = CommonAncester(bt->lchild,p,q);BTNode *right = CommonAncester(bt->rchild,p,q);if((left == p && right == q) || (left ==q || right == p))return bt;return (left != NULL} ? left:right;
}
// 如果p,q 分别在左右子树中，则根节点就是最近的公共祖先，分别对左右子树进行递归，
// 如果某一子树返回为空，则证明返回上一层寻找。

n个节点的完全二叉树存放在数组A[n]中，建立一棵用二叉链表表示的二叉树根用tree指向。

BTNode *Create(ElementType a[], int i){BTNode * tree;if(i <= n){tree = (BTNode) malloc(sizeof(BTNode));tree->data = A[i];if(2*i > n)tree->lchild = NULL;elsetree->lchild = Create(A, 2*i);if(2*i+1>n)tree->rchild = NULL;elsetree->rchild = Create(A, 2*i+1);}return tree;
}

对上面那棵树进行前序非递归遍历

void preorder(ElemType bt[], int n){int i = 1,top = 0,s[];while(i<= n || top > 0){while(i<n){visit(bt[i]);   //访问根节点if(2*i+1 <= n)s[++top] = 2*i+1;  //柚子树入栈i = 2*i;   //不断访问左子树}if(top>0)i = s[top--];   //开始访问柚子树}
}

由二叉树的中序遍历和后序遍历建立二叉树

BiTree IntoPost(ElemType in[], post[], int l1, int h1, int l2, int h2){//in和post是中序序列和后序序列，l1，h1是第一个和最后一个节点的下标BiTree bt = (BiTree)malloc(sizeof(BiNode));bt->data = post[h2];  //后序序列最后一个元素是根节点for(int i = l1;i<=h1;i++){if(in[i] == post[h2])break;   //在中序序列中查找根节点}if(i == l1)bt->lchild = NULL;elsebt->lchild = IntoPost(in,post,l1,i-1,l2,l2+i-l1-1);if(i == h1)bt->rchild = NULL;elsebt->rchild = IntoPost(in, post, i+1, h1, l2+i-l1,h2-1);return bt;
}

已知满二叉树先序遍历序列，求其后序遍历序列

void change(char pre[], int L1, inr R1, char post[], int L2, int R2){if(L1 <= R2){post[R2] = pre[L1];change(pre, L1+1,(L1+1+R1)/2, post, L2, (L2+R2-1)/2);change(pre, (L1+1+R1)/2+1, R1, post, (L2+R2-1)/2+1, R2-1);}
}先序遍历的第一个元素为根节点，将除第一个元素之外的元素序列分为前后两个相等的序列，前一半
为左子树的节点，后一半为柚子树的节点。只需将根节点移至序列的末尾，再分别递归处理前一半，后一半。

求有向图中邻接表的入度

void indegree(Adjlist g){for(i = 0; i<n; i++){num = 0;  //入度for(j = 0;j<n;j++)if(i!=j){p = g[i].firstarc;while(p){if(p->adjvex == i)num++;p = p->next;}}}
}another way:
for(i =0;i<n;i++){p = G->adjlist[i].firstarc;while(p){indegree[p->adjvex]++; p = p->nextarc;}
}

下面是出度的算法

int out;
void outdegree(AdjList g){for(int i = 0; i< n; i++){out = 0;p = g[i].firstarc;while(p){out++;p = p->nextarc;}cout<<"顶点"<<g[i].vexdata<<"的出度为"<<out;}
}

邻接矩阵转邻接表

void AdjmatrixToAdjList(AdjMatrix gm, AdjList gl){for(i = 0; i<n; i++){cin>>gl[i].vertex;gl[i].firstarc = NULL;}  //初始化for(i = 0;i<n;i++){for(j = 0;j<n;j++){if(gm[i][j] == 1){p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->next = g[i].firstarc;g[i].firstarc = p;}}}
}

已知图邻接链表，设计算法生成相应的逆邻接表，时间复杂度为o(n+e)

void InvertAdjList(AdjList gin, AdjList gout){for(int i = 0; i<n; i++){gin[i].vertex = gout[i].vertex;gin[i].firstarc = NULL;for(int i = 0; i<n;i++){p = gout[i].firstarc;while(p!= NULL){j = p->adjvex;s= (ArcNode*)malloc(sizeof(ArcNode));s->adjvex = i;s->next = gin[j].firstarc;gin[j].firstarc = s;p = p->next;}}}
}

二叉树的查找与删除（真题出现过）

bool DeleteBST(BiTree *T, int key){if(T == NULL)return false;else if(key == T->data){Delete(T);return false;}else if(key < T->data)return DeleteBST(T->lchild, key);elsereturn DeleteBST(T->rchild, key);
}void Delete(BiTree *T){BiTree L;if(T->lchild == NULL && T->rchild == NULL)T = NULL;else if(T->rchild != NULL && T->lchild == NULL)T = T->rchild;else if(T->rchild == NULL && T->lchild != NULL)T = T->lchild;else{L = T->lchild;while(L->rchild) L = L->rchild;  //标注一L->rchild = T->rchild;  // 标注二T = T->lchild;   // 标注三}
}这里的标注一是寻找最右子树，标注二是T的柚子树接到左子树的最右孩子的柚子树，
标注三是T的左子树直接作为T父节点的子树

图的深度非递归遍历

void DFS(graph g, int v){int i;arcnode *p;int visited[vnum],top = -1,stack[vnum];for(i = 0; i<g.vexnum;i++){visited[i] = 0;}visit(v);top++;stack[top] = v;visited[v] = 1;while(top > 0){v = stack[top];--top;p = g.adjlist[v].firstarc;while(p!=NULL && visited[p->adjvex] == 1)p = p->nextarc;if(p == NULL) --top;else{v = p->adjvex;visit(v);visited[v] = 1;top++;stack[top] = v;}}
}

打印vi到vj所有长度为L的简单路径。这类问题有模板，基本上解题思路大同小异，如果理解了这个问题。

int visited[Vnum],A[Vnum];
void dfs(graph *g, int vi, int vj, int L, int d){int v,i;arcnode *p;visited[vi] = 1;d++;A[d] = vi;if(vi == vj && d == L){cout<<"一条路径";   // dfs模板for(i = 0; i<=d; i++)cout<<A[i];return;  // 退出这层递归}p = g->adjlist[vi].firstarc;while(p != NULL){v = p->adjlist;if(visited[v] == 0)dfs(g,v,vj,L,d);p = p->nextarc;}visited[vi] = 0;--d;  //擦除访问标记，使顶点可以重用
}

hash 函数的构造方法

  • 直接定址法
  • 数字分析法
  • 平方取中法
  • 除留余数法

处理冲突的方法

  • 开放定址法
  • 链地址法

开放定址法包括 线性探查法（容易堆积），平方探查法（不能探查表上的所有单元）

a = 装填因子 = {关键字个数 n} / {表的长度 m} a越大，发生冲突的可能性越大，反之则反
散列表的平均查找长度依赖于a，不直接依赖于n 或 m

关于一些方法的总结：
数组的去重，可以先排序后用插入排序的思想，还可以用一个数组来计算元素的个数，计数排序的思想。

用dfs来拓扑排序

void DFS(Graph G, int v){visited[v] = 1;visit(v);p = G->adjlist[v].firstarc;while(p){if(visited[p->adjvex] == 0)DFS(G, p->adjvex);p = p->nextarc;}time = time+1;finishTime[v] = time;
}for(v = 0;v<G.n;v++)if(!visited[v])DFS(G,v);finishTime数组中结束的时间从小到大排列，既为TOPSort

总结图时间复杂度：

类型时间复杂度空间复杂度
广+表o(n+e)o(n)
深+表o(n+e)o(n)
广+矩阵o(n^2)o(n)
深+矩阵o(o^2)o(n)

非递归的快排：

void quickSort_Nonrecursion(int a[], int n){int stack[maxsize];int top = -1;stack[++top] = n-1;while(top >= 0){int high = stack[top--];int low = stack[top--];int m = partition(a,low,high);if(m+1 < high){stack[++top] = m+1;stack[++top] = high;}if(low < middle -1){stack[++top] = low;stack[++top] = middle-1;}}
}partion函数在王道292页

MST专题

prim函数和kruskal函数都是针对无向图

prim

时间复杂度o(v^2)，不依赖|E|，因此适用于稠密图

kruskal

时间复杂度o(log(E))，其实它的时间复杂度由排序算法决定的，而排序规模是由边数e决定的，因此适用于稀疏图

Dijkstra

见天勤，内容太多了。。。。

Floyd

它的核心思想，对每个中间点进行更新一次距离，中间点为两个顶点的必经点。

还有一些需要注意的是归并排序的比较次数，这个笔记有点多，就不一一写了。需要的可以私聊我拍笔记照片给你。

还有Dijkstra图的画法，这个今年考到了，下面给个例子。

顶点第一趟第二趟
a(a,b)2…
b无穷…
c…(a,b,d)5
集合a,b{a,b,c}

这个好像王道还是天勤上有一个例子，和上面的差不多。

基本总结的差不多，最后祝大家考上理想的大学

传送门 吉大高级程序设计笔记

这篇关于966，967吉大数据结构笔记的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/544441。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

系列文章目录 监督学习：参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归（SAheart.csv） 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

本章知识考点：         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
论文阅读笔记: Segment Anything

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear
阅读更多...
数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2
阅读更多...
【C++学习笔记 20】C++中的智能指针

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别，使用new关键字创建变量时，需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时，不必自己去调用delete，甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针，是一种作用域指针，意思是当指针超出该作用域时，会自动调用delete。它名为unique的原因是这个
阅读更多...
查看提交历史 —— Git 学习笔记 11

查看提交历史 —— Git 学习笔记 11

查看提交历史 查看提交历史 不带任何选项的git log-p选项--stat 选项--pretty=oneline选项--pretty=format选项git log常用选项列表参考资料 在提交了若干更新，又或者克隆了某个项目之后，你也许想回顾下提交历史。 完成这个任务最简单而又有效的 工具是 git log 命令。 接下来的例子会用一个用于演示的 simplegit
阅读更多...
记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪（un-tracking）文件重新跟踪（re-tracking）文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法，现在我们已经有了一个仓库，并从这个仓
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2