c数据结构学习
数据的逻辑结构
根据数据元素间的基本特性，有四种基本数据结构
| 类型 | 特性 |
|---|---|
| 集合 | 数据元素间除“同属于同一集合”外，无其他关系 |
| 线性结构 | 一个对一个，如线性表，栈，队列 |
| 树形结构 | 一个对多个 |
| 图状结构 | 多个对多个 |
线性结构的特点
- 一对一的关系
- 除了第一个和最后一个元素外，数据中的每一个元素都有且只有一个直接前驱和一个直接后继
树形结构的特点
- 一对多的关系
- 有且只有一个特定的称为根(root)的数据元素(节点)
- 在树形结构中，树根节点没有前驱元素，其余的每个节点有且只有一个前驱元素。末端元素没有后续的元素，其余的每个元素的后续元素个数可以是一个也可以是多个
图状结构的特点
- 多对多的关系
- 任意的两个元素都可能相关，即图中的任一元素可以有若干个直接前驱和直接后继，属于网状结构类型
逻辑结构
表示数据元素之间的抽象关系(如邻接关系，从属关系等)，按每个元素可能具有的直接前驱数和直接后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。它是从具体问题中抽象出来的数学模型，是独立于计算机存储器(与机器无关)。
数据的存储结构思想
无论数据的逻辑结构是怎样的，它都需要参与各种运算，那就需要将这些数据元素他原本的逻辑关系进行保存，存储于计算机的存储器中(内存)。存储结构是通过计算机语言所编制的程序来实现的故而是依赖于具体的计算机语言的。
顺序存储
将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中(如c语言的数据)
如表L = (a1,a2,a3...)顺序结构
链式存储
将数据结构中各元素分布到存储器的不同点，用地址(或链指针)方式建立他们之间的联系，由此得到的存储结构为链式存储结构
如表L = (a1,a2,a3...)顺序结构
链式存储结构是数据结构的一个重点，因为数据结构元素的关系在计算机内部很大程序上是通过地址或指针建立的
索引存储
在存储数据的同时，建立一个附加的索引表，即索引存储结构=数据文件+索引表
电话号码查询问题:为便于提高查询速度，在存储用户数据文件的同时，建立一张姓氏索引表
散列存储
散列技术是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。
散列法存储的基本思想是:由节点的关键码决定节点的存储位置。散列技术除了可以用于查找外，还可以用于存储
散列是数组存储方式的一种发展，相比数组，散列的数据访问速度要高于数组，因为可以依据存储数据的部分内容找到数据在数组中的存储位置，进而能够快速实现数据的访问，理想的散列访问速度是非常迅速的。
算法
算法是一个有穷规则(或语句，指令)的有序集合
它确定了解决某一问题的一个运算序列。对于问题的初始输入，通过算法有限步的运行，产生一个或多个输出
算法的特点
- 有穷性:算法的执行步骤是有限的
- 确定性:每个计算步骤无二义性
- 可行性:每个计算步骤能够在有限的时间内完成
- 输入:算法有一个或多个外部输出
要说明的是，算法与程序既有联系又有区别。二者都是为了完成某个任务，或解决某个问题而编制的规则(或语句)的有序集合，这是他们的共同点。区别在于:其一，算法与计算机无关，但程序依赖于具体的计算机语言。其二，算法必须是有穷尽的，但程序可能是无穷尽的。其三，算法可能忽略一些语法细节问题，重点放在解决问题的思路上，但程序必须严格遵循相应语言工具的语法。算法转换成程序后才能在计算机上运行。
数据结构是研究从具体问题中抽象出来的数学模型如何在计算机存储器中表示出来;而算法研究的是对数据处理的步骤。如果对问题的数据表示和数据处理都作出了具体的设计，就相当于完成了相应的程序。
算法分析
词句的频度
词句频度定义为可执行语句在算法(或程序)中重复执行的次数，若某语句执行一次时间为t，执行次数为f则该语句所耗时间估计为t*f
示例
float A[n][n],B[n][n],C[n][n];
int j,j,k;
for(i = 0;i < n;i++) // n + 1
{
for(j = 0;j < n;j++) // n * (n + 1)
{
C[n][n] = 0; // n * n
for(k = 0;k < n;k++) // n * n * (n + 1)
{
C[i][j] = C[i][j] + A[i][j] * C[i][j]; // n * n * n
}
}
}时间复杂度
算法的时间复杂度定义为可执行语句的频度之和，记为T(n)。T(n)是算法所需时间的一种估计，其中n为问题的规模(或大小，体积)。
空间复杂度
设算法对应问题的体积(或规模)为n，执行算法所占存储空间的量为D(n)，则D(n)为算法的空间复杂度
算法效能度量
- 算法效率:用依据该算法编制的程序在计算机上执行所消耗的时间来度量。用字母“O”表示其数量级的概念
- 算法中基本操作重复执行的次数是问题规模n的某个函数f(n)
线性表
- 定义:线性表是信息表的一种形式，表中数据元素之间满足线性逻辑关系(或线性结构)，是一种最基本，最简单的数据结构类型
线性表(Linear List)是包含若干数据元素的一个线性序列，记为:L=(a0,...ai-1,ai,ai+1,...an-1)
- 其中:
L为表面，ai(0 <= i <= n-1)为数据元素，n为表长，n大于0时，线性表L为非空表，否则为空表。线性表L可用二元组形式描述:L=(D,R) - 即线性表L包含数据元素集合D和关系集合R。
- 其中:
- 线性表的特征:对非空表，a0是表头，无前驱；an-1是表尾，无后继；其他元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)
运算:设线性表L=(a0,a1,...an-1)
- 建立一个空表:
CreateList(L); - 置空表:
ClearList(L); - 判断表是否为空:
EmptyList(L);，如表为空，返回true，否则返回false - 求表长:
LengthList(L); - 取表中某个元素:
GetList(L,i);，即ai。要求0 <= i <= length(L) - 1 - 定位运算:
LocateList(L,x);，确定元素x在表L中的位置(或序号) - 插入:
InsertList(L,x,i);，将元素x插入表L中的第i个元素ai之前，切表长加1 - 删除:
DeleteList(L,i);删除表L中第i个元素ai，且表长减1，要求0 <= i <= n-1 - 其他:合并，拆分，复制，排序，遍历等
- 建立一个空表:
线性表的存储
线性表作为一种基本数据类型结构，在计算机存储器中的映像(或表示)一般有两种形式，一种是顺序映像，一个是链式映像
线性表的存储结构
若将线性表中的各元素依次存储于计算机一片连续的空间。这种为线性表的顺序存储结构。
- 逻辑上相邻的元素，存储位置上也是相邻的
- 对数据元素ai的存取为随机存取或按地址存取
- 存储密度高。存储密度D=(数据结构中元素所占的存储空间)/(整个数据结构所占空间)
顺序存储结构的不足
- 对表的插入和删除等运算的时间复杂度较差
子c语言中，一维数组的元素也是存放在一片连续的存储空间中，故可借助c语言中一维数组类型来描述线性表的顺序存储结构，即
- 对表的插入和删除等运算的时间复杂度较差
#define MAX // 线性表的最大长度
typedef struct{ // 表的类型
datatype data[MAX]; // 表的存储空间
int last; // 当前表尾指针
}sqlist;*sqlink; // 表说明符如说明sqlink L;L = (sqlink)malloc(sizeof(sqlist))
关于线性表的运算，有些实现起来是相当简单的
置空表
ClearList(L)，令L->last=-1
取表元素
GetList(L,i)，取L->data[i]的值
求表长
Length(L)，取L->last之值加1即可
示例
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "01_lib.h"
#define MAX 20
typedef struct{
int data[MAX];
int last;
}sqlist;
typedef sqlist* sqlink;
sqlink CreateList(void)
{
sqlink l = (sqlink)realloc(NULL,sizeof(sqlist));
l->last = -1;
memset(l->data,0,MAX);
return l;
}
int Length(sqlink L)
{
return L->last + 1;
}
void ClearList(sqlink L)
{
free(L);
}
int EmptyList(sqlink L)
{
return L->last == -1;
}
int FullList(sqlink L)
{
return L->last == (MAX - 1);
}
int GetList(sqlink L,int index)
{
if(index >= 1 || index <= (L->last + 1))
{
return L->data[index - 1];
}
return -1;
}
int LocateList(sqlink L,int value)
{
if(EmptyList(L))
{
return -1;
}
for(int i = 0;i <= L->last;i++)
{
if(L->data[i] == value)
{
return i + 1;
}
}
return -1;
}
void InsertList(sqlink L,int value,int index)
{
if(EmptyList(L) || FullList(L) || index - 1 > L->last)
{
return;
}
for(int i = index - 1;i <= L->last;i++)
{
L->data[i + 1] = L->data[i];
}
L->data[index - 1] = value;
L->last++;
}
void DeleteList(sqlink L,int index)
{
if(EmptyList(L) || FullList(L) || index - 1 > L->last)
{
return;
}
for(int i = index - 1;i < L->last;i++)
{
L->data[i] = L->data[i + 1];
}
L->last--;
}
void PushList(sqlink L,int value)
{
if(FullList(L))
{
return;
}
L->data[++L->last] = value;
}
void PrintList(sqlink L)
{
for(int i = 0;i <= L->last;i++)
{
printf("data[%d] = %d\n",i,L->data[i]);
}
}单向链表
将线性链表L=(a<sub>0</sub>,a<sub>1</sub>,...,a<sub>n-1</sub>)中各元素分布在存储器的不同存储块，称为节点，通过地址或指针建立他们之间的联系，所得到的存储结构为链表结构
- 其中元素ai的节点有由
data和next两部分组成 - 其中，节点的data域存放元素ai，而next域是一个指针，指向ai的直接后继ai + 1所在的节点。于是，线性表L=(a0,a1,...,an-1)的结构
- 示例
#include "03_lib.h"
#include <malloc.h>
int empty(sqlink* L)
{
if(*L == NULL)
{
return 0;
}
return 1;
}
sqlink* CreateList(void)
{
sqlink* L = (sqlink*)malloc(sizeof(sqlink));
*L = NULL;
return L;
}
int Length(sqlink* L)
{
if(empty(L) == 0)
{
return 0;
}
int length = 0;
sqlink l = *L;
while(l->next != NULL)
{
length++;
}
return length;
}
void freeList(sqlink L)
{
if(L->next != NULL)
{
freeList(L->next);
}
free(L);
}
void ClearList(sqlink* L)
{
if(empty(L) == 0)
{
return;
}
freeList(*L);
}
int GetList(sqlink* L,int index)
{
if(empty(L) == 0)
{
return -1;
}
index--;
int i = 0;
sqlink l = *L;
while(l->next != NULL)
{
if(i == index)
{
return l->data;
}
l = l->next;
i++;
}
return -1;
}
int LocateList(sqlink* L,int value)
{
if(empty(L) == 0)
{
return -1;
}
int i = 1;
sqlink l = *L;
while(l->next != NULL);
{
if(l->data == value)
{
return i;
}
i++;
}
return -1;
}
void PushList(sqlink* L,int value)
{
if(empty(L) == 0)
{
*L = (sqlink)malloc(sizeof(sqlist));
(*L)->data = value;
(*L)->next = NULL;
return;
}
sqlink l = *L;
while(1)
{
if(l->next == NULL)
{
l->next = (sqlink)malloc(sizeof(sqlist));
l->next->data = value;
l->next->next = NULL;
return;
}
l = l->next;
}
}
void InsertList(sqlink* L,int value,int index)
{
sqlink l = NULL;
if(index == 1)
{
l = (sqlink)malloc(sizeof(sqlist));
l->data = value;
l->next = *L;
*L = l;
return;
}
int i = 1;
sqlink l1 = *L;
do{
if(index == (i + 1))
{
l = (sqlink)malloc(sizeof(sqlist));
l->data = value;
l->next = l1->next;
l1->next = l;
return;
}
i++;
l1 = l1->next;
}
while(l1->next != NULL);
}
void DeleteList(sqlink* L,int index)
{
if(empty(L) == 0)
{
return;
}
sqlink l = NULL;
if(index == 1)
{
l = (*L)->next;
free(*L);
*L = l;
return;
}
l = *L;
int i = 1;
while(l->next != NULL)
{
if(i == (index - 1))
{
sqlink temp = l->next->next;
free(l->next);
l->next = temp;
}
i++;
}
}
void PrintList(sqlink* L)
{
if(empty(L) == 0)
{
return;
}
sqlink l = *L;
int i = 1;
do
{
printf("data[%d] = %d\n",i,l->data);
l = l->next;
i++;
}
while(l != NULL);
}
void reverse(sqlink* L)
{
if(empty(L) == 0)
{
return;
}
sqlink l = *L,reverse = NULL,last = *L,temp;
do{
temp = l;
l = l->next;
if(reverse == NULL)
{
reverse = temp;
}
else
{
temp->next = reverse;
reverse = temp;
}
}
while(l != NULL);
*L = reverse;
last->next = NULL;
}
void merge(sqlink * L_left,sqlink * L_right)
{
if(empty(L_left) == 0 || empty(L_right) == 0)
{
return;
}
sqlink l = *L_left;
while(l != NULL)
{
if(l->next == NULL)
{
l->next = *L_right;
}
l = l->next;
}
*L_right = *L_left;
}- 约瑟夫环
#include <stdio.h>
#include <malloc.h>
struct node
{
int data;
struct node* pre;
struct node* next;
};
void Joseph_problem(int i,int j,int k);
int main(void)
{
Joseph_problem(7,2,3);
return 0;
}
void Joseph_problem(int i,int j,int k)
{
struct node* L = NULL,* l = NULL;
int a = 1;
for(;a <= i;a++)
{
if(L == NULL)
{
L = (struct node*)malloc(sizeof(struct node));
L->data = a;
l = L;
}
else
{
l->next = (struct node*)malloc(sizeof(struct node));
l->next->data = a;
l->next->pre = l;
l = l->next;
}
}
L->pre = l;
l->next = L;
l = L;
for(a = 1;a <= j;a++)
{
l = l->next;
}
a = 1;
struct node* temp;
while(L->next != L)
{
if(k == a)
{
temp = L->next;
L->next = L->next->next;
L->next->pre = L;
printf("%d\n",temp->data);
free(temp);
a = 1;
}
else
{
a++;
}
L = L->next;
}
printf("%d\n",L->data);
free(L);
}栈
- 定义:栈是限制在一端进行插入操作和删除操作的线性表(俗称堆栈)，允许操作的一端称为栈顶，另一端固定称为栈底，当栈中没有元素时称为空栈。
- 特点:后进先出
- 由于栈也是线性逻辑结构，因此线性表的存储结构对栈也适用，通常栈有顺序链和链栈两种存储结构，这两种存储结构的不同，则实现栈的基本运算的算法也不同。
运算:设S=(a0,a1,...,an-1)
- 构造空栈:
InitStack(S); - 设置空栈:
SetEmpty(S); - 判断是否是空栈:
IsEmpty(S); - 元素进栈:
StackPush(S,x);，可形象的理解为压入，这时栈中会多一个元素 - 元素出栈:
StackPop(S);，可形象的理解为弹出，弹出后栈中就无此元素了 - 读取栈顶元素:
ShowTop(S);，不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变
- 构造空栈:
- 顺序存储
typedef struct node{
int* data;
int top;
} node,* nodep;
nodep InitStack(void)
{
nodep p = malloc(sizeof(node));
p->top = -1;
p->data = NULL;
return p;
}
void SetEmpty(nodep p)
{
free(p->data);
p->top = -1;
p->data = NULL;
}
int IsEmpty(nodep p)
{
if(p->top == -1)
{
return 1;
}
else
{
return 0;
}
}
void StackPush(nodep p,int data)
{
p->data = realloc(p->data,sizeof(int) * (++p->top + 1));
p->data[p->top] = data;
}
int StackPop(nodep p)
{
if(1 == IsEmpty(p))
{
return 0;
}
int data = ShowTop(p);
p->data = realloc(p->data,sizeof(int) * p->top--);
if(p->top == -1)
{
p->data = NULL;
}
return data;
}
int ShowTop(nodep p)
{
if(1 == IsEmpty(p))
{
return 0;
}
return p->data[p->top];
}- 链表存储
typedef struct node{
int data;
struct node* next;
} node,* nodep;
nodep* InitStack(void)
{
nodep* p = (nodep*)malloc(sizeof(nodep));
*p = NULL;
return p;
}
void freeNode(nodep p)
{
if(p->next != NULL)
{
freeNode(p->next);
}
free(p);
}
void SetEmpty(nodep* p)
{
if(IsEmpty(p) == 1)
{
return;
}
freeNode(*p);
}
int IsEmpty(nodep* p)
{
if(*p == NULL)
{
return 1;
}
return 0;
}
void StackPush(nodep* p,int data)
{
nodep temp = (nodep)malloc(sizeof(node));
temp->data = data;
temp->next = *p;
*p = temp;
}
int StackPop(nodep* p)
{
if(IsEmpty(p) == 1)
{
return 0;
}
int data = (*p)->data;
nodep temp = *p;
*p = (*p)->next;
free(temp);
return data;
}
int ShowTop(nodep* p)
{
if(IsEmpty(p) == 1)
{
return 0;
}
return (*p)->data;
队列
- 定义:队列也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端成为队头(Front)，允许插入的一端称为队尾(rear)，当线性表中没有队尾时，称为空队。
- 特点:先进先出
常用基本运算
- 置空队:
SetEmpty(Q); - 判断空队:
IsEmpty(Q); - 判断满队:
IsFull(Q); - 入队:
PushQueue(Q,x) - 出队:
OutQueue(Q); - 取队头:
ShowFront(Q);
- 置空队:
队列顺序存储结构
顺序队列是线性逻辑结构顺序存储的一种，具有和顺序表一样的存储结构，由数组定义，配合用数组下标表示的对头指针和队尾指针(相对指针)完成各种操作
- 规定:头指针
front总是指向队头元素的第一个位置，尾指针rear总是指向队尾元素所在位置的下一个位置 - 在队列操作过程中，为了提高效率，以调整指针代替队列元素的移动，并将数组作为循环队列的操作空间
- 为区别空队和满队，尾指针
rear指向的位置必须为空，满队元素个数比数组元素个数少一个。 - 实例
typedef struct queue
{
int data[MAX_SIZE];
int front;
int rear;
}queue,* queuep;
queuep InitQueue(void)
{
queuep q = (queuep)malloc(sizeof(queue));
SetEmpty(q);
return q;
}
int IsEmpty(queuep q)
{
return (q->front == q->rear) ? 1 : 0;
}
void SetEmpty(queuep q)
{
q->front = 0;
q->rear = 0;
}
int IsFull(queuep q)
{
return (((q->rear + 1) % MAX_SIZE) == q->front) ? 1 : 0;
}
void PushQueue(queuep q,int v)
{
if(IsFull(q) == 1)
{
return;
}
q->data[q->rear] = v;
q->rear = (q->rear + 1) % MAX_SIZE;
}
int OutQueue(queuep q)
{
if(IsEmpty(q) == 1)
{
return -1;
}
int temp = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return temp;
}
int ShowFront(queuep q)
{
if(IsEmpty(q) == 1)
{
return -1;
}
return q->data[q->front];
}链式存储
- 在c语言中，不能用静态分配的一维数组来实现循环队列，若使用循环队列，必须设置最大队列长度，若无法估计最大长度，就使用链式队列。
- 插入操作在队尾进行，删除操作在队头进行，由队头指针和队尾指针控制队列的操作
typedef struct node
{
int data;
struct node* next;
}node,* nodep;
typedef struct queue
{
nodep front;
nodep rear;
}queue,* queuep;
queuep InitQueue(void)
{
queuep q = (queuep)malloc(sizeof(queue));
q->front = NULL;
q->rear = NULL;
return q;
}
int IsEmpty(queuep q)
{
return (q->front == NULL) ? 1 : 0;
}
void SetEmpty(queuep q)
{
nodep n = q->front,temp = NULL;
while(n != NULL)
{
temp = n;
n = n->next;
free(temp);
}
q->front = NULL;
q->rear = NULL;
}
int IsFull(queuep q)
{
return 0;
}
void PushQueue(queuep q,int v)
{
if(q->rear == NULL)
{
q->rear = (nodep)malloc(sizeof(node));
q->front = q->rear;
q->rear->next = NULL;
}
else
{
q->rear->next = (nodep)malloc(sizeof(node));
q->rear->next->next = NULL;
q->rear = q->rear->next;
}
q->rear->data = v;
}
int OutQueue(queuep q)
{
if(IsEmpty(q) == 1)
{
return -1;
}
int n = q->front->data;
nodep temp = q->front;
q->front = q->front->next;
if(q->front == NULL)
{
q->rear = NULL;
}
free(temp);
return n;
}
int ShowFront(queuep q)
{
if(IsEmpty(q) == 1)
{
return -1;
}
return q->front->data;
}树
树(Tree)是n(n>=0)个节点的有限集合，可记为T，满足两个条件
- 有且只有一个特定的称为根(Root)的节点
- 其余的节点可以分为m(m>=0)个互不相交的有限集合T1,T2...Tm，其中每一个集合又是一个树并称为其根的子树
- 表示方法:树形表示法，目录表示法
- 特点:仅有一个根节点，节点间有明显的层次关系
树的基本术语
- 一个节点的子树的个数称为该节点的度数，一棵树的度数是指该树中节点的最大度数
- 度数为0的节点称为树叶或终端节点，度数不为0的节点称为分支节点，除根节点之外的节点称为内部节点
- 一个节点的子树的节点称为该节点的子节点，该节点称为他们的父节点，同一节点的各个子节点之间称为兄弟节点。一个数的根节点没有父节点，叶节点没有子节点
- 节点的层数等于父节点的层数加1，根节点的层数定义为1。树中节点层数的最大值称为该树的高度或深度
- 一个节点k1，k2,...ki,ki+1,...,kj并满足ki是ki+1的父节点，就称为一条从k1到kj的路径，路径的长度为j-1，即路径的边数。路径总前面的节点是后面的节点的祖先，后面节点是前面节点的子孙
- 若树中每个节点的各个子树的排列为从左到右，不能交换，即兄弟之间是有序的，则称该树为有序树，一般的树是有序树
- m(m>=0)颗互不相交的树的集合，称为森林。树去掉根节点就成为森林，森林加上一个新的根节点就称为树
树的逻辑结构
树中任何节点都可以有零个或多个直接后继节点(子节点)，但至多只有一个直接前驱节点(父节点)，根节点没有前驱结点，叶节点没有后继节点。
树的存储结构
树的存储结构可以采用具有多个指针域的多重链表，节点中指针域的个数应由树的度来决定。在实际应用中，这种存储结构很不方便，一般将树转化为二叉树表示法进行处理
二叉树
- 二叉树是一种重要的树形结构。是由n(n>=0)个节点组成的有限集合，他或者是空集(n=0)，或者是由一个根节点以及两颗互不相交的，分别称为左子树和右子树的二叉树组成
- 二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右，左右次序不能颠倒。
基本形态:
- 要点:二叉树结点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确的指出该子树是左子树还是右子树
二叉树的性质
- 二叉树第i(i>=1)层上的节点最多2i-1个
- 深度为k(k>=1)的二叉树最多有2k-1个节点
- 在任意一颗二叉树中，叶子数(度数为0)=度数为2的节点数 + 1
二叉树的形式
- 满二叉树:深度为k(k>=1)且有2k-1个节点的二叉树
完全二叉树:只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。
- 具有n个节点的完全二叉树的深度为(log2n)+1或log2(n+1)
二叉树存储结构
顺序存储结构
- 完全二叉树节点的编号方法是从上到下，从左到右，根节点为一号节点
- 有n个节点的完全二叉树可以用有n+1个元素的数组进行顺序存储，节点号和数组下标一一对应，下表为0的元素不用
- 利用以上特性，可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚结点构成完全二叉树，然后用数组存储，还要浪费一些存储空间
- 一般二叉树必须转换成完全二叉树的形式存储，将造成存储的浪费
- 若父节点在数组中i下标处，其左孩子在2i处，右孩子在2i-1处
链式存储结构
- 每个节点由数据域，左指针域和右指针域组成
typedef struct BiTNode
{
int data;
struct BiTNode *lchilde,*rchild;
}BiTNode,* BiTree;二叉树遍历
- 沿着某条搜索路径周游二叉树，对树中的每一个节点访问一次且仅访问一次
- 是任何类型均有的操作，对线性结构而言，只有一条搜索路径(因为每个节点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个节点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。
- 查找某个节点，或对二叉树中全部节点进行某种处理，就需要遍历
- 由于二叉树的递归性质，遍历算法将采用递归方式
三种基本的遍历方法如下
- 先上(根)后下(子树)的按层次遍历
- 先左(子树)后(子树)的遍历
- 先右(子树)后左(子树)的遍历
遍历的算法
前序遍历(D L R)
- 访问跟节点，按先序遍历左子树，按先序访问右子树
中序遍历(L D R)
- 按中序遍历左子树，访问根节点，按中序遍历右子树
后序遍历(L R D)
- 按后序遍历左子树，按后序遍历右子树，访问根节点
- 二叉树为空时，执行空操作，即空二叉树已遍历完
- 实例
typedef struct BiTNode{
int data;
struct BiTNode *l,*r;
}BiTNode,* BiTree;
BiTree create(void)
{
BiTree tree = NULL;
char c;
if((c = fgetc(stdin)) != '#' && c != '\n')
{
tree = (BiTree)malloc(sizeof(BiTNode));
tree->data = c;
tree->l = create();
tree->r = create();
}
return tree;
}
// 前序
void PerOrder(BiTree tree)
{
printf("%c",tree->data);
if(tree->l != NULL)
{
PerOrder(tree->l);
}
if(tree->r != NULL)
{
PerOrder(tree->r);
}
}
// 中序
void InOrder(BiTree tree)
{
if(tree->l != NULL)
{
InOrder(tree->l);
}
printf("%c",tree->data);
if(tree->r != NULL)
{
InOrder(tree->r);
}
}
// 后序
void PostOrder(BiTree tree)
{
if(tree->l != NULL)
{
PostOrder(tree->l);
}
if(tree->r != NULL)
{
PostOrder(tree->r);
}
printf("%c",tree->data);
}排序
- 将无序的记录序列调整成有序的序列
- 对记录进行排序有着重要的意义。如果记录按key有序，可对其折半查找，使查找效率提高；在数据库(Data Base)和文件库(File Base)等系统中，一般要建立若干索引文件(记录)，就涉及到排序问题；在一些计算机的应用系统中，要按不同的数据做出若干统计，也涉及到排序。排序效率的高低，直接影响到计算机的工作效率。
- 设有n个记录文件f=(R1,R2,...,Rn)，相应记录关键字(key)集合k={k1,k2,...,kn}，若对1,2,3,...,n的一种排列
P(1) P2 P3 (1 <= P(i) <= n,i!=j时，Pi!=Pj)
有:KP(1) <= KP(2) <= ... <= KP(n) 递增
有:KP(1) >= KP(2) >= ... >= KP(n) 递减
则使f按key线性有序:(Rp(1) Rp(2) ... Rp(n))，称这种运算为排序(或分类)，关系符"<="和">="并不一定是数学意义上的"小于等于"或者"大于等于"，而是一种次序关系。但为了讨论问题方便，取整型数作为key，故"<="和">="可以看作通常意义上的符号
- 稳定排序和非稳定排序
设文件f=(R1,R2,...,Ri,...,Rj,...,Rn)中记录Ri Rj(i!=j,i=1...n)的key相等，即Ri=Rj,若在排序前Ri领先于Rj，排序后Ri仍领先于Rj，则称这种排序是稳定的，其含义是没有破坏原本已有序的次序。反之，若排序后Ri和Rj的次序有可能颠倒，则这种排序是非稳定的，即他有可能破坏了原本以有序记录的次序 - 内排序和外排序
若待排文件f在计算机的内部存储器中，且排序过程也在内存中进行，称这种排序为内排序，内排序速度快，但由于内存容量一般很小，文件的长度(记录个数)n受到一定限制。若排序中的文件存入外存储器，排序过程借助于内外数据交换(或归并)来完成，则称这种排序为外排序 内排序的分类
交换法排序
- 冒泡排序
- 快速排序
插入法排序
- 直插排序
- 选择法排序
- 归并法排序
排序的对象
- 顺序结构:类似线性表的顺序存储，将文件f=(R1,R2,...,Rn)存于一片连续的存储空间，逻辑上相连的存储记录在存储器中的物理位置也是相邻的，在这种结构上对文件进行排序，一般要作记录的移动。当发生成片记录移动时，是一个非常耗时的工作
- 链表结构:类似于线性表的链式存储，文件中记录用节点来表示，其物理位置随意，节点之间用指针相连，链表的优点在于排序时无需移动记录，只需修改相应记录的指针即可
- 交换法-冒泡排序
外层循环决
void sort1(sqlink* L)
{
int length = Length(L);
sqlink i_temp = NULL;
for(int i = 0;i < length - 1;i++)
{
i_temp = *L;
// while(l->next != NULL)
for(int j = 0;j < length - i - 1;j++)
{
//printf("%d\n",j);
if(i_temp->data < i_temp->next->data)
{
if(i_temp->pre != NULL)
{
i_temp->pre->next = i_temp->next;
}
if(i_temp->next->next != NULL)
{
i_temp->next->next->pre = i_temp;
}
i_temp->pre = i_temp->next;
i_temp->next = i_temp->next->next;
if(i_temp->pre != NULL)
{
i_temp->pre->next = i_temp;
}
if(j == 0)
{
*L = i_temp->pre;
}
}
else
{
i_temp = i_temp->next;
}
}
}
}- 交换法-快速排序
对冒泡排序的一种改进，目的是提高排序的效率
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
- 示例
void sort2(sqlink* L,sqlink left,sqlink right)
{
sqlink key,left_copy = left,right_copy = right;
int flag_left = 1,flag_right = 1;
while(left != right)
{
while(left != right)
{
if(left->data > right->data)
{
swapSqlink(L,left,right);
key = left;
left = right;
right = key;
if(flag_left == 1)
{
left_copy = left;
if(flag_right == 1)
{
right_copy = right;
}
}
break;
}
else
{
flag_right++;
right = right->pre;
}
}
while(left != right)
{
if(left->data > right->data)
{
swapSqlink(L,left,right);
key = left;
left = right;
right = key;
if(flag_right == 1)
{
right_copy = right;
}
break;
}
else
{
flag_left++;
left = left->next;
}
}
}
// printf("\nleft_copy %d; address = %p\n",left_copy->data,left_copy);
// printf("right_copy %d; address = %p\n",right_copy->data,right_copy);
// printf("right %d; address = %p\n",right->data,right);
// printf("left %d; address = %p\n",left->data,left);
//printf("left->pre %d; address = %p\n",left->pre->data,left->pre);
if(left_copy != left->pre && left->pre != NULL && left != left_copy)
{
sort2(L,left_copy,left->pre);
}
// printf("start %d; address = %p\n",left->data,left);
if(right_copy != right->next && right->next != NULL && right != right_copy)
{
sort2(L,right->next,right_copy);
}
// printf("end\n");
// return left;
}
void swapSqlink(sqlink* L,sqlink left,sqlink right)
{
// PrintList(L);
// printf("\tstart %d %d\n",left->data,right->data);
if(left->pre == NULL)
{
*L = right;
}
if(left->next == right)
{
if(left->pre != NULL)
{
left->pre->next = right;
}
if(right->next != NULL)
{
right->next->pre = left;
}
left->next = right->next;
right->pre = left->pre;
left->pre = right;
right->next = left;
}
else
{
sqlink ll = left->pre,lr = left->next,rl = right->pre,rr = right->next;
if(ll != NULL)
{
ll->next = right;
}
// printf("\tyyy %d %d\n",left->data,right->data);
lr->pre = right;
right->pre = ll;
right->next = lr;
if(rr != NULL)
{
rr->pre = left;
}
rl->next = left;
left->pre = rl;
left->next = rr;
}
// printf("\tend %d %d\n",left->data,right->data);
}- 插入法-直插排序
Last login: Sat Feb 4 08:55:01 2017 from 192.168.1.62
-bash-4.1$ pwd
/home/jin
-bash-4.1$ cd c_test/
-bash-4.1$ cd 19_algorithm/
-bash-4.1$
-bash-4.1$ ls
bin include obj src
-bash-4.1$ vim src/
01.c 02.c 03_lib.c 05.c 06.c 07.c 08_lib.c 09_lib.c 10_lib.c 11_lib.c 12_lib.c
01_lib.c 03.c 04.c 05_lib.c 06_lib.c 08.c 09.c 10.c 11.c 12.c
-bash-4.1$ vim src/.
./ ../
-bash-4.1$ vim src/12
12.c 12_lib.c
-bash-4.1$ vim src/12.c
-bash-4.1$ vim src/12.c
{
new_l_copy->pre->next = old_l;
}
else
{
new_l = old_l;
old_l->pre = NULL;
}
new_l_copy->pre = old_l;
old_l->next = new_l_copy;
new_l_copy = new_l;
break;
}
else if(new_l_copy->next == NULL)
{
new_l_copy->next = old_l;
old_l->next = NULL;
old_l->pre = new_l_copy;
new_l_copy = new_l;
break;
}
new_l_copy = new_l_copy->next;
}
old_l = *l;
}
*l = new_l;
}- 以上案例是基于如下链表的
typedef struct node{
int data;
struct node* next;
struct node* pre;
}sqlist,*sqlink;
int empty(sqlink* L)
{
if(*L == NULL)
{
return 0;
}
return 1;
}
sqlink* CreateList(void)
{
sqlink* L = (sqlink*)malloc(sizeof(sqlink));
*L = NULL;
return L;
}
int Length(sqlink* L)
{
if(empty(L) == 0)
{
return 0;
}
int length = 0;
sqlink l = *L;
while(l != NULL)
{
l = l->next;
length++;
}
return length;
}
void freeList(sqlink L)
{
if(L->next != NULL)
{
freeList(L->next);
}
free(L);
}
void ClearList(sqlink* L)
{
if(empty(L) == 0)
{
return;
}
freeList(*L);
}
sqlink GetList(sqlink* L,int index)
{
if(empty(L) == 0)
{
return NULL;
}
index--;
int i = 0;
sqlink l = *L;
while(l->next != NULL)
{
if(i == index)
{
return l;
}
l = l->next;
i++;
}
return NULL;
}
int LocateList(sqlink* L,int value)
{
if(empty(L) == 0)
{
return -1;
}
int i = 1;
sqlink l = *L;
while(l->next != NULL);
{
if(l->data == value)
{
return i;
}
i++;
}
return -1;
}
void PushList(sqlink* L,int value)
{
if(empty(L) == 0)
{
*L = (sqlink)malloc(sizeof(sqlist));
(*L)->data = value;
(*L)->next = NULL;
(*L)->pre = NULL;
return;
}
sqlink l = *L;
while(1)
{
if(l->next == NULL)
{
l->next = (sqlink)malloc(sizeof(sqlist));
l->next->data = value;
l->next->next = NULL;
l->next->pre = l;
return;
}
l = l->next;
}
}
void InsertList(sqlink* L,int value,int index)
{
if(empty(L) == 0 || index > Length(L))
{
return;
}
sqlink l = NULL;
if(index == 1)
{
l = (sqlink)malloc(sizeof(sqlist));
l->data = value;
l->next = *L;
(*L)->pre = l;
*L = l;
return;
}
int i = 1;
sqlink l1 = *L;
do{
if(index == i)
{
l = (sqlink)malloc(sizeof(sqlist));
l->data = value;
l->pre = l1->pre;
l->next = l1;
l->next->pre = l;
l->pre->next = l;
return;
}
i++;
l1 = l1->next;
}
while(l1 != NULL);
}
void DeleteList(sqlink* L,int index)
{
if(empty(L) == 0)
{
return;
}
sqlink l = NULL;
if(index == 1)
{
l = (*L)->next;
free(*L);
*L = l;
return;
}
l = *L;
int i = 1;
while(l->next != NULL)
{
if(i == (index - 1))
{
sqlink temp = l->next->next;
free(l->next);
l->next = temp;
}
i++;
}
}
void PrintList(sqlink* L)
{
if(empty(L) == 0)
{
return;
}
sqlink l = *L;
int i = 1;
do
{
printf("data[%d] = %d\n",i,l->data);
l = l->next;
i++;
}
while(l != NULL);
}查找
- 顺序查找，就是遍历链表，就不写了
- 二分查找
int BinSearch(sqlink l,int value,int length)
{
int left = 0,right = length,mid = (left + right) / 2,i;
sqlink l_copy = l;
while(left <= right)
{
mid = (left + right) / 2;
l_copy = l;
for(i = 0;i < mid;i++)
{
l_copy = l_copy->next;
}
// printf("%d\n",l_copy->data);
if(l_copy->data > value)
{
left = mid + 1;
}
else if(l_copy->data < value)
{
right = mid - 1;
}
else
{
return 1;
}
}
return -1;
}哈希表
- 又称散列表，杂凑表。在前面讨论的顺序，拆半，分块查找和树表的查找中，其ASL的量级都在O(n)~O(log2n)之间。不论ASL是哪个量级，都与记录长度n有关，随着n的扩大，算法的效率会越来越低。ASL与n有关是因为存储在存储器中的存放是随机的，或者说记录的key与记录的存放地址无关，因而查找只能建立在key的比较基础上。
- 理想的查找是:对给定的k，不经任何比较便能获取所需记录，其查找时间复杂度为常数级O(C)。这叫要求在建立记录表的时候，确定记录的key与其存储地址之间的关系f，即使key与记录的存放地址H相对应
- 或者说记录按key存放
- 之后，当要查找key=k的记录时，通过关系f就可得到响应记录的地址儿获取记录了，从而免去了key的比较过程。这个关系f就是所谓的哈希函数(或称散列函数，杂凑函数)，记为H(key)。它实际上是一个地址映像函数，其自变量为记录的key，函数值为记录的存储地址(或称Hash地址)
- 另外，不同的key可能得到同一个Hash地址，即当key1 != key2时，可能会有H(key1)=H(key2)，此时称key1和key2为同义词。这种现象称为冲突或碰撞，因为一个数据单位只可存放一条记录。
- 一般，选取Hash函数只能做到使冲突尽可能少，却不能完全避免。这就要求在出现冲突后，寻求适当的方法来解决冲突记录的存放问题
例 设记录的key的集合为c语言的一些保留字，则
k={case,char,float,for,int,while,struct,typedef,union,goto,void,return,switch,if,break,continue,else}，构造关于k的Hash表时，可按不同的方法选取H(key)。- 令H1(key)=key[0]-'a'，其中key[0]为key的第一个字符。显然这样选取的Hash函数冲突现象频繁。如:H1(float)=H1(for)='f'-'a'=5。解决冲突的方法之一时为for寻求另一个有效位置。
- 令H2(key)=(key[0]+key[i-1]-2'a')/2。其中key[i-1]为key的最后一个字符。如:H2(float)=('f'+'t'-2'a')/2=12，H2(for)=('f'+'r'-2*'a')/2=11，从而消除了一些冲突的发生，但仍无法完全避免，如:H2(case)=H2(continue)
综上所述，对Hash表的含义描述如下
- 根据选取的hash函数H(key)和处理冲突的方法，将一组记录(R1 R2 R3 ...)映射到记录的存储空间，所得到的记录表称为Hash表
- 关于Hash表的讨论关键时两个问题，一是选取Hash函数的方法；二是确定解决冲突的方法
选取(或构造)Hash函数的方法很多，原则是尽可能将记录均匀分布，以减少冲突现象发生。以下是几种常用的构造方法
直接地址法
- 直接取key的某个线性函数为hash函数，即令:
H(key)=a*key+b，其中a，b为常数，此时称H(key)为直接hash函数或自身函数
- 直接取key的某个线性函数为hash函数，即令:
数字分析法
- 分析数据的规律，取数据中的部分进行hash
- 平方取中法
- 保留除数法
- 根据实际情况，数据的规律，选取(或构造)Hash函数的方法