数据结构

阅读量：5446 字数：11459 阅读时间：28min

数据结构的研究不仅涉及到计算机硬件（特别是编码理论、存储装置和存取方法等）的研究范围，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便查找和存取数据元素更为方便。因此，可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，在计算机科学中，数据结构不仅是一般程序设计（特别是非数值计算的程序设计）的基础，而且是设计和实现编译程序、操作系统、数据系统及其它系统程序和大型应用程序的重要基础。值得注意的是，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型的观点来论论数据结构，已成为一种新的趋势，越来越被人们所重视。

线性表

顺序储存结构(数组)

定义及初始化

实现线性表的顺序储存结构的类型定义：

#define MAXSIZE 100
typedef struct node {
    DataType data[MAXSIZE];
    int length;
} SeqList, *PseqList;

定义一个顺序表：

SeqList L;

PSeqList 是指向 SeqList 类型变量的指针类型；

定义一个顺序表指针：

PSeqList PL;

初始化顺序表指针：

PL = (PSeqList)malloc(sizeof(SeqList));
// 或
PL = &L;

典型操作的算法实现

插入运算的定义

int Insert_SeqList(PSeqList PL, int i, DataType x){
    int j;
    if(!PL){
        printf("表不存在");
        return -2;
    }
    if(PL->length >= MAXSIZE){
        printf("表溢出");
        return -1;
    }
    if(i < 1 || i > PL->length + 1){
        printf("插入位置不合法");
        return 0;
    }
    for(j = PL->length -1; j >= i - 1; j--){
        PL->data[j+1] = PL->data[j]
    }
    PL->data[i-1] = x;
    PL->length++;
    return 1;
}

删除运算的定义

int Delete_SeqList(PSeqList PL, int i){
    int j;
    if(!PL){
        printf("表不存在");
        return -1;
    }
    if(i < 1 || i > PL->length){
        printf("删除位置不合法");
        return 0;
    }
    for(j = i; j < PL->length; j++){
        PL->data[j-1] = PL->data[j];
    }
    PL->length--;
    return 1;
}

链式储存结构（单链表）

定义及初始化

链表的每个元素构成一个节点，定义：

typedef struct node {
    DataType data; /* 数据域 */
    struct node *next; /* 指针域 */
} LNode, *LinkList;

定义头指针变量：

LinkList H;

单链表的集中形态

典型操作的算法实现

序号查找算法

LinkList Locate_LinkList(LinkList H, int i){
    LinkList p;
    int j = 0;
    p = H;
    while(p && j < i){
        p = p->next;
        j++;
    }
    if(j != i || !p){
        printf("参数 i 错误或单链表不存在");
        return NULL;
    }
    return p;
}

值查找算法

LinkList Locate_LinkList(LinkList H, DataType x){
    LinkList p;
    if(H == NULL){
        return NULL;
    }else{
        p = H->next;
        while(p && p->data != x){
            p = p->next;
        }
        return p;
    }
}

单链表插入算法

int Insert_LiskList(LinkList H, int i, DataType x){
    LinkList p, q;
    p = Locate_LinkList(H, i-1);
    if(!p){
        printf("i 错误");
        return 0;
    }
    q = (LinkList)malloc(sizeof(LNode));
    if(!q){
        printf("申请空间失败");
        return 0;
    }
    q->data = x;
    q->next = p->next;
    p->next = 1;
    return 1;
}

单链表删除算法

int Del_LinkList(LinkList H, int i){
    LinkList p, q;
    if(H == null || H->next == null){
        printf("空表不能删除");
        return 0;
    }
    p = Locate_LinkList(H, i-1);
    if(p == null || p->next == null){
        printf("参数 i 错");
        return 0;
    }
    q = p->next;
    p->next = q->next;
    free(q);
    return 1;
}

链式储存结构（循环单链表）

循环单链表

链式储存结构（双向单链表）

定义及初始化

typedef struct node {
    DataType data;
    struct node *prior;
    struct node *next;
} LNode, *LinkList

定义头指针变量：

LinkList H;

典型操作的算法实现

插入算法

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

删除算法

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

链式储存结构（静态链表 (数组) ）

定义

typedef struct {
    DataType data; /* 元素 */
    int next; /* 相对指针 */
} SNode; /* 节点类型 */
// 再定义一个静态链表
#define MAXSIZE 100
typedef struct {
    SNode sp[MAXSIZE];
    int SL; /* 静态链表头指针 */
} StList, *PStList;

栈

栈的顺序储存（静态链表 (数组) ）

