一、基本概念 1.1 定义 树时n(n>=0)个节点的有限集。n=0时称为空树。 非空树具有以下特性： 有且仅有一个称为根的节点； 当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1,T2...Tn，其中每个集合本身又是一棵树，称为根的子树。 树作为一种逻辑结构，具有以下特点： 树的根节点没有前驱，除根节点以外的其他节点有且只有一个前驱； 树中所有节点可以有0或者多个后继； n个节点的树中有n-1条边。 1.2 基本术语 从节点A->K的唯一路径上的任意节点，称为K的祖先，B为K的祖先，K为B的子孙，E是K的双亲，K为E的孩子。有相同双亲的节点称为兄弟，K和L是兄弟 树中一个节点的孩子个数称为该节点的度，树中节点最大的度数，称为树的度。如节点B度为2，节点D度为3 度大于0的节点称为分支节点，度为0的节点称为叶子节点 节点的深度、高度和层次 节点的层次从根节点开始定义，逐级向下递增 双亲在同一层的节点称为堂兄弟，如K、L、M互为堂兄弟 节点的深度是从根节点开始自顶向下累加的 节点的高度是从叶子节点开始自底向上累加的 树的高度是树中节点的最大层数 路径..... 数据结构学习笔记--树与二叉树 待分类
一、基本概念 1.1 定义 1.1.1 串 串是由0或者多个字符组成的有限序列。一般记为S='aa1...an' S是串名，ai可以是字母、数字或者其他字符； 1.1.2 串长 串中字符个数n称为串的长度，n=0时的串称为空串 1.1.3 子串 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应的称为主串。某个字符在串中的序号称为该字符在串中的位置，当两个串的长度相等，且每个位置对应的字符相同，则这两个串是相等的 1.1.4 空格串 由一个或多个空格组成的串 1.2 串的存储 1.2.1 定长顺序存储 用一组连续的存储单元存储串的字符序列，是一个固定长度的数组 #include <stdio.h> // 固定长度的串 typedef struct SString { char ch[10]; int length; }SString; int main() { SString str; str.ch[0] = 'H'; str.ch[1] = 'e'; str.ch[2] = 'l'; str.ch[3] = 'l'; str.ch[4] = 'o'; str..... 数据结构学习笔记--串 数据结构
一、栈 1.1 基本概念 栈是只允许在一端进行插入或删除操作的线性表，这意味着我们可以使用顺序表或者链表的形式来实现一个栈，遵循后进先出的原则 栈顶 线性表允许插入或删除的一端 栈底 不允许插入或删除的一端 空栈 不含有元素的空表 1.2 基本操作 InitStack 初始化一个空栈S Push 入栈 Pop 出栈 GetTop 获取栈顶元素 PrintStack(&S) 遍历栈元素 出栈入栈流程如下 1.3 栈的实现 栈是一个线性表，可以使用顺序表实现，也可以使用链表实现 1.3.1 栈的顺序表实现 使用顺序表实现栈时，需要提前申请连续的内存空间，且存在栈满、扩容等问题 可以建立一个数组，数组头部作为栈底，数组尾部作为栈顶，同时使用一个变量来记录当前栈顶元素所在的数组下标，所有操作都在栈尾进行，这样可以避免移动元素 #include <stdio.h> #include <stdlib.h> #define MAX_SIZE 8 #define ARRAY_STACK_INCRE_MENT 8 typedef enum Status { OK, MEM.... 数据结构学习笔记--栈和队列 数据结构
wenyl 的个人博客