C语言数据结构

发表于 更新于 分类于 Waline： 本文字数： 42k 阅读时长 ≈ 1:16

C语言–数据结构

---------------------------------------内容参考《郝斌数据结构》，《王道》《王卓》

未显示目录

一、数据结构之基础

1.数据结构的三要素

1.若采用顺序存储，则各个数据元素在物理上必须是连续的;若采用非顺序存储，则各个数据元素在物理上可以是离散的。
2.数据的存储结构会影响存储空间分配的方便程度
3数椐的存储结构会影响对数据运算的速度

数据的存储结构有几种

​ 线性

​ 连续存储（数组）

​ 优点：存储速度很快

​ 缺点：插入和删除元素很慢，空间通常是有限的

​ 离散存储（链表）

​ 优点：空间没有限制，插入删除元素很快

​ 缺点：存取速度很慢

2、存储结构

顺序结构

顺序存储,把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。

链式存储

链式存储，逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。（指针链接指针）

索引存储

索引存储。在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项，索引项的一般形式是（关键字，地址)离散的

散列存储

散列存储。根据元素的夭键字直接计算出该元素的存储地址，又称哈希（Hash）存储

3.算法特征：

确定性，可行性，输入，输出

好算法特征：

正确性，可读性，健壮性，高效率与低存储需求（时间，空间复杂度低）

image-20240911172342285

二、链表

1.数组的优缺点：

优点：存储速度快

缺点：需要一个连续很大的内存，插入和删除元素的效率很低

2.链表

优点：插入 删除元素效率高，不需要一个连续的很大内存

缺点：查找某个元素的效率低

3.术语：

首节点

  • 存放第一个有效数据的节点

尾节点

  • 存放最后一个元素的有效数据节点

头结点：

  1. 头结点的数据类型和首节点的类型是一样的
  2. 头结点是首结点前面的那个节点
  3. 头结点里面不存放有效数据
  4. 设置结点是为了方便对链表经行操作

头指针

  • 存放头结点的地址的指针变量
  • 可以通过头指针推算出链表的其他信息

4.链表的定义

  • n个节点离散分配
  • 彼此通过指针相连接
  • 每个节点只有一个前驱节点和后驱节点
  • 首节点没有前驱节点， 尾节点没有后续节点
1
2
3
4
5
6
typedef struct Node
{
    int date;//数据
    struct Node * pNext;//指向下一元素的指针域-递归（相同类型的指针)
}Node,*pNode;//node等价于struct Node,pNode等价于struct Node *

5.分类：

  • 单链表

  • 双链表

    ​ 每一个节点都有两个指针域

  • 循环链表

    ​ 能通过任何一个节点找到其他所有节点

  • 非循环链表

6.算法

遍历

查找

清空

销毁

排序

删除节点

插入节点

7.创建带头单链表并遍历输出

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
// Created by 李阳 on 2024/9/26.
/**
* 数据结构之链表
*/

#include <stdio.h>
#include <stdlib.h>

//定义单链表

typedef struct Node
{
    int data;//数据
    struct Node * pNext;//指向下一元素的指针域-递归（相同类型的指针)
}Node,* pNode;//node等价于struct Node,pNode等价于struct Node *

pNode creat_list();
void traverse_list(pNode pNode);

int main()
{
    pNode pHead =NULL;//等价于struct Node * pHead =NULL;
    pHead = creat_list();//创建一个非循环的单链表，并将该链表的头结点的地址给pHead
    traverse_list(pHead);//遍历
    return 0;
}

//创建单链表（带头）

pNode creat_list() {//返回值是一个地址
    int len;
    int i;
    int val;//用来临时存放用户输入的节点值
  //分配了一个不存放有效数据的头结点
    pNode pHead =(pNode) malloc(sizeof(Node));
    if(NULL==pHead)
    {
        printf("内存分配失败");
        exit(-1);
    }
    pNode pTail=pHead;//定义了一个指针变量，首先分配一个头节点 pHead。然后，将 pTail 初始化为指向这个头节点。由于此时链表为空，头节点也是尾节点。
    pTail->pNext=NULL;//地址为空

    printf("请输入链表的节点个数：len =");
    scanf("%d",&len);
    for ( i = 0; i < len; ++i) {
        printf("请输入第%d个节点的值",i+1);
        scanf("%d",&val);
        pNode pNew =(pNode) malloc(sizeof(Node));
        if(NULL==pNew)
        {
            printf("内存分配失败");
            exit(-1);
        }
        pNew->data=val;//将临时val的值放给新创的节点
        pTail->pNext=pNew;// 设置为指向新节点的指针，这样新节点就被添加到了链表的末尾
        pNew->pNext=NULL;
        pTail=pNew;//pTail 将指向链表的最后一个节点(更新，向后移）

    }
    return pHead ;
}

//遍历输出

void traverse_list(pNode pHead)
{
      pNode p=pHead->pNext;//定义了一个指针变量p，将链表的头指针给p
    while (NULL !=p)//p不为NULL时
    {
        printf("%d  ",p->data);//打印p的数据
        p=p->pNext;//p向后移
    }
    printf("\n");
}


8.※链表的基本操作※

带头结点的基本操作

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
//
// Created by 李阳 on 2024/11/12.
//带头单链表
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
    int data;
    struct Node * next;
}Node;


//初始化
Node * initList()
{
     Node * head=(Node *) malloc(sizeof(Node));
    if(!head)
    {
        printf("动态内存分配失败!");
        exit(1);
    }
    head->next=NULL;
    return head;
}


//尾插法
void instertATEnd(Node * head ,int date)
{
    Node * newNode=(Node *) malloc(sizeof(Node));
    if(!newNode)
    {
        printf("创建失败");
        exit(1);
    }
    newNode ->data=date;
    newNode->next=NULL;

    Node *temp=head;
    while (temp->next!=NULL)
    {
        temp=temp->next;
    }
    temp->next=newNode;
}

//头插法
void insertATHead(Node * head,int  data)
{
    Node * newNode=(Node *) malloc(sizeof(Node));
    if(!newNode)
    {
        printf("创建失败");
        exit(1);
    }
    newNode->data=data;
    newNode->next=head->next;//尾巴结点为NULL
    head->next=newNode;
}