栈的顺序储存结构是用一组连续的储存单元依次存放栈中的每个数据元素，并用起始端作为栈底。

类型定义

#define MAXSIZE 100
typedef struct {
    DataType data[MAXSIZE];
    int top; // 栈顶指针的位置
} SeqStack, *PSeqStack;

定义指向顺序栈的指针：

PSeqStack S;
S = (PSeqStack) malloc(sizeof(SeqStack));

初始化栈

PSeqStack Init_SeqStack(void){
    // 创建一顺序栈，返回指向栈的指针
    PSeqStack S;
    S = (PSeqStack) malloc(sizeof(SeqStack));
    if(S){
        S->top = -1;
    }
    return S;
}

销毁栈

void Destory_SeqStack(PSeqStack *SeqStackPoint){
    if(*SeqStackPoint){
        free(*SeqStackPoint);
    }
    *SeqStackPoint = NULL;
    return;
}

eg:

int main(){
    PSeqStack S;
    S = Init_SeqStack();
    ......
    Destory_SeqStack(&S);
}

判断空栈

int Empty_SeqStack(PSeqStack S){
    if(S->top == -1){
        return 1;
    }else{
        return 0;
    }
}

入栈

int Push_SeqStack(PSeqStack S, DataType x){
    if(S->top == MAXSIZE - 1){
        return 0;
    }else{
        S->top++;
        S->data[S->top] = x;
        return 1;
    }
}

出栈

出栈操作是在栈的等不进行删除操作。

int Pop_SeqStack(PSeqStack S, DataType *x){
    if(Empty_SeqStack(S)){
        return 0;
    }else{
        *x = S->data[S->top];
        S->top--;
        return 1;
    }
}

取栈顶元素

int GetTop_SeqStack(PSeqStack S, DataType *x){
    if(Empty_SeqStack(S)){
        return 0
    }else{
        *x = S->data[S->top];
        return 1;
    }
}

栈的应用

倒叙输出字符串

PSeqStack S;
char ch;
S = Init_SeqStack(void);
while((ch = getchar()) != 13){
    Push_SeqStack(S, ch);
}
printf("\n");
while(!Empty_SeqStack(S)){
    Pop_SeqStack(S, &ch)
    printf("%c",ch);
}
printf("\n");

数制转化问题

typedef int DataType;
int conversion(int N, int r){
 PSeqStack S;
 DataType x;
 if(!r){
    printf("基数不能为 0");
    return 0;
 }
 S = Init_SeqStack();
 if(!S){
    printf("初始化栈失败");
    return 0;
 }
 while(N){
    Push_SeqStack(S, N % r);
    N = N / r;
 }
 while(!Enpty_SeqStack(S)){
    Pop_SeqStack(S, &x);
    printf("%d", x);
 }
 printf("\n");
 Destory_SeqStack(&S);
}

栈与递归

递归的定义：若一个对象部分地包括它自己。或用它自己给自己定义，则称这个对象是递归的。

递归：直接递归、间接递归

递归的例子

求 n 的阶乘

int fact(int n){
 if(n == 1){
    return 1;
 }else{
    return (n * fact(n-1));
 }
}

汉诺塔问题

// Hanio

队列

队列是一种特殊的线性表，队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。

队列的特点：先进先出（First In First Out），简称 FIFO 线性表。

定义队列

#define MAXSIZE 100
typedef struct {
    DataType data[MAXSIZE]; // 队列的存储空间
    int front, rear; // 队头、队尾指针
} SeqQueue, *PSeqQueue;

// eg:

SeqQueue* Q;
Q = (SeqQueue*) malloc(sizeof(SeqQueue));
/* 
或
PSeqQueue Q;
Q = (PSeqQueue) malloc(sizeof(SeqQueue));
*/

真假溢出

真溢出

入队时，Q->rear 加1，Q->rear == MAXSIZE 时队满； 出队时，所有的队列元素向前移一位，Q->rear 减1，Q->front 始终指向 0 位置不变。

假溢出

入队时，Q->rear加一，Q->rear == MAXSIZE 时队满；出队时 Q->front 加一。

队列初始化

PSeqQueue Init_SeqQueue(){
    // 返回新顺序队列指针
    PSeqQueue Q;
    Q = (PSeqQueue) malloc(sizeof(SeqQueue));
    if(Q){
        Q->front = 0;
        Q->rear = 0;
    }
    return Q;
}

销毁队列

void Destory_SeqQueue(PSeqQueue *Q){
    if(*Q){
        free(*Q)
    }
    *Q = null;
}

判断空队列

