第二章 线性表

线性表的基本操作

  InitList(&L): 初始化表。构建一个空线性表L，分配内存空间
  DestroyList(&L): 销毁操作。销毁线性表，并释放线性表L所占用的内存空间
  ListInsert(&L,i,e): 插入操作。在表L中的第i个位置插入指定元素e
  ListDelete(&L,i,&e): 删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值
  LocateElem(L,e): 按值查找操作。在表L中查找具有给定关键字值的元素
  GetElem(L,i): 按位查找操作。获取表L中第i个位置的元素的值
  其他常用操作：
  Length(L): 求表长。返回线性表L的长度，即L中数据元素的个数
  PrintList(L): 输出操作。按前后顺序输出线性表L的所有元素值
  Empty(): 判空操作。若L为空表，则返回true，否则返回false

顺序表的定义

静态分配

#include <stdio.h>
  #define MaxSize 10       //定义最大长度
  typedef struct{
      ElemType data[MaxSize];    //用静态的“数组”存放数据元素
      int length;    //顺序表的当前长度
  }SeqList;    //顺序表的类型定义（静态分配方式）
  //基本操作——初始化一个顺序表
  void InitList(SqList &L){
      for(int i=0; i<MaxSize; i++)   
          L.data[i]=0;    //将所有数据元素设置为默认初始值
      L.length=0;    //顺序表初试长度为0
  }        
  int main(){
      SeqList L;    //声明一个顺序表
      InitList(L);    //初始化顺序表
      ......
      return 0;
  }

动态分配

#include <stdlib.h>
  #define InitSize 10    //默认的最大长度
  typedef struct{
      int *data;    //指示动态分配数组的指针
      int MaxSize;    //顺序表的最大容量
      int length;    //顺序表的当前长度
  }SeqList;
  void InitList(SeqList &L){
      //用 malloc 函数申请一片连续的存储空间
      L.data = (int *)malloc(InitSize*sizeof(int));
      L.length = 0;
      L.MaxSize = InitSize;
  }
  //增加动态数组的长度
  void IncreaseSize(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;    //顺序表最大长度增加 len
      free(p);    //释放原来的内存空间
  }
  int main(){
      SeqList L;    //声明一个顺序表
      InitList (L);    //初始化顺序表
      ...... 
      IncreaseSize(L,5);
      return 0;
  }

顺序表的基本操作

插入操作

#define MaxSize 10    //定义最大长度
  typeof struct{
      int data[MaxSize];    //用静态“数组”存放数据元素
      int length;    //顺序表的当前长度
  }SeqList;    //顺序表的类型定义
  bool ListInsert(SeqList &L,int i,int e){
      if(i<1 || i>L.length+1)    //判断i的范围是否有效
          return false;
      if(L.length >= MaxSize)    //当前存储空间已满，不能插入
          return false;
      for(int i=L.length; j>=i; j--)    //将第i个元素及之后的元素后移
          L.data[j] = L.data[j-1];
      L.data[i-1]=e;    //在第i个位置放入e
      L.length++;    //长度加1
      return true;
  }

删除操作

bool ListDelete(SeqLizt &L,int i,int &e){
      if(i<1 || i>L.length)    //判断i的范围是否有效
          return false;   
      e = L.data[i-1];    //将被删除的元素赋给e
      for(int j=i; j<L.length; j++)    //将第i个位置后的元素前移
          L.data[j-1] = L.data[j];
      L.length--;    //线性表长度-1
      return true;
  }
  int main(){
      SeqList L;
      InitList(L);
      ......
      int e = -1;
      if (ListDelete(L,3,e))
          printf("已删除第3个元素，删除元素值为=%d\\n",e);
      else
          printf("位序i不合法，删除失败\\n");
      return 0;
  }

查找操作

按位查找
GetElem(L,i);        获取表中第i个位置的元素的值

#define MaxSize 10    //定义最大长度
  typedef struct{
      ElemType data[MaxSize];    //用静态的“数组”存放数据元素（静态分配）
      or
      ElemType *data;    //动态分配
      int length;    //顺序表的当前长度
  }SeqList;    //顺序表的类型定义（静态分配方式）
  ElemType GetElem(SeqList L, int i){
      return L.data[i-1];
  }

按值查找
LocateElem(L,e); 在表L中查找具有给定关键字的值

#define InitSize 10
  typedef struct{
      ElemType *data;
      int MaxSize;
      int length;
  }SeqList;
  //在顺序表L中查找第一个元素值等于e的元素，并返回其位序
  int LocateElem(SeqList L, ElemType e){
      for(int i=0; i<L.length; i++)
          if(L.data[i] == e;
              return i+1;
      return 0;
  }

单链表上基本操作的实现

头插法建立链表

LinkList List_HeadInsert(LinkList &L){  //逆向建立单链表 
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));//创建头结点 
    L->nest = NULL;                      //初始为空链表 
    scanf("%d",&x);                       //输入结点的值 
    while(x!=9999){                     //输入9999表示结束 
        s=(LNode*)malloc(sizeof(LNode));//创建新结点 
        s->data = x;
        s->next = L->next;
        L->next = s;                 //将新结点插入表中，L为头指针 
        scanf("%d",&x);
    }
    return L;
  }

尾插法建立链表

LinkList List_TailInsert(LinkList &L){  //正向建立单链表 
    int x;                              //设ElemType为整型 
    L = (LinkList)malloc(sizeof(LNode));//建立头结点 
    LNode *s, *r=L;                     //r为表尾指针 
    scanf("%d",&x);                       //输入结点的值 
    while(x!=9999){                     //输入9999表示结束 
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r=s;                            //r指向新的表尾结点 
        scanf("%d",&x);
    } 
    r->next->NULL;                        //尾结点指针置空 
    return L;
  }

 按序号查找结点

//按位查找，返回第i个元素（带头结点）
  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){   //循环找到第i个结点 
        p = p->next;
        j++;
    }
    return p;
  }

