数据结构

线性表

线性表：顺序存储——顺序表

链式存储—-单链表，双链表，循环链表—指针实现

静态链表（借助数组实现）

线性表的基本操作：

• InitList(&L)
• Length(L)
• LocateElem(L,e)
• ListInsert(&L,i,e)
• ListDelete(&L,i,&e)
• PrintList(L)
• DestroyList(&L)

注：&是C++中的引用，传入的变量是指针型的变量

函数体内要对传入的指针进行改变，将用到执行变量的引用

C中采用*，指针的效果也可以

顺序表的定义

地址连续的存储单元，依次存储线性表中的数据元素，逻辑上相邻的两个元素在物理位置上也相邻。

#define MaxSize 50//定义线性表的最大长度
typedef struct Node{
    ElemType data[MaxSize];//顺序表的元素
    int length;// 顺序表当前长度   
}SqList;//顺序表的类型定义
一位数组静态分配，动态分配。
静态分配：数组大小和空间已经固定，当空间占满，再加入元素，将产生溢出，导致程序崩溃
动态分配：存储数组的空间在程序执行过程中通过动态分配语句分配的。
一旦数据空间站满，可以另外开辟一块更大的存储空间，替换原来的存储空间。
从而达到扩充存储数组空间的目的
#define InitSize 100
typedef struct Node{
	ElemType *data;
    int MaxSize,length;
}SeqList;
C的动态分配：
L.dada=(ElemType*)malloc(sizeof(ElemType)*InitSize)
C++的动态分配：
L.data=new ElemType[InitSize];

注：顺序表的主要特点：随机访问，通过首地址和元素序号可以再O(1)的时间内

找到指定的元素。

顺序表的存储密度高，每个节点只存储数据元素

顺序比哦啊逻辑上相邻的元素物理上也是相邻。插入和删除需要移动大量元素

顺序表的基本操作 实现

• 插入操作

  bool ListInsert(SqList &L,int i,ElemType e){//本算法实现将元素e插入到顺序表L中第i个位置,注：第i个位置的元素，数组下标是i-1
      if(i<1||i>L.length+1)
          return false;
      if(L.length>=MaxSize)
          return false;
      for(int j=L.lenght;j>=i;j--)//将第i个元素以及后面的元素后移
          L.data[j]=L.data[j-1];
      L.data[i-1]=e;//在位置i处放入e
      L.length++;//线性表长度+1
      return true
  }
  //时间复杂度：O(n)

• 删除操作

  bool ListDelete(SqList &L,int i,ElemType &e){//将顺序表L中第i个位置的元素删除
      if(i<1||i>L.length)
          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;
  }
  //时间复杂度：O(n)

• 按值查找（顺序查找）

  int LocateElem(SqList L,ElemType e){
      //查找顺序表L中值为e的元素，返回元素的位置号，下标为i的元素，是第i+1个位置
      for(int i=0;i<L.length;i++)
          if(L.data[i]==e)
              return i+1;
      return 0;
  }
  //时间复杂度：O(1)

链表

顺序表的插入，删除需要移动大量元素，引入线性表的链式存储。不需要使用地址连续的存储单元

不要求逻辑上相邻的两个元素在物理位置上相邻。

单链表

typedef struct Node{//单链表的节点
    ElemType data;//数据域
    struct Node *next;//指针域
}LNode,*LinkList;

注：用头指针标识一个单链表，如果单链表L，L->next=NULL，表示为一个空表

头结点，头指针区别：

不管带不带头结点，头指针始终只想链表的第一个节点，头结点是一个带头结点链表的第一个节点

通常节点不存储信息。