//遍历
void printList(Node * head)
{
    Node * temp=head->next;
    while (temp!=NULL)
    {
        printf("%d  ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}

//删除指定元素
void deleteNode(Node * head, int data)
{
    Node * temp=head;
    while (temp->next!=NULL&&temp->next->data!=data)
    {
        temp=temp->next;
    }

    if(temp->next!=NULL)
    {
        Node * current=temp->next;
        temp->next=current->next;
        free(current);
    } else{
        printf("没找到哦");
    }
}

//返回指定元素
Node * findNode(Node* head,int data)
{
    Node * temp=head->next;
    while (temp!=NULL&&temp->data!=data){
        temp=temp->next;
    }
    return temp;// 返回找到的节点指针或NULL
}

// 获取链表的长度
int getListLength(Node* head) {
    int length = 0;
    Node* current = head->next; // 不计算头结点
    while (current != NULL) {
        length++;
        current = current->next;
    }
    return length;
}

// 释放链表内存的函数
void freeList(Node* head) {
    Node* current = head->next; // 从头结点的下一个节点开始释放
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
    free(head); // 最后释放头结点
}

int main()
{
    Node * head=initList();

    instertATEnd(head,1);
    instertATEnd(head,2);
    instertATEnd(head,3);
    instertATEnd(head,4);

    printf("尾插法");
    printList(head);

    printf("----------------------");
    printf("头插法\n");

    insertATHead(head,5);
    insertATHead(head,4);
    printList(head);

    //删除元素
    deleteNode(head,2);

    printList(head);

    // 获取链表长度
    int length = getListLength(head);
    printf("Linked list length: %d\n", length);

    // 释放链表内存
    freeList(head);

    return 0;

}


郝斌老师代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
// Created by 李阳 on 2024/9/26.
/**
* 数据结构之单链表
*/

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node
{
    int data;//数据
    struct Node * pNext;//指向下一元素的指针域-递归（相同类型的指针)
}Node,* pNode;//node等价于struct Node,pNode等价于struct Node *

pNode creat_list();
void traverse_list(pNode pNode);//遍历
bool is_empty(pNode pHead);//是否为空
int length_list(pNode);
bool insert_list(pNode,int ,int );
bool delete_list(pNode pHead,int pos,int *pval);
void sort_list(pNode);
int main()
{
    pNode pHead =NULL;//等价于struct Node * pHead =NULL;
    pHead = creat_list();//创建一个非循环的单链表，并将该链表的头结点的地址给pHead
    traverse_list(pHead);//遍历

    /*
    //判断链表是否为空
    if(is_empty(pHead))
    {
        printf("链表为空！\n");
    }
    else
    {
        printf("链表不空");
    }

     */

    /*
    //返回链表长度

    int len= length_list(pHead);
    printf("链表长度是 %d\n",len);

     */

    /*
    //排序
    printf("从小到大排序后的代码是：\n");
    sort_list(pHead);
    traverse_list(pHead);

    */

    /*
    //插入
    insert_list(pHead,3,44);
    traverse_list(pHead);

     */

    /*
    //删除
    int val;
    if(delete_list(pHead,3,&val))
    {
        printf("删除成功，您删除的元素是%d\n",val);

    } else
        printf("删除未成功\n");

    traverse_list(pHead);
     */
    return 0;
}

pNode creat_list() {//返回值是一个地址
    int len;
    int i;
    int val;//用来临时存放用户输入的节点值
  //分配了一个不存放有效数据的头结点
    pNode pHead =(pNode) malloc(sizeof(Node));
    if(NULL==pHead)
    {
        printf("内存分配失败");
        exit(-1);
    }
    pNode pTail=pHead;//定义了一个指针变量，首先分配一个头节点 pHead。然后，将 pTail 初始化为指向这个头节点。由于此时链表为空，头节点也是尾节点。
    pTail->pNext=NULL;//地址为空

    printf("请输入链表的节点个数：len =");
    scanf("%d",&len);
    for ( i = 0; i < len; ++i) {
        printf("请输入第%d个节点的值",i+1);
        scanf("%d",&val);
        pNode pNew =(pNode) malloc(sizeof(Node));
        if(NULL==pNew)
        {
            printf("内存分配失败");
            exit(-1);
        }
        pNew->data=val;//将临时val的值放给新创的节点
        pTail->pNext=pNew;// 设置为指向新节点的指针，这样新节点就被添加到了链表的末尾
        pNew->pNext=NULL;
        pTail=pNew;//pTail 将指向链表的最后一个节点(更新，向后移）

    }
    return pHead ;
}

void traverse_list(pNode pHead)
{
      pNode p=pHead->pNext;//定义了一个指针变量p，将链表的头指针给p
    while (NULL !=p)//p不为NULL时
    {
        printf("%d  ",p->data);//打印p的数据
        p=p->pNext;//p向后移
    }
    printf("\n");
}

//判断链表是否为空
bool is_empty(pNode pHead)
{
    if(NULL==pHead->pNext)
    {
        return true;
    } else
        return false;
}

//返回链表长度

int length_list(pNode pHead)
{
    pNode p=pHead->pNext;//定义了一个指针变量p，将头节点的地址给他
    int len =0;
    while (NULL!=p)//如果这里面是空的
    {
        ++len;//++
        p=p->pNext;//p指向下一个元素
    }
    return len;
}


//排序
void sort_list(pNode pHead)
{
int i,j,t;
int len = length_list(pHead);
pNode p,q;
    for ( i = 0,p=pHead->pNext; i <len-1 ; ++i,p=p->pNext) {//p放的是第一个元素，
        for (j = i+1,q=p->pNext; j <len ; ++j,q=q->pNext) {//q放的是p的后面的一个元素
            if(p->data > q->data)
            {
                t=p->data;
                p->data=q->data;
                q->data=t;
            }
        }
    }
    return;
}

//插入--在第pos的前面插入一个新的节点val，pos从1开始
bool insert_list(pNode pHead,int pos,int val)
{
    int i=0;
    pNode p=pHead;

    while (NULL!=p && i<pos-1)
    {
        p=p->pNext;
        i++;
    }
    if(i>pos-1 || NULL ==p)
    {
        return false;
    }


    pNode pNew =(pNode) malloc(sizeof (Node));

    if(NULL==pNew)
    {
        printf("动态内存分配失败\n");
        exit(-1);
    }
    pNew ->data=val;//定义了一个新节点，将val先放进去
    pNode q=p->pNext;//p此时已经来到了pos-1的地方，也就是他的前面，
    p->pNext=pNew;//将他的地址给pNew
    pNew->pNext=q;//再将pNew的下一元素的地址给next

    return true;
}


bool delete_list(pNode pHead,int pos,int * pval)
{
    int i=0;
    pNode p=pHead;

    while (NULL!=p->pNext && i<pos-1)
    {
        p=p->pNext;
        i++;
    }
    if(i>pos-1 || NULL ==p->pNext)//pos-1:eg:删除第3个必须要知道第二个
    {
        return false;
    }

    pNode q=p->pNext;//第pos个节点
    *pval=q->data;//将要删除的节点保存下来

    //删除p节点后面的节点
    p->pNext=p->pNext->pNext;
    free(q);
    q=NULL;


    return true;
}

9.顺序表的顺序存储结构

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
//
// Created by 李阳 on 2024/11/11.--线性表
//

#include <stdio.h>
#include <malloc.h>

#define MAXNUM 100
typedef int DateType;

typedef struct {
    DateType data[MAXNUM];//定义了一个数组
    int length;//当前长度
}SqList;

//初始化顺序表
void initList (SqList *L){
      L->length=0;
}

//插入元素
int ListInsert(SqList *L,int i,DateType d)//第i位置插入d
{
    if(i<1 || i>L->length+1)
    {
        return 0;//插入位置不合法
    }
    if(L->length>MAXNUM)
    {
        return 0;//表满了
    }

    for (int k = L->length; k >=i ; k--) //依次向后移
    {
        L->data[k]=L->data[k-1];
    }
    L->data[i-1]=d;//当用户输入在3的位置插入，其实是在索引2的位置，如果想
    L->length++;//修改，可以将k>=i改为k>i即可
    return 1;
}

//删
int ListDelete(SqList *L,int i,DateType *d)//删除第i个元素并保存在d中
{
    if(i<1||i>L->length)
    {
        return 0;
    }
    *d=L->data[i-1];//保存被删除的元素
    for(int k=i;k<L->length;k++)//找到被删除元素位置
    {
       L->data[k-1]= L->data[k];//向前移
    }
    L->length--;
    return 1;
}

//遍历
void TraverseList(SqList L)//这里传的L而不是*L是值传递，不需要对数据进行修改
{
    for (int i = 0; i < L.length; ++i) {
        printf("%d ",L.data[i]);
    }
    printf("\n");
}

//返回当前元素个数
int ListLength(SqList L)
{
    return L.length;
}

//修改指定位置元素
int ListUpdate(SqList *L,int i,DateType e)
{
    if(i<0||i>L->length)
    {
        return 0;
    }
    L->data[i-1]=e;
    return 1;
}

//查找索引为i的指定元素
int ListGit(SqList L,int i,DateType *x)
{
    if(i<0||i>L.length)
    {
        return 0;
    }
    *x=L.data[i];
    return 1;
}

// 查找元素的位置（返回第一个匹配元素的位置）
int LocateElem(SqList L, DateType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e) {
            return i + 1; // 返回的是位置索引，从1开始计数
        }
    }
    return 0; // 未找到
}

int main()
{
    SqList  L;
    initList(&L);//初始化

    //插入
    ListInsert(&L,1,1);
    ListInsert(&L,2,2);
    ListInsert(&L,3,3);
    ListInsert(&L,4,4);
    ListInsert(&L,5,5);
    ListInsert(&L,6,6);

    //遍历
    TraverseList(L);

    DateType d;
    //删除
    ListDelete(&L,2,&d);
    printf("删除的元素是：%d ",d);

    printf("\n");

    TraverseList(L);

}

三、栈

1.定义

​ 一种可以实现“先进后出”的存储结构

​ 栈类似于一个箱子，先放进去的后拿出来，后进去的先拿出来

2.分类

静态栈

动态栈

3.算法

​ 出栈

​ 压栈

链式代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
//
// Created by 李阳 on 2024/11/13.--链式栈
//
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int data;
    struct Node * next;
}Node;

//定义栈结构
typedef struct LinkedStack{
    Node * top;//栈顶指针，初始化为NULL表示空栈
} LinkedStack;

//初始化
LinkedStack * initStack(){
    LinkedStack * stack=(LinkedStack *) malloc(sizeof(LinkedStack));
    stack->top=NULL; // 初始化栈顶指针为NULL
    return stack;
}

//判断栈是否为空
int isEmpty(LinkedStack * stack)
{
    return stack->top==NULL;
}
/**
 * @param stack
 * @param data
 * 解析：hh看不懂了吧 让我来为你解析吧！
 * 首先我们定义了一个链表，然后一个空栈，里面有一个top指向NULL
 * 然后我们传入一个元素假设为1
 * 然后newNode->next=stack->top;// 新节点的next指向当前栈顶
    stack->top=newNode;
 *这俩是核心代码 我们直接说这个
 * stack->top上面初始化为NULL
 * 所以newNode->next里面就是NULL
 * 然后newNode为指针类型的， stack->top=newNode;就是将top指向了他的指针
 * 我理解的是双胞胎，栈的top的指针就指向了NewNode
 * 假设我们现在又传入了一个2
 * newNode->next=stack->top
 * 2的next里面放的是1的地址
 * stack->top=newNode;
 * 我们又将2的地址给了top，类似top再向上移动
 * 宇宙第一聪明的你听明白了吗
 */

//入栈
void push(LinkedStack* stack,int data){
    Node * newNode=(Node *) malloc(sizeof(Node));
    newNode->data=data;

    newNode->next=stack->top;// 新节点的next指向当前栈顶
    stack->top=newNode;
}

/**
 * @param stack
 * @return
 * 我又来啦，现在由李阳为你解析链栈的出栈
 * 我们这个是有返回值的，首先传入一个栈是毋庸置疑的
 * 还需要一个小小的判断-如果栈里面没有元素呢
 * -------核心代码要来喽----
 * 首先我们定义了一个临时变量temp用于存放栈顶，
 * 这里top里面放的是最后一个元素的地址
 * 根据地址可以找到元素没问题吧
 * 然后我们再将栈顶的元素的下一个地址重新给top
 * 我们之前top里面放的是栈顶的地址，现在我们变成传入栈顶
 * 的下一元素的地址，也就是将top向下移动
 * 现在明白了吗 o.O
 */

int pop(LinkedStack * stack){
    if(isEmpty(stack))
    {
        printf("栈是空的");
        return -1;
    }
    Node * temp=stack->top;
    int  popData=temp->data;
    stack->top=temp->next;
    free(temp);
    return popData;
}

//打印
void printStack(LinkedStack *stack)
{
    Node *temp=stack->top;
    while (temp!=NULL)
    {
        printf("%d  ",temp->data);
        temp=temp->next;
    }
    printf("NULL\n");
}

//取出栈顶元素
int StackTop(LinkedStack*stack)
{
    Node * temp=stack->top;
    if(temp==NULL)
    {
        printf("栈为空");
        return 0;
    }
    int topdata=temp->data;
    return topdata;

}

//释放
void freeStack(LinkedStack*stack)
{
      Node * temp=stack->top;
      Node *nextNode;
    while (temp!=NULL)
    {
        nextNode=temp->next;
        free(temp);
        temp=nextNode;
    }
    free(stack);
}

//来检验一下吧^_^
int main()
{
    LinkedStack *stack=initStack();//初始化
    push(stack,1);
    push(stack,2);
    push(stack,3);
    push(stack,4);

    printStack(stack);
    printf("\n");

  int a=  StackTop(stack);
    printf("栈顶元素是：%d ",a);

    printf("\n");
    int b= pop(stack);
    printf("%d出栈了",a);

    printf("\n");
    printStack(stack);

    freeStack(stack);
}

郝斌老师代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/**
 * 数据结构之栈 o.O
 *  Created by 李阳 on 2024/10/9.
 */

#include <stdio.h>
#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

typedef struct Node
{
    int data;
    struct Node *pNext;
}Node,*pNode;
//栈
typedef struct Stack
{
    pNode pTop;//元素顶部
    pNode pBottom;//元素底部
}sTack,*pStack;

void initStack(pStack);
void pushStack(pStack pS,int val);
void traverse(pStack);
bool popStack(pStack,int *);
bool empty(pStack pS);
void clear(pStack pS);
int main()
{
    int val;
   sTack S;//sTack等价于 struct Stack--建立了一个名为S的成员变量，里面有两个元素，ptop和pbottom，里面暂时没有有效数据

   initStack(&S);//初始化-造出空栈
   pushStack(&S,1);//压栈
    pushStack(&S,2);//压栈
    pushStack(&S,3);//压栈
    pushStack(&S,4);//压栈

    traverse(&S);//输出

    //清空
    clear(&S);
   // traverse(&S);//输出


    //出栈
    if( popStack(&S,&val))
        printf("出栈成功，出栈的元素是：%d\n",val);
    else
        printf("出栈失败\n");


   traverse(&S);//输出

    return 0;
}

