数据结构初识

发表于 | 更新于:
路漫漫其修远兮，吾将上下而求索

1. 绪论

1.1 基本概念和术语

  • 数据

  • 数据元素

  • 数据对象【数据元素的集合】

  • 数据类型

    • 原子类型
    • 结构类型
    • 抽象数据类型

  • 数据结构

    数据结构是相互之间存在一种或多种特定关系的数据元素的集合

    • 逻辑结构

    • 存储结构

    • 数据的运算

1.2 数据结构三要素

  • 逻辑结构

包括线性结构【一对一】：一般线性表、受限线性表【栈、队列、串】、线性表推广【数组】

非线性结构【一对多或同属一个集合】：集合、树形结构【一般树、二叉树、B+树】、图状结构【有向图、无向图，网状结构】

  • 存储结构【物理】

顺序存储、链式存储、索引存储、散列存储【hash】

  • 数据的运算

运算的定义【逻辑结构】和实现【存储结构】

1.3 算法

<1> 五个特性

  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出

<2>效率的度量

  • 时间复杂度

最坏时间复杂度，平均时间复杂度，最好时间复杂度

  • 空间复杂度

2. 线性表

2.1 定义

线性表是具有相同数据类型的n（n >= 0）个数据元素的优先序列

2.2 线性表的基本操作

1
2
3
4
5
6
7
8
9
InitList(&L) //初始化表
Length（L）//求表长
   LocateElem(L,e)//按值查找操作
   GetElem(L,i)//按位查找操作
   ListInsert(&L,i,e)//插入操作
   ListDelete(&L,i,&e)//删除操作
   PrintList(L)//输出操作
   Empty(L)//判空操作
   DestoryList(&L)//销毁操作

2.3 顺序表【数组】

线性表的顺序存储【随机存储的存储结构】，其逻辑顺序与其物理顺序相同，线性表中元素的位序是从1开始的，高级程序设计语言数组的下标从0开始

  • 顺序表不适合插入和删除

2.4 单链表

线性表的链式存储

1
2
3
4
typedef struct LNode { //定义单链表结点类型
    ElemType data;//数据域
    struct LNode *next;//指针域
}LNode,*LinkList;
  • 采用头插法建立单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList List_HeadInsert(LinkList &L) {//逆向建立单链表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));//创建头结点
    L->next = null;//初始为空链表
    scanf("%d",&x);//输入结点的值
    while(x != 9999) {//输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode))；//创建新结点
        s -> data = x;
        s -> next = L -> next;
        L -> next = s;//将新结点插入表中，L为头指针
        scanf("%d",&x);
    }
    return L;
}

缺点和优点：简单，生成结点的次序和输入数据的顺序不一致

  • 采用尾插法建立单链表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LinkList List_TailInsert(LinkList &L) {//正向建立单链表
    int x;//设置元素类型为整型
    L = (LinkList)malloc(sizeof(LNode));//创建头结点
    LNode *s，*r = L;//r为表尾指针
    scanf("%d",&x);
    while(x != 9999) {//输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode))；//创建新结点
        s -> data = x;
        r -> next = s;
        r = s;//r指向新的表尾结点
        scanf("%d",&x);
    }
    r -> next = null;//尾结点指针置空
    return L;
}
  • 按序号查找节点值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
LNode *GetElem(LinkList L,int i) {
    int j = 1;//计数，初始为1
    LNode *p = L -> next;//头结点指针赋值给p
    if (i == 0) {//若i等于0，则返回头结点
        return L;
    }
    if (i < 1) {
        return null;
    }
    while (p && j < i) {
        p = p -> next;
        j++;
    }
    return p;
}
  • 按值查找表节点
1
2
3
4
5
6
7
LNode *LocateElem(LinkList L,ElemType e) {
    LNode *p = L -> next;
    while(p != null && p -> date != e) {
        p = p -> next;
    }
    return p;
}
  • 插入节点操作
1
2
3
p = GetElem(L,i-1);
s -> next = p -> next;
p -> next = s;
  • 对某一结点进行前插操作
1
2
3
4
5
s -> next = p -> next;
p -> next = s;
temp = p -> data;//交换数据域
p -> data = s->data;
s->data = temp;
  • 删除节点操作
1
2
3
4
p = GetElem(L,i-1);//查找删除位置的前驱结点
q = p->next; //令q指向被删除结点
p->next = q->next;//将*q结点从链中断开
free(q);//释放结点的存储空间
  • 删除结点 *p
