数据结构第一章绪论
2024-04-14 23:36:54 0 举报AI智能生成
登录查看完整内容
计算机科学与技术408系列之数据结构
作者其他创作
大纲/内容
数据的基本单位（整体）（行）-由若干数据项组成
数据元素
数据的最小单位（列）
数据项
性质相同的数据元素的集合——字符型变量
数据对象
有说数据间的关系就是数据结构
数据结构是带结构（关系）的数据元素集合
数据元素的前后关系——逻辑结构
数据元素在计算机中的存储方式——物理结构
元素间关系
数据结构包括
数据结构
与数据元素本身的形式、内容、相对位置、个数、存储无关
独立于计算机，抽象出来的，从逻辑关系上描述数据的一种数学模型。
线性表、栈、队列
线性结构
集合、树、图
非线性结构
关系
包含两个要素
数据的逻辑结构
存数据对象时，既要存储各数据元素数据。也要存储数据元素之间的逻辑关系
数据对象在计算机中的存储表示
需要一块连续的存储区域，方式：逻辑上相邻的结点存储在物理位置相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系体系
顺序存储结构
不需要所有结点占用一片连续的存储空间，结点间的逻辑关系由附加的引用字段（指针）来表示
链式存储结构
存储方式：采用附加的索引表方式存储结点信息，索引表由若干索引项（关键字、地址）组成
索引存储结构
存储方式：根据结点的关键字直接算出该结点的存储地址（通过散列函数，哈希函数）
散列存储结构
数据物理结构（四种基本存储结构）
无论顺序存储还是链式存储，每个结点都要占用一片连续的存储区域
同一逻辑结构采用不同的存储方法可以得到不同的存储结构
数据的物理结构
数据类型是一个值的集合和定义在这个值集上的一组操作的总称
数据类型
数据对象间的关系
数据对象的基本操作
是指由用户定义的，表示应用问题的数学模型以及定义在这个模型上的一组操作的总称（结构体）
抽象数据类型ADT
数据结构的基本概念
定义：是对特定问题求解步骤的一种描述，是指令的有限序列。
有穷性：一个算法总是在执行有限步后结束，且每一步都是在有穷时间内完成
任何条件下算法只有唯一的执行路径，即1：1，相同输入得相同输出
确定性：算法的每一条语句指令都必须由确定的含义，别人理解时候不产生二义性。
可行性：算法可行，即算法中描述的操作均可由有限次已成型的基本运算实现
输 入：可以有0个或多个输入
输 出：可以有1个或多个输出
算法的五个特性：
正确性
可读性
健壮性
高效率和低存储量
一个好的算法包括四个方面：
算法执行的效率与数据的逻辑结构，物理结构，程序的控制结构，输入的数据量 问题规模n，语句频度（T与n关系），解决问题的策略等有关。
❌
算法最终必须由计算机程序实现
同一个算法，实现语言的等级越低，执行效率越高，越快
算法
算法的时间复杂度与选择的程序设计语言无关
执行算法的语句次数/语句频度
T与n的关系
关注基本操作执行的次数
现实中常讨论最坏情况下的时间复杂度，所以，所谓时间复杂度是指最坏情况下估算算法执行时间的一个上界。
问题的规模
不考虑与空间复杂度的关系
（如某些算法受数据初始状态杂乱程度的影响）
待处理数据的状态
算法时间复杂度取决于
强调相同规模n下的情况下，O(n)才总比O(n²)快。否则不一定
算法时间复杂度并不是指算法执行时所用的具体时间，时间复杂度是一个函数（定量的描述了算法的运行时间）
T(n) = O(f(n))
n是指问题规模；即输入的数据量；数据的个数；数据的规模
O(1)算法运行时间与数据量大小无关。
O(n)算法运行时间与数据量大小呈线性关系，即数据量增大n倍，算法运行时间增大n倍。
O(n²)算法运行时间与数据量大小呈线性关系，即数据量增大n倍，算法运行时间增大n²倍。
要循环次数最多的那段代码
循环次数最多原则
要量级最大的代码块代码
加法原则
内外嵌套且无关：内外乘积
乘法原则
计算原则
①找出循环条件；②设循环次数a，③找a与i关系；④代入条件；⑤出结果
分单层循环①②③④⑤步
②若内外无关，就各算各的，相当于两次单层循环任何乘起来
②若内外有关，则列累加求和式，由右向左算，最后再当单层循环算①②③④⑤步
①看内外是否无关
和多层循环①②步
计算方法
时间复杂度
执行当前算法需要占用多少辅助空间
算法所需存储空间的量度
S(n) = O(f(n))
含义：原地工作是指不需要任何额外的辅助空间
算法所需要的辅助空间（临时空间）不随问题规模n而变化，即辅助空间与n无关
则此算法的空间复杂度为一个常量。记作O(1)
原地工作：
空间复杂度
确定算法的优劣
算法效率的度量
算法和算法分析
1绪论
定义：线性表是 相同数据类型 的n(n >= 0)个数据元素 的 有限 序列
顺序表可以随机存取O(1)，插入和删除是O(n)链式存储的查询是O(n)，插入和删除是O(1)单链表只能单向按顺序查找
特点：
线性表
插入：(n + 0)n/2 * 1/n = n/2
删除：(n-1 + 0)n/2 * 1/n = (n-1)/2
顺序存储的线性表中移动元素的次数
在长度为n的顺序表第i个位置插入一个元素时，元素移动次数为n-i+1，即要移动该位置及其之后的所有元素
当已知顺序表中元素的查找概率时，为使查找成功的平均查找长度达到最小，则应交换表中元素次序，查找概率大的放在顺序表的前列
顺序表
线性表的链式存储结构称为链表。每个存储结点不仅包括结点本身信息，且饱含元素与元素之间的逻辑关系信息，分别称数据域与指针域。链式存储设计时，各个不同结点的存储的存储空间可以不连续，但结点内的存储单元地址必须连续。
单链表：单向性，单链表中只有一个指示直接后继的指针域（因此从某个结点出发只能顺着指针往后查找其他结点，若查找结点的直接前驱，则需重新从表头出发）。
单链表中访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)
单链表带头结点的优点：1️⃣使链表 首结点的插入和删除操作 与其他结点一致。无需特殊处理。2️⃣无论单链表是否为空，均有头结点，统一空表与非空表的处理过程。
头插法与尾插法：头插法：是将新的结点插入到当前链表的表头上（插入在头结点之后，原开始结点之前）。形成一个“逆序”的序列。 s->next = L->next; L->next = s;尾插法：是将新的结点插入到当前链表的表尾上（将s插入到r尾指针之后）。形成一个“顺序”的序列。 r->next = s; r=s; (原r 与 现r)
不带头结点的单链表：空表：head == NULL; //头指针直接指向第一个结点
带头结点的单链表：空表： head->next == NULL;
外框
单链表
双链表的结点中有两个指针域，一个指向直接后继，一个指向直接前驱。
从任一结点出发可以快速访问其他结点。
双链表可以从任一结点出发可以快速找到某一结点的前驱结点和后继结点。
优点：
尾插法：r = L; //r始终指向尾结点，开始时指向头结点s->data = a[i]; r->next = s； //将s插入r之后s->prior = r;r = s; //将r指向尾结点
双链表的头插法与尾插法：头插法：s->data = a[i]; //创建数据结点ss->next = L->next;if(L->next != NULL) //若L存在数据指针 则需要 修改前驱指针 L-> next->prior = s; L->next = s;s->prior = L;
双链表
因此从表中任一结点出发，都可以找到链表中的其他结点。
有的单循环链表不设头指针，只设尾指针。这是因为 单循环链表有了尾指针之后 r->next 就转化为了 头指针——>这样对表头 表尾 的操作就都成了O(1)。
单循环链表在实现约瑟夫问题时不需要头结点。
单循环链表：单循环链表的 尾结点 next域 指向头结点，使整个单链表形成一个环。
因此从表中任一接结点出发，都可以找到链表中的其他结点。
双循环链表：双循环链表的尾指针next指向头结点，而头指针的prior指针指向尾结点，这样使整个双链表形成两个环。
循环链表
与指针型描述的线性链表有所不同。
静态链表是利用一维数组去描述一个线性链表。
静态链表的整形变量cur便于在不设“指针”类型的高级程序语言中使用链表结构。这样数组的一个分量表示一个结点，游标（指针域cur）代替指针 用以指示结点在数组中的相对位置。数组的0结点看成头结点，其指针域指示链表的第一个结点。
静态链表结构需要预先分配一个较大的存储空间，但在做线性表的插入和删除操作时不需要移动元素，只需要修改指针，故仍具有链式存储结构的主要优点。
静态链表
链式存储的定义和特点
给不带头结点的单链表的头上插入一个新结点，相当于无头结点的头插法：将t的下一结点指向h，然后将t改为新的头结点。 t->next = h; h=t;
一个单链表中，有头尾两个指针，执行什么操作与链表的长度有关删除第一个元素。 删除最后一个元素。 在第一个元素前插入一个元素。 在最后一个元素后插入一个元素。单链表中想找到最后一个元素只能按顺序遍历。
单链表中删除时候：先存再删
如删除链表的第一个元素：【先存后删】【p尾指针，q临时指针存待删结点】q = h->next; h->next = h->next-next； (h->next = q->next;)if(p==q) p=h; //将尾指针指向头结点 free(q);
以单链表方式存储的队列，在进行删除时候一般只用修改队头指针即可，但有一种情况就是出队以后是空队列了，需要修队尾指针以对准队头指针。所以链队列的删除运算时，头尾指针都有可能修改。
若用单链表来表示队列，则选用带尾结点单循环链表来实现表头出队（删除），表尾入队（插入）。
先建表，后依次插入建立有序表 O(n的平方)
先排序，后建表 O(n*log2n)
给定n个元素的一维数组，建立一个有序单链表的最低时间复杂度是：O(n*log2n)
删除p指针：【先连p的前驱，后连p的后继】p->next->prior = p->prior; p->prior->next = p->next
*p之后插入*s：先处理待插入结点的后继，再处理后一结点的前驱；然后处理前一结点的后继，再处理待插入结点的前驱。s->next = p->next; p->next->prior = s; p->next = s; s->prior = p; 1️⃣ ——> 2️⃣ <—— 3️⃣ ——> 4️⃣ <——先处理待插入结点的前驱，再处理待插入结点的后继；然后处理前一结点的后继，再处理后一结点的前驱。 s->prior = p; s->next = p->next; p->next = s; s->next->prior = s; 1️⃣ <—— 2️⃣ ——> 3️⃣ ——> 4️⃣ <——先处理待插入结点的前驱，再处理待插入结点的后继；然后处理后一结点的前驱，再处理前一结点的后继。 s->prior = p; s->next = p->next; p->next->prior = s; p->next = s; 1️⃣ <—— 2️⃣ ——> 3️⃣ <—— 4️⃣ ——>
*p之前插入*q：先处理前一结点的后继，再处理待插入结点的后继；然后处理待插入结点的前驱，再处理后一结点的前驱 p->prior->next = q; q->next = p; q->prior = p->prior; p->prior = q; 1️⃣ ——> 2️⃣ ——> 3️⃣ <—— 4️⃣ <——
共性就是：平行的去处理，且箭头都对应完整
非循环链表可以没用头结点，有头结点只是更好，操作一致循环链表必须要有头结点，否则循环没有意义，找不到循环的头了（没有腰带扣啦）
单循环链表的主要优点：从表中任一点出发都能扫描遍历到整个链表
单循环链表的判空条件：head->next == head;
某线性表常用的操作是：在最后一个结点后插入一个新结点 或 删除第一个元素 最适合用：带有尾指针的单循环链表在最后一个结点后插入一个新结点 或 删除最后一个结点 宜采用：双向链表
单循环链表
双循环链表
定义：静态链表是使用一维数组实现的链式存储结构
特点：整体需要分配较大的存储空间。 适合 插入、删除 操作 还是不适合随机存储哈
题型总结
考点
链表
链式结构使用的是指针，指针的创建与设置比较万能，代表性强故可更方便的表示各逻辑结构
顺序存储结构只能通过其物理上的顺序邻接来体现逻辑结构
顺序存储与链式存储的对比
栈是操作受限的线性表，仅允许在表尾（栈顶）进行插入和删除操作栈的表头称作栈底，栈的表尾称作栈顶。
特点：后进先出：LIFO 先进后出：FILO
定义
定义：栈由两个指针组成，栈底指针指向栈底，栈顶指针初值指向栈底，插入top+1，删除top-1，所以栈顶指针总是指向栈顶元素的下一个位置
所以top指针就表示新的栈顶。（数据可能残留在内存中，只是逻辑上被删除）
top指向当前栈顶元素的位置。
栈的顺序存储结构：顺序栈
单链表——头插法
实现：采用不带头结点的单链表实现。规定栈的所有操作都只在此单链表表头进行。
优点：不存在栈满溢出的情况
栈的链式存储结构： 链栈
存储
顺序栈结构体：typedef struct{ SElemType *base; //栈构造之前和销毁之后，base=NULL SElemType *top; int stacksize; //表示当前已分配的存储空间}Sqstack
初始化：Status InitStack(SqStack &S){ S.base = (SElemType *)malloc (STACK_INIT_SIZE * sizeof(SELemType)); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;}
销毁：Status DestroyStack_Sq(Sqstack &S) {}
栈空：S.top = S.base;
栈满：S.top == MaxSize-1
顺序栈操作
初始化：Status InitStack(LinkStack &S){ s = NULL; return OK;}
链栈的进栈相当于单链表的头插法
取栈顶元素：Status GetTop(LinkStack s){ if(s != NULL) return s->data;}
链栈操作
初始化：S.top = -1; //top现在指向栈顶元素
栈顶元素：S.top[S.top]
S.data[++S.top] = x;
进栈：栈不满时，栈顶指针先+1，再赋值值到栈顶元素
x = S.data[S.top--]
出栈：栈非空时，先存栈顶元素，再将栈顶指针-1
栈空：S.top == -1;
栈满：S.top == MaxSize-1;
栈长：S.top + 1;
顺序栈的操作（2）
初始化：S.top = 0; //top指针指向栈顶元素的下一个位置
栈顶元素：S.top[S.top-1];
进栈：S.data[S.top++] = x;
出栈：x = S.data[--S.top];
栈空：S.top == 0;
栈满：S.top == MaxSize;
栈长：S.top;
改变栈顶指针，改变top指针
若需要用到两个相同类型的栈，可用一个数组data[0...maxSize-1]来实现这两个栈，称为共享栈（共享一个一维数组）。数组的左右两个端点分别是两个栈的栈底，一个栈的栈底为数组始端0，另一个栈道栈底为数组末端MaxSize-1当元素进栈时，栈顶向共享空间的中间延伸。
定义：
存取数据的时间复杂度是O(1)
可以更新有效的利用存储空间，节省存储空间，两个栈的空间可以相互调节，只有在整个存储空间被两个栈占满（即两个栈栈顶相遇）时，才发生上溢（降低上溢发生的几率）。
栈空：top1 = -1 top2 = MaxSize
top2-top1 = 1;
栈满：top1 + 1 == top2;
进栈：top1++; data[top1] = x; top2--; data[top2] = x; S.data[++top1] = x; S.data[--top2] = x;
出栈：x = data[top1]; top1--; x = data[top2]; top2++; x = S.data[top1--]; x = S.data[top2++];
操作：
栈空：top1 = 0; top2 = MaxSize-1;
栈满：top1 == top2; ?
入栈：S.data[top1++] = x; S.data[top2--] = x;
出栈：x = S.data[--top1]; x = S.data[++top2];
改变top指针
为了便于管理，可以将共享栈设计为一个结构体类型。
设计：
共享栈（双端栈）
表达式求值
数制转换
括号匹配的校验
行编辑程序的输入缓冲区
迷宫求解
车辆调度中求出栈车厢序列，
栈的应用
递归的时候用栈。程序调用是一个递归过程，用栈实现，首先从main函数进入，即栈的进栈过程。函数调用是一个递归的过程。
这个入栈出栈序列可以相同，可以互为逆序。
由于栈具有后进先出的特性，所以根据入栈（出栈）序列能判断出出栈（入栈）序列。
因为不知其中元素的出栈时间。
即使确定了入栈次序，也不能就此来确确定定出栈序列。
n个元素进栈，出栈元素的不同排列个数为：卡特兰数 C2n的n / n+1
写出出入栈序列
判断可能取值的个数
共享栈判初始，栈空，满
向一个栈顶指针为top的链栈，插入一个x结点：先将x的next指针域指向top，再将栈顶指针指向xx->next = top; top = x;
通常情况下，递归算法在计算机中的执行过程中会有很多重复的计算或是验证步骤，所以递归算法比非递归算法效率低。
调用函数时，系统将会为调用者构造一个由参数表和返回地址组成的活动记录，并将记录和函数的局部变量压入系统提供的栈中。
题型
栈
队列queue，是一种限制存取位置的线性表，它只允许在表的一端（表尾，队尾）进行插入，另一端（表头，队头）进行删除。
队列的插入和删除操作分别在各自一端进行，每个元素按照进入的次序出队。即先进先出 FIFO。
特点
1️⃣少用一个队列空间，即队列空间大小为m时，认为有m-1个元素时队满。队空：q->front == q->rear;队满：(q->rear+1)%MaxSize == q->front; （约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志）队列长度：(rear - front + m) % m;
2️⃣增设表示队列元素个数的数据成员size。队空：size == 0 && front == rear;队满：size == MaxSize && front == rear;
3️⃣增设tag标签 数据成员以区分队满与空 （队空队满代码一样，那就再设一个变量记录此时队列状态）队空：tag == 0；因删除导致front = rear队满：tag != 0；因插入导致front = rear
+1的原因是下标默认值为-1
循环队列：【0， m-1】front指向队头元素前一个位置，rear指向队尾元素。<=>front指向队头元素，rear指向队尾元素的下一个位置一样 入队时队尾指针前进1：(rear + 1) % QueueSize（QueueSize循环队列的最大长度）出队时队头指针前进1：(front + 1) % QueueSize该循环队列的元素个数 / 队列长度：(rear - front + QueueSize) % QueueSize
循环队列：【0， m-1】front指向队头元素，rear指向队尾元素队列长度（队列中元素个数）： 当rear>front时，当前队列的元素个数是：rear - front + 1 当rear<front时，当前队列的元素个数是：rear - front + m + 1综合上述两种情况： 当前队列的元素个数是：(rear - front + m + 1) MOD m
循环队列：【0， m-1】默认front，rear当前队列中元素个数是：(rear - front + m) % m
将顺序队列臆想为一个环状的空间——循环队列（插入队尾指针增1，通过模来运算）
顺序队列满了怎么办？又不能像顺序栈一样进行数组再分配扩大数组空间。
front队头指针指向队列 队头元素位置，rear队尾指针指向队列 队尾元素的下一个位置。
操作：队空（初始化）：q->front == q->rear;队满：q->rear == MaxSize;进队：data[rear] = x; rear++; q->data[q->rear] = x; q->rear++;出队：x = data[rear]; front++; x = q->data[q->front]; q->front++;
队列的顺序存储结构：顺序队列
实现：采用单链表来实现队列，在单链表表头删除，表尾插入。
是一个同时带有 队头指针（指队头结点） 和 队尾指针（指队尾结点） 的 单链表
本质：
链队列在做删除运算时，看成单链表的删除操作：当队列有多个元素时，只需修改头指针即可。当队列只有一个元素时，该结点既是头又是为尾，则需要修改尾指针置空。
特点：同链栈一样，不存在队满溢出的情况
用单链表表示的链队列适合于数据元素变动较大的情形，且不存在队列满产生溢出的问题
适合：
LinkQueue结构体声明：typedef struct qnode{ QElemType data; struct qnode *next;}DataNode;typedef struct{ DataNode *front; DataNpde *rear;}LinkQuNode;
front == rear q==null
带头结点
front+1 == rear q->next=null
不带头结点
链队列的判空条件
操作：队空：q->front = q->rear;队满：不考虑入队：插入到单链表表尾出队：删除单链表表首结点(q->front ==NULL; 且 q->rear == NULL;)
队列的链式存储结构：链队列
定义：是指队列的两端都可以进行进队和出队操作，不受限制，其元素的逻辑关系仍为线性关系。
问：既然队列前后端都可以出入队，那是不是可以想得到什么序列就得到什么序列？例如dcab这个序列，可以ab后端进，cd前端进，最后都从前端出。但是abcd入队，出队dacb是不无论如何也出不来的。因为c不论是前端进出还是后端进出，都无法在ab之间。
特点：双端队列中，元素从前端进后段出 或 从后段进前端出，都体现了队列先进先出的特性。 而元素从前端进前端出 或 从后端进后段出，则体现了栈的后进先出的特性。
若只能从左进（限制入队），左右都能出，则说明已知入队序列，想要得到目标序列就看左右两边怎么出队了。
若只能从右出（限制出队），两边都能进，则说明目标序列只能从右边出来，看左右两边怎么进能得到目标序列。
实际使用中，可以自定义双端队列的两端进出规则。若再次限定双端队列中从某端进队的元素只能从某端出队，则该双端队列即变为了两个栈底相邻的栈。
双端队列
队列的应用
F1：自己按逻辑排一下，顺一下。
F2：以第一个入队元素A为中心，在队列中向左向右看都是顺序，没有逆序，则可实现。
F3：以ab或是其他挨着的序列看，无论ab是从一端进还是两端进，只要已知入队顺序，则在队列中，ab必相挨。
做自定义双端队列出入时，已知入队顺序，判不可能的出队顺序。
rear = (rear+1) % MaxSize
front = (front+1) % MaxSize
顺序队列中判断front，rear指针位置时，注意套公式。
队列
子主题
summary
前言：矩阵在计算机图形学、工程计算中占有举足轻重的地位，而在数据结构中，我们的精力重心放在如何让将矩阵更有效地存储在内存中，并能方便地提取矩阵中元素。
每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
一维数组是由n（n=>1）个相同数据类型元素组成的有限序列
二维数组也叫矩阵，行列相等的叫方阵。
一个二维数组（矩阵）可以看作是每个数据元素都是相同数据类型的一维数组的一维数组。
数组与线性表的关系：数组是线性表的推广
数组一旦被定义，其维数和维界就不再改变。即数据元素数目固定，一旦定义来一个数组，其数据元素的数目不再有增减的变化。
读操作：给定一组下标，读取相应的数据元素。
写操作：给定一组下标，存储或修改相应的数据元素。
数组中通常只有两种操作：不做插入与删除上因为定义好数组后长度就固定了
数组中的数据元素数目固定。一旦定义来一个数组，其数据元素的数目不再有增减的变化。
数组中的数据元素具有相同的数据类型。
数组中的数据元素都和一组唯一的下标一一对应。
数组是一种随机存储结构，具有随机存取的特性，即可随机存取数组中的任意数据元素。
性质
通常将数组的所有元素存储到存储器的一块地址连续的内存单元中，即数组特别适合采用顺序存储结构来存储。
设：每个元素占用k个内存单元LOC(ai) = LOC(a1) + (i-1)*k (1 <= i <= n)
一维数组的存储结构：
二维数组的存储结构：
数组的存储结构
定义：特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。 所以利用此种规律对数组进行压缩存储进而提高存储空间效率。
对称矩阵按主对角元素对称，其上下三角部分对应元素相等，所以存储时可以只存主对角元素+上/下三角元素。(存一半就行)
k = i * (i-1) / 2 + j-1
在以行序为主序的存储方式下，存下三角元素（i => j）至一维数组B：b k = (i+1)*i / 2 + j
k = j * (j-1) / 2 + i-1
在以行序为主序的存储方式下，存上三角元素（i < j） 至一维数组B：b k = (j+1)*j / 2 + i
对称矩阵的存储：
font color=\"#4669ea\
上三角矩阵：上三角矩阵的上三角为正常序列（i<=j），下三角为常数C的n阶方阵。
下三角矩阵：下三角矩阵的下三角为正常序列（i > j），上三角为常数C的n阶方阵。
i => j : k = (i+1) * i / 2 + j
i < j : k = (n+1) * n / 2
下三角( i > j )以行序为主序的方式存储
k = ( n + n-i+2 ) * ( i-1 ) / 2 + j-ik = ( 2n-i+2 ) * (i-1) / 2 + j-i
i <= j : k = ( n + n-i+1 ) * i / 2 + j-i k = ( 2n-i+1 ) * i / 2 + j-i
i > j : k = (n+1)*n/2
上三角( i < j )以行序为主序的方式存储
三角矩阵的压缩存储
A中行下标为0的行和行下标为n-1的行都只有两个非零元素，其余各行有三个非零元素。
此时 j = i-1，即k=2i + i-1 = 2i+j
i.1 : k = 2+3(i-1) = 3i-1
此时 j = i，即k=2i + i = 2i+j
i.2 : k = 2+3(i-1) + 1 = 3i
此时 j = i+1，即k=2i + i+1 = 2i+j
i.3 : k = 2+3(i-1) + 2 = 3i+1
在第i行分为三种情况
【0，n】此时的 k = ( 2i + j - 3 ) + 1
【1，n】此时的 k = 2i + j - 3
前i行存储元素总数2+3(i-1)
三对角矩阵的压缩存储
特殊矩阵包括：均为方阵，即m=n（行数=列数）
特殊矩阵
⚠️稀疏矩阵压缩存储后便失去了随机存取的特性
稀疏矩阵中的非零元素的个数相较于矩阵元素总个数来说非常小，且分布没有规律。
顺序存储 => 形成三元组顺序表（三元组表）
三元组表示法：稀疏矩阵中的每一个非零元素由一个font color=\"#5b79e8\
采用链式存储结构来表示三元组线性表，链表中的每个非零元素既是某个行链表中的一个结点，又是某个列链表的一个结点。整个矩阵构成十字交叉的链表。
采用两个分别存储 行链表的头指针 和 列链表的头指针 的一维数组来表示。
十字链表表示法：当矩阵的非零元素个数和位置在操作过程中变化较大时，就不宜采用顺序存储来表示三元组的线性表。——>
稀疏矩阵的存储
稀疏矩阵：
对称矩阵中，上三角按列优先 = 下三角按行优先 计算时候：（上列 <=> 下行）（公式中 i 换成 j ）（所求的具体下标中 i，j 也互换）
三角矩阵的计算：首先看需要求的矩阵位置点位于上三角还是下三角，然后对应看题目要求的存储方式，再去对应公式计算。
若矩阵0，1 放到数组B [1，n]，则还按经典公式算，最后 +1 即可
矩阵0，1开始放到数组B [0，n-1] 算经典公式
数组 和 特殊矩阵
对称矩阵上下三角对应元素相等，所以存一半就行
上三角存储：1——n2——n-13——n-2 ......i——n-i+1
补充
树的定义是递归的，所以树是一种递归的数据结构。
树是n（n => 0）个结点的有限集合T，满足：（当n=0时，称为空树）1️⃣有且仅有一个特定的被称为“根”的结点。2️⃣其余结点分为m（m > 0）个互不相交的子集T1、T2、T3，其中每个子集又是一棵树，称为根的子树。
树的定义：
树中每个元素（除根结点外）均有一个直接前驱（辫子），有零个或多个后继。——故n个结点有n-1条边。
树是一种非线性的数据结构，一对多。
树适合表示具有层次结构的数据
度=m，则为m叉树
度为 k 的树也称 k叉树，其中每个结点最多有k个子树
结点的度：一个结点的子树个数。树的度：该树中结点的最大度数。
度不为零的结点。N1，2
分支结点（非终端结点）：
度为0的结点。N0
叶子结点（终端结点）：
⚠️在树的分支结构中，每个结点的分支数就是该结点的度数。如：对于度为1的结点，其分支数为1，为单分支结点；度为2的结点，其分支数为2.，称为双分支结点。
孩子结点和双亲结点：树中某个结点的子树的根，该结点则为孩子的双亲结点。
堂兄弟结点：双亲结点是兄弟关系的结点（即在同一层）。
兄弟结点：同双亲的孩子结点互称为兄弟。
该结点的祖先是从树的根结点到该结点所经分支上的所有结点。
以某结点为根的子树中的任意结点 称为该结点的子孙。
子孙结点和和祖先结点：
基本结点介绍：
树中结点的最大层数称为树的高度或深度。
树的层次：从根结点开始，根为第1层，其子结点为第2层，以此类推。
树的深度：从根结点开始 自上而下 数。
树的高度：从叶结点开始 自下而上 数
树的层次、深度和高度：
有序树：树中结点的各子树从左到右有次序，位置不可互换；若互换，则称为一棵不同的树。
无序树：树中结点的各子树交换，不影响树的基本排列。
有序树和无序树
路径：树中两个结点的路径是指两个结点之间所经过的 结点 的序列。
路径长度：在此路径上所经过的结点个数。
同一双亲的孩子之间不存在路径。
⚠️树中的分支是有向的，即从双亲指向孩子，所以树中的路径树从上到下的。
树的路径长度是指 树根到每个结点的路径长度的 总和。
路径与路径长度；
若在两棵树中，各结点对应相等，各结点的对应关系也相等，则称这两棵树相等或等价。
若在两棵树中，适当重命名其中一棵树的结点可以使两棵树等价，则称为树的同构。
树的等价和同构：
所以树与森林可以相互转换。
显然，删除一个树的根，就可以得到一个森林；反之加上一个结点作为树根，将这m棵树作为该结点的子树，森里就变为一棵树。
森林是m（m => 0）棵互不相交的树的集合。
森林：
与树有关的术语：
写两个式子：n = n0 + n1 + n2 + n3 （设n0 n1 n2 n3 分别是度为0123的结点个数） 等于各度数的结点数量之和n = 0*n0 + 1*n1 + 2*n2 + 3*n3 + 1
树的结点数 = 所有结点的度数 + 1 = 总度数 + 1 = 分支数 + 1
度为m的树中，第i层上至多有 m的i-1次 个结点。
高度为h的m叉树 至多有( m的h次-1 ) / (m-1)。
具有n个结点的m叉树的最小高度是logm(n*(m-1)+1)。
树的性质：
根到每个结点的路径长度最大值为：h-1。
树有n个结点，度为m，要使此树最高：h = n - (m-1) 【即除最后一层外，每层结点数为1，即只有最后一层为m】。
已知结点总数n，度数m，求树的最小高度，那就是把每一层的每一结点都排满度数 n - (1 + m + m的2次 + m的3次...) 或者套公式：logm(n*(m-1)+1)。
已知树高h，度数m，求结点总数，则n至少为 h + (m-1)； 至多为 1 + m + m 的2次 + ... + m的h-1次 = ( m的h次-1 ) / (m-1)。
若结点数量为n，则边的数量为n-1。
树的题型：
树
二叉树由一个根结点及两棵互不相交的，分别称作该根的左子树和右子树的二叉树组成。（递归定义）
二叉树（Binary Tree）是 n (n=>0)个结点的有限集合。（二叉树可以为空）
二叉树的定义：
每个结点最多只能有两棵子树（即二叉树不存在度 > 2的结点），并且这两棵子树有左右顺序之分，其次序不能随意颠倒。
度为2的树最最少 (至少) 有三个结点，但是二叉树是可以为空的。
而二叉树即使只有一个孩子，也要严格区分左右，即左孩子和右孩子。（因为二叉树的孩子左右是确定好的，不是相对于另一个的）
度为2的有序树的孩子虽然有左右之分，但若只有一个孩子，则不分左右。（因为有序树孩子的左右次序是相对于另一个孩子而言的）
总结：由此来看，二叉树与树是两个不同的概念。二叉树既不是树的特殊情况，也不是有序树的特殊情形。
二叉树与度为2的有序树的区别；
二叉树的主要特征：
定义：满二叉树的每一层上的结点数都达到了最大（即给定高度的二叉树中，满二叉树结点数最多）
满二叉树中的每层都含有最多的结点。
满二叉树的深度为k，则有2的k次-1个结点。
满二叉树中不存在度为1的结点（除叶子结点外），每个分支结点的度数都是2。
即满二叉树的叶结点全在最后一层。
满二叉树的每个分支结点均有两棵高度相同的子树，且所有叶结点均在最下面一层。
其双亲为 i-1/2，左孩子为 2i+1，右孩子为 2i+2。
【 若 i 属于[0，n-1] 】
例：i=5 的双亲结点为：⌊5/2⌋=2
对于编号为 i 的结点来说，其双亲为⌊i/2⌋，左孩子为2i，右孩子为2i+1。
可对满二叉树的结点进行连续编号，一般约定，从根结点开始，按“自上而下，自左向右”按层序排序编号。
1️⃣满二叉树：(Full Binary Tree)
即深度为k的满二叉树中编号从1～n的前n个结点构成了一棵深度为k的完全二叉树。【2的k-1次<= n <=2的k次-1】
在完全二叉树中，至多只有最下面两层的结点的度可以小于2，并且最下层的结点都集中在该层的最左边的若干位置。比满二叉树少了最右边的几个叶结点。
定义：若高度为h，结点数为n的二叉树，当且仅当其每一个结点都与高度为h的满二叉树中编号从1-n的结点一一对应。
即高度为h的完全二叉树中，其1～h-1层构成了一个高度为h-1的满二叉树。共有2的h-1次-1个结点。
一棵完全二叉树，前 h-1 层为满二叉树
完全二叉树的高度 是所有 二叉树 中 最小的高度。
具有n个结点的完全二叉树的 深度/高度 为 ⌊log₂ n⌋+1 / ⌈log₂(n+1)⌉ = ⌊log₂ 2n⌋
在完全二叉树中，若有度为 1 的结点，则只有一个结点 且 该结点只有左孩子而无右孩子。
完全二叉树中n1的取值只可能为0或1。
例：完全二叉树最后一个结点为n，其父结点为 s = ⌊n/2⌋，叶结点个数：n0 = n-s
i > ⌊i/2⌋ 为叶子结点。
叶结点只可能在层数最大的两层中出现。
在完全二叉树中，若某一个结点没有左孩子，则其一定没有右孩子，即必定为叶结点。【因为根据定义，完全二叉树必须先有左孩子、再有右孩子】
若已知完全二叉树的第 i 层出现了叶结点，说明此树高h = i 或 i+1
为完全二叉树按层序编号后，一旦出现某个结点( i )为叶结点或 i 只有左孩子，则 > i 的结点全为叶子结点。
完全二叉树叶结点特点
若编号n为奇数，则每个分支结点均有左右孩子；若编号n为偶数，则编号最大的分支结点只有左孩子无右孩子。其余分支结点左右孩子均有。
满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。
空二叉树和只有根结点的二叉树 既是满二叉树，也是完全二叉树。
【找 双亲】 若 i>1 ，i双亲是结点 ⌊i/2⌋（下取整），即：当i为偶数时，则其双亲是 i/2（ i是双亲的左孩子 ）；当i为奇数时，其双亲的编号为(i-1)/2（ i是双亲的右孩子 ）。
故 i > n/2（下取整）必定是叶子
【找 左孩子】若2i <= n，则结点 i 的左孩子编号为 2i，否则无左孩子（即结点i 为叶结点） 。
【找 右孩子】若2i+1 <= n，则结点i 右孩子编号为 2i+1，否则无右孩子。
结点 i 所在的层次 (深度) 为 ⌊log₂ n⌋+1
对于一棵有n个结点的完全二叉树（ 其深度为⌊log₂ n⌋+1 ）的结点按层序编号（ 从第1层到⌊log₂ n⌋+1层 ），每层中从左到右，则对任一结点 i (1 <= i <= n)，i=1为根，有：
2️⃣完全二叉树：(Complete Binary Tree)
定义：在平衡二叉树中，任意一个结点的左子树和右子树深度之差的绝对值不超过 (<=) 1。
平衡二叉树有更高的搜索效率。
平衡二叉树 本质上是 二叉排序树。❓
从平衡因子定义看，完全二叉树任一结点平衡因子绝对值<=1，但完全二叉树不一定是排序树，所以不是平衡二叉树。
3️⃣平衡二叉树：(Balance Binary Tree)
定义：在二叉排序树中，左子树上所有结点的关键字 均小于根结点的关键字，右子树上所有结点的关键字 均大于根结点的关键字。
二叉排序树的左子树，右子树又是一棵二叉排序树。（且是递归定义）
二叉排序树方便关键字的检索，插入操作。
4️⃣二叉排序树：(Sort Binary Tree)
几种特殊的二叉树：
二叉树第 i 层上的结点数为2的i-1次。(i => 1)
深度为 k 的二叉树至多有2的k次-1个结点。(全满)【以2为公比的等比数列求和（0～k-1）】
二叉树高度为 h，且只有度为0，2，则结点数 至少( 最少 )有：1 + 2(h-1) = 2h-1 （即第一层一个，其余h-1层均有两个结点）
高度为 h 的二叉树至多有2的h次-1个结点。
n与n0关系：n = 2n0 - 1 +n1
对任何一个二叉树，都有：n0 = n2 + 1。
一般二叉树高度：⌊log₂n⌋+1 ～ n
具有n个结点的二叉树，要求其最小高度：——>当二叉树构成完全二叉树时，高度最小。h = log₂ n + 1 = log₂ 50 + 1 = 5+1 = 6。 所以h=6。
二叉树的性质：
可以问：构造二叉树时：结点最多：——> 满二叉树。若为完全二叉树，则根据前h-1层为满二叉树，数形结合的看。结点最少：——> 1+(h-1)*2。高度最高：——> h = n （ 二叉树高度范围：⌊log₂ n⌋+1 ~ n ）高度最低：——> 完全二叉树 在 二叉树 中 高度最低。（最小深度）
二叉树的题型：
二叉树的顺序存储就是将所有结点存储到一组连续的存储单元中（数组），并能通过结点间的物理位置关系反映逻辑关系（双亲和孩子关系）。顺序存储时，结点间的次序关系要能反映结点间的逻辑关系。用数组下标（编号）来表示结点之间的父子关系。（根据二叉树的性质）
顺序存储编号建议从数组下标 1 开始存储树中的结点，否则下面的性质无法实现。
编号过程：首先把树根结点定为1，然后按照层次从上而下，每层从左至右的顺序，对每一结点进行编号。 即将二叉树上编号为 i 的结点存储在一维数组下标 i-1 的分量中。
顺序存储的随机存取，i，2i-1，2i+1。
便于访问每一结点的 双亲 和 左右孩子。
二叉树的顺序存储结构适用于 完全二叉树 和 满二叉树。这样既能充分利用、节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。
对退化的二叉树（每个结点都是单分支），或单分支较多的一般二叉树来说不实用，空间浪费较为严重，空间利用率低。
存储一般二叉树的时候，为了能让数组下标反映二叉树中结点的关系，所以添加用0表示的空结点，让其与完全二叉树对照，再存到一维数组的相应分量中。
最坏情况下，高度为 h 的h个结点的单支树，竟然需要2的h次 -1个存储单元。
顺序存储的二叉树 插入、删除等操作不方便。
缺点：
顺序存储结构：
即为二叉链表存储结构——参考双链表：一个data数据结点，两个指针，一个左指针，一个右指针。
若增加父结点的指针，双亲域，即为三叉链表。
一般二叉树 通常采用链式存储结构存储。
声明：typedef struct BTNode { ElemType data; struct BTNode *lchild; struct BTNode *rchild;}BTNode
利用n+1个空链域存储结点直接前驱与后继，则形成线索链表。
特点：对于n个结点，有2n个指针域；n-1个前驱指针 (辫子，非空指针)；n+1个空链域。【2n-(n-1)=总分支-非空指针=空指针】
链式存储结构：
静态链表存储：
二叉树的存储结构：
这里的访问是指对结点进行某种处理，包括：读、写、修改和输出结点信息。
定义：二叉树的的遍历( Traversal )是指沿某条搜索路径巡访二叉树，对每个结点访问一次且仅访问一次。
作用：通过一次完整的遍历，可使二叉树的结点信息由非线性排列变为某种意义上的线性序列。
根左右
先序(根)遍历：
void preOrder(BTNode *T) { if (T != NULL) { visit(T->data); preOrder(T->LChild); preOrder(T->RChild); }}
void inOrder(BTNode *T) { if (T != NULL) { preOrder(T->LChild); visit(T->data); preOrder(T->RChild); }}
void preOrder(BTNode *T) { if (T != NULL) { preOrder(T->LChild); preOrder(T->RChild); visit(T->data); }}
递归算法：
左根右
中序(根)遍历：
左右根
后序(根)遍历：
由L D R，分别表示遍历左子树、访问根结点、遍历右子树，则可得到三种递归的遍历方法：
遍历种类：
以上三种遍历方法中，递归遍历左右子树的顺序都是固定的，只是访问根结点的顺序不同，所以“序”指根结点的访问顺序。
因为每个结点仅访问一次，故时间复杂度都是O(n)。
递归算法和非递归算法的转换【借助栈】
定义：是指从第一层( 即根 )开始，按从上到下，每层从左到右的顺序对结点逐个进行访问。
特点：因上下层结点之间具有父子关系，所以在层序遍历中必然是先访问的结点其孩子也先访问。
遍历过程：设置一个队列（初始化为空）来保存待访问的结点( 已访问结点的孩子 )，首先将二叉树的根结点A入队，然后出队，visit访问出队结点（此时可对结点加操作），根A出完后，将其所有孩子入队BC；队头B出队，访问B，将B的所有孩子入队；C出队，访问C，将C的所有孩子入队。
层序遍历：
由二叉树的 先序遍历 和 中序遍历 可以唯一地确定一棵二叉树。
由二叉树的 后序遍历 和 中序遍历 可以唯一地确定一棵二叉树。
由二叉树的 层序遍历 和 中序遍历 也可以唯一地确定一棵二叉树。
由遍历序列反过来构造二叉树：
二叉树的遍历：
设n个结点，共有2n个指针，用了n-1个，除根结点，2n-(n-1) = n+1 个空指针。
每个叶结点有2个指针，每个度为1的结点有一个指针，所以空指针= 2n0 + n1 ，又因为n0=n2+1，所以指针个数为：n0+n1+n2+1 = n+1。
空指针的计算：
先来对比传统二叉树与线索二叉树：遍历二叉树后存储至传统二叉链表，其仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。
定义：利用空链域存放指向结点的直接前驱或后继的指针。这种附加的指针称为“线索”，加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
ltag = 0 lchild域指示结点的左孩子ltag = 1 lchild域指示结点的直接前驱
rtag = 0 rchild域指示结点的右孩子rtag = 1 rchild域指示结点的直接后继
标志域说明：
规定：若某一结点无左子树，则令lchild指向其前驱结点，若无右子树，则令rchild指向其后继结点；再增加两个标志域标识指针域，用以指向左右孩子或前驱后继。
作用：引入线索二叉树，就是为了加快查找结点前驱和后继的速度。这样就可以像遍历单链表那样方便地遍历二叉树。
对二叉树以某种次序遍历 使其变为 线索二叉树 的过程称为 线索化。
线索二叉树：
所以线索化的过程就是在遍历的过程中修改中空指针的过程。可用递归算法。
线索二叉树构造的实质 是将二叉链表中的 空指针 改为 指向前驱或后继的 线索。
线索化的实质就是遍历一次二叉树。
对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树，包括先序、中序和后序。
设指针p指向当前访问的结点，指针pre指向刚才访问过的结点，由此记录下遍历过程中访问结点的先后关系。
建立font color=\"#569230\
例：以结点p为根的子树的 font color=\"#569230\
构造线索二叉树：
二叉树
树与二叉树
在二叉排序树中，如果先删除分支结点后再插入它，则会导致二叉排序树的重构，其结果与之前不再相同。
题型：
⌊log₂ n⌋
收藏
职业：暂无
0 条评论
回复 删除
下一页
