数据结构

线性表

顺序表静态分配

  #define MaxSize = 10
  typedef struct{
      ElemType data[MaxSize];
      int length;
  }SqList;
  bool ListInsert(SqList &L, int i, int e){
      if(i < 1 || i > L.length+1)
          return false;
      if(L.length >= MaxSize)
          return false;
      for(int j = L.length; j >= i; j--)
          L.data[j] = L.data[j-1];
      L.data[i-1] = e;
      L.length++;
      return true;
  }
  
  bool ListDelete(SqList &L, int i, int &e){
      if(i < 1 || i > L.length+1)
          return false;
      e = L.data[i-1];
      for(int j = i; i< L.length; j++)
          L.data[j-1] = L.data[j];
      L.length--;
      return true;
  }

顺序表动态分配实现(C语言)

  #define InitSize 10        //顺序表的初始长度
  typedef struct{
      int *data;        //指示动态分配数组的指针
      int MaxSize;        //顺序表最大容量
      int length;            //顺序表当前长度
  }SeqList;                //顺序表的类型定义(动态分配方式)
  
  void InitList(SeqList &L){
      L.data = (int *)malloc(InitSize * sizeof(int));
      L.length = 0;
      L.MaxSize = InitSize;
  }
  
  //增加动态数组的长度
  void IncreseSize(SeqList &L, int len){
      int *p = L.data;
      L.data = (int *)malloc((L.MaxSize + len) * sizeof(int));
      for(int i = 0; i < L.length; i++){
          L.data[i] = p[i];            //将数据复制到新区域
      }
      L.MaxSize = L.MaxSize + len;
      free(p);
  }
  
  ElemType GetElem(SeqList L, int i){
      return L.data[i-1];
  }
  
  int LocateElem(SeqList L, ElemType e){
      for(int i=0; i<L.length; i++)
          if(L.data[i]==e)
              return i+1;
      return 0;
  }
  
  int main(){
      SeqList L;
      InitList(L);
      //...往顺序表中随便插入几个元素
      IncreaseSize(L, 5);
      return 0;
  }

在C语言中常用mallocfree两个函数实现动态分配

malloc:动态申请内存空间。malloc函数返回一个指针,需要强制转型为你定义的数据元素类型指针。malloc参数需指明要分配多大的连续内存空间

free:动态申请释放内存空间

  L.data = (ElemType*) malloc(sizeof(ElemTyoe) * InitSize);

在C++语言中常用newdelete关键字实现动态分配

  L.data = new Elemtype[InitSize];

单链表

每个节点除了存放数据元素,还有指向下一个节点的指针

  typedef struct LNode{
      ElemType data;
      struct LNode *next;
  }LNode, *LinkList;
  
  /*
  不带头节点
  */
  bool InitList(LinkList &L){
      L = NULL;
      return true;
  }
  
  /*
  带头节点
  */
  
  bool InitList(LinkList &L){
      L = (LNode *) malloc(sizeof(LNode));
      if (L==null)
          return false;
      L->next = NULL;
      return true;
  }
  
  //在第i个位置插入元素e(带头节点)
  bool ListInsert(LinkList &L, int i, ElemType e){
      if(i<1)
          return false;
      LNode *p;
      int j = 0;
      p = L;
      while(p!=NULL && j<i-1){
          p = p->next;
          j++;
      }
      return InsertNextNode(p, e)
  }
  
  //按位序插入(不带头节点)
  
  bool ListInsert(LinkList &L, int i, ElemType e){
      if(i<1)
          return false;
      if(i==1){
          LNode *s = (LNode *)malloc(sizeof(LNode));
          s->data = e;
          s->next = L;
          L = s;        //头指针指向新节点
          return true;
      }
      LNode *p;
      int j = 1;
      p = L;
      while(p!=NULL && j<i-1){
          p = p->next;
          j++;
      }
      if(p==NULL)
          return false;
      LNode *s = (LNode *)malloc(sizeof(LNode));
      s->data = e;
      s->next = p->next;
      p->next = s;
      return true;
  }
  
  //后插操作
  bool InsertNextNode(LNode *p, ElemType e){
      if(p==NULL)
          return false;
      LNode *s = (LNode *)malloc(sizeof(LNode));
      if(s==NULL)        //内存分配失败
          return false;
      s->data = e;
      s->next = p->next;
      p->next = s;
      return true;
  }
  
  //前插操作
  bool InsertPriorNode(LNode *p, ElemType e){
      if(p==NULL)
          return false;
      LNode *s = (LNode *)malloc(sizeof(LNode));
      if(s==NULL)        //内存分配失败
          return false;
      s->next = p->next;
      p->next = s;
      s->data = p->data;
      p->data = e;
      return true;
  }
  
  //按位序删除(带头节点)
  bool ListDelete(LinkList &L, int i, ElemType &e){
      if(i<1)
          return false;
      LNode *p;
      int j = 0;
      p = L;
      while(p!=NULL && j<i-1){
          p = p->next;
          j++;
      }
      if(p==NULL)
          return false;
      LNode *q = p->next;
      e = q->data;
      p->next = q->next;
      free(q);
      return true;
  }
  //删除指定节点p
  bool DeleteNode(LNode *p){
      if(p==NULL)
          return false;
      LNode *q = p->next;
      p->data = p->next->data;
      p->next = q->next;
      free(q);
      return true;
  }
  
  //按位查找(带头节点)
  LNode * GetElem(LinkList L, int i){
      if(i<0)
          return NULL;
      LNode *p;        //指针p指向当前扫描到的节点
      int j = 0;        //当前p指向的第几个节点
      p = L;            //L指向头节点,头节点上第0个节点,不存储数据
      while(p!=NULL && j<i){
          p = p->next;
          j++;
      }
      return p;
  }
  
  //按值查找
  LNode * LocateElem(LinkList L, ElemType e){
      Lnode *p = L->next;
      while(p != NULL && p->data != e)
          p = p->next;
      return p;
  }
  
  //尾插法建立单链表
  LinkList List_TailInsert(LinkList &L){
      int x;
      L=(LinkList)malloc(sizeof(LNode));
      LNode*s, *r = L;
      scanf("%d", &x);
      while(x!=9999){
          s = (LNode *)malloc(sizeof(LNode));
          s->data = x;
          r-next = s;
          r = s;
          scanf("%d", &x);
      }
      r->next = NULL;
      return L;
  }
  
  //头插法建立单链表
  
  LinkList List_HeadInsert(LinkList &L){
      LNode *s;
      int x;
      L = (LinkList)malloc(sizeof(LNode));
      L->next = NULL;
      scanf("%d", &x);
      while(x!=9999){
          s = (LNode *)malloc(sizeof(LNode));
          s->data = x;
          s-next = L->next;
          L->next = s;
          scanf("%d", &x);
      }
      return L;
  }
  void test(){
    
  }
  
  