1
2
3
4
q = p->next;
p->data = p->next->data;
p->next = q->next;
free(q);
  • 求表长操作

带头结点和不带头结点是不同的

1
2
3
4
5
6
int count = 0;//计数器
q = p->next;
while (q != null) {
    count ++;
}
return count;

2.5 双链表

线性表的链式存储，增加了指向前驱的prior指针，双链表按位查找和按值查找与单链表相同,插入和删除的实现上有不同

1
2
3
4
typedef struct DNode {
    ElemType e;
    struct DNode *prior,*next;
} DNode,*DLinkList;
  • 双链表的插入操作
1
2
3
4
s->next = p->next;//将结点 *s 插入到 *p结点之后
p -> next ->prior = s;
s->prior = p;
p->next = s;
  • 双链表的删除操作
1
2
3
p->next = q->next;
q->next-prior = p;
free(q);

2.6 循环链表

2.6.1 循环单链表

最后一个结点的指针不是NULL，而改为指向头结点，判空判断是否为头指针，插入和删除和单链表一致，无需判断是否为表尾

2.6.2 循环双链表

在循环双链表中，某结点 *p为尾结点时，p->next == L;当循环双链表为空表时，其头结点的prior和next都等于L；

2.7 静态链表

静态链表借助数组来描述线性表的链式存储结构，结点也有data和next，next表示为相对地址【相当于数组下标】，叫游标，以next == -1 作为结束的标志

1
2
3
4
5
#define MaxSize 50//静态链表的最大长度
typedef struct{
    ElemType data;//存储数据元素
    int next;//下一个元素的数组下标
} SLinkList[MaxSize]

2.8 顺序表和链表的比较

2.8.1 存储（读写）方式

顺序表可以顺序存取，也可以随机存取，链表只能从表头顺序存取

2.8.2 逻辑与物理结构

顺序存储，逻辑相邻，物理存储也相邻；链式存储，逻辑相邻，物理存储不一定相邻

2.8.3 查找、插入和删除操作

2.8.4 空间分配

顺序存储在静态存储分配情形下，不能够扩充，动态存储扩充需要移动大量的元素

2.9 栈和队列

2.9.1 栈的属性

栈是只允许在一端进行插入和删除操作的受限线性表，其操作的特性是后进先出【Last In First Out】LIFO

  • 栈顶
  • 栈底
  • 空栈

2.9.2 栈的基本操作

1
2
3
4
5
6
InitStack(&S) //初始化一个栈
   StackEmpty(S)//判空
   Push(&S,x)//进栈
   Pop(&S,x)//出栈
   GetTop(S,&x)//读栈顶元素
   DestoryStack(&S)//销毁栈

2.9.3 栈的顺序存储

  • 顺序栈的实现
1
2
3
4
5
#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int top;
}sqStack;

栈顶指针 ：S.top,初始化时设置S.top = -1 或者S.top = 0,栈顶元素：S.data[S.top]

  • 初始化
1
2
3
void InitStack(SqStack &S) {
    S.top = -1;
}
  • 判栈空
1
2
3
4
5
6
7
bool StackEmpty(SqStack S) {
    if (S.top == -1) {
        return true;
    } else {
        return false;
    }
}
  • 进栈
1
2
3
4
5
6
7
8
bool Push(SqStack &S,ElemType x) {
    if (S.top == MaxSize - 1) {
        return false;//栈满
    }
    S.data[++S.top] = x;//指针先加1，再入栈,top指向栈顶
    //S.data[S.top++] = x; //top指向栈顶元素的下一个位置
    return true;
}
  • 出栈
1
2
3
4
5
6
7
8
bool Pop(SqStack &S,ElemType &x) {
    if (S.top == -1) {
        return false;
    }
    x = S.data[S.top--];//先出栈，指针减一，top指向栈顶
    //x = S.data[--S.top]//top指向栈顶元素的下一个位置
    return true;
}
  • 读栈顶元素
1
2
3
4
5
6
7
bool GetTop(SqStack &S,ElemType &x) {
    if (S.top == -1) {
        return false;
    }
    x = S.data[S.top];
    return true;
}

2.9.4 共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间

2.9.5 栈的链式存储结构

  • 链式存储
1
2
3
4
typedef struct Linknode{
    ElemType data;
    struct Linknode *next;
} *LiStack;

入栈与出栈都在链表的表头进行

2.9.6 队列的属性

队列简称队，也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除，其操作特性是先进先出【First In First Out】FIFO

  • 队列基本操作