//初始化
void initStack(pStack pS)
{
    pS->pTop=(pNode)malloc(sizeof (Node));//将top指向一个新造的空节点
    if(NULL==pS->pTop)
    {
        printf("内存分配失败\n");
        exit(-1);
    }
    else
    {
        pS->pBottom=pS->pTop;//地址都指向空节点
        pS->pTop->pNext=NULL;//将新造的节点的指针域为空--因为他是最后一个元素的下一个元素，因此没有指针域
    }

}

//压栈--进栈
void pushStack(pStack pS,int val)
{
    pNode pNew=(pNode) malloc(sizeof (Node));
    pNew->data=val;
    pNew->pNext=pS->pTop;//此时ptoop里面放的是初始化时的临时变量地址，这里调用，将新建的栈的指针域指向初始化的元素地址
    pS->pTop=pNew;//再将新的节点地址给top
}

//遍历
void traverse(pStack pS)
{
    pNode p=pS->pTop;//定义个临时指针变量p，将头的值给p，
    while (p!=pS->pBottom)//当p为底部元素时程序终止
    {
        printf("%d",p->data);
        p=p->pNext;//p指向p的下一元素地址
    }
    printf("\n");
}

//出栈
bool empty(pStack pS)
{
    if(pS->pTop==pS->pBottom)
        return true;
    else
        return false;
}
bool popStack(pStack pS,int * pVal)//把ps所指向的栈出栈一次，并将出栈元素存入pval新参所指向的变量中，成功返回true，否则false
{
     if(empty(pS))
     {
         return false;
     }
     else
     {
        pNode r=pS->pTop;//定义一个变量r，将顶元素给r
        *pVal=r->data;
        pS->pTop=r->pNext;//再将top指向下一元素，这样r就被孤立了
         free(r);
         r=NULL;
         return true;
     }

}

//清空表
void clear(pStack pS)
{
    if(empty(pS))
    {
        return;
    }
    else
    {
    pNode p=pS->pTop;
    pNode q=NULL;
        while (p!=pS->pBottom)
        {
            q=p->pNext;//q指向第二个
            free(p);
            p=q;//p又指向了下一个元素了
        }
        pS->pTop=pS->pBottom;
    }
}

4.应用

函数调用

中断

表达式求值

内存分配

缓存处理

迷宫

5.栈的表达式求值–后缀表达式（逆波兰表达式）

1.例如：1+2*3

​ 后缀表达式为 1 2 3 * +

​ 遇到一个运算符他会在前面两个数字间运算

  1. ​ 2 *3
  2. 然后向后移到+
  3. 6+1

2、(a + b) * (c - (d / e)) + f

1
a b + c d e / - * f +

3.、a * (b + c) - (d / e)

1
a b c + * d e / -

4、a + b * (c - d / e) ^ f

1
a b c d e / - f ^ * +

总结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1. 操作数和运算符
操作数（如变量和常数）直接添加到输出列表中。
运算符则需要根据优先级和括号来决定是否入栈、弹出或保持在栈中。
2. 运算符优先级
运算符的优先级从高到低一般为：
* 和 / （乘法和除法）优先级高
+ 和 - （加法和减法）优先级低
在遇到相同优先级的运算符时，按照左结合性处理（从左到右）。
3. 括号的处理
遇到左括号 ( 时，直接入栈。
遇到右括号 ) 时，弹出栈中的运算符到输出，直到遇到对应的左括号为止，左括号被丢弃。
4. 栈的使用
当一个运算符被处理时，检查栈顶运算符的优先级：
如果栈顶运算符的优先级高于或等于当前运算符，则弹出栈顶运算符到输出。
否则，将当前运算符入栈。
5. 表达式结束时的处理
当整个中序表达式处理完毕后，仍有运算符在栈中时，将它们全部弹出到输出。
6. 后缀表达式的特征
后缀表达式不需要括号，因为运算符的顺序和位置已经明确了运算的优先级和关联性。

当一个运算符被处理时，检查栈顶运算符的优先级：
如果栈顶运算符的优先级高于或等于当前运算符，则弹出栈顶运算符到输出。
否则，将当前运算符入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
当然可以，关于将中序表达式转换为后缀表达式（也称为逆波兰表达式）时处理括号和运算符的一些规律，可以总结如下：

括号处理：
左括号 (：在遇到左括号时，通常不需要立即进行任何操作，但可以将其视为一个标记，表示一个新的运算范围的开始。在某些实现中，可能会使用一个辅助栈来跟踪左括号的位置或数量。
右括号 )：当遇到右括号时，需要开始从运算符栈中弹出运算符，并将它们添加到后缀表达式中，直到遇到对应的左括号或栈为空。弹出的运算符应该按照它们被压入栈的顺序的逆序添加到后缀表达式中。
运算符栈：
运算符栈用于存储等待处理的运算符。当遇到一个新的运算符时，需要将其与栈顶的运算符进行比较，以确定是否需要弹出栈顶的运算符（基于运算符的优先级）。
栈顶的运算符具有更高的优先级时（或者当前运算符需要右结合时），它应该被弹出并添加到后缀表达式中。这个过程一直持续到栈顶的运算符优先级低于或等于当前运算符，或者栈为空。
操作数处理：
操作数（如变量、常量等）直接添加到后缀表达式中，不需要经过运算符栈的处理。
运算符优先级和结合性：
运算符的优先级决定了在相同位置上的运算符哪个应该先被处理。例如，乘法和除法的优先级高于加法和减法。
运算符的结合性决定了当两个运算符具有相同的优先级时，它们应该如何组合。例如，加法和乘法都是从左到右结合的。
后缀表达式的构建：
后缀表达式是通过从左到右扫描中序表达式，并根据上述规则处理运算符和括号来构建的。
最终的后缀表达式应该只包含操作数和运算符，并且运算符的顺序应该反映了它们在中序表达式中的计算顺序。
验证：
一个简单的方法来验证后缀表达式是否正确是将其转换回中序表达式（这通常涉及使用一个额外的栈来模拟计算过程），并检查转换后的中序表达式是否与原始表达式相同。
另一种方法是直接计算后缀表达式和原始中序表达式的值，并检查它们是否相等。
这些规律是理解和实现中序表达式到后缀表达式转换的关键。通过遵循这些规律，可以确保转换过程的正确性和效率。

四、队列

1、定义

​ 一种可以实现“先进先出”的存储结构–排队买票进站

2.分类

​ 链式队列（链表）

​ 静态队列（数组）

​ 静态队列通常都必须是循环队列

​ image-20241010163206657

3.代码

链式队列

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
//
// Created by 李阳 on 2024/11/13.--链式队列
//
#include <stdio.h>
#include <stdlib.h>

// 定义节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;
// 定义队列结构
typedef struct LinkedQueue {
    Node* front;  // 队头指针
    Node* rear;   // 队尾指针
} LinkedQueue;

LinkedQueue * initQueue()
{
    LinkedQueue * queue=(LinkedQueue*) malloc(sizeof(LinkedQueue));
    queue->front=queue->rear=NULL;
    return queue;
}


// 判断队列是否为空
//返回0为空，1不为空所以为int类型
int isEmpty(LinkedQueue* queue) {
    return queue->front == NULL;
}

//入队
void enqueue (LinkedQueue * queue,int data)
{
    Node *newNode=(Node* ) malloc(sizeof(Node));
    newNode->data=data;
    newNode->next=NULL;

    if(isEmpty(queue))
    {
        queue->front=queue->rear=newNode;
    } else{
        queue->rear->next=newNode;
        queue->rear=newNode;
    }
}

int dequeue(LinkedQueue * queue)
{
    if(isEmpty(queue))
    {
        printf("队列是空的");
        return -1;
    }

    Node *temp=queue->front;//先进先出
    int deque=temp->data;
    queue->front=queue->front->next;

    if(queue->front==NULL){
        queue->rear=NULL;
    }
    free(temp);
    return deque;
}

