1顺序表&链表

A.顺序表

基本结构

1
2
3
4
5
6
7
8
typedef struct SeqList {

  ElemType elem[MAXSIZE];  /*线性表占用的数组空间*/

  int last;   
/*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/

} SeqList, LList, *LListPtr;
关于last

last=-1表示空表，last+1是实际元素个数

因为last是按照角标来的

插入

1
2
3
if (i < 1 || i > L->last + 2)

​    return false;

插 入：在前面插入

插入的范围：i∈[1,last+ 2 ]

last+2是在最后一个后面插入

插入从后向前移动

1
2
3
4
5
for* (int k = L->last; k >= i; --k)
​    L->elem[k + 1] = L->elem[k];
		/*k是数组下标*/
  L->elem[i - 1] = e;
  ++L->last;

复杂度O（n）

1
2
3
4
5
6
7
for* (int k = L->last; k >= i; --k)

​    L->elem[k + 1] = L->elem[k];

  L->elem[i - 1] = e;

  ++L->last;

删除

1
2
3
if* (i < 1 || i > L->last + 1)

​    *return* false;

删 除：删除指定节点

删除的范围：i∈[1,last+1]

删除从后向前移动

1
2
3
4
for* (int k = i - 1; k <= L->last; ++k)
​    L->elem[k] = L->elem[k + 1];
     /*k是数组下标，删除第i个，下表为i-1*/
  --L->last;

复杂度O（n）

注意：在长度为n的顺序表中的的末尾位置上插入/删除一个元素，其算法时间复杂度为O（1）。

1
2
3
4
5
for (int k = i - 1; k <= L->last; ++k)

​    L->elem[k] = L->elem[k + 1];

  --L->last;

！特别需要注意的是边界条件

在顺序表中，逻辑上相邻的两个元素物理存储上也一定也相邻。

线性表采用顺序存储，必须占用一段地址连续的存储单元。

线性表在顺序存储时，查找第i个元素的时间同i 的值无关。

顺序表结构适宜进行随机访问

顺序存储方式的优点是存储密度大

顺序存储中，插入和删除的效率比较低。

插入和删除操作是线性表的基本操作。这两种操作在数组中不常使用因为数组本身不能进行插入和删除，因为数组的长度是不可变的。（在某些语言中）

若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（顺序表）存储方式最节省时间。

练习题

假设删除长度为n的顺序表中的每个元素的概率相同，则删除一个元素平均要移动的元素个数是$(n-1)/2$。

在长度为n的顺序表中删除第i(1<=i<=n)个位置上的元素，需要移动的元素个数为$n-i$。

在长度为n的顺序表中的第i( 1 =< i <= n+1 )个位置上插入一个元素，需要移动的元素个数为$n-i+1$。

B.链表

①普通链表

1
2
3
4
5
6
7
typedef struct _node {

  ElemType data;

  struct _node  *next;

} Node, *NodePtr, LList, *LListPtr;

插入与删除

插入删除须从1开始，若有n个元素，

插入位置有效位置为 1~n+1；删除位置有效位置为 1~n

后插

初始位置 p = &L->head/L k=1;

k表示节点的标，与i同，无需加减1.

插入判断条件（可以一直移动到最后一个node的后一个，才会出现null）

1
2
3
4
5
6
7
while* ( p != NULL && k < i) {
    /*数到i-1(<=)/i(<)即可找到*/
​   p = p->next;
​    ++k;
  }
if (p == NULL) return false;
/*到头但还没找到i,那么就不对了；*/

注：当i=1时，插入时恰好k=1。没有移动。

删除判断条件

1
2
3
4
5
while* (p->next != NULL && k < i) {
​    p = p->next;
​    ++k;
  }
  *if* (p->next == NULL) *return* false;

注意是p->next不是p了，因为插入可以在插入后面插入，但删除不行

②循环链表

插入和删除

1
2
3
4
5
6
7
8
NodePtr p = L;
  /*由于p仍然从头结点开始，因此 k 仍然初始化为 1*/
  int k = 1;
  while (p->next != L && k < i) {
​    p = p->next;
​    ++k;
  }
  if (p->next == L && k < i) *return* false;

p->next == L 表示链表循环又到头了

③双向链表

初始化 (*L)->next=(*L)->prior=NULL;

判断条件（与其他同）

1
2
3
4
5
6
7
while* (p != NULL && k < i) {
​    p = p->next;
​    ++k;
  }

  *if* (p == NULL && k < i) *return* false;

插入
1
2
3
4
5
6
7
8
9
10
11
12
13
if* (p->next == NULL) { /*p指向最后一个元素*/
​    p->next =s;
​    s->next=NULL;
​    s->prior=p;
  } *else* {
​    p = p->next; /*因为是在节点前插入，因此需要再前进一步*/
​    s->prior=p->prior;
​    /*永远先将s链接前方*/
​    p->prior=s;
​    s->prior->next=s;
​    s->next=p;
  }

删除
1
2
3
4
5
6
7
8
9
10
11
p=p->next;

 //先放到要删除的位置，链接两边

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

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

 //此时p仍然指向被删去的内存，为无效指向。(请勿use after free)

 free(p);

链表插入、删除不需要移动元素；所需存储空间与线性表程度成正比；不必事先估计存储空间

链表添加头结点的目的是，简化操作，使得在表头和中间位置对链表的操作统一化。不一定是为了存储链表的长度。

顺序表的每个结点只能是一个基本类型，而链表的每个结点可以是一个构造类型。

栈和队列

栈

LIFO：先进后出

栈的两个结构

顺序栈

1
2
3
4
5
typedef struct {
  StackElementType elem[Stack_Size]; 
    //用来存放栈中元素的一维数组
  int top;         //用来存放栈顶元素的下标，top为-1表示空栈
} SeqStack, Stack, *StackPtr;

链式栈

1
2
3
4
typedef struct node {
  StackElementType data;
  struct node *next;
} LinkStackNode, *LinkStackNodePtr, LinkStack, Stack, *StackPtr;

弹栈与出栈

PUSH

1
S->elem[++S->top] = x;
1
2
3
temp->data = x;
temp->next = S->next;
S->next = temp;//头插法

POP

1
--S->top;
1
2
3
*x = temp->data;
S->next = temp->next;
free(temp);

但两者的接口相同 Push/Pop(StackPtr S, StackElementType x)

顺序表有“栈顶指针”，链表也有临时指针

异常返回

队列

FIFO：后进后出

链表结构

顺序表结构（循环）

判空判满
1
2
3
4
5
6
7
8
判断空
 Q->front==Q->rear;

判断满

 Q->front==(Q->rear+1)%MAXSIZE;
//rear从后面追上

注意：front的上一个单元一直未被用到。所以会浪费一个单元

串

串的定义

1
2
3
4
typedef struct {
  CHAR ch[MAXLEN];
  int len;
} String, *StringPtr;

插入时串的下标

–代表s；|代表t

1
2
3
4
    pos           max
-----||||-----
        A     B
A: pos+t->len    B:s->len+t->len-1
1
2
3
4
    pos           max
------||||----------------
         A         B
A POS+t->len    B max-1
1
2
    pos           max
------|||||||||||||||||---

串的匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int StrIndex(SString s,int pos, SString t) { 
    int i, j, start;
    if (t.len==0)  
        return(0);   /* 模式串为空串时，是任意串的匹配串 */
    start=pos; 
    i=start; 
    j=0;  		/* 主串从pos开始，模式串从头（0）开始 */
    while (i<s.len && j<t.len)
        if (s.ch[i]==t.ch[j]) {		
	i++;
	j++;
        }   /* 当前对应字符相等时推进 */
        else {		
	start++;        /* 当前对应字符不等时回溯 */
	i=start; 
	j=0;   /* 主串从start+1开始，模式串从头（0）开始*/
        } 
    if (j>=t.len) 
        return(start);    /* 匹配成功时，返回匹配起始位置 */
    else 
        return(-1);        /* 匹配不成功时，返回-1 */
}

块链串

块链串
定义如下

1
2
3
4
5
6
7
8
9
10
typedef struct _block {
    char ch[BLOCK_SIZE];    //块的数据域
    struct _block *next;    //块的指针域
} Block;

typedef struct {
    Block *head;        // 串的头指针
    Block *tail;        // 串的尾指针
    int len;            // 串的当前长度
} BLString;

读取关键

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
28
29
30
/*————I.跳过大节点————*/
//pos为正常串的字符的下标
 sub->head = p;//init head
        while (pos > 0) {
            if (a == BLOCK_SIZE) {
                a = 0;
                q = q->next;
            }//先把未到下标的节点(block)跳过
            //例如：共计4节点，16个字符，从14个字符开始，那么跳过1、2、3节点。
            a++;
            pos--;
            slen--;
        }
/*————II.小结点内读取字符————*/
		q->ch[a]=...
        while (...) {
            if (a == BLOCK_SIZE) {
                a = 0;
                q = q->next;//若本节点（node）读取完直接进入下一节点
            }
           
        }
        
/*例子*/
/*
qwer tyui opas dfgh
要读取第10号字符，从q开始，a=1，a++一直到a==4，那么a归零，进入下一节点
一直读取到a==10停止继续。
*/
//@icoding

树与二叉树

基本概念

度

☺结点的度：树中一个结点的子树的个数称为该结点的度。

☺树的度：树中各结点的度的最大值称为树的度，通常将度为m的树称为m次树或者m叉树

高度

树中结点的最大层次称为树的高度（或树的深度）。一般包含根节点

二叉树的性质

在二叉树的第i层上至多有$2^i-1$个结点(i≥1)

深度为k的二叉树至多有$2^k-1$个结点（k≥1）

对任意一棵二叉树T，若叶结点数为$n0$，而其度数为2的结点数为$n2$，则满足 $n0= n2+1$

具有n个结点的完全二叉树的深度为：$\lfloor log_{2}^n \rfloor +1$

对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为 i 的结点有：

  • ① 若 i = 1, 则 i 无双亲结点
    若 $i >1$, 则 i 的双亲结点为$\lfloor i/2 \rfloor$
  • ② 若 2i > n, 则 i 无左孩子
    若 $2i≤n$, 则 i 结点的左孩子结点为$ 2i $
  • ③ 若 2i +1 > n ,则 i 无右孩子
    若$ 2i +1≤n $, 则 i 的右孩子结点为$ 2i+1 $

二叉树的遍历

由遍历确定二叉树

$√$中序＋后序/先序 可以

$×$先序+后序 是不可以的！

非递归算法

先/中/后 序访问

基于栈

栈是递归的神奇

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
void Preorder(BiTree root){/* 先序遍历二叉树的非递归算法 */
    Stack s;
    init_stack(&s);
    if (root == NULL)
        return;
   
    BiTree p=root;
    while (p != NULL || !is_empty(&s)) {
        if (p != NULL) {
            push(&s, p);
            visit_node(p);
            p = p->left;
        } else {
            pop(&s, &p);
            p = p->right;
        }
    
    }
    return;

}
void InOrder(BiTree root, CALLBACK Visit) { /* 中序遍历二叉树的非递归算法 */
    Stack s, *S = &s;
    BiTree p;

    InitStack(&S);

    //TODO
    p = root;

    while (p != NULL || !IsEmpty(S)) {
        if (p != NULL) {
            Push(S, &p);
            p = p->LChild;
        } else {
            Pop(S, &p);
            Visit(p->data);
            p = p->RChild;
        }
    }

    ClearStack(S);
}


void PostOrder(BiTree root, CALLBACK Visit) {/* 后序遍历二叉树的非递归算法 */
    BiTNode *p, *q;
    Stack s, *S = &s;

    q = NULL;
    p = root;

    InitStack(&S);

    //TODO
    while (p != NULL || !IsEmpty(S)) {
        if (p != NULL) {
            Push(S, &p);
            p = p->LChild;
        } else {
            //Pop(S, &p);
            //Visit(p->data);
            GetTop(S, &p);
            if(p->RChild==NULL || p->RChild ==q) {
                Visit(p->data);
                Pop(S, &p);
                q = p;//q保存上一个访问的结点，用于判断是否需要访问右子树，如果q为空，则说明p是根结点，需要访问右子树，否则不需要访问右子树，因为q已经访问过了，不会再访问右子树
                p = NULL;//使得p为空，不进入循环，继续访问左子树
            }else{
                p=p->RChild;
            }
            p = p->RChild;
        }
    }

    ClearStack(S);
}

层级访问

基于队列,同一级别的节点加入队列。

先进先出，所以同一层级必须紧接着出来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void LayerOrder(BiTree tree, CALLBACK visit) {
    Queue q, *Q = &q;
    BiTree p;
    InitQueue(Q);
    
    EnterQueue(Q, tree);
    
    while(!IsEmpty(Q)) {
        DeleteHead(Q, &p);
        visit(p->data);
        if(p->LChild != NULL) {
            EnterQueue(Q, p->LChild);
        }
        if(p->RChild != NULL) {
            EnterQueue(Q, p->RChild);
        }

    }
    ClearQueue(Q);
}

递归题目

查找标签值相同的node
1
2
3
4
5
6
7
8
9
10
11
12
BiTree WhereIs(BiTree root, char node) {
    
    if(root==NULL) return NULL;
    if(root->data.tag==node) return root;
    
    BiTree p=WhereIs(root->LChild,node);
    if(p!=NULL) return p;
    p=WhereIs(root->RChild,node);
    if(p!=NULL) return p;

    return NULL;
}
两棵树是否结构相似
1
2
3
4
5
6
bool IsLike(BiTree t1, BiTree t2) {
    if(t1==NULL&&t2==NULL) return true;
    else if(t1==NULL||t2==NULL) return false;
    
    return IsLike(t1->LChild,t2->LChild)&&IsLike(t1->RChild,t2->RChild);
}

进阶：如果是镜像那么return IsLike(t1->LChild,t2->RChild)&&IsLike(t1->RChild,t2->LChild);

先序+中序确定二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
BiTree _Create(char *pre, char *in) {
    BiTNode *root;
    int j;
    if (*in == ‘\0’) return NULL;  //处理到了叶节点
    /*确立root位置*/
    for (j = 0; in[j] != *pre; ++j); //空循环，找到本次处理的根节点在中序遍历里的位置
    in[j++] = ‘\0’; //在这位置将中序序列分成两部分：左子树和右子树，置空的为root。
    
    root = (BiTNode *)malloc(sizeof(BiTNode)); //生成本次的根节点并填充数据
    root->data = *pre;
    root->LChild = _Create(pre + 1, in); //递归生成左子树
    root->RChild = _Create(pre + j, in + j); //递归生成右子树
    return root;    
}
树转二叉树
1
2
3
4
5
6
7
8
9
BiTree CS2Bi(CSTree rootCS) {
    if (rootCS == NULL) return NULL;
    BiTree rootBi = (BiTree)malloc(sizeof(BiTNode));
    rootBi->data = rootCS->data;
    rootBi->LChild = CS2Bi(rootCS->FirstChild);
    rootBi->RChild = CS2Bi(rootCS->NextSibling);
    //其第一个孩子最为左孩子，其他孩子接在右子树
    return rootBi;
}

其他

树的删除

删除二叉树应该是后序删除

普通树的遍历

先序访问与二叉树先序相同；

后序访问与二叉树中序相同；

普通树无中序

图

基本概念

邻接矩阵
邻接表

算法思想

查找出度和入度

邻接矩阵

A的出度：A所在矩阵的行中非∞值个数

A的入度：A所在矩阵的列中非∞值个数

邻接表

A的出度：p=A->firstarc,p进行遍历，每遇到一个即i++，输出i

A的入度：双重循环，遍历全图（除了A向量的链表），遇到A即i++，输出i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//求入度
void FindID(AdjList *G, int indegree[]) {
    int i;
    ArcNode *p;

    for (i = 0; i < G->vexnum; ++i)
        indegree[i] = 0;

    for (i = 0; i < G->vexnum; ++i) {
        p = G->vertex[i].firstarc;
        while (p != NULL) {
            ++indegree[p->adjvex];//****
            p = p->nextarc;
        }
    }
}

8-查找

线性查找

二分法

递归

1
2
3
if (bfind(1,m-1,key)!=-1)
	return ;
	bfind(m,h,key);

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int bfind(int a[], int len, int key) {
    int l, h, m;

    l = 0;
    h = len - 1;
    while (l <= h) {
        m = (l + h) / 2; // m = (l + h) >> 1;
        if (key == a[m]) return m;
        else if (key < a[m]) h = m - 1;
        else l = m + 1;
    }

    return -1;
}