1
2
3
4
5
InitQueue(&Q) //初始化队列
   QueueEmpty(Q) //判队列空
   EnQueue(&Q,x)//入队
   DeQueue(&Q,&x)//出队
   GetHead(Q,&x)//读取头元素

2.9.7 队列的顺序存储

  • 顺序队的实现
1
2
3
4
5
#define MaxSize 50
typedef struct {
    ElemType data[MaxSize];
    int front,rear;//队头指针和队尾指针
} SqQueue；

初始状态（队空条件）：Q.front == Q.rear == 0

【入】进队操作：队不满时，先送值到队尾元素，队尾指针+1

【出】离队操作：队不空时，先取队头元素值，再将队头指针+1

顺序存储可能会造成假溢出的情况

2.9.8 循环队列

  • 初始化
1
2
3
void InitQueue(SqQueue &Q) {
  Q.front = Q.rear = 0；  
}
  • 判队空
1
2
3
4
5
6
7
8
bool isEmpty(SqQueue Q) {
    if (Q.front == Q.rear) {
        return true;
    }
    else {
        return false;
    }
}
  • 入队
1
2
3
4
5
6
7
8
bool EnQueue(SqQueue &Q,ElemType x) {//入队
    if ((Q.rear + 1) % MaxSize == Q.front) { //队满则报错
        return false;
    }
    Q.data[Q.rear] = x;
    Q.rear = (Q.rear +1) % Maxsize;
    return true;
}
  • 出队
1
2
3
4
5
6
7
8
bool DeQueue(SqQueue &Q,ElemType &x) {
    if (Q.front == Q.rear) {
        return false;
    }
    x = data[Q.front];
    Q.front = (Q.front + 1) % MaxSize;
    return true;
}

2.9.9 队列的链式存储

  • 链式存储的定义
1
2
3
4
5
6
7
typedef struct{//链式队列结点
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear;
}LinkQueue;
  • 初始化
1
2
3
4
void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));//建立头结点
    Q.front -> next = null;
}
  • 判队空
1
2
3
4
5
6
7
bool isEmpty(LinkQueue Q) {
    if (Q.front == Q.rear) {
        return true;
    } else {
        return false;
    }
}
  • 入队
1
2
3
4
5
6
7
void EnQueue(LinkQueue &Q,ElemType e) {
   LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    s->data = x;
    s-next = null;
    Q.rear->next = s;
    Q.rear = s;
}
  • 出队
1
2
3
4
5
6
7
8
9
10
11
12
13
bool DeQueue(LinkQueue &Q,ElemType &x) {
    if (Q.front == Q.rear) {
        return false;
    }
    LinkNode *p = Q.front -> next;
    x = p -> data;
    Q.front->next = p -> next;
    if(Q.rear == p) {
        Q.rear = Q.front;
    }
    free(p);
    return true;
}

2.9.10 双端队列

双端队列是指允许两端都可以进行入队和出队的操作，逻辑结构仍是线性结构

2.9.11 栈和队列的应用

  • 栈在括号匹配的应用

  • 栈在表达式求值中的应用

  • 栈在递归中的应用【通常情况下，减少了代码量，但效率不是太高】

  • 队列在层次遍历中的应用

  • 队列在计算机系统的应用

    • 解决主机和外部设备之间速度不匹配的问题
    • 解决多用户引起的资源竞争问题

2.9.12 特殊矩阵的压缩存储

  • 对称矩阵
  • 三角矩阵
  • 三对角矩阵
  • 洗漱矩阵

3. 串

3.1 串的概念和属性

串是由零个或者多个字符组成的有限序列

  • 串中任意多个连续的字符组成的子序列称为该串的子串，包含子串的串称为主串

  • 定长顺序存储表示

1
2
3
4
5
#define MAXLEN 255
typedef struct {
    char ch[MAXLEN];
    int length;
}SString;
  • 堆分配存储表示
1
2
3
4
typedef struct {
    char *ch;
    int length;
}HString;
  • 块链存储表示

类似于线性表的链式存储结构，也可采用链表方式的存储串值，最后一个结点占不满时用#补上；

3.2 串的基本操作

1
2
3
4
5
6
7
8
9
10
StrAssign(&T,chars)//赋值操作
   StrCopy(&T,S)//复制操作
   StrEmpty(S)//判空操作
   StrCompare(S,T)//比较操作，S>T,返回值>0,S=T,返回值=0，S<T,返回值<0
   StrLength(S)//求串长
   SubString(&Sub,S,pos,len)//求子串
   Concat(&T,S1,S2)//由T返回S1和S2联接而成的新串
   Index(S,T)//定位操作
   ClearString(&S)//清空操作
   DestoryString(&S)//销毁串S

