Notebook online

数据结构

 计算机基础知识

线性表

线性表的基本概念与实现

线性表的定义

线性表是具有相同特性数据元素的一个有限序列

线性表的存储结构

线性表的存储结构有顺序存储结构和链式存储结构两种。前者称为顺序表，后者称为链表

  • 顺序表
    顺序表就是把线性表中的所有元素按照其逻辑顺序，依次存储到从指定的存储位置开始的一块连续的存储空间中。线性表中第一个元素的存储位置就是指定的存储位置，第i+1个元素的存储位置紧接在第i个元素的存储位置的后面
  • 链表
    在链表存储中，每个结点不仅包含所存元素的信息，还包含元素之间逻辑关系的信息，如单链表中前驱结点包含了后继结点的地址信息，这样就可以通过前驱结点中的地址信息找到后继结点的位置。

链表有以下5种形式

  1. 单链表
    在每个结点中除了包含数据域外，还包含一个指针域，用以指向其后继结点。 1 ①带头结点的单链表中，头指针head指向头结点，头结点的值域不含任何信息，从头结点的后继结点开始存储数据信息。头指针head始终不等于NULL，当head->next 等于NULL时，链表为空。
    ②不带头结点的单链表中的头指针head直接指向开始结点，即图中的结点A1，当head等于NULL时，链表为空。

总之，两者最明显的区别是，带头结点的单链表中有一个结点不存储信息（仅存储一些描述链表属性的信息，如表长)，只是作为标志，而不带头结点的单链表的所有结点都存储信息。

  1. 双链表 双链表就是在单链表结点上增添了一个指针域，指向当前结点的前驱。这样就可以方便地由其后继来找到其前驱，从而实现输出从终端结点到开始结点的数据序列。 1 同样，双链表也分为带头结点的双链表和不带头结点的双链表，情况类似于单链表。带头结点的双链表，当head->next为NULL时，链表为空;不带头结点的双链表，当head为NULL时，链表为空。

  2. 循环单链表
    将单链表的最后一个指针域(空指针）指向链表中的第一个结点即可 1 带头结点的循环单链表，当head等于head->next时，链表为空；不带头结点的循环单链表，当head等于NULL时，链表为空。

  3. 循环双链表
    将终端结点的next指针指向链表中的第一个结点，将链表中第一个结点的 prior指针指向终端结点。
    当head等于NULL时，不带头结点的循环双链表为空。带头结点的循环双链表中是没有空指针的，其空状态下，head->next和 head->prior必然都等于head。所以判断其是否为空，只需要检查head->next和 head->prior两个指针中的任意一个是否等于head指针即可。因此，以下四句代码中的任意-句为真，都可以判断循环双链表为空。

head->next == head;
head->prior == head;
head->next == head && head->prior == head;
head->next == head || head->prior == head;

1 5) 静态链表
静态链表借助一维数组来表示 1 左图是静态链表，右图是其对应的一般链表。一般链表结点空间来自于整个内存，静态链表则来自于一个结构体数组。数组中的每一个结点含有两个分量:一个是数据元素分量 data;另一个是指针分量,指示了当前结点的直接后继结点在数组中的位置(这和一般链表中next指针的地位是同等的)。

顺序表和链表的比较

(1) 基于空间的比较

  1. 存储分配的方式:顺序表的存储空间是一次性分配的，链表的存储空间是多次分配的。
  2. 存储密度（存储密度=结点值域所占的存储量/结点结构所占的存储总章-顺序表的存储密度=1，链表的存储密度<1（因为结点中有指针域)。

(2) 基于时间的比较

  1. 存取方式: 顺序表可以随机存取，也可以顺序存取（对于顺序表，一般只答随机存取即可);链表只能顺序存取（所谓顺序存取，以读取为例，要读取某个元素必须遍历其之前的所有元素才能找到并读取它)
  2. 插入/删除时移动元素的个数:顺序表平均需要移动近一半元素;链表不需要移动元素，只需要修改指针。

线性表的结构体定义和基本操作

线性表的结构体定义

  1. 顺序表的结构体定义
typedef struct
{
    intdata [maxsize];//存放顺序表元素的数组(默认是int型,可根据题目要求将int换成其他类型)
    int length;//存放顺序表的长度

}Sqlist;//顺序表类型的定义

用的最多的是这种定义

int A[maxSize];
int n;
  1. 单链表结点定义
typedef struct LNode
{
    int data;//data中存放结点数据域(默认是int型)
    struct LNode *next;//指向后继结点的指针
}LNode;//定义单链表结点类型

1

  1. 双链表结点定义
typedef struct DLNode
{
    int data;//data中存放结点数据域(默认是 int型)
    struct DLNode *prior;//指向前驱结点的指针
    struct DLNode *next;//指向后继结点的指针
}DLNode;//定义双链表结点类型

1

说明:结点是内存中一片由用户分配的存储空间，只有一个地址来表示它的存在，没有显式的名称，因此我们会在分配链表结点空间时定义一个指针，来存储这片空间的地址（这个过程通俗地讲叫指针指向结点)，并且常用这个指针的名称来作为结点的名称。

顺序表的操作

【例1】己知一个顺序表L，其中的元素递增有序排列，设计一个算法，插入一个元素x(x为 int型）后保持该顺序表仍然递增有序排列(假设插入操作总能成功)

分析:
由题干可知，解决本题需完成两个操作:

  1. 找出可以让顺序表保持有序的插入位置。
  2. 将步骤1)中找出的位置上以及其后的元素往后移动一个位置，然后将x放至腾出的位置上。

操作一:因为顺序表L中的元素是递增排列的，所以可以从小到大逐个扫描表中元素，当找到第一个比x大的元素时,将插在这个元素之前即可。

int findElem (Sqlist L, int x)
{
    int i;
    for(i=0;i<L.length;++i)
    {
        if(x<L.data[i]>) //对顺序表中的元素从小到大逐个进行判断,看x是否小于当前所扫描到的元素,如果小于则返回当前位置i
        {
            return i;
        }
    }
    return i;//如果顺序表中不存在比×大的元素,则应将x插入表尾元素之后,返回i来标记这种情况(因i<L.length这一句不成立而退出for循环后,i正好指示了表尾元素之后的位置,同样也是正确的插入位置)
}

操作二:找到插入位置之后,将插入位置及其以后的元素向后移动一个元素的位置即可。

void insertElem (Sqlist &L,int x)
{
    int p,i;
    p=findElem(L,x);
    for(i=L.length-1;i>=p;--i)
    {
        L.data[i+1]=L.data[i];//从右往左,逐个将元素右移一个位置
    }
    L.data[p]=x;//将×放在插入位置p上
    ++ (L.length);//表内元素多了一个,因此表长自增1
}

【例2】删除顺序表L中下标为p (0≤p≤length-1)的元素，成功返回1，否则返回0，并将被删除元素的值赋给e

分析：
要删除表中下标为p的元素，只需将其后边的元素逐个往前移动一个位置，将p位置上的元素覆盖掉，就达到了删除的目的。

int deleteElem (Sqlist &L, int p, int &e)
{
    int i;
    if(p<0||p>L.length-1)
    {
        return 0;
    }
    e=L.data[p];//将被删除元素赋值给e
    for(i=p;i<L.length-1;++i)//从p位置开始,将其后边的元素逐个前移一个位置
    {
        L.data[i]=L.data[i+1];
    }
    -- (L.length);
    return 1;
}

