Data Struct Learning-线性数据结构

List

 2018/06/08   Share

线性数据结构

线性表

线性表的基础

1. 表中元素个数为线性表的长度

2. 线性表没有元素时，称为空表

3. 表起始位置称为表头， 表结束位置称表尾

抽象数据类型描述：

类型名称：线性表（List）

数据对象集：线性表是 n（>= 0）个元素构成的有序序列

操作集：

    1. List MakeEmpty() ： 初始化一个空线性表 L

    2. ElementType FindKth(int K, List L): 根据位序K， 返回相应元素

    3. Int Find(ElementType X, List L):  在线性表 L 中查找 X 的第一次出现的位置

    4. void Insert(ElementType X, init I, List L): 在位序 i 前插入一个新元素 X

    5. void Delete(int i, List L ): 删除指定位序 i 的元素

    6. init Length(List L) :返回线性表 L 的长度n

数组存储

1. 初始化
List *MakeEmpty ()
{
    List *Ptrl
       Ptrl = (List*)malloc(sizeof(List))   // 申请结构
       Ptrl->Last = -1                        // 将尾指针指向-1, 线性表长度则为0
       return Ptrl;
}



2. 查找 (查找 List 里面第一个元素等于 X 的位置)
int Find(ElementType X, List *Ptrl)
{
    init i = 0
    while(i<=Ptrl->Last && Ptrl->Data[i]!= X)
        i++;
       if(i>Ptrl->Last) return -1 // 没找到，返回-1
       else return i;
}



3. 插入 (第 i(1<= i <= n+1)个位置插入一个值为 X的新元素)
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(“插入数据不合法”)
        return;
    }

    for (j=Ptrl->Last; j>=i-1; i--)
        Ptrl->Data[j+1] = Ptrl->Data[j]            // 将 i 之后的每个元素都往后挪一位
    Ptrl->Data[i]= X;                            // 将X的值付给第 i 位元素
    Ptrl->Last++;                                // 将 Last 指向最后一位元素
    return;
}




4. 删除 (删除表第i(1<= i <= n)个位置元素)
void Delete(int i, List *Ptrl)
{
    int j;
    if (i<1 || i> Ptrl->Last+1){
        printf("不存在第%d 个元素")
        return;
    }
    for (j=i; j<Ptrl->Last+1; j++)
        Ptrl->Data[j-1] = Ptrl->Data[j]
    Ptrl->Last--;
    return;
}

链表存储

1. 求表长
int Length (List *Ptrl)
{
    List *p = Ptrl;            // *p指向表的第一个结点
    int j = 0
    while(p){
        p=p->Next;
        j++
    }
    return j;
}



2-1. 查找：按序号查找：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;
    else return NULL;
}

2-2. 查找： 按值查找:Find
List *Find(ElementType X, List *Ptrl)
{
    List *p = Ptrl
    while(p->Data != X && p != NULL)
        p=p->Next;
    return p;
}

3. 插入 (第 i-1(1<= i <= n+1)个位置插入一个值为 X的新元素)
List *Insert(ElementType X, int i, List *Ptrl)
{
    List *p, *s;
    if (i==1){
        s=(List*)malloc(sizeof(List));
        s->Data = X;
        s->Next = Ptrl;
        return s;                            // 返回头指针
    }
    p = FindKth(i-1, Ptrl);
    if(p==NULL) {
        print("参数报错");
        return NULL;
    }else{
        s=(List*)malloc(sizeof(List))
        s->Data = X;
        s->Next = p->Next;                    // s 的下个指针指向p的下个的指针
        p->Next = s;
        return Ptrl;                        // 返回头指针

    }
}



4.删除(删除链表的第i(1<=i<=n)个位置上的结点)
List *Delete(int i, List *Ptrl)
{
    List *p, *s;
    if (i==1) {
        s=Ptrl;
        if(Ptrl!=NULL) Ptrl=Ptrl->Next;
        else return NULL;
        free(s);
        return Ptrl;
    }

    p = FindKth(i-1, Ptrl)
    if(p==NULL|| p->Next==NULL) {
       print("不存在 删除的第%d个结点");
       return NULL;
    }else {
        s=P->Next;
        P->Next=s->Next;
        free(s);
        return Ptrl;
    }

}