按值查找表结点

//按值查找，找到数据域==e的结点
  LNode *LocateElem(LinkList L, ElemType e){
    LNode *p = L->next;
    //从第1个结点开始查找数据域为e的结点
    while(p!=NULL && p->data!=e)
        p = p->next;
    return p;   //找到后返回该结点指针，否则返回NULL 
  }

插入结点操作

在第i个位置插入元素e（带头结点）

//在第i个位置插入元素e（带头结点） 
  bool ListInsert(LinkList &L,int i, ElemType e){
    if(i<1)
        return false;
    LNode *p;   //指针p指向当前扫描到的结点 
    int j=0;    //当前p指向的是第几个结点 
    p = L;      //L指向头结点，头结点是第0个结点（不存数据） 
    while(p!=NULL && j<i-1){ //循环找到第 i-1 个结点 
        p=p->next;
        j++;
    }
    if(p==NULL)     //i值不合法 
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s; //将结点s连到p之后 
    return true;    //插入成功 
  }

在第i个位置插入元素e（不带头结点）

//按位序插入（不带头结点）
  bool ListInsert (&L, int i, ElemType e){
    if(i<1)
        return false;
    if(i==1){   //插入第1个结点的操作与其他结点不同 
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;  //头指针指向新结点 
        return true;
    }
    LNode *p;   //指针p指向当前扫描到的结点 
    int j=1;    //当前p指向的是第几个结点 
    p = L;      //p指向第1个结点（注意：不是头结点） 
    while(p!=NULL && j<i-1){ //循环找到第i-1个结点 
        p = p->next;
        j++;
    }
    if(p==NULL)     //i值不合法 
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;    //插入成功 
  }

指定结点的前插、后插操作：

//前插操作：在p结点之前插入元素e
  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连到p之后 
    s->data = p->data;    //将p中元素复制到s中 
    p->data = e;     //p中元素覆盖为e 
    return true;
  }

//后插操作：在p结点之后插入元素e
  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保存数据元素e 
    s->next = p->next;
    p->next = s; //将结点s连到p之后 
    return true;
  }

//在第i个位置插入元素e（带头结点） 
  bool ListInsert(LinkList &L, int i, ElemTypee e){
    if(i<1)
        return false;
    LNode *p;    //指针p指向当前扫描到的结点
    int j=0;     //当前p指向的是第几个结点
    p = L;       //L指向头结点，头结点是第0个结点（不存数据）
    while(p!=NULL && j<i-1){    //循环找到第 i-1 个结点
        p = p->next;
        j++;
    }
    return InsertPriorNode(p,e);
    or
    return InsertNextNode(p,e);
  }

删除结点操作 

//删除指定结点p
  bool DeleteNode (LNode *p){
    if(p==NULL)
        return false;
    LNode *q = p->next;      //令q指向*p的后继结点 
    p->data = p->next->data;//和后继结点交换数据域 
    p->next = q->next;        //将*q结点从链中“断开” 
    free(q);                //释放后继结点的存储空间 
    return true;
  }

求表长操作

//求表的长度
  int Length(LinkList L){
    int len = 0;    //统计表长 
    LNode *p = L;
    while(p->next != NULL){
        p = p->next;
        len++;
    }
    return len;
  }

双链表

双链表的初始化

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; 
  } 
  void testDLinkList(){
    //初始化双链表
    DLinklist L;
    InitDLinkList(L);
    ...... 
  }

双链表的插入（后插）

//在p结点之后插入s结点
  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; //如果p结点后有后继节点 
    s->prior = p;
    p->next = s;
    return true; 
  }

双链表的删除（后删）

//删除p结点的后继结点
  bool DeleteNextDNode(DNode *p){
    if(p == NULL)   return false;
    DNode *q = p->next;      //找到p的后继结点q
    if(q == NULL)   return false;   //p没有后继 
    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;   //头指针指向NULL 
  }

双链表的遍历

//后向遍历
  while(p!=NULL){
    //对结点p做相应处理，如打印
    p = p->next; 
  } 
  //前向遍历
  while(p!=NULL){
    //对结点p做相应处理
    p = p->prior;
  }
  //前向遍历（跳过头结点） 
  while(p->prior!=NULL){
    //对结点p做相应处理
    p = p->prior;
  }

循环链表

循环单链表

typedef struct LNode{   //定义单链表结点类型 
    ElemType data;      //每个结点存放一个数据元素 
    struct LNode *next; //指针指向下一个结点 
  }LNode, *LinkList;
  //初始化一个循环单链表
  bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode)); //分配一个头结点 
    if(L==NULL)         //内存不足，分配失败 
        return false;
    L->next = L;     //头结点next指向头结点 
    return true;
  }
  //判断循环单链表是否为空
  bool Empty(LinkList L){
    if(L->next == L)
        return true;
    else
        return false;
  } 
  //判断结点p是否为循环单链表的表尾结点
  bool isTail(LinkList L, LNode *p){
    if(p->next == L)
        return true;
    else
        return false;
  }

循环双链表

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 = L;        //头结点的 prior 指向头结点 
    L->next = L;     //头结点的 next 指向头结点 
    return true;
  } 
  void testDLinkList(){
    //初始化循环双链表
    DLinklist L;
    InitDLinkList(L);
    ......
  }
  //判断循环双链表是否为空
  bool Empty(DLinklist L){
    if(L->next == L)
        return true;
    else
        return false;
  } 
  //判断结点p是否为循环双链表的表尾结点
  bool isTail(DLinklist L, DNode *p){
    if(p->next == L)
        return true;
    else
        return false;
  }

双链表的插入

//在p结点之后插入s结点
  bool InsertNextDNode(DNode *p, DNode *s){
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
  }

双链表的删除

//删除p的后继结点q
  p->next = q->next;
  q->next->prior = p;
  free(q);