单链表的操作

【例3】A和B是两个单链表（带表头结点)，其中元素递增有序。设计一个算法，将A和B归并成一个按元素值非递减有序的链表C，C由A和B中的结点组成

分析： 已知A、B中的元素递增有序，要使归并后的C中元素依然有序，可以从A、B中挑出最小的元素插入C的尾部，这样当A、B中的所有元素都插入C中时，C一定是递增有序的。由于A、B是递增的，因此A中的最小元素是其开始结点中的元素，B也一样。只需从A、B的开始结点中选出一个较小的来插入C的尾部即可。这里还需注意，A与B中的元素有可能一个已经全部被插入到C中，另一个还没有插完，如A中所有元素已经全部插入到C中，而B还没有插完，这说明B中的所有元素都大于C中的元素，因此只要将B链接到C的尾部即可。如果A没有插完，则用类似的方法来解决。

void merge (LNode *A, LNode *B, LNode *&C)
{
    LNode *p = A->next;
    LNode *q = B->next;
    LNode *r;
    C=A;
    C->next=NULL;
    free(B);
    r=C;
    while(p!=NULL&&q!=NULL)
    {
        if(p->data<=q->data)
        {
            r->next=p;
            p=p->next;
            r=r->next;
        }
        else
        {
            r->next=q;
            q=q->next;
            r=r->next;
        }
    }
    r->next=NULL;
    if(p!=NULL) r->next=p;
    if(q!=NULL) r->next=q;
}

尾插法

void createlistR (LNode *&C, int a[], int n)
{
    LNode *s, *r;
    int i;
    C=(LNode *)malloc(sizeof(LNode));
    C->next=NULL;
    r=C;
    for(i=0;i<n;++i)
    {
        s=(LNode *)malloc(sizeof(LNode));
        s->data=a[i];
        r->next=s;
        r=r->next;
    }
    r->next=NULL;
}

头插法

void createlistF (LNode *&C, int a[], int n)
{
    LNode *s;
    int i;
    C=(LNode *)malloc(sizeof(LNode));
    C->next=NULL;
    for(i=0;i<n;++i)
    {
        s=(LNode *)malloc(sizeof(LNode));
        s->data=a[i];
        s->next=C->next;
        C->next=s;
    }
}

【例4】查找链表C(带头结点)中是否存在一个值为x的结点，若存在，则删除该结点并返回1,否则返回0

分析：
对于本题需要解决两个问题:一个是要找到值为×的结点，另一个是将找到的结点删除。第一个问题引出了本章要讲的单链表中最后-一个重要操作一―链表中结点的查找。为了实现查找，定义一个结点指针变量p，让它沿着链表一直走到表尾，每遇到一个新结点就检测其值是否为x，是则证明找到，不是则继续检测下一个结点。当找到值为x的结点后删除该结点。

int findAndDelete (LNode *C, int x)
{
    LNode *p, *q;
    p=C;
    while(p->next!=NULL)
    {
        if(p->next->data==x)
        {
            break;
        }
        p=p->next;
    }
    if(p->next=NULL)
    {
        return 0;
    }
    else 
    {
        q=p->next;
        p->next=p->next->next;
        free(q);
        return 1;
    }
}

双链表的操作

  1. 采用尾插法建立双链表
void createDlistR(DLNode *&L, int a[], int n)
{
    DLNode *s,*r;
    int i;
    L=(DLNode*)malloc(sizeof(DLNode));
    L->prior=NULL;
    L->next=NULL;
    r=L;
    for(i=0;i<n;++i)
    {
        s=(DLNode*)malloc(sizeof(DLNode));
        s->data=a[i];

        r->next=s;
        s->prior=r;
        r=s;
    }
    r->next=NULL;
}
  1. 查找结点的算法
DLNode *findNode(DLNode *C, int x)
{
    DLNode *p=C->next;
    while(p!=NULL)
    {
        if(p->data==x)
        {
            break;
        }
        p=p->next;
    }
    return p;
}
  1. 插入结点的算法
s->next=p->next;
s->prior=p;
p->next=s;
s->next->prior=s;
  1. 删除结点的算法
q=p->next;
p->next=q->next;
q->next->prior=p;
free(q);

逆置问题

【例5】
(1) 将一长度为n的数组的前端k(k<n)个元素逆序后移动到数组后端，要求原数组中数据不丢失，其余元素的位置无关紧要。
(2) 将一长度为n的数组的前端k(k<n)个元素保持原序移动到数组后端，要求原数组中数据不丢失，其余元素的位置无关紧要。
(3) 将数组中的元素（X0，X1，…，Xn-1)，经过移动后变为(Xp，Xp+1，…，Xn-1,X0，X1，…,Xp-i)，即循环左移p(0<p<n)个位置。

分析： (1) 只需要逆置整个数组，即可满足前端k个元素逆序后放到数组的后端

void reverse(int a[], int left, int right, int k)
{
    int temp;
    for (int i=left,j=right;i<left+k && i<j;++i,--j)
    {
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}

(2) 只需要将前端k个元素逆置，然后将整个数组逆置，即可满足前端k个元素保持原序放到数组的后端

void moveToEnd (int a[], int n, int k)
{
    reverse(a,0,k-1,k);
    reverse(a,0,n-1,k);
}

(3) 只需要将0~p-1位置的元素逆置，再将p~n-1位置的元素逆置，然后将整个数组逆置即可

void moveP (int a[], int n, int p)
{
    reverse(a,0,p-1,p);
    reverse(a,p,n-1,n-p);
    reverse(a,0,n-1,n); 
}

栈和队列

栈和队列的基本概念

栈的基本概念

  1. 栈的定义
    栈是一种只能在一端进行插入或删除操作的线性表。其中允许进行插入或删除操作的一端称为栈顶(Top)。表的另一端称为栈底，栈底是固定不变的。栈的插入和删除操作一般称为入栈和出栈。
  2. 栈的特点
    由栈的定义可以看出，栈的主要特点是先进后出（FILO)。
  3. 栈的存储结构
    可用顺序表和链表来存储栈，依照存储结构分为两种:顺序栈和链式栈。

队列的基本概念

  1. 队列的定义
    队列简称队，它也是一种操作受限的线性表，其限制为仅允许在表的一端进行插入，在表的另一端进行删除。可进行插入的一端称为队尾(Rear)，可进行删除的一端称为队头（Front)。向队列中插入新的元素称为进队，新元素进队后就成为新的队尾元素;从队列中删除元素称为出队，元素出队后，其后继元素就成为新的队头元素。
  2. 队列的特点
    队列的特点概括起来就是先进先出（FIFO)。
  3. 队列的存储结构
    可用顺序表和链表来存储队列，队列按存储结构可分为顺序队和链队两种。

栈和队列的存储结构、算法与应用

结构体定义

  1. 顺序栈定义
typedef struct
{
    int data[maxSize];
    int top;
}SqStack;
  1. 链栈结点定义
typedef struct LNode
{
    int data;
    struct LNode *next;
}
  1. 顺序队列定义
typedef struct
{
    int data[maxSize];
    int front;
    int rear;
}SqQueue;
  1. 链队定义 (1) 队结点类型定义