//打印
void printQueue(LinkedQueue*queue)
{
    Node *temp=queue->front;
    while (temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("NUll\n");
}

//释放
void freeQueue(LinkedQueue*queue)
{
    Node * temp=queue->front;
    Node * nextNode;
    while (temp!=NULL)
    {
        nextNode=temp->next;
        free(temp);
        temp=nextNode;
    }
    free(queue);
}
//取队头元素
int getFront(LinkedQueue*queue)
{
    if(isEmpty(queue))
    {
        printf("队列为空");
        return -1;
    } else{
        int temp=queue->front->data;
        return temp;
    }

}

int main() {
    LinkedQueue* queue = initQueue();

    enqueue(queue, 10);
    enqueue(queue, 20);
    enqueue(queue, 30);

    printQueue(queue);  // 打印队列内容
    printf("\n");
    int temp = getFront(queue);
    printf("队头%d \n",temp);

    printf("Dequeued: %d\n", dequeue(queue));
    printf("Dequeued: %d\n", dequeue(queue));

    printQueue(queue);  // 再次打印队列内容

    freeQueue(queue);  // 释放队列内存

    return 0;
}

郝斌老师代码

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/**
* Created by 李阳 on 2024/10/14.
 * 数据结构之静态循环队列o.O
*/

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

typedef struct Queue
{
    int *pBase;
    int front;//首
    int rear;//尾
} QUEUE;

void init(QUEUE *);//改变实参的值所以要加*
bool en_queue(QUEUE *,int);//入队列
void traverse_queue(QUEUE *);//遍历
bool full_queue(QUEUE *);//判断是否满
bool out_queue(QUEUE *,int *pVal);//出队
bool emput_queue(QUEUE *);//判断是否为空
int main()
{
    QUEUE Q;
    int val;
    init(&Q);//调用初始化函数
    en_queue(&Q,1);
    en_queue(&Q,2);
    en_queue(&Q,3);
    en_queue(&Q,4);
    en_queue(&Q,5);
    traverse_queue(&Q);
    
    if (out_queue(&Q, &val)) {
        printf("出队成功: %d\n", val); // 修正输出格式
    } else {
        printf("出队失败\n");
    }
    traverse_queue(&Q);
    return 0;
}

//初始化
void init(QUEUE *pQ)
{
    pQ->pBase=(int *) malloc(sizeof (int)*6);//定义了6个数据的数组
    pQ->front=pQ->rear=0;//初始化


}

//入队
bool en_queue(QUEUE *pQ,int val)
{
    if(full_queue(pQ))
    {
        printf("队列满啦");
        return false;
    } else
    {
        pQ->pBase[pQ->rear]=val;//将值放入尾部，并且尾部要+1
        pQ->rear=(pQ->rear+1)%6;//尾部+1--因为是循环队列，当他满的时候会又从0开始
        return true;
    }
}

//判断是否为满
bool full_queue(QUEUE *pQ)
{
    if((pQ->rear+1)%6==pQ->front)
        return true;
    else
        return false;
}

//遍历
void traverse_queue(QUEUE *pQ)
{
    int i=pQ->front;
    while ((i!=pQ->rear))
    {
        printf("%d",pQ->pBase[i]);
        i=(i+1)%6;
    }
    printf("\n");

}

//判断是否空
bool emput_queue(QUEUE * pQ)
{
    if(pQ->front==pQ->rear)
    {
       return true;
    } else
        return false;

}

//出队
bool out_queue(QUEUE * pQ,int *pVal)//因为要带回来值，所以要*
{
   if(emput_queue(pQ))
   {
       printf("表是空的");
       return false;
   } else
   {
     *pVal=pQ->pBase[pQ->front];
     pQ->front=(pQ->front+1)%6;
       return true;
   }
}

4.队列的操作

所有和时间有关的操作

五、递归

image-20241015182021998

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
/**
* 数据结构之递归
 * Created by 李阳 on 2024/10/15.
*/
#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

//demo1--求阶层
/* for循环版
int jiec(int a)
{
    int b=1;
    int i;
    for ( i=1; i <=a; ++i)
    {
        b=b*i;
    }
    return b;
}

int main()
{
    int b=5;
    int a= jiec(b);
    printf("%d 的阶层是 %d",b,a);
}

*/

//递归版
long f(long n)
{
    if(1==n)
    {
        return 1;
    } else
    {
        return f(n-1)*n;
    }

}
int main()
{
   long a,b;
    printf("请输入要求的阶层");
    scanf("%d",&a);
    b= f(a);
    printf("%ld 的阶层是 %ld",a,b);
}

 


//递归实现1+2+...
long sum(long n)
{
    if(n==1)
    {
        return 1;
    } else
    {
        return sum(n-1)+n;
    }
}

2.定义，要求，意义

①定义：

一个函数间接或直接调用自己

②递归需要满足的三个条件

  1. 递归必须要有一个明确的终止条件
  2. 该函数所处理的数据规模必须在递减
  3. 这个转化必须是可解的

③意义

优点：易于理解

缺点：速度慢，存储空间大

④循环：

不易理解，速度快，存储空间小

六、串、数组和广义表

一、串（string）

0个或多个任意字符组成的有限序列

1.子串的定义

一个串中任意个连续字符组成的子序列（含空串）称为该串的子串

例如：“abcd”的子串有

“ ”，“a",“ab”,“abc”,“abcd”

真子串：是指不包含自身的所有子串

主串:包含子串的串相应的称为主串

字符位置:字符在序列中的序号为该字符串中的位置

子串位置：子串第一个字符在主串中的位置

**空格串：**由一个或多个空格组成的串，与空串不同

image-20241015220006062

**串相等:**当且仅当两个串的长度相等并且各个对应立置上的字符都相同时，这两个串才是相等的。

2.串的类型定义、存储结构及运算

顺序存储结构-顺序串

链式存储结构-链式串

3.串的表示

顺序存储
1
2
3
4
5
6
7
//串的顺序存储结构
#define MAXLEN 255
typedef struct {
    char ch[MAXLEN+1];//存储串的一维数组1-255
    int length;//串的当前长度
}SString;

链式存储
1
2
3
4
5
6
7
8
9
10
11
12
//串的链式存储结构--块链结构
#define CHUNKSIZE 80
typedef struct Chunk {
    char ch[CHUNKSIZE]; // 存储字符块
    struct Chunk *next;  // 指向下一个块的指针
} Chunk;

typedef struct {
    Chunk *head;  // 串的首指针
    Chunk *tail;  // 串的尾指针
    int curlen;   // 串的当前长度
} LString;

4.串的模式匹配

1.BF算法（穷举法）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int index_BF(SString S,SString T)
{
    int i=1,j=1;
    while (i<=S.length&&j<=T.length)
    {
        if(S.ch[i]==T.ch[j])
        {
            i++;
            j++;
        } else
        {
            i=(i-j)+2;j=1;
        }
    }
  if(j>T.length)
      return i-T.length;//匹配成功
  else
      return 0;
}

image-20241016164724670

2.※※※ KMP算法

image-20241017130343420

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
// 计算模式串 T 的 next 数组
void get_next(SString T, int next[]) {
    int i = 1;  // T 的当前位置
    int j = 0;  // 前缀的长度
    next[1] = 0; // next[0] 通常设为 0

    while (i < T.length) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            i++;
            j++;
            next[i] = j; // 注意：next[i] 是 i 位置的前缀长度
        } else {
            j = next[j - 1]; // 使用 next 数组回溯
        }
    }
}

// KMP 算法实现，返回模式串 T 在主串 S 中首次出现的位置
int Index_KMP(SString S, SString T, int next[]) {
    int i = 1;  // S 的当前位置
    int j = 1;  // T 的当前位置
    while (i <= S.length && j <= T.length) {
        if (j == -1 || S.ch[i] == T.ch[j]) { // j = -1 表示需要跳过
            i++;
            j++;
        } else {
            j = next[j]; // 使用 next 数组回溯
        }
    }
    if (j == T.length) return i - T.length; // 匹配成功，返回匹配位置
    else return -1; // 匹配失败，返回 -1
}
}
3.KMP算法改进

image-20241017144344602

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void get_nextval(SString T, int nextval[]) {
    int i = 1;  // T 的当前位置
    int j = 0;  // 前缀的长度
    nextval[1] = 0; // next[0] 通常设为 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]; // 使用 next 数组回溯
        }
    }
}

二、数组

1.定义

按照一点格式排列起来的具有相同的数据元素集合

一维数组：若线性表中的元素为非结构的简单元素，则称为一维数组（线性结构，定长的线性表）

二维数组：若一维数组中的元素又是一维数组结构，则称为二维数组

二维数组逻辑结构：

  • 非线性结构： 每一个元素既在一个行表中，又在一个列表中
  • 线性结构：该线性表的每一个元素也是一个定长的线性表

数组特点：结构固定–定义后，维度和为界不再改变

结论:

  • 线性表结构是数组的一个特例
  • 而数组结构又是线性表结构的扩展

基本操作：除了结构的初始化和销毁之外，只有取元素和修改元素值的操作

一般采用顺序结构来表示数组

2.存储位置

image-20241017154244958

数组元素a[i] [j] 的存储位置是 LOC(i,j)=LOC(0,0)+n * i+j * L(L是存储每个元素所需要L个存储单元)

3.压缩存储

  1. 什么是压缩存储?
    若多个数据元素的值都相同，则只分配一个元素值的存储空间，且零元素不占存储空间
  2. 什么样的矩阵能够压缩?
    一些特殊矩阵，如:对称矩阵，对角矩阵，三角矩阵，稀疏矩阵等。
  3. 什么叫稀疏矩阵?
    矩阵中非零元素的个数较少（一般小于5%)
1.对称矩阵
  1. [特点]

    沿着对角线对称

    在nxn的矩阵a中，满足如下性质: aij=aji (1 ≤i, j <n)

  2. [存储方法]

    只存储下(或者上)三角(包括主对角线)的数据元素。共占用n(n+1)/2个元素空间。

image-20241017155259933

image-20241017155934811

2.三角矩阵
  1. [特点]

    对角线以下(或者以上)的数据元素(不包括对角线)全部为常数co

  2. [存储方法]

    重复元素c共享一个元素存储空间，共占用n(n+1)/2+1个元素空间: sa[1… n(n+1)/2+1]

image-20241017160251060

3.对角矩阵（带状矩阵）

[特点]在nxn的方阵中，所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为对角矩阵。常见的有三对角矩阵、五对角矩阵、七对角矩阵等。

image-20241017160553699

image-20241017160653491

4.稀疏矩阵

稀疏矩阵:设在mxn的矩阵中有t个非零元素。
令ɸ= t/(mxn)
当ɸ≤0.05时称为稀疏矩阵。

三元组顺序表又称有序的双下标法。

  1. 三元组顺序表的优点:非零元在表中按行序有序存储，因此便于进

    行依行顺序处理的矩阵运算。

  2. 三元组顺序表的缺点:不能随机存取。若按行号存取某一行中的非

    零元，则需从头开始进行查找。

十字链表

优点:它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算
image-20241017162515773

image-20241017162538457

image-20241017163651081

三.广义表

1.定义

广义表 （又称列表Lists）是n≧0个元素 a0,a1…an-1的有限序列，其中每一个ai或者是原子，或者是一个广义表