静态链表

代码定义静态链表

#define MaxSize 10  //静态链表的最大长度 
  struct Node{      //静态链表结构类型的定义 
    ElemType data;  //存储数据元素  
    int next;       //下一个元素的数组下标 
  };
  typeof struct Node SLinkList [MaxSize];

第三章 栈、队列和数组

栈的顺序存储

栈的初始化

//初始化栈
  void InitStack(SqStack &S){
    S.top = -1;     //初始化栈顶指针 
  } 
  void testStack(){
    SqStack S;  //声明一个顺序栈（分配空间）
    InitStack(S);
    ...... 
  } 
  //判断栈空
  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.top = S.top+1;        //指针先+1 
    S.data[S.top] = x;      //新元素入栈 
    return true; 
  }

出栈操作

//出栈操作
  bool Pop(SqStack &S,ElemType &x){
    if(S.top == -1)     //栈空，报错
        return false;
    x = S.data[S.top];  //栈顶元素先出栈 
    S.top = S.top-1;    //指针再-1 
    return true;
  }

读栈顶元素操作

//读栈顶元素操作 
  bool Pop(SqStack &S,ElemType &x){
    if(S.top == -1)     //栈空，报错
        return false;
    x = S.data[S.top];  //x记录栈顶元素   
    return true;
  }

共享栈

//共享栈
  #define MaxSize 10            //定义栈中元素的最大个数 
  typedef struct{
    ElemType data[MaxSize]; //静态数组存放栈中元素 
    int top0;               //0号栈栈顶指针 
    int top1;               //1号栈栈顶指针
  }ShStack; 
  //初始化栈
  void InitStack(ShStack &S){
    S.top0 = -1;
    S.top1 = MaxSize;
  }

 栈的链式存储

链栈的定义

typedef struct Linknode{
    ElemType data;          //数据域 
    struct Linknode *next;  //指针域 
  }*LiStack;                    //栈类型定义

链栈的进栈、出栈操作

对应头插法建立单链表（进栈）、单链表的删除操作（出栈）

队列的顺序实现

队列的初始化

#define MaxSize 10  //定义队列中元素的最大个数
  typedef struct{
    ElemType data[MaxSize]; //用静态数组存放队列元素
    int front,rear;         //队头指针和队尾指针 
  }SqQueue;
  //初始化队列
  void InitQueue(SqQueue &Q){
    //初始时 队头、队尾指针指向0
    Q.rear = Q.front = 0; 
  } 
  void testQueue(){
    //声明一个队列（顺序存储）
    SqQueue Q;
    InitQueue(Q);
    ...... 
  }
  //判断队列是否为空
  bool QueueEmpty(SqQueue Q) {
    if(Q.rear == Q.front)   //队空条件
        return true;
    else 
        return false; 
  }

入队操作

判断队满：rear == MaxSize?
当队尾等于最大长度时有可能是队满，也有可能存在假溢出(可以>使用循环队列解决这个问题)

//入队操作
  bool EnQueue(SqQueue &Q,ElemType x){
    if(队列已满)
        return false;   //队满则报错
    Q.data[Q.rear] = x;
    Q.rear = Q.rear+1;
    return true; 
  }

循环队列

队列已满的条件：队尾指针的再下一个位置就是队头
即：(Q.rear+1)%MaxSize == Q.front

//判断队列是否为空
  bool QueueEmpty(SqQueue Q){
    if(Q.rear == Q.front)   //队空条件
        return true;
    else
        return false; 
  } 
  //入队
  bool EnQueue(SqQueue &Q,ElemType x){
    if((Q.rear+1)%MaxSize == Q.front)
        return false;           //队满则报错
    Q.data[Q.rear] = x;         //新元素插入队尾 
    Q.rear = (Q.rear+1)%MaxSize; //队尾指针+1取模
    return true; 
  } 
  //出队(删除一个队头元素，并用x返回) 
  bool DeQueue(SqQueue &Q,ElemType &x){
    if(Q.rear == Q.front)
        return false;       //队空则报错 
    x = Q.data[Q.front];
    Q.front = (Q.front+1)%MaxSize;
    return true; 
  } 
  //获得队头元素的值，用x返回
  bool GetHead(SqQueue Q,ElemType &x){
    if(Q.rear == Q.front)
        return false;   //队空则报错
    x = Q.data[Q.front]
    return true; 
  }

判断队列已满/已空
方案一：牺牲一个位置存放队尾指针
方案二：定义size变量，表示队列当前长度
方案三：定义tag变量，表示最近进行的是插入or删除

队列的链式实现

typedef struct LinkNode {   //链式队列结点
    ElemType data;
    struct LinkNode *next; 
  }LinkNode;
  typedef struct{               //链式队列 
    LinkNode *fron,*rear;   //队列的队头和队尾指针 
  }LinkQueue;

队列的初始化

//初始化队列（带头结点）
  void InitQueue (LinkQueue &Q){
    //初始时 front、rear 都指向头结点
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    Q.front->next = NULL;
  } 
  //判断队列是否为空（带头结点）
  bool IsEmpty(LinkQueue Q){
    if(Q.front == Q.rear)
        return true;
    else
        return false;
  } 
  ----------------------------------------
  //初始化队列（不带头结点）
  void InitQueue(LinkQueue &Q){
    //初始时 front、rear 都指向NULL
    Q.front= NULL;
    Q.rear = NULL; 
  } 
  //判断队列是否为空（不带头结点）
  bool IsEmpty(LinkQueue Q){
    if(Q.front == NULL)
        return true;
    else
        return false;
  } 
  void testLinkQueue(){
    LinkQueue Q;    //声明一个队列
    InitQueue(Q);   //初始化队列
    ...... 
  }

入队操作

