数据结构与算法

一、绪论

1.1 数据结构基本概念

1.2 算法和算法评价

数据结构三要素：逻辑结构，存储结构，数据的运算。 （描述的数据之间的关系以及数据在计算机中的存储方式）

逻辑结构：线性结构，非线性结构 存储结构：顺序存储，链式存储，索引存储，散列存储

算法五个特性：输入，输出，有穷性，确定性，可行性 好的算法应该具备：正确性，可读性，健壮性，高效性。 算法的效率评价：时间复杂度，空间复杂度

---

二、线性表

顺序表（数组）
链表：单链表，双列表，带头节点操作一致
操作受限的线性表：栈FILO，队列FIFO

广义表

head：取表头元素，去括号
tail：去表头元素，不去括号

链表代码题：一律使用带头节点的链表，方便操作

//结点结构体 
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*List;

//初始化申请
List p = (List)malloc(sizeof(LNode));//链表概念，已是指针形式
LNode *p = (LNode*)malloc(sizeof(LNode));//节点概念，变量名定义指针

• 逆置带头节点的单链表

List Reverse(List head)
{
    LNode *p,*q,*r;//三指针p q r
    p = head->next;
    q = p->next;
    p->next = NULL;

    while(q){
        //pqr位置按顺序排列
        r = q->next;
        //逆指
        q->next = p;
        //后移
        p = q;
        q = r;

        head->next = p;
    }
    return head;
}

• 带头结点的单链表删除重复元素

void Delete(List &L)
{
    LNode *p = L->next,*q,*prep;

    while(p!=NULL)
    {
        prep = p;
        q = p->next;
        while(q!=NULL)
        {
            if(p->data==q->data){
                prep->next = q->next;
                free(q);
                q = prep->next;
            }
            else{
                prep=q;
                q=q->next;
            }
        }
        p=p->next;
    }
}

• 合并递增有序的的A链表与B链表，形成递增有序的新链表C

List Merge(List &A,List &B)
{
    List C=(List)malloc(sizeof(LNode));
    //pc指针指向c尾结点
    LNode *pc=C;
    //pa，pb访问a,b的每个节点
    LNode *pa=A->next,*pb=B->next;

    //循环添加小元素
    while(pa&&pb){
        if(pa->data<=pb->data)
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else
        {
            pc->next=pb;
            pc=pb;
            pb=pb->next; 
        }
    }
    //其中一表已空，另外一表属于直接并入
    if(pa){
        pc->next=pa;
    }
    if(pb){
        pc->next=pb;
    }
    return C;
}

---

三、栈 队列 数组

---

四、串

---

五、树

二叉树的遍历

先序NLR 中序LNR 后序LRN 层序。
除了先序+后序，其他任意两个序列可以推出二叉树的形状。

线索二叉树

序列有先序，中序，后序。节点有左孩子指针和右孩子指针。
根据序列，若左孩子指针为空，左孩子指针指向前继节点，若右孩子为空，则右孩子指针指向后继节点。
序列首没有前继，左孩子指针指向NULL，序列尾没有后继，右孩子指针指向NULL。

平衡二叉树的插入删除调整

哈夫曼树（带权路径长度）

一堆带有权值的节点，构成一个森林
1 森林中选取权值最小的两个节点，组成一个树，树的根节点为两个节点权值和。（左小右大）
2 将树加入森林中，再选取根节点最小的两个树，形成新的树，树的根节点为两根节点之和，再加入森林
3 循环，直至所有节点加入，生成哈夫曼树

哈夫曼编码由哈夫曼树生成，左路为0，右路为1.

WPL=Σ（节点权值*节点哈夫曼树路径长度）/节点个数

树/森林 转二叉树

孩子兄弟表示法，左孩子，右兄弟。
二叉树的左子树是森林里某树的孩子
二叉树的右子树是森林里某树的兄弟

树的节点与度的计算

边数=节点数-1=n-1（除了根节点，每个节点有唯一被指）
度数总和等于边数：n-1=0* n0 +1* n1+2* n2...（度即是边）

• 树的存储：顺序存储，链式存储

• 稀疏矩阵的存储：三元组、单链表、十字链表

• n个顶点的最小连通图：n-1条边

• 图的表示：（）为无向图，<>为有向图

• 图的存储：邻接矩阵，邻接表存储

二叉树代码题:树用孩子兄弟表示法，指针域表示不同

//结点结构体
//若是孩子兄弟表示法表示树
//struct TNode *firstchild,*nextsibling;
typedef struct TNode{
    int data;
    struct TNode *lchild,*rchild;
}TNode,*Tree;

//初始化申请
Tree p = (Tree)malloc(sizeof(TNode));//树概念，已是指针形式
TNode *p = (TNode*)malloc(sizeof(TNode));//节点概念，变量名定义指针

• 递归遍历

（代码题都是遍历的扩展，万变不离其中）

//NLR 前序遍历 
void TravelNLR(TNode *t)//t根节点指针
{
    if(t==NULL) return;

    printf("%d",t->data);
    TravelNLR(t->lchild);
    TravelNLR(t->rchild);
}

//LNR 中序遍历 
void TravelLNR(TNode *t)//t根节点指针
{
    if(t==NULL) return;

    TravelLNR(t->lchild);
    printf("%d",t->data);
    TravelLNR(t->rchild);
}