typedef struct QNode
{
    int data;
    struct QNode *next;
}QNode;

(2) 链队类型定义

typedef struct
{
    QNode *front;
    QNode *rear;
}LiQueue;

顺序栈

  1. 顺序栈的要素 (1)状态
  • 栈空状态
    st.top==-1
  • 栈满状态
    st.top==maxSize-1
  • 非法状态
    上溢和下溢 (2)操作
  • 进栈操作：++(st.top);st.data[st.top]=x;
  • 出栈操作：x=st.data[st.top]; --(st.top);
  1. 初始化栈的代码
void initStack(SqStack &st)
{
    st.top==-1;
}
  1. 判断栈空代码
int isEmpty(SqStack st)
{
    if(st.top==-1)
    {
        return 1;
    }
    else {
        return 0;
    }
}
  1. 进栈代码
int push(SqStack &st, int x)
{
    if(st.top==maxSize-1)
        return 0;
    ++(st.top);
    st.data[st.top]=x;
        return 1;
}
  1. 出栈代码
int pop(SqStack &st, int &x)
{
    if(st.top==-1)
        return 0;
    x=st.data[st.top];
    --(st.top);
        return 1;
}

链栈

  1. 链栈的要素 (1)状态
  • 栈空状态
    lst->next==NULL (2)操作
  • 进栈操作
p->next=lst->next;
lst->next=p;
  • 出栈操作
p=lst->next;
x=p->data;
lst->next=p->next;
free(p);
  1. 链栈的初始化代码
void initStack(LNode *&lst)
{
    lst=(LNode*)malloc(sizeof(LNode));
    lst->next=NULL;
}
  1. 判断栈空代码
int isEmpty(LNode *lst)
{
    if(lst->next==NULL)
    {
        return 1;
    }
    else 
        return 0;
}
  1. 进栈代码
void push(LNode *lst, int x)
{
    LNode *p;
    p=(LNode*)malloc(sizeof(LNode));
    p->next=NULL;

    p->data=x;
    p->next=lst->next;
    lst->next=p;
}
  1. 出栈代码
int pop(LNode *lst, int &x)
{
    LNode *p;
    if(lst->next==NULL)
        return 0;
    p=lst->next;
    x=p->data;
    lst->next=p->next;
    free(p);
    return 1;
}

栈的应用

  1. 顺序栈的应用

【例1】C语言里算术表达式中的括号只有小括号。编写算法，判断一个表达式中的括号是否正确配对，表达式已经存入字符数组exp[]中，表达式中的字符个数为n。

int match(char exp[], int n)
{
    char stack[maxSize];
    int top=-1;
    int i;
    for(i=0;i<n;++i)
    {
        if(exp[i]=='('){
            stack[++top]='(';
        }
        if(exp[i]==')')
        {
            if(top==-1){
                return 0;
            }
            else {
                --top;
            }
        }
    }
        if(top==-1){
            return 1;
        }
        else {
            return 0;
        }
}

【例2】编写一个函数，求后缀式的数值，其中后缀式存于一个字符数组 exp中，exp中最后一个字符为“10”，作为结束符，并且假设后缀式中的数字都只有一位。

执行过程:当遇到数值时入栈，当遇到运算符时，连续两次出栈，将两个出栈元素结合运算符进行运算，将结果作为新遇到的数值入栈。如此往复，直到扫描到终止符“10”。此时栈底元素值即为表达式的值。

int op(int a,char Op,int b)
{
    if(Op=='+') return a+b;
    if(Op=='-') return a-b;
    if(Op=='*') return a*b;
    if(Op=='/')
    {
        if(b==0)
        {
            cout<<"ERROR"<<endl;
            return 0;
        }
    }
}
int com(char exp[])
{
    int i,a,b,c;
    int stack[maxSize];
    int top=-1;
    char Op;
    for(i=0;exp[i]!='\0';++i)
    {
        if(exp[i]>='0'&&exp[i]<='9')

            stack[++top]=exp[i]-'0';
        else
        {
            Op=exp[i];
            b=stack[top--];
            a=stack[top--];
            c=op(a,op,b);
            stack[++top]=c;
        }
    }
    return stack[top];
}
  1. 链栈的应用

【例3-3】用不带头结点的单链表存储链栈，设计初始化栈、判断栈是否为空、进栈和出栈等相应的算法。

分析：
不带头结点的单链表lst为空的条件是lst==NULL，进栈和出栈操作都是在表头进行的

void initStackl(LNode *&lst)
{
    lst=NULL;
}
int isEmptyl(LNode *lst)
{
    if(lst==NULL)
        return 1;
    else 
        return 0;
}
void pushl(LNode *&lst, int x)
{
    LNode *p;
    p=(LNode *)malloc(sizeof(LNode));
    p->next=NULL;
    p->data=x;
    p->next=lst;
    lst=p;
}
int popl(LNode *&lst,int &x)
{
    LNode *p;
    if(lst==NULL)
        return 0;
    p=lst;
    x=p->data;
    lst=p->next;
    free(p);
    return 1;   
}

顺序队

  1. 循环队列

在顺序队中,通常让队尾指针rear 指向刚进队的元素位置,让队首指针front 指向刚出队的元素位置。因此，元素进队时，rear要向后移动;元素出队时，front 也要向后移动。这样经过一系列的出队和进队操作以后,两个指针最终会到达数组末端maxSize-1处。虽然队中已经没有元素，但仍然无法让元素进队，这就是所谓的“假溢出”。要解决这个问题，可以把数组弄成一个环,让 rear和 front沿着环走，这样就永远不会出现两者来到数组尽头无法继续往下走的情况，这样就产生了循环队列。循环队列是改进的顺序队列。

front=(front+1)%maxSize

  1. 循环队列的要素

(1)两个状态

  • 队空状态：qu.rear==qu.front
  • 队满状态：(qu.rear+1)%maxSize==qu.front (2)两个操作
  • 元素x进队操作
qu.rear=(qu.rear+1)%maxSize;
qu.data[qu.rear]=x;
  • 元素x出队操作
qu.front=(qu.front+1)%maxSize;
x=qu.data[qu.front];
  1. 初始化队列算法
void initQueue (SqQueue &qu)
{
    qu.front=qu.rear=0;
}
  1. 判断队空算法
int isEmpty(SqQueue qu)
{
    if(qu.front==qu.rear)
        return 1;
    else 
        return 0;
}
  1. 进队算法
int enQueue(SqQueue &qu, int x)
{
    if((qu.rear+1)%maxSize==qu.front)
        return 0;
    qu.rear=(qu.rear+1)%maxSize;
    qu.data[qu.rear]=x;
    return 1;
}
  1. 出队算法
int deQueue(SqQueue &qu, int x)
{
    if(qu.front==qu.rear)
        return 0;
    qu.front=(qu.front+1)%maxSize;
    x=qu.data[qu.front];
    return 1;
}

链队

  1. 链队的要素
  • 队空状态
lqu->rear==NULL 
lqu->front==NULL

元素进队操作

lqu->rear->next=p;
lqu->rear=p;

元素出队操作

p=lqu->front;
lqu->front=p->next;
x=p->data;
free(p);
  1. 初始化链队算法