广义表

广义表是线性表的推广

堆栈

栈的顺序存储结构通常有一个一位数组和一个记录栈顶元素位置的变量组成

顺序存储结构

#define MaxSize <存储数据元素的最大个数>
typeof struct {
    ElementType Data[MaxSize];
    int Top;
} Stack;

入栈
void Push (Stack *PtrS, ElementType item)
{
    if (PtrS->Top === MaxSize-1) {
        printf("堆栈满);
        return;
    } else {
        PtrS->Data[++(PtrS->Top)] = item;
        return;
    }
}

出栈
void Pop (Stack *PtrS)
{
    if(PtrS->Top === -1){
        printf("堆栈空");
        return;
    }else{
        return(PtrS->Data[(PtrS->Top)--]);
    }
}

应用场景：计算器

两栈共享空间

#define MaxSize<存储数据元素的最大个数>
struc DStack {
    ElementType Data[MaxSize]l
    int Top1;
    int Top2;
}S;
S.Top1 = -1;
S.Top2 = MaxSize

入栈
void Push(struct DStack *PtrS, ElementType item, int Tag)
{
    if (PtrS->Top2 - Ptrl->Top1 == 1) {
           printf("堆栈满);
        return;
    }
    if (Tag == 1)
        Ptrs->Data[++(PtrS->Top1)] = item;
    else
        Ptrs->Data[--(PtrS->Top2)] = item;
}

出栈
void Pop(struct DStack *PtrS, int Tag)
{
    if(Tag==1){
        if(PtrS->Top1 == -1) {
            printf("堆栈1空");
            return;
        }else{
            return PtrlS->Data[(PtrS->Top1)--];
        }
    } else {
        if(PtrS->Top2 == MaxSize) {
            printf("堆栈2空");
            return;
        }else{
            return PtrS->Data[(PtrS->Top2)++];
        }
    }
}

应用场景：股票

事实上，使用这样的数据结构，通常都是当两个梢的空间需求有相反关系时，也就是一个枝增长时另一个枝在缩短的情况。就像买卖股票一样，你买入时，一定是有一个你不知道的人在做卖出操作. 有人赚钱，就一定是有人赔钱。这样使用两钱共享空间存储方法才有比较大的意义 . 否则两个钱都在不停地增长，那很快就会因枝满而溢出了。

链栈

堆栈的链式存储实现

typedef struct Node
{
    ElementType Data;
    struct Node *Next;
}LinkStack;
LinkStack *Top;



/* 构建一个堆栈的头节点，返回指针 */
LinkStack *CreateStack()
{
   LinkStack *S;
   S = (LinkStack *)malloc(sizeof(Struct Node));
   S-> Next = NULL;
   return S;
}

/* 判断堆栈S是否为空*/
int IsEmpty(LinkStack *S)
{
    return (S->Next == NULL);
}



/* PUSH */
void Push(ElmentType item, ListStack *S)
{
    struct Node*TmpCell;
    TmpCell = malloc(sizeof(struct Node));
    TmpCell->Element = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell
}



/* POP */
void Pop(ListStack *S)
{
    struct Node *FirstCell;
    ElementType TopElem;
    if (IsEmpty(S)){
        printf("堆栈空");
        return NULL;
    }else{
        FirstCell=S->Next;
        S->Next = FirstCell->Next;
        TopElem = FirstCell->Element;
        free(FirstCell);
        return TopElem;
    }
}

中缀表达式求值

基本策略：将中缀表达式转换为后缀表达式，然后求值

方法：

运算数相对顺序不变，
运算符号顺序发生改变（括号也是运算符）
1. 需要存储“等待中”的运算符号，(相当于堆栈)
2. 需要将当前运算符号与“等待中”的最后一个运算符号比较，“等待中”的最后一个运算符比当前运算符优先级高，则可入栈

a(b+c)/d ————> abc+()d/

2(6/3+4)-5 ————> 263/4+5-

2(9+6/3-5)+4 ————> 2963/+5-4+

流程：

运算数：直接输出
左括号：压入堆栈
右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出栈，不输出）
运算符：
1. 若优先级大于栈顶运算符时，则把它压栈；
2. 若优先级小于等于栈顶运算符时，将栈顶运算符弹出并输出；再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级位置，然后将该运算符压栈；
若个对象处理完毕，则把堆栈中存留的运算符一并输出

队列

顺序存储结构

#define MaxSize <存储数据元素的最大个数>
typeof struct {
    ElementType Data[MaxSize];
    int rear;
    int front;
} Queue



/* 创建队列 */
Queue *Create

循环队列

链式存储结构

#定义结构
typedef struct Node {
    ElementType Data;
    struct Node *Next;
}QNode;
typedef struct {
    QNode *rear;
    QNode *front;
}LinkQueue;
LinkQueue *PtrQ;



#删除操作
ElementType DeleteQ(LinkQueue *PtrQ)
{
    Qnode *FrontCell;
     ElementType FrontElem;

    if (PtrQ->front == NULL){
        print("队列空");
        return;
    }
    FrontCell = PtrQ->front;
    if (PtrQ->front == PtrQ->rear)
        PtrQ->front = PtrQ->rear = NULL;
    else
        PtrQ->front = FrontCell->Next;
    FrontElem = FrontCell->Data;
    free(FrontCell);
    return FrontElem;
}



#插入操作
ElementType EnQueue(LinkQueue *PtrQ, ElementType X)
{
    Qnode *RearCell;
    RearCell->Data = X;
    RearCell->Next = NULL;

    PtrQ->rear->next = RearCell;
    PtrQ->rear=RearCell;
    return OK;
}

树

树的定义

斜二叉树

完美二叉树/满二叉树

完全二叉数

几个重要的性质

一个二叉树的第 i 层的最大结点数为：2^(i-1), i>=1.
深度为 k 的二叉树的最大总结点数为：2^k-1,k>=1 （1+2^1+2^2+····2^k = 2^k - 1）
对于任何非空二叉树 T，若n0表示叶结点的个数、n2表示度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1 (叶结点：没有儿子的结点) 【证明：边数+1=结点数， n22+n11+n0*0+1 = n2+n1+n0】

顺序存储结构

完全二叉树

一般二叉树

链式存储

遍历

先序遍历

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

使用堆栈实现非递归先序遍历

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

中序遍历

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

使用堆栈实现非递归中序遍历

       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);
                   print("%5d", T->Data);
                   T=T->Right;
               }
           }
       }


