如:学生记录是一个数据元素,由学号、姓名等数据项组成
严书拓展
- 数据类型:一个值的集合和定义在这个值集上的一组操作的总称
按"值"的不同特性分为:
- 非结构的原子类型:C语言中的基本类型(int、char、枚举等)、指针类型、空类型
- 结构类型:数组等
结构类型可以看成由一种数据结构和定义在其上的一组操作组成- 抽象数据类型:指一个数学模型以及定义在该模型上的一组操作
- 原子类型:变量的值不可分解
- 固定聚合类型:其值由确定数目的成分按某种结构组成(e.g. 复数由两个实数依据确定的次序关系构成)
- 可变聚合类型:值的成分的数目不确定
- 与数据的存储无关,是独立于计算机的
- 分为线性结构和非线性结构
- 线性结构:数据元素之间只存在一对一的关系
- 非线性结构:数据元素之间存在一对多的关系
- 包括数据元素的表示和关系的表示
- 是用计算机语言实现的逻辑结构,依赖于计算机语言
- 有顺序存储、链式存储、索引存储、散列存储(哈希存储)
- 包括运算的定义和实现
- 运算的定义是针对逻辑结构的
- 运算的实现是针对存储结构的
算法的特性:
- 有穷性:算法必须是有穷的,而程序可以是无穷的
- 确定性:对相同的输入只能得到相同的输出
- 可行性
- 输入:可以有零个或多个输入
- 输出:至少有一个输出
算法的目标:
- 正确性
- 可读性
- 健壮性
- 高效率与低存储需求
线性表的定义:具有相同特征的数据元素的一个有限序列
线性表的长度可以为0,表示一个空表
存储结构:顺序存储(顺序表)和链式存储(链表)两种
线性表的基本操作
void merge(LNode *A,LNode *B,LNode *&C)
{
LNode *p = A->next; //p跟踪A的最小值结点
LNode *q = B->next; //q跟踪B的最小值结点
LNode *r; //r跟踪C的终端结点
C = A; //将A的头结点设定为C的头结点
C->next = NULL;
r = C;
free(B); //释放B的头结点
while(p != NULL && q != NULL)
{
if(p->data <= q->data)
{
r->next = p;
p = p->next;
r = r->next;
}
else
{
r->next = q;
q = q->next;
r = r->next;
}
}
r->next = NULL;
//将剩下的直接连接到C的末尾
if(p != NULL)
r->next = p;
if(q != NULL)
r->next = q;
}
void creatlistR(LNode *&C,int a[],int n)
{
LNode *s,*r; //s指向新申请的节点,r指向C的终端结点
int i;
C = (LNode *)malloc(sizeof(LNode)); //申请C的头结点空间
C->next = NULL;
r = C;
for(i = 0; i < n; i++)
{
s = (LNode *)malloc(sizeof(LNode));
s->data = a[i];
r->next = s;
r = r->next;
}
r->next = NULL;
}
void creatlistF(LNode *&C,int a[],int n)
{
LNode *s;
int i;
C = (LNode *)malloc(sizeof(LNode)); //申请C的头结点空间
C->next = NULL;
for(i = 0; i < n; i++)
{
s = (LNode *)malloc(sizeof(LNode));
s->data = a[i];
//下面两句是头插法的关键
s->next = C->next; //s所指新节点的指针域next指向C中的开始结点
C->next = s; //头结点的指针域next指向s结点,是的s成为新的开始结点
}
r->next = NULL;
}
- 后插
- 前插
void creatDlistR(LNode *&C,int a[],int n)
{
LNode *s,*r; //s指向新申请的节点,r指向C的终端结点
int i;
C = (LNode *)malloc(sizeof(LNode)); //申请C的头结点空间
C->prior = NULL;
C->next = NULL;
r = C;
for(i = 0; i < n; i++)
{
s = (LNode *)malloc(sizeof(LNode));
s->data = a[i];
r->next = s;
//开始与单链表不同
s->prior = r;
r = s;
}
r->next = NULL;
}
s->next = p->next;
s->prior = p;
p->next = s;
s->next->prior = s;
q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
比较简单,此处省略
天勤上的,王道没有
逆转整个数组
void reverse(int a[], int left, int right, int k)
{
int temp;
for(int i = left, j = right; i < left + k && i < j; ++i, --j)
{
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
将前k个元素逆置,再将整个数组逆置
void moveToEnd(int a[], int k, int n)
{
reverse(a, 0, k - 1, k);
reverse(a, 0, n - 1, k);
}
将0p-1位置的元素逆置,再将pn-1位置的元素逆置,最后将整个数组逆置
void moveP(int a[], int n, int p)
{
reverse(a, 0, p - 1, p);
reverse(a, p, n - 1, n - p);
reverse(a, 0, n - 1, n);
}
存取方式即为读写方式
链式存储结构比顺序存储结构更能方便的表示各种逻辑结构
队列需要在表头删除元素,表尾插入元素,用带尾指针的循环链表更方便
用给定的n个元素的以为数组,建立一个有序单链表的最低时间复杂度是O(nlogn)
删除链表的最后一个元素的时间复杂度是O(n),就算有尾指针也是,因为要遍历到其前驱结点,把next指向NULL
从顺序表汇总删除其值在给定值s到t之间(包含s和t,s<t)的所有元素,若s和t不合理或顺序表为空,则显示出错信息并退出运行
空间换时间的思想
n个不同元素进展,不同的出栈顺序有 1 n + 1 C 2 n n \frac{1}{n+1}C^n_{2n} n+11C2nn种
进栈:先动指针再进元素
stack[++top] = x;
x = stack[top--];
rear = (rear + 1) % maxSize;
data[rear] = x;
一般情况下front所指的位置为空,所以先变指针再出队
rear所指的位置为尾元素,所以先变指针再进队
方法一:划线试探法
详情见24王道课视频
方法二:最长公共前后缀法
同样先划线,next数组的值等于其前最长公共前后缀数+1
void get_next(SString T, int next[]){
int i = 1, j = 0;
next[1] = 0;
while(i < T.length)
{
if(j == 0 || T.ch[i] == T.ch[j])
{
i++;
j++;
next[i] = j; //若Pi=Pj,则next[j+1]=next[j]+1
}
else
j = next[j]; //否则令j=next[j]
}
}
常考性质
- 结点数 = 总度数+1
- 度为m的树,第i层最多有 m i − 1 m^{i-1} mi−1个结点
- m叉树第i层最多有 m i − 1 m^{i-1} mi−1个结点
- 高度为h的m叉树最多有 m h − 1 m − 1 \frac{m^h-1}{m-1} m−1mh−1个结点
- 高度为h的m叉树至少有h个结点
- 高度为h,度为m的树至少有h+m-1个结点
- 具有n个结点的m叉树的最小高度为 ⌈ l o g m ( n ( m − 1 ) + 1 ) ⌉ \lceil log_m(n(m-1)+1) \rceil ⌈logm(n(m−1)+1)⌉
叶子结点都在最后一层,不存在度为1的结点
每个结点都与高度为h的满二叉树中的编号一一对应
- 叶子结点只能出现在最后两层
- 最多只有一个度为1的结点(只有左孩子)
度为0的结点 = 度为2的结点 + 1
2叉树第i层最多有 2 i − 1 2^{i-1} 2i−1个结点
高度为h的2叉树最多有 2 h − 1 2^h-1 2h−1个结点
有n个结点的完全二叉树的高度为 ⌈ l o g 2 ( n + 1 ) ⌉ \lceil log_2(n+1) \rceil ⌈log2(n+1)⌉或 ⌊ l o g 2 n ⌋ + 1 \lfloor log_2n \rfloor + 1 ⌊log2n⌋+1(计算i所在的层次也是一样)
完全二叉树若已知结点数为n,可推出度为0/1/2的结点数的个数
Status PreOrderTraverse(BiTree T){
if(T == NULL)
return OK;
else
{
visit(T); //访问根节点
PreOrderTraverse(T->lchild); //递归遍历左子树
PreOrderTraverse(T->rchild); //递归遍历右子树
}
}
Status InOrderTraverse(BiTree T){
if(T == NULL)
return OK;
else
{
InOrderTraverse(T->lchild); //递归遍历左子树
visit(T); //访问根节点
InOrderTraverse(T->rchild); //递归遍历右子树
}
}
Status PostOrderTraverse(BiTree T){
if(T == NULL)
return OK;
else
{
PostOrderTraverse(T->lchild); //递归遍历左子树
PostOrderTraverse(T->rchild); //递归遍历右子树
visit(T); //访问根节点
}
}
前序+中序
后序 + 中序
层序 + 中序
双亲表示法(顺序存储)
孩子表示法(顺序+链式存储)
孩子兄弟表示法(链式存储)
树→二叉树
森林→二叉树
二叉树→树
二叉树→森林
先根遍历
后根遍历
层序遍历
在含有n个带权叶结点的二叉树中,WPL最小的二叉树即为Huffman树
结点按完全二叉树层序编号的二叉树中,第i个结点的左孩子编号为2i:错,不一定有左孩子
设二叉树有2n个结点,m < n,则不可能存在2m个度为1的结点
三叉树的结点数为50,则最小高度为5
对任意一颗高度为5且有10个结点的二叉树,若采用顺序存储结构保存,每个结点占1个存储单元(仅存放结点的数据信息),则存放该二叉树所需的存储单元数至少 为31 (任意→考虑最坏情况)
二叉树中可用后续遍历找到祖先到子孙的路径
线索二叉树是一种物理结构
线索化后仍不能有效求解后序线索二叉树中求后序后继
后序线索树的遍历需要栈的支持
一棵有2011个结点的树,其中叶结点个数为116,则对应的二叉树中无右孩子的结点个数为?
设哈夫曼编码的长度不超过4,若已对两个字符编码为1和01,则最多还能对4个字符编码
度为m的哈夫曼树中,叶结点为n,则非叶结点个数为?
- 并非任意挑几个边几个顶点就是子图
- 生成子图:包含所有顶点
- 连通分量:无向图的极大连通子图
- 强连通分量:有向图的极大连通子图
n个顶点的树有n-1条边
n个顶点的图若边 >n-1则一定有回路
空间复杂度O(V+E)
问题模型:道路规划,使每个城市都联通,且花销最少
问题模型:寻找两个顶点之间的最短路径
不断加顶点,算新的最短路径
尝试以所有结点为中转点,路径是否变小
逆拓扑排序
- 正看最大,反看最小
- 活动的最早发生时间就是该结点所连的弧尾的事件的最早发生时间
- 活动的最迟发生时间 = 该活动所连弧头时间的最晚发生时间 - 该活动所花费的时间
–
哨兵:保证查找时不会越界
仅适用于有序表,适合顺序存储结构,不适合链式存储结构
性质
- 对任何一个结点:右子树结点数 - 左子树结点数 = 0或1
- 折半查找树预定是平衡二叉树,结点个数为n时,树高为 ⌈ l o g 2 ( n + 1 ) ⌉ \lceil log_{2}^{(n+1)} \rceil ⌈log2(n+1)⌉
- 若折半查找树中共有n个成功结点,则失败结点有n+1个
- 折半查找的时间复杂度
low>high,在low所在的分块查找
- 法一:用右子树中最小的结点代替
- 法二:用左子树中最大的结点代替
LL
RR
LR
RL
练习
- 用前驱替代
- 用后继替代
性质:
- 从根节点到叶结点的最长路径不大于最短路径的2倍
- 若有n个内部结点的红黑树高度 h ≤ O ( l o g 2 ( n + 1 ) ) h \leq O(log_{2}^{(n+1)}) h≤O(log2(n+1))
3直接插
25、18直接插
…
对于含有n个关键字的m阶B树 l o g m ( n + 1 ) ≤ h ≤ l o g ⌈ m 2 ⌉ n + 1 2 + 1 log_{m}{(n+1)} \leq h \leq log_{\lceil \frac{m}{2} \rceil}{\frac{n+1}{2}} + 1 logm(n+1)≤h≤log⌈2m⌉2n+1+1
- 兄弟够借:
借右兄弟:
借左兄弟:
- 兄弟不够借
α \alpha α 越大说明表中记录数越多,说明表装的越满,冲突的可能性越大,查找的次数越多
拉链法的平均查找长度
- 线性探测法
- 平方探测法
- 双散列法
- 伪随机序列法: d i = 伪随机数序列 d_i = 伪随机数序列 di=伪随机数序列
线性探测法的查找效率
判断能否构成折半查找中关键字比较序列
高度为h的AVL至少有多少结点
正常AVL中序遍历得到的是升序序列,而这道题说的是降序序列。坑…
高度为5的3阶B树至少有31个结点,最多有121个结点 (注意问的是结点数还是关键字数)
线性探测法的ASL
void InsertSort(int A[], int n)
{
int i, j;
for(i = 2; i <= n; i++)
{
if(A[i] < A[i - 1])
{
A[0] = A[i]; //复制为哨兵
for(j = i - 1; A[0] < A[j]; j--)
{
A[j + 1] = A[j]; //记录后移
}
A[j + 1] = A[0]; //插入到正确位置
}
}
}
ps.对链表进行插入排序,移动元素的次数变少,但关键字对比次数仍为 O ( n 2 ) O(n^2) O(n2)数量级
void InsertSort(int A[], int n)
{
int i, j, low, high, mid;
for(i = 2; i <= n; i++)
{
low = 1;
high = i - 1;
while(low <= high) //折半查找
{
mid = (low + high)/2;
if(A[mid] > A[0]) //找左半边
hgih = mid - 1;
else //找右半边(保持稳定性)
low = mid + 1;
}
for(j = i - 1; j >= high + 1; j--) //后移
A[j + 1] = A[j];
A[high + 1] = A[0]; //插入到正确位置
}
}
void ShellSort(int A[], int n)
{
int d, i ,j;
for(d = n / 2; d >= 1; d = d / 2) //步长变化
{
for(i = d + 1; d <= n; i++)
{
if(A[i] < A[i - d]) //将A[i]插入有序增量子表
{
A[0] = A[i]; //暂存在哨兵位置
for(j = i - d; j > 0 && A[0] < A[j]; j -= d) //插入排序
A[j + d] = A[j];
A[j + d] = A[0]; //插入到正确位置
}
}
}
}
void BubbleSort(int A[], int n)
{
for(int i = 0; i < n - 1; i++)
{
bool flag = false; //本次冒泡排序是否发生交换
for(int j = n - 1; j < i; j-->) //一趟冒泡过程,从后往前找
{
if(A[j - 1] > A[j])
{
swap(A[j - 1], A[j]); //交换
flag = true;
}
}
if(flag = false)
return;
}
}
ps.上图最好和最坏复杂度写反了
//用第一个元素将序列划分为左右两部分
int Partition(int A[], int low. int high)
{
int pivot = A[low]; //将第一个元素作为基准
while(low < high)
{
while(low < high && A[high] >= pivot)
--high; //从后往前找比基准小的元素
A[low] = A[high]; //比基准小的移动到左端
while(low < high && A[low] <= pivot)
++low; //从前往后找比基准大的元素
A[high] = A[low]; //比基准大的移动到右端
}
A[low] = A[high]; //将基准放到最终位置
return low; //返回基准所在的位置
}
//快速排序
void QuikSort(int A[], int low, int high)
{
if(low < high)
{
int pivotpos = Partition(A, low, high); //划分
QuikSort(A, low, pivotpos - 1); //划分左子表
QuikSort(A, pivotpos + 1, high); //划分右子表
}
}
void SelectSort(int A[], int n)
{
for(int i = 0; i < n - 1; i++) //共n-1趟
{
int min = i; //记录最小元素的位置
for(int j = i + 1; j < n; j++)
if(A[j] < A[min]) //找最小元素
min = j; //更新最小元素位置
if(min != i)
swap(A[i], A[min]); //交换
}
}
在顺序存储的完全二叉树中,非终端节点编号 i ≤ ⌊ n / 2 ⌋ i \leq \lfloor n/2 \rfloor i≤⌊n/2⌋
//建立大根堆
void BuildMaxMap(int A[], int len)
{
for(int i = len / 2; i > 0; i--) //从后往前调整所有非终端结点
HeadAdjust(A, i ,len);
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len)
{
A[0] = A[k]; //暂存
for(int i = 2 * k; i <= len; i *= 2)
{
if(i < len && A[i] < A[i + 1]) //选左右孩子中更大的
i++;
if(A[0] > A[i]) //满足大根堆,退出
beak;
else //不满足大根堆,小元素下坠
{
A[k] = A[i]; //将A[i]放到上面
k = i; //修改k值,继续向下比较
}
}
A[k] = A[0]; //最终位置
}
//堆排序
void HeapSort(int A[], int len)
{
BuildMaxHeap(A, len); //初始建堆
for(i = len; i > 1; i--) //n-1趟交换和建堆过程
{
swap(A[i], A[1]); //每次把最大的元素放在最后
HeadAdjust(A, 1, i - 1); //声誉元素调整为堆
}
}
int *B = (int *)malloc(n * sizeof(int)); //辅助数组B
//将A[low..mid]和A[mid+1..high]归并
void Merge(int A[], int low, int mid, int high)
{
int i, j, k;
for(k = low; k <= high; k++)
B[k] = A[k]; //将A数组复制到B中
for(i = low, j = mid + 1, k = i; i<= mid && j <= high; k++)
{
if(B[i] < B[k]) //将小的放到A中
A[k] = B[i++];
else
A[k] = B[j++];
}
//将数组中剩余部分直接放入
while(i <= mid)
A[k++] = B[i++];
while(j <= high)
A[k++] = B[j++];
}
//归并排序
void MergrSort(int A[], int low, int high)
{
if(low < high)
{
int mid = (low + high) / 2;
MergeSort(A, low, mid); //归并左半部分
MergeSort(A, mid + 1, high); //归并右半部分
Merge(A, low, mid, high); //归并
}
}
例如,对1,2,3(n=3)进行从小到大排序,即序列有6(3!)种可能,我们要从这6种可能中找到唯一的一个序列1,2,3。针对3个元素中的任意两个元素,比如1和2,一定要求1在2前面,对此只剩3个序列满足要求,之后依次进行对数折半筛选,只剩唯一一个序列。注意到每次筛选都是折半的,因此是以2为底的对数运算。
n
n个关键字的小根堆中,关键字最大的记录可能存储在 ⌊ n / 2 ⌋ + 1 n \lfloor n/2 \rfloor + 1 ~ n ⌊n/2⌋+1 n中
满二叉树最后一个非叶结点为 ⌊ n / 2 ⌋ \lfloor n/2 \rfloor ⌊n/2⌋
堆排序和希尔排序用到了顺序表随机存储的特点,用链表实现更慢
设有5个初始归并段,每个归并段有20个记录,采用5路平衡归并的方法,若不采用败者树,总的比较次数为369次;若采用败者树,总的比较次数为300次
文章浏览阅读331次。第一部分:准备工作1 安装虚拟机2 安装centos73 安装JDK以上三步是准备工作,至此已经完成一台已安装JDK的主机第二部分:准备3台虚拟机以下所有工作最好都在root权限下操作1 克隆上面已经有一台虚拟机了,现在对master进行克隆,克隆出另外2台子机;1.1 进行克隆21.2 下一步1.3 下一步1.4 下一步1.5 根据子机需要,命名和安装路径1.6 ..._创建一个hadoop项目
文章浏览阅读1.7k次。心脏滴血漏洞HeartBleed CVE-2014-0160 是由heartbeat功能引入的,本文从深入码层面的分析该漏洞产生的原因_heartbleed代码分析
文章浏览阅读1.4k次。前言ofd是国家文档标准,其对标的文档格式是pdf。ofd文档是容器格式文件,ofd其实就是压缩包。将ofd文件后缀改为.zip,解压后可看到文件包含的内容。ofd文件分析工具下载:点我下载。ofd文件解压后,可以看到如下内容: 对于xml文件,可以用文本工具查看。但是对于印章文件(Seal.esl)、签名文件(SignedValue.dat)就无法查看其内容了。本人开发一款ofd内容查看器,..._signedvalue.dat
文章浏览阅读1.8w次,点赞29次,收藏313次。整体系统设计本设计主要是对ADC和DAC的使用,主要实现功能流程为:首先通过串口向FPGA发送控制信号,控制DAC芯片tlv5618进行DA装换,转换的数据存在ROM中,转换开始时读取ROM中数据进行读取转换。其次用按键控制adc128s052进行模数转换100次,模数转换数据存储到FIFO中,再从FIFO中读取数据通过串口输出显示在pc上。其整体系统框图如下:图1:FPGA数据采集系统框图从图中可以看出,该系统主要包括9个模块:串口接收模块、按键消抖模块、按键控制模块、ROM模块、D.._基于fpga的信息采集
文章浏览阅读2.5w次。1.背景错误信息:-- [http-nio-9904-exec-5] o.s.c.n.z.filters.post.SendErrorFilter : Error during filteringcom.netflix.zuul.exception.ZuulException: Forwarding error at org.springframework.cloud..._com.netflix.zuul.exception.zuulexception
文章浏览阅读358次。1.介绍图的相关概念 图是由顶点的有穷非空集和一个描述顶点之间关系-边(或者弧)的集合组成。通常,图中的数据元素被称为顶点,顶点间的关系用边表示,图通常用字母G表示,图的顶点通常用字母V表示,所以图可以定义为: G=(V,E)其中,V(G)是图中顶点的有穷非空集合,E(G)是V(G)中顶点的边的有穷集合1.1 无向图:图中任意两个顶点构成的边是没有方向的1.2 有向图:图中..._给定一个邻接矩阵未必能够造出一个图
文章浏览阅读321次。(十二)、WDS服务器安装通过前面的测试我们会发现,每次安装的时候需要加域光盘映像,这是一个比较麻烦的事情,试想一个上万个的公司,你天天带着一个光盘与光驱去给别人装系统,这将是一个多么痛苦的事情啊,有什么方法可以解决这个问题了?答案是肯定的,下面我们就来简单说一下。WDS服务器,它是Windows自带的一个免费的基于系统本身角色的一个功能,它主要提供一种简单、安全的通过网络快速、远程将Window..._doc server2012上通过wds+mdt无人值守部署win11系统.doc
文章浏览阅读219次。python–xlrd/xlwt/xlutilsxlrd只能读取,不能改,支持 xlsx和xls 格式xlwt只能改,不能读xlwt只能保存为.xls格式xlutils能将xlrd.Book转为xlwt.Workbook,从而得以在现有xls的基础上修改数据,并创建一个新的xls,实现修改xlrd打开文件import xlrdexcel=xlrd.open_workbook('E:/test.xlsx') 返回值为xlrd.book.Book对象,不能修改获取sheett_xlutils模块可以读xlsx吗
文章浏览阅读8.2w次,点赞267次,收藏656次。运行Selenium出现'WebDriver' object has no attribute 'find_element_by_id'或AttributeError: 'WebDriver' object has no attribute 'find_element_by_xpath'等定位元素代码错误,是因为selenium更新到了新的版本,以前的一些语法经过改动。..............._unresolved attribute reference 'find_element_by_id' for class 'webdriver
文章浏览阅读198次。一:模态窗口//父页面JSwindow.showModalDialog(ifrmehref, window, 'dialogWidth:550px;dialogHeight:150px;help:no;resizable:no;status:no');//子页面获取父页面DOM对象//window.showModalDialog的DOM对象var v=parentWin..._jquery获取父window下的dom对象
文章浏览阅读1.7w次,点赞15次,收藏129次。算法(algorithm)是解决一系列问题的清晰指令,也就是,能对一定规范的输入,在有限的时间内获得所要求的输出。 简单来说,算法就是解决一个问题的具体方法和步骤。算法是程序的灵 魂。二、算法的特征1.可行性 算法中执行的任何计算步骤都可以分解为基本可执行的操作步,即每个计算步都可以在有限时间里完成(也称之为有效性) 算法的每一步都要有确切的意义,不能有二义性。例如“增加x的值”,并没有说增加多少,计算机就无法执行明确的运算。 _算法
文章浏览阅读1.5k次,点赞18次,收藏26次。网络安全的标准和规范是网络安全领域的重要组成部分。它们为网络安全提供了技术依据,规定了网络安全的技术要求和操作方式,帮助我们构建安全的网络环境。下面,我们将详细介绍一些主要的网络安全标准和规范,以及它们在实际操作中的应用。_网络安全标准规范