数据结构与算法（C语言）学习笔记
一、数据结构的基本概念
用计算机去解决实际问题，需要经过哪些步骤流程：
（1）分析问题，将实际问题抽象成一个具体的数学模型
（2）设计一个解决该数学模型的算法
（3）经过不断的调试，得出结果
问题：
如何的得出一个数学模型出来？
步骤：
分析问题-------找出操作的对象------找出对象之间的关系-----得出数学模型
例如：
（1）计算：1+2+3+4+......+100的和
操作的对象：1、2、3、......100
对象之间的关系：后面一个数字是前一个数字的基础之上加1
数学模型：等差数列
sn=n*a1+n（n-1）*d /2
编写代码实现数学模型即可
（2）随着开发经验年限的不断增长与收入之间的关系问题
操作的对象：经验年限、收入
对象之间的关系：经验年限与收入是呈现线性关系
数学模型：
f（x）= a*x+b
编写代码实现数学模型即可
数据对象：
例子中的数据对象是数值类型的数据
实际问题中数据对象不一定是数值类型的数据（即非数值类型的数据）
例如：
（1）图书馆书目检索自动化问题
1）编号
2）书名
3）出版社名称
4）作者名称
......
每个对象之间呈现出一种一对一的关系-----数学模型：线性结构
（2）计算机和人对弈下棋问题
对象之间呈现一对多的关系------数学模型：树形结构
（3）多叉路口交通灯问题
对象之间呈现多对多的关系-----数学模型：图形结构
总结：
面试题：
数据结构主要研究的是什么内容？
答题：
数据结构实质上研究的是非数值类型问题中数据与数据之间的关系以及在关系上的操作
1、什么是数据结构？
（1）数据
数据分为：数值类型和非数值类型
是指客观事物的符号表示，所有能输入到计算机并被计算机处理的符号的总称
（2）结构
数据与数据之间隐含的关系，称之为“结构”
（3）数据结构
是指计算机处理和存储数据的一种方式，是数据之间具有某种特定关系的集合
数据结构又分为：
存储结构和逻辑结构
存储结构：是指数据在计算机中存储方式
1）顺序存储
是指数据与数据之间的存储位置相邻
2）链式存储
是指数据与数据之间的存储位置不一定相邻
逻辑结构：是指数据与数据之间的逻辑位置
1）集合结构：数据与数据之间除了属于同一个集合，再无其他关系
2）线性结构：数据与数据之间呈现一对一的关系
3）树形结构：数据与数据之间呈现一对多的关系
4）图形结构：数据与数据之间呈现多对多的关系
2、为什么要学习数据结构？
C语言：
C语言可以去解决实际的一些问题，解决问题的时候，一般没有考虑解决问题的效率
数据结构：
使用数据结构高效的处理问题
高效体现的方面：
（1）代码的执行时间上
代码执行的时间越少，效率越高
（2）代码所用的空间内存上
代码在执行过程中，所用的内存越少，效率也越高
3、为什么学习算法？
算法：
官方：
对实际问题求解的步骤描述，称为“算法”
个人：
高效的实现特定的功能
高效：
时间上
内存上
例如：
（1）计算：1+2+3+4+...............+100的和
1）高斯公式：等差数列求和
sn=n*a1+n(n-1)*d/2
2）利用for循环
sum=0;
for（int i=1;i<=100 ; i++）
{
sum+=i;
}
3）(1+99)+(2+98)+......+(49+51)+50+100
..................
解决一个实际问题，可能有多种方法（算法），如何去选择最优的算法？
（1）时间上
面试题：
可不可以通过绝对的时间度量去衡量算法的执行时间？为什么不可以？采用什么方式去衡量？
绝对的时间度量：1s、1us、1h等等
不可以
原因：同一段代码，放在不同的平台上，耗费的时间是不一样
例如：
两个人去将水槽里的水挑干净
两个人：
一个是体弱多病
一个是身体强壮
两个人去将海洋里的水挑干净
两个人：
一个是体弱多病
一个是身体强壮
抛开硬件、软件相关的因素，可以理解为一个算法的执行时间只与问题规模的大小有关，问题规模一般使用整数n来表示
时间复杂度：
是指基本操作重复执行的次数（频度&时间）是问题规模n的某个函数f（n），记作：
T（n）=O（f（n）） //大O表示法
随着问题规模n的增大，f（n）的增长率是与问题规模n增长率相同，称为渐进时间复杂度，简称“时间复杂度”
算法的构成：
顺序|分支|循环+基本（原）操作构成
例如：
常量阶：O（1）
{
sum+=2； //时间复杂度：O（1）
}
线性介：O（n）
sum=0；
for（int i=1; i<=n; i++）
{
sum+=i；//时间复杂度：O（n）
}
平方介：O（n^2）
for（int i=1; i<=n ; i++）
for（int j=1; j<=n ; j++）
{
printf（“hello world”）； //时间复杂度：O（n^2）
}
对数阶：O（logn）
sum=1;
for（int i=1; i<=n ; i*=2）
{
sum*=2; //时间复杂度：O（logn）
}
总结：
1）如果基本操作有多处地方使用，算出来的时间复杂度只是取增长率最快的那一个
2）如果没有特别说明的情况（例如：最坏和最好情况）下，一般时间复杂度是按照最坏的情况进行计算
（2）内存上
空间复杂度：
是指基本操作申请的空间大小是问题规模n的某个函数f（n），记作：
S（n）=O（f（n）） //大O表示法
随着问题规模n的增大，空间大小的增长率是与问题规模n增长率相同，简称“空间复杂度”
常见的：
常量阶
int a=10; //从内存中申请了一个内存空间，O（1）
线性阶
int *p=(int *)malloc（siezof（int）*n）;//从内存中申请n个内存空间，O（n）
....
二、线性结构
是指数据与数据之间呈现一对一的关系，即线性关系
1、线性表
是指由零个或多个数据组成的有限序列，称为“线性表”，数据是线性关系
例如：
（a1，a2，a3，a4，a5，.............，an）
直接前驱：除了线性表中的第一个数据之外，其它的数据都有一个直接前驱，例如，a2的直接前驱是a1，a3的直接前驱是a2，....
直接后继：除了线性表中的最后一个数据之外，其它的数据都有一个直接后继，例如，a1的直接后继a2，a2的直接后继是a3，.....
线性表的存储：
（1）顺序存储___数组为例
对于线性表来讲，数据元素不仅是逻辑位置相邻，并且物理存储位置也相邻
数组：
静态数组和动态数组
静态数组：
是指数组的大小在编译时的就已经确定了，在后期不允许更改数组的大小，称为“静态数组”
例如：
int arr[5];
动态数组：
是指数组的大小在运行时才确定，并且后期可以更改数组的大小，称为“动态数组”
例如：
使用malloc、realloc等等来申请空间
#define n 10
int * p = （int *）malloc（4*n）；
线性表的顺序存储，称之为“顺序表”
顺序表的常见的操作：
创建
判满
判空
插入
在空位插入，直接插入
在指定位置插入，要判断位置关系
删除
....
1）在顺序表中指定位置插入数据指定的数据
2）删除顺序表中指定位置的数据
（2）链式存储
对于线性表来讲，数据元素逻辑位置是相邻，但是物理存储位置不一定相邻
线性表的链式存储，称之为“线性链表”，简称“单链表”
链式存储的结点：
1）数据域：数据域中存放的是本身的数据
2）指针域：指针域中存放的是下一个结点的地址
为什么要存储下一个结点的位置？解释了的
头指针：
头指针是链表中一定存在的指针，它是指向整个链表，头指针存放的是链表中的第一个结点的地址
头节点：
头节点是链表中的第一个结点，可有可无，如果有的话，方便后续对链表进行相关的操作，头节点中数据域一般不存放任何的具体数据（可以存链表的长度等等），指针域是存放下一个结点的地址
面试题：
头指针与头节点的区别？
首元结点：是指链表中第一个存放数据的结点
框架：
利用C语言的结构体
struct Node
{
(1)数据域；
(2)指针域
}
（1）不带头节点的链表
略
（2）带头节点的链表
创建单链表：
关键代码：
struct Node *p=(struct Node *)malloc(sizeof(struct Node));
if(p==NULL)
{
printf("单链表创建失败！n");
return NULL;
}
memset(p->name,0,sizeof(p->name));
p->age=0;
p->next=NULL;
遍历单链表：
关键代码：
struct Node *tra=p->next;
while(tra)
{
tra=tra->next;
}
头插法插入结点：
关键代码：
//将头节点之后的节点地址保存起来
struct Node *m=p->next;
p->next=new_Node;
new_Node->next=m;
尾插法插入结点：
关键代码：
struct Node *tra=p;
while(tra->next)
{
tra=tra->next;
}
tra->next=new_Node;
指定位置插入结点：
关键代码：
int i=0;//遍历链表，找到插入位置的前一个结点的地址
struct Node *tra=p;
struct Node *temp;//存放tra后面结点的地址
while(i<list_Len)
{
i++;
if(i==pos)
{
temp=tra->next;
struct Node *new_Node=(struct Node *)malloc(sizeof(struct Node));
if(new_Node==NULL)
{
return false;
}
strcpy(new_Node->name,name1);
new_Node->age=age1;
tra->next=new_Node;
new_Node->next=temp;
return true;
}
tra=tra->next;
}
单链表的反转：
关键代码：
struct Node *p1=p->next;
struct Node *q1=p->next->next;
while(q1)
{
p1->next=q1->next;
q1->next=p->next;
p->next=q1;
q1=p1->next;
}
############笔试题#####################
（1）删除创建的单链表
（2）如何判断一个单链表中是否有环？
设置一个快慢指针
快指针走两步
慢指针走一步
只要快指针和慢指针相遇，说明链表中有环
单链表的优缺点：
优点：
（1）从链表的某一个结点出发，都能找到后续的结点
（2）插入、删除方便
缺点：
（1）如果从链表的某一个结点出发，不能找到该结点的前驱结点
（2）访问链表中的数据麻烦（遍历链表）
//查找单片表的第k个结点
文件：
Linear_List_Fined_Back_K_Node.c
思路：
设置两个指针，一个指针先走k步
之后，两个指针一起走
当先走的指针指向空时，后走的指针就指向倒数第k个结点
循环单链表：
单链表有：
如果从链表的某一个结点出发，不能找到该结点的前驱结点的问题
循环单链表：
单链表的首、尾相连构成“循环单链表”
框架：
struct Node
{
数据域
指针域
}；
循环单链表的创建：
struct Node *p=(struct Node *)malloc(sizeof(struct Node));
if(p==NULL)
{
return NULL;
}
p->age=0;
p->next=p;
循环单链表的头插法：
if(p->next==p)
{
struct Node *new_Node=(struct Node *)malloc(sizeof(struct Node));
if(new_Node==NULL)
{
return false;
}
new_Node->age=data;
p->next=new_Node;
new_Node->next=p;
return true;
}
struct Node *new_Node=(struct Node *)malloc(sizeof(struct Node));
if(new_Node==NULL)
{
return false;
}
new_Node->age=data;
struct Node *temp=p->next;
p->next=new_Node;
new_Node->next=temp;
//参考单片表的操作，需要把条件换一下，判断尾结点是否是指向头结点
循环单链表实现约瑟夫环：
//思路：
创建链表的时候，会创建一个结点，用头指针指向该结点，将该结点作为首元结点
new_Node->data=data;
new_Node->next=NULL;
struct Node *L=new_Node;
创建其他结点
struct Node *node=NULL;
struct Node *p=L->next;
for（int i=2;i<=num;i++）//num代表创建多少个结点
{
node=(struct Node *)malloc(sizeof（struct Node）);
//将结点插入到链表中
node->data=i; //向节点插入数据
p->next=node;
p=p->next;
node->next=NULL;
}
node->next=new_Node;
//实现约瑟环，数到3（用变量n来代替），杀掉一个结点
struct Node *temp=NULL;
struct Node *move=L; //指向的首元结点
//遍历循环单链表，找到数到几的结点，删除该结点
while（move->next!=move）
{
for（int i=2;i<=n;i++）
{
temp=move;
move=move->next;
}
temp->next=m->next;
move->next=NULL;
//释放m指向的结点
free（m）;
//m要指向下一个结点
m=temp->next;
}
//输出move指向的结点
双向链表：
链表中不仅存放了指向下一个结点的地址，还存存放了指向上一个结点的地址
优点：
从某一个结点出发，我都能找到链表中的任意一个结点
既可以前向遍历，也可以后向遍历
双向链表的结点的构成：
数据域：存放的是当前的结点的数据
指针域：
一个指针域存放的是下一个结点的地址
另一个指针域存放的是上一个节点的地址
例如：
struct Node
{
int data；
struct Node *next; //存放下一个结点的地址
struct Node *pre; //存放上一个节点的地址
}
基本操作：
创建链表：
struct Node *p=(struct Node *)malloc(sizeof(struct Node));
if(p==NULL)
{
return NULL;
}
p->data=0;
p->pre=NULL;
p->next=NULL;
遍历链表：
struct Node *tra=p;
while(tra->next)
{
tra=tra->next;
}
插入结点：
new_Node->data=data;
struct Node *temp=p->next;
p->next=new_Node;
new_Node->pre=p;
new_Node->next=temp;
temp->pre=new_Node;
循环双向链表：
将双向链表的首尾进行相连，即可构成循环双向链表
双向链表的头节点的pre域存放尾结点的地址
双向链表的尾结点的next域存放头结点的地址
#################栈####################
栈：
栈是属于线性表中的一种基本数据结构
栈的特点：
只允许在栈的一端进行相关的操作（插入、删除等等），它是一种先进后出（FILO）或后进先出（LIFO）的结构
栈顶：
在栈的一端能进行出栈或入栈的操作，称之为“栈顶”
栈底：
不能在栈的一段进行入栈或出栈的操作，称之为“栈底”
栈的存储分为：顺序存储和链式存储
栈的顺序存储，称之为“顺序栈”
栈的链式存储，称之为“链式栈”简称“链栈”
需要在栈中设置一个栈顶指针，该指针指向的是栈顶元素，方便用户对栈进行入栈或出栈操作
顺序栈：
栈顶指针非彼指针
顺序栈的操作：
创建顺序栈：
栈顶指针默认是赋值为-1
top=-1; //栈顶指针为-1表示空栈
入栈：
判断栈是否已满
if（p->top==MAXSZIE-1）
{
return false;
}
p->top+=1;//栈顶指针加1
p->stack[p->top]=data;
出栈：
判断栈是否为空
if（p->top==-1）
{
return false;
}
*data=p->stack[p->top];
printf("取出的数据：%dn",p->stack[p->top]);
p->stack[p->top]=0;//清空
p->top--;
链式栈：
参考前面
队列：
队列是一种限制在一端进行插入另外一端进行删除的一种数据结构，队列类似于一根水管，是一种先进先出（FIFO）的数据结构
面试题：
队列和栈的区别是什么？
如何用栈来实现队列的操作？
队头：是指向队列的头部数据
队尾：是指向队列的尾部数据
队列的存储：
顺序存储：
基本的操作：
入队：
//可以操作头指针，让头指针加1，需要移动数据
//可以操作尾指针，尾指针-1 （课上讲的），不需要移动数据
出队：
//如果入队时操作的头指针，出队时只需要修改头指针的指向，不需要移动数据
//如果入队时操作的尾指针，出队时需要移动数据
判空：
//尾指针和头指针是否指向同一个位置，如果是空，否则不空
判满：
//如果操作的头指针，只需要判断头指针是否等于MAXSIZE-1
//如果操作的尾指针，只需要判断尾指针是否等于-1
链式存储：
需要定义头指针和尾指针
struct Que
{
int data ;
struct Que *next; //存储下一个结点的地址
//头指针和尾指针需要单独存起来
//struct Que *front;//头指针
//struct Que *rear; //尾指针
}；
struct Que_Point
{
struct Que *front;
struct Que *rear ;
}
判断是否为空：
if(q->front==q->rear)
{
}
入队：
struct Que *new_Node=(struct Que *)malloc(sizeof(struct Que));
if(new_Node==NULL)
{
return false;
}
new_Node->data=data;
q->rear->next=new_Node;
new_Node->next=NULL;
q->rear=new_Node;
出队：
struct Que *temp=q->front->next;
q->front->next=temp->next;
temp->next=NULL;
*data=temp->data;
free(temp);
其它队列：
循环队列：
循环队列顺序存储和链式存储
以顺序存储为例：
判断循环队列是否已满：
if((que->rear+1)%MAXSIZE==que->front)
{
}
判断循环队列是否为空：
if（que->rear==que->front）
{
}
双端队列：
可以在队列的两端进行插入和删除操作
队列有A、B两端
如果A端进行入队操作，B端就进行出队操作
如果A端进行出队操作，B端就进行入队操作
参考双向链表
输入受限队列：
限制队列的一端只能进行入队操作，不能进行出队操作
输出受限队列：
限制队列的一端只能进行出队操作，不能进行入队操作
三、树形结构
树形结构：
是指数据之间呈现一对多的关系
现实中的数据，并不一定呈现一对一的关系，可能呈现一对多的关系
例如：
一个公司的组织架构
或
一个家族的关系系统
树：
由n个结点构成的有限序列，称之为“树”，结点之间呈现一对多的关系，每个结点就是一个数据
树中有且仅有一个结点称为根结点，根结点之后的其它结点构成的集合，称之为结点的子树
结点的度：
结点拥有的子树的个数，称之为“结点的度”
树的度：
结点拥有的最大的子树的个数（结点的度最大的值），称之为“树的度”
树的高度或深度：
结点的层次的最大值，称之为树的高度或深度
结点的层次：
按照从上往下从1开始对层次进行编号，根结点处于第1层
孩子：
结点的子树，称之为结点的孩子
父亲：
结点的根结点，称之为“结点的父亲”
兄弟：
根节点的子结点之间，称呼“兄弟”
堂兄弟：
处于同一层的结点之间，称为“堂兄弟”
祖宗：
从该结点出发，它的所有父结点，都是该结点的祖宗
叶子：
叶子也称为“终端结点”，结点没有任何的孩子，就成为该结点为“叶子”
....
树的应用：
二叉树：
树中结点的子树不能超过2
概念：
二叉树也是由n个结点构成的有限序列，其中每一个结点的度大小不超过2，并且二叉树有严格的左右子树之分
二叉树的性质：
（1）深度为k的二叉树最多有多少个结点？答案：2^k-1个结点
（2）在二叉树的第k层上最多有多少个结点？答案：2^(k-1)个结点
（3）在任意的一颗二叉树中，终端结点（叶子）数为n0，度为2的结点数为n2，请问n0和n2之间的关系？答案：n0=n2+1
（4）具有n个结点的完全二叉树的深度为多少?答案：log2n+1
满二叉树：
深度为k并且具有2^k-1个结点的二叉树，称之为“满二叉树”，除了叶子节点之外，二叉树中其他结点都有左、右子树，并且叶子节点都处于同一层
完全二叉树：
深度为k具有n个结点的二叉树与满二叉树的结点编号一致，称为“完全二叉树”，满二叉树是完全二叉树的一种特殊情况
遍历二叉树：
沿着二叉树的某一个结点出发，依次访问二叉树中的每一个结点，并且每一个结点只访问一次
先序遍历：
先访问二叉树中的根节点，再访问二叉树中的左子树，最后再访问二叉树中右子树
简称“根左右”
中序遍历：
先访问二叉树中的左子树，再访问二叉树中的根节点，最后再访问二叉树中右子树
简称“左右根”
后序遍历：
先访问二叉树中的左子树，再访问二叉树中的右子树，最后再访问二叉树中的根结点
二叉树的存储：
顺序存储：
存储二叉树中的结点时，是从上往下，从左往右（二叉树的层次存储&层次遍历）的顺序依次存储二叉树中的结点
为了方便的表示二叉树中的结点之间的关系，将结点的度不满的子树开辟空间并赋为空（缺点，需要为空的结点开辟空间）
顺序存储适用于满二叉树，不需要额外的开辟空间，没有造成空间资源的浪费
struct B_Tree
{
char tree[MAXSIZE];
};
//创建二叉树的顺序存储
struct B_Tree *Tree_Create()
{
struct B_Tree *tree1=(struct B_Tree *)malloc(sizeof(struct B_Tree));
if(tree1==NULL)
{
return false;
}
memset(tree1->tree,0,sizeof(tree1->tree));
return tree1;
}
void Tree_Insert(struct B_Tree *T ,char data)
{
for(int i=0; i<MAXSIZE;i++)
{
if（T->tree[i]!=0）
{
T->tree[i]=data;
break;
}
}
}
void Tree_Travel(struct B_Tree *T )
{
for（int i=0; i<MAXSIZE;i++）
{
if(T->tree[i]=='#')
{
continue;
}
printf("二叉树中的结点：%dn",T->tree[i]);
}
}
int main()
{
struct B_Tree *T=Tree_Create();
Tree_Insert(T,'a');
Tree_Insert(T,'b');
Tree_Insert(T,'#');
Tree_Travel(T);
return 0;
}
链式存储：
对于二叉树中的结点：包含了数据域和指针域
格式：
struct Tree
{
数据域；
指向左子树的指针；
指向右子树的指针；
}；
例如：
struct Tree
{
int data;
struct Tree *LChild;//左子树
struct Tree *RChild;//右子树
};
//练习：创建二叉树，遍历时将先序遍历、中序遍历、后序遍历的结果输出出来
//创建二叉树
struct Tree *Tree_Create()
{
struct Tree *T;
char in_ch;//获取用户输入的字符
scanf("%c",&in_ch);
if(in_ch=='#')
{
return NULL;
}
T=(struct Tree *)malloc(sizeof(struct Tree));
if(T==NULL)
{
printf("结点空间申请失败，创建失败！n");
return NULL;
}
T->data=in_ch;
T->LChild=Tree_Create();
T->RChild=Tree_Create();
return T;
}
//先序遍历
status begin_Travel(struct Tree *T)
{
if(T==NULL)
{
return false;
}
printf("%c",T->data);
begin_Travel(T->LChild);
begin_Travel(T->RChild);
return true;
}
//中序遍历
status mid_Travel(struct Tree *T)
{
if(T==NULL)
{
return false;
}
mid_Travel(T->LChild);
printf("%c",T->data);
mid_Travel(T->RChild);
return true;
}
//后序遍历
status back_Travel(struct Tree *T)
{
if(T==NULL)
{
return false;
}
back_Travel(T->LChild);
back_Travel(T->RChild);
printf("%c",T->data);
return true;
}
二叉树的应用：
哈夫曼树：
树的带权路径长度最小的树，称之为“哈夫曼树”，也称为“最优二叉树”，应用：编码（哈夫曼编码）问题
结点的路径长度：
从根节点出发一直到该结点的分支数目，就成为结点的路径长度
树的路径长度：
从根结点出发一直到所有的叶子结点的分支数目之和，称为“树的路径长度”
结点的带权路径长度（WPL：weight path length）：
权：权重
是指从根节点出发一直到该节点的分支数目乘以权重
树的带权路径长度：
从根结点出发一直到所有的叶子结点的分支数目乘以该叶子结点的权重之和，称为“树的路径长度”
哈夫曼树的构造过程：
（1）创建n个具有一个结点的二叉树，n个具有一个结点的二叉树就构成了深林T={T1，T2，T3，.......................}
（2）在深林T中取出两个权重最小的二叉树组成一个新的二叉树（两个二叉树的权重相加称为新的二叉树的权重），将新的二叉树放入深林中
（3）重复第（2）步，直到最终构成的一棵树，就成为“哈夫曼树”
哈夫曼树如何进行编码：
将哈夫曼树中的结点的左分支编码为0，将结点的右分支编码为1
注意：
离根结点越近，结点的权重越大
离根结点越远，结点的权重越小
结点的度没有为1的情况，结点的度要么是2要么是0
四、图形结构
数据与数据之前呈现的是多对多的情况，类似于现实中的关系网或者是互联网
图形结构的表示：
分为结点（顶点）和边构成
符号表示：
G（V，E）；
Graph：图形
Vertex：顶点，V是顶点的集合
Edge：边，E是边的集合
图形结构：有向图和无向图
无向图：顶点之间连接的边是没有方向，称为无向图
有向图：顶点之间连接的边是有方向，称为有向图
图形的存储：
顺序存储
采用邻接矩阵去存储图中的数据元素（包含了顶点和边）
邻接矩阵采用二维数组存储图中的数据元素
无向图（无向网）的存储：
无向图中本身自己的结点是没有边，用0表示
无向图中的其他两个结点没有边，用0表示
Graph[m][n]=
顶点用一维数组进行存储
struct Graph
{
顶点的集合；
边的集合；
存储大小；
....
};
例如：
struct Graph
{
char vertex[max];//顶点的集合
char edge[max][max];//边的集合
int graph_len;//图的大小
}
有向图（有向网）的存储：
如果结点和其他结点之间边有方向，A->B ，edge<A,B>=1 edge<B,A>=0或无穷
其他参考无向图
图带权值：
二维数组中如果两个顶点之间没有边，那么就表示为无穷，如果有边，表示为权值
链式存储
采用邻接表去存储图中的数据元素（包含了顶点和边，还包含定点与顶点之间的连接）
链式存储：顺序表和链表结合起来对图中的顶点和边进行存储
（1）存储顶点的数据元素和指向下一个顶点的指针
（2）创建类似于单链表的表，来存储顶点之间的关系和其他顶点的下标
图的遍历：
深度优先遍历
是从图的某一个顶点出发，一直遍历图中的所有结点，并且每一个结点只访问一次
广度优先遍历
类似于树形结构中的层次遍历，是从某一个顶点出发，依次访问与该顶点相关的其他顶点，并且每一个结点只访问一次
五、算法
查找算法：
（1）顺序查找
例如：
从表中的第一个数据元素开始进行查找，按照顺序，一直找到表的最后一个数据元素
遍历表中的所有数据元素，一个一个的进行查找，如果找到，返回成功，找不到即失败
时间复杂度：
最坏情况下，查找的时间为：O（n）
最好情况下，查找的时间为：O（1）
（2）二分查找（拆半查找）
前提：
表中的数据元素是按照一定的顺序（由小到大或由大到小）进行存储，从而才能实现拆半查找
思路：
1）创建一张顺序表
2）定义两个哨兵，一个哨兵p执行顺序表的第一个数据元素，另外一个哨兵q指向最后一个数据元素
3）将顺序表的长度除以2（temp=(p+q)/2）存储在临时变量temp中
4）将待查找的数据data与temp指向的数据进行比较，如果data小于temp指向的数据，将q指向temp-1的位置，重复第3步；如果data大于temp指向的数据，将p指向temp+1的位置，重复第3步
5）当temp指向的位置的数据与data相等，找到该数据，如果不相等，重复第3、4步，当两个哨兵相遇之后，还未找到，查找失败（顺序表中没有该数据）
（3）冒泡排序
思路：
使用嵌套的for循环，外层循环控制循环多少次才能实现表中的数据变得有序，内层循环控制找到表中的最大的数据元素
1）外层循环第1次，内层循环遍历表长度-1次，找到最大的数据元素
2）外层循环第2次，内层循环遍历表长度-2次（注：这里-2次是因为第1）步已经找到最大的数据元素），找到最大的数据元素
3）依次类推，直到表中剩下两个数据比较完成，代表整个冒泡排序完成
（4）选择排序
思路：
（5）快速排序
思路：
1）创建一张表，表对顺序没有要求
2）从表中找到一个数据，作为基准数据，基准数据一般是用表中的第一个数据（最后一个数据）作为基准数据
3）设置两个哨兵A和B，一个哨兵A是指向表中的第一个数据元素，另外一个哨兵B指向表中的最后一个数据元素
4）哨兵B开始从右往左开始行走，直到走到比基准数据小的就停下；哨兵A从左往右开始行走，直到走到比基准数据大的就停下；只要哨兵A和哨兵B没有相遇，就将哨兵A指向的数据与哨兵B指向的数据进行交换；当哨兵A和哨兵B相遇（即指向同一个数据元素），这时候就将哨兵指向的数据元素与基准数据进行交换