双链表

带头节点

  typedef struct DNode{
      ElemType data;
      struct DNode *prior, *next;
  }DNode, *DLinklist;
  
  bool InitDLinkList(DLinklist & L){
      L = (DNode *) malloc(sizeof(DNode));
      if(L==NULL)
          return false;
      L->prior = NULL:
      L->next = NULL;
      return true;
  }
  bool Empty(DLinklist L){
      if(L->next == NULL)
          return true;
      else
          return false;
  }
  
  bool InsertNextDNode(DNode *p, DNode *s){
      if(p==NULL || s==NULL)
          return false;
      s->next = p->next;
      if(p->next != NULL)
          p->next->prior = s;
      s->prior = p;
      p->next = s;
      return true;
  }
  
  bool DeleteNextNode(DNode *p){
      if(p==NULL)
          return false;
      DNode *q = p->next;
      if(q==NULL)
          return false;
      p->next = q->next;
      if(q->next != NULL)
          q->next->prior = p;
      free(q);
      return true;
  }
  
  void DestoryList(DLinklist &L){
      while(L->next != NULL)
          DeleteNextDNode(L);
      free(L);
      L = NULL;
  }
  
  
  void testDLinkList(){
      Dlinklist L;
      InitDlinkList(L);
  }

静态链表

#define MaxSize 10
struct Node{
    ElemType data;
    int next;
};
typedef struct Node SLinkList[MaxSize]

void testSLinkList(){
    SLinkList a;
}

只允许在一端进行插入或删除操作,后进先出

顺序栈的缺点,栈顶大小不可变

顺序栈

#define MaxSize 10

typedef struct{
    ElemType data[MaxSize];        //静态数组存放栈中元素
    int top;                    //栈顶指针
} SqStack;

void InitStatck(SqStack &S){
    S.top = -1;
}

bool StackEmpty(SqStack S){
    if(S.top==-1)
        return true;
    else
        return false;
}

bool Push(SqStack &S, ElemType x){
    if(S.top==MaxSize-1)
        return false;
    S.data[++S.top] = x;
    return true;
}

bool Pop(SqStack &S, Elemtype &x){
    if(S.top==-1)
        return false;
    x = S.data[S.top--];
    return true;
}
void testStack(){
    SqStack S;
}

链栈

#include <stdio.h>
#include <stdlib.h>
typedef struct LineStack{
    int data;
    struct LineStack * next;
}LineStack;


LineStack* push(LineStack * stack,int a){
    LineStack * line=(LineStack*)malloc(sizeof(LineStack));
    line->data=a;
    line->next=stack;
    stack=line;
    return stack;
}

lineStack * pop(LineStack * stack){
    if (stack) {
        lineStack * p=stack;
        stack=stack->next;
        printf("弹栈元素:%d ",p->data);
        if (stack) {
            printf("栈顶元素:%d\n",stack->data);
        }else{
            printf("栈已空\n");
        }
        free(p);
    }else{
        printf("栈内没有元素");
        return stack;
    }
    return stack;
}
int main() {
    lineStack * stack=NULL;
    stack=push(stack, 1);
    stack=push(stack, 2);
    stack=push(stack, 3);
    stack=push(stack, 4);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    stack=pop(stack);
    return 0;
}                //栈类型定义

括号匹配算法

#define MaxSize 10
typedef struct{
    char data[MaxSize];
    int top;
}SqStack;

void InitStack(SqStack &S){
  
}

bool StackEmpty(SqStack S){
  
}

bool Push(SqStack &S, char x){
  
}

bool Pop(SqStack &S, char x){
  
}

bool bracketCheck(char str[], int length){
    SqStack S;
    InitStack(S);
    for (int i=0; i<length; i++){
        if (str[i]=='(' || str[i]=='[' || str[i]=='{'){
            Push(S, str[i]);
        }
        else{
            if(StackEmpty(S))
                return false;
            char topElem;
            Pop(S,topElem);
            if (str[i]==')' && topElem!='(')
                return false;
            f (str[i]==']' && topElem!='[')
                return false;
            f (str[i]=='}' && topElem!='{')
                return false;
        }
    }
    return StackEmpty(S);
}

前缀中缀后缀算法

队列

只允许在一端进行插入,在另一端删除,先进先出FIFO

队列的顺序实现

队列元素个数:(rear+MaxSize-front)%MaxSize

#define MaxSize 10
typedef struct{
    ElemType data[MaxSize];
    int front, rear;        //队头,队尾指针
    int size;
} SqQueue;

void InitQueue(SqQueue &Q){
    Q.rear = Q.front = Q.size = 0;
}

bool QueueEmpty (SqQueue Q){
    if(Q.rear == Q.front)
        return true;
    else
        return false;
}

bool EnQueue(SqQueue &Q, ElemType x){
    if(size==MaxSize)    //队满
        return false;
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear + 1) % MaxSize;    //队尾指针加1取模,循环队列
    size++;
    return true;
}

bool DeQueue(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)                //or size==0
        return false;
    x = Q.data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;    //队头指针后移
    size--;
    return true;
}

bool GetHead(SqQueue &Q, ElemType &x){
    if(Q.rear == Q.front)
        return false;
    x = Q.data[Q.front];
    return true;
}

void testQueue(){
    SqQueue Q;
    InitQueue(Q);
}

队列的链表实现(链队列)

带头节点

typedef struct LinkNode{
    ElemType data;        
    struct LinkNode *next;
} *LinkNode;

typedef struct{
    LinkNode *front, *rear;
}LinkQueue;

void InitQueue(LinkQueue &Q){
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
}

void EnQueue(LinkQueue &Q, ElemType x){
    LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s-> next = NULL;
    Q.rear->next = s;
    Q.rear = s;
}