//新元素入队（带头结点）
  void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    Q.rear->next = s;    //新结点插入到rear之后 
    Q.rear = s;         //修改表尾指针 
  } 
  ------------------------------------------------------- 
  //新元素入队（不带头结点）
  void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data = x;
    s->next = NULL;
    if(Q.front == NULL){    //在空队列中插入第一个元素 
        Q.front= s;         //修改队头队尾指针 
        Q.reat= s;
    }else{
        Q.rear->next = s;    //新结点插入到 rear 之后 
        Q.rear = s;         //修改rear指针 
    }
  }

出队操作

//队头元素出队（带头结点）
  bool DeQueue(LinkQueue  &Q,ElemType &x){
    if(Q.front == Q.rear)
        return false;   //空队
    LinkNode *p = Q.front->next;//p指针指向要删除的结点（队头元素出队）
    x = p->data; //用变量x返回队头元素
    Q.front->next = p->next;  //修改头结点的next指针
    if(Q.rear == p)             //此次是最后一个结点出队 
        Q.rear = Q.front;       //修改 rear 指针 
    free(p);                    //释放结点空间 
    return true;
  }

//队头元素出队（不带头结点）
  bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front == NULL)
        return false;   //空队
    LinkNode *p = Q.front; //p指向此次出队的结点
    x = p->data;        //用变量x返回队头元素
    Q.front = p->next;      //修改front指针
    if(Q.rear == p){       //此次是最后一个结点出队 
        Q.front = NULL;    //front 指向 NULL 
        Q.rear = NULL;     //rear 指向 NULL 
    } 
    free(p);
    return true; 
  }

栈在括号匹配中的应用

算法实现

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;
        if(str[i] == ']' && topElem != '[')
            return false;
        if(str[i] == '}' && topElem != '{')
            return false;
    } 
    return StackEmpty(S);       //检索完全部括号后，栈空说明匹配成功 
  }

匹配失败情况：①左括号单身 ②右括号单身 ③左右括号不匹配

第四章 串

串的存储结构

顺序存储

#define MAXLEN 255      //预定义最大串长为255
  //静态数组实现（定长顺序存储）
  typedef struct{
    char ch[MAXLEN];    //每个分量存储一个字符 
    int length;         //串的实际长度 
  }SString; 
  //动态数组实现（堆分配存储） 
  typedef struct{
    char *ch;       //按串长分配存储区，ch指向串的基地址    
    int length;     //串的长度 
  }HString; 
  HString S;
  S.ch = (char *) malloc(MAXLEN * sizeof(char));
  S.length = 0;

链式存储

typedef struct StringNode{
    char ch;    //每个结点存1个字符
    struct StringNode * next; 
  }StringNode, * String;
  typedef struct StringNode{
    char ch[4]; //每个结点存4个字符
    struct StringNode * next; 
  }StringNode, * String;

基本操作（求子串、串的比较、定位操作）

//求子串（用Sub返回串S的第pos个字符起长度为len的子串） 
  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;
  } 
  //串的比较（若S>T,则返回值>0;若S=T，则返回值=0；若S<T，则返回值<0） 
  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; 
  } 
  //求串在主串中的位置（若S中存在与串T相同的子串，则返回它在主串S中第一次出现的位置；否则函数值为0）
  int Index(SString S, SString T){
    int i=1, n=StrLength(S), m=StrLength(L);
    SString sub;    //用于暂存子串
    while(i<=n-m+1){
        SubString(Sub,s,i,m);
        if(StrCompare(sub,T)!=0)  ++i;
        else return i;  //返回子串在主串中的位置 
    } 
    return 0;   //S中不存在与T相等的子串 
  }

匹配算法

 朴素模式匹配算法

最坏时间复杂度：O(nm)

//朴素模式匹配算法
  int Index(SSring S,SString T){
    int i=1,j=1;
    while(i<=s.length && j<=T.length){
        if(S.ch[i] == S.ch[j]){
            ++i; ++j;   //继续比较后续字符 
        }
        else{
            i=i-j+2;    //i=(i-(j-1))+1 
            j=1;    //指针后退重新开始匹配 
        } 
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0; 
  }

i=i-j+2 的解释：
当i=j=6，模式串与主串不匹配时，i需要回到起始元素的下一个>位置2，j回到1才能进行下一次匹配，即 i-（j-1），i回到1位置>后再加一：i = i -( j-1)+1 = i-j+2

KMP匹配算法

//KMP匹配算法
  int Index_KMP(SSring S,SString T,int next[]){
    int i=1,j=1;
    while(i<=s.length && j<=T.length){
        if(j==0 || S.ch[i] == S.ch[j]){
            ++i; ++j;   //继续比较后续字符 
        }
        else
            j = next[i];    //模式串向后移动 
    }
    if(j>T.length)
        return i-T.length;  //匹配成功 
    else
        return 0; 
  }

第五章 树与二叉树

二叉树的存储结构

顺序存储

#define MaxSize 100
  struct TreeNode{
    ElemType value;     //结点中的数据结构
    bool isEmpty;       //结点是否为空 
  }; 
  TreeNode t[MaxSize];
  for(int i=0; i<MaxSize; i++){
    t[i].isEmpty = true;
  }

链式存储

//二叉树的结点（链式存储）
  struct ElemType{
    int value;
  };
  typedef struct BiTNode{
    ElemType data;      //数据域
    struct BiTNode *lchild,*rchild; //左、右孩子指针 
      (sruct BiTNode *parent;)  //父结点指针 
  }BiTNode,*BiTNode; 
  //定义一棵空树
  BiTree root = NULL;
  //插入根节点
  root = (BiTree) malloc(sizeof(BiTNode));
  root->data = {1};
  root->lchild = NULL;
  root->rchild = NULL;
  //插入新结点
  BiTree *p = (BiTNode *) malloc(sizeof(BiTNode));
  p->data = {2};
  p->lchild = NULL;
  p->rchild = NULL;
  root->lchild = p;  //作为根节点的左孩子

二叉树的遍历和线索二叉树

二叉树的遍历

//先序遍历
  void PreOrder(BiTree T){
    if(T != NULL){
        visit(T);           //访问根节点
        PreOrder(T->lchild);//递归遍历左子树 
        PreOrder(T->rchild);//递归遍历右子树 
    }
  } 
  //中序遍历
  void InOrder(BiTree T) {
    if(T != NULL){
        InOrder(T->lchild);//递归遍历左子树 
        visit(T);           //访问根节点
        InOrder(T->rchild);//递归遍历右子树 
    }
  }
  //后序遍历 
  void PostOrder(BiTree T){
    if(T != NULL){
        PostOrder(T->lchild);//递归遍历左子树 
        PostOrder(T->rchild);//递归遍历右子树
        visit(T);           //访问根节点
    }
  }

例：求树的深度（应用）

int treeDepth(BiTree T){
    if(T == NULL){
        return 0;
    }else{
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        //树的深度 = Max（左子树深度，右子树深度）+ 1
        return l>r? l+1:r+1; 
    }
  }

层序遍历

//层序遍历
  void LevelOrder(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);    //右孩子入队 
    } 
  } 
  typedef struct BiTNode{
    ElemType data;  
    struct BiTNode *lchild,*rchild; 
  }BiTNode,*BiTNode; 
  //链式队列结点
  typedef struct LinkNode{
    BiTNode * data;
    struct LinkNode *next;
  }LinkNode;
  typedef struct{
    LinkNode *front,*rear;  //队头队尾 
  }LinkQueue;