image-20241017164155126

  • 广义表通常记作:Ls=(a1, a2,…，an)

    其中:LS为表名，n为表的长度，每一个ai为表的元素

  • 习惯上，一般用大写字母表示广义表，小写字母表示原子。

  • **表头：**若LS非空(n≥1)，则其第一个元素a1就是表头。
    记作head(LS) = a1。注:表头可以是原子，也可以是子表。

  • 表尾：除表头之外的其它元素组成的表。

    ​ 记作tail(LS） = (a2, … an)。

    ​ 注:表尾不是最后一个元素，而是一个子表。

image-20241017170321265

2.性质

  • (1)广义表中的数据元素有相对次序;一个直接前驱和一个直接后驱

  • (2)广义表的长度定义为最外层所包含元素的个数;

    ​ 如: C=(a (b, q))是长度为2的广义表。

  • (3)广义表的深度定义为该广义表展开后所含括号的重数;

    ​ A=(b ,c)的深度为1,B=(A,d)的深度为2，C=(f, B,h)的深度为3。

    ​ 注意:“原子”的深度为0;“空表”的深度为1。

  • 广义表可以为其他广义表共享，如：广义表B就共享了广义表A。在b中不必列出A的值，而是通过名称来引用，B=(A)

  • 广义表可以是一个递归的表。如：F=（a,F=(a,(a,(a,…)))

​ 注意：递归表的深度是无穷值，长度是有限值，这里长度是2

  • 广义表是多层次结构，广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，….。
    可以用图形象地表示。
    例:D=(E，F）其中:E=(a, (b,c)）F=(d,(e))

3.广义表和线性表的区别

  1. 广义表可以看成是线性表的推广，线性表是广义表的特例。
  2. 广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。
  3. 当二维数组的每行(或每列)作为子表处理时，二维数组即为一个广义表。
  4. 另外，树和有向图也可以用广义表来表示。
  5. 由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。

4.广义表的基本运算

image-20241031143536962

案例分析

image-20241031144308247

代码实现

七、树

1.树的定义

image-20241031144903388

树的定义

树(Tree)是n (n≥0)个结点的有限集。(递归)
若n =0，称为空树;
若n >0，则它满足如下两个条件:
(1)有且仅有一个特定的称为根(Root)的结点;
(2)其余结点可分为m (m≥0)个互不相交的有限集T1,T2,T3,…Tm，其中每一个集合本身又是一棵树，并称为根的子树(SubTree)。

树的基本术语

结点：数据元素以及指向树的分支

根结点：非空树中无前驱点的结点

结点的度：结点拥有的子树数

​ eg: A 3,B 2,F 0

image-20241031152141050

树的度： 数内各结点的度的最大值

**叶子结点：**终端结点（度为0）

​ eg: k L G M J

**分支结点：**非终端结点

​ eg: B,C,D…

**内部结点：**根节点以外的分支结点称为内部结点

**孩子结点：**结点的子树的根称为孩子

双亲结点：孩子结点的前驱

image-20241031154837095

​ eg: BCD是A的孩子结点，A是bcd的双亲结点

兄弟结点：同级的结点

**祖先结点：**从根到该结点所经分支上的所有结点

​ eg: M的祖先结点为H,D,A

**子孙结点：**从某结点为根的子树的任意结点

​ eg: D的孙子有HM

**树的深度：**树中结点的最大层次

**有序树：**树中的各子树从左至右有次序(最左边为第一个孩子)

**无序树：**树中结点的各子树无次序

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

image-20241031160124987

​ 树一定是森林，森林不一定是树

树结构和线性结构的比较

image-20241031160854242

2.二叉树的定义

image-20241031161122434

定义

​ 二叉树是n(n>=0)个结点的有限集，它或者是空集(n= 0),或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

特点

  1. 每个结点最多有俩孩子(二叉树中不存在度大于2的结点)。
  2. 子树有左右之分，其次序不能颠倒。
  3. 二叉树可以是空集合，根可以有空的左子树或空的右子树。

树和二叉树区别

  • 二叉树不是树的特殊情况，它们是两个概念
  • 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也经行区分，说明它是左子树，还是右子树。
  • 树当结点只有一个孩子时，就无须区分它是左还是右的次序。因此二者是不同的。这是二叉树与树的最主要的差别。
  • (也就是二叉树每个结点位置或者次序都是固定的，可以是空，但是个可以说它没有位置，而树的结点位置是相对于别的结点来说的，没有别的结点时.它就无所谓左右了)

image-20241031161802875

image-20241031161947956

3.案例引用

image-20241031162420574

4.树和二叉树的抽象数据类型定义

image-20241031162925621

image-20241031170614463

5.二叉树的性质和存储结构

1.性质

满二叉树与完全二叉树

满二叉树：一颗深度为且有个结点的二叉树就叫满二叉树

完全二叉树：深度为的具有个结点的二叉树，当且仅当每一个结点都与深度为的满二叉树中的编号为的结点一一对应时，称为完全二叉树（叶子结点的编号是连续的,左侧树必须满元素)

  • 叶子只可能分布在层次最大的两层上，
  • 对任意结点，如果其右子树的最大层次为i，则其左子树的最大层次必为i或i+1

image-20241031204537868

性质1

​ 在二叉树的第i层上至多有个结点

性质2

​ 深度为k的二叉树至多有 个结点(k>=1)

性质3

​ 对任何一个二叉树,如果其叶子为,度为2的结点为，\则

image-20241031173605833

​ eg:这里叶子结点7 8 9 10 11 12有6个,度为2的有1 2 3 4 5 有五个

总结点数n 又

总边个数B =

性质4

具有n个结点的完全二叉树的深度为

性质5

如果有一颗个结点的完全二叉树(深度为 [)的结点按层编号(从第1层到第[层，每层从左到右)，对任一结点i(1<=<=n),有

  1. 如果=1，则结点i是二叉树的根，无双亲;如果i>1，则其双亲是结点[i /2]。
  2. 如果2，则结点i为叶子结点，无左孩子;否则，
    其左孩子是结点2i。
  3. 如果，则结点无右孩子;否则，其右孩
    子是结点2i + 1。

总结: 编号为i，他的父结点为,左结点为2i，右节点

2.存储结构

image-20241031214118623

1.二叉树的顺序存储结构

  • 实现：按满二叉树的结点层次编号，依次存放在二叉树的数据元素

    1
    2
    3
    #define MAXTSIZE 100
    typedef  int SqBiTree[MAXTSIZE];
    SqBiTree bt;

    image-20241102133931076

  • 缺点： image-20241102134705813

    结点间的关系蕴含在其存储位置中，浪费空间，适合满二叉树和完全二叉树

2.二叉树的链式存储结构
1
2
3
4
5
typedef struct BiNode
{
    int data;
    struct BiNode *lchild,*rchile;//左右孩子
}BiNode,*BiTree;

image-20241102135937947

在n个结点的二叉链表中，有个空指针域

必有2n个链域，除根节点外，每个结点有且仅有一个双亲，所有只会有n-1个结点的链域存放指针，指向非空子女结点

3.三叉链表
1
2
3
4
typedef struct TriTNode{
    int data;
    struct TriTNode *Ichild,*parent,*rchild;//指向双亲结点
}TriTNode,*TriTree;

3.遍历二叉树和线索二叉树

1.类型

先序遍历：根左右

中序遍历：左根右

后续遍历：左右根

image-20241102144633249

先–根左右

image-20241102150119954

ABELDHMIJ

中–左根右

image-20241102150600713

ELBAMHIDJ

后–左右根

image-20241102151437701

LEBMIHJDA

实例：6E50FE1F8569BEB2D29488718E198F13

image-20241102154045025

2.根据遍历序列确定二叉树（先 中 后序）

  • 若二叉树中的各结点均不相同，则二叉树结点的先徐序列、中序序列和后序序列都是唯一的

  • 由二叉树的先序和中序序列，或由二叉树的后序和中序序列可以确定唯一一颗二叉树

实例1：先序+中序

先：A B C D E F G H I

中：C D B F E A I H G J

解题思路

  1. 由先知A必为根，B必为左 由中知 CDBFE在左部，IHGJ在右边

    image-20241102180223951

  2. 由先序知道B为根，由中序知道CD为左子树，FE为右子树

    image-20241102180244711

  3. 由先序知道G是根，那么I H为左子树，J为右子树

    image-20241102181222814

  4. 由中序CD左根右知道，c为左，d为右，先序知道E为根，中序知道F为左

    image-20241102181439508

  5. 由中序知道I为左子树

    image-20241102181539924

实例2–中序+后续
  1. 中序序列:BDCEAFHG
  2. 后序序列:DECBHGFA
  3. 由中序后续知道根为A，BDCE为左根 FHG为右根
  4. 后序知道B为根，中序推出没有左根，c为下一个根
  5. 左右根D为左，E为右边
  6. 后序知道F为根
  7. 由中序知道F没有左，那么H为左，G为根

image-20241102183841772

3.遍历的算法实现-先序遍历

image-20241102201045571

代码实现
1
2
3
4
5
6
7
8
9
void  PerOrderTraverse(BiTree T)//指向根节点的指针T
{
    if(T!=NULL){
        printf("%d\t",T->data);
        // visit(T)
        PerOrderTraverse(T->lchild);
        PerOrderTraverse(T->rchile);
    }
}
递归代码解释

  1. 首先进入函数，此时T为传入的根结点

  2. 打印根节点

  3. 第一次调用：根左右函数指向根B

  4. 进入第二层循环 遍历左，左为空此时返回

  5. 回到第二层循环此时 PerOrderTraverse(T->lchild);为空，那么自动执行下一条语句PerOrderTraverse(T->rchile);

  6. 进入循环，执行到D

  7. 再向下执行为空返回到第一次循环

  8. 再执行C

    image-20241103142345827

(●ˇ∀ˇ●)明白了吗！

4.遍历的算法实现-中序遍历
1
2
3
4
5
6
7
8
9
10
void  PerOrderTraverse(BiTree T)//指向根节点的指针T
{
    if(T!=NULL){
       
        PerOrderTraverse(T->lchild);
         printf("%d\t",T->data);//可替换(访问根节点)
        // visit(T)
        PerOrderTraverse(T->rchile);
    }
}
5.历的算法实现-后序遍历
1
2
3
4
5
6
7
8
9
10
11
void  PerOrderTraverse(BiTree T)//指向根节点的指针T
{
    if(T!=NULL){
       
        PerOrderTraverse(T->lchild);
         
        PerOrderTraverse(T->rchile);
        printf("%d\t",T->data);//可替换(访问根节点)
        // visit(T)
    }
}
6.二叉树遍历小总结

image-20241103143731170

时间复杂度O(n)//每个结点只访问一次

空间复杂度O(n)//栈占用的最大辅助空间

7.中序遍历非递归算法-栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void InOrderTraverse(BiTree T){
    BiTree P;
    InitStack(S);//初始化
    P=T;
    while (p||StackEmpty(S))//遇到的是根的时候
    {
        if(P)//不为空
        {
            Push(S,p);//入栈
            p=p->Ichild;//访问左子树
        } else
        {
            Pop(S,q);//出栈
            printf("%d",q->data);//输出根
            p=q->rchild;
        }//while
    }
}
8.二叉树的层次遍历

image-20241103154648957

image-20241103154702890

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//队列定义
typedef struct{
    BTNode data[MAXSIZE];
    int front,rar;
    
}SqQueue;

void LevelOrder(BTNode *b)
{
    BTNode *p;
    SqQueue *qu;
    initQueue(qu);//初始化
    enQuenue(qu,b);//根节点指针进入队列
    while(!QueueEmpty(qu)){//队不为空则循环
        deQueue(qu,p);//出栈结点p
        printf("%c",p->data);访问结点p
        if(p->Ichild!=NULL)enQueue(qu,p->Ichild);//有左孩子时将其进队
        if(p->rchild!=NULL)enqueue(qu,p->rchild);//有右孩子时将其进队
    }
}
9.二叉树遍历算法的应用
1.二叉树的建立
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void CreateBiTree(BiTree &T)
{
    char ch;
scanf(&ch);
if(ch=="#") T=NULL;
else{
    if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
        exit(OVRTFLOW);
    T->data=ch;//生成根节点

CreateBiTree(T->Ichild);//构造左子树

CreateBiTree(T->rchild);//构造右子树
}

}//CreateBiTree

image-20241103164836364

2.复制二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Copy(BiTree T,BiTree &newT)
{
    if(T==NULL)
{
        NewT=NULL;
         return 0;
}else{
        NewT=new BiTNode;
        NewT->data=T->data;

        Copy(T->lchild,NewT->lchild);
        Copy(T->rchild,NewT->rchild);
    }
    return OK;
}
3.计算二叉树的深度

  • 如果是空树，则深度为0

  • 否则，递归计算左子树的深度计为m，递归计算右子树的深度计为n，二叉树的深度则为m与n的较大者

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13

    int Depth(BiTree T)
    {
        int m,n;
        if(T==NULL)
            return 0;
        else{
            m= Depth(T->lchild);
            n= Depth(T->rchile);
            if(m>n)return (m+1);
            else return (n+1);
        }
    }
4.计算二叉树的结点总数
  • 如果为空树则结点为0
  • 否则，结点个数为左子树个数+右子树结点个数再+1
1
2
3
4
5
6
7
int NodeCount(Bitree T)
{
    if(T==NULL)
        return 0;
    else
        return NodeCount(T->lchild)+ NodeCount(T->rchild)+1;
}
5.计算叶子结点的个数
  • 如果是空树返回0
  • 否则，为左子树的叶子结点+右子树的叶子结点
1
2
3
4
5
6
7
8
9
int LeafCount(BiTree T)
{
    if(T==NULL)//空树
        return 0;
    if(T->lchild==NULL&&T->rchile==NULL)//如果是叶子结点返回1
        return 1;
    else
        return LeafCount(T->lchild)+leafCount(T->rchile);
}
10.线索二叉树
  • 如果某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；
  • 如果某孩子的右结点为空，则将空的右孩子的指针域改为指向其后继；

image-20241104153725343

这里是依照遍历来判断前驱后继，而不是图

1.定义
1
2
3
4
5
6
typedef struct BiThNode{
    int data;
    int ltag,rtag;//0表示是左/右孩子，1表示是前/后继
    struct BiThNode *lchild,*rchild;
    
};

image-20241104155234167

image-20241104155240636

image-20241104155253366

2.线索二叉树画法

image-20241104155331910

3.遍历算法

408不要求掌握

6.树和森林

1
2
3
408要求
2森林与二叉树的转换
3树和森林的遍历

1.定义

**森林：**是棵互不相交的树的集合

2.双亲表示法

  • 实现：定义结构数组

    ​ 存放树的结点

    ​ 每个结点含两个域

  • 数据域：存放结点本身信息

  • 双亲域：指示本结点的双亲结点在数组中的位置

image-20241104162141056

**特点：**找双亲容易，找孩子难

1
2
3
4
5
6
7
8
9
10
typedef struct PTNode{//树的结点定义
    TElemType data;//数据元素
    int parent;//双亲位置域
}PTNode;

typedef struct {//树的类型定义
    PTNode nodes[MAXTSIZE];//双亲表示
    int n,r;//节点数,根节点位置
}PTree;

3.孩子链表

把每个结点的孩子结点排列起来，看成是一个线性表， 用单链表存储，则n个结点有n个孩子链表(叶子的孩子链表为空表)。而n个头指针又组成一个线性表，用顺序表(含n个元素的结构数组)存储。

解释：每个结点都有一个单链表，叶子节点的单链表是空表，然后再将这些链表的头指针存放在数组中

image-20241104164756540

孩子结点结构

1
2
3
4
typedef struct CTNode{
    int child;//整数
    struct CTNode *next;//下一个孩子的地址
}* ChildPrt;

双亲结点结构

1
2
3
4
typedef struct {
    TElemType data;//数据元素
    ChildPrt firstchild;//孩子链表头指针
}CTBox;

树结构

1
2
3
4
typedef struct {
    CTBox nodes[MAXTSIZE];//头指针数组
    int n,r;//节点数和根节点位置下标
}CTree;

**特点:**找孩子容易，找双亲难

4.*孩子兄弟表示法（二叉树表示法，二叉链表表示法）

1.定义

实现：用二叉链表作树的存储结构，链表中的美观结点的指针域分别指向其第一个孩子节点和下一个兄弟节点

1
2
3
4
typedef struct CSNode{
    ELemtype data;//元素类型 数据元素
    struct CSNode *firstchild,*nextsibling;//第一个孩子，下一个兄弟
}CSNode,*CSTree;

左孩子 右兄弟，是兄弟的就来砍我

image-20241104171329061

特点：找孩子，找兄弟简单，找双亲难

5.*树与二叉树的转换

1.定义
  • 将树转化为二叉树，利用二叉树的算法实现对树的操作
  • 由于树和二叉树都可以用二叉链表作存储结构，则以二叉树链表作媒介可以导出树与二叉树之间的对应关系

image-20241104173140758

2.操作
1.将树转为二叉树

  1. 加线:在兄弟之间加一连线

  2. 抹线:对每个结点，除了其左孩子外，去除其与其余孩子之间的关系

  3. 旋转:以树的根结点为轴心，将整树顺时针转45°

image-20241104173843558

2.将二叉树转为树
  1. 加线:若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩…沿分支找到的所有右孩子，都与p的双亲用线连起来
  2. 抹线:抹掉原二叉树中双亲与右孩子之间的连线
  3. 调整:将结点按层次排列，形成树结构

image-20241104173926325

6.*森林和二叉树的转换（二叉树与多棵树之间的关系)

1.森林转化为二叉树

  1. 将各棵树分别转换成二叉树

  2. 将每棵树的根结点用线相连

  3. 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

image-20241104180338598

2.二叉树转为森林

  1. 抹线:将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二又树（去掉全部右孩线）

  2. 还原:将孤立的二又树还原成树（孤立二叉再还原)

    image-20241104181000820

7.树与森林的遍历

1.树的遍历的三种方式{先根（次序)，后根，层次遍历}

  • 先根遍历（次序）

    ​ 若树不空，则先访问根结点，然后依次先根遍历各棵子树

  • 后根遍历（次序）

    ​ 若树不空，则先依次后根遍历各棵子树，然后访问根结点

  • 层次遍历

    ​ 若树不空，则至上而下自左至右访问树的每个结点

image-20241104182021725

2.森林的遍历

将森林看作3部分构成

  1. 森林中第一棵树的根结点;
  2. 森林中第一棵树的子树森林，
  3. 森林中其它树构成的森林。
1.先序遍历

若森林不空 则：

  1. 访问森林中第一棵树的根结点;
  2. 先序遍历森林中第一棵树的子树森林;
  3. 先序遍历森林中(除第一棵树之外)其余树构成的森林。

image-20241104182719934

2.中序遍历

若森林不空，则

​ 1.中序遍历森林中第一棵树的子树森林;

​ 2.访问森林中第一棵树的根结点;

​ 3.中序遍历森林中(除第一棵树之外)其余树构成的森林。

对应：213

3.小案例

image-20241104183504031

7.*哈夫曼树及其应用

1
2
3
4
5
6
408要求：
1．哈夫曼（Huffman）树和哈夫曼编码

2．并查集及其应用

3．堆及其应用（25新增）

1.基本概念

**路径：**从树中的一个结点到另一个结点之间的分支构成这两个结点间的路径

**结点路径的长度:**两结点间的路径上的分支数

image-20241107090341596

**树的路径长度：**从树根到每一个结点的路径长度之和，记作TL

image-20241107090440851

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树

权：将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权

结点的带权路径长度：从根节点到该结点之间的路径长度与该结点的权的乘积

树的带权的路径长度：树中的所有叶子结点带权路径长度之和(WPL)

image-20241107091528322

**最优树：**带权路径最短的树（最优树）度要相同

最优二叉树：带权路径长度(WPL)最短的二叉树

满二叉树不一定是哈夫曼树

具有相同带权结点的哈夫曼树不唯一

**贪心算法：**构造哈夫曼树时首先选择权最小的叶子结点

2.哈夫曼算法

1.构造方法

  1. 根据个给定的权值构成的棵二叉树的森林,其中T_i只有一个带权为W_i的根节点

    ​ 构造森林全是根

  2. 在中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且设置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。

    ​ 选用两小造新树

  3. 在F中删除这两棵树，同时将新得到的二叉校加入森林中。·

​ 删除两小添新人

​ 4. 重复2，3剩单根

image-20241107094439746

image-20241107095725435

总结
  1. 哈夫曼树的结点只有度为0或2的没有度为1的结点
  2. 包含n各叶子结点的哈夫曼树共有个结点
  3. 包含n棵树的森林要经过n-1次合并才能形成哈夫曼树，共产生n-1个新结点
  4. 在哈夫曼算法中，初始时有n棵二叉树，要经过n-1次合并最终形成哈夫曼树。
  5. 经过n-1次合并产生n-1个新结点，且这n-1个新结点都是具有两个孩子的分支结点。
  6. 可见:哈夫曼树中共有n+n-1 = 2n-1个结点，且其所有的分支结点的度均不为1。
2.哈夫曼树的算法
顺序结构（一维数组）
1
2
3
4
5
typedef struct
{
    int weight;//权值
    int parent,lch,rch;//双亲，左孩子，右孩子
}HTNode,*HUffmanTree;

image-20241107101801514

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void CreatHuffmanTree (HuffmanTree &HT, int n){//构造哈夫曼树——哈夫曼算法
    int m,i;
    if(n<=1)return;
    m=2*n-1;//数组共2n-1个元素
    HT=new HTNode[m+1];//0号单元未用，HT[m]表示根结点
     for(i=1;i<=m;++i){//将2n-1个元素的Ich、rch、parent置为O
    HT[i].lch=0; HT[i].rch=0; HT[i].parent=0;
}
for(i=1;i<=n;++i) cin>>HT[i].weight;//输入前n个元素的weight值
// 初始化结束，下面开始建立哈夫曼树

for( i=n+1;i<=m; i++){//合并产生n-1个结点——构造Huffman树
     Select(HT, i-1,s1,s2);//在HT[k](1≤ksi-1)中选择两个其双亲域为0，
                           //且权值最小的结点,并返回它们在HT中的序号s1和s2
HT[s1].parent=i; HT[s2] .parent=i;//表示从F中删除s1,s2
HT[i].llch=s1;HT[i].rch=s2;//s1,s2分别作为i的左右孩子
HT[i].weight=HT[s1].weight + HT[s2].weight;//i的权值为左右孩子权值之和
}
}
  1. 初始化HT[1…….2n-1]: lch=rch=parent=0
  2. 输入初始n个叶子结点:置HT[1…n]的weight值;
  3. 进行以下n-1次合并，依次产生n-1个结点HT[i], i=n+1…2n-1:
  • a)在HT[1…i-1]中选两个未被选过(从parent ==0的结点中选)的weight最小的两个结点HT[s1]和HT[s2], s1、s2为两个最小结点下标;
  • b)修改HT[s1]和HT[s2]的parent的值：HT[s1].parent=i;HT[s2].parent=i;
  • c)修改新产生的HT[i]:
    .HT[i].weight=HT[s1].weight + HT[s2].weight;. HT[i]. Ich=s1; HT[i]. rch=s2;