bool DeQueue(LinkQueue &Q, ElemType &x){
    if(Q.front==Q.rear)
        return false;
    LinkNode *p = Q.front->next;
    x = p->data;
    Q.front->next = p->next;
    if(Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return true;
}

串,也就是字符串string,由零个或多个字符组成的有限序列。是特殊的线性表,数据元素之间呈线性关系。数据对象限定为字符集,基本操作例如增删改查通常以子串为操作对象

子串:串中任意个连续的字符组成的子序列

主串:包含子串的串

字符在主串中的位置:字符中串中的序号(从1开始)

子串中主串中的位置:子串的第一个字符中主串中的位置

#define MaxLen 255
typedef struct{
    char ch[MaxLen];    //静态数组实现(定长顺序存储)
    int length;
}SString;

//求子串
bool SubString(SString &Sub, SString S, int pos, int len){
    if (pos+len-1 > S.length)
        return false;
    for (int i=pos; i<pos+len; i++)
        Sub.ch[i-pos+1] = S.ch[i];
    Sub.length = len;
    return true;
}

//比较
int StrCompare(SString S, SString T){
    for (int i=1; i<S.length && i<=T.length; i++){
        if (S.ch[i] != T.ch[i])
            return S.ch[i]-T.ch[i];
    }
    return S.length-T.length;
}

//定位
int Index(SString S, SString T){
    int i=1, n=StrLength(S), m=StrLength(T);
    SString sub;
    while(i<=n-m+1){
        SubString(sub, S, i, m);
        if(StrCompare(sub, T)!=0)
            i++;
        else
            return i;    
    }
    return 0;
}

typedef struct{
    char *ch;            //按串长分配存储区,ch指向串的基地址
    int length;
}HString;                //动态数组实现(堆分配存储)

HString S;
S.ch = (char *)malloc(MaxLen * sizeof(char));    //用完需要手动free
S.length = 0;



//链式存储
typedef struct StringNode{
    char ch[4];                //每个节点存多个字符
    struct StringNode * next;
}StringNode, * String;

朴素模式匹配算法

时间复杂度:mn

字符串模式匹配:在主串中找到与模式串相同的子串并返回其所在位置

数组方法

int Index(SString S, SString T){
   int i=1, j=1;
   while(i<=S.length && j<=T.length){
       if(S.ch[i]==T.ch[j]){
           ++i; ++j;
       }
       else{
           i=i-j+2;
           j=1;
       }
   }
   if(j>T.length)
       return i-T.length;
   else
       return 0;
}

KMP算法

int Index_KMP(SString S, SString T, int next[]){
    int i=1, j=1;
    while(i<=S.length && j<=T.length){
        if(j==0 || S.ch[i] == T.ch[i]){
            ++i;
            ++j;
        }
        else
            j = next[j];        //模式串右移
    }
    if(j>T.length)
            return i-T.length;
    else
            return 0;
}

时间复杂度m+n

树是n(n≥0)个结点的有限集合,n=0时,成为空树

任意非空树:

  • 有且仅有一个特定的称为根的结点
  • $n>1$时,其余结点可分为$m(m>0)$个互不相交的有限集合,其中每个集合本身又是一棵树,并称为根结点的子树。

结点层次:也就是深度,从上往下数

结点高度:从下往上数

树的高度/深度:总共多少层

结点的度:结点有几个分支

结点数=总度数+1

树的度:各结点的度的最大值

  • 度为$m$的树

    • 任意结点的度$≤m$
    • 至少有一个结点度$=m$
    • 一定是非空树,至少有$m+1$个结点
    • 第$i$层至多有$m^{i-1}$个结点$(i≥1)$
    • 高度为$h$,度为$m$,至少有$h+m–1$结点
  • $m$叉树:每个结点最多只能有$m$个分支的树

    • 任意结点的度$≤m$
    • 允许所有结点的度$<m$
    • 可以是空树
    • 高度为$h$的$m$叉树至多有$\frac{m^h-1}{m-1}$个结点,至少有h个结点
    • 第$i$层至多有$m^{i-1}$个结点$(i≥1)$
    • 有$n$个结点度$m$叉树,最小高度为$\log_m (n(m-1)+1)$

二叉树

二叉树是$n$个结点的有限集合,是有序树:

  1. 或为空二叉树,$n=0$
  2. 或由一个根结点和两个互不相交的被称为根的左子树和右子树组成,它们分别又是一棵二叉树。特点是:每个结点至多有两棵子树;左右子树不能颠倒

常见考点

  • 设非空二叉树中度为0、1和2度结点个数分别为$n_0,n_1,n_2$则$n_0=n_2+1$,也就是叶子结点比二分支结点多一个
  • 高度为$h$的二叉树至多有$2^n-1$个结点(满二叉树)

满二叉树

  • 高度$h$,则含有$2^h-1$个结点
  • 只有最后一层有叶子结点
  • 按层序从1开始编号,结点i的左结点为$2i$,右结点为$2i+1$,结点$i$的父结点为$\frac{i}{2}$(如果存在的话)

完全二叉树

当且仅当每个结点都与高度为$h$的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树

  • 只有最后两层可能有叶子结点
  • 最多只有一个度为1度结点
  • 按层序从1开始编号,结点i的左结点为$2i$,右结点为$2i+1$,结点$i$的父结点为$\frac{i}{2}$(如果存在的话)
  • $i≤[\frac{n}{2}]$为分支结点,$i>[\frac{n}{2}]$为叶子结点

常见考点

  • $具有n个(n>0)结点的完全二叉树的高度h为log_2(n+1)或log_2n +1$
  • 高度$h$,则含有$2^h-1$个结点
  • $若完全二叉树有2k个结点,则必有n_1=1,n_0=k,n_2=k-1$
  • $若完全二叉树有2k-1个结点,则必有n_1=0,n_0=k,n_2=k-1$

二叉排序树

  • 左子树上所有结点的关键字小于根结点的关键字
  • 右子树上所有结点的关键字大于根结点的关键字
  • 左右子树又各自是一棵二叉排序树

平衡二叉树

树上任一结点的左子树和右子树深度之差不超过1

二叉树的顺序存储

只适用于存储完全二叉树

#define maxSize 100
struct TreeNode{
    ElemType value;
    bool isEmpty;
}

二叉树链式存储

struct ElemType{
    int value;
};

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild, *rchild, *parent;
}BiTNode,*BiTree;
/*
n个结点的二叉链表共有n+1个空链域,可用于构造线索二叉树
*/

//定义一棵空树
BiTree root = NULL;

//插入根结点
root = (BiTree) malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;

//插入新结点
BiTNode * p = (BiTNode *) malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;
p->parent = root;

二叉树遍历

二叉树构造

#include<iostream>
#include<stack>
using namespace std;

typedef struct BiTNode{
    char data;
    int lvisited,rvisited;//左、右孩子是否访问过,1表示已访问(此项只在后序非递归2算法中需要)
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void InitBiTree(BiTree &T)//构造空二叉树
{
    T=NULL;
}
void CreateBiTree(BiTree &T)//生成二叉树
{
    char ch;
    cin>>ch;
    if(ch=='0')//0代表空
        T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));//生成根结点
        if(!T)
        {
            cout<<"生成结点错误!"<<endl;
            return;
        }
        T->data=ch;
        T->lvisited=0;
        T->rvisited=0;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

先序遍历、中序遍历、后序遍历(都是以根结点为中心的称呼)