线索二叉树

//线索二叉树结点
  typedef struct ThreadNode{
    ElemType data;
    struct ThreaDNode *lchild,*rchild;
    int ltag,rtag;  //左、右线索标志 
    //ltag == 1，表示lchild指向前驱；ltag == 0，表示lchild指向左孩子
    //rtag == 1，表示rchild指向前驱；rtag == 0，表示rchild指向右孩子
  }ThreadNode,*ThreadTree;

土办法找到中序前驱

//土办法找中序前驱
  void findPre(BiTree){
    if(T!=NULL){
        findPre(T->lchild);
        visit(T);
        findPre(T->rchild);
    }
  } 
  //访问结点p
  void visit(BiTNode *q){
    if(p==q)            //当前访问结点刚好是结点p 
        final = pre;    //找到p的前驱
    else
        pre = q; 
  } 
  //辅助全局变量，便于查找p的前驱
  BiTNode *p;               //p指向目标结点 
  BiTNode * pre = NULL; //指向当前访问结点的前驱 
  BiTNode * final = NULL; //用于记录最终结果

中序线索化

//中序线索化
  //全局变量pre，指向当前访问结点的前驱
  ThreadNode *pre = NULL;
  //中序线索化二叉树T
  void CreateInThread(ThreadTree T){
    pre = NULL;             //初始化pre为NULL 
    if(T!=NULL){            //非空二叉树才能线索化 
        InThread(T);        //中序线索化二叉树 
        if(pre->rchild == NULL)
            pre->rtag = 1;   //处理遍历的最后一个结点 
    }
  } 
  //线索二叉树结点
  typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
  }ThreadNode,*ThreadTree;
  //中序遍历二叉树，一边遍历一遍线索化
  void InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);
        visit(T);
        InThread(T->rchild);
    }
  } 
  void visit(ThreadNode *q){
    if(q->lchild == NULL){   //左子树为空，建立前驱线索 
        q->lchild = pre;
        q->ltag =  1;
    }
    if(pre!=NULL && q->rchild == NULL){
        pre->rchild = q; //建立前驱结点的后驱线索 
        pre->rtag = 1;
    } 
    pre = q;
  }

先序线索化

//先序线索化
  //全局变量pre，指向当前访问结点的前驱
  ThreadNode *pre = NULL;
  //先序线索化二叉树T
  void CreatePreThread(ThreadTree T){
    pre = NULL;                 //pre初始化为NULL
    if(T!=NULL){                //非空二叉树才能线索化 
        PreThread(T);           //先序线索化二叉树 
        if(pre->rchild == NULL)
            pre->rchild = 1; //处理遍历的最后一个结点 
    } 
  }
  //先遍历二叉树，一边遍历一遍线索化
  void PreThread(ThreadTree T){
    if(T!=NULL){
        visit(T);           //先处理根节点 
        if(T->ltag == 0) //lchild不是前驱线索
            PreThread(T->lchild);
        PreThread(T->rchild); 
    }
  } 
  void visit(ThreadNode *q){
    if(q->lchild == NULL){   //左子树为空，建立前驱线索 
        q->lchild = pre;
        q->ltag = 1;
    }
    if(pre!=0 && q->rchild == NULL){
        pre->rchild = q; //建立前驱结点的后继线索 
        pre->rtag = 1;
    }
    pre = q;
  }

后序线索化

//后序线索化
  //全局变量pre，指向当前访问结点的前驱
  ThreadNote *pre = NULL;
  //后序线索化二叉树T
  void CreatPostThread(ThreadTree T){
    pre = NULL;             //pre初始为NULL 
    if(T!=NULL){            //非空二叉树才能线索化 
        PostThread(T);      //后序线索化二叉树 
        if(pre->rchild == NULL)
            pre->rtag = 1;   //处理遍历的最后一个结点 
    } 
  } 
  //后序遍历二叉树，一边遍历一边线索化 
  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 && q->rchild == NULL){
        pre->rchild = q; //建立前驱结点的后继线索
        pre->rtag = 1; 
    }
    pre = q;
  }

  线索二叉树找前驱/后继

中序线索二叉树找中序后继