void initQueue (LiQueue *&lqu)
{
    lqu=(LiQueue*)malloc(sizeof(LiQueue));
    lqu->front=lqu->rear=NULL;
}
  1. 判断队空算法
int isQueueEmpty(LiQueue *lqu)
{
    if(lqu->rear==NULLl11qu->front==NULL)
        return 1;
    else 
        return 0;
}
  1. 进队算法
void enQueue(LiQueue *lqu, int x)
{
    QNode *p;
    P=(QNode*)malloc(sizeof(QNode));
    p->data=x;
    p->next=NULL;
    if(lqu->rear==NULL)
        lqu->front=lqu->rear=p;
    else
    {
        lqu->rear->next=p;
        lqu->rear=p;
    }
}
  1. 出队算法
int deQueue(LiQueue *lqu,int &x)
{
    QNode *p;
    if(lqu->rear==NULL)
        return 0;
    else
        p=lqu->front;
    if(lqu->front==lqu->rear)
        lqu->front=lqu->rear=NULL;
    else
        lqu->front=lqu->front->next;
    x=p->data;
    free (p);
    return 1;
}

串

串数据类型的定义

串的定义

串是由零个或者多个字符组成的有限序列。串中字符的个数称为串的长度，含有零个元素的串叫空串

串的存储结构

  1. 定长顺序存储表示
  2. 变长分配存储表示

串的基本操作

  1. 赋值操作
  2. 取串长度操作
  3. 串比较操作
  4. 串连接操作
  5. 求字串操作
  6. 串清空操作

串的模式匹配算法

简单模式匹配算法

对一个串中某子串的定位操作称为串的模式匹配，其中待定位的子串称为模式串。算法的基本思想:从主串的第一个位置起和模式串的第一个字符开始比较，如果相等，则继续逐一比较后续字符;否则从主串的第二个字符开始，再重新用上一步的方法与模式串中的字符做比较，以此类推，直到比较完模式串中的所有字符。若匹配成功，则返回模式串在主串中的位置;若匹配不成功，则返回一个可区别于主串所有位置的标记，如“0”。

int index(Str str,Str substr)
{
    int i=1,j=1,k=i;
    while(i<=str.length && j<=substr.length)
    {
        if(str.ch[i]==substr.ch[j])
        {
            ++i;
            ++j;
        }
        else 
        {
            j=1;
            i=++k;
        }
    }
    if(j>substr.length)
        return k;
    else return 0;
}

KMP算法

KMP算法的改进

树与二叉树

树的基本概念

树的定义

树是一种非线性的数据结构。

树的基本用语

1 结点:A、B、C等都是结点，结点不仅包含数据元素，而且包含指向子树的分支。例如，A结点不仅包含数据元素A，而且包含3个指向子树的指针。
结点的度:结点拥有的子树个数或者分支的个数。例如，A结点有3棵子树，所以A结点的度为3。树的度:树中各结点度的最大值。如例子中结点度最大为3(A、D结点)，最小为0(F、G、I、J、K、L、M结点)，所以树的度为3。
叶子结点:又叫作终端结点，指度为0的结点，如F、G、1、J、K、L、M结点都是叶子结点。非终端结点:又叫作分支结点，指度不为0的结点，如A、B、C、D、E、H结点都是非终端结点。除了根结点之外的非终端结点，也叫作内部结点，如B、C、D、E、H结点都是内部结点。
孩子:结点的子树的根，如A结点的孩子为B、C、D。
双亲:与孩子的定义对应，如B、C、D结点的双亲都是A。
兄弟:同一个双亲的孩子之间互为兄弟。如B、C、D互为兄弟，因为它们都是A结点的孩子。祖先:从根到某结点的路径上的所有结点，都是这个结点的祖先。如K的祖先是A、B、E，因为从A到K的路径为A一B-E─K。
子孙:以某结点为根的子树中的所有结点，都是该结点的子孙。如D的子孙为H、I、J、M.层次:从根开始，根为第一层，根的孩子为第二层，根的孩子的孩子为第三层，以此类推。树的高度(或者深度):树中结点的最大层次。如例子中的树共有4层，所以高度为4。结点的深度和高度:
1）结点的深度是从根结点到该结点路径上的结点个数。
2）从某结点往下走可能到达多个叶子结点，对应了多条通往这些叶子结点的路径，其中最长的那条路径上结点的个数即为该结点在树中的高度,如结点D的高度为3,就是从D到M的路径上的结点个数。
3）根结点的高度为树的高度，如结点A，其高度为4，是从A到K（L、M）这条路径上结点的个数，也是整棵树的高度。
堂兄弟:双亲在同一层的结点互为堂兄弟。如G和H互为堂兄弟，因为G的双亲是C，H的双亲是D，C和D在同一层上。注意和兄弟的概念的区分。
有序树:树中结点的子树从左到右是有次序的，不能交换，这样的树叫作有序树。无序树:树中结点的子树没有顺序，可以任意交换，这样的树叫作无序树。
丰满树:丰满树即理想平衡树，要求除最底层外，其他层都是满的。
森林:若干棵互不相交的树的集合。例子中如果把根A去掉，剩下的3棵子树互不相交，它们组成一个森林。

树的存储结构

  1. 顺序存储结构 1
  2. 链式存储结构

二叉树

二叉树的定义

在理解了树的定义之后，二叉树的定义也就很好理解了。将一般的树加上如下两个限制条件就得到了二叉树。

  1. 每个结点最多只有两棵子树，即二叉树中结点的度只能为0、1、2。
  2. 子树有左右顺序之分，不能颠倒。

根据二叉树的定义可知，二叉树共有5种基本形态。 1

在一棵二叉树中，如果所有的分支结点都有左孩子和右孩子结点，并且叶子结点都集中在二叉树的最下一层，则这样的二叉树称为满二叉树。

如果对一棵深度为k、有n个结点的二叉树进行编号后，各结点的编号与深度为k的满二叉树中相同位置上的结点的编号均相同，那么这棵二叉树就是一棵完全二叉树。

二叉树的主要性质

性质1:非空二叉树上叶子结点数等于双分支结点数加1。

证明:设二叉树上叶子结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数为n0+n1+n2。在一棵二叉树中，所有结点的分支数等于单分支结点数加上双分支结点数的两倍，即总的分支数为n1+2n2。

由于二叉树中除根结点之外，每个结点都有唯一的一个分支指向它，因此二叉树中有总分支数=总结点数-1（显然这一条结论对于任何树都是适用的，而不仅仅是针对二叉树)。

由此可得: n0+n1+n2-1=n1+2n2
化简得:n0=n2+1

Q:二叉树中总的结点数为n，则树中空指针的个数是多少?
A:可以将所有的空指针看作叶子结点，则树中原有的所有结点都成了双分支结点。因此可得空指针的个数为树中所有结点个数加1，即 n+1个。

总结点数=n0+n1+n2+...+nm
总分支数=1×n1+2×n2+...+m×nm(度为m的结点引出m条分支)
总分支数=总结点数-1

性质2:二叉树的第i层上最多有2i-1(i≥1)个结点。

性质3:高度（或深度）为k的二叉树最多有2k-1(k≥1)个结点。

二叉树的存储结构

  1. 顺序存储结构

