数据结构

---

第一讲 基本概念

1.1 什么是数据结构

1.数据结构是数据对象，及存在于该对象的实例和组成实例的数据元素之间的各种联系，联系可以通过定义相关函数来给出，数据结构是ADT的物理实现。
数据对象在计算机中的组织方式包括逻辑结构和物理存储结构，数据对象必定与一系列加在其上的操作相关联，完成操作所用的方法就是算法。

1.2什么是算法

1.有限指令集，接受一些输入，产生输出，有限步骤后终止，每条指令必须有充分明确的目标，不可以有歧义，计算机能处理的范围之内，描述不依赖于任何计算机语言及具体实现手段。
2.for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
if-else结构复杂度取决于if条件判断复杂度和两个分歧部分的复杂度，总体复杂度取三者最大。

1.3最大数例子

int Max3( int A, int B, int C )
{ /* 返回3个整数中的最大值 */
    return A > B ? A > C ? A : C : B > C ? B : C;
}
 
int DivideAndConquer( int List[], int left, int right )
{ /* 分治法求List[left]到List[right]的最大子列和 */
    int MaxLeftSum, MaxRightSum; /* 存放左右子问题的解 */
    int MaxLeftBorderSum, MaxRightBorderSum; /*存放跨分界线的结果*/
 
    int LeftBorderSum, RightBorderSum;
    int center, i;
 
    if( left == right )  { /* 递归的终止条件，子列只有1个数字 */
        if( List[left] > 0 )  return List[left];
        else return 0;
    }
 
    /* 下面是"分"的过程 */
    center = ( left + right ) / 2; /* 找到中分点 */
    /* 递归求得两边子列的最大和 */
    MaxLeftSum = DivideAndConquer( List, left, center );
    MaxRightSum = DivideAndConquer( List, center+1, right );
 
    /* 下面求跨分界线的最大子列和 */
    MaxLeftBorderSum = 0; LeftBorderSum = 0;
    for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
        LeftBorderSum += List[i];
        if( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    } /* 左边扫描结束 */
 
    MaxRightBorderSum = 0; RightBorderSum = 0;
    for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
        RightBorderSum += List[i];
        if( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    } /* 右边扫描结束 */
 
    /* 下面返回"治"的结果 */
    return Max3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}
 
int MaxSubseqSum3( int List[], int N )
{ /* 保持与前2种算法相同的函数接口 */
    return DivideAndConquer( List, 0, N-1 );
}

第二讲 线性结构

2.1线性表及其实现
1.第一种方法表示多项式的方法，数组各分量对应多项式各项；第二种方法用二元数组分量表示系数，指数组成的结构，对应非零项；第三种方法用链表结构存储非零项，每个结点包括系数和指数两个数据域，以及一个指针域。
2.线性表的操作：初始化一个空线性表，根据位序，返回相应元素，在线性表中查找元素第一次出现的位置，在位序i前插入一个新元素，删除指定位序的元素，返回线性表的长度。
3.利用数组的存储空间顺序存储线性表元素
访问下标为i的元素：L.Data[i]或PtrL->Data[i]
线性表的长度：L.Last+1或者PtrL->Last+1.
4.初始化

List MakeEmpty()
{List PtrL;
Ptrl=(List)malloc(sizeof(struct LNode));
PtrL->Last=-1;
return PtrL;}
int Find(ElementType,List PtrL)
{int i=0;
while(i<=Ptrl->Last&&Ptrl->Data[i]!=X)
    i++;
if(i>PtrL->Last)return -1;
else return i;}

5.插入

void Insert(ElementType X, int i,List PtrL)
{int j;
if(PtrL->Last==MAXSIZE-1){
    printf("表满")}
    return；}
if(i<1||i>PtrL->Last+2){
printf(位置不合法)；}
for(j=PtrL->Last;j>=i-1;j--)
    PtrL->Data[j+1]=PtrL->Data[j];
PtrL->Data[i-1]=X;
PtrL->Last++;
return;

6.删除

void Delete(in i,List PtrL)
{
int j;
if(i<1||i>PtrL->Last+1){
printf("不存在第%d个元素"，
return；)}
for(j=i;j<=PtrL->Last;j++){
    PtrL->Data[j-1]=PtrL->Data[j];
PtrL->Last--;
return;}}

7.线性表的链式存储实现

typedef struct LNode *List;
struct LNode{
    ElementType Data;
    List Next;};