//中序线索二叉树找中序后继
  //找到以P为根的子树中，第一个被中序遍历的结点
  ThreadNode *Firstnode(ThreadNode *p){
    //循环找到最左下结点（不一定是叶结点）
    while(p->ltag == 0)
        p=p->lchild;
    return p; 
  } 
  //在中序线索二叉树中找到结点p的后继结点
  ThreadNode *Nextnode(ThreadNode *p){
    //右子树中最左下结点
    if(p->rtag == 0)
        return Firstnode(p->rchild);
    else 
        return p->rchild;    //rtag==1直接返回后继线索 
  } 
  //对中序线索二叉树进行中序遍历（利用线索实现的非递归算法）
  void Inorder(ThreadNode *T){
    for(ThreadNode *p=Firstnode(T); p!=NULL; p=Nextnode(p))
        visit(p);
  }

中序线索二叉树找中序前驱 

//中序线索二叉树找中序前驱
  //找到以P为根的子树中，最后一个被中序遍历的结点
  ThreadNode *Lastnode(ThreadNode *p){
    //循环找到最右下的结点（不一定是叶结点）
    while(p->rtag == 0)
        p=p->rchild;
    return p; 
  } 
  //在中序线索二叉树中找到结点p的前驱结点
  ThreadNode *Prenode(ThreadNode *p){
    //左子树中最右下结点
    if(p->ltag == 0)
        return Lastnode(p->lchild);
    else
        return p->lchild;    //ltag==1直接返回前驱线索 
  } 
  //对中序线索二叉树进行逆向中序遍历
  void RevInorder(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 *firstChild;  //第一个孩子 
  }CTBox;
  typedef struct{
    CTBox nodes[mAX_TREE_SIZE];
    int n, r;   //结点数和根的位置 
  }CTree;

孩子兄弟表示法（链式存储）

//孩子兄弟表示法
  typedef struct CSNode{
    ElemType data;      //数据域 
    struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针 
  }CSNode,*CSTree;

树的遍历

先根遍历

//树的先根遍历
  void PreOrder(TreeNode *R){
    if(R!=NULL){
        visit(R);   //访问根节点
        while(R还有下一个子树T)
            PreOrder(T);    //先根遍历下一个子树 
    }
  }

后根遍历

//树的后根遍历
  void PostOrder(TreeNode *R){
    if(R!=NULL){
        while(R还有下一个子树T)
            PostOrder(T);   //后根遍历下一棵子树 
        visit(R);   //访问根节点 
    }
  }

  并查集

基本操作

//并查集的基本操作
  #define SIZE 13
  int UFSets[SIZE]; //集合元素数组
  //初始化并查集
  void Initial(int S[]){
    for(int i=0; i<SIZE; i++)
        S[i] = -1;
  } 
  //Find “查”操作，找x所属集合（返回x所属根节点）
  int Find(int S[],int x){
    while(S[x]>=0)       //循环寻找x的根
        x = S[x];
    return x;           //根的S[]小于0 
  } 
  //Union “并”操作，将两个集合合并为一个 
  void Union(int S[],int Root1,int Root2){
    //要求Root1与Root2是不同的集合
    if(Root1 == Root2)  return;
    //将根Root2连接到另一根Root1下面
    S[Root2] = Root1; 
  }

Union的优化

//Union “并”操作，小树合并到大树
  void Union(int S[],int Root1,int Root2){
    if(Root1 == Root2)  return;
    if(S[Root2]>S[Root1]){       //Root2结点数更少 
        S[Root1] += S[Root2];   //累加节点总数 
        S[Root2] = Root1;       //小树合并到大树 
    }else{
        S[Root2] += S[Root1];   //累加结点总数 
        S[Root1] = Root2        //小树合并到大树 
    }
  }

Find的优化

//Find “查”操作，先找到根节点，再进行“压缩路径” 
  int Find(int S[],int x){
    int root = x;
    while(S[root]>0) root = S[root]; //循环找到根
    while(x != NULL){   //压缩路径 
        int t = S[x];   //t指向x的父节点 
        S[x] = root;    //x直接挂到根节点下 
        x = t;
    } 
    return root;        //返回根结点编号 
  }

第六章 图

图的存储

邻接矩阵法

//邻接矩阵法
  #define MaxVertexNum 100      //顶点数目的最大值 
  typedef struct{
    char Ver[MaxVertexNum];                 //顶点表 
    int Edge[MaxVertexNum][MaxVertexNum];   //邻接矩阵、边表
    int vexnum,arcnum;                      //图的当前顶点数和边数/弧数 
  }MGraph; 
  //邻接矩阵法存储带权图  
  #define MaxVertexNum 100      //顶点数目的最大值 
  #define INFINITY 最大的int值  //宏定义常量“无穷” 
  typedef char VertexType;      //顶点的数据类型 
  typedef int EdgeType;         //带权图中边上权值的数据类型 
  typedef struct{
    VertexType Vex[MaxVertexNum];               //顶点 
    EdgeType Edge[MaxVertexNum][MaxVertexNum];  //边的权 
    int vexnum,arcnum;                          //图的当前顶点数和弧数 
  }MGraph;

邻接表法

//用邻接表存储的图
  typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
  }ALGRaph; 
  //“边/弧” 
  typedef struct ArcNode{
    int adjvex;             //边/弧指向哪个结点 
    struct ArcNode *next;   //指向下一条弧的指针 
    //InfoType info;        //边权值 
  }ArcNode; 
  //顶点
  typedef struct VNode{
    VertexType data;    //顶点信息 
    ArcNode *first;     //第一条边/弧 
  }VNode,AdjList[MaxvertexNum];

图的遍历

广度优先遍历BFS