• 头插法建立单链表

  LinkList CreateList(LinkList &L){
      Node *s;
      int x;
      L=(LinkList)malloc(sizeof(Node));//创建头结点
      L->next=NULL;//头指针为空，初始化为空表
      scanf("%d",&x);//输入节点的值
      while(x!=9999){
          s=(Node*)malloc(sizeof(Node));
          s->data=x;
          s->next=L->next;//s放在L->next是下一个元素之前
          L->next=s;//头指针L->next指向s
          scanf("%d",&x)
      }
      return L;
  }
  //插入时间复杂度：O(1)

• 尾插法建立单链表

  LinkList CreateList(LinkList &L){
      int x;
      L=(LinkList)malloc(sizeof(Node);
      Node *s,*r=L;
      scanf("%d",&x);
      while(x!=9999){
          s=(Node*)malloc(sizeof(Node));
          s->data=x;
          r->next=s;//尾指针r等于L,让r->next指向新插入的节点s
          r=s;//调整尾指针r指向s
          scanf("%d",&x);
      }
      r->next=NULL;
      return L;                   
  }
  //时间复杂度：O(n)

• 按序号查找节点

  Node *GetElem(LinkList L,int i){
      //取出单链表L中第i个位置的节点指针
      int flag=1;
      LNode *p=L->next;
      if(i==0)
          return L;
      if(i<1)
          return NULL;
      while(p&&i>flag){//从第i个节点开始找，查找第i个节点
          p=p->next;//import step循环。
          flag++;
      }
      return p;//返回第i个节点的指针，如果i大于表长，p=NULL
  }
  //时间复杂度：O(n)

• 按照值来查找节点

  Node *LocateElem(LinkList L,ElemType e){
      //查找单链表L，数据域值为e的节点指针，否则返回NULL
      Node *P=L->next;
      while(p!=NULL&&p->data!=e){
          p=p->next;//从第1个节点开始查找data域为e的节点
      }
      return p;
  }
  //时间复杂度：O(n)

• 插入节点操作

  p=GetElem(L,i-1);
  s->next=p->next;
  p->next=s;

• 删除节点操作

  p=GetElem(L,i-1);
  q=p->next;
  p->next=q->next;
  free(q);   
  
  //method 2：
  p->data=p->next->data;
  p->next=p->next->next;
  free(p->next)

双链表

单链表的节点中只有一个指向后继的指针，单链表只能从头结点依次顺序的向后遍历

想访问某个节点的前驱节点，比如插入，删除，只能从头遍历。

双链表的节点：

typedef struct DNode{
    ElemType data;//数据域
    struct DNode *prior,*next;//前驱，后继指针
}DNode,*DLinkList;

关键在于保证在修改的过程不断链。双链表可以方便的找到前驱节点。插入、删除节点的时间复杂度仅为O(1)

• 双链表的插入操作

  s->next=p->next;
  p->next->prior=s;
  s->prior=p;
  p->next=s;

• 双链表的删除操作

  p->next=q->next;
  q->next->prior=p;
  free(q);

循环链表

循环链表与单链表的区别：表中最后一个节点的指针不为NULL，改为指向头结点。

单链表中只能从表头节点开始往后顺序遍历整个链表，而循环单链表可以从表中的任一节点开始遍历整个链表。有时对单链表常做的操作是在表头和表尾进行的，此时可对循环单链表不设头指针而设尾指针。

静态链表

是借助数组来描述线性表的链式存储结构，节点也有数据域data和指针域next。

指针是数组的下标，也叫游标。

静态链表结构的定义：

#define MaxSize 50
typedf struct{
    ElemType data;
    int next;
}SLinkList[MaxSize];

栈Stack

栈的基本操作：

• InitStack(&S):初始化一个空栈S

• StackEmpty(S)：判断一个栈是否为空，S为空返回true，否则false

• Push(&S,x)：进栈，如果栈S未满，将x加入让它成为新的栈顶

• Pop(&S,&x)：出栈，如果栈S非空，弹出栈顶元素，并用x返回

• GetTop(S,&x)：读取栈顶元素 ，如果栈S非空，用x返回栈顶元素

• ClearStack(&S)：销毁栈，并释放栈S占用的存储空间

  注：&是C++的特有，用来引用，采用C的写法是*，用来传达地址的目的

顺序栈：

• 顺序栈的实现

  #define MaxSize 50
  typedef struct{
      ElemType data[MaxSize];
      int top;
  }SqStack;
  栈顶指针：初始化为S.top=-1
  栈顶元素：S.data[S.top]
  进栈操作：S is not full,top++
  出栈操作：S is not empty,get top ,top--
  栈空条件:S.top==-1
  栈满条件：S.top==MaxSize-1
  栈长：S.top+1

• 顺序栈的基本运算

  • 初始化

    void InitStack(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;
    }

  • 出栈

    boop Pop(SqStack &S,ElemType &x){
        if(S.top==-1)
            return false;
        x=S.data[S.top--];
        return true;
    }

  • 读取栈顶元素

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

链式栈

• 链栈的节点定义

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

队列Queue

队列的常见基本操作

• InitQueue(&Q)：初始化队列，构建一个空队列Q
• QueueEmpty(Q)：判断队列为空，Q为空返回true，否则false
• EnQueue(&Q,x)：入队，若队列Q未满，将x加入，成为新的队尾
• DeQueue(&Q,&x)：出队，若队列Q非空，将队头元素赋值给x
• GetHead(Q,&x)：读取队头元素，若队列Q非空，将队头元素赋值给x

顺序队列

• 节点定义：

  #define MaxSize 50
  typedef struct{
      ElemType data[MaxSize];
      int front,rear;
  }SqQueue;
  队空条件：Q.front==Q.rear==0
  进队操作：Queue is not full,enqueue data,rear+1
  出队操作：Queue is not empty,dequeue data,front+1

• 循环队列

  初始化：Q.front==Q.rear=0
  队首指针rear：Q.rear=(Q.front+1)%MaxSize
  队尾指针front:Q.rear=(Q.rear+1)%MaxSize
  队列长度：(Q.rear+MaxSize-Q.front)%MaxSize
  队满条件：(Q.rear+1)%MaxSize==Q.front
  队空条件：Q.front==Q.rear
  队中元素个数：(Q.rear-Q.front+MaxSize)%MaxSize

• 循环队列的操作

  • 初始化

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

  • 判断队空

    bool isEmpty(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;
        return true;
    }

  • 出队

    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;
    }