struct Lnode L;
List PtrL;

8.求表长

int Length(List PtrL){
List p=PtrL;
int j=0;
while(p){
p=p->Next;
j++;}
return j;}

9.查找
按序号查找FindKth；

List FindKth(int K,List PtrL){
List p=PtrL;
int i=1;
while(p!=NULL&&i<K){
p=p->Next;
i++;}
if(i==K)return p;
elase return NULL;}
按值查找
List Find(ElementType X,List PtrL)
{List p=PtrL;
while(p!=NULL&&p->Data!=X)
    p=p->Next;
return p;}

10.线性表操作

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last;
};
 
/* 初始化 */
List MakeEmpty()
{
    List L;
 
    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;
 
    return L;
}
 
/* 查找 */
#define ERROR -1
 
Position Find( List L, ElementType X )
{
    Position i = 0;
 
    while( i <= L->Last && L->Data[i]!= X )
        i++;
    if ( i > L->Last )  return ERROR; /* 如果没找到，返回错误信息 */
    else  return i;  /* 找到后返回的是存储位置 */
}
 
/* 插入 */
/*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Insert( List L, ElementType X, Position P ) 
{ /* 在L的指定位置P前插入一个新元素X */
    Position i;
 
    if ( L->Last == MAXSIZE-1) {
        /* 表空间已满，不能插入 */
        printf("表满"); 
        return false; 
    }  
    if ( P<0 || P>L->Last+1 ) { /* 检查插入位置的合法性 */
        printf("位置不合法");
        return false; 
    } 
    for( i=L->Last; i>=P; i-- )
        L->Data[i+1] = L->Data[i]; /* 将位置P及以后的元素顺序向后移动 */
    L->Data[P] = X;  /* 新元素插入 */
    L->Last++;       /* Last仍指向最后元素 */
    return true; 
} 
 
/* 删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/
bool Delete( List L, Position P )
{ /* 从L中删除指定位置P的元素 */
    Position i;
 
    if( P<0 || P>L->Last ) { /* 检查空表及删除位置的合法性 */
        printf("位置%d不存在元素", P ); 
        return false; 
    }
    for( i=P+1; i<=L->Last; i++ )
        L->Data[i-1] = L->Data[i]; /* 将位置P+1及以后的元素顺序向前移动 */
    L->Last--; /* Last仍指向最后元素 */
    return true;   
}

typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;
 
/* 查找 */
#define ERROR NULL
 
Position Find( List L, ElementType X )
{
    Position p = L; /* p指向L的第1个结点 */
 
    while ( p && p->Data!=X )
        p = p->Next;
 
    /* 下列语句可以用 return p; 替换 */
    if ( p )
        return p;
    else
        return ERROR;
}

/* 带头结点的插入 /
/注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是链表结点指针，在P之前插入新结点 */