3.3 串的模式匹配

  • 简单的模式匹配算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Index(SString S,SString T) {
    int i = 1,j = 1;
    while(i<=S.length && j <= T.length) {
        if(S.ch(i) == Tch(j)) {
            ++i;
            ++j;
        } else {
            i = i - j + 2;
            j = 1;
        }
    }
    if (j > T.length) {
        return i - T.length;
    } else {
        return 0；
    }
}
  • KMP算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int Index_KMP(String S,String T,next[]) {
    int i = 1,j = 1;
    while(i<=S.length && j <= T.length) {
       if (j == 0 || S.ch[i] == T.ch[j]) {
           ++i;
           ++j;
       } else {
           j = next[j];
       }
        
    }
    if (j > T.length) {
        return i - T.length;
    } else {
        return 0；
    }
}
  • KMP算法进一步-nextval数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int Index_KMP(String S,String T,next[]) {
	get_nextval(String T,int nextval[])
    
}
void get_nextval(String T,int nextval[]) {
    int i = 1, j = 0;
    nextval[1] = 0;
    while(i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            ++i;
            ++j;
            if (T.ch[i] != T.ch[j]) {
                nextval[i] = j;
            } else {
                nextval[i] = nextval[j];
            }
        } else {
            j = nextval[j];
        }
    }
    if (j > T.length) {
        return i - T.length;
    } else {
        return 0；
    }
    
}

4. 树与二叉树

4.1 树的概念和属性

树是指n(n>=0)个结点的有限值，树适合具有层次结构的数据

  • 祖先 子孙 双亲 孩子 兄弟
  • 结点的度 树的度

树中一个结点孩子的个数称之为该结点的度，树中结点的最大度数称之为树的度

  • 分支结点【非终端结点】 叶子结点【终端结点】

度大于0 叫分支结点，度等于0叫叶子结点

  • 深度 高度 层次

结点的层次从根开始定义，深度是从根节点自顶向下逐层累加，高度是从叶节点开始自底向上逐层累加

  • 有序树 无序树

树中结点的各子树从左到右是有次序的，不能互换，称之为有序树，否则为无序树

  • 路径和路径长度

路径是这两个结点之间所经过的结点序列构成，路径长度是指路径上所经过的边的个数

  • 森林

森林是m(m>=0)棵互不相交的树的集合

4.2 二叉树的定义

二叉树是一种树形结构，子树有左右之分，次序不能任意颠倒，每个结点至多有两棵子树

  • 特殊二叉树
    • 满二叉树
    • 完全二叉树
    • 二叉排序树
    • 平衡二叉树

4.3 二叉树的存储结构

4.3.1 顺序存储结构

二叉树的顺序存储是指用一组地址连续的存储单元依次从上到下，从左到右存储完全二叉树上的结点元素

  • 完全二叉树
  • 满二叉树

4.3.2 链式存储结构

由于顺序存储的空间利用率比较低，因此二叉树一般采用链式存储结构

  • 二叉树的链式存储结构
1
2
3
4
typedef struct BiTNode {
    ElemType data;//数据域
    struct BiTNode *lchild,*rchid;//左右孩子指针
}BiTNode,*BiTree;

4.4 二叉树的遍历

  • 先序遍历<从上到下，从左到右>

若二叉树为空，什么也不做，否则，访问根节点，先序遍历左子树，先序遍历右子树

  • 递归
1
2
3
4
5
6
7
void PreOrder(BiTree T) {
    if (T != null) {
        visit(T);//访问根节点
        PreOrder(T -> lchild);//递归遍历左子树
        PreOrder(T -> rchild);//递归遍历右子树
    }
}
  • 非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void PreOrder2(BiTree T) {
    InitStack(S);
    BiTree p = T;
    while(p || !isEmpty(S)) {
		if (p) {
            visit(p)
            Push(S,p);
            p = p->lchild;
        } else {
            Pop(S,p);
            p = p -> rchild;
        }
    }
}
  • 中序遍历<从左到右>

若二叉树为空，什么也不做，否则，中序遍历左子树，访问根节点，中序遍历右子树

  • 递归
1
2
3
4
5
6
7
void InOrder(BiTree T) {
    if (T != null) {
        InOrder(lchild);
        visit(T);
        InOrder(rchild);
    }
}
  • 非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void InOrder2(BiTree T) {
    InitStack(S);
    BiTree p = T;
    while(p || !isEmpty(S)) {
		if (p) {
            Push(S,p);
            p = p->lchild;
        } else {
            Pop(S,p);
            visit(p);
            p = p -> rchild;
        }
    }
}
  • 后序遍历(从下到上，从左到右)

