数据结构

作者: Cherryjs | 来源:发表于2017-05-20 14:53 被阅读0次

第一讲基本概念

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或者链表

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

数据结构

第一讲基本概念

1.1 什么是数据结构

1.2什么是算法

1.3最大数例子

第二讲线性结构

2.3队列

2.5多项式的表示

3树

3.1树与树的表示

3.3二叉树的遍历

3.4小白：树的同构

第四讲：树（中）

4.1二叉搜索树

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构

第一讲 基本概念

1.1 什么是数据结构

1.2什么是算法

1.3最大数例子

第二讲 线性结构

2.3队列

2.5多项式的表示

3树

3.1树与树的表示

3.3二叉树的遍历

3.4小白：树的同构

第四讲：树（中）

4.1二叉搜索树

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

第一讲基本概念

第二讲线性结构