//广度优先遍历 
  bool visited[MAX_VERTEX_NUM]; //访问标记数组 
  void BFSTraverse(Graph G){        //对图G进行广度优先遍历   
    for(i=0; i<G.vexnum; ++i)     
        visited[i] = FALSE;     //访问标记数组初始化 
    InitQueue(Q);               //初始化辅助队列Q 
    for(i=0; i<G.vexnum; ++i)    //从0号顶点开始遍历  
        if(!visited[i])         //对每个连通分量调用一次BFS 
            BFS(G,i);           //vi未访问过，从vi开始BFS 
  } 
  void BFS(Graph G,int v){      //从顶点v出发，广度优先遍历图G 
    visit(v);                   //访问初始顶点v 
    visited[i] = TRUE;          //对v做已访问标记 
    Enqueue(Q,v);               //顶点v入队列Q 
    while(!isEmpty(Q)){
        DeQueue(Q,v);           //顶点v出队列 
        for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))
            //检测v所有邻接点
            if(!visited[w]){    //w为v的尚未访问的邻接顶点 
                visit(w);       //访问顶点w 
                visited[w]=TRUE;//对w做已访问标记 
                EnQueue(Q,w);   //顶点w入队列 
            }//if
    }//while
  }

深度优先遍历DFS

//深度优先遍历
  bool visited[MAX_VERTEX_NUM]; //访问标记数组
  void DFSTraverse(Graph G){        //对图G进行深度优先遍历 
    for(v=0; v<G.vexnum; ++v)
        visited[v] = FALSE;     //初始化已访问标记数据 
    for(v=0; v<G.vexnum; ++v)    //从v = 0开始遍历 
        if(!visited[w])
            DFS(G,v);
  } 
  void DFS(Graph G,int v){  //从顶点v出发，深度优先遍历G 
    visit(v);               //访问顶点v 
    visited[v] = TRUE;      //设已访问标记 
    for(w=FirstNeighbor(G,v); w>=0; w=NextNeighor(G,v,w))
        if(!visited[w]){    //w为u的尚未访问的邻接顶点 
            DFS(G,w);
        }   //if
  }

图的应用

最短路径问题

BFS算法

//求顶点u到其他顶点的最短路径
  void BFS_MIN_Distance(Graph G,int u){
    //d[i]表示u到i结点最短路径 
    for(i=0; i<G.vexnum; ++i){
        d[i] = ∞;       //初始化路径长度 
        path[i] = -1;   //最短路径从哪个顶点过来 
    } 
    d[u] = 0;
    visited[u] = TRUE;
    EnQueue(Q,u);
    while(!isEmpty(Q)){
        while(!isEmpty(Q)){             //BFS算法主过程 
            DeQueue(Q,u);               //队头元素u出队 
            for(w=FirstNeighbor(G,u); w>=0; w=NextNeighbor(G,u,w))
                if(!visited[w]){        //w为u的尚未访问的邻接顶点 
                    d[w] = d[u]+1;      //路径长度加1 
                    path[w] = u;        //最短路径应从u到w 
                    visited[w] = TRUE;  //设已访问标记 
                    EnQueue(Q,w);       //顶点w入队 
                }//if
        }//while
    }
  }

Dijkstra算法

初始：若从v0开始，令final[0]=true; dist[0]=0; path[0]=-1。
其余顶点final[k]=false; dist[k]=arcs[0][k]; path[k]=(arc[0][k]== ∞)? -1:0
n-1轮处理：循环遍历所有的顶点，找到还没确定最短路径，且dist最小的顶点vi，令final[i]=true。并检查所有邻接自vi的顶点，对于邻接自vi的顶点vj，若final[j]=false 且 dist[i]+arcs[i][j]<dist[j]，则令dist[j]=dist[i]+arcs[i][j];path[j]=i（注：arcs[i][j]表示vi到vj的弧的权值）

Floyd算法

//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;                 //中转点 
            }
        }
    }
  }

拓补排序

//拓补排序
  #define MaxVertexNum 100  //图中顶点数目的最大值
  typedef struct ArcNode{       //边表结点 
    int adjvex;         //该弧所指向的顶点的位置 
    struce ArcNode *nextarc;//指向下一条弧的指针 
    //InfoType info;        //网的边权值 
  }ArcNode;
  typedef struct VNode{     //顶点表结点 
    VertexType data;        //顶点信息 
    ArcNode * firstare;     //指向第一条依附该顶点的弧的指针 
  }VNode,AdjList[MaxvertexNum];
  typedef struct{
    AdjList vertices;       //邻接表 
    int vexnm,arcnum;       //图的顶点数和弧数 
  }Graph;                   //Graph是以邻接表存储的图类型 
  bool TopologicalSort(Graph G){
    InitStack(S);
    for(int i=0 ;i<G.vexnum; i++)
        if(indegree[i] == 0)
            Push(S,i);
    int count=0;
    while(!IsEmpty(S)){
        Pop(S,i);
        print[count++]=i;
        for(P=G.vertices[i].firstarc; p; p->nextarc){
        //将所有i指向的顶点的入度减1，并且讲入度减为0的顶点压入栈S
        v=p->adjvex;
        if(!(--indegree[v])) 
            Push(S,v);  
        }
    }//while
  if(count<G.vexnum)
    return false;
  else
    return true;
  }

//逆拓补排序的实现（DFS算法）
  void DFSTraverse(Graph G){    //对图G进行深度优先遍历 
    for(v=0; v<G.vexnm; v++)
        visited[v]=FALSE;   //初始化已访问标记数据 
    for(v=0; v<G.vexnm; v++)//从v=0开始遍历 
        if(!visited[v])
            DFS(G,v);
  } 
  void DFS(Graph G,int v){  //从顶点v出发，深度优先遍历图G 
    visited[v]=TRUE;        //设已访问标记 
    for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))
        if(!visited[w]){    //w为u的尚未访问的邻接顶点 
            DFS(G,w);
        }//if
    print(v);               //输出顶点 
  }

第七章 查找

基本查找操作

顺序查找