若二叉树为空，什么也不做，否则，后序遍历左子树，后序遍历右子树，访问根节点

  • 递归
1
2
3
4
5
6
7
void PostOrder(BiTree T) {
    if (T != null) {
       PostOrder(lchild);
        PostOrder(rchild);
        visit(T);
    }
}
  • 非递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void PostOrder2(BiTree T) {
   InitStack(S);
   p = T;
   r = null;
    while(p || !isEmpty(S)) {
		if (p) {
            Push(S,p);
            p = p->lchild;
        } else {
           GetTop(S,p);
            if (p->rchild && p->rchild != r) {
                p = p-> rchild;
            } else {
                pop(S,p);
                visit(p->data);
                r = p;
                p = null;
            }
        }
    } 
}
  • 层次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void levelOrder(BiTree T) {
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T);
    while (!IsEmpty(Q)) {
 		DeQueue(Q,q);
        visit(p);
        if(p->lchild != null) {
            EnQueue(Q,p->lchild);
        }
        if(p->rchild != null) {
            EnQueue(Q,p->rchild);
        }
    }
}
  • 由遍历序列构造二叉树

由二叉树的先序序列和中序序列可以唯一确定一棵二叉树

由二叉树的后序序列和中序序列可以唯一确定一棵二叉树

由二叉树的层序序列和中序序列可以唯一确定一棵二叉树

只知道二叉树的先序序列和后序序列无法唯一确定一棵二叉树

4.5 线索二叉树

4.5.1 线索二叉树的定义

1
2
3
4
5
typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;//左右孩子指针
    int ltag,rtag;//左右线索标志
}ThreadNode,*ThreadTree;

4.5.2 中序线索二叉树的构造

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void InTread(ThreadTree &p,ThreadTree &pre) {
    if (p != null) {
       InTread(p->lchild,pre);
        if(p->lchild == null) {
            p->lchild = pre
            p->ltag = 1;
        }
        if (pre != null && pre -> rchild == null) {
            pre-rchild = p;
            pre -> rtag = 1;
        }
        pre = p;
        InTread(p->rchild,pre);
    }
    
}

4.5.3 中序线索二叉树的遍历

  • 中序线索二叉树中中序序列下的第一个结点
1
2
3
4
5
6
ThreadNode * Firstnode(ThreadNode *p) {
    while(p->ltag == 0) {
        p = p->lchild;
    }
    return p;
}
  • 中序线索二叉树中结点p在中序序列下的后继
1
2
3
4
5
6
7
ThreadNode *Nextnode(ThreadNode *p) {
    if(p->rtag == 0) {
        return Firstnode(p->rchild);
    } else {
        return p->rchild;
    }
}
  • 利用上面两个算法，可以写出不含头结点的中序线索二叉树的中序遍历的算法
1
2
3
4
5
void Inorder(ThreadTree *T) {
    for (ThreadNode *p = FirstNode(T); p != null; p = Nextnode(p)) {
        visit(p);
    }
}

4.6 森林

4.6.1 树的存储结构

  • 双亲表示法
1
2
3
4
5
6
7
8
9
#define MAX_TREE_SIZE 100//树最多结点数
typedef struct {
    ElemType data;
    int parent;
}PTree;
typedef struct {
    PTNode nodes[MAX_TREE_SIZE];
    int n;
}PTree;
  • 孩子表示法
  • 孩子兄弟表示法
1
2
3
4
typedef struct CSNode{
    ElemType data;//数据域
    struct CSNode *firstchild,*nextsibling;//第一个孩子和右兄弟指针
}CSNode,*CSTree;

4.6.2 树，森林，二叉树的转换

  • 树转换为二叉树

<1> 在兄弟结点之间加一条连线

<2>对于每一个结点，只保留它与第一个孩子的连线，而与其他孩子的连线全部抹掉

<3>以树根为轴心，顺时针旋转45度

  • 森林转换为二叉树

<1> 先将森林中每棵树转换为相应的二叉树

<2> 每棵树的根也可以视为兄弟关系，在每棵树的根之间加一根连线

<3> 以第一棵树的根为轴心顺时针旋转45度

4.6.3 树和森林的遍历

  • 树的遍历

    • 先根遍历
    • 后根遍历

  • 森林的遍历

    • 先序遍历森林
    • 中序遍历森林【后根遍历】