顺序存储结构即用一个数组来存储一棵二叉树，这种存储方式最适合于完全二叉树，用于存储一般二叉树会浪费大量的存储空间。将完全二叉树中的结点值按编号依次存入一个一维数组中，即完成了一棵二叉树的顺序存储。 1 2. 链式存储结构

其中，data表示数据域，用于存储对应的数据元素；lchild和 rchild分别表示左指针域和右指针域,分别用于存储左孩子结点和右孩子结点的位置。 1

二叉树的遍历算法

  1. 先序遍历
void preorder (BTNode *p)
{
    if(p!=NULL)
    {
        visit(p);
        preorder(p->lchild);
        preorder(p->rchild);
    }
}
  1. 中序遍历
void inorder (BTNode *p)
{
    if(p!=NULL)
    {
        inorder(p->lchild);
        visit(p);
        inorder(p->rchild);
    }
}
  1. 后序遍历
void postorder (BTNode *p)
{
    if(p!=NULL)
    {
        postorder(p->lchild);
        postorder(p->rchild);
        visit(p);
    }
}

二叉树遍历算法的改进

  1. 二叉树深度优先遍历算法的非递归实现
//先序遍历非递归算法
void preorderNonrecursion(BTNode *bt)
{
    if(bt!=NULL)
    {
        BTNode *Stack[maxSize];
        int top=-1;
        BTNode *p;
        Stack[++top]=bt;
        while(top!=-1)
        {
            p=Stack[top--];
            visit(p);
            if(p->rchild!=NULL)
                Stack[++top]=p->rchild;
            if(p->lchild!=NULL)
                Stack[++top]=p->lchild;
        }
    }
}
//中序遍历非递归算法
void inorderNonrecursion(BTNode *bt)
{
    if(bt!=NULL)
    {
        BTNode *Stack[maxSize];
        int top=-1;
        BTNode *p;
        p=bt;
        while(top!=-1||p!=NULL)
        {
            while(p!=NULL)
            {
                Stack[++top]=p;
                p=p->lchild;
            }
            if(top!=-1)
            {
                p=Stack[top--];
                visit(p);
                p=p->rchild;
            }
        }
    }
}
//后序遍历非递归算法
void postorderNonrecursion(BTNode *bt)
{
    if(bt!=NULL)
    {
        BTNode *Stack1[maxSize];
        int top1=-1;
        BTNode *Stack2[maxSize];
        int top2=-1;
        BTNode *p=NULL;
        Stack[++top1]=bt;
        while(top1!=-1)
        {
            p=Stack[top1--];
            Stack[++top2]=p;
            if(p->lchild!=NULL)
               Stack1[++top1]=p->lchild;
            if(p->rchild!=NULL)
               Stack1[++top1]=p->rchild;
        }
        while(top2!=-1)
        {
            p=Stack2[top2--];
            visit(p);
        }
    }
}
  1. 线索二叉树

线索二叉树可以分为前序线索二叉树、中序线索二叉树和后序线索二叉树。对一棵二叉树中所有结点的空指针域按照某种遍历方式加线索的过程叫作线索化,被线索化了的二叉树称为线索二叉树。 1

void InThread(TBTNode *p, TBTNode *&pre)
{
    if(p!=NULL)
    {
        InThread(p->lchild,pre);
        if(p->lchild==NULL)
        {
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL&&pre->rchild==NULL)
        {
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;
        p=p->rchild;
        InThread(p,pre);
    }
}

树与二叉树的应用

赫夫曼树和赫夫曼编码

  • 与赫夫曼树相关的一些概念
    赫夫曼树又叫作最优二叉树，它的特点是带权路径最短。首先需要说明几个关于路径的概念。
  1. 路径:路径是指从树中一个结点到另一个结点的分支所构成的路线。
  2. 路径长度:路径长度是指路径上的分支数目。
  3. 树的路径长度:树的路径长度是指从根到每个结点的路径长度之和。
  4. 带权路径长度:结点具有权值，从该结点到根之间的路径长度乘以结点的权值，就是该结点的带又路径长度。
  5. 树的带权路径长度(WPL):树的带权路径长度是指树中斤有叶子结点的带权路径长度之和。
  • 赫夫曼树的构造方法
    给定n个权值，用这n个权值来构造赫夫曼树的算法描述如下:
  1. 将这n个权值分别看作只有根结点的n棵二叉树，这些二叉树构成的集合记为F。
  2. 从F中选出两棵根结点的权值最小的树（假设为a、b)作为左、右子树，构造一棵新的二叉树(假设为c)，新的二叉树的根结点的权值为左、右子树根结点权值之和。
  3. 从F中删除a、b，加入新构造的树c。
  4. 重复进行2)、3）两步，直到F中只剩下一棵树为止，这棵树就是赫夫曼树。 1

图

图的基本概念

  1. 图

图由结点的有穷集合V和边的集合E组成。为了与树形结构进行区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对。若两个顶点之间存在一条边，则表示这两个顶点具有相邻关系。

  1. 有向图和无向图

有向图，即每条边都有方向;无向图，即每条边都没有方向。

  1. 弧

在有向图中，通常将边称为弧，含箭头的一端称为弧头，另一端称为弧尾，记作<vi,vj>，它表示从顶点vi到顶点vj有一条边。

  1. 顶点的度、入度和出度

在无向图中，边记为(vi,vj)，它等价于在有向图中存在<vi,vj>和<vi,vj>两条边。与顶点v相关的边的条数称为顶点v的度。指向顶点v的边的条数称为顶点v的入度，由顶点v发出的边的条数称为顶点v的出度。

  1. 有向完全图和无向完全图

若有向图中有n个顶点，则最多有n(n-1)条边（图中任意两个顶点都有两条边相连)，将具有n(n-1)条边的有向图称为有向完全图。若无向图中有n个顶点，则最多有n(n-1)/2条边（任意两个顶点之间都有一条边)，将具有n(n-1)/2条边的无向图称为无向完全图。

  1. 路径和路径长度

在一个图中，路径为相邻顶点序偶所构成的序列。路径长度是指路径上边的数目。

  1. 简单路径

序列中顶点不重复出现的路径称为简单路径。

  1. 回路

若一条路径中第一个顶点和最后一个顶点相同,则这条路径是一条回路。

  1. 连通、连通图和连通分量

在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图;否则，图中的极大连通子图称为连通分量。

  1. 强连通图和强连通分量

在有向图中，若从vi到vj有路径，则称从vi到vj是连通的。如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图:否则，将其中的极大强连通子图称为强连通分量。

  1. 权和网

图中每条边都可以附有一个对应的数，这种与边相关的数称为权。权可以表示从一个顶点到另一个顶点的距离或者花费的代价。边上带有权的图称为带权图，也称为网。

图的存储结构

邻接矩阵

邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E)是具有n个顶点的图，顶点序号依次为0，1，…，n-1，则G的邻接矩阵是具有如下定义的n阶方阵A:
A[i][j]=1表示顶点i与顶点j邻接，即i与j之间存在边或者弧。
A[i][j]=0表示顶点i与顶点j不邻接（0≤i， j≤n-1)。
邻接矩阵是图的顺序存储结构，由邻接矩阵的行数或列数可知图中的顶点数。对于无向图，邻接矩阵是对称的，矩阵中“1”的个数为图中总边数的两倍，矩阵中第i行或第i列的元素之和即为顶点i的度。对于有向图，矩阵中“1”的个数为图的边数，矩阵中第i行的元素之和即为顶点i的出度，第j列元素之和即为顶点j的入度。