void PreOrder(BiTree T)//先序递归遍历
{
    if(T!=NULL)
    {
        cout<<T->data<<" ";
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
void SqlPreOrder(BiTree T)//先序非递归遍历
{
    stack<BiTree> s;
    BiTree p=T;
    while(p || !s.empty())
    {
        if(p)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->lchild;
        }
        else
        {
            p=s.top();
            p=p->rchild;
            s.pop();
        }
    }
}

void InOrder(BiTree T)//中序递归遍历
{
    if(T!=NULL)
    {
        InOrder(T->lchild);
        cout<<T->data<<" ";
        InOrder(T->rchild);
    }
}
void SqInOrder(BiTree T)//中序非递归遍历
{
    stack<BiTree> s;
    BiTree p=T;
    while(p || !s.empty())
        if(p)
        {
            s.push(p);
            p=p->lchild;
        }
        else
        {
            p=s.top();
            cout<<p->data<<" ";
            s.pop();
            p=p->rchild;
        }
}



void PostOrder(BiTree T)//后序递归遍历
{
    if(T!=NULL)
    {
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        cout<<T->data<<" ";
    }
}

//后序非递归遍历1思路:因为后序非递归遍历二叉树的顺序是先访问左子树,再访问后子树,最后
//访问根结点。当用堆栈来存储结点,必须分清返回根结点时,是从左子树返回的,还是从右子树
//返回的。所以,使用辅助指针r,其指向最近访问过的结点。
void SqlPostOrder1(BiTree T)//后序非递归遍历1
{
    stack<BiTree> s;
    BiTree p=T,r;
    while(p || !s.empty())
    {
        if(p)                             //走到最左边
        {
            s.push(p);
            p=p->lchild;
        }
        else                             //向右
        {
            p=s.top();//取栈顶结点
            if(p->rchild && p->rchild!=r)//如果右子树存在,且未被访问过
            {
                p=p->rchild;
                s.push(p);
                p=p->lchild;             //再走到最左
            }
            else                         //否则,访问栈顶结点并弹出
            {
                cout<<p->data<<" ";
                r=p;                     //记录该结点
                s.pop();
                p=NULL;                     //结点访问完后,重置p指针
            }
        }
    }
}
//思路2:在结点中增加标志域,记录是否已被访问。
void SqlPostOrder2(BiTree T)//后序非递归遍历2
{
    stack<BiTree> s;
    BiTree p=T;
    while(p || !s.empty())
    {
        if(p && p->lvisited==0)                     //左走,且左子树未被访问
        {
            p->lvisited=1;
            s.push(p);
            p=p->lchild;
        }
        else
        {
            p=s.top();
            if(p->rchild!=NULL && p->rvisited==0)//右子树未被访问,右走一步
            {
                p->rvisited=1;
                p=p->rchild;
            }
            else                                 //访问栈顶元素并弹栈
            {
                cout<<p->data<<" ";
                s.pop();
                if(!s.empty())
                    p=s.top();
                else                             //当最后一个元素弹栈出去后,结束
                    return ;
            }
        }
    }
}

层序遍历

  1. 初始化一个辅助队列
  2. 根结点入队
  3. 若队列非空,则队头结点出队,访问该结点,并将其左右子结点插入队尾(如果存在)
  4. 重复至队列为空
void LeveOrder(BiTree T){
    LinkQueue Q;
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while(!IsEmpty(Q)){
        DeQueue(Q, p);
        visit(p);
        if(p->lchild!==NULL)
            EnQueue(Q,p-lchild);
        if(p->rchild!==NULL)
            EnQueue(Q,p-rchild);
    }
}

遍历序列构造二叉树

  • 前序+中序
  • 后序+中序
  • 层序+中序

中序线索二叉树

ThreadNode *pre = NULL;

//线索二叉树结点
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag,rtag;            //tag为0表示指针指向子结点,为1表示指针是线索
}ThreadNode,* ThreadTree;

void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);    //中序遍历左子树
        visit(T);
        InThread(T->rchild);
    }
}

void PreThread(ThreadTree T){
    if(T!=NULL){
        visit(T);
        if(T->tag==0)
            PreThread(T->lchild);//先序遍历左子树
        PreThread(T->rchild);
    }
}

void PostThread(ThreadTree T){
    if(T!=NULL){
        PostThread(T->lchild);
        PostThread(T->rchild);
        visit(T);
    }
}

void visit(ThreadNode *q){
    if(q->lchild==NULL){
        q->lchild=pre;
        q->ltag=1;
    }
    if(pre!=NULL && pre->rchild==NULL){
        pre->rchild=q;
        pre->rtag=1;
    }
    pre=q;
}

//中序线索化二叉树T
void CreateInThread(ThreadTree T){        
    pre=NULL;
    if(T!=NULL){
        InThread(T);
        if (pre->rchild==NULL)
            pre->rtag=1;
    }
}

//先序线索化二叉树T
void CreatePreThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        PreThread(T);
        if(pre->rchild==NULL)
            pre->rtag=1;        //处理遍历的最后一个结点
    }
}

//后序线索化二叉树T
void CreatePostThread(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        PostThread(T);
        if(pre->rchild==NULL)
            pre->rtag=1;        //处理遍历的最后一个结点
    }
}

线索二叉树找后继/前驱

//中序线索二叉树中,找到以P为根的子树中,第一个被中序遍历的结点
ThreadNode *Firstnode(ThreadNode *p){
    //循环找到最左下结点,不一定是叶结点
    while(p->ltag==0)
        p = p->lchild;
    return p;
}

//中序线索二叉树中,找到以P为根的子树中,最后一个被中序遍历的结点
ThreadNode *Lastnode(ThreadNode *p){
    //循环找到最右下结点,不一定是叶结点
    while(p->ltag==0)
        p = p->rchild;
    return p;
}

//在中序线索二叉树中找到结点p的后继点
ThreadNode *Nextonde(ThreadNode *p){
    //右子树中最左下结点
    if(p->rtag==0)
        return Firstnode(p->rchild);
    else 
        return p->rchild;    //rtag==1直接返回后继线索
}

//在中序线索二叉树中找到结点p的前驱结点
ThreadNode *Preonde(ThreadNode *p){
    //右子树中最左下结点
    if(p->rtag==0)
        return lastnode(p->lchild);
    else 
        return p->lchild;    //rtag==1直接返回后继线索
}

//对中序线索二叉树进行中序遍历,利用线索非递归,空间复杂度O(1)
void Inoder(ThreadNode *T){
    for(threadNode *p=Firstnode(T); p!=NULL; p=Nextnode(p))
        visit(p);
}

//对中序线索二叉树进行逆向中序遍历,利用线索非递归,空间复杂度O(1)
void Inoder(ThreadNode *T){
    for(threadNode *p=Lastnode(T); p!=NULL; p=Prenode(p))
        visit(p);
}

树的存储