4.6.4 树与二叉树的应用

  • 二叉排序树【BST】
  • 非递归查找算法
1
2
3
4
5
6
7
BSTNode *BST_Search(BiTree T,ElemType key) {
    while (T != null && key != T->data) 【
        if(key < T->data) {
            T = T -> lchild;
        }
    return T;
}
  • 二叉排序树的插入
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int BST_Insert(BiTree &T,KeyType k) {
    if(T == null) {
        T = (BiTree)malloc(sizeof(BSTNode));
        T -> key = k;
        T->lchild = T->rchild = Null;
        return 1;
    } else if(k == T->key) {
        return 0;
    } else if (k < T-> key) {
        return BST_Insert(T->lchild,k);
    } else {
        return BST_Insert(T->rchild,k);
    }
}
  • 二叉排序树的构造
1
2
3
4
5
6
7
8
void Creat_BST(BiTree &T,KeyType str[],int n) {
    T = null;
    int i = 0;
    while (i < n) {
        BST_Insert(T,str[i]);
        i++;
    }
}

  • 平衡二叉树

  • 哈夫曼树和哈夫曼编码

5. 图

图不可以是空图，图的顶点集V一定非空

5.1 图的属性

  • 有向图
  • 无向图
  • 简单图、多重图
  • 完全图【简单完全图】
  • 子图
  • 连通，连通图，连通分量
  • 强连通图，强连通分量
  • 生成树，生成森林
  • 顶点的度，入度和出度
  • 边的权和网
  • 稠密图、稀疏图
  • 路径，路径长度和回路
  • 简单路径、简单回路
  • 距离
  • 有向树

5.2 图的存储和操作

5.2.1 邻接矩阵法

  • 存储结构定义
1
2
3
4
5
6
7
8
#define MaxVertexNum 100 //顶点项目的最大值
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型
typedef struct {
    VertexType Vex[MaxVertexNum];//顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum]//邻接矩阵，边表
    int vexnum,arcnum;//图的当前顶点数和弧数 
}MGraph;

5.2.2 邻接表法

  • 存储结构定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define MaxVertexNum 100 //顶点项目的最大值
typedef struct ArcNode{ //边表结点
    int adjvex;//该弧所指向的的顶点的位置
    struct ArcNode *next；//指向下一条弧的指针
   //InfoType info;//网的边权值
}ArcNode；
typedef struct VNode{//顶点表结点
    VertexType data;//顶点信息
     ArcNode *first；//指向第一条依附该顶点的
}VNode,AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices;//邻接表
    int vexnum,arcnum;//图的顶点数和弧数
}ALGraph;//ALGraph是以邻接表存储的图类型

5.2.3 十字链表

5.2.4 邻接多重表

5.3 图的基本操作

1
2
3
4
5
6
7
8
9
10
Adjacent(G,x,y)//判断图是否存在边<x,y>或(x,y)
   Neighbors(G,x)//列出图G中与结点x邻接的边
   InsertVertex(G,x)//在图G中插入顶点x
   DeleteVertex(G,x)//从图G中删除顶点x
   AddEdge(G,x,y)//若无向边(x,y)或有向边<x,y>不存在，则向图G中添加该边
   RemoveEdge(G,x,y)//若无向边(x,y)或有向边<x,y>存在，则向图G中删除该边
   FirstNeighbor(G,x)//求图G中顶点x的第一个邻接点
   NextNeighbor(G,x，y)//假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号
   Get_edge_value(G,x,y)//获取图G中边(x,y)或<x,y>对应的权值
   Set_dege_value(G,x,y,v)//设置图G中边(x,y)或<x,y>对应的权值为v

5.4 图的遍历

5.4.1 广度优先搜索【Breadth-First-Search,BFS】

类似树的层序遍历算法

  • 伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool visited[Max_Vertex_num];//访问标记数组
void BFSTraverse(Graph G) {
    for (i = 0; i < G.vexnum;++i) {
        visited[i] = false;
    }
    InitQueue(Q);
    for (i = 0; i < G.vexnum;++i) {
        if(!visited[i]) {
            BFS(G,i);
        }
    }
}
void BFS(Graph G,int v) {
    visit(v);
    visited[v] = true;
    enqueue(Q,v);
    while(!isEmpty(Q)) {
        DeQueue(Q,v);
        for (w = FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) {
            if(!visited[w]) {
                visit(w);
                visited[w] = true;
                Enqueue(Q,w);
            }
        }
    }
}

5.4.2 深度优先搜索【Depth-First-Search，DFS】