3.哈夫曼编码

前缀编码：任意一字符不是另一个字符的前缀

1.方法

1、统计字符集中每个字符在电文中出现的平均概率 (概率越大，
要求编码越短)。
2、利用哈夫曼树的特点:权越大的叶子离根越近;将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的结点，路径越短。
3、在哈夫曼树的每个分支上标上O或1:
结点的左分支标0，右分支标1
把从根到每个吐子的路径上的标号连接起来，作为该叶子代表的字符的编码。

image-20241107110159328

image-20241107112200535

左分支标记0，右分支标记1

问题

1.为什么哈夫曼编码能够保证是前缀编码?

因为没有一片树叶是另一片树叶的祖先，所以每个叶结点的编码就不可能是其它叶结点编码的前缀

2.为什么哈夫曼编码能够保证字符编码总长最短?
因为哈夫曼树的带权路径长度最短，故字符编码的总长最短。

性质1：哈夫曼编码是前缀编码

性质2：哈夫曼编码是最优前缀码

2.实现
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
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode & HC, int n){
    //从叶子到根逆向求每个字符的哈夫曼编码，存储在编码表HC中
    int i,cd,start;
    HC=new char *[n+1];//分配n个字符编码的头指针矢量

    cd=new char [n];//分配临时存放编码的动态数组空间

    cd[n-1]='\0’;//编码结束符

    for(i=1; i<=n; ++i){//逐个字符求哈夫曼编码

    start=n-1; c=i; f=HT[i].parent;
    while(f!=O){//从叶子结点开始向上回溯，直到根结点
    --start;//回溯一次start向前指一个位置

    if (HT[f].Ichild= =c) cd[start]= 'O' ;//结点c是f的左孩子，则生成代码O
    else cd[start]= '1' ;//结点c是f的右孩子，则生成代码1
    c=f; f=HT[f].parent;//继续向上回溯

}
//求出第i个字符的编码
HC[i]= new char [n-start];//为第i个字符串编码分配空间

strcpy(HC[i],&cd[start]);//将求得的编码从临时空间cd复制到HC的当前行中

}
delete cd;//释放临时空间

}// CreatHuffanCode