邻接表

邻接表是图的一种链式存储结构。所谓邻接表就是对图中的每个顶点﹔建立一个单链表，每个单链表的第一个结点存放有关顶点的信息，把这一结点看作链表的表头，其余结点存放有关边的信息。因此，邻接表由单链表的表头形成的顶点表和单链表其余结点形成的边表两部分组成。一般顶点表存放顶点信息和指向第一个边结点的指针，边表结点存放与当前顶点相邻接顶点的序号和指向下一个边结点的指针。

图的遍历算法操作

深度优先搜素遍历

图的深度优先搜索遍历（DFS）类似于二叉树的先序遍历。它的基本思想是:首先访问出发点v,并将其标记为已访问过;然后选取与v邻接的未被访问的任意一个顶点 w，并访问它;再选取与w邻接的未被访问的任一顶点并访问，以此重复进行。当一个顶点所有的邻接顶点都被访问过时，则依次退回到最近被访问过的顶点，若该顶点还有其他邻接顶点未被访问，则从这些未被访问的顶点中取一个并重复上述访问过程，直至图中所有顶点都被访问过为止。

以邻接表为存储结构的图的深度优先搜索遍历算法如下:

int visit[maxSize];
void DFS(AGraph *G, int v)
{
    ArcNode *p;
    visit[v]=1;
    Visit(v);
    p=G->adjust[v].firstarc;
    while(p!=NULL)
    {
        if(visit[p->adjvex]==0)
        {
            DFS(G,p->adjvex);
        }        
        p=p->nextarc;
    }
}

广度优先搜索遍历

图的广度优先搜索遍历（BFS）类似于树的层次遍历。它的基本思想是:首先访问起始顶点v，然后选取与v邻接的全部顶点w1，…，wn,进行访问，再依次访问与w1,…,wn,邻接的全部顶点（已经访问过的除外)，以此类推，直到所有顶点都被访问过为止。

广度优先搜索遍历图时，需要用到一个队列(二叉树的层次遍历也要用到队列)，算法执行过程可简单概括如下:

  1. 任取图中一个顶点访问，入队，并将这个顶点标记为已访问。
  2. 当队列不空时循环执行:出队，依次检查出队顶点的所有邻接顶点，访问没有被访问过的邻接顶点并将其入队。
  3. 当队列为空时跳出循环，广度优先搜索即完成。

以邻接表为存储结构的广度优先搜索遍历算法如下:

void BFS(AGraph *G, int v, int visit[maxSize])
{
    ArcNode *p;
    int que[maxSize], front=0, rear=0;
    int j;
    Visit(v);
    visit[v]=1;
    rear=(rear+1)%maxSize;
    que[rear]=v;
    while(front!=rear)
    {
        front=(front+1)%maxSize;
        j=que[front];
        p=G->adjlist[j].firstarc;
        while(p!=NULL)
        {
            if(visit[p->adjvex==0])
            {
                Visit(p->adjvex);
                visit[p->adjvex]=1;
                rear=(rear+1)%maxSize;
                que[rear]=p->adjvex;
            }
            p=p->nextarc;
        }
    }
}

例题

【例1】设计一个算法，求不带权无向连通图G中距离顶点v最远的一个顶点（所谓最远就是到达v的路径长度最长)。

int BFS(AGraph *G, int v)
{
    ArcNode *p;
    int que[maxSize],front=0,rear=0;
    int visit[maxSize];
    int i,j;
    for(i=0;i<G->n;++i)
       visit[i]=0;
    rear=(rear+1)%maxSize;
    que[rear]=v;
    visit[v]=1;
    while(front!=rear)
    {
        front=(front+1)%maxSize;
        j=que[front];
        p=G->adjlist[j].firstarc;
        while(p!=NULL)
        {
            if(visit[p->adjvex]==0)
            {
                visit[p->adjvex]=1;
                rear=(rear+1)%maxSize;
                que[rear]=p->adjvex;
            }
            p=p->nextarc;
        }
    }
    return j;
}

【例2】设计一个算法，判断无向图G是否是一棵树。若是树，返回1，否则返回0。

void DFS2(AGraph *G,int v,int &vn,int &en)
{
    ArcNode *p;
    visit[v]=1;
    ++vn;
    p=G->adjlist[v].firstarc;
    while(p!=NULL)
    {
        ++en;
        if(visit[p->adjvex]==0)
        {
            DFS2(G,p->acijvex, vn, en);
        }
        p=p->nextare;
    }
}
int GisTree (AGraph*G)
{
    int vn=0, en=0,i;
    for(i=0;i<G->n;++i)
        visit[i]-0;
    DFS2(G, 1, vn,en);
    if(vn==G->n&&(G->n-1)==en/2)
        return 1;
    else 
        return 0;
}

【例3】图采用邻接表存储，设计一个算法，判别顶点i和顶点j(i!=j）之间是否有路径。

int DFSTrave(AGraph *G,int i, int j)
{
    int k;
    for(k=0;k<G->n; ++k)
        visit[k]-0;
    DFS(G,i);
    if(visit[j]--1)
        return 1;
    else
        return 0;
}

最小生成树

普利姆算法和克鲁斯卡尔算法

普利姆算法
  1. 算法思想

从图中任意取出一个顶点，把它当成一棵树，然后从与这棵树相接的边中选取一条最短（权值最小)的边，并将这条边及其所连接的顶点也并入这棵树中，此时得到一棵有两个顶点的树。然后从与这棵树相接的边中选取一条最短的边，并将这条边及其所连顶点并入当前树中，得到一棵有3个顶点的树。以此类推，直到图中所有顶点都被并入树中为止，此时得到的生成树就是最小生成树。

  1. 普利姆算法执行过程 从树中某一个顶点v0开始，构造生成树的算法执行过程如下:
    1）将v0到其他顶点的所有边当作候选边。
    2）重复以下步骤n-1次，使得其他n-1个顶点被并入到生成树中。
  • 从候选边中挑选出权值最小的边输出，并将与该边另一端相接的顶点v并入生成树中;
  • 考查所有剩余顶点v,如果(v,vi)的权值比 lowcost[vj]小，则用(v,vi)的权值更新lowcost[vi]。
void Prim (MGraph g, int v0, int &sum)
{
    int lowcost[maxsize], vset[maxsize],v;
    int i,j,k,min;
    v=v0;
    for(i=0;i<g.n;++i)
    {
        lowcost[i]=g.edges[v0][i];
        vset[i]=0;
    }
    vset[v0]=1;
    sum=0;
    for(i=0;i<g.n-1;++i)
    {
        min=INF;
        for(j=0;j<g.n;++j)
        {
            if(vset[j]==0&&lowcost[j]<min)
            {
                min=lowcost[j];
                k=j;
            }
        vset[k]=1;
        v=k;
        sum+=min;
        for(j=0;j<g.n;++j)
        {
            if(vset[j]==0&&g.edges[v][j]<lowcost[j])
               lowcost[j]=g.edges[v][j];
        }
        }
    }
}
克鲁斯卡尔算法
  1. 算法思想