3. 后序遍历
    ```c
       void InOrderTraversal(BinTree BT)
       {
           if(BT){
               InOrderTraversal(BT->Left);
               InOrderTraversal(BT->Right);
               printf("%d",BT->Data);
           }
       }

使用堆栈实现非递归后序遍历

void InOrderTraversal(BinTree BT)
{
    BinTree T=BT;
    BinTree Root = BT;//保存根节点地址，以用于最后打印
    Stack S = creatStack(MaxSize);
    while(T || !IsEmpty(S)){
        while(T){
            Push(S,T);
            T=T->Left;
        }
        if(!IsEmpty(S)){
            T=Pop(S);
            if (!T->Left)
                printf("$d",T->Data);
            T=T->Right;

        }
    }
    printf("%d ",Root->Data);//最后打印根节点数据
}

图

排序

最大堆

哈夫曼树

原文作者: White

原文链接: http://yuchenzhen.github.io/2018/06/08/Data-Struct-Learning/

发表日期: June 8th 2018, 1:41:38

Next Post

Leetcode-一字节二字节判断
Previous Post

hexo摘要

CATALOG

1. 线性数据结构



缺失模块。
1、请确保node版本大于6.2
2、在博客根目录（注意不是archer根目录）执行以下命令：
npm i hexo-generator-json-content --save
3、在根目录_config.yml里添加配置：

jsonContent:
  meta: false
  pages: false
  posts:
    title: true
    date: true
    path: true
    text: false
    raw: false
    content: false
    slug: false
    updated: false
    comments: false
    link: false
    permalink: false
    excerpt: false
    categories: true
    tags: true