数据结构期末复习
脉络与算法
基本术语：
抽象数据类型- ADT
按 逻辑结构 分为 ： 集合（结点之间没有联系的）、线性结构（结点之间存在一对一关系的）、树形结构（结点之前存在一对多关系的）、图形结构（结点之间存在多对多的关系的）
按 存储结构（物理结构） 分为：顺序储存结构（一段连续的储存单元）、链式储存结构（存储位置由编译器随机分配，结点间需要用指针联系起来）、索引储存结构（拥有索引表，其中包含着结点的关键码以及储存位置）、散列储存结构（储存位置由散列函数决定）
算法分析
时间复杂度 ：算法的时间复杂度是一个函数，它定性描述该算法的运行时间。时间复杂度常用大O符号表述，例如
、
、
、
等；其中n用来表示输入的长度，该值可以影响算法的空间复杂度。不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。
空间复杂度 ：算法空间复杂度是一个函数，定性地描述该算法运行所需要的存储空间。它表示一个算法完全执行所需要的存储空间大小。和时间复杂度类似，空间复杂度通常也使用大O记号来渐进地表示，就像时间复杂度的计算不考虑算法所使用的空间大小一样，空间复杂度也不考虑算法运行需要的时间长短。
时间复杂度的计算O()：
看算法中那一条语句的执行次数最多的语句（一般是循环最里面的那句），如果这句语句执行的次数是n次，那么该算法的时间复杂度就是。
常见的时间复杂度量级有：
- 常数阶O(1)
- 对数阶O(logN)
- 线性阶O(n)
- 线性对数阶O(nlogN)
- 平方阶O(n²)
- 立方阶O(n³)
- K次方阶O(n^k)
- 指数阶(2^n)
不会算的话可以看看这个网站：https://zhuanlan.zhihu.com/p/50479555
线性表
什么时候使用线性表？
具有“一对一”逻辑关系的数据，最佳的存储方式是使用线性表
顺序表 VS 链表
1.定义
顺序表：用一组地址连续的储存单元依次存储线性表中的各元素，通过位置来表示数据元素之间的线性逻辑关系
链表：用一组任意地址的储存单元存储线性表中的各元素，通过指针来表示数据元素之间的线性逻辑关系
2.C语言中的实现
顺序表常常使用数组来实现。
单链表，顾名思义就是用链表来实现的，它常常使用头指针来表示。
单循环链表，顾名思义也是用链表来实现的，它常常使用尾指针来表示，因为尾指针的下一个指针就是头指针，遍历时十分方便。
数据类型定义：
顺序表：
typedef int DataType;
struct List
{
int Max;
int n;
DataType* elem;
};
typedef struct List* SeqList;
|
单链表：
typedef int DataType;
struct Node {
DataType data;
struct Node* next;
};
typedef struct Node *PNode;
typedef struct Node *LinkList;
|
顺序表的 建立、查找、遍历、插入、删除、判空：
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
struct List
{
int Max;
int n;
DataType* elem;
};
typedef struct List* SeqList;
SeqList SetNullList_Seq(int m)
{
SeqList slist = (SeqList)malloc(sizeof(struct List));
if (slist != NULL)
{
slist->elem = (DataType*)malloc(sizeof(DataType) * m);
if (slist->elem) {
slist->Max = m;
slist->n = 0;
return(slist);
}
else free(slist);
}
printf("out of space!!\n");
return NULL;
}
int IsNullList_seq(SeqList slist)
{
return(slist->n == 0);
}
int InsertPre_seq(SeqList slist, int p, DataType x)
{
int q;
if (slist->n >= slist->Max) {
printf("overflow");
return(0);
}
if (p<0 || p>slist->n) {
printf("not exist!\n");
return(0);
}
for (q = slist->n - 1; q >= p; q--)
slist->elem[q + 1] = slist->elem[q];
slist->elem[p] = x;
slist->n = slist->n + 1;
return(1);
}
void print(SeqList slist)
{
int i;
for (i = 0; i < slist->n; i++)
printf("%d ", slist->elem[i]);
}
int DelIndex_seq(SeqList slist, int p)
{
int q;
if (p < 0 || p >= slist->n) {
printf("Not exist\n");
return 0;
}
for (q = p; q < slist->n - 1; q++) {
slist->elem[q] = slist->elem[q + 1];
}
slist->n = slist->n - 1;
return 1;
}
|
单链表的 建立、查找、遍历、插入、删除、判空：
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
struct Node {
DataType data;
struct Node* next;
};
typedef struct Node *PNode;
typedef struct Node *LinkList;
LinkList SetNullList_Link()
{
LinkList head = (LinkList)malloc(sizeof(struct Node));
if (head != NULL) head->next = NULL;
else printf("alloc failure");
return head;
}
int IsNull_Link(LinkList llist)
{
return(llist->next == NULL);
}
void CreateList(struct Node *head)
{
PNode p = NULL; int data;
scanf("%d", &data);
while (data != -1) {
p = (struct Node*)malloc(sizeof(struct Node));
p->data = data;
p->next = head->next;
head->next = p;
scanf("%d", &data);
}
}
void print(LinkList head)
{
PNode p = head->next;
while (p) {
printf("%d ", p->data);
p = p->next;
}
}
void DestoryList_Link(LinkList head)
{
PNode pre = head; PNode p = pre->next;
while (p) {
free(pre);
pre = p;
p = pre->next;
}
free(pre);
}
int InsertPost_link(LinkList llist, DataType x, DataType y)
{
PNode p = llist;
while(p->next){
p = p->next;
if(p->data == x){
PNode insert = (struct Node*)malloc(sizeof(struct Node));
insert->data = y;
insert->next = p->next;
p->next = insert;
break;
}
}
if(p->next==NULL)printf("not exist data %d\n",x);
}
void DelNode_Link(LinkList head, DataType deldata)
{
PNode p = head;
while(p->next){
PNode temp = p->next;
if(temp->data == deldata){
p->next = temp->next;
temp->next = NULL;
free(temp);
break;
}else p = p->next;
}
if(p->next==NULL)printf("not exist %d\n",deldata);
}
|
单循环链表的 建立、遍历、删除：
PNode buildCircularLinkedList(int n, PNode tail)
{
PNode current=NULL, prev;
prev = tail;
for (int i = 0; i < n; i++)
{
current = (PNode)malloc(sizeof(Node));
current->next = NULL;
scanf("%d", ¤t->data);
prev->next = current;
prev = current;
}
current->next = tail->next;
tail->next = current;
return tail;
}
void DestoryList_Link(LinkList tail)
{
PNode pre = tail->next;
PNode p = pre->next;
while (p != tail)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre);
free(tail);
}
void printCircularLinkedList(PNode tail)
{
PNode current, last;
last = tail->next;
current = last->next;
do
{
printf("%d ", current->data);
current = current->next;
} while (current != last->next);
}
|
另一种 建立：
LinkList CreateList_Tail_loop()
{
LinkList head = (LinkList)malloc(sizeof(struct Node));
PNode cur = NULL;
PNode tail = head;
DataType data;
scanf("%d", &data);
while (data != -1)
{
cur = (struct Node*)malloc(sizeof(struct Node));
cur->data = data;
tail->next = cur;
tail = cur;
scanf("%d", &data);
}
tail->next = head;
return tail;
}
|
栈和队列
栈和队列的定义
栈：
栈（stack）是限定在表尾进行插入和删除的操作的线性表。
我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不包含任何数据元素的栈称为空栈。栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构。
栈的插入操作，叫做进栈，也称压栈、入栈。
队列：
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
什么时候使用栈，什么时候使用队列？
这两种数据结构经常作为我们解决实际问题的工具来进行使用，想让数据以后进先出的方式保存的使用栈，想让数据以先进先出的方式保存的使用队列。
递归在系统底层的本质就是使用了栈这种数据结构，程序中如果使用了递归，那么它在编程时可以被改写成用栈来实现，但是无法用队列来实现。
C语言中的实现
栈
顺序栈的 建立、入栈、出栈、弹栈顶、判空：
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
struct SeqStackNode
{
int MAX;
int top;
DataType *elem;
};
typedef struct SeqStackNode *SeqStack;
SeqStack SetNullStack_Seq(int m)
{
SeqStack sstack = (SeqStack)malloc(sizeof(struct SeqStackNode));
if (sstack != NULL) {
sstack->elem = (int*)malloc(sizeof(int)*m);
if (sstack->elem != NULL) {
sstack->MAX = m;
sstack->top = -1;
return(sstack);
}
else {
free(sstack);
return NULL;
}
}
else {
printf("out of space");
return NULL;
}
}
int IsNullStack_seq(SeqStack sstack)
{
return(sstack->top == -1);
}
void Push_seq(SeqStack sstack, int x)
{
if(sstack->top + 1 == sstack->MAX){
printf("overflow!\n");
}
else
{
sstack->elem[++ sstack->top] = x;
}
}
void Pop_seq(SeqStack sstack)
{
if (IsNullStack_seq(sstack))
printf("Underflow!\n");
else
sstack->top = sstack->top - 1;
}
DataType Top_seq(SeqStack sstack)
{
if (IsNullStack_seq(sstack))
{
printf("it is empty");
return 0;
}
else
return sstack->elem[sstack->top];
}
|
链栈的 建立、入栈、出栈、弹栈顶、判空：
#include <stdio.h>
#include <stdlib.h>
typedef int Datatype;
struct Node{
Datatype data;
struct Node* next;
};
typedef struct Node* PNode;
typedef struct Node* LinkStack;
LinkStack SetNullStack_Link()
{
LinkStack top = (LinkStack)malloc(sizeof(struct Node));
if(top)
top->next = NULL;
else
printf("Alloc failure");
return top;
}
int IsNULLStack_Link(LinkStack top)
{
if(top->next == NULL)
return 1;
else
return 0;
}
void Push_Link(LinkStack top,Datatype x)
{
PNode p;
p = (PNode)malloc(sizeof(struct Node));
if(p == NULL)
printf("Alloc failure");
else
{
p->data = x;
p->next = top->next;
top->next = p;
}
}
void Pop_Link(LinkStack top)
{
PNode p;
if(IsNULLStack_Link(top))
printf("it is empty stack!");
else
{
p = top->next;
top->next = p->next;
free(p);
}
}
Datatype Top_Link(LinkStack top)
{
if(IsNULLStack_Link(top))
printf("it is empty stack!");
else
return top->next->data;
}
|
队列
循环队列（顺序队列）的 建立、入队、出队、取队头、判空：
#include <stdio.h>
#include <stdlib.h>
typedef char DataType;
struct Queue
{
int Max;
int f;
int r;
DataType *elem;
};
typedef struct Queue *SeqQueue;
SeqQueue SetNullQueue_seq(int m)
{
SeqQueue squeue;
squeue = (SeqQueue)malloc(sizeof(struct Queue));
if (squeue == NULL)
{
printf("Alloc failure\n");
return NULL;
}
squeue->elem = (char*)malloc(sizeof(DataType) * m);
if (squeue->elem != NULL)
{
squeue->Max = m;
squeue->f = 0;
squeue->r = 0;
return squeue;
}
}
int IsNullQueue_seq(SeqQueue squeue)
{
return (squeue->f == squeue->r);
}
void EnQueue_seq(SeqQueue squeue, DataType x)
{
if ((squeue->r + 1) % squeue->Max == squeue->f)
{
printf("It is FULL Queue!");
}
else
{
squeue->elem[squeue->r] = x;
squeue->r = (squeue->r + 1) % (squeue->Max);
}
}
void DeQueue_seq(SeqQueue squeue)
{
if (IsNullQueue_seq(squeue))
{
printf("It is empty queue!");
}
else
{
squeue->f = (squeue->f + 1) % squeue->Max;
}
}
DataType FrontQueue_seq(SeqQueue squeue)
{
if (IsNullQueue_seq(squeue))
{
printf("It is empty queue!");
return 0;
}
else
{
return squeue->elem[squeue->f];
}
}
|
链队列的 建立、入队、出队、取队头、判空：
#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
struct Node {
DataType data;
struct Node* next;
};
typedef struct Node *PNode;
struct Queue
{
PNode f;
PNode r;
};
typedef struct Queue *LinkQueue;
LinkQueue SetNullQueue_Link()
{
LinkQueue lqueue;
lqueue = (LinkQueue)malloc(sizeof(struct Queue));
if (lqueue != NULL)
{
lqueue->f = NULL;
lqueue->r = NULL;
}
else
printf("Alloc failure! \n");
return lqueue;
}
int IsNullQueue_link(LinkQueue lqueue)
{
return (lqueue->f == NULL);
}
void EnQueue_link(LinkQueue lqueue, DataType x)
{
PNode p;
p = (PNode)malloc(sizeof(struct Node));
if (p == NULL)
printf("Alloc failure!");
else {
p->data = x;
p->next = NULL;
if (lqueue->f == NULL)
{
lqueue->f = p;
lqueue->r = p;
}
else
{
lqueue->r->next = p;
lqueue->r = p;
}
}
}
void DeQueue_link(LinkQueue lqueue)
{
struct Node * p;
if (lqueue->f == NULL)
printf("It is empty queue!\n ");
else
{
p = lqueue->f;
lqueue->f = lqueue->f->next;
free(p);
}
}
DataType FrontQueue_link(LinkQueue lqueue)
{
if (lqueue->f == NULL)
{
printf("It is empty queue!\n");
return 0;
}
else
return (lqueue->f->data);
}
|
树和二叉树
树的定义和术语
定义：
树 是一种用来模拟具有树状结构性质的数据集合的数据结构，它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 每个节点都只有有限个子节点或无子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
- 树里面没有环路(cycle)
术语：
- 节点的度：一个节点含有的子树的个数称为该节点的度；
- 树的度：一棵树中，最大的节点度称为树的度；
- 叶子节点或终端节点：度为零的节点；
- 非终端节点或分支节点：度不为零的节点；
- 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 深度：对于任意节点n,n的深度为从根到n的唯一路径长，根的深度为0；
- 高度：对于任意节点n,n的高度为从n到一片树叶的最长路径长，所有树叶的高度为0；
- 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
- 森林：由m（m>=0）棵互不相交的树的集合称为森林；
树的表示方法
树有三种表示方法，分别是 长子-右兄弟表示法、树的双亲表示法、树的子表表法。
这里只介绍考试要考的 长子-右兄弟表示法。
长子-右兄弟表示法
这种表示方法设置了两个指针，分别指向结点的长子（最左孩子）结点和结点的右兄弟结点。
这种表示树的方法其实是二叉树表示，所以这种方法也用于将树转换为二叉树
什么时候使用树这种数据结构？
抽象地说，基本上有序列的地方就可以应用树，因为树结构即是一种序列索引结构，由此引申出很多的排序树，如二叉搜索树、平衡二叉树等等。
并且由于树具有分层和继承的特性，当需要分层，继承的场景下均可以考虑用树结构来实现，例如操作系统的文件管理系统。
二叉树
二叉树是最简单的树，同时也是考试的重点，下面让我们来研究一下二叉树。
定义：
二叉树是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。在二叉树中严格区分左右，不能随意颠倒。
特殊的二叉树：
1、满二叉树：对于一棵二叉树，如果每一个非叶子节点都存在左右子树，并且二叉树中所有的叶子节点都在同一层中，这样的二叉树称为满二叉树。
2、完全二叉树：如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。
3、扩充二叉树：将二叉树中的所有结点都扩充到具有两个子结点。
4、线索二叉树：
一个二叉树通过如下的方法 “穿起来”：所有原本为空的右(孩子)指针改为指向该节点在中序序列中的后继，所有原本为空的左(孩子)指针改为指向该节点的中序序列的前驱。
线索二叉树能线性地遍历二叉树，从而比递归的中序遍历更快。使用线索二叉树也能够方便的找到一个节点的父节点，这比显式地使用父亲节点指针或者栈效率更高。
二叉树的储存方式
1.顺序储存（仅适用于完全二叉树）
用数组存储完全二叉树的各节点，通过数组下标来确定节点之间的关系。
本质是任何二叉树都可以通过扩充二叉树的方法变为完全二叉树来使用顺序储存，但是这样的做的空间利用率很低，所以并不适用。
优点：不用通过指针来联系父节点和子结点，节省大量指针的空间。
缺点：不适应于所有二叉树、需要提前开辟空间，可能导致空间的浪费、插入和删除节点需要大量的移动节点。
2.链式储存（适用于所有二叉树）
用链表来储存二叉树的结点，通过链表的指针域找到每个节点的子节点。
优点：可以适用于所有类型的二叉树，并且不会造成空间的浪费，插入删除节点方便。
缺点：使用了大量指针，较顺序存储空间开销更大。
二叉树在C语言中的实现（链式储存）
1.二叉树类型定义：
typedef char Datatype;
typedef struct BTreeNode //二叉树的结点
{
Datatype data;
struct BTreeNode *leftchild;
struct BTreeNode *rightchild;
}BinTreeNode;
typedef BinTreeNode *BinTree;
|
2.创建二叉树：
递归创建二叉树：
BinTree CreateBinTree_Recursion()
{
char ch;
BinTree bt;
scanf("%c", &ch);
if(ch == '@')
bt = NULL;
else
{
bt = (BinTreeNode *)malloc(sizeof(BinTreeNode));
bt->data = ch;
bt->leftchild = CreateBinTree_Recursion();
bt->rightchild = CreateBinTree_Recursion();
}
return bt;
}
|
非递归创建二叉树（了解即可）：
利用栈：
void PreOrder_NRecursion(BinTree bt)
{
BinTree p;
LinkStack stack = SetNullStack_Link();
if(bt == NULL) return;
p = NULL;
Push_Link(stack, bt);
while (!IsNULLStack_Link(stack))
{
p = Top_Link(stack);
Pop_Link(stack);
printf("%c",p->data);
if(p->rightchild != NULL)
Push_Link(stack, p->rightchild);
if(p->leftchild != NULL)
Push_Link(stack, p->leftchild);
}
}
void InOrder_NRecursion(BinTree bt)
{
BinTree p;
LinkStack stack = SetNullStack_Link();
if(bt == NULL) return;
Push_Link(stack, bt);
p = bt;
p = p->leftchild;
while (p || !IsNULLStack_Link(stack))
{
while(p != NULL)
{
Push_Link(stack, p);
p = p->leftchild;
}
p = Top_Link(stack);
Pop_Link(stack);
printf("%c",p->data);
p = p->rightchild;
}
}
void PostOrder_NRecursion(BinTree bt)
{
BinTree p;
LinkStack stack = SetNullStack_Link();
if(bt == NULL) return;
p = bt;
while (p || !IsNULLStack_Link(stack))
{
while(p != NULL)
{
Push_Link(stack, p);
p = p->leftchild ? p->leftchild : p->rightchild;
}
p = Top_Link(stack);
Pop_Link(stack);
printf("%c",p->data);
if(!IsNULLStack_Link(stack) && (Top_Link(stack)->leftchild == p))
p = (Top_Link(stack))->rightchild;
else
p = NULL;
}
}
|
利用队列：
BinTree CreateBinTree_NRecursion()
{
LinkQueue queue = SetNullQueue_Link();
BinTreeNode *s, *p, *bt;
char ch;
int count = -1;
ch = getchar();
bt = NULL;
while(ch != '#')
{
s = NULL;
if(ch != '@')
{
s = (BinTreeNode *)malloc(sizeof(BinTreeNode));
s->data = ch;
s->leftchild = s->rightchild = NULL;
}
EnQueue_link(queue,s);
count++;
if(count == 0)
bt = s;
else
{
p = FrontQueue_link(queue);
if(s != NULL && p != NULL)
{
if(count % 2 == 1)
p->leftchild = s;
else
p->rightchild = s;
}
if(count % 2 == 0)
DeQueue_link(queue);
}
ch = getchar();
}
return bt;
}
|
3.二叉树的遍历：
递归遍历：
void PreOrder_Recursion(BinTree bt)
{
if(bt == NULL) return;
visit(bt);
PreOrder_Recursion(bt->leftchild);
PreOrder_Recursion(bt->rightchild);
}
void InOrder_Recursion(BinTree bt)
{
if(bt == NULL) return;
InOrder_Recursion(bt->leftchild);
visit(bt);
InOrder_Recursion(bt->rightchild);
}
void PostOrder_Recursion(BinTree bt)
{
if(bt == NULL) return;
PostOrder_Recursion(bt->leftchild);
PostOrder_Recursion(bt->rightchild);
visit(bt);
}
|
交叉遍历：
void PreOrder_Cross(BinTree bt)
{
if(bt == NULL) return;
visit(bt);
InOrder__Cross(bt->leftchild);
InOrder__Cross(bt->rightchild);
}
void InOrder__Cross(BinTree bt)
{
if(bt == NULL) return;
PreOrder__Cross(bt->leftchild);
visit(bt);
PreOrder__Cross(bt->rightchild);
}
void main()
{
bt = CreateBintree();
PreOrder__Cross(bt);
}
|
遍历过程演示：
非递归遍历：
利用栈：
void PreOrder_NRecursion(BinTree bt)
{
BinTree p;
LinkStack stack = SetNullStack_Link();
if(bt == NULL) return;
p = NULL;
Push_Link(stack, bt);
while (!IsNULLStack_Link(stack))
{
p = Top_Link(stack);
Pop_Link(stack);
printf("%c",p->data);
if(p->rightchild != NULL)
Push_Link(stack, p->rightchild);
if(p->leftchild != NULL)
Push_Link(stack, p->leftchild);
}
}
void InOrder_NRecursion(BinTree bt)
{
BinTree p;
LinkStack stack = SetNullStack_Link();
if(bt == NULL) return;
Push_Link(stack, bt);
p = bt;
p = p->leftchild;
while (p || !IsNULLStack_Link(stack))
{
while(p != NULL)
{
Push_Link(stack, p);
p = p->leftchild;
}
p = Top_Link(stack);
Pop_Link(stack);
printf("%c",p->data);
p = p->rightchild;
}
}
void PostOrder_NRecursion(BinTree bt)
{
BinTree p;
LinkStack stack = SetNullStack_Link();
if(bt == NULL) return;
p = bt;
while (p || !IsNULLStack_Link(stack))
{
while(p != NULL)
{
Push_Link(stack, p);
p = p->leftchild ? p->leftchild : p->rightchild;
}
p = Top_Link(stack);
Pop_Link(stack);
printf("%c",p->data);
if(!IsNULLStack_Link(stack) && (Top_Link(stack)->leftchild == p))
p = (Top_Link(stack))->rightchild;
else
p = NULL;
}
}
|
利用栈的非递归中序遍历演示：
利用队列（层次遍历）：
void LevelOrder(BinTree bt)
{
BinTree p;
LinkQueue queue = SetNullQueue_Link();
if(bt == NULL) return;
p = NULL;
EnQueue_link(queue, bt);
while (!IsNullQueue_Link(queue))
{
p = FrontQueue_link(queue);
DeQueue_link(queue);
printf("%c ",p->data);
if(p->leftchild != NULL)
EnQueue_link(queue, p->leftchild);
if(p->rightchild != NULL)
EnQueue_link(queue, p->rightchild);
}
}
|
二叉树的恢复
已知一颗二叉树的中序序列以及先序和后序序列中的其中之一，可以还原出这颗二叉树的过程
方法：
先通过先序或后序序列确定根，再通过中序序列确定其左右子树上的结点
树、森林与二叉树的转换
1.树与二叉树的转换
树 -> 二叉树
将一颗树转换为二叉树按照以下三个步骤进行：
（1）加线：树中的所有兄弟之间的连线；
（2）去线：对于树中的每个结点、只保留其与第一个孩子结点的连线，去掉与其他孩子的连线；
（3）调整：以树根为轴心，按照顺时针将树旋转成一定的角度（例如45°），使之看起来结构层次分明、美观。
二叉树 -> 树
将一颗树转换为二叉树按照以下三个步骤进行：
（1）加线：对于二叉树中的每个左孩子结点，将其父节点和其（该左孩子结点）右孩子结点、其（该左孩子结点）右孩子的右孩子结点等等（该左孩子结点一直往右下去）进行连线；
（2）去线：去除树中的每个结点与其右孩子的连线；
（3）调整：调整得到的树，使之看起来结构层次分明、美观。
2.森林与二叉树的转换
森林 -> 二叉树
将森林的每一颗树按照上面 树 -> 二叉树 的方法转换成二叉树。
二叉树 ->森林
与 二叉树 -> 树 的方法是完全一样的，只是因为有右子树的二叉树的转化通过这个方法会变成两颗树即森林。
哈夫曼树
定义
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
树的带权路径长度-WPL
树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1L1+W2L2+W3L3+…+WnLn），N个权值Wi（i=1,2,…n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,…n）。可以证明哈夫曼树的WPL是最小的。
哈夫曼算法
哈夫曼给出了构造最优二叉树（WPL最小树）的方法，具体思路如下：
（1）给定 n 个外部结点权值，构造n棵不同的二叉树，设T是这n棵二叉树的集合。
（2）在T中选取两棵根结点权值最小的和次小的二叉树，作为左子树和右子树（如无特殊说明严格区分左右），构造一棵新的二叉树，新的二叉树的根结点权值等于左、右子树根结点的权值之和。
（3）从T中删除这两棵二叉树，并将新生成的二叉树加入到T中。
（4）重复（2）、（3），直到T中只有一棵二叉树为止，这棵二叉树就是哈夫曼树。
哈夫曼算法的c语言实现
typedef char Datatype;
struct HuffNode
{
Datatype data;
int weight;
int parent;
int leftchild;
int rightchild;
};
typedef struct HuffNode* HtNode;
typedef struct HuffTreeNode
{
int n;
int root;
HtNode ht;
}*HuffTree;
HuffTree CreateHuffTree(int n,int w[],char data[])
{
HuffTree pht;
int i = 0, j = 0;
int x1, x2, min1, min2;
pht = (HuffTree)malloc(sizeof(struct HuffTreeNode));
if (pht == NULL)
{
printf("pht malloc Out of space!\n");
return pht;
}
pht->ht = (HtNode)malloc(sizeof(struct HuffNode) * (2 * n - 1));
if (pht->ht == NULL)
{
printf("ht malloc Out of space!\n");
return pht;
}
for (i = 0; i < 2 * n - 1; i++)
{
pht->ht[i].leftchild = -1;
pht->ht[i].rightchild = -1;
pht->ht[i].parent = -1;
if (i < n)
{
pht->ht[i].weight = w[i];
pht->ht[i].data = data[i];
}
else
{
pht->ht[i].weight = -1;
}
}
for (i = 0; i < n - 1; i++)
{
min1 = M;
min2 = M;
x1 = -1;
x2 = -1;
for (j = 0; j < n + i; j++)
{
if (pht->ht[j].weight < min1 && pht->ht[j].parent == -1 )
{
min2 = min1;
x2 = x1;
min1 = pht->ht[j].weight;
x1 = j;
}
else if (pht->ht[j].weight < min2 && pht->ht[j].parent == -1 )
{
min2 = pht->ht[j].weight;
x2 = j;
}
}
pht->ht[n + i].weight = min1 + min2;
pht->ht[n + i].leftchild = x1;
pht->ht[n + i].rightchild = x2;
pht->ht[x1].parent = n + i;
pht->ht[x2].parent = n + i;
}
pht->root = 2 * n - 2;
pht->n = n;
return pht;
}
void PrintHuffCode(int n,HuffTree pht)
{
int i = 0, num = 0, j = 0;
int parent = 0;
int times = 0;
int code[Maxn];
for (i = 0; i < n; i++)
{
num = i;
j = 0;
times = 0;
while (pht->ht[num].parent != -1)
{
parent = pht->ht[num].parent;
if (pht->ht[parent].leftchild == num)
{
code[j] = 0;
j++;
times++;
}
else if (pht->ht[parent].rightchild == num)
{
code[j] = 1;
j++;
times++;
}
num = parent;
}
printf("%c:", pht->ht[i].data);
for (j = times-1; j >= 0; j--)
{
printf("%d", code[j]);
}
printf("\n");
}
return;
}
|
哈夫曼编码
利用每个字符出现的频率作为权值，生成哈夫曼树，将生成的哈夫曼树的每个 结点到的其左孩子的边 标记为二进制 ‘0’，每个结点到的其右孩子的边 标记为二进制 ‘1’，将根结点到每个外部结点的路径上所有的二进制数连起来，就构成了该外部结点的最优前缀编码，通常把这种编码称为 哈夫曼编码
例子：
搜索树
二分查找判定树
概念：
二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。
生成过程：
- 在长度为10的有序表中进行折半查找，
先和中间记录进行比较，而中间记录的序号为(1+10)/2=5，
即判定树的根结点是5，如图7-2(a)所示；
- 考虑判定树的左子树，即 将查找区间调整到左半区，此时的查找区间是[1，4]，也就是，左分支上根结点的值减1，代表查找区间的上限high，此时，根结点的左孩子是(1+4)/2=2，如图7-2(b)所示；
- 考虑判定树的右子树，即 将查找区间调整到右半区，此时的查找区间是[6，10]，也就是，右分支上根结点的值加1，代表查找区间的下限low，此时，根结点的右孩子是(6+10)/2=8，如图7-2(c)所示；
- 重复⑵⑶步，依次确定每个结点的左右孩子，不断缩小，如图7-2(d)所示。
二叉排序树（二叉搜索树）
定义：
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
生成过程：
（1）将一个一组关键码的第一项拿出来作为根结点；
（2）从剩余的关键码取出一个关键码，利用逐个结点比较的方法，将该关键码放到树中的合适位置（满 足二叉树树定义）；
（3）重复（2），直到关键码全部取完，生成的二叉树就称为二叉排序树（二叉搜索树）。
查找方法：
1.指定一个需要查找的值x，在二叉搜索树b中查找；
2.若二叉搜索树b是空树，则查找失败，否则：
3.若x等于b的根节点的数据域之值，则查找成功；否则：
4.若x小于b的根节点的数据域之值，则搜索左子树；否则：
5.查找右子树；
6.重复3-5步骤，直到查找成功，或查找失败。
ASLcg（成功） 的计算方法：
在等概率情况下查找成功时的平均查找长度
Pi为成功查找到k的概率，level(Ki)为k对应内部结点的层次
例子：
给11个数据元素有序表（2,3,10,15,20,25,28,29,30,35,40）采用折半查找。则ASL成功=？
图
图的概念与特性
概念：
图的数据结构包含一个有限（可能是可变的）的集合作为节点集合，以及一个无序对（对应无向图）或有序对（对应有向图）的集合作为边（有向图中也称作弧）的集合。节点可以是图结构的一部分，也可以是用整数下标或引用表示的外部实体。图的数据结构还可能包含和每条边相关联的数值（edge value），例如一个标号或一个数值（即权重，weight；表示花费、容量、长度等）。
特性：
1.有向图、无向图： 无向图是表示边的两个顶点之间没有次序，方向的关系，有向图是表示边的两个顶点 之间具有次序，方向的关系。
2.度：在无向图中，两个顶点Vi，Vj之间存在一条边，则称这条边为度，并且称Vi，Vj相邻；
在有向图中，存在一条顶点Vi到顶点Vj边，则称这条边为 顶点Vi的 出度，顶点Vj的 入度，并且称 Vi邻接到Vj，或Vj邻接于Vi。
3.连通图：无向图中，两个顶点之间存在一条 路径 ，则称这两个顶点是连通的，如果一个无向图中所有顶 点都是连通的，则称这这个图是 连通图。
4.带权图：图的每条边是被赋予一个权值，权值可以表示通过这条边所要付出的代价。
5.生成树：一个无向图 G 的生成树是具有 G 的全部顶点，但边数最少的连通子图。一个带权图的所有生成树中，总权重最小的称为最小生成树。
6.完全图：具有最多边数的图称为完全图，即任意两个顶点之间都存在有边，特别的，对于有向图每个顶点都具有两条边。
图的C语言实现
图的储存
1.邻接矩阵：
typedef struct GraphMatrix_STRU
{
int size;
int **graph;
}GraphMatrix;
GraphMatrix * InitGraph(int num)
{
int i,j;
GraphMatrix * graphMatrix = ( GraphMatrix *)malloc(sizeof(GraphMatrix));
graphMatrix->size = num;
graphMatrix->graph = (int **)malloc(sizeof(int *) * graphMatrix->size);
for(i = 0;i < graphMatrix->size;i++)
graphMatrix->graph[i] = (int *)malloc(sizeof(int) * graphMatrix->size);
for(i = 0;i < graphMatrix->size;i++)
{
for(j = 0;j < graphMatrix->size;j++)
graphMatrix->graph[i][j] = MAX;
}
return graphMatrix;
}
void ReadGraph_Matrix(GraphMatrix * graphMatrix)
{
int vex1, vex2, weight,max = 0;
scanf("%d %d %d",&vex1, &vex2, &weight);
while(weight != 0)
{
if(vex1 > vex2)
{
if(max < vex1)
{
max = vex1;
}
}
else
{
if(max < vex2)
{
max = vex2;
}
}
graphMatrix->graph[vex1][vex2] = weight;
scanf("%d %d %d",&vex1, &vex2, &weight);
}
}
|
2.邻接表：
typedef struct GRAPHLISTNODE_STRU
{
int nodeno;
struct GRAPHLISTNODE_STRU* next;
}GraphListNode;
typedef struct GRAPHLIST_STRU
{
int size;
GraphListNode* graphListArray;
}GraphList;
GraphList* InitGraph(int num)
{
int i;
GraphList *graphList = (GraphList *)malloc(sizeof(GraphList));
graphList->size = num;
graphList->graphListArray = (GraphListNode*)malloc(sizeof(GraphListNode)*num);
for (i = 0; i<num; i++)
{
graphList->graphListArray[i].next = NULL;
graphList->graphListArray[i].nodeno = i;
}
return graphList;
}
void ReadGraph(GraphList* graphList)
{
int vex1, vex2;
GraphListNode *tempNode = NULL;
scanf("%d %d", &vex1, &vex2);
while (vex1 >= 0 && vex2 >= 0)
{
tempNode = (GraphListNode*)malloc(sizeof(GraphListNode));
tempNode->nodeno = vex2;
tempNode->next = graphList->graphListArray[vex1].next;
graphList->graphListArray[vex1].next = tempNode;
scanf("%d %d", &vex1, &vex2);
}
}
|
图的遍历：
深度优先搜索-DFS:
void DFS(GraphList* graphList, int * visited, int i)
{
int j;
GraphListNode *tempNode = NULL;
visited[i] = 1;
printf("%d ", i);
tempNode = graphList->graphListArray[i].next;
while (tempNode != NULL)
{
if (!visited[tempNode->nodeno])
DFS(graphList,visited,tempNode->nodeno);
tempNode = tempNode->next;
}
}
void DFSGraphList(GraphList* graphList)
{
int i;
int *visited = (int*)malloc(sizeof(int)* graphList->size);
for (i = 0; i < graphList->size; i++)
visited[i] = 0;
for (i = 0; i < graphList->size; i++)
if (!visited[i])
DFS(graphList, visited, i);
}
|
广度优先搜索-BFS：
void BFSMatrixGraph(GraphMatrix G, int u)
{
queue Queue;
initQueue(Queue);
visited[u] = true;
enQueue(Queue, u);
while(!emptyQueue(Queue)){
u = getQueueTopElem(Queue);
printf("%d ", u);
int e = -1;
deQueue(Queue, e);
for (int i = 0; i < G.vNum; i++) {
if (!visited[i] && G.vNode[u][i] < INF) {
visited[i] = true;
enQueue(Queue,i);
}
}
}
}
|
求最小生成树的方法
1.PRIM算法
实现过程：
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V：
a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
动画演示：
代码：
void Prim(GraphMatrix *graphMatrix, int source)
{
int i,j;
int * component = (int *)malloc(sizeof(int) * graphMatrix->size);
int * distance = (int *)malloc(sizeof(int) * graphMatrix->size);
int * neighbor = (int *)malloc(sizeof(int) * graphMatrix->size);
for(j = 0;j < graphMatrix->size;j++)
{
component[j] = 0;
distance[j] = graphMatrix->graph[source][j];
neighbor[j] = source;
}
component[source] = 1;
for (i = 1; i < graphMatrix->size; i++)
{
int v;
int min = MAX;
for(j = 0;j < graphMatrix->size;j++)
{
if(!component[j] && (distance[j] < min) )
{
v = j;
min = distance[j];
}
}
if(min < MAX)
{
component[v] = 1;
for(j = 0;j < graphMatrix->size;j++)
{
if(!component[j] && (graphMatrix->graph[v][j] < distance[j]))
{
distance[j] = graphMatrix->graph[v][j];
neighbor[j] = v;
}
}
}
else break;
}
}
|
2.KRSUSKAL算法
实现过程：
1).记Graph中有v个顶点，e个边
2).新建图Graphnew，Graphnew中拥有原图中相同的e个顶点，但没有边
3).将原图Graph中所有e个边按权值从小到大排序
4).循环：从权值最小的边开始遍历每条边 直至图Graph中所有的节点都在同一个连通分量中
if 这条边连接的两个节点于图Graphnew中不在同一个连通分量中
添加这条边到图Graphnew中
动画演示：
代码：
void Kruskal(MGraph G)
{
int i, n, m;
Edge edges[MAGEDGE];
int parent[MAXVEX];
for( i=0; i < G.numVertexes; i++ )
{
parent[i] = 0;
}
for( i=0; i < G.numEdges; i++ )
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if( n != m )
{
parent[n] = m;
printf("(%d, %d) %d ", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
|
字典
散列表
概念：
散列表（hash table），我们平时叫它哈希表或者Hash 表，你肯定经常听到它。散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。由定义我们可以知道，散列表用的是数组支持下标访问数据的特性，所以散列表是数组的一种扩展，由数组演化而来。
构造方法：
利用给出的 **散列函数h() **，将数据元素的 关键码key 代入散列函数，得到 h(key) ,该值就是该数据元素在数组中的存放位置，将所有数据元素都通过这种方法储存到数组中，最后得到这一数组就称为 散列表。
解决冲突的方法：
1.线性探查
当发生冲突时，探查序列从原来的 h(key) ,更改为 h(key) + i , i = 1,2,…,size -1 (size为数组大小)，即一个位置发生冲突，那这个数据元素就往后挨个找当前空余的空间，直到找到空余的空间存放，或发现没有空间存放退出。
2.拉链法
设置散列表中的每一个地址关联着一个链表，链表里存放着具有相同散列地址的数据元素。这种方法永远不会产生溢出线性，不过空间开销较大。
在散列表中 ASLcg（成功） 的计算方法：
在等概率情况下查找成功时的平均查找长度
$$
ASL(cg)=（比较总次数)/(元素总数)
$$
例题：
ALScg = （1 + 1 + 1 + 2 + 4 + 1 + 1 + 4 + 5）/ 9 = 19/9
排序
考试重点排序
前三个排序掌握排序过程即可，后四个排序不仅要掌握排序过程，还得掌握其算法
1.直接插入排序
2.二分法插入排序
3.shell排序
4.冒泡排序
void bubble_sort_better(int a[],int n)
{
for(int i=0; i<n-1; i++)
{
int isSorted = 1;
for(int j=0; j<n-1-i; j++)
{
if(a[j] > a[j+1])
{
isSorted = 0;
int temp = a[j];
a[j] = a[j+1];
a[j+1]=temp;
}
}
if(isSorted) break;
}
}
|
5.快速排序
int partition(int arr[], int low, int high){
int key;
key = arr[low];
while(low<high){
while(low <high && arr[high]>= key )
high--;
if(low<high)
arr[low++] = arr[high];
while( low<high && arr[low]<=key )
low++;
if(low<high)
arr[high--] = arr[low];
}
arr[low] = key;
return low;
}
void quick_sort(int arr[], int start, int end){
int pos;
if (start<end){
pos = partition(arr, start, end);
quick_sort(arr,start,pos-1);
quick_sort(arr,pos+1,end);
}
return;
}
|
6.直接选择排序
void SelectSort(SortArr * sortArr)
{
int i,j;
int minPos;
for(i = 0; i < sortArr->cnt-1; i++)
{
minPos = i;
for(j = i + 1; j < sortArr->cnt; j++)
{
if(sortArr->recordArr[j].key < sortArr->recordArr[minPos].key)
minPos = j;
}
if(minPos != i)
Swap(sortArr,minPos,i);
}
}
|
7.堆排序
void HeapSort(SortArr * sortArr,int size)
{
int i;
for(i = size/2 - 1; i >= 0; i--)
HeapAdjust(sortArr,i,size);
for(i = size - 1; i >= 1; i--)
{
Swap(sortArr,0,i);
HeapAdjust(sortArr,0,i);
}
}
|
各种排序算法的比较