双亲表示法(顺序存储

每个结点中保存指向双亲“指针”

  • 优点:查指定结点的双亲很方便
  • 缺点:查指定结点的孩子只能从头遍历
#define MAX_TREE_SIZE 100
typedef struct{
    ElemType data;
    int parent;
}PTNode;

typedef struct{
    PTNode nodes[MAX_TREE_SIZE];
    int n;    //结点数
}PTree;

孩子表示法(顺序+链式

  • 顺序存储结点数据,结点中保存孩子链表头指针
  • 优点:找孩子方便;缺点:找父结点不方便
struct CTNode
{
    int child;    //孩子结点在数组中的位置
    struct CTNode *next
};

typedef struct
{
    ElemType data;
    struct CTNode *nextChild;
} CTBox;

typedef struct
{
    CTBox nodes[MAX_TREE_SIZE];
    int n, r;    //结点数和根的位置
} CTree;

孩子兄弟表示法(链式存储

用二叉链表存储树——左孩子右兄弟

孩子兄弟表示法存储的树,从存储视角来看形态上和二叉树类似

考点:树与二叉树的相互转换,本质是用孩子兄弟法存储树

typedef struct CSNode
{
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

森林与二叉树的转换:二叉链表存储森林,森林中各个树的根结点之间视为兄弟关系

树/森林的遍历

  1. 先根遍历
  2. 后根遍历
  3. 层序遍历(队列实现

森林

1.先序遍历:若森林非空,则访问森林第一棵树的根结点,先序遍历第一棵树根结点的子树森林。先序遍历除去第一棵树之后剩余的树构成的森林。(其实就是对每个子树先序)

其它遍历同上

二叉排序/查找树(BST

一棵二叉树或具有如下性质的二叉树:左子树上所有结点的关键字均小于根结点的关键字;右子树上所有结点的关键字均大于根结点的关键字。左子树和右子树又各是一棵二叉排序树。

typedef struct BSTNode
{
    int key;
    struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;

BSTNode *BST_Search(BSTree T, int key)
{
    while(T!=NULL && key!=T->key)
    {
        if(key<T->key)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

BSTNode *BST_Search(BSTree T, int key)
{
    if (T==NULL)
        return NULL;
    if (key==T->key)
        return T;
    else if (key < T->key)
        return BSTSearch(T->lchild, key);
    else
        return BSTSearch(T->rchild, key);
}

int BST_Insert(BSTree &T, int k)
{
    if (T==NULL)
    {
        T = (BSTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if (k == T->key)
        return 0;
    else if (k < T->key)
        return BST_Insert(T->lchild, k);
    else
         return BST_Insert(T->rchild, k);
}

void Creat_BST(BSTree &T, int str[], int n)
{
    T = NULL;
    int i = 0;
    while (i < n)
    {
        BST_Insert(T, str[i]);
        i++;
    }
}

平衡二叉树AVL树

二叉搜索树的查找效率取决于树的高度,因此保持树的高度最小,即可保证树的查找效率.AVL树的存在可以避免二叉树链表化(全都在右结点)导致查找效率降低。

树上任一结点的左子树和右子树的高度差不超过1

结点的平衡因子=左子树高-右子树高

每次调整对象都是最小不平衡子树

  • LL:在A的左孩子的左子树中插入导致不平衡
  • RR:在A的右孩子的右子树中插入导致不平衡
  • LR:在A的左孩子的右子树中插入导致不平衡
  • RL:在A的右孩子的左子树中插入导致不平衡
typedef struct AVLNode
{
    int key;
    int balance;
    struct AVLNode *lchild, *rchild;
}AVLNode, *AVLTree;

查找效率:若树高为h,则最坏情况下查找一个关键字最多需要对比h次。

平衡二叉树的平均查找长度为$O(log_2n)$

哈夫曼树

在含有n个带权结点的二叉树中,其中带权路径长度WPL最小的二叉树称为哈夫曼树,也称为最优二叉树。

哈夫曼树构造

$给定n个权值分别为w_1,w_2,...,w_n的结点$

  1. 将这n个结点分别作为n棵仅含一个结点的二叉树,构成森林F
  2. 构造一个新结点,从F中选取两棵根结点权值最小的树作为新结点的左右子树,并且将新结点的权值置为左右子树上根结点的权值之和
  3. 从F中删除刚刚选出的两棵树,同时将新树加入F中
  4. 重复步骤2和3,直到F中只剩下一棵树

哈夫曼树性质

  1. 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大
  2. 结点总数为2n-1
  3. 不存在度为1的结点
  4. 并不唯一,但WPL必然相同并且最优

哈夫曼编码

字符集中的每个字符作为一个叶子结点,各个字符出现的频度作为结点的权值

固定长度编码:每个字符用相等长度的二进制位表示

可变长度编码:允许对不同字符用不等长的二进制位表示

若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码

$图G由顶点集V和边集E组成,记为G=(V,E)$

$其中V(G)表示图G中顶点的有限非空集:E(G)表示图G中顶点之间的关系(边)集合。$

若V={v_1,v_2,...,v_n},则用|V|表示图G中顶点个数,也称图G的阶

$E=\lbrace (u,v)|u\in V,v\in V \rbrace用|E|表示图G中边的条数$

  • 图不为空,边集可为空
  • 路径:顶点序列
  • 回路:第一个顶点和最后一个顶点相同的路径称为回路
  • 简单路径:在路径序列中,顶点还不重复出现的路径为简单路径
  • 简单回路:除第一个和最后一个顶点以外,无重复顶点
  • 路径长度:路径上边的数目
  • 点到点的距离:从顶点u出发到顶点v的最短路径若存在,则此路径的长度称为从u到v的距离,若u到v根本不存在路径,则记为距离无穷

无向图

  • 顶点v的度:指依附于该顶点的边的条数,记为TD(v)
  • 若从顶点v到顶点w有路径存在,则称v和w连通
  • 对于n个顶点的无向图G:

    • 若是连通图,最少有n-1条边
    • 非连通图,最多可能有$C^2_{n-1}$条边

有向图

  • 入度是以顶点v为终点的有向边的数目,记为ID(v)
  • 出度是以顶点v为起点的有向边的数目,记为OD(v)
  • 顶点v的度等于入度和出度之和
  • 若从顶点v到顶点w,从w到v都有路径存在,则为强连通

图的存储

  • 邻接矩阵:数组实现的顺序存储,空间复杂度高($O(|V|^2)$),不适合存储稀疏图
  • 邻接表:顺序+链式存储,表示方式并不唯一,空间复杂度,无向图是$O(|V|+2|E|)$,有向图是$O(|V|+|E|)$
  • 十字链表:存储有向图,$O(|V|+|E|)$。
  • 邻接多重表:存储无向图
typedef struct VNode{
    VertexType data;    //顶点信息
    ArcNode *first;        //第一条边/弧
}VNode,AdjList[MaxVertexNum];

//用邻接表存储的图
typedef struct{
    AdjList vertices;
    int vexnum, arcnum;
}ALGraph;

typedef struct ArcNode{
    int adjvex;        //边/弧指向哪个结点
    struct ArcNode *next;
    //InfoType info;    //边权值
}ArcNode;

图的基本操作

Adjacent(G,x,y):判断图G是否存在边x,y

Neighbors(G,x):列出图G中与结点x邻接的边

InsertVertex(G,x):在图G中插入顶点x

DeleteVertex(G,x):从图中删除顶点x

AddEdge(G,x,y)

FirstNeighbor(G,x):求图G中顶点x的第一个邻接点,若有则返回顶点号

NextNeighbor(G,x)

Get_edge_value:权值设置

图的广度优先搜索

对于无向图,调用BFS函数的次数=连通分量数

/**
无向图
**/
bool visited[MAX_VERTEX_NUM];    //访问标记数组

//防止无法遍历完非连通图
void BFSTraverse(Graph G){
    for (i=0; i<G.vexnum; ++i)
        visited[i] = FALSE;
    InitQueue(Q);
    for(i=0; i<G.vexnum; ++i)
        if(!visited[i])
            GFS(GFS(G, i));
}

//从顶点v出发,广度优先遍历图G
void BFS(Graph G, int v){
    visit(v);        //访问初始顶点v
    visited[v] = TRUE;    //对v做已访问标记
    Enqueue(Q, v);
    while(!isEmpty(Q)){
        DeQueue(Q,v);
        for(w=FirstNeighbor(G,v); w>=NextNeighbor(G,v,w)){
            //检测v所有邻接点
            if(!visited(w)){
                visit(w);
                visited(w) = TRUE;
                EnQueue(Q, w);
            }
        }
    }
}

图的深度优先遍历

bool visited[MAX_VERTEX_NUM];    //访问标记数组

void DFSTraverse(Graph G){
    for(v=0; v<G.vexnum; ++v)
        visited[v] = FALSE;
    for(v=0; v<G.vexnum; ++v)
        if(!visited[v])
            DFS(G,v);
}
void DFS(Graph G, int v){
    visit(v);
    visited[v] = TRUE;
    for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))
        if(!visited[w]){
            DFS(G,w);
        }
}

最小生成/代价树(MST)

对于一个带权连通无向图G=(V,E),生成树不同,每棵树的权值之和也不同。设R为G的所有生成树的集合,若T为R中边的权值之和最小的生成树,则称T为G的MST

  • 最小生成树可能有多个,但最小权值唯一
  • 只有连通图才有最小生成树

Prim算法

从某一个顶点开始构建树,每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入

$O(|V| ^2)$,适用于边稠密图

Kruskal算法

每次选择一条权值最小的边,使这条边的两头连通(原本已经连通的就不选),直到所有结点连通

$O(|E|log_2|E|)$,适用于边稀疏图

最短路径

BFS求无权图(每条边权值为1)的单源最短路径

void BFS_MIN_Distance(Gragh G, int u){
    //d[i]表示u到i结点的最短路径
    for(int i=0; i<G.vexnum; ++i){
        d[i] = 0;    //init orginal long
        path[i] = -1;    //最短路径从哪个顶点过来
    }
    d[u] = 0;
    visited = TRUE;
    EnQueue(Q, u);
    while(!isEmpty(Q)){
        DeQueue(Q. u);
        for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))
            if(!visited[w]){        //w为u的尚未访问邻接顶点
                d[w] = d[u] + 1;
                path[w] = u;
                visited[w] = TRUE;
                EnQueue;
        }
    }
}

Dijstra算法

计算带权最短路径,$O(|V| ^2)$,n-1轮处理,每次都O(n),不适合用于带负权值的带权图

Floyd算法

求出每一对顶点之间的最短路径;无法解决带有负权回路的图

//...根据图的信息初始化矩阵A(无中转点带权距离)和path(记录中转点)
for(int k=0; k<n; k++){        //考虑以Vk为中转点
    for(int i=0; i<n; i++){    //遍历整个矩阵,i行j列
        for(int j=0; j<n; j++){
            if(A[i][j]>A[i][k]+A[k][j]){    //以Vk为中转点点路径更短
                A[i][j] = A[i][k]+A[k][j];    //更新最短路径长度
                path[i][j] = k;                //中转点
            }
        }
    }
}

有向无环图DAG

运算符处理

  1. 把各个操作数不重复地排成一排
  2. 标出各个运算符的生效顺序
  3. 按顺序加入运算符,注意分层
  4. 自底向上逐层检查同层的运算符是否可以合并

拓扑排序

AVO网:Activity On Vertex Network,用顶点表示活动的网

用DAG表示一个工程,顶点表示活动,有向边$<V_i,V_j>$表示活动$V_i$必须比$V_j$先活动

实现

  1. 从AOV网选择一个没有前驱(入度0)的顶点并输出
  2. 从网中删除该顶点和所有以它为起点的有向边
  3. 重复第一步和第二步直到当前AOV网为空或当前网中不存在无前驱的顶点为止
#define MaxVertexNum 100    //图中顶点数目的最大值
typedef struct ArcNode{        //边表结点
    int adjvex;                //该弧所指向的顶点的位置
    struct ArcNode *nextarc;
    //Infotype info;        //网的边权值
}ArcNode;

typedef struct VNode{        //顶点表结点
    VertexType data;
    ArcNode *firstarc;
}VNode,AdjList[MaxVertexNum];

typedef struct{
    AdjList vertices;        //邻接表
    int vexnum,arcnum        //图的顶点数和弧数
}Graph;

bool TopologicalSort(Graph G){
    InitStack(S);            //初始化栈,存储入度为0的顶点
    for(int i=0; i<G.vexnum; i++)
        if(indegree[i]==0)
            Push(S,i);
    int count = 0;            //记录当前已经输出的顶点数
    while(!IsEmpty(S)){        //栈不空,则存在入度为0的顶点
        Pop(S, i);
        print[count++] = i;
        for(p=G.vertices[i].firstac; p; p=->nextarc){
            //将所有i指向的顶点的入度减1,并且将入度减为0的顶点压入栈S
            v = p->adjvex;
            if(!(--indegree[v]))
                Push(S, v);        //入度为0则入栈
        }
    }
    if(count<G.vexnum)
        return false;        //失败,有向图中有回路
    else
        return true;
}

逆拓扑排序DFS实现

DFSTraverse(Graph G){
    for(v=0; v<G.vexnum; ++v)
        visited[v] = FALSE;
    for(v=0; v<G.vexnum; ++v)
        if(!visited[v])
            DFS(G, v);
}

void DFS(Graph G, int v){
    visit(v);
    visited[v] = TRUE;
    for(w=FirstNeigbor(G,v); w>=0; w=NextNeighbor(G,v,w))
        if(!visited[w])
            DFS(G, w);
}

关键路径

AOE网:Activity On Edge Network;在带权有向图中,以顶点表示事件,以有向边表示活动,边上的权值表示完成该活动的开销,称为用边表示活动的网络

  • 只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始
  • 只有在进入某顶点的各有向边所代表的活动都已结束时,该顶点所代表的事件才能发生
  • 有些活动可以并行进行
  • 在AOE网中仅有一个入度为0的顶点,称为源点,它表示整个工程的开始
  • 仅有一个出度为0顶点称为汇点,表示整个工程的结束

关键路径:从源点到汇点的有向路径可能有多条,所有路径中具有最大路径长度的路径叫做关键路径,关键路径上的活动称为关键活动。完成整个工程的最短时间就是关键路径的长度,若关键活动不能按时完成,则整个工程完成时间就会延长。当一个关键活动缩短到一定程度,可能会变成非关键活动

步骤

  1. 求所有事件的最早发生时间ve
  2. 求所有事件的最迟发生时间vl
  3. 求所有活动的最早发生时间e
  4. 求所有活动的最迟发生时间l
  5. 求所有活动的时间余量d

查找

在数据集合中寻找满足某种条件的数据元素的过程称为查找

  • 查找表(查找结构):用于查找的数据集合称为查找表,它由同一类型的数据元素或记录组成。常见操作:

    • 查找符合条件的数据元素
    • 插入、删除某个元素
  • 关键字:数据元素中唯一标识该元素的某个数据项的值,使用基于关键字的查找,查找结果应该是唯一的
  • 查找长度:在查找运算中,需要对比关键字的次数
  • 平均查找长度ASL:所有查找过程中进行关键字的比较次数的平均值,ASL数量级反应了算法的时间复杂度

顺序/线性查找

typedef struct{
    ElemType *elem;
    int TableLen;
}SSTable;

//顺序查找
int Search_Seq(SSTable ST, ElemType key){
    ST.elem[0] = key;                        //哨兵
    int i;
    for(i=ST.TableLen; ST.elem[i]!=key; --i);//从后往前找
    return i;
}

二分查找

仅适用于有序的顺序表

typedef struct{
    ElemType *elem;
    int TableLen;
}SSTable;

int Binary_Search(SSTable L, ElemType key){
    int low=0, hight=L.TableLen-1, mid;
    while(low<=high){
        mid = (low+high)/2;
        if(L.elem[mid]==key)
            return mid;
        else if(L.elem[mid]>key)
            high = mid-1;
        else
            low = mid+1;
    }
    return -1;
}
  • 若当前low和high之间有奇数个元素,则mid分隔后,左右两部分元素个数相等
  • 若当前low和high之间有偶数个元素,则mid分隔后,左部分元素比右边少一个
  • 二分查找的判定树中,若$mid=\lfloor(low+high)/2\rfloor$,则对于任何一个结点必有:右子树结点数-左子树结点数=0或1,二分查找树一定是平衡二叉树

多路平衡查找树/B树

规定对于任何一个结点,其所有子树的高度都要相同,否则树太高,查询层数多,效率下降

B树中所有结点的孩子个数的最大值称为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树:

  1. 树中每个结点至多有m棵子树,即至多含有m-1个关键字
  2. 若根结点不是终端结点,则至少有两棵子树
  3. 除根结点外的所有非叶结点至少有m/2棵子树,即至少含有m/2-1关键字
  4. 所有叶结点出现在同一层次上,并且不带信息:可视为外部结点或类似于折半查找判定树的查找失败点,实际上这些结点不存在,指向这些结点的指针为空

B+树

可由分块排序类比;一棵m阶的B+树满足以下条件

  1. 每个分支结点最多有m棵子树
  2. 非叶根结点至少有两棵子树,其它每个分支结点至少有m/2棵子树
  3. 结点的子树个数与关键字个数相等
  4. 所有叶结点包含全部关键字及指向相应记录的指针,叶结点中将关键字按大小顺序排序,并且相邻叶结点按大小顺序相互链接
  5. 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针
  6. 无论查找成功与否,最终一定都要走到最下面一层

散列查找

散列表Hash Table:数据元素的关键字与其存储地址直接相关

链接法处理:把所有同义词放在同一链表中,数组位置存指针

装填因子$\alpha = 表中记录树/散列表长度$

常见散列函数

除留余数法:H(key)=key%p 散列表表长m,取一个不大于m但最接近于m的质数,为了让不同关键字的冲突尽可能地少

直接定址法:H(key)=key或者a*key+b;适合关键字的分布基本连续的情况,否则分布不连续,空位较多,造成存储空间浪费

数字分析法:选取数码分布较为均匀的若干单位作为散列地址

平方取中法:取关键词的平方值的中间几位作为散列地址

开放定址法

可存放新表项的空闲地址既向它的同义词表项开发,又向非同义词开放;

m表示散列表表长,d为增量序列

$H_i=(H(key)+d)\%m$ ,$i=0,1,2,...,k(≤m-1)$

  1. 线性探测:发冲突时每次往后探测相邻的下一单元是否为空;
  2. 平方探测法:$d_i=0^2,1^2,-1^2,2^2,...k^2,-k^2$

排序

排序算法的分类

  • 内部排序:数据都在内存中
  • 外部排序:数据太多,无法全部放入内存,放在磁盘

插入排序

每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列中,直到全部记录插入完成

void InsertSort(int A[], int n){
    int i,j;
    for(i=2; i<n; i++)
        if(A[i]<A[i-1]){
            A[0] = A[i];
            for(j=i-1; A[0]<A[j]; --j)
                A[j+1] = A[j];
            A[j+1] = A[0];
        }
}

void InsertSort(int A[], int n){
    int i,j,low,high,mid;
    for(i=2; i<=n; i++){
        A[0] = A[i];
        low= 1;ß
        high = i-1;
        while(low<high){
            mid = (low+high) / 2;
            if(A[mid]>A[0])
                high = mid - 1;
            else
                low = mid + 1;
        }
        for(j=i-1; j>=high+1; --j)
            A[j+1] = A[j];
        A[high+1] = A[0];
    }
}

希尔排序

先将待排序表分割成若干形如$L[i,i+d,i+2d,...i+kd]$的“特殊”子表,对各个子表分别进行直接插入排序,缩小增量d,重复上述过程直到d=1

只能用于顺序表,不稳定

void ShellSor(int A[], int n){
    int d,i,j;
    for(d=n/2; d>=1; d=d/2)
        for(i=d+1; i<=n; ++i)
            if(A[i]<A[i-d]){
                A[0] = A[i];
                for(j=i-d; j>0 && A[0]<A[j]; j -=d)
                    A[j+d] = A[j];
                A[j+d] = A[0];
            }
}

冒泡排序

void swap(int &a, int &b){
    int temp = a;
    a = b;
    b = temp;
}

void BubbleSort(int A[], int n){
    for(int i=0; i<n-1; i++){
        bool flag = false;
        for(int j=n-1; j>i; j--){
            if(A[j-1]>A[j]){
                swap(A[j-1]>A[j]);
                flag=true;
            }
        }
        if(flag==false)
            return;
    }
}

快速排序

int Partition(int A[], int low, int high){
    int pivot=A[low];        //第一个元素作为枢轴
    while(low<high){
        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];
        while(low<high && A[high]<=pivot)
            ++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void QuickSort(int A[], int low, int high){
    if(low<high){
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotops-1);
        QuickSort(A, pivotops-1, high);
    }
}

堆排序

每一趟将堆顶元素加入有序子序列(与待排序序列中的最后一个元素交换)并将待排元素序列再次调整为大根堆;$O(nlog_2 n)$;不稳定

若n个关键字序列$L[1...n]$满足下面某一条性质,则称为堆Heap

  1. 若满足:$L(i)≥L(2i)且L(i)≥L(2i+1),(1≤i≤n/2)$——大根/大顶堆
  2. 若满足:$L(i)≤L(2i)且L(i)≤L(2i+1),(1≤i≤n/2)$——小根/小顶堆

逻辑上可以理解为顺序存储的完全二叉树,大根堆:完全二叉树中,根≥左、右;小根堆则是根≤左、右。非终端结点编号i≤n/2

存储上看,是数组

void BuildMaxHeap(int A[], int len){
    for(int i=len/2; i>0; i--)        //从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
}

//将以k为根堆子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
    A[0] = A[k];
    for(int i=2*k; i<=len; i*2){
        if(i<len && A[i]<A[i+1])
            i++;
        if(A[0]>=A[i])
            break;
        else{
            A[k] = A[i];
            k = i;
        }
    }
    A[k] = A[0];
}

void HeapSort(int A[], int len){
    BuildMaxHeap(A, len);        //初始建堆
    for(int i=len; i>1; i--){    //堆顶元素和堆底元素交换
        swap(A[i], A[1]);
        HeadAdjust(A, 1, i-1);    //把剩余的待排序元素整理成堆
    }
}

归并排序

$O(nlog_2n)$

int *B = (int *)malloc(n*sizeof(int));//辅助数组B

void Merge(int A[], int low, int mid, int high){
    int i, j, k;
    for(k=low; k<=high; k++)
        B[k] = A[k];
    for(i=low, j=mid+1, k=i; i<=mid && j<=high; k++){
        if(B[i]<=B[j])
            A[k] = B[i++];        //将较小值复制到A中
        else
            A[k] = B[j++];
    }
    while(i<=mid)
        A[k++] = B[i++];
    while(j<=high)
        A[k++] = B[j++];
}

void MergeSort(int A[], int low, int high){
    if(low<high){
        int mid = (low+high)/2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        MergeSort(A, mid, high);
        
    }
}

基数排序

通常基于链式存储实现

假设长度为n的线性表中每个结点$a_j的关键字由d元组(k_j^{d-1},k_j^{d-2},..,k_j^1,k_j^0)组成。其中0≤k_j^i≤r-1,(0≤j<n,0≤i≤d-1),r称为基数$

基数排序得到递减序列的过程如下

  1. 初始化:$设置r个空队列,Q_{r-1},Q_{r-2},...,Q_0$按照各个关键字位 权重递增的次序,对d个关键字位分别做“分配”和“收集” ,例如个、十、百、千
  2. 分配:顺序扫描各个元素,若当前处理的关键字位等于x,则将元素插入$Q_X$队尾
  3. 收集:把$Q_{r-1},Q_{r-2},...,Q_0$各个队列中的结点依次出队并链接
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode, *LinkLists;

typedef struct{
    LinkNode *front, *rear;
}LinkQueue;
  • 需要r个辅助队列,空间复杂度$O(r)$,时间复杂度$O(d*(n+r))$
  • 基数排序是稳定的
  • 适合解决关键字方便拆分为d组的且d较小;每组关键字的取值范围不大,即r比较小;数据元素个数n大

外部排序

外存与内存的数据交换

内存读磁盘数据,把数据写进磁盘。磁盘读写以“块”为单位。

构造初始“归并段”,归并排序每次读入两个有序段,在内存中排序到输出缓冲区,每当一块输入缓冲区空了之后需要立即用下一段有序段补上,否则归并排序会出现错误

读取外存最耗时间

优化:多路归并

对于r个初始归并段,做k路归并,则归并树可用k叉树表示

若树高为h,则归并趟数=$h-1=r[log_kr]向上取整$

若能增加初始归并段段长度,则可减少初始归并段数量r

k越大,r越小,归并趟数越少,读写磁盘次数越少

败者树

k路归并,第一次构造败者树需要对比关键字k-1次,选出最小元素,只需要对比关键字$\lceil log_2k \rceil$次

置换 选择排序

设初始待排文件FI,初始归并段输出文件为FO,内存工作区为WA,FO和WA到初始状态为空,WA可容纳w个记录。置换 选择算法的步骤如下

  1. 从FI中输入w个记录到工作区WA
  2. 从WA中选出其中关键字取最小的记录,几位MINIMAX
  3. 将MINIMAX记录输出到FO中去
  4. 若FI不空,则从FI输入下一个记录到WA中
  5. 从WA中所有关键字比MINIMAX记录到关键字大大记录中选出最小关键字记录,作为新的MINIMAX记录
  6. 重复3~5,直至在WA中选不出新的MINIMAX记录为止,由此得到一个初始归并段,输出一个归并段的结束标志到FO中
  7. 重复2~6,直至WA为空,由此得到全部初始归并段

最佳归并树

  • 理论基础:每个初始归并段对应一个叶子结点,把归并段的块数作为叶子的权值;归并树的WPL=树中所有叶结点的带权路径长度之和;归并过程中磁盘I/O次数=归并树的WPL*2
  • k叉归并的最佳归并树一定是严格k叉树,即树中只有度为k、度为0的结点
  • 补充虚段:

    • 若(初始归并段数量-1)% (k-1)= 0,刚好可以构成严格k叉树,不需要添加虚段
    • 若初始归并段数量-1)% (k-1)= u ≠0,则需要补充(k-1)-u个虚段
  • 构造k叉哈夫曼树:每次选择k个根结点权值最小的树合并,并将k个根结点的权值之和作为新的根结点的权值
Last modification:March 4th, 2022 at 10:23 pm
如果觉得我的文章对你有用,请随意赞赏
END
本文作者:
文章标题:C语言数据结构
本文地址:http://feiqiuz.com/index.php/archives/10/
版权说明:若无注明,本文皆MixZou的小窝原创,转载请保留文章出处。