类似树的先序遍历

  • 伪代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool visited[Max_verTex_Num];
void DFSTraverse(Graph G) {
    for(v = 0; v < G.vexnum; ++v) {
        visited[v] = false；
    }
    for(v = 0; v < G.vexnum; ++v) {
        if(!visited[v]) {
            DFS(G,v);
        }
    }
}
void DFS(Graph G,int v) {
    visit(v);
    visited[v] = true;
    for(w = FirstNeighbor(G,r); w >= 0; w = NextNeighbor(G,v，w)) {
        if(!visited[w]) {
            DFS(G,w);
        }
    }
}
  • 图的遍历与图的连通性

5.5 图的应用

  • 最小生成树

    • Prim算法
    • Kruskal算法

  • 最短路径

    • Dijkstra算法求单源最短路径问题
    • Floyd算法求各顶点之间最短路径问题

  • 有向无环图描述表达式

  • 拓扑排序

  • 关键路径

6. 查找

在数据集合中寻找满足某种条件的数据元素的过程称为查找

6.1 查找的属性

  • 查找表【查找结构】

用于查找的数据集合

  • 静态查找表
  • 关键字
  • 平均查找长度

6.2 顺序查找

  • 一般线性表的顺序查找
1
2
3
4
5
6
7
8
9
10
typedef struct {
    ElemType *elem;
    int TableLen;
}SStable;
int Search_Seq(SSTable ST,Elemtype key) {
    St.elem[0] = key;//哨兵 提高程序效率
    for(i = ST.TableLen;ST.elem[i] != key;--i) {
        return i;
    }
}
  • 有序表的顺序查找
  • 折半查找【二分查找】