typedef struct{     //查找表的数据结构（顺序表） 
    ElemType *elem; //动态数组基址 
    int TableLen;   //表的长度 
  }SSTable;
  //顺序查找 
  int Search_Seq(SSTable ST,ElemType key){
    int i;
    for(i=0; i<ST.TableLen && ST.elem[i] != key; ++i);
    //查找成功，则返回元素下标；查找失败，则返回-1
    return i==ST.TableLen? -1:i; 
  } 
  //顺序查找(哨兵）
  int Search_Seq(SSTable ST,ElemType key){
    (ST.elem[0] = key;) //哨兵 
    int i;
    for(i=ST.TableLen; ST.elem[i] != key; --i); //引入哨兵时 
    //查找成功，则返回元素下标；查找失败，则返回0 
    return i; 
  }

折半查找

//折半查找
  int Binary_Search(SSTable L, ElemType key){
    int low = 0, high = 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;                      //查找失败，返回-1 
  }

分块查找

//索引表
  typedef struct{
    ElemType maxValue;
    int low,high;
  }Index;
  //顺序表实际存储元素
  ElemType List[100];

树型查找

二叉排序树（BST）

二叉树的查找

//二叉排序树结点
  typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild;
  }BSTNode,*BSTree; 
  //在二叉排序树中查找值为key的结点
  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;
  }

//在二叉排序树中查找值为key的结点（递归实现）
  BSTNode *BSTSearch(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); //在右子树中找 
  }

二叉树的插入

//在二叉排序树插入关键字为k的新结点（递归实现）
  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)     //插入到T的左子树 
        return BST_Insert(T->lchild,k);
    else                    //插入到T的右子树 
        return BST_Insert(T->rchild,k); 
  }

二叉树的构造

//按照 str[] 中的关键字序列建立二叉排序树
  void Creat_BST(BSTree &T,int str[],int n){
    T=NULL;         //初始时T为空树 
    int i=0;
    while(i<n){      //依次将每个关键字插入到二叉排序树中 
        BST_Insert(T,str[i]);
        i++;
    }
  }

第八章 排序

插入排序

直接插入排序

//直接插入排序
  void InsertSort(int A[], int n){
    int i,j,temp;
    for(i=1; i<n; i++)           //将各元素插入已排好序的序列中 
        if(A[i]<A[i-1]){     //若A[i]关键字小于前驱 
            temp = A[i];        //用temp暂存A[i] 
            for(j=i-1; j>=0&&A[j]>temp; --j)  //检查所有前面已排好序的元素 
                A[j+1] = A[j];  //所有大于temp的元素都向后挪位 
            A[j+1] = temp;      //复制到插入位置 
        }
  } 
  //直接插入排序（带哨兵）
  void InsertSort(int A[], int n){
    int i,j;
    for(i=2; i<=n; i++)          //依次将A[2]~A[n]插入到前面已排序序列 
        if(A[i]<A[i-1]){     //若A[i]关键字小于前驱，将A[i]插入有序表 
            A[0] = A[i];        //复制为哨兵，A[0]不存元素 
            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 j,i,low,high,mid;
    for(i=2; i<=n; i++){         //依次将A[2]~A[n]插入前面的已排序序列 
        A[0]=A[i];                  //将A[i]暂存到A[0] 
        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];           //插入操作 
    }
  }

希尔排序

//希尔排序
  void ShellSort(int A[],int n){
    int d,i,j;
    //A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(d=n/2; d>=1; d=d/2)  //步长变化
        for(i=d+1; i<=n; ++i)
            if(A[i]<A[i-d]){ //需要将A[i]插入有序增量子表 
                A[0]=A[i];          //暂存在A[0] 
                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){     //用low、high搜索枢轴的最终位置 
        while(low<high&&A[high]>=pivot)   --high;
        A[low] = A[high];   //比枢轴小的元素移动到左端 
        while(low<high&&A[low]<=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,pivotpos-1);    //划分左子表 
        QuickSort(A,pivotpos+1,high);   //划分右子表 
    }
  }

选择排序

选择排序：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列

简单选择排序

//简单选择排序
  void SelectSort (int A[],int n){
    for(int i=0; i<n-1;i++){     //一共进行n-1躺 
        int min=i;                  //记录最小元素位置 
        for(int j=i+1; j<n; j++) //在A[i...n-1]中选择最小的元素 
            if(A[j]<A[min])  min=j;  //更新最小元素位置 
        if(min!=i) swap(A[i],A[min]);//封装的swap()函数共移动元素3次 
    }
  } 
  //交换
  void swap(int &a,int &b){
    int temp = a;
    a = b;
    b = temp;
  }

堆排序

//建立大根堆
  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];                      //A[0]暂存子树的根结点 
    for(int i=2*k; i<=len; i*=2){    //沿key较大的子结点向下筛选 
        if(i<len&&A[i]<A[i+1])
            i++;                    //取key较大的字结点的下标 
        if(A[0]>=A[i])   break;      //筛选结束 
        else{       
            A[k] = A[i];            //将A[i]调整到双亲结点下 
            k = i;                  //修改k值，以便向下继续筛选 
        }   
    }
    A[k] = A[0];                    //被筛选结点的值放入最终位置 
  } 
  //完整逻辑
  void HeapSort(int A[], int len){
    BuildMaxHeap(A,len);        //初始建堆 
    for(int i=len; i>1; i--){    //n-1躺的交换和建堆过程 
        swap(A[i],A[1]);        //把堆顶元素和堆底元素交换 
        HeadAjdust(A,1,i-1);    //把剩余的待排序元素整理成堆 
    }
  }

归并排序和基数排序

归并排序

//归并排序
  int *B = (int *)malloc(n*sizeof(int)); //辅助数组B
  //A[low...mid]和A[mid+..high]各自排序，将两个部分归并
  void Merge(int A[], int low, int mid, int high){
    int i,j,k;
    for(k=low; k<=high; k++)
        B[k] = A[k];        //将A中所有元素复制到B中
    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++]; 
    }//if 
    while(j<=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);    //对右半部分归并排序
        Merge(A,low,mid,high);      //归并 
    }//if 
  }