每次找出候选边中权值最小的边，就将该边并入生成树中。重复此过程直到所有边都被检测完为止。

  1. 克鲁斯卡尔算法执行过程

1）将图中边按照权值从小到大排序，然后从最小边开始扫描各边，并检测当前边是否为候选边，即是否该边的并入会构成回路，如不构成回路，则将该边并入当前生成树中，直到所有边都被检测完为止。

2）并查集。判断是否产生回路要用到并查集。并查集中保存了一棵或者几棵树，这些树有这样的特点:通过树中一个结点，可以找到其双亲结点，进而找到根结点（其实就是之前讲过的树的双亲存储结构)。这种特性有两个好处:一是可以快速地将两个含有很多元素的集合并为一个。两个集合就是并查集中的两棵树，只需找到其中一棵树的根，然后将其作为另一棵树中任何一个结点的孩子结点即可。二是可以方便地判断两个元素是否属于同一个集合。通过这两个元素所在的结点找到它们的根结点，如果它们有相同的根，则说明它们属于同一个集合，否则属于不同集合。

typedef struct
{
    int a,b;
    int w;
}Road;
Road road[maxSize];
int v[maxSize];
int getRoot(int a)
{
    while(a!=v[a])
        a=v[a];
    return a;
}
void Kruskal(MGraph g,int &sum,Road road[])
{
    int i;
    int N,E,a,b;
    N=g.n;
    E=g.e;
    sum=0;
    for(i=0;i<N;++i)
    {
        v[i]=i;
    }
    sort(road,E);
    for(i=0;i<E;++i)
    {
        a=getRoot(road[i].a);
        b=getRoot(road[i].b);
        if(a!=b)
        {
            v[a]=b;
            sum+=road[i].w;
        }
    }
}

最短路径

迪杰斯特拉算法

弗洛伊德算法

拓扑排序

AOV网

活动在顶点上的网(Activity On Vertex network,AOV网)是一种可以形象地反映出整个工程中各个活动之间的先后关系的有向图。

拓扑排序核心算法

对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若存在由u到v的路径，则在拓扑排序序列中一定是u出现在v的前面。

在一个有向图中找到一个拓扑排序序列的过程如下:
1）从有向图中选择一个没有前驱（入度为0）的顶点输出。
2）删除1）中的顶点，并且删除从该顶点发出的全部边。
3）重复上述两步，直到剩余的图中不存在没有前驱的顶点为止。

int TopSort(AGraph *G)
{
    int i,j,n=0;
    int stack[maxSize],top=-1;
    ArcNode *p;
    for(i=0;i<G->n;++i)
    {
        if(G->adjlist[i].count==0)
           stack[++top]=i;
    }
    while(top!=-1)
    {
        i=stack[top--];
        ++n;
        p=G->adjlist[i].firstarc;
        while(p!=NULL)
        {
            j=p->adjvex;
            --(G->adjlist[j].count);
            if(G->adjlist[j].count==0)
               stack[++top]=j;
            p=p->nextarc;
        }
    }
    if(n==G->n)
        return 1;
    else 
        return 0;
}

关键路径

AOE网

对于活动在边上的网（Activity On Edge network，AOE网）可以和AOV网对比着来记忆。

  • 两者的相同点:都是有向无环图。
  • 两者的不同点:AOE网的边表示活动，边有权值，边代表活动持续时间;顶点表示事件，事件是图中新活动开始或者旧活动结束的标志。AOV网的顶点表示活动，边无权值，边代表活动之间的先后关系。

关键路径核心算法

排序

排序的基本概念

排序算法的分类

  1. 插入类的排序
  2. 交换类的排序
  3. 选择类的排序
  4. 归并类的排序
  5. 基数类的排序

插入类排序

直接插入排序

  1. 算法思想

每趟将一个待排序的关键字按照其值的大小播入到已经排好的部分有序序列的适当位置上，直到所有待排关键字都被插入到有序序列中为止。

void InsertSort(int R[],int n)
{
    int i,j;
    int temp;
    for(i=1;i<n;++i)
    {
        temp=R[i];
        j=i-1;
        while(j>=0&&temp<R[j])
        {
            R[j+1]=R[j];
            --j;
        }
        R[j+1]=temp;
    }
}

折半插入排序

折半插入排序的基本思想和直接插入排序类似，区别是查找插入位置的方法不同，折半插入排序是采用折半查找法来查找插入位置的。

折半查找法的一个基本条件是序列已经有序，而从直接插入排序的流程中可以看出，每次都是在一个已经有序的序列中插入一个新的关键字，因此可以用折半查找法在这个有序序列中查找插入位置。

希尔排序

  1. 算法介绍

希尔排序又叫作缩小增量排序，其本质还是插入排序，只不过是将待排序列按某种规则分成几个子序列，分别对这几个子序列进行直接插入排序。这个规则的体现就是增量的选取，如果增量为 1，就是直接插入排序。例如，先以增量5来分割序列，即将下标为0、5、10、15…的关键字分成一组，将下标为1、6、11、16…的关键字分成另一组等，然后分别对这些组进行直接插入排序，这就是一趟希尔排序。将上面排好序的整个序列，再以增量2分割，即将下标为0、2、4、6、8…的关键字分成一组，将下标为1、3、5、7、9…的关键字分成另一组等，然后分别对这些组进行直接插入排序，这又完成了一趟希尔排序。最后以增量1分割整个序列，其实就是对整个序列进行一趟直接插入排序，从而完成整个希尔排序。

注意到增量5、2、1是逐渐缩小的，这就是缩小增量排序的由来。前面讲过，直接插入排序适合于序列基本有序的情况，希尔排序的每趟排序都会使整个序列变得更加有序，等整个序列基本有序了，再来一趟直接插入排序，这样会使排序效率更高，这就是希尔排序的思想。

交换类排序

起泡排序

  1. 算法介绍

起泡排序又称冒泡排序。它是通过一系列的“交换”动作完成的。首先第一个关键字和第二个关键字比较，如果第一个大，则二者交换，否则不交换;然后第二个关键字和第三个关键字比较，如果第二个大，则二者交换，否则不交换……。一直按这种方式进行下去，最终最大的那个关键字被交换到了最后，一趟起泡排序完成。经过多趟这样的排序，最终使整个序列有序。在这个过程中，大的关键字像石头一样“沉底”，小的关键字像气泡一样逐渐向上“浮动”，起泡排序的名字由此而来。

void BubbleSort(int R[],int n)
{
    int i,j,flag;
    int temp;
    for(i=n-1;i>=1;--i)
    {
        flag=0;
        for(j=1;j<=i;++j)
        {
            if(R[j-1]>R[j])
            {
                temp=R[j];
                R[j]=R[j-1];
                R[j-1]=temp;
                flag=1;
            }
            if(flag==0)
                return;
        }
    }
}

快速排序

  1. 算法介绍

快速排序也是“交换”类的排序，它通过多次划分操作来实现排序。以升序为例，其执行流程可以概括为:每一趟选择当前所有子序列中的一个关键字（通常是第一个）作为枢轴，将子序列中比枢轴小的移到枢轴前面，比枢轴大的移到枢轴后面;当本趟所有子序列都被枢轴以上述规则划分完毕后会得到新的一组更短的子序列，它们成为下一趟划分的初始序列集。