image-20241107135013070

4.编码的实现

image-20241107140225327

image-20241107140705475

八、图

1.图的定义和基本术语

1.图的定义

图：

​ V:顶点（数据元素）的有穷非空集合

​ E:边的有穷集合

**无向图：**每条边都没有方向

**有向图：**每条边都有方向

image-20241107141712274

**完全图：**任意两个点都有一条边相连

image-20241107141847834

**稀疏图：**有很少边或弧的图（e<nlogn)

**稠密图：**有较多边或弧的图

**网：**边/弧带权的图

邻接:有边/弧相连的两个顶点之间的关系。

​ 存在，则称和;互为邻接点;(无向图)

​ 存在，则称v邻接到,邻接于(有向图)

**关联：**边/弧与顶点的关系

​ 存在称为该边/弧关联于和

**顶点的度:**与该顶点相关联的边的数目，记为TD(v)

在有向图中，顶点的度等于该顶点的入度与出度之和。

顶点v的入度是以v为终点的有向边的条数,记作ID(v)

顶点v的出度是以v为始点的有向边的条数,记作OD(v)

image-20241107142753964

路径：接续的边构成的顶点序列

路径长度:路径上边或弧的数目/权值之和。
**回路(环):**第一个顶点和最后一个顶点相同的路径。
**简单路径:**除路径起点和终点可以相同外，其余顶点均不相同的路径。

**简单回路(简单环):**除路径起点和终点相同外，其余顶点均不相同的路径。

image-20241107144251328

连通图(强连通图)
在无(有)向图中，若对任何两个顶点v、u都右在从v至到u的路径称G是连通图(裾连通图)

image-20241107144721137

权与网
图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。
带权的图称为网。

子图
设有两个图G= (V，{E})、G1= (V1，{E1})，若V1⊆V,E1⊆E,则称G1是G的子图

image-20241107145900753

连通分量（强连通分量)
无向图G的极大连通子图称为G的连通分量。
极大连通子图意思是:该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。

image-20241107150554317

有向图G的极大强连通子图称为G的强连通分量

极大强连通子图意思是:该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。

image-20241107150813934

**极小连通子图:**该子图是G的连通子图，在该子图中删除任何一天边子图不再连通。
**生成树:**包含无向图G所有顶点的极小连通子图。
**生成森林:**对非连通图，由各个连通分量的生成树的集合。

image-20241107151129261

2.图的类型定义

1.图的抽象数据类型定义如下:

ADT Graph{
数据对象V:具有相同特性的数据元素的集合，称为顶点集。
数据关系R: R={VR}
VR={<v,w>|<v,w> | v,w⊆V ^ p(v,w),
<v,w>表示从v到w的弧，P(v,w)定义了弧<v,w>的信息

}

2. 图的操作

image-20241107152052212

3.图的存储结构

image-20241107152459776

1.数组（邻接矩阵）表示法

image-20241107152717210

无向图邻接矩阵

image-20241107153625208

分析1：无向图的邻接矩阵是对称的

分析2：顶点i的度=第i行（列）中的1的个数

特别：完全的邻接矩阵中，对角元素为0，其余为1

有向图的邻接矩阵

image-20241107155521228

分析1：有向图的邻接矩阵可能不是对称的

分析2：顶点的出度=第i行元素之和（ 指向&V_2& 和）

​ 顶点的出度=第i列元素之和

​ 顶点的度=第i行元素之和+第i列元素之和

有向网的邻接矩阵

网（即有权图)的邻接矩阵表示法

定义为

V_iV_j或V_i,V_j∊

​ 无边弧

如果两个顶点之间存在弧或边，那么我就记录两个顶点为权，如果不存在则记录无穷大

image-20241109095058803

2.邻接矩阵的存储形式

1.用两个数组分别存储顶点表和邻接矩阵
1
2
3
4
5
6
7
8
9
#define MVNum 100 //最大顶点数
typedef char VerTexType;//设顶点的娄文据类型为字符型
typedef int ArcType;//假设边的权值类型为整型

typedef struct{
VerTexType vexs[MVNum]; //顶点表
ArcType arcs[MVNum][MVNum]; //邻接矩阵
int vexnum, arcnum;//图的当前点数和边数
}AMGraph; // Adjacency Matrix Graph
2.采用邻接矩阵表示法创建无向网
算法思想

​ (1)输入总顶点数和总边数。

(2)依次输点的信息存人顶点表中。

（3）初始化邻接矩阵，使每个权值初始化为极大值。

（4）构造邻接矩阵

代码先欠着

3.邻接矩阵的好处和坏处
好处
  • 直观、简单、好理解
  • 方便检查任意一对顶点间是否存在边
  • 方便找任一顶点的所有“邻接点”(有边直接相连的顶点)
  • 方便计算任一顶点的“度”(从该点发出的边数为“出度”，指向该点的边数为“入度”)·无向图:对应行（或列)非O元素的个数·有向图:对应行非0元素的个数是“出度”;对应列非0元素的个数是“入度”
坏处

  • 不便于增加和删除顶点

  • 浪费空间——传稀疏图人点很多而边很少）有大量无效元素

  • ​ 对稠密图（特别是完全图)还是很合算的

  • 浪费时间——统计稀疏图中一共有多少条边

3.邻接表表示法（链式）

1.无向图的邻接表
  • ·顶点:

​ ·按编号顺序将顶点数据存储在一维数组中;·

  • 关联同一顶点的边(以顶点为尾的弧)︰

    ​ ·用线性链表存储

image-20241109105841878

data表示顶点本身，firstarc表示第一条边的指针（以v1为例子，下标为3或为1的元素的指针）adjvex表示邻接的顶点，nextarc表示下一元素的指针

特点:
  • ·邻接表不唯一
  • ·若无向图中有个顶点、条边，则其邻接表需个头结点和 个表结点。适宜存储稀疏图。
  • 无向图中顶点v的度为第i个单链表中的结点数。
2.有向图

image-20241109111503505

特点:

顶点的出度为第i个单链表中的结点个数。
顶点的入度为整个单链表中邻接点域值是的结点个数。

image-20241109112935783

3.链式代码
1.定义代码

顶点

1
2
3
4
5
6
typedef struct VNode{
    
    VerTexType data;//顶点信息--类型自义定
    ArcNode * firstarc;//指向第一条依附该顶点的边的指针
    
}VNode,AdjList[MVNum]; //AdjList表示邻接表类型,MVNUM为最大数组数

边结点

1
2
3
4
5
6
#define MVNum 100//最大顶点数
typedef struct ArcNode{//边结点
int adjvex;//该边所指向的顶点的位置
struct ArcNode * nextarc;//指向下一条边的指针
OtherInfo info;//和边相关的信息
}ArcNode;

image-20241109122123413

图结点

1
2
3
4
5
typedef struct {
     AdjList vertices;//vertices--vertex的复数顶点数组
    int vexnum, arcnum;//图的当前顶点数和弧数
} ALGraph;

image-20241109123727673

2.采用邻接表表示法创建无向网的算法思想

【算法思想】

  1. 输入总顶点数和总边数。
  2. 建立顶点表
    依次输入点的信息存入顶点表中
    使每个表头结点的指针域初始化为NULL
  3. 创建邻接表
    依次输入每条边依附的两个顶点确定两个顶点的序号i和j，建立边结点
    将此边结点分别插入到和对应的两个边链表的头部

5.邻接表的特点