bool Insert( List L, ElementType X, Position P )
{ /* 这里默认L有头结点 */
    Position tmp, pre;
 
    /* 查找P的前一个结点 */        
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            
    if ( pre==NULL ) { /* P所指的结点不在L中 */
        printf("插入位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 在P前插入新结点 */
        tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */
        tmp->Data = X; 
        tmp->Next = P;
        pre->Next = tmp;
        return true;
    }
}

/* 带头结点的删除 /
/注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */

bool Delete( List L, Position P )
{ /* 这里默认L有头结点 */
    Position tmp, pre;
 
    /* 查找P的前一个结点 */        
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            
    if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */
        printf("删除位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 将P位置的结点删除 */
        pre->Next = P->Next;
        free(P);
        return true;
    }
}

11.线性表是由同类型数据元素构成的有序序列的线性结构。元素个数为线性表的长度。数据对象集，操作集
12.链表表示堆栈的时候，一定要用链表头做top。另外用链表入栈不需要检查空间足不足。
13.用链表处理中缀表达式变成后缀表达式的时候，先把运算符号入栈，然后当下一个符号优先级比上一个低的时候，上一个符号可以出栈了。
运算数：直接输出；左括号：压入堆栈；右括号：将栈顶的运算符弹出并输出，直到遇到左括号；运算符：若优先级大于栈顶运算符，则压栈，优先级小于栈顶，将栈顶运算符弹出并输出。
14.堆栈的应用：函数调用及递归，深度优先搜索，回溯算法。
15.堆栈用数组+top或者链表

16. typedef int Position;
    struct SNode {
    ElementType Data; / 存储元素的数组 /
    Position Top; / 栈顶指针 /
    int MaxSize; / 堆栈最大容量 */
    };
    typedef struct SNode *Stack;

    Stack CreateStack( int MaxSize )
    {
    Stack S = (Stack)malloc(sizeof(struct SNode));
    S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
    S->Top = -1;
    S->MaxSize = MaxSize;
    return S;
    }

    bool IsFull( Stack S )
    {
    return (S->Top == S->MaxSize-1);
    }

    bool Push( Stack S, ElementType X )
    {
    if ( IsFull(S) ) {
    printf("堆栈满");
    return false;
    }
    else {
    S->Data[++(S->Top)] = X;
    return true;
    }
    }

    bool IsEmpty( Stack S )
    {
    return (S->Top == -1);
    }

    ElementType Pop( Stack S )
    {
    if ( IsEmpty(S) ) {
    printf("堆栈空");
    return ERROR; /* ERROR是ElementType的特殊值，标志错误 */
    }
    else
    return ( S->Data[(S->Top)--] );
    }

17.堆栈的操作

typedef struct SNode *PtrToSNode;
struct SNode {
    ElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;
 
Stack CreateStack( ) 
{ /* 构建一个堆栈的头结点，返回该结点指针 */
    Stack S;
 
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}
 
bool IsEmpty ( Stack S )
{ /* 判断堆栈S是否为空，若是返回true；否则返回false */
    return ( S->Next == NULL );
}
 
bool Push( Stack S, ElementType X )
{ /* 将元素X压入堆栈S */
    PtrToSNode TmpCell;
 
    TmpCell = (PtrToSNode)malloc(sizeof(struct SNode));
    TmpCell->Data = X;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
    return true;
}
 
ElementType Pop( Stack S )  
{ /* 删除并返回堆栈S的栈顶元素 */
    PtrToSNode FirstCell;
    ElementType TopElem;
 
    if( IsEmpty(S) ) {
        printf("堆栈空"); 
        return ERROR;
    }
    else {
        FirstCell = S->Next; 
        TopElem = FirstCell->Data;
        S->Next = FirstCell->Next;
        free(FirstCell);
        return TopElem;
    }
}

2.3队列

1.生成队列，判别是否满，插入，判别队列是否空，删除并返回。
2.顺序存储用数组，或者链表存储。
front，rear，开始front，rear-1，删除front+1，插入rear-1.链表的末尾做插入没问题，做删除有问题
3.判断队列是否为空front=rear是空的，但顺环队列会出现问题，解决方法是用size或者tag标记插入输出，或者仅仅用n-1个数组空间。

2.5多项式的表示

1.数组编程容易，调试简单，需要事先确定数组的大小
2.链表动态性强，编程略为复杂，调试比较困难

3树

3.1树与树的表示

1.查找：根据某个给定的关键字K，从集合R中找出关键字与K相同的记录
静态查找：集合中记录是固定的，没有插入和删除操作，只有查找。动态查找：集合中记录是动态变化的，除查找外还可能发生插入和删除。
2.顺序查找：
有哨兵：

int SequentialSearch(List Tbl,ElementType K)
{int i;
Tbl->Element[0]=K;
for(i=Tbl->Length;Tbl->Element[i]!=K;i--);
return i;)}
typedef struct LNode *List;
struct LNode{
       ElementType Element[MAXSIZE];
       int Length;}

3.二分查找Binary Search

 int BinarySearch(List Tbl,ElementType K)
 {int left,right,mid,NoFound=-1;
 left=1;
 right=Tbl->Length;
 while(left<=right)
 {mid=(left+right)/2;
 if(K<Tbl->Element[mid])  
    right=mid-1;
 else if(K>Tbl->Element[mid]) 
    left=mid+1;
 else return mid;}
 return NotFound;
 }

3.n个结点判定树深度为[lgn+1]。树和非树：子树是不相交的，除了根结点外，每个结点有且只有一个父结点，一棵N个结点的树有N-1条边。
4.结点的度，结点的子树个数。树的度，树的结点中最大的度数。叶结点，度为0的结点。父结点，有子树的结点是其子树的根结点的父结点。子结点，若A是B的父结点，则B是A的子结点。祖先结点，子孙结点，结点的层次，树的深度。
5.斜二叉树，完美二叉树，完全二叉树。
6.一个二叉树第i层的最大结点数为2^(i-1),i>1.
深度为k的二叉树有最大的结点总数为 2^k-1,k>=1.
对任何非空二叉树T，若n0表示叶结点的个数，n2是度为2的非叶结点个数，那么两者满足关系n0=n2+1.
7.二叉树重要操作有：判别BT是否为空，遍历，按照某顺序访问每个结点，创建一个二叉树。先序，中序，后序，层次遍历。
8.顺序存储结构 ，二叉树。
完全二叉树可以用数组表示，非根结点(序号i>1)的父结点序号是[i/2]向下取整;
结点(序号为i)的左孩子结点是2i，若2i<=n,否则没有左孩子，结点的右孩子2i+1，若2i+1<N,则没有右孩子。
9.链表存储

  typedef struct TreeNode *BinTree;
  typedef BinTree Position;
  struct TreeNode{
         ElementType Data;
         BinTree Left;
         BinTree Right;}

3.3二叉树的遍历

1.先序遍历
根结点，先左后右

void PreOrderTraversal(BinTree BT)
{if(BT){
    printf("%d",BT->Data);
    PreOrderTraversal(BT->Left);
    PreOrderTraversal(BT->Right);}
    }

2.中序遍历

void InOrderTraversal(BinTree BT)
{if(BT){
    PreOrderTraversal(BT->Left);
    printf("%d",BT->Data);
    PreOrderTraversal(BT->Right);}
    }
3.后序递归
void PostOrderTraversal(BinTree BT)
{if(BT){
    PreOrderTraversal(BT->Left);
    PreOrderTraversal(BT->Right);
    printf("%d",BT->Data);}
    }

4.二叉树的非递归遍历
中序遍历非递归遍历算法
遇到结点，把它压栈，遍历左子树，左子树遍历结束后从栈顶弹出结点并访问它，然后按其右指针再去中序遍历该结点的右子树。

void InOrderTraversal(BinTree BT)
{BinTree T=BT;
 Stack S=CreatStack(MaxSize);
 while(T||！IsEmpty(S)){
    while(T){
        Push(S,T);
        T=T->Left;}
        if(!IsEmpty(S)){
            T=Pop(S);
            printf("%5d",T->Data);
            T=T->Right;}}}

先序遍历

void InOrderTraversal(BinTree BT){
        BinTree T BT;
        Stack S=CreatStack(MaxSize);
        while(T||!IsEmpty(S)){
            while(T){
                printf("%5d",T->Data);
                Push(S,T);
                T=T->Left;}
            if(!IsEmpty(S)){
                T=Pop(S);
           
                T=T->Right;
                }}}
层序遍历
二叉树遍历的核心问题：二维结构的线性化
队列实现：遍历从根结点开始，根结点入队，然后结点出队，访问结点，左右儿子入队。
void LevelOrderTraversal(BinTree BT)
{   Queue Q;BinTree T;
    if(!BT)return;
    Q=CreatQueue(MaxSize)
    AddQ(Q,BT);
    while(!IsEmptyQ(Q)){
        T=DeleteQ(Q);
        printf("%d\n",T->Data);
        if(T->Left)AddQ(Q,T->Left);
        if(T->Right)AddQ(Q,T->Right);
        }}

遍历二叉树的应用：输出二叉树的叶子结点
在中序遍历中增加if(!BT-Left&&BT->Right)
求二叉树的高度：在后序遍历中

int PostOrderGetHeight(BinTree BT){
int HL,HR,MaxH;
if(BT){
    HL=PostOrderGetHeight(BT->Left);
    HR=PostOrderGetHeight(BT->Right);
    MaxH=(HL>HR)?HL:HR;
    return(MaxH+1);
    }
else return 0;}

5.二元运算表达式树及其遍历
有两种遍历序列确定二叉树，必须有中序遍历。
根据先序遍历第一个结点确定根结点，根据根结点在中序遍历序列中分割出左右两个子序列，对左子树和右子树分别递归使用相同的方法继续分解。

3.4小白：树的同构

1.通过左右孩子互换变成一样就叫同构。
2.结构数组表示二叉树：静态链表

struct TreeNode
{   ElementType Element;
    Tree Left;
    Tree Right;
    }T1[MaxTree],T2[MaxTree];
3.int main(){
Tree R1,R2;
R1=BuildTree(T1)
R2=BuildTree(T2);
if(Isomorphic(R1,R2))printf("Yes\n");
else printf("No\n");
return 0;}

创建二叉树

Tree BuildTree(struct TreeNode T){
scanf("%d\n",&N);
if(N){
    for(i=0;i<N;i++)check[i]=0;
    for(i=0;j<N;i++){
        scanf("%c %c %c\n",&T[i].Element，&cl，&cr);
        if(cl!='-'){
            T[i].Left=cl='0';
            check[T[i].Left]=1;}
        else T[i].Left=Null;}
        if(cr!='-'){
            T[i].Right=cl='0';
            check[T[i].Right]=1;}
        else T[i].Right=Null;}
        for(i=0;i<N;i++)
            if(!check[i]break;)
        Root=i;
    }
        return Root;
}