仅适用于有序的顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Binary_Search(SeqList L，ElemType key) {
    int low = 0,high = L.TabLen - 1,mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if(L.elem[mid] == key) {
            return mid;
        } else if (L.elem[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
    
}
  • 分块查找【索引顺序查找】

6.3 B树和B+树

6.3.1 B树的属性

B树，多路平衡查找树

  • B树的高度(磁盘存取次数)
  • B树的查找

在B树中找结点，在结点内找关键词

  • B树的插入
  • B树的删除

6.3.2 B+树的基本概念

B+树是应数据库所需而出现的一种B树的变形树

一棵m阶的B+树需满足下列条件：

  • 每个分支结点最多有m棵子树(孩子结点)
  • 非叶根结点至少有两棵子树，其他每个分支结点至少有[m/2]棵子树
  • 结点子树的个数与关键字个数相等
  • 所有叶节点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来
  • 所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针

6.4 散列表

根据关键字而直接进行访问的数据结构

6.4.1 散列表的构造方法

  • 直接定址法

H(key) = key 或H(key) = a*key + b

  • 除留余数法

H(key) = key % p

  • 数字分析法
  • 平方取中法

6.4.2 处理冲突的方法

  • 开放定址法

    • 线性探测法
    • 平方探测法
    • 再散列法
    • 伪随机序列法

  • 拉链法【链接法，chaining】

7. 排序

就是重新排列表中的元素，通常由比较和移动，分为插入排序、交换排序、选择排序、归并排序、基数排序，大部分排序算法仅适用于顺序存储的线性表

7.1 插入排序

  • 普通插入排序
1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertSort(ElemType A[],int n) {
    int i,j;
    for (int i = 2; i <= n; i++) {
        if (A[i] < A[i-1]) {
            A[0] = A[i];//哨兵
        	for (int j= i -1;A[0] < A[j];--j) {
                A[j+1] = A[j];
                
            }
            A[j+1] = A[0];
            }
    }
}
  • 折半插入排序

稳定的排序方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void InsertSort(ElemType A[],int n) {
    int i,j,low,high,mid;
    for(i = 2; i <= n; i++) {
        A[0] = A[i];
        low = 1;
        high = i - 1;
        while(low <= high) {
            mid = (low + high)/2;
            if(A[mid] > A[0]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        for (j = i - 1; j >= high + 1; --j) {
            A[j+1] = A[j];
        }
        A[high+1] = A[0];
    }
}
  • 希尔排序【缩小增量排序】
1
2
3
4
5
6
7
8
9
10
11
12
13
void ShellSort(ElemType A[], int n) {
    for (dk = n/2;dk>=1;dk = dk/2) {
        for (i = dk + 1; i < n; ++i) {
			if(A[i] < A[i-dk]) {
                A[0] = A[i];
                for(j = i - dk; j>0&&A[0] < A[j];j-=dk)  {
                    A[j + dk] = A[j];
                }
                A[j + dk] = A[0];
            }
        }
    }
}

7.2 交换排序

  • 冒泡排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void BubbleSort(ElemType A[],int n) {
    for(int i = 0; i < n - 1; i++) {
        flag = false;
 		for(j = n -1; j > i; j--) {
            if(A[j-1] > A[j]) {
                swap(A[j-1],A[j]);
                flag = true;
            }
        }
        if (flag == false) {
            return;
        }
    }
}
  • 快速排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void QuickSort(ElemType A[],int low,int high) {
    if (low < high) {
        int pivotpos = Partition(A,low,high);
        QuickSort(A,low,pivotpos -1);
        QuickSort(A,pivotpos + 1，high);
    }
}
int Partition(ElemType A[],int low,int high) {
    ElemType pivot = A[low];
    while(low < high) {
        while (low < high && A[high] >= pivot) {
            --high;
        }
        A[low] = A[high];
        while(low < high && A[low] <= pivot) {
            ++low;
        }
    }
    A[low] = pivot;
    return low;
}

7.3 选择排序

  • 简单选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
void SelectSort(ElemType A[],int n) {
    for(int i = 0; i < n - 1; i++) {
        min = i;
        for(j = i +1; j < n; j++) {
            if(A[j] < A[min]) {
                min = j;
            }
            if(min != i) {
                swap(A[i],A[min]);
            }
        }
    }
}
  • 堆排序
  • 建立大根堆
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void BuildMaxHeap(ElemType A[], int len) {
    for(int i = len/2; i > 0; i--) {
        HeadAdjust(A,i,len);
    }
}
void HeadAdjust(ElemType A[],int k,int len) {
        A[0] = A[k];
        for(i = 2*k; i <= len; i *= 2) {
            if(i < len && A[i] < A[i+1]) {
                i++;
            }
            if(A[0] >= A[i]) {
                break;
            } else {
                A[k] = A[i];
                k = i;
            }
        }
    A[k] = A[0] 
}
  • 堆排序算法
1
2
3
4
5
6
7
void HeapSort(ElemType A[], int len) {
    BuildMaxHeap(A,len);
    for(i = len; i > 1; i--) {
        swap(A[i],A[1]);
        HeadAdjust(A,1,i-1);
    }
}

堆排序是一种不稳定的排序方法

7.4 归并排序和基数排序

  • 归并排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ElemType *B = (ElemType *)malloc((n+1)*sizeof(ElemType));
void Merge(ElemType A[],int low,int mid,int high) {
    for(int k = low; k <= high;k++) {
        B[k] = A[k];
    }
    for(i = low,j = mid + 1,k = i;i <= mid && j <= high; k++) {
        if(b[i] < B[j]) {
            A[k] = B[i++];
        } else {
            A[k] = B[j++];
        }
    }
    while(i <= mid) {
        A[k++] = B[i++];
    }
    while(j <= high) {
        A[k++] = B[j++];
    }
}

上面的代码中，只有一个while会执行

  • 合并
1
2
3
4
5
6
7
8
void MergSort(ElemType A[],int low,int high) {
    if(low < high) {
        int mid = (low + high)/2;
        MergeSort(A,low,mid);
        MergeSort(A,mid + 1,high);
        Merge(A,low,mid,high);
    }
}

7.5 各种内部排序算法的比较

序号 算法种类 时间复杂度最好情况 时间复杂度平均情况 时间复杂度最坏情况 空间复杂度 是否稳定
1 直接插入排序 O(n) O(n^2) O(n^2) O(1) 是
2 冒泡排序 O(n) O(n^2) O(n^2) O(1) 是
3 简单选择排序 O(n^2) O(n^2) O(n^2) O(1) 否
4 希尔排序 O(1) 否
5 快速排序 O(nlog2n) O(nlog2n) O(n^2) O(nlog2n) 否
6 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) O(1) 否
7 2路归并排序 O(nlog2n) O(nlog2n) O(nlog2n) O(n) 是
8 基数排序 O(d(n+r)) O(d(n+r)) O(d(n+r)) O(r) 是

7.6 外部排序

外部排序是指待排序文件较大，内存一次放不下，需存放在外存的文件的排序，通常采用归并排序法

  • 外部排序的总时间 = 内部排序的所需时间 + 外存信息读写的时间 + 内部归并所需的时间
  • 多路平衡归并与败者树
  • 置换选择排序
  • 最佳归并树

8. 总结

这次对于数据结构有了基本的了解，自己不知道的东西还是有许多的。