链队

• 链队节点定义：

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

• 链式队列的基本操作

  • 初始化

    void InitQueue(LinkQueue &Q){
        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 EnQueue(LinkQueue &Q,ElemType x){
        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;
        p=Q.front->next;
        x=p->data;
        Q.front->next=p->next;
        if(Q.rear==p)
            Q.rear=Q.front;//原来队列中如果只有一个节点，删除后变为空
        free(p);
        return true;
    }

队列在计算机系统中的应用

队列在计算机系统中应用非常广泛：

• 解决主机CPU与外部设备IO之间的速度不匹配问题

• 解决由多用户引起的资源竞争问题

  主机与打印机之间速度不匹配的问题：主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快很多。由于速度不匹配，如果直接把输出的数据送给打印机打印显然是不行的

  解决方法：设置一个打印数据的缓冲区，主机把要打印输出的数据依次写入到这个缓冲区。写满后就暂停输出，转去做其他事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印。打印完后再向主机发出请求。

  CPU资源的竞争是一个典型的队列应用问题。在一个带有终端的计算机系统上，有多个用户需要CPU格子运行自己的程序，它们分别通过各自的终端向系统提出占用CPU的请求。操作系统通常按照每个用户请求在时间上的先后顺序，把它们排成一个队列。每次把CPU分配给队首的用户使用。当相应的程序运行结束后，或者用户用完规定的时间片后，让它出队，再把CPU分配给新的队首请求的用户使用。

括号匹配问题

算法思想：扫描每个字符，遇到花，中，圆左括号进栈，遇到花，中，圆有括号出栈

bool BracketsCheck(char *str){
    InitStack(SqStack S);
    int i=0;
    while(str[i]!='\0'){
        switch(str[i]){
            //左括号入栈    
            case '(':Push(S,'(');break;
            case '[':Push(S,'[');break;
            case '{':Push(S,'{');break;
            //遇到右括号，检测栈顶
            case ')':Pop(S,e);
                if(e!='(')return false;
               break;
            case ']':Pop(S,e);
                if(e!='[')return false;
                break;
            case '}':Pop(S,e);
                if(e!='{')return false;
                break;
            default:break;    
        }
        i++;
    }
    if(!IsEmpty(S)){
        printf("括号不匹配\n");
        return false;
    }
    else{
        printf("括号匹配\n");
        return true;
    }
}

树与二叉树

• 二叉树链式存储节点：

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

• 二叉树的遍历

  • 先序遍历PreOrder

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

  • 中序遍历InOrder

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

  • 后序遍历PostOrder

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

    三种遍历方式的时间复杂度，空间复杂度都为O(n)

  • 层次遍历LevelOrder

    void LevelOrder(BiTree T){
        //需要借助到队列Queue
        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);//右子树不空，右子树入队
        }
    }

  • 中序遍历非递归

    void InOrder(BiTree T){//需要借助一个栈
        InitStack(S);//初始化栈S，
        BiTree p=T;//p是遍历指针
        while(p||!IsEmpty(S)){//栈不为空，p不空循环
            if(p){
                Push(S,p);//根指针进栈
                p=p->lchild;//遍历左子树
            }
            else{
                Pop(S,p);//根指针出栈
                visit(p);//访问根节点
                p=p->rchild//遍历右子树
            }
        }
    }

  • 后序遍历非递归

    void PostOrder(BiTree T){
        InitStack(S);
        BiTree p=T;//p是遍历指针
        BiTree r=NULL;
        while(p||!IsEmpty(S)){
            if(p){//走到最左边
                push(S,p);
                p=p->lchild;
            }
            else{//向右
                GetTop(S,p);//获取栈顶节点
                if(p->rchild&&p->rchild!=r){//如果右子树存在，且未被访问
                    p=p->rchild;//转向右子树
                    push(S,p);//将右子树节点进栈
                    p=p->lchild;//然后转向最左边
                }
                else{//没有右子树，弹出节点并访问
                    pop(S,p);//将节点弹出
                    visit(p->data);//访问节点
                    r=p;//记录最近访问的节点
                    p=NULL;//节点访问完后，重置p指针
                }
            }
        }
    }