3.判别二叉树同构

int Isomorphic(Tree R1,Tree R2)
{
    if((R1==Null)&&(R2==Null))
            return 1;
    if(((R1==Null)&&(R2！=Null))||((R1!=Null)&&(R2==Null)))
            return 0;
    if(T1[R1].Element !=T2[R2].Element)
            return 0;
    if((T1[R1].Left==Null)&&(T2[R2].Left==Null))
            return Isomorphic(T1[R1].Right,T2[R2].Right);}
    if(((T1[R1].Left!=Null)&&(T2[R2].Left!=Null))&&((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)))
        return(Isomorphic(T1[R1].Left,T2[R2].Left)&&Isomorphic(T1[R1].Right,T2[R2]Right));
    else
        return(Isomorphic(T1[R1].Left,T2[R2].Right)&&Isomorphic(T1[R1].Right,T2[R2]Left));}

第四讲：树（中）

4.1二叉搜索树

1.查找问题：静态查找与动态查找
针对动态查找，数据如何组织？
2.非空左子树的所有键值小于其根结点的键值，非空右子树的所有键值大于其根结点的键值，左右子树都是二叉搜索树。
3.从二叉搜索树BST中查找元素X，返回其所在结点的地址；从二叉搜索树中查找并返回最小元素所在结点的地址，从二叉搜索树中查找并返回最大元素所在结点的地址。
4.二叉搜索树的查找操作：find
查找从根结点开始，树为空，返回null。非空，根结点关键字和x比较，x小于根结点键值，在左子树搜索，x大于根结点键值，在右子树中搜索，相等的话，搜索完成，返回指向此结点的指针。

 Position Find(ElementType X,BinTree BST)
 {
 if(!BST)return NULL;
 if(X>BST->Data)
    return Find(X,BST->Right);
Else if(X<BST->Data)
    return Find(X,BST->Left);
else
    return BST;}