int Empty_SeqQueue(PSeqQueue Q){
    if(Q && Q->front == Q->rear){
        return 1; // 空
    }else{
        return 0; // 非空
    }
}

入队

int In_SeqQueue(PSeqQueue Q, DataType x){
    if((Q->rear + 1) % MAXSIZE == Q->front){ // *****
        // 队满
        return -1;
    }else{
        Q->rear = (Q->rear + 1) % MAXSIZE;
        Q->data[Q->rear] = x;
        return 1;
    }
}

出队

int Qut_SeqQueue(PSeqQueue Q, DataType *x){
    if(Emoty_SeqQueue(Q)){
        // 队空
        return -1;
    }else{
        Q->front = (Q->front + 1) % MAXSIZE;
        *x = Q->data[Q->front];
        return 1;
    }
}

读队头元素

int Front_SeqQueue(PSeqQueue Q, DataType *x){
    if(Emoty_SeqQueue(Q)){
        // 队空
        return -1;
    }else{
        *x = Q->data[Q->front];
        return 1;
    }
}

串

串的顺序储存

第一种

#define MAXSIZE 256
typedef struct{
    char data[MAXSIZE];
    int Length; // 串长
} SeqString;

第二种

char s[MAXSIZE];

第三种

char s[MAXSIZE + 1];

s[0] 存放串的实际长度，串值存放在 s[1] ~ s[MAXSIZE],字符的序号和存储位置一致。

串的链式存储

  1. 就是线性表链式结构，只要把 DataType 改为 char
  2. 节点大小、存储密度

?????

广义表

广义表的存储

typedef struct GenealNode{
    int tag; // 取 0 表示原子节点，取 1 表示子表节点
    union{
        DataType data;
        struct GenealNode *hp, *tp;
    };
} *GList

广义表的存储结构为：

tag; data/slink; link

tag=1 为原子; tag=0 为子表；

data 为原子数据; slink 为子表地址；

link 为本元素的同层下一个元素的地址

Q: 广义表中中怎么区分原子节点和表节点？或者说什么是原子节点、什么是表节点？或者说 tag 取值如何?

A: 表结点的特点就是：它的内容是表，而原子结点的内容内容就是一个数值。

Q: 广义表表头和表尾分别是什么？

A: 当广义表LS非空时，称第一个元素为LS的表头；称广义表LS中除去表头后其余元素组成的广义表为LS的表尾。例如，广义表(a, (b))的表头是单元素a，表尾是广义表((b))。

取表头

GList GetHead(GList p){
    // 表空是返回 null，否则返回表头指针
    if(!p){
        printf("空表");
        return NULL;
    }else{
        return p->hp;
    }
}

取表尾

GLIst GetTail(GList p){
    // 空表或单个原子，返回 NULL
    if(!p || !p->tag){
        return NULL
    }else{
        return(p->tp);
    }
}

取深度

深度: 指广义表中所含括号的重述

int depth(GList ls){
    int max = 0, dep;
    GList tmp = ls;
    if(temp == NULL){
        return 1;
    }
    if(temp->tag == 0){
        return 0;
    }
    while(tmp != NULL){
        dep = depth(tmp->hp);
        if(dep > max){
            max = dep;
        }
        tmp = tmp->tp;
    }
    return max+1;
}

小结

广义表是广义上的线性表，表头是原子或子表，表为一定是子表。

树与二叉树

树的基本概论

数是一种常见非线形结构，是 n 个结点的有限集合。若 n=0，则称为空树；否则，仅有一个特定节点的成为根。当 n>1 时，其余街道被分为 m 个互不相交的子集 T1，T2，...，Tm，每个子集又是一棵树。

结点：数据元素的内容及其指向其子树根的分支系统称为结点

结点的度：结点的分支数

终端结点（叶子）：度为零的结点

非终端结点：度不为零的结点

结点的层次：树中根结点的层次为 1，根结点子树的为第 2 层

树的度：树中所有结点度的最大值

树的深度：树中所有结点中层次的最大值

有序树、无序树：如果树中每颗子树丛左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。

森林：是 m 颗互不相交的树的集合

孩子、双亲：结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲

子孙：以某个结点为根的子树上的所有结点都为该结点的子孙

祖先：丛根结点到该结点路径上的所有结点

兄弟：同一个双亲的孩子之间互为兄弟

堂兄弟：双亲在同一层的结点

树的特点

树的根节点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。

二叉树的定义与性质

二叉树是树的特殊情况

二叉树的性质

在二叉树的第 i 层上最多有 2i-1 个结点（i>=1）

深度为 k 的二叉树最多有 2k-1 个结点（k>=1）