二叉排序树BST

也叫二叉查找树，左<根<右

• 二叉排序树的查找

  BSTNode *BST_search(BiTree T,ElemType key,BSTNode *&p){
      p=NULL;
      while(T!=NULL&&key!=T->data){
          p=T;
          if(key<T->data)
              T=T->lchild;
          else
              T=T->rchild;
      }
      return T;
  }

• 二叉排序树的插入

  int BST_Insert(BiTree &T,int k){
      if(T==NULL){
          T=(BiTree)malloc(sizeof(BSTNode));
          T->key=k;
          T->lchild=T->rchild=NULL;
          return 1;//返回1，表示成功
      }
      else if(k==T->key)//树中存在相同的关键字节点，返回0
          return 0;
      else if(k<T->key)//递归，插入到T的左子树中
          return BST_Insert(T->lchild,k);
      else//递归，插入到T的右子树中
          return BST_Insert(T->rchild,k);
  }

• 二叉排序树的构造

  void Create_BST(BiTree &T,char str[],int n){
      T=NULL;//初始化的时候T为空树
      int i=0;
      while(i<n){//依次将每个元素插入
          BST_Insert(T,str[i]);
          i++
      }
  }

平衡二叉树VAL

平衡二叉树的各个节点的平衡因子只能为-1,0,1