数据：是描述客观事务的数值、字符以及能输入到计算机中且被处理的各种符号集合。
数据元素：组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体考虑和处理。
数据对象：性质相同的数据元素的集合，是数据的一个子集
数据结构：是指相互之间存在一种或多种特定关系的数据元素的集合，是研究数据的逻辑结构和物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算。
数据类型：一组性质相同的值的集合以及定义在这个值集合上的一组操作的总称。
抽象数据类型（ADT）：一个数学模型以及定义在该模型上的一组操作（或者说基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作）。
ADT的定义格式
ADT<ADT名>
{
数据对象：<数据对象的定义>
结构关系：<结构关系的定义>
基本操作：<基本操作的定义>
} ADT<ADT名>
逻辑结构：是数据元素之间的逻辑关系的描述
四种基本逻辑结构:
1）集合结构 仅同属于一个集合
2）线性结构 一对一线性关系
3）树形结构 一对多层次关系
4）图形结构 多对多任意关系
存储结构：数据结构在计算机存储器中的表示
两种存储结构：顺序映像、非顺序映像
逻辑结构与存储结构关系：存储结构是逻辑关系的映象与元素本身的映象，是数据结构的实现；逻辑结构是数据结构的抽象。
算法
算法特性：
1）有穷性
2）确定性
3）可行性
4）有输入
5）有输出
算法评价标准：
1）正确性
2）可读性
3）健壮性（鲁棒性）
4）高效率与低存储量需求
算法度量：时间复杂度和空间复杂度（T(n)=O(f(n)) S(n)=O(f(n))）
算法执行时间相关因素：
1）算法所采用的“策略”
2）算法所解决问题的“规模”
3）编程所采用的“语言”
4）编译程序产生的机器代码的质量
5）执行算法的计算机的“速度”
算法执行所需存储空间因素：
1）算法程序所占的空间
2）输入的初始数据所占的存储空间
3）算法执行过程中所需要的额外空间
线性表是n(n>=0)个数据元素的有限序列，在表中，元素之间存在着线性的逻辑关系：表中有只有一个开始结点，有且仅有一个终端结构。
线性表的存储结构：
顺序存储：指在内存中用一块地址连续的存储空间按顺序存储性表的各个数据元素。采用顺序存储结构线性表称为顺序表
链式存储：通过“链”建立数据元素之间的逻辑关系。采用链式存储的线性表称为链表
顺序表实现
#define MAXSIZE 100
typedef int ElemType;
typedef struct
{
ElemType elem[MAXSIZE];
int length;
}seqList;
seqList L; //定义一个顺序表
//顺序表的初始化
void init_SeqList(SeqList *L)
{
L->length = 0;
}
//顺序表的插入
int Insert_SeqList(SeqList *L, int i, elemType x)
{
int j;
if (L->length == MAXSIZE-1)
{
printf("List overflow ")
return OVERFLOW;
}
if (i < 1 || i > L->length+1)
{
printf("location error")
return ERROR;
}
for (j=L->lenght; j>=i; j--)
{
L->elem[j+1] = L->elem[j];
}
L->elem[i] = x;
L->length++;
return TRUE;
}
/顺序表的删除
int Delete_SeqList(SeqList *L, int i)
{
int j;
if (i < 1 || i > L->length)
{
printf("non-existent No.i ")
}
for (j = i; j <= L->length -1; j++)
{
L->elem[j] = L->elem[j+1];
}
L->length--;
return TRUE;
}
//顺序表的按值查找
int Location_SeqList(SeqList *L,ElemType x)
{
int i = 1;
while (i <= L->length && L->elem[i] != x)
{
i++;
}
if (i >L->length)
{
return FALSE;
}
else
{
return L;
}
}
单链表
typedef int ElemType;
typedef struct node
{
ElemType data; //数据域
struct node *next; //指针域
} LNode, *LinkList;
//建立链表
LinkList Create_LinkList()
{
LinkList H = (LinkList)malloc(sizeof(LNode));
if (H == NULL)
{
printf(" malloc error") ;
return NULL;
}
H->next = NULL;
return H;
}
//求表长
int Length_LinkList(LinkList H)
{
LinkList p = H;
int j = 0;
while (p->next != NULL)
{
p = p->next;
j++;
}
return j;
}
//查找操作（按序号）
LinkList Get_LinkList(LinkList H, int k)
{
LinkList p = H;
int j = 0;
while(p->next != NULL && j < k)
{
p = p->next;
j++;
}
return p;
}
//查找操作（按值）
LinkList Locate_LinkList(LinkList H, ElemType x)
{
LinkList p = H->next;
while(p != NULL && p->data != x)
{
p = p->next;
}
return p;
}
//插入操作
int Insert_LinkList(LinkList H, int i, ElemType x)
{
LinkList
p = Get_LinkList(H, i-1);
if (p == NULL)
{
printf("insert location error");
return ERROR;
}
else
{
s = (LinkList)malloc(sizeof(LNode));
s->data = x;
s->next = p->next;
p->next = s;
return TRUE;
}
}
//删除操作
int Delete_LinkList(LinkList H, int i)
{
LinkList p, q;
p = Get_LinkList(H, i-1)
if (p != NULL && p->next != NULL)
{
q = p->next;
p->next = q->next;
free(q);
return TURE;
}
else
{
printf("no-existent node No.i");
return ERROR;
}
}
//链表倒置
void Reverse_LinkList(LinkList H)
{
LinkList p, q;
p = H->next;
H->next = NULL;
while(p)
{
q =p;
p=p->next;
q->next = H->next;
H->next = q;
}
}
//链表差A-B
void Difference_LinkList(LinkList LA, LinkList LB)
{
LinkList q;
if (LB == NULL)
{
return;
}
q = LB->next;
while (q != NULL)
{
Delete_LinkList(LA, q->data);
q = q->next;
}
}
双链表
typedef struct dlnode
{
ElemType data;
struct dlnode *prior, *next;
} DLNode, *DLinkList;
插入操作：p指向链表中某结点，s指向待插入的新结点，将*s插入到*p前面
1）s->prior = p->prior;
2）p->prior->next = s;
3）s->next = p;
4）p->prior = s;
删除操作：p指向双向链表中待删除的结点
1）p->prior->next = p->next;
2）p->next->prior = p->prior;
3）free(p);
静态链表
typedef struct snode
{
ElemType data;
int next; //cursor
} SNode;
SNode sd[MAXSIZE]
int SL; //头指针变量
稀疏多项式
一元稀疏多项式可写成：Pn(x) = p1xe1+p2xe2+ ... + pmx^em pi是非零系数 0<=e1<e2<...<em<=n
线性表表示为（(p1,e1), (p2,e2), ..., (pm,em)）
typedef struct Polyn
{
float coef; //系数
int expn; //指数
struct Polyn *next; //指向下一个节点的指针
} PolynNode, *PolynLink;
PolynLink Create_Polyn()
{
PolynLink head, rear, s;
int c, e;
head = (PolynLink)malloc(sizeof(PolynNode));
rear = head;
scanf("%d, %d", &c, &e);
while(c != 0)
{
s = (PolynLink)malloc(sizeof(PolynNode));
s->coef = c;
s->expn = e;
rear->next = s;
rear = s;
scanf("%d, %d", &c, &e);
}
rear->next = NULL;
return head;
}
void PrintPolyn(PolynLink p)
{
PolynLink q = p->next;
int flag = 1;
if (!q)
{
putchar('0');
printf("\n");
return;
}
while(q)
{
if (q->coef > 0 && flag != 1)
{
putchar('+');
}
if (q->coef != 1 && q->coef != -1)
{
printf("%g",q->coef);
if (q->expn == 1)
{
putchar('X');
}
else if (q->expn)
{
printf("X^%d", q->expn);
}
}
else
{
if (q->coef == 1)
{
if (!q->expn) putchar('1');
else if (q->expn == 1) putchar('1');
else printf("-X^%d", q->expn);
}
}
q = q->next;
flag++;
}
printf("\n");
}
PolynLink AddPolyn(Polyn pa, Polyn pb)
{
PolynLink qa = pa->next;
PolynLink qb = pb->next;
PolynLink headc, pc, qc;
pc = (PolynLink)malloc(sizeof(PolynNode));
pc->next = NULL;
headc = pc;
while (qa != NULL && qb != NULL)
{
qc = (PolynLink)malloc(sizeof(PolynNode));
if (qa->expn < qb->expn)
{
qc->coef = qa->coef;
qc->expn = qa->expn;
qa = qa->next;
}
else if (qa->expn == qb->expn)
{
qc->coef = qa->coef + qb->coef;
qc->expn = qa->expn;
qa = qa->next;
qb = qb->next;
}
else
{
qc->coef = qb->coef;
qc->expn = qb->expn;
qb = qb->next;
}
if (qc->coef != 0)
{
qc->nex = pc->next;
pc->next = qc;
pc = qc;
}
else
{
free(qc);
}
}
while (qa != NULL)
{
qc = (PolynLink)malloc(sizeof(PolynNode));
qc->coef = qa->coef;
qc->expn = qa->expn;
qa = qa->next;
qc->next = pc->next;
pc->next = qc;
pc = qc;
}
while (qb != NULL)
{
qc = (PolynLink)malloc(sizeof(PolynNode));
qc->coef = qb->coef;
qc->expn = qb->expn;
qb = qb->next;
qc->next = pc->next;
pc->next = qc;
pc = qc;
}
return
}
PolynLink SubPolyn(PolynLink pa, PolynLink pb)
{
PolynLink h = pb;
PolynLink p = pb->next;
PolynLink pd;
//pb反号
while (p)
{
p->coef *= -1;
p = p->next;
}
pd = AddPolyn(pa,h)
//恢复pb符号
for (p=h->next; p != NULL; p=p->next;)
{
p->coef *= -1;
}
return pd;
}
栈和队列
栈(Stack)是一种只允许在一端(栈顶top)进行插入和删除的线性表，它是一种操作受限的线性表。
队列(Queue)是一种只允许在表的一端（队尾rear）进行插入，在表的另 一端（队头front）进行删除，它是一种操作受限的线性表。
顺序栈
#define MAXSIZE 100
typedef int Elem
typedef struct
{
ElemType data[MAXSIZE];
int top;
} SeqStack;
SeqStack *s;
//初始化stack
SeqStack* Init_SeqStack()
{
SeqStack *s;
s = (SeqStack*)malloc(sizeof(SeqStack));
s->top = -1;
return s;
}
//判空栈
int Empty_SeqStack(SeqStack* s)
{
return (s->top == -1);
}
//判满栈
int Full_SeqStack(SeqStack* s)
{
return (s->top == MAXSIZE -1);
}
//入栈
int Push_SeqStack(SeqStack* s, ElemType x)
{
if (!Full_SeqStack(s))
{
s->top++;
s->data[s->top] = x;
return 1;
}
else
{
return 0;
}
}
//出栈
int Pop_SeqStack(SeqStack* s, ElemType *x)
{
if (!Empty_SeqStack(s))
{
*x = s->data[s->top];
s->top--;
return 1;
}
else
{
return 0;
}
}
//取栈顶元素
ElemType Top_SeqStack(SeqStack *s)
{
if (!Empty_SeqStack(s))
{
return (s->data[s->top]);
}
else
{
return 0;
}
}
共享栈
typedef struct
{
ElemType stack[MAXNUM];
int leftTop;
int rightTop;
} dupSqStack;
char status;
//初始化操作
int initDupStack(dupSqStack *s)
{
if ((s=(dupSqStack*)malloc(sizeof(dupSqStack))) == NULL) return FALSE;
s->leftTop = -1;
s->rightTop = MAXNUM;
return TRUE;
}
//入栈操作
int pushDupStack(dupSqStack *s, char status, ElemType x)
{
if (s->leftTop+1 == s->rightTop) return FALSE;
if (status== 'L') s->stack[++s->leftTop]=x;
else if (status == 'R') s->stack[--s->rightTop] = x;
else return FALSE;
return TURE;
}
ElemType popDupStack(dupSqStack *s, char status)
{
if (status == 'L')
{
if (s->leftTop < 0)
{
return NULL;
}
else
{
return (s->stack[s->leftTop--]);
}
}
else if (status == 'R')
{
if (s->rightTop>MAXNUM-1)
{
return NULL;
}
else
{
return (s->stack[s->rightTop++]);
}
}
else return NULL;
}
链式栈
typedef struct StackNode
{
ElemType data;
struct StackNode *nex;
} StackNode, StackLinkList;
int pushLStack(StackLinkList top, ElemType x)
{
StackLinkList p;
if ((p=(StackLinkList)malloc(sizeof(StackNode))) == NULL) return FALSE;
p->data = x;
p->next = top->next;
top->next = p;
return TRUE;
}
ElemType popLStack(StackLinkList *top)
{
StackLinkList p;
ElemType x;
if (top->next == NULL) return NULL;
p = top->next;
top->next = p->next;
x = p->data;
free(p);
return x;
}
递归
//阶乘函数n!
int fact(int n)
{
if (n == 0)
{
return 1;
}
else
{
return (n*fact(n-1));
}
}
//Hanoi塔问题
void hanoi(int n, char x, char y, char z, int &i)
{
if (n == 1)
{
move(x, 1, z); i++;
}
else
{
hanoi(n-1, x, z, y);
move(x, n, z);
i++;
hanoi(n-1, y, x, z);
}
}
顺序队列
define MAXSIZE 100
typedef struct
{
ElemType data[MAXSIZE];
int rear, front;
} SeQueue;
SeQueue *sq;
int Create_SeQueue()
{
sq = (SeQueue*)malloc(sizeof(SeQueue));
sq->rear = sq->front = -1;
}
int Get_QueueLength(SeQueue *s)
{
return ((s->rear) - (s->front));
}
int Full_Queue(SeQueue *s)
{
return (Get_QueueLength(s) == MAXSIZE);
}
int Empty_Queue(SeQueue *s)
{
return (Get_QueueLength(s) == 0);
}
int In_Queue(SeQueue *s, ElemType x)
{
if (Full_Queue(s)) return FAILE;
s->rear++;
s->data[sq->rear] = x;
return TRUE;
}
int Out_Queue(SeQueue *s, ElemType *x)
{
if (Empty_Queue(s)) return FAILE;
s->front++;
x = sq->data[sq->front];
}
循环队列
typedef struct
{
ElemType data[MAXSIZE];
int front, rear;
}CSeQueue;
//初始化空队
CSeQueue* InitSeQueue()
{
q = (CSeQueue*)malloc(sizeof(CSeQueue));
if (q == NULL) printf("malloc fail\n");
q->front = q->rear = MAXSIZE-1;
return q;
}
//判断队空
int Empty_CSeQueue(CSeQueue *q)
{
return (q->front == q->rear)
}
//判断队满
int Full_CSeQueue(CSeQueue *q)
{
return ((q->rear+1)%MAXSIZE == q->front);
}
//入队
int In_CSeQueue(CSeQueue* q, ElemType x)
{
if (Full_CSeQueue(q))
{
return FALSE;
}
else
{
q->rear = (q->rear +1) % MAXSIZE;
q->data[q->rear] = x;
return TRUE;
}
}
//出队
int Out_CSeQueue(CSeQueue* q, ElemType *x)
{
if (Empty_CSeQueue(q) ) return FALSE;
else
{
q->front = (q->front + 1) % MAXSIZE;
*x = q->data[q->front];
return TRUE;
}
}
链队列（循环队列）
typedef struct node
{
ElemType data;
struct node *next;
} QNode;
typedef struct
{
QNode *front;
QNode *rear;
} LQueue;
//定义一个指向链队的指针
LQueue *HQueue;
//创建一个带点结点的空队
LQueue* Init_LQueue()
{
LQueue *q, *p;
q = (LQueue*)malloc(sizeof(LQueue));
p = (QNode*)malloc(sizeof(QNode));
p->next = NULL;
q->front = q->rear = p;
return q;
}
int Empty_LQueue(LQueue *q)
{
return (q->front == q->rear);
}
void In_LQueue(LQueue *q, ElemType x)
{
QNode *p;
p = (QNode*)malloc(sizeof(QNode));
if (p == NULL)
{
printf("malloc fail");
return NULL;
}
p->data = x; p->next = NULL;
q->rear->next =p;
q-rear = p;
}
void Out_LQueue(LQueue *q, ElemType *x)
{
QNode *p;
if (Empty_LQueue(q)) return FALSE
p=q->front->next;
q->front->next=p->next;
*x = p->data;
free(p);
if (q->front->next == NULL) q->rear = q->front;
return TRUE;
}
串（string)是由零个或多个字符组成的有限序列，一般记作：S=a1a2a3..an(n>=0,串长度)，其中S为串的名字，单引号括起来的字符序列为串的值
顺序串存储结构：
#define MAXLEN 50 //leng
typedef struct {
char ch[MAXLEN-1];
int len;
}
块链串存储结构
#define BLOCK_SIZE 4
typedef struct block
{
char ch[BLOCK_SIZE];
struct block *next;
} Block;
typedef struct
{
Block *head;
Block *tail;
int len;
} LString;
串的模式匹配
【BF模式匹配算法】Brute-Force算法又称蛮力匹配算法，从主串S的第pos个字符开始的子串与模式串T比较的策略是从前到后依次进行比较。当在最坏情况下时，算法的时间复杂度为O(nxm)
int Index(String S, int pos, String T)
{
int i = pos, j = 1;
while (i <= S.len && j <= T.len)
{
if (S.ch[i] == T.ch[j]) //当对应字符相等时，比较后续字符
{
i++;
j++;
}
else //当对应字符不等时
{
i = i - j + 2; //主串回溯到(i-j+2)的位置重新比较
j = 1; //模式串从头开始重新比较
}
}
if (j > T.len)
{
return (i - T.len); //匹配成功时，返回匹配起始位置
}
else
{
return 0; //匹配失败时，返回0
}
}
【KMP模式匹配算法】Knuth-Morris-Pratt算法，每当一趟匹配过程中出现字符比较不等时，主串S中的i指针不需回溯，而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离后，继续进行比较。时间复杂度为O(n+m)。KMP算法的不同点是消除BF算法中主串S指针回溯的情况
int Index_KMP(String S, int pos, String T)
{
int i = pos, j = 1;
while(i <= S.len && j <= T.len)
{
if (j == 0 || S.ch[i] == T.ch[j])
{
i++;
j++;
}
else
{
j = next[j]
}
}
if (j > T.len)
{
return (i - T.len);
}
else
{
return 0;
}
}
三元组顺序表存储结构
#define MAXSIZE 1000
typedef struct {
int row, col;
ElementType value;
} Triple;
typedef struct {
Triple data[MAXSIZE+1];
int rows, cols, nums;
} TSMatrix;
十字链表
typedef struct OLNode
{
int row, col;
ElemType value;
struct OLNode *right, *down;
} OLNode, *OLink;
typedef struct
{
OLink *rowhead, *colhead;
int rows,cols,nums;
} *CrossList;
广义表
1.头尾链表存储结构
typedef struct GLNode
{
int tag;
union
{
AtomType atom;
struct
{
struct GLNode *head, *tail;
} LNode;
} atom_LNode;
} GLNode, *GList;
2.扩展的线性链表存储结构（孩子兄弟存储结构）
typedef struct GLNode
{
int tag;
union
{
AtomType atom;
struct GLNode *head;
} atom_LNode;
struct GLNode *tail;
} GLNode, *GList;
树的基本术语
结点（Node）：包含一个数据元素及若干指向其子树的分支
结点的度（Degree）：结点拥有子树的个数称为该结点的度
树的度：树中所有结点的度的最大值
叶子结点（Leaf）：度为0的结点称为叶子结点，也称为终端结点
内部结点（Lnternal node）：度不为0的结点和为内部结点，也称为分支结点或非终端结点
孩子结点（Child）：结点的子树的根（即直接后继）称为该结点的孩子结点
双亲结点（Parent）：结点是其子树的根的双亲，即结点是其孩子的双亲
兄弟结点（Sibling）：同一双亲的孩子结点之间互称兄弟结点
堂兄弟：双亲是兄弟或堂兄弟的结点间互称堂兄弟结点
祖先结点（Ancestor）：结点的祖先结点是指从根结点到该结点的路径上的所有结点
子孙结点（Descendant）：结点的子孙结点是指该结点的子树中的所有结点
结点的层次（Level）：结点的层次从树根开始定义，根为第一层，根的孩子为第二层。若某结点在第k层，则其孩子就是在第k+1层，依此类推。
树的深度（Depth）：树中所有结点层次的最大值称为树的深度，也称为树的高度
前辈：层号比该结点层号小的结点，都可称为该结点的前辈
后辈：层号比该结点层号大的结点，都可称为该结点的后辈
森林（forest）：m(m>=0)棵互不相交的树的集合称为森林
有序树（Ordered tree）和无序树（Unordered tree）：树中结点的各棵子树从左到右是有特定次序的树称为有序树，否则称为无序树
二叉树：满足以下两个条件的树形结构
（1）每个结点的度不大于2；
（2）结点每棵子树的位置是明确区分左右的，不能随意改变 ；
二叉树性质
性质1：在二叉树的第 i 层上至多有2^(i-1)个结点(i >= 1)
性质2：深度为k的二叉树至多有2^k - 1个结点(k >= 1)
性质3：对任意一棵二叉树T，若终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1
满二叉树：深度为k且含有2^k - 1结点的二叉树称为满二叉树
完全二叉树：深度为k，结点数为n（n <= 2^k -1）的二叉树，当且仅当其n个结点与满二叉树中连续编号为1至n的结点位置一一对应时，称为完全二叉树
完全二叉树特征：1）所有叶子结点只可能出现在层号最大的两层上；2）对任意结点，若其右子树的层高为k，则其左子树层高只可为k或k+1
性质4：具有n个结点的完全二叉树的深度为(log2 n) + 1
性质5：对于具有n个结点的完全二叉树，如果按照对满二叉树结点进行连续编号的方式，对所结点从1开始顺序编号，则对于任意序号为 i 的结点有：
1）如果 i = 1, 则结点 i 为根，其无双亲结点；如果 i > 1，则结点 i 的双亲结点序号为 i/2;
2）如果2i <= n, 则结点 i 的左孩子结点序号为 2i，否则结点 i 无左孩子；
3）如果2i+1 <= n，则结点 i 的右孩子结点序号为2i+1，否则，结点 i 无右孩子。
二叉树顺序存储结构
#define MAX 100
typedef struct
{
dataType SqBiTree[MAX+1]; /* 0号单元不用 */
int nodemax; /* 数组中最后一个结点的下标 */
} Bitree;
二叉树链式存储结构
typedef struct Node
{
dataType data;
struct Node *LChild;
struct Node *RChild;
} BiTNode, *BiTree;
二叉树遍历的递归定义
1.先序遍历：1）访问根结点 2）按选序遍历左子树 3）按先序遍历右子树
2.中序遍历：1）按中序遍历左子树 2）访问根结点 3）按中序遍历右子树
2.后序遍历：1）按后序遍历左子树 2）按后序遍历右子树 3）访问根结点
// 递归遍历算法
// 三个递归遍历时间复杂度均为O(n)
void PreOrder(BiTree root)
{
if (root == NULL) return;
Visit(root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
void InOrder(BiTree root)
{
if (root == NULL) return;
InOrder(root->LChild);
Visit(root->data);
InOrder(root->RChild);
}
void PostOrder(BiTree root)
{
if (root == NULL) return;
PostOrder(root->LChild);
PostOrder(root->RChild);
Visit(root->data);
}
//非递归遍历实现
//非递归遍历时间复杂度为O(n)，空间复杂度为O(k) (k为二叉树深度)
void PreOrder(BiTree root)
{
SeqStack *S;
BiTree p;
InitStack(S);
p = root
while(p != NULL || ！IsEmpty(S))
{
while(p != NULL)
{
Visit(p->data);
Push(S,p);
p = p->LChild;
}
if (!IsEmpty(S))
{
Pop(S, &p);
p = p->RChild;
}
}
}
void InOrder(BiTree root)
{
SeqStack *S;
BiTree p;
InitStack(S);
p = root
while(p != NULL || !IsEmpty(S))
{
while(p != NULL)
{
Push(S,p);
p = p->LChild;
}
if (!IsEmpty(S))
{
Pop(S,&p);
Visit(p->data);
p = p->RChild;
}
}
}
void PostOrder(BiTree root)
{
SeqStack *S;
BiTree p, q;
InitStack(S);
p = root; q = NULL;
while (p != NULL || !IsEmpty(S))
{
while(p != NULL)
{
Push(S,p);
p = p->LChild;
}
if (!IsEmpty(S))
{
Top(S,&p);
if ((p->RChild == NULL) || (p->RChild == q))
{
Pop(S,&p);
Visit(p->data);
q = p;
p = NULL;
}
else
{
p = p->RChild;
}
}
}
}
//层次遍历
void LevelOrder(BiTree root)
{
SeqQueue *Q;
BiTree p;
InitQueue(Q);
EnterQueue(Q, root);
while(!IsEmpty(Q))
{
DeleteQueue(Q, &p);
Visit(p->data);
if (p->LChild != NULL)
{
EnterQueue(Q, p->LChild);
}
if (p->RChild != NULL)
{
EnterQueue(Q, p->RChild);
}
}
}
//统计二叉树结点数
int Count = 0;
void PreOrder(BiTree root)
{
if (root == NULL) return;
Count++;
PreOrder(root->LChild);
PreOrder(root->RChild);
}
//打印二叉树的叶子结点
void InOrder(BiTree root)
{
if (root == NULL) return;
InOrder(root->LChild);
if (root->LChild == NULL && root->RChild == NULL) printf("%d",root->data);
InOrder(root->RChild);
}
//统计叶子结点数目
void Leaf(BiTree root)
{
int nl, nr;
if (root == NULL) return 0;
if ((root->LChild == NULL) && (root->RChild == NULL)) return 1;
nl = Leaf(root->LChild);
nr = Leaf(root->RChild);
return (nl+nr);
}
//二叉树高度
int TreeDepth(BiTree root)
{
int hl, hr, h;
if (root == NULL) return 0;
hl = TreeDepth(root->LChild);
hr = TreeDepth(root->RChild);
h = (hl > hr ? hl : hr) +1;
return h;
}
//结点的双亲
BiTree Parent(BiTree root, BiTree current)
{
BiTree *p;
if (root == NULL) return NULL;
if (root->LChild == current || root->RChild == current)
{
return root;
}
p = Parent(root->LChild, current);
if (p != NULL)
{
return p;
}
else
{
return (Parent(root->RChild, current));
}
}
//相似性判定
int Like(BiTree t1, BiTree t2)
{
int like1,like2;
if (t1 == NULL && t2 == NULL) return 1;
else if (t1 == NULL && t2 == NULL) return 0;
else {
like1 = Like(t1->LChild, t2->LChild);
like2 = Like(t1->RChild, t2->RChild);
return (like1 && like2);
}
}
//按树状打印二叉树
void PrintTree(BiTree root, int h)
{
if (root == NULL) return;
PrintTree(root->RChild, h+1);
for(int i=0; i<h; i++) Printf(" ");
printf("%c\n", root->data);
PrintTree(root->LChild, h+1);
}
//建立二叉树
void CreateBiTree(BiTree *root)
{
char ch;
ch = getchar();
if (ch == '^') { *root = NULL; return; }
*root = (BiTree)malloc(sizeof(BiTNode));
(*root)->data = ch;
CreateBiTree(&((*root)->LChild));
CreateBiTree(&((*root)->RChild));
}
由遍历序列确定二叉树
1.由先序和中序序列确定二叉树
a.由先序序列中的第一个结点确定根结点D；
b.由根结点D分割中序序列：D之前是左子树L的中序序列，D之后是右子树R的中序序列，同时获得L和R的结点个数；
c.根据左子树L的结点个数，分割先序序列：第一个结点根D，之后是左子树L的先序序列，最后右子树R的先序序列；
至此，已确定了根D，左子树L的先序和中序序列，右子树R的先序和中序序列。如此类推，再对每棵子树进行上述处理，便可确定整棵二叉树。
2.由中序和后序序列确定二叉树
a.由后序序列中的最后一个结点确定根结点D；
b.由根结点D分割中序序列：D之前是左子树L的中序序列，D之后是右子树R的中序序列，同时获得L和R的结点个数；
c.根据左子树L的结点个数，分割后序序列：首先是左子树L的后序序列，随后是右子树R的后序序列，最后是根结点D；
至此，已确定了根D，左子树L的中序和后序序列，右子树R的中序和后序序列。如此类推，再对每棵子树进行上述处理，便可确定整棵二叉树。
线索化二叉树
//先序线索化算法
void PreOrder(BiTree root)
{
static BiTree pre = NULL;
if(root == NULL) return;
if (root->LChild == NULL)
{
root->LChild = pre;
root->Ltag = 1;
}
if (pre != NULL && pre->RChild == NULL)
{
pre->RChild = root;
pre->Rtag = 1;
}
pre = root;
PreOrder(root->LChild);
PreOrder(root->RChild);
}
//中序线索化算法
void InThread(BiTree root)
{
static BiTree pre = NULL;
if (root == NULL) return;
InThread(root->LChild);
if (root->LChild == NULL)
{
root->LChild = pre;
root->Ltag = 1;
}
if (pre != NULL && pre->RChild == NULL)
{
pre->RChild = root;
pre->Rtag = 1;
}
pre = root;
InThread(root->RChild);
}
//后序线索化算法
void Post(BiTree root)
{
static BiTree pre = NULL;
if (root==NULL) return;
PostOrder(root->LChild);
PostOrder(root->RChild);
if (root->LChild == NULL)
{
root->LChild = pre;
root->Ltag = 1;
}
if (pre != NULL && pre->RChild == NULL)
{
pre->RChild = root;
pre->Rtag = 1;
}
pre = root;
}
树的存储结构
1.双亲表示法 2.孩子表示法 3.孩子兄弟表示法
树转换为二叉树方法
1）加线：树中所有相邻兄弟之间加一条连线
2）删线：对每个结点，只保留其与第一个孩子结点之间的连线，删掉该结点与其他孩子结点之间的连线
3）旋转调整：以树的根结点为轴心，将整棵顺时针旋转一定的角度，使之层次结构清晰、左右子树分明
森林转换为二叉树
1）转换：将森林中的每一棵树均转换成相应二叉树
2）加线：将相邻的各棵二叉树的根结点之间加线，使之连为一体
3）旋转调整：以第一棵二叉树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之层次结构清晰、左右子树分明。即依次把后一棵二叉树的根结点调整到作为前一棵二叉树根结点的右孩子的位置
二叉树转换为森林
1）加线：若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、....都与该结点的双亲结点间加上连线
2）删线：删掉原二叉树中所有双亲结点与右孩子间的连线
3）旋转调整：旋转、整理由1）2）两步所得到的各棵树，使之结构清晰、层次分明
树的遍历
（1）先根遍历：若树非空，1.访问根结点；2.从左到右依次先根遍历根结点的每一棵子树
（2）后根遍历：若树非空，1.从左到右依次后根遍历根结点的每一棵子树；2.访问根结点
void RootFirst(CSTree root)
{
if (root == NULL) return;
Visit(root->data); //访问根结点
RootFirst(root->FirstChild); //先根遍历首子树
RootFirst(root->NextSibling); //先根遍历兄弟子树
}
void RootTail(CSTree root)
{
if (root == NULL) return；
RootTail(root->FirstChild); //后根遍历首子树
RootTail(root->NextSibling); //后根遍历兄弟树
Visit(root->data); //访问根结点
}
森林的遍历
（1）先序遍历：若森林非空，1）访问森林中第一棵树的根结点 2）先序遍历第一棵树中根结点的子树森林 3）先序遍历除去第一棵树之后剩余的树构成的森林
（2）中序遍历：若森林非空，1）中序遍历森林中第一棵树的根结点的子树森林 2）访问第一棵树的根结点 3）中序遍历除去第一棵树之后剩余的树构成的森林
树和森林与二叉树遍历总结
(1) 树的先根遍历、后根遍历对应于转换的二叉树的先序遍历、中序遍历
(2) 森林的先序遍历、中序遍历对应于转换的二叉树的先序遍历、中序遍历；
(3) 另外，把一棵树看成森林，则森林的先序遍历、中序遍历对应于树的先根遍历、后根遍历
哈夫曼树
路径：从树中一个结点到另一个结点之间的分支序列构成两个结点间的路径
路径长度：路径上分支的条数称为路径长度
树的路径长度：从树根到每个结点的路径长度之和称为树的路径长度
结点的权：给树中结点赋予一个数值，该数值称为结点的权
带权路径长度：结点到树根间的路径长度与结点的权的乘积，称为该结点的带权路径长度
树的带权路径长度：树中所有叶子结点的带权路径长度之和，称为树的带权路径长度
最优二叉树：在叶子个数n以及各叶子的权值Wk确定的条件下，树的带权路径长度值最小的二叉树称为最优二叉树
哈夫曼算法存储结构
#define N 30
#define M 2*N-1
typedef struct
{
int weight;
int parent, LChild, RChild;
} HTNode, HuffmanTree[M+1]
void CrtHuffmanTree(HuffmanTree ht, int w, int n)
{
int m = 2*n -1;
for (i = 1; i <= n; i++) ht[i] = {w[i], 0, 0, 0};
for (i = n+1; i <= m; i++) ht[i]={0,0,0,0};
for (i = n+1; i <= m; i++)
{
select(ht, i-1, &s1, &s2);
ht[i].weight = ht[s1].weight + ht[s2].weight;;
ht[i].LChild = s1; ht[i].RChild = s2;
ht[s1].parent = i; ht[s2].parent = i;
}
}
哈夫曼编译码
哈夫曼编码算法
(1)构造哈夫曼树 （2）在哈夫曼树上求叶子结点编码
void CrtHuffmanCode(HuffmanTree ht, HuffmanCode hc, int n)
{
char *cd;
int start;
cd = (char *)malloc(n * sizeof(char));
cd[n-1] = '\0';
for (i = 0; i <= n; i++)
{
start = n-1; c = i; p=ht[i].parent;
while(p != 0)
{
--start;
if (ht[p].LChild == c) cd[start] = '0';
else cd[start] = '1';
c = p; p = ht[p].parent;
}
hc[i] = (char*)malloc((n-start)*sizeof(char));
strcpy(hc[i], &cd[start]);
}
}
二叉树对应表达式为（A+B)+(C-D)/E
先序遍历序列：++AB/-CDE 对应前缀表达式
中序遍历序列：A+B+C-D/E 对应中缀表达式
后序遍历序列：AB+CD-E/+ 对应后缀表达式
图
图的定义：图是由顶点集V和弧集R构成的数据结构，Graph=（V,R），
其中：V={v|v ∈ DataObject}, R={VR}, VR={<v,w>|P(v,w) 且 (v,w ∈ V)}.
<v,w>表示从顶点v到顶点w的一条弧，并称为v为弧尾，w为弧头。
若<v,w>∈VR必有<w,v>∈VR，则以(v,w)代替这两具有序对，称v和w之间存在一条边
有向图：由顶点集和弧集构成的图称为有向图，其中：
V1={A,B,C,D,E},
VR1={<A,B>, <A,E>, <B,C>, <C,D>, <D,A>, <D,B>, <E,C>}
无向图：由顶点集和边集构成的图称为无向图，其中：
V2={A,B,C,D,E,F}
VR2={(A,B), (A,E), (B,E), (B,F), (C,D), (D,A), (D,B), (E,C)}
有向图和无向网：有向图或无向图中的弧或边带权后的图分别称为有向网和无向网
完全图：图中有n个顶点，n(n-1)/2条边的无向图称为完全图
有向完全图：图中有n个顶点，n(n-1)条弧的有向图称为有向完全图
稀疏图：假设图中有n个顶点e条边(或弧)，若边（或弧）的个数 e < nlogn，则称为稀疏图，否则称为稠密图
邻接点：若无向图中顶点v和w之间存在一条边(v,w)，则称为顶点v和w互为邻接点，称边(v,w)依附于顶点v和w或边(v,w)与顶点v和w相关联
顶点的度：在无向图中的顶点v关联的边的数目定义为v的度，记为TD(v)
路径：设图G={V,{V,R}}中的{u=Vi,0, Vi,1, ..., Vi,m = w}顶点序列中，有(Vi,j-1, Vi,j)∈VR (1≤ j ≤ m), 则称为从顶点u到顶点w之间存在一条路径。路径上边的数目称为路径长度，有向图的路径也是有向的
简单路径：顶点不重复的路径称为简单路径
回路：首尾顶点相同的路径称为回路
简单回路：除了首尾顶点，中间任何一个顶点不重复的回路称为简单回路
连通图：在无向图中，若顶点Vi到Vj有路径存在，则称Vi和Vj是连通的。若无向图中任意两个点顶点之间都有路径相通，即是连通的，则称此图为连通图，否则为非连通图。无向图中各个极大连通子图称为该图的连通分量
强连通图：在有向图中，基任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图，否则为非强连通图。有向图中各个极大强连通子图称为该图的强连通分量
生成树：包含连通图中全部顶点的极小连通子图称为该图的生成树，即假设一个连通图有n个顶点和e条边，其中n个顶点和n-1条边构成一个极小连通子图，该极小连通子图为此连通图的生成树。对非连通图，由各个连通分量的生成树的集合称为非连通图的生成森林
邻接矩阵存储结构
#define MAXVEX 20 //最大顶点个数
#define INFINITY 32768 //表示极大值∞
typedef struct
{
int arcs[MAXVEX][MAXVEX]; //边（或弧）信息
VexType vex[MAXVEX]; //顶点信息，顶点类型根据实际情况自行定义
int vexnum; //顶点数目
int arcnum; //边（或弧）数目
} AdjMatrix; //邻接矩阵
采用邻接矩阵存储图，由于无向图的邻接矩阵是对称矩阵，采用特殊矩阵的压缩存储，即下三角矩阵即可完成。具有n个顶点的无向图，只需要n(n-1)/2个空间即可，但对于有向图而言，邻接矩阵不一定是对称的，所以仍然需要n2个空间
邻接表存储结构
#define MAXVEX 20
typedef struct ArcNode
{
int adjvex;
int weight;
struct ArcNode *next;
} ArcNode;
typedef struct VertexNode
{
char vexdata;
ArcNode *head;
} VertexNode;
typedef struct
{
VertexNode vertex[MAXVEX];
int vexnum; //顶点数
int arcnum; //弧数
} AdjList;
十字链表
#define MAXVEX 20
typedef struct ArcNode
{
int tailvex； //弧尾（终点）顶点序号
int headvex; //弧头（起点）顶点序号
int weight; //弧权值
struct ArcNode *hnextarc, *tnextarc;
} ArcNode;
typdef struct VertexNode
{
char vexdata; //顶点的相关数据信息
ArcNode *head, *tail;
} VertexNode;
typedef struct
{
VertexNode vertex[MAXVEX];
int vexnum; //顶点数
int arcnum; //弧数
} OrthList;
多重链表
#define MAXVEX 20
typedef struct ArcNode
{
int mark, ivex, jvex;
int weight;
struct ArcNode *inext, *jnext;
} ArcNode;
typedef struct VertexNode
{
char vexdata;
ArcNode *head;
} VertexNode;
typedef struct
{
VertexNode vertex[MAXVEX];
int vexnum;
int arcnum;
} AdjMultipleList;
图的遍历
int visited[MAXVEX] = {0};
//递归深度优先搜索遍历连通子图
void DFS(Graph g, int v0)
{
visit(v0);
visited[v0]=1;
w = FirstAdjVex(g, v0);
while (w != -1)
{
if (!visited[w]) DFS(g,w);
w = NextAdjVex(g,v0,w);
}
}
//非递归深度优先搜索遍历连通子图
void DFS(Graph g, int v0)
{
int visited[MAXVEX] = {0};
InitStack(S);
Push(S, v0);
while (!Empty(S))
{
v = Pop(S);
if (!visited[v])
{
visit(v);
visited[v] = 1;
}
w = FirstAdjVertex(g,v);
while (w != -1)
{
if (!visit[w]) Push(S, w);
w = NextAdjVertex(g,v,w);
}
}
}
//广度优先搜索遍历连通子图
void BFS(Graph g, int v0)
{
visit(v0);
visited[v0] = 1;
InitQueue(&Q);
EnterQueue(&Q, v0);
while (!Empty(Q))
{
DeleteQueue(&Q, &v);
w = FirstAdj(g,v);
while ( w != -1)
{
if (!visited[w])
{
visit(w);
visited[w] = 1;
EnterQueue(&Q, w);
}
w = NextAdj(g,v,w);
}
}
}
void TraverseG(Graph g)
{
for (v=0; v<g.vexnum; v++)
visited[v] = 0;
for (v=0; v<g.vexnum; v++)
if (!visited[v]) DFS(g,v);
}
最小生成树
最小生成树要解决的两个问题如下：
1）尽可能选取权值小的边，但不能构成回路
2）选取n-1条恰当的边以连接网中的n个顶点
1.Prim算法
基本思想：从连通网络N={v,E}中的某一顶点u0出发，选择与它关联的具有最小权值的边（u0,v), 将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中而另一个顶点不在U中的各条边中选择最小的边(u,v)，把它的顶点加入到集点V中，这意味着（u,v）也加入到生成树的边集合中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止，因此Prim也称为加点法
具体地：记N是连通网折顶点集，U是求得生成树的顶点集，TE是求得生成树的边集（1）开始时，U={U0}，TE=Φ；（2）修正U到其余顶点N-U最小极值，将具有最小极值的边纳入TE，对应的顶点纳入U；（3）重复（2）直到N=N。
void Prim(AdjMatrix *G, int start)
{
struct
{
int adjvex;
int lowcost;
} closedge[MAXVEX];
int i,e,k,m,min;
closedge[start].lowcost = 0;
for (i = 1; i<= G->vexnum; i++)
{
if (i != start)
{
closedge[i].adjvex = start;
closedge[i].lowcost = G->arcs[start][i];
}
for (e = 1; e <= G->vexnum-1; e++)
{
min = INFINITY;
for (k = 1; k <= G->vexnum; k++)
{
if (closedge[k].lowcost != 0 && closedge[k].lowcost < min)
{
m = k;
min = closedge[k].lowcost;
}
}
closedge[m].lowcost = 0;
for (i=1; i <= G->vexnum; i++)
{
if (i != m && G->arcs[m][i] < closedge[i].lowcost)
{
closedge[i].lowcost = G->arcs[m][i];
closedge[i].adjvex = m;
}
}
}
}
2.Kruskal算法
基本思想：先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加入该边，依次按照权值递增的次序，选择合适的边进行添加，如此重复，直至加完n-1条边为止。因此也称为加边法
拓扑排序
void FindID(AdjList G, int indegree[MAXVEX])
{
int i;
ArcNode *p;
for (i = 0; i < G.vexnum; i++)
{
indegree[i] = 0;
}
for (i = 0; i < G.vexnum; i++)
{
p = G.vertex[i].head;
while(p != NULL)
{
indegree[p->adjvex]++;
p = p->next;
}
}
}
int TopoSort(AdjList G)
{
Queue Q;
int indegree[MAXVEX];
int i, count, k;
ArcNode *p;
FindID(G, indegree);
InitQueue(&Q);
for (i = 0; i < G.vexnum; i++)
{
if (indegree[i] == 0) EnterQueue(&Q,i);
}
count = 0;
while (!IsEmpty(Q))
{
DeleteQueue(&Q,&i);
printf("%c", G.vertex[i].data);
count++;
p = G.vertex[i].head;
while (p != NULL)
{
k = p->adjvex;
indegree[k]--;
if (indegree[k] == 0) EnterQueue(&Q, k);
p = p->next;
}
}
if (count < G.vexnum) return 0;
else return 1;
}
关键路径：在AOE网中，从源点到汇点之间可能有多条路径，这些路径中具有最长路径长度的路径被称为关键路径
最短路径
单源最短路径
Dijkstra算法思想：
1）初始时，集合S中仅包含源点V0，集合V-S中包含除源点V0以外的所有顶点，V0到V-S中各顶点的路径长度或者为某个权值（如果它们之间有弧相连）或者为∞（没有弧相连）
2）按照最短路径长度递增的次序，从集合V-S中选出到顶点V0路径长度最短的顶点Vk加入到S集合中
3）加入Vk之后，为了寻找下一个最短路径，必须修改从V0到集合V-S中剩余所有顶点Vi的最短路径。若在路径上加入Vk之后，使得V0到Vi的路径长度比原来没有加入Vk时的路径长度短，则修正V0到Vi的路径长度为其中较短的
4）重复以上步骤，直至集合V-S中的顶点全部被加入到集合S中为止
void Dijkstra(AdjMatrix *G, int start, int end, int dist[], int path[][MAXVEX])
{
int mindist, i, j, k, t = 1;
for (i = 1; i <= G->vexnum; i++)
{
dist[i] = G->arcs[start][i];
if (G->arcs[start][i] != INFINITY)
{
path[i][1] = start;
}
}
path[start][0] = 1;
for (i = 2; i <= G->vexnum; i++)
{
mindist = INFINITY;
for (j = 1; j <= G->vexnum; j++)
{
if (!path[j][0] && dist[j] < mindist)
{
k = j;
mindist = dist[j];
}
}
if (mindist == INFINITY) return;
path[k][0] = 1;
for (j = 1; j <= G->vexnum; j++)
{
if (!path[j][0] && G->arcs[k][j] < INFINITY && dist[k] + G->arcs[k][j] < dist[j])
{
dist[j] = dist[k] + G->arcs[k][j];
t = 1;
while (path[k][t] != 0)
{
path[j][t] = path[k][t];
t++;
}
path[j][t] = k;
path[j][t+1] = 0;
}//if
}//for
}//for
}
每对顶点最短路径
Floyd算法
void Floyd(AdjMatrix g, int F[][MAXVEX])
{
int Path[MAXVEX][MAXVEX];
int i,j,k;
for (i = 0; i < g->vexnum; i++)
{
for (j = 0; j < g->vexnum; j++)
{
F[i][j] = g->arcs[i][j];
Path[i][j] = INFINITY;
}
}
for (i = 0; i < g->vexnum; i++)
{
for (j = 0; j < g->vexnum; j++)
{
for(k = 0; k < g->vexnum; k++)
{
if (F[i][j] > F[i][k] + F[k][j])
{
F[i][j] = F[i][k] + F[k][j];
Path = k;
}
}
}
}
}
查找
查找，就是根据给定某个值，在一组记录集合中确定某个“特定的”数据元素（记录）或者找到属性值符合特定条件的某些记录。
查找算法的性能主要是通过平均查找长度进行评价的。平均查找长度：为确定某无素在查找表中的位置需要和给定值进行比较的关键字个数的期望值，称为该查找算法查找成功进的平均查找长度
静态查找表
顺序查找成功的平均查找长度为ASL = (n+1)/2
折半查找成功的平均查找长度为ASL = (n+1)/n * log2 (n+1) - 1 当N>50 近似为ASL = log2 (n+1) - 1
分块查找（或索引查找）将长度为n的表均匀地分成b块，每块含有s个记录，即b=[n/s].
成功的平均查找长度为:
ASL = 1/2 * (n/s + s) + 1 (顺序查找确定所在块)
ASL = log2 (n/s + 1) + s/2（折半查找确定所在块）
#define MAXSIZE 1000
typedef int KeyType;
typedef struct
{
KeyType key;
OtherType other_data;
} RecordType;
typedef struct
{
RecordType r[MAXSIZE + 1];
int length;
} SeqRList;
SeqRList L; //L为一个顺序查找表
//顺序查找
int SeqSearch(SeqRList L, KeyType K)
{
i = L.Length;
while (i >= 1 && L.r[i].key != K) i--;
if (i >= 1) return i;
else return 0;
}
//加监视哨的顺序查找
int SeqSearch(SeqRList L, KeyType K)
{
L.r[0].key = K;
i = L.Length;
while(L.r[i].key != K) i--;
return i;
}
//折半查找
int BinSrch(SeqRList L, KeyType K)
{
int low = 1, high = L.length, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (K == L.r[mid].key) return mid;
else if (K < L.r[mid].key) high = mid - 1;
else low = mid + 1;
}
return 0;
}
动态查找表
二叉排序树（二叉查找树）：空树或者是具有如下特性的二叉树：
1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
3）它的左、右子树也都分别是二叉排序树
BSTree searchBST(BSTree bst, KeyType K)
{
if (!bst) return NULL;
else if (bst->key == K) return bst;
else if (K < bst->key) return SearchBST(bst->lchild, key);
else return SearchBST(bst->rchild, key);
}
平衡二叉树：空树，或者是满足以下性质的特殊二叉排序树：
1）二叉排序树中任何一个结点的左子树和右子树高度相差的绝对值最多为1；
2）它的左、右子树也分别都是平衡二叉树
哈希表
哈希hash（散列、杂凑），根据设定的哈希函数H(key)和处理冲突的方法将一组关键字映像到一个有限的连续的地址集（区间）上，并以关键字面地址集中的“像”作为记录在表中的存储位置，这种表便称为哈希表，这一映像过程称为哈希表或散列，所得存储位置称哈希地址或散列地址
Hash函数构造方法 （构造原则为简单和均匀）
1）除留余数法 H(key) = key %p;
2）数字分析 法
3）平方取中法
4）分段叠加法
5）基数转换法
处理冲突的方法
1）开放定址法
2）二次探测再散列
3）随机探测再散列
内部排序
排入类排序算法
#define MAXSIZE 1000
typedef int KeyType;
typedef struct
{
KeyType key;
OtherType other_data;
} RecordType;
typedef struct
{
RecordType r[MAXSIZE+1];
int length;
} RecordList;
RecordList L; //L为一个记录序列
直接插入排序
算法思想：将第i个记录的关键字Ki与前记录r[1]~r[i-1]的关键字从后向前顺次进行比较，将所有关键字大于Ki的记录依次向后移动一个位置，直到遇到一个关键字小于或等于Ki的记录，该记录的位置即为r[i]的插入位置
void InsertSort(RecordList L)
{
for (i = 2; i <= L.length; i++)
{
if (L.r[i].key < L.r[i-1].key)
{
L.r[0] = L.r[i];
for (j = i -1; L.r[0].key < L.r[j].key; j--)
{
L.r[j+1] = L.r[j];
}
L.r[j+1] = L.r[0];
}
}
}
折半插入排序
算法思想：利用折半查找在r[1]~r[i-1]这个按关键字有序的序列中区中确定r[i]的插入位置
void BiTinsertSort(RecordList L)
{
for (i = 2; i <= L.Length; i++)
{
if (L.r[i].key < L.r[i-1].key)
{
L.r[0] = L.r[i];
low = 1; high = i-1;
while(low <= high)
{
mid = (low + high) / 2;
if (L.r[0].key < L.r[mid].key)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
for (j = i -1; j >= low; j--)
{
L.r[j+1] = L.r[j]; //记录后移
}
L.r[low] = L.r[0]; //插入到正确位置
}
}
}
希尔排序
基本思想：先将整个待排元素序列分割成若干个子序列分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序时，再对全体元素进行一次直接插入排序
void ShellInsert(RecordList L, int dk)
{
for (i = dk +1; i <= L.length; i++)
{
if (L.r[i].key < L.r[i-dk].key)
{
L.r[0] = L.r[i];
for (j = i - dk; j > 0 && L.r[0].key < L.r[j].key; j -= dk)
{
L.r[j+dk] = L.r[j];
}
L.r[j+dk] = L.r[0];
}
}
}
void ShellSort(RecordList L, int dlta[], int t)
{
for (k = 0; k < L.length; t++)
{
ShellInsert(L. dlta[k]);
}
}
交换类排序算法
冒泡排序
算法思想：对待排序记录的关键字两两比较，只要发现两个记录为逆序就进行交换，直到没有逆序的记录为止
void BubbleSort(RecordList L)
{
flag = 1;
for (i = 1; i <= L.length -1 && flag; i++)
{
flag = 0;
for (j = 1; j <= L.length - i; j++)
{
if (L.r[j].key > L.r[j+1].key)
{
t = L.r[j];
L.r[j] = L.r[j+1];
L.r[j+1] = t;
flag = 1;
}
}
}
}
快速排序
算法思想：从待排序列中任意选择一个记录，以该记录的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列r[1...n]将分割成左右的两个子序列，然后分别对分割所得两个子序列递归地进行快速排序，以此类推，直至第个子序列中只含一个记录为止。
int QKpass(RecordList L, int low, int high)
{
L.r[0] = L.r[low];
while (low < high)
{
while(low < high && L.r[high].key >= L.r[0].key) --high;
L.r[low] = L.r[high];
while(low < high && L.r[low].key < L.r[0].key) ++low;
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];
return low;
}
void QKSort(RecordList L, int low, int high)
{
if (low < high)
{
pos = QKpass(L, low, high);
QKSort(L, low, pos -1);
QKSort(L, pos+1, high);
}
}
选择类排序算法
简单选择排序
算法思想：在第i趟的记录序列中选取关键字第i小记录作为有序序列的第i个记录。该类算法关键在于如何从剩余的待排序序列中找出最小或最大的那个记录
void SelectSort(RecordList L)
{
for (i = 1; i <= L.length-1; i++)
{
k = i;
for (j = i+1; j <= L.length-1; j++)
{
if (L.r[j].key < L.r[k].key)
{
k = j;
}
if (k != i)
{
t = L.r[i];
L.r[i] = L.r[k];
L.r[k] = t;
}
}
}
}
推排序
void HeapAdjust(RecordList L, int s, int m)
{
t = L.r[s];
for (j = 2*s; j <= m; j *= 2)
{
if (j < m && L.r[j].key > L.r[j+1].key)
{
j++;
}
if (t.key <= L.r[j].key)
{
break;
}
L.r[s] = L.r[j];
s = j;
}
L.r[s] = t;
}
void CreatHeap(RecordList L)
{
for (i = L.length/2; i >= 1; i--)
{
HeapAdjust(L,i,L.length);
}
}
void HeapSort(RecordList L)
{
CreatHeap(L);
for (i = L.length; i >= 2; i--)
{
L.r[0] = L.r[1];
L.r[1] = L.r[i];
L.r[i] = L.r[0];
HeapAdjust(L,1,i-1);
}
}
网友评论