改进
Position IterFind(ElementType X,BinTree BST)
{while(BST){
    if(X>BST->Data)
        BST=BST->Right;
    else if(X<BST->Data)
        BST=BST->Left;
    else
        return BST;
    }

return NULL;
}
找最小值
Position FindMin()
5.二叉搜索树的插入

BinTree Insert(ElementType X,BinTree BST)
{
    if(!BST){
        BST=malloc(sizeif(struct TreeNode));
        BST->Data=X;
        BST->Left=BST->Right=NULL;
    }else
        if(X<BST->Data)
            BST->Left=Insert(X,BST->Left);
        else if(X>BST->Data)
            BST->Right=Insert(X,BST->Right);
    return BST;}

6.二叉搜索树的删除
叶结点直接删除，修改父结点为null
只有一个孩子，将父结点指针指向要删除结点的孩子结点。
要删除的结点有左右子树，用另一个结点替代被删除的结点，右子树的最小元素或者左子树的最大元素。

BinTree Delete(ElementType X,BinTREE BST){
Position Tmp;
if(!BST)printf("要删除的元素未找到");
else if(X<BST->Data)
    BST->Left=Delete(X,BST->Left);
else if(X>BST->Data)
    BST->Right=Delete(X,BST->Right); 
else
    if(BST->Left && BST->Right)
    {Tmp=FindMin(BST->Right);
    BST->Data=Tmp->Data;
    BST->Right=Delete(BST->Data,BST->Right);
    }else{
        Tmp=BST;
        if(!BST->Left)
            BST=BST->Right;
        else if(!BST->Right)
            BST=BST->Left;
        free(Tmp);}
    return BST;}