void QuickSort(int R[], int low, int high)
{
    int temp;
    int i=low,j=high;
    if(low<high)
    {
        temp=R[low];
        while(i<j)
        {
            while(j>i&&R[j]>=temp)
            {
                --j;
            }
            if(i<j)
            {
                R[i]=R[j];
                ++i;
            }
            while(i<j&&R[i]<temp)
            {
                ++i;
            }
            if(i<j)
            {
                R[j]=R[i];
                --j;
            }
        }
        R[i]=temp;
        QuickSort(R,low,i-1);
        QuickSort(R,i+1,high);
    }
}

选择类排序

简单选择排序

  1. 算法介绍

选择类排序的主要动作是“选择”，简单选择排序采用最简单的选择方式，从头至尾顺序扫描序列,找出最小的一个关键字，和第一个关键字交换，接着从剩下的关键字中继续这种选择和交换，最终使序列有序。

void SelectSort(int R[],int n)
{
    int i,j,k;
    int temp;
    for(i=0;i<n;++i)
    {
        k=i;
        for(j=i+1;j<n;++j)
        {
            if(R[k]<R[j])
            {
                k=j;
            }
        }
        temp=R[i];
        R[i]=R[k];
        R[k]=temp;
    }

}

堆排序

  1. 算法介绍

堆是一种数据结构，可以把堆看成一棵完全二叉树，这棵完全二叉树满足:任何一个非叶结点的值都不大于(或不小于）其左、右孩子结点的值。若父亲大孩子小，则这样的堆叫作大顶堆;若父亲小孩子大，则这样的堆叫作小顶堆。

根据堆的定义知道，代表堆的这棵完全二叉树的根结点的值是最大（或最小）的，因此将一个无序序列调整为一个堆，就可以找出这个序列的最大(或最小）值，然后将找出的这个值交换到序列的最后(或最前)，这样，有序序列关键字增加1个，无序序列中关键字减少1个，对新的无序序列重复这样的操作，就实现了排序。这就是堆排序的思想。

堆排序中最关键的操作是将序列调整为堆。整个排序的过程就是通过不断调整，使得不符合堆定义的完全二叉树变为符合堆定义的完全二叉树。

二路归并排序

基数排序

外部排序

查找

查找的基本概念、顺序查找法、折半查找法

查找的基本概念

查找的定义:给定一个值k，在含有n个记录的表中找出关键字等于k的记录。若找到，则查找成功，返回该记录的信息或者该记录在表中的位置;否则查找失败，返回相关的指示信息。

顺序查找法

顺序查找法是一种最简单的查找方法。它的基本思路是:从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k进行比较，若当前扫描的关键字与k相等，则查找成功;若扫描结束后，仍未发现关键字等于k的记录，则查找失败。由以上可知，顺序查找法对于顺序表和链表都是适用的。对于顺序表，可以通过数组下标递增来顺序扫描数组中的各个元素;对于链表，则可通过表结点指针(假设为p）反复执行p=p->next;来扫描表中各个元素。

折半查找法

折半查找的基本思路:设R[low，…., high]是当前的查找区间，首先确定该区间的中间位置mid=(low+high)/2;，然后将待查的k值与R[mid]比较，若相等，则查找成功，并返回该位置，否则需确定新的查找区间。若R[mid]>k，则由表的有序性可知R[mid，….,high]均大于k，因此若表中存在关键字等于k的记录，则该记录必定是在 mid左边的子表R[low，…,mid-1]中，故新的查找区间是左子表R[low，.…, mid-1]。类似地，若R[mid]<k，则要查找的k必在mid的右子表K[mid+1，…，high]中，即新的查找区间是右子表R[mid+1，.… , high]。递归地处理新区间，直到子区间的长度小于1时查找过程结束。

分块查找

分块查找又称为索引顺序查找，其数据结构可以简单地描述为:分块查找把线性表分成若干块，每一块中的元素存储顺序是任意的，但是块与块之间必须按照关键字大小有序排列，即前一块中的最大关键字要小于后一块中的最小关键字。对顺序表进行分块查找需要额外建立一个索引表，表中的每一项对应线性表中的一块，每个索引项都由键值分量和链值分量组成，键值分量存放对应块的最大关键字，链值分量存放指向本块第一个元素和最后一个元素的指针（这里的指针可以是存放线性表数组中的元素下标或者地址，或是任何可以帮助找到这个元素的信息)，显然索引表中的所有索引项都是按照其关键字的递增顺序排列的。

树形查找

二叉排序树

  1. 二叉树的定义与存储结构

（1）二叉排序树BST的定义
1）若它的左子树不空，则左子树上所有关键字的值均不大于（不小于）根关键字的值。
2）若它的右子树不空，则右子树上所有关键字的值均不小于（不大于）根关键字的值。
3）左右子树又各是一棵二叉排序树。

（2）二叉排序树的存储结构 二叉排序树通常采用二叉链表进行存储，其结点类型定义与一般的二叉树类似。

typedef struct BTNode
{
    int key;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode;
  1. 二叉排序树的基本算法
    （1） 查找关键字的算法
BTNode* BSTSearch(BTNode* bt,int key)
{
    if(bt==NULL)
        return NULL;
    else 
    {
        if(bt->key==key)
            return bt;
        else if(key<bt->key)
            return BSTSearch(bt->lchild,key);
        else 
            return BSTSearch(bt->rchild,key);
    }
}

（2） 插入关键字的算法

int BSTInsert(BTNode *&bt, int key)
{
    if(bt==NULL)
    {
        bt=(BTNode*)malloc(sizeof(BTNode));
        bt->lchild=bt->rchild=NULL;
        bt->key=key;
        return 1;
    }
    else 
    {
        if(key==bt->key)
            return 0;
            else if (key<bt->key)
                return BSTInsert(bt->lchild,key);
            else
                return BSTInsert(bt->rchild,key);
    }
}

平衡二叉树

  1. 平衡二叉树的概念

平衡二叉树又称为AVL树，是一种特殊的二叉排序树。其左右子树都是平衡二叉树，且左右子树高度之差的绝对值不超过1。一句话表述为:以树中所有结点为根的树的左右子树高度之差的绝对值不超过1。

  1. 平衡二叉树的建立

建立平衡二叉树的过程和建立二叉排序树的过程基本一样，都是将关键字逐个插入空树中的过程。所不同的是，在建立平衡二叉树的过程中，每插入一个新的关键字都要进行检查，看新关键字的插入是否会使得原平衡二叉树失去平衡，即树中出现平衡因子绝对值大于1的结点。如果失去平衡则需要进行平衡调整。

  1. 平衡调整

假定向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性，则首先要找出插入新结点后失去平衡的最小子树，然后再调整这棵子树，使之成为平衡子树。值得注意的是，当失去平衡的最小子树被调整为平衡子树后，无须调整原有其他所有的不平衡子树，整个二叉排序树就会成为一棵平衡二叉树。所谓失去平衡的最小子树是指距离插入结点最近，且以平衡因子绝对值大于1的结点作为根的子树，又称为最小不平衡子树。

B-树的基本概念及其基本操作、B+树的基本概念

B-树的基本概念

B-树的基本操作

B+树的基本概念

散列表

散列表的概念

根据给定的关键字来计算关键字在表中的地址

散列表的建立方法以及冲突解决方法

相关文章：