满二叉树：如果一个深度为 k 的二叉树结点数达最大即拥有 2k-1 个结点，则称他为满二叉树

完全二叉树：n 个结点的二叉树，若将它与与一棵同深度的满二叉树中的所有结点按从左上到下，丛左到右的顺序进行编号，且该二叉树中的每个结点分别与满二叉树中编号为 1～n 的结点位置一一对应，则称这颗二叉树为完全二叉树。

具有 n 个结点的完全二叉树的深度为 [\log_2 n]+1 ([]：取整符号)

对于有 n 个结点的完全二叉树的所有结点按从上到下，从走到右的顺序编号，则对任意一个结点i，有：

  1. 若 i=1，则结点 i 是这棵完全二叉树的根，没有双亲；否则其双亲的结点编号为 [i/2]；
  2. 如果 2i>n 则结点 i 没有左孩子；否则其左孩子结点的编号为 2i；
  3. 如果 2i+1>n 则结点 i 没有右孩子；否则其右孩子结点编号为 2i+1。

二叉树的存储结构

顺序存储结构

补全为完全二叉树。将结点的编号作为数组的下标。

#define MaxTreeNodeNum 100
typedef struct{
    DataType data[MaxTreeNodeNum]; /* 根存储在下标为 1 的数组单元中 */
    int n; /* 当前完全二叉忽视结点个树 */
}QBTree;

顺序存储特点：

  1. 二叉树是完全二叉树，空间利用率高、寻找孩子和双亲比较容易
  2. 若二叉树不是完全二叉树，需要将空缺的位置用特定的符号填补，造成空间利用率的下降

链式存储结构

各结点设计结构：左孩子域、右孩子域、数据域

typedef char DataType /* 设结点内容的数据类型为字符型 */
typedef struct bnode{
    DataType data;
    struct bnode *lchild, *rchild;
}Bnode, *BTree;

二叉树的遍历算法（递归）

遍历过程是将非线形结构线性化的过程

根据访问根的次序分为：

  1. 先序遍历 TLR
  2. 中序遍历 LTR
  3. 后序遍历 LRT

先序遍历

void PreOrder(BTree t){
    if(t){
        visit(t->data);
        PreOrder(t->lchild);
        PreOrder(t_>rchild);
    }
}

中序遍历

void InOrder(BTree t){
    if(t){
        InOrder(t->lchild);
        visit(t->data);
        InOrder(t->rchild);
    }
}

后序遍历

void PostOrder(BTree t){
    if(t){
        PostOrder(t->lchild);
        PostOrder(t->rchild);
        visit(t->data);
    }
}

建立二叉树方法

  1. 由先序方式建立二叉树
  2. 由先序和中序建立二叉树

线索二叉树

哈夫曼树

定义

哈夫曼树，又称最优树，是一类戴荃路径长度最短的树。

1、路径和路径长度

从树中一个结点到另一个结点之间的分支构成两个结点的路径，路径上的分支数目叫做路径长度。树的路径长度是从树根到每一个结点的路径长度之和。

2、带权路径长度

结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作WPL。

若有n个权值为w1,w2,...,wn的结点构成一棵有n个叶子结点的二叉树，则树的带权路径最小的二叉树叫做哈夫曼树或最优二叉树。

在上图中，3棵二叉树都有4个叶子结点a、b、c、d，分别带权7、5、2、4，则它们的带权路径长度为

（a）WPL = 7 * 2 + 5 * 2 + 2 * 2 + 4 * 2 = 36

（b）WPL = 4 * 2 + 7 * 3 + 5 * 3 + 2 * 1 = 46

（c）WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 35

其中（c）的WPL最小，可以验证，（c）恰为哈夫曼树。

发布于： #数据结构 #笔记

上一篇：梦长安

2018 年夏，同父母前往十三朝古都陕西西安一行。西安曾名长安，意为长治久安，是历史上第一座被称为“京”的都城，是中华文明和中华民族重要发祥地。长安也是丝绸之路的东方起点和隋唐大运河的起点，与雅典、罗马、开罗并称世界四大文明古都。建都长安的周、秦、汉、隋、唐曾是中国古代最为强盛和文明的黄金时代，而如今的西安面貌如何？ 住宿篇 提前半个月在 airbnb 上预定了六晚民宿，价格很便宜，¥318/

下一篇：PHP Website: Pengcheng.ga

pengcheng.ga 是我高中阶段的个人网站，没有使用博客框架，页面设计参考 Material Design 卡片式设计。 网站于 2017 年 八月关闭。 网站部分截图

雁过留痕，风过留声

目 录