1.特点

  • ·方便找任一顶点的所有“邻接点”

  • ·节约稀疏图的空间

    ​ 需要N个头指针＋2E个结点(每个结点至少2个域)·

  • 方便计算任一顶点的“度”?
    对无向图:是的

    对有向图:只能计算“出度”;需要构造“逆邻接表”(存指向自己的边)来方便计算入度”

  • ·不方便检查任意、对顶点间是否存在边

4.邻接矩阵与邻接表表示方法的关系

image-20241109131228879

2.联系:

邻接表中每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。

2.区别:

对于任一确定的无向图，邻接矩阵是唯一的(行列号与顶点编号一致)，但邻接表不唯一（链接次序与顶点编号无关）。

邻接矩阵的空间复杂度为,而邻接表的空间复杂度为

3.用途:

邻接矩阵多用于榈密图;而邻接表多用于稀疏图

5.十字链表

image-20241109132236978

1.简介

十字链表(Orthogonal List)是有向图的另一种链式存储结构。我们也可以把它看成是将有向图的邻接表和逆邻接表结合起来形成的一种链表。
有向图中的每一条弧对应十字链表中的一个弧结点，同时有向图中的每个顶点在十字链表中对应有一个结点，叫做顶点结点。

2.具体

data:数据

firstin:第一个入度边

firstout:第一个出度边

tailvex:弧尾位置

headvex:弧头位置

hlink:弧头相同的下一条弧

tlink:弧尾相同的下一条弧

image-20241109134222311

6.邻接多重表

image-20241109144018754

image-20241109144858776

4.图的遍历

1.定义

遍历定义:

从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算

**遍历实质:**找每个顶点的邻接点的过程。

图的特点:
图中可能存在回路，且图的任一顶点都可能与其它顶点相通在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

如何避免回路:

解决思路:设置辅助数组，用来标记每个被访问过的顶点。

  • 初始状态为0
  • ·顶点i被访问，改为1，防止被多次访问

2.深度优先(DFS)

1.连通图的遍历
方法:
  • 在访问图中某一起始顶点v后，由v出发，访问它的任一邻接顶点w1
  • 再从w出发，访问与w邻接但还未被访问过的顶点W2;
  • 然后再从w出发，进行类似的访问，…
  • 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。
  • 如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问;
  • 如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

image-20241109151227573

实现

image-20241109154118743

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
//王道代码

bool visited[MAX_VERTEX_NUM];//访问标记数组

void DFSTraverse(Graph G)//对图G进行深度优先遍历
{
   int v;
   for(v=0;v<G;v++)
   {
       visited[v]=false;//初始化已访问数组
       for ( v = 0; v < G; ++v) {//从v0开始遍历
           if(!visited[v])
           {
               DFS(G,v);
           }
       }
        
    }
}

void DFS(Grap G,int V)//从顶点v出发，深度遍历图G
{
    int w;
    visit(v);//访问顶点v
    visited[v]=true;//设已访问标记
    for (w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))//依次检查邻接矩阵v所在的行 
    {
        if(!visited[w])//w为v还没访问的邻接顶点
        {
            DFS(G,w);
        }
    }
}

效率分析

用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在的行，时间复杂度为。

用邻接表来表示图，虽然有个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为.

结论:
  • 稠密图适于在邻接矩阵上进行深度遍历;
  • 稀疏图通于在邻接表上进行深度遍历。

2.广度优先遍历

1.方法

方法:从图的某一结点出发，首先依次访问该结点的所有邻接点,再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点
重复此过程，直至所有顶点均被访问为止。

image-20241110090045314

2.实现
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
//王道代码
bool visited [Max_VERTEX_NUM];//访问标记数组

void BFSTraverse(Grap G){//对图G进行广度优先遍历
    for (int i = 0; i < G.vexnum; ++i) {
        visited[i]=false;//访问标记数组初始化
    }
    InitQueue(Q);//初始化辅助队列Q
    for ( i = 0; i <G.vexnum ; ++i) {//从0号顶点开始遍历
        if(!visited[i]){//对每个连通分量调用一次BFS
            BFS(G,i);//vi未访问过，从vi开始BFS
        }
    }
}

void BFS(Graph G,int v){//从顶点v出发，广度优先遍历图G
    visit(v);//访问初始顶点v
    visited[v]=true;//对v做以访问标志
    Enqueue(Q,v);//顶点v入队列Q
    while (!isEmpty(Q)){
        DeQueue(Q,v);//顶点v出队列
        for (int w = FirstNeighbor(G,v); w>0 ; w=NextNeighbor(G,v,w)) {
                                           //检测到v的所有邻接点
            if(!visited[w]){//w为v未访问的邻接顶点
                visit(w);//访问顶点w
                visited[w]=true;//对w做以访问标记
                Enqueue(Q,w);//顶点w入队列
            }
        }
    }
}

3.效率分析
  • 如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要
    循环检测矩阵中的整整一行（ n个元素)，总的时间代价为O()。
  • 用邻接表来表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为。
4.效率比较
  • ·空间复杂度相同，都是O(n)(借用了堆栈或队列) ;
  • ·时间复杂度只与存储结构,(邻接矩阵或邻接表)有关，而与搜索路径无关。

5.图的应用

1.最小生成树

1.生成树的简介

生成树：所有顶点均由边连接在一起，但不存在回路

image-20241110095716787

一个图可以有许多棵不同的生成树

所有生成树具有以下共同特点

  • 生成树的顶点个数与图的顶点个数相同;
  • 生成树是图的极小连通子图，去掉一条边则非连通;·
  • 一个有n个顶点的连通图的生成树有条边;
  • ·在生成树中再加一条边必然形成回路。
  • 生成树中任意两个顶点间的路径是唯一的;

含有个顶点 条边的图不一定是最小生成树

image-20241110095828535

2.无向图的生成树

image-20241110100335510

3.最小生成树

最小生成树:给定一个无向网络在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。

image-20241110100803730

构造最小生成树

构造最小生成树的算法很多，其中多数算法都利用了MST的性质。

**MST性质:**设N =(V, E)是一个连通网,U是顶点集V的一个非空子集。若边(u, v)是一条具有最小权值的边，其中u∈u,v∈V-U,则必存
在一棵包含边(u, v)的最小生成树。

Prim-普里姆算法

算法思想

设是连通网，是N上最小生成树中边的集合。

初 始 令,∊TE={ }$。

在所有∊,∊的边∊中，找一条代价最小的边。

将并入集合，同时并入U

重复上述操作直至，则为的最小生成树。

从顶点往下找最小的权

Kruskal-克鲁斯卡尔算法

所有边按权值排序,然后选择最小的

当有循环时舍弃这条边

当所有边连通时结束

与prim算法不同的是他是按排序来找最小,prim是依次选最小

设连通网，令最小生D树初始状态为只有n个顶点而无边的非连通图,每个顶点自成一个连通分量。

在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上(即:不能形成环)，则将此边加入到T中;否则，舍去此边，选取下一条代价最小的边。

依此类推，直至T中所有顶点都在同一连通分量上为止。

最小生成树可能不唯一

两种比较

image-20241110111651349

2.最短路径

1.定义

最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。

单源最短路径-Dijkstra迪杰斯特拉算法

image-20241110112448263

所有顶点间的最短路径–Floyd弗洛伊德算法

image-20241110112715538

2.Dijkstra算法
概述

1.初始化:先找出从源点到各终点v的直达路径, 即通过一条弧到达的路径。

2选择:从这些路径中找出一条长度最短的路径。

3.更新:然后对其余各条路径进行适当调整:

​ 若在图中存在弧 ，且则以路径(V_o,u,V_k)代替(vo_,Vi)。

在调整后的各条路径中，再找长度最短的路径)依此类推。

(先找出直达的,然后与不直达的比较,有小的就更新被比较的)

具体-按路径长度递增次序产生最短路径

1、把V分成两组:辅助数组D存放。
(1) S:已求出最短路径的顶点的集合。
(2)T=V -s∶尚未确定最短路径的顶点集合。

2、将T中顶点按最短路径递增的次序加入到S中，

保证:(1）从源点到S中各顶点的最短路径长度都不大于从到T中任何顶点的最短路径长度。

(2)每个顶点对应一个距离值:
S中顶点:从到此顶点的最短路径长度。

​ T中顶点:从到此顶点的只包括S中顶点作中间顶点的最短路径长度。

image-20241110143716951

3.Floyd 弗洛伊德算法
算法思想
  • ·逐个顶点试探
  • ·从到v,的所有可能存在的路径中·
  • 选出一条长度最短的路径

image-20241110151313801

3.拓扑排序

有向无环图：无环的有向图，简称DAG

image-20241110151722949

一个结点可能有多个前驱，但是没有回路

1.AOV网
定义

用一个有向图表示一个工程的各子工程及其相冥制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网(Activity On Vertex network)

特点
  • 若从i到j有一条有向路径，则i是j的前驱;j是i的后继。
  • 若<i,j >是网中有向边，则i是j的直接前驱;j是i的直接后继
  • AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。
检测AOV 网中是否存在环方法:

对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV 网必定不存在环。

2.AOE网

用一个有向图表承一个工程的各子工程及其相互制约的关系,以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网(Activity On Edge)。

3.拓扑排序

在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧<i,j>存在，则在这个序列甲，I一疋排仕J的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。

image-20241110160144846

4.关键路径

image-20241110165246291

对于AOE网，我们关心两个问题:

(1)完成整项工程至少需要多少时间?

(2)哪些活动是影响工程进度的关键?

关键路径 ：路径长度最长的路径。
路径长度：路径上各活动持续时间之和。

------>求解关键路径问题

image-20241110171020097

由若干个关键活动组成的就是关键路径

image-20241110171553903

ve(j)最早开始时间：从原点开始找到权的最大值

vl(n)最迟发生时间：从汇点向前，找到最小值

image-20241110172431466

具体计算

image-20241110173552506

e(i)就是弧尾的长度

​ eg: v5就是6（v5连接的是v2，只用算v2），

l(i)就是vl-路径上的权值

​ eg: v5就是7-a4的权=7-1=6

image-20241110174727136

讨论

1、若网中有几条关键路径,则需加快同时在几条关键路径上的关键活动。
如: a11、a10、a8、a7。

2、如果一个活动处于所有的关键路径上，那么提高这个活动的速度，就能缩短整个工程的完成时间。如: a1、a4。

3、处于所有的关键路径上的活动完成时间不能缩短太多)，否则会使原来的关键路径变成不是关键路径。这时，必须重新寻找关键路径。

​ 如:a1由6天变成3天，就会改变关键路径。