//LRN 后序遍历 
void TravelLRN(TNode *t)//t根节点指针
{
    if(t==NULL) return;

    TravelLRN(t->lchild);
    TravelLRN(t->rchild);
    printf("%d",t->data);
}

• n个节点的完全二叉数组，建树

Tree Create(ElemType A[],int i){
    if(i>n) return NULL;//下标越界

    TNode *p = (TNode*)malloc(sizeof(TNode));//申请树节点
    p->data = A[i];
    p->lchild = Create(A,2*i);
    p->rchild = Create(A,2*i+1);

    return p;
}

• 统计二叉树中度为1的结点的个数

void Count(TNode *t,int *num)
{
    if(t==NULL)  return;
    if((t->rchild==NULL&&t->lchild!=NULL)||(t->rchild!=NULL&&t->lchild==NULL))
        *num+=1;

    Count(t->lchild,num); 
    Count(t->rchild,num); 
}

Count(T,&num)

• 二叉树左右子树交换

void Change(Tree &T)
{
    if(T==NULL) return;
    else{
        TNode *temp=T->lchild;
        T->lchild=T->rchild;
        T->rchild=temp;

        Change(T->lchild);
        Change(T->rchild);
    }
}

Change(T)

• 二叉树输出每一个节点的深度

void NodeDepth(TNode *t,int h)
{
    if(t==NULL) return;
    //前序遍历
    printf("%d",h);
    NodeDepth(t->lchild,h+1);
    NodeDepth(t->rchild,h+1);
}

NodeDepth(T,1);

• 兄弟孩子表示法的树输出每个叶子节点所在层数

typedef struct TNode{
    int data;
    struct TNode *firstchild,*nextsibling;
}TNode,*Tree;

void nodedepth(TNode *t,int h)
{
    if(t==NULL) return;
    //为叶子结点，直接输出
    if(t->firstchild==NULL) printf("%d %d",t->data,h);

    //左孩子，深度+1
    nodedepth(t->firstchild,h+1);
    //右兄弟，深度不变
    nodedepth(t->nextsibling,h);
}

---

六、图

• 图的存储

  邻接矩阵与邻接表存储
  

• 有向图的拓扑排序

  1找到入度为0的顶点，该点指向的其他点入度减一（擦去指向）
  2这些入度减一（擦去指向）的顶点中，选取入度为0的顶点
  重复，直到找不到入度为0的顶点。
  

• 图的遍历

  深度优先DFS：从一个节点开始，向下层遍历，直到无法向下，回退至可向下遍历的点，直到所有节点被访问
  
  广度优先BFS：从一个节点开始，遍历它的所有邻接点，再从第一个邻接点开始，如此循环
  

• 最小生成树（不唯一）

  Prim求最小生成树(顶点开始发散)
  
      1从顶点开始，选取权值最小的边，最小边顶点加入生成树。
      2再寻找生成树内权值最小的边，最小边顶点加入生成树，循环。
  
  Kruskal求最小生成树（加入最小边）
  
      1将所有的边按照权值从小到大排序
      2依次将边从小到大加入生成树
      3若加入的边使树形成回路，则舍去
      直至所有定点加入生成树
  

---

七、查找算法

• 顺序查找，求ASL

• 二分查找（折半查找）

  如果序列长度为奇数，则二分中间位置确定，为中间数，两侧等长
  如果序列长度为偶数，则二分中间位置为n/2取整，为小一边的数，两侧差1
  

• 散列查找（线性探测法，平方探测，链地址法），求ASL

  线性探测：冲突后+1移位寻找空位
  平方探测：冲突后1^2,-1^2,2^2,-2^2，...以此类推
  链地址：冲突后，添加链表
  
  冲突一次，该数据的查找次数+1,初始查找次数为1
  ASL平均查找长度=sum（各数据查找次数）/数据个数
  

---

八、排序算法

• 插入排序类

  直接插入：选取确定序列后的一个元素，向前寻找插入位置
  
  希尔排序：按照步长，分为多个小组进行直接插入排序
  

• 交换排序类

  冒泡排序：从前向后冒，一趟确定一个
  
  快速排序：位置待定法，前后指针比较交换，一趟确定一个
  

• 选择排序类

  简单选择排序：
  
      在待查找序列中选择最小的值，放入已确定序列末尾，一趟确定一个
  
  堆排序：
  
      大顶堆：每个节点的值都 大于 或等于其子节点的值，用于升序排列
      小顶堆：每个节点的值都 小于 或等于其子节点的值，用于降序排列
  
      1构建二叉树堆
      2按照大/小顶堆规律，从最底层最小子树开始，向上传递子树内最大/小值
      3最底层完成后，最底层子树规模扩大一层，再向上一层传递子树内最大/小值
      4传递后应该再调整小一层规模的子树，确保每个节点大于孩子
      5循环至整个二叉树层全包含，并且向下调整完成
  

• 归并排序

  分而治之，大序列分小序列排序，排序后小序列间进行排序，组成大序列，循环
  

• 基数排序

  不需要比较的排序。适合大数据量
  排序思想：根据数字的个位进行排序，再根据数字十位排序，百位排序，以此类推
  

• 排序算法的时间复杂度，空间复杂度