电大数据结构开卷一纸小抄(可编辑)

电大数据结构开卷一纸小抄(可编辑) 绪论 数据 数据对象 数据元素 数据项 数据对客观事物的符号 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示所有能输入到计算机中并被计算机程序处理的符号总称数据元素数据的基本单位可由若干个数据项组成数据对象性质相同的数据元素的集合数据的一个子集 数据结构相互之间存在一种或多种特定关系的数据元素的集合无操作 抽象数据类型指一个数学模型以及定义在该模型上的一组操作有操作 顺序存储结构相对位置 链式存储结构借助指针 算法五特性有穷确定可行输入输出 时间复杂度问题随着规模N的增大算法执行时间的增长率常见O n O nlogn O n2 空间复杂度算法所需存储空间的量度原地工作常数 线性表 线性表n个数据元素的有限序列 顺序存储逻辑结构与物理结构一致缺点插入删除元素需要移动平均约一半的元素属于随机存取方式 链式存储逻辑结构与物理结构不一致属于顺序存储方式 顺序表线性表采用顺序存储结构表示有序表内容按从小到大排列的线性表 线性链表单向双向循环 不特殊说明均带头结点 第3章 栈和队列 栈限定仅在表尾进行插入或删除操作的线性表后进先出LIFO 队列在一端进行插入另一端删除元素先进先出FIFO 第6章 树与二叉树 树以分支关系定义的层次结构 森林m m 0 棵互不相交的树的集合 二叉树每个结点之多只有两棵子树并且有左右之分 完全二叉树若设二叉树的高度为h除第 h 层外其它各层 1,h-1 的结点 数都达到最大个数第 h 层所有的节点都连续集中在最左边这就是完全二叉树 二叉树五性质 1 第i层上之多有2 i-1 个结点 i 1 2 深度为k的二叉树至多有2k-1个结点 k 1 3 对于任意一棵二叉树如果终端节点数为n0度为2的节点数为n2则n0 n21 4 具有n个结点的完全二叉树的深度为 下取整 log2n 1 5 对n个结点的完全二叉树按层从上到下每层从左到右 1 第i个结点的双亲是 下取整 i2 2 如果2i n则是叶子结点否则左孩子是2i 3 如果2i1 n则结点i无右孩子否则右孩子是2i1 WLP最小的二叉树称为最优二叉树赫夫曼树 赫夫曼树特点 1 每个结点的度不是0就是2 2 如果有n个权值赫夫曼树就有2n-1个结点其中n个叶子结点n-1个度为 2的结点 3 构造赫夫曼树就是构造n-1个度为2的结点过程 第7章 图 有向图由顶点集和弧集构成的图 无向图由顶点集和边集构成的图 深度优先遍历从图中的某个顶点V0 出发访问此顶点然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图中的其余顶点直至图中所有和V0有路径相通的顶点都被访问到为止 广度优先遍历从图中的某个顶点V0出发并在访问此顶点之后依次访问V0的所有未被访问过的邻接点随后按这些顶点被访问的先后次序依次访问它们的邻接点直至图中所有与V0有路径相通的顶点都被访问到为止 拓扑排序 从有向图中选取一个没有前驱的顶点并输出之 从有向图中删去此顶点以及所有以它为尾的弧 重复上述两步直至图空或者找不到无前驱的顶点为止 第9章 查找 顺序查找从表中的最后一个 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 开始逐个进行记录的关键字和给定值的比较若某个记录的关键字和给定值比较相等则查找成功找到所查记录反之若直至第一个纪录其关键字和给定值比较都不想等则表明表中没有所查记录查找不成功 折半查找先确定待查记录所在的范围然后逐步缩小范围直到找到或找不到该记录为止 二叉排序树 平衡二叉树树中每个结点的左右子树深度之差的绝对值不大于1 给定值与关键字进行比较的次数不超过平衡树的深度大约log n 哈希表根据设定的哈希函数H key 和所选用的处理冲突的方法将一组关键字映象到一个有限的 地址连续的地址集 区间 上并以关键字在地址集中的映象作为相应记录在表中的存储 位置 如此构造所得的查找表称之为哈希表 构造哈希函数直接定址法数字分析法平方取中法折叠法除留余数法随机数法 处理冲突开放定址法再哈希法链地址法建立公共溢出区 决定哈希表查找的ASL的因素 选用的哈希函数 选用的处理冲突的方法 哈希表饱和程度的装载因子α nm值的大小 n-记录数m-表长 哈希表的ASL是处理冲突方法和装载因子的函数 常见ASL线性探测 - 229 二次探测 - 149 链地址法 - 139 第10章 内部排序 插入排序不断地将无序子序列中的记录插入到有序序列中从而逐渐地增加有序子序列的长 度直到所有记录都进入有序序列中为止 比较次数最坏 - n-4 n-1 2最好 - n-1 移动次数最坏 - n-4 n-1 2最好 - 0 适用原始数据基本有序或数据量不大的情况 冒泡排序 不断地考查待排序列中关键字之间的有序性一旦发现非有序关 系将其交换直到 所有记录均按照有序性就位为止 比较次数最坏 - n n-1 2最好 - n-1 移动次数最坏 - 3n n-1 2最好 – 0 快速排序 首先对无序的记录序列进行一次划分之后分别对划分后的两个子序列递归进行 快速排序 时间复杂度为O nlogn 适用于原始数据杂乱无章的倾向辅助空间数量为递归调用所开辟的栈空间 选择排序 不断地从无序子序列中选择关键字最小 或最大 者并将其加入到有序子序列中 以此方法增加有序子序列的长度直到所有的记录都进入有序序列中为止 比较次数n n-1 2 移动次数最坏 - 3 n-1 最好 - 0 堆排序利用堆的特性对记录序列进行排序的一种排序方法 基本过程 1根据原始记录序列创建堆 2将根与堆中的最后一个结点交换 3将堆中的最后结点从堆中删去 4将剩余的结点重新调整成堆 调整 对一棵左右子树均为堆的完全二叉树调整根结点使整个二叉树也成为一个堆 时间复杂度为O nlogn 优势节省空间且堆原始数据的排序不敏感 归并排序 通过归并两个或两个以上的有序子序列逐步增加有序序列的长度直到所有的记 录都进入一个有序序列中为止 时间复杂度为O nlogn 是一种稳定性排序方法辅助空间复杂度O n 基数排序 借助多关键字排序的思想来实现单关键字排序的内部排序算法 多关键字的排序 最高位优先MSD 先对K0进行排序并按K0的不同值将记录序列分成若干子序列之后分别 对K1进行排序 依次类推直至最后对最次位关键字排序完成为止 最低位优先LSD 先对Kd-1进行排序然后对Kd-2进行排序依次类推直至对最主位关 键字K0排序完成为止不需要根据前一关键字的结果分割子序列 链式基数排序分配 - 收集排序法 1 待排序记录以指针相链构成一个链表 2 分配 时按照当前关键字位的取值将记录分配到相应的链队列 中每个 队列中记录的关键字位 相同 3 收集时按当前关键字位取值从小到大将各队列首尾相链成一个链表 4 对每个关键字位均重复2和3两步 时间复杂度为O d nrd d为分配-收集的趟数 横向比较 平均时间性能 O nlogn 快速排序归并排序堆排序 O n2 插入排序冒泡排序选择排序 O d nrd 基数排序 最坏时间性能 O nlogn 归并排序堆排序 O n2 快速排序插入排序冒泡排序选择排序 最好时间性能 O n 插入排序冒泡排序改进版 O n2 快速排序退化 时间性能不随记录序列的关键字分布改变选择排序堆排序归并排序 空间性能 所有的简单排序方法 插入冒泡选择 和堆排序的空间复杂度为O 1 快速排序为O logn 为递归程序执行过程中栈所需的辅助空间 归并排序所需辅助空间最多其空间复杂度为O n 链式基数排序需附设队列首尾指针故空间复杂度为O rd 稳定性能 有无跨元素交换 当对多关键字的记录序列进行LSD方法排序时必须采用稳定的排序方法 快速排序堆排序希尔排序是不稳定的排序方法 1 设计判断单链表中结点是否关于中心对称算法 typedef struct int s[100] int top sqstack int lklistsymmetry lklist head sqstack stack stacktop -1 lklist p for p headp 0p p- next stacktop stacks[stacktop] p- data for p headp 0p p- next if p- data stacks[stacktop] stacktop stacktop-1 else return 0 return 1 2 设计在链式存储结构上建立一棵二叉树的算法 typedef char datatype typedef struct node datatype data struct node lchildrchild bitree void createbitree bitree bt char ch scanf "c"ch if ch bt 0 return bt bitree malloc sizeof bitree bt- data ch createbitree bt- lchild createbitree bt- rchild 3 设计判断一棵二叉树是否是二叉排序树的算法 int minnum -32768flag 1 typedef struct node int key struct node lchildrchild bitree void inorder bitree bt if bt 0 inorder bt- lchild if minnum bt- key flag 0 minnum bt- key inorder bt- rchild 2 设有两个集合A和集合B要求设计生成集合C A?B的算法其中集合AB 和C用链式存储结构表示 typedef struct node int data struct node next lklist void intersection lklist halklist hblklist hc lklist pqt for p hahc 0p 0p p- next for q hbq 0q q- next if q- data p- data break if q 0 t lklist malloc sizeof lklist t- data p- datat- next hc hc t 1 设计在单链表中删除值相同的多余结点的算法 typedef int datatype typedef struct node datatype data struct node next lklist void delredundant lklist head lklist pqs for p headp 0p p- next for q p- nexts 0 if q- data p- data s- next q- next free q q s- next else s q- next 2 设计一个求结点x在二叉树中的双亲结点算法 typedef struct node datatype data struct node lchildrchild bitree bitree q[20] int r 0f 0flag 0 void preorder bitree bt char x if bt 0 flag 0 if bt- data x flag 1 return else r r1 20 q[r] bt preorder bt- lchildx preorder bt- rchildx void parent bitree btchar x int i preorder btx for i f1 i r i if q[i]- lchild- data x q[i]- rchild- data break if flag 0 printf "not found x\n" else if i r printf "c"bt- data else printf "not parent" 2 设计在链式存储结构上交换二叉树中所有结点左右子树的算法 typedef struct node int data struct node lchildrchild bitree void swapbitree bitree bt bitree p if bt 0 return swapbitree bt- lchild swapbitree bt- rchild p bt- lchild bt- lchild bt- rchild bt- rchild p 3 在链式存储结构上建立一棵二叉排序树 define n 10 typedef struct node int key struct node lchildrchild bitree void bstinsert bitree btint key if bt 0 bt bitree malloc sizeof bitree bt- key keybt- lchild bt- rchild 0 else if bt- key key bstinsert bt- lchildkey else bstinsert bt- rchildkey void createbsttree bitree bt int i for i 1i ni bstinsert btrandom 100 1 设计判断两个二叉树是否相同的算法 typedef struct node datatype data struct node lchildrchild bitree int judgebitree bitree bt1bitree bt2 if bt1 0 bt2 0 return 1 else if bt1 0 bt2 0 bt1- data bt2- data return 0 else return judgebitree bt1- lchildbt2- lchild judgebitree bt1- rchildbt2- rchild 2 设计两个有序单链表的合并排序算法 void mergelklist lklist halklist hblklist hc lklist s hc 0 while ha 0 hb 0 if ha- data hb- data if s 0 hc s ha else s- next ha s ha ha ha- next else if s 0 hc s hb else s- next hb s hb hb hb- next if ha 0 s- next hb else s- next ha 3 设计求结点在二叉排序树中层次的算法 int lev 0 typedef struct node int key struct node lchildrchild bitree void level bitree btint x if bt 0 lev if bt- key x return else if bt- key x level bt- lchildx else level bt- rchildx 好文档好知识 删除结点一定要释放空间 线性表的线性链表存储结构 typedef struct ElemType data struct LNode next LNode LinkList 带头节点的线性链表类型 typedef struct LNode 结点类型 ElemType data struct LNode next Link Position typedef struct 链表类型 Link head tail 指向头尾结点 int len 数据元素的个数 LinkList 线性表的动态分配顺序存储结构 typedef struct ElemType elem 存储空间基址 int length 当前长度 int listsize 当前分配的储存容量 SqList ADT List InitList L 构造空线性表L DestroyList L 销毁线性表L ClearList L 将L重置为空表 ListEmpty L 判断L是否为空表返回TRUEFALSE ListLength L 返回L中数据元素个数 GetElem L i e 用e返回L中第i个数据元素的值 LocateElem L e compare 返回L中第1个与e满足compare函数关系的元素位序 PriorElem NextElem L cur_e pre_e next_e 返回L中e的前驱后继 ListInsert L i e 在L中第i个位置前插入元素e表长1 ListDelete L i e 删除L中第i个数据元素并用e返回其值表长-1 ListTraverse L visit 遍历L的每个元素并对其调用visit函数 Status ListDelete_L LinkLIst L int i ElemType e 删除带头结点的单链表L中第i个结点并由e返回其值 p L j 0 while p- next j i-1 p p- next j 查找第i-1个结点并由p指向 if p- next j i-1 return ERROR 删除位置不合理 q p- next e q- data 删除结点并将其值赋给e p- next q- next 修改前驱指针 free q 释放结点 return OK Status ListInsert_Sq SqList Lint iElemType e 在L的第i个元素之前插入一个新结点e if i 1 i LLength1 return ERROR if Llength Llistsize newbase ElemType realloc Lelem LlistsizeLISTINCREMENT sizeof ElemType if newbase exit OVERFLOW Lelem newbase Llistsize LISTINCREMENT q Lelem[i-1] for p Lelem[Llength-1] p q--p p1 p q e Llength return OK ListInsert_Sq Status Create_L LinkList Lint n 正序创建链表 L LNode malloc sizeof LNode if L return ERROR 创建头结点 last L 设置last指针 for int i 1i ni cin data 输入元素信息 p LNode malloc sizeof LNode if p return ERROR p- data data 创建结点 last- next p last p 将新结点插到链表尾端 last- next NULL return OK Status CreateList_L LinkList Lint n 逆序创建链表 L LNode malloc sizeof LNode if L return ERROR L- next NULL 创建头结点 for i ni 0i-- cin data 输入元素信息 p LNode malloc sizeof LNode if p return ERROR p- data data 创建结点 p- next L- next L- next p 将新结点插入到首端 return OK 队列的链式存储结构单链队列 typedef struct QNode 结点类型 QElemType data struct QNode next QNode QueuePtr typedef struct 队列类型 QueuePtr front 队头指针 QueuePtr rear 队尾指针 LinkQueue 若队列不空 头指针指向队列头元素 尾指针指向队尾元素的下一个位置 栈的顺序存储表示 typedef struct SElemType base 栈底指针 SElemType top 栈顶指针 int stacksize 栈的大小 SqStack 构造前和销毁后base NULL ADT LinkQueue InitQueue Q 构造空队列Q DestroyQueue Q 销毁队列Q ClearQueue Q 将Q置为空队列 QueueEmpty Q 判断Q是否为空队列返回TRUEFALSE QueueLength Q 返回Q中数据元素个数 GetHead Q QELemType e 用e返回Q的队头元素并返回OK EnQueue Q QElemType e 插入元素e为新的队尾元素 DeQueue Q QElemType e 删除Q的队头元素用e返回其值并返回OK QueueTraverse Q Status Visit 从队头调用Visit函数遍历至队尾 ADT SqStack InitStack S 构造空栈S DestroyStack S 销毁栈S ClearStack S 将S置为空栈 StcakEmpty S 判断S是否为空栈返回TRUEFALSE StackLength S 返回S中数据元素个数 GetTop S SELemType e 用e返回S的栈顶元素并返回OK Push S SElemType e 插入元素e为新的栈顶元素 Pop S SElemType e 删除S的栈顶元素用e返回其值并返回OK StackTraverse S Status Visit 从栈底调用Visit函数遍历至栈顶 队列的顺序存储结构循环队列 typedef struct QElemType base int front 头指针 int rear 尾指针 SqStack Root T 返回T的根 BiTreeEmptyT 判断T是否为空树返回TRUEFALSE CreateBiTree T definition 按definition构造二叉树T Value T e 返回e的值 Assign T e value 结点e赋值为Value Parent T e 返回e的双亲节点无则返回NULL LeftChildRightChild T e 返回e的左右孩子无则返回NULL LeftSiblingRightSibling T e 返回e的左右兄弟无则返回NULL InsertChild T p LR c 根据LR的01值插入c为T中p结点的左右子树原有 结点成为c的右子树 DeleteChild T p LR 根据LR的01值删除T中p结点的左右子树 PreOrderTraverse T Visit 先序遍历T依次对每个结点调用Visit函数 InOrderTraverse T Visit 中序遍历T依次对每个结点调用Visit函数 PostOrderTraverse T Visit 后序遍历T依次对每个结点调用Visit函数 LevelOrderTraverse T Visit 层序遍历T依次对每个结点调用Visit函数 ADT BiTree InitBiTree T 构造空二叉树T DestroyBiTree T 销毁二叉树T ClearBiTree T 将T置为空二叉树 BiTreeDepth T 返回T的深度 Status CreateBiTree BiTree T 先序构造二叉树 scanf ch if ch T NULL else if T BiTNode malloc sizeof BitNode exit OVERFLOW T- data ch CreateBiTree T- lchild CreateBiTree T- rchild return OK 类似适用于 中序构造二叉树递归 后续构造二叉树递归 层序构造二叉树递归 Status hiberarchy BiTree T 层序遍历二叉树 if T return OK InitQueue Q visit T- data EnQueue QT 一定要结点入队 while QueueEmpty Q 队不空继续循环 DeQueue Qp 出队 if p- lchild 处理左孩子 visit p- lchild- data EnQueue Qp- lchild if p- rchild 处理右孩子 visit p- rchild- data EnQueue Qp- rchild return OK int Search_Seq SSTable ST KeyType key STelem[0]key key for k 1 k LLength STelem[k] key k if k LLength return k else return 0 Search_Seq int Search_Bin SSTable ST KeyType key low 1 high STlength 设置区间初值 while low high mid low high 2 if EQ key STelem[mid]key return mid 找到待查元素 else if LT key STelem[mid]key high mid - 1 else low mid 1 , return 0 Search_Bin typedef struct BiTNode 结点结构 TElemType data struct BiTNode lchild rchild 左右孩子指针 BiTNode BiTree Status SearchBST BiTree T KeyType key BiTree f BiTree p if T p f return FALSE 查找不成功 else if EQ key T- datakey p T return TRUE 查找成功 else if LT key T- datakey SearchBST T- lchild key T p 在左子树中继续查找 else SearchBST T- rchild key T p 在右子树中继续查找 SearchBST Status Insert_BST BiTree T ElemType e if SearchBST T ekey NULL p s new BiTNode 为新结点分配空间 s- data e s- lchild s- rchild NULL if p T s 插入s 为新的根结点 else if LT ekey p- datakey p- lchild s 插入s 为p 的左孩子 else p- rchild s 插入s 为p 的右孩子 return TRUE 插入成功 else return FALSE Insert_BST void QuickSort SqList L 对顺序表进行快速排序 QSort Lr 1 Llength QuickSort void QSort SqList Lint lowint high if low high 长度大于1 pivotloc Partition L low high QSort L low pivotloc-1 QSort L pivotloc1 high QSort int Partition SqList L int low int high Lr[0] Lr[low] pivotkey Lr[low]key while low high while low high Lr[high]key pivotkey -- high 从右向左搜索 Lr[low] Lr[high] while low high Lr[low]key pivotkey low 从左向右搜索 Lr[high] Lr[low] Lr[low] Lr[0] return low Partition void HeapAdjust HeapType H int s int m rc Hr[s] for j 2sj mj 2 if j m LT Hr[j]keyHr[j1]key j if LQ Hr[j]keyrckey break Hr[s] Hr[j] s j Hr[s] rc HeapAdjust void HeapSort HeapType H for i Hlength2 i 0 --i HeapAdjust Hr i Hlength for i Hlength i 1 --i Hr[1]??Hr[i] HeapAdjust Hr 1 i-1 HeapSort 将单链表按逆序连接 Lnode P HL HL NULL while p null Lnodeq p P p- next q- next HL HL q 统计单链表中等于X的节点的个数 int countX LNodeHLElemType x int i 0LNodep HL计数器 while p NULL if P- data x i p p- next while出循环时i中的值即为x结点的个数 return i countX