数据结构笔记
第1章-绪论
绪论
数据(data)是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(data element)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据对象(data object)是性质相同的数据元素的集合，是数据的一个子集。数据结构(data structure)又称逻辑结构，是相互之间存在一种或多种特定关系的数据元素的集合。通常有以下四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。存储结构（物理结构）是数据结构在计算机中的表示（又称映像）。数据类型(data type)是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型(AbstractData Type)是指一个数学模型以及定义在该模型上的一组操作，可细分为：原子类型、固定聚合类型、可变聚合类型。
-
常用的数据结构类型：集合、线性、树形、图状
-
数据结构：
① 逻辑结构：
数据元素之间的关系② 存储结构：数据结构在计算机中的表示。存储结构分为：
顺序存储结构和链式存储结构 -
算法是对特定问题求解步骤的一种描述，算法具有如下特性：有穷性、确定性、可行性、输入、输出
-
算法的度量：
①
时间复杂度②
空间复杂度
衡量 一个算法 是否优秀，则主要从以下几点考虑：正确性，可读性，健壮性，时间复杂度，空间复杂度
时间与空间复杂度
时间复杂度 主要衡量一个算法的 运行快慢，而 空间复杂度 主要衡量一个算法 运行所需要的额外空间（但如今我们已经不需要特别关注一个算法的空间复杂度）
时间复杂度 简单来说是一个数学里的 函数表达式，算法中的 基本操作的执行次数（就是跑了多少次）为算法的时间复杂度。
空间复杂度 是对算法运行过程中临时 额外占用存储空间大小的量度，不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是 变量的个数，也使用大O渐进表示法。
注意：函数运行时所需要的 栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定
-
如何计算时间复杂度？
-
大O的渐进表示法（估算）：
推导大O阶方法① 用常数
1取代运行时间中的所有加法常数。
② 在修改后的运行次数函数中，只保留最高阶项。
③ 如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。
双重循环时间复杂度
常数循环时间复杂度
strchar时间复杂度
冒泡排序时间复杂度
二分查找时间复杂度
递归时间复杂度
- 常见的时间复杂度所耗费的时间从
小到大依次是
冒泡排序空间复杂度
习题
- 抽象数据类型与计算机内部表示和实现
无关（✔） - 数据的
逻辑结构分两大类: 1.线性结构2.非线性结构 逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构
- 数据的
存储方法有四种: 1、顺序存储方法2、链接存储方法3、索引存储方法4、散列存储方法 - 数据结构的
逻辑结构独立于其存储结构 - 数据结构在计算机内存中的表示是指数据的
存储结构 - 物理上：数据元素的
映像相当于值，关系有顺序存储和链式存储
链式存储的存储结构所占存储空间：分两部分,一部分存节点值,另一部分存表示节点间关系的指针- 算法的
时间复杂度取决于问题的规模和待处理数据的初态
第2章-线性表
- 线性表包括数据结构中的：
数组，单链表，双链表 ，循环链表(尾部可以指向头部)等
- 线性表的定义：首先它是
n个数据元素的有限序列，元素之间是有顺序的，若元素存在多个，则第一个元素无前驱，最后一个元素无后继，其他每个元素都有且只有一个前驱和后继 - 用
malloc扩展内存容量，这样就做到了既不浪费内存，又可以让线性表容量随输入的增加而自适应大小
顺序表（数组的操作）
- 也是一个
线性表 - 用
数组描述数据元素物理存储的连续性，实际上就是一个数组的操作 - 理解为数组的操作即可 → 用来封装数组的常规操作(
增、删、改、查) - 采用
顺序存储描述的线性表叫做顺序表 - 要知道顺序表的长相，抽象结构体代码的根本
顺序表的创建
- 用
数组描述 maxSize：记录最大容量的变量curSize：记录当前元素个数的变量（容器）- (顺序表中的定义需要有一个一级指针去做内存申请)：
定义一个数组指针|动态内存申请变成一个数组
顺序表的实现
# include <stdio.h>
# include <stdlib.h>
# include <assert.h>//断言|用于判空处理|申请内存可能失败
# define Max 10 //最大元素个数
typedef int DataType; //给数据类型起别名
//结构体的抽象----->抽象长相
enum INFO //枚举变量类型-1:错误信息
{
OK=1,
ERROR=-1
};
//注意这里是用typedef给struct List{...} * 起一个别名LPList
typedef struct
{
DataType* data; //存储char类型的数据
int maxSize; //最大元素个数--->容量
int curSize; //当前元素个数
}List,*LPList; //结构体的别名/结构体指针别名顺序表的创建
- 用一个
指针表示一个结构体变量，返回的是一个指针，创建过程就是初始化数据，有几个数据成员就给几个数据成员初始化即可 - 任何一种结构都是一个结构体变量，只是表达方式不一样
顺序表的创建
LPList createList(int maxSize) //参数：最大值
{
//创建过程，就是初始化数据---动态内存申请把指针变成变量
LPList list=(LPList)malloc(sizeof(List));
assert(list); //断言处理
//初始化变量中的东西
list->maxSize=maxSize;
list->curSize=0;
//指针变成一个数组---数组的内存需要二次申请
//DataType*代表要申请什么类型的这里是int
//sizeof(DataType)*maxSize代表要申请多大，sizeof(类型)*大小
list->data=(DataType*)malloc(sizeof(DataType)*maxSize);
assert(list->data);
return list;
}任何数据结构都有的万金油函数
万金油函数
//获取当前元素个数（或者返回bool类型）
int size(LPList list)
{
if(list==NULL) //前提是list不能为空
return ERROR;
return list->curSize;
}
int empty(LPList list)
{
if(list==NULL)
return ERROR;
return list->curSize==0; //当curSize为空时为真(1)，否则为假(0)
}顺序表的增删改查实现
获取顺序表中的元素—通过下标去获取元素
-
参数：获取哪个顺序表中的元素 -
注意：表
不能为空&下标是否满足要求 -
下标不合格的情况：当前元素个数
curSize < 要访问的下标 index
通过下标获取元素
//参数：LPList list：获取哪个顺序表中的元素 int index:通过下标去获取元素
DataType getData(LPList list,int index)
{
if(list==NULL || list->curSize==0) //任一条件满足都会退出
{
printf("list is empty......\n"); //错误提示，无法获取
return ERROR;
}
if(list->curSize<index) //下标是否满足要求？
{
printf("index is invalid......\n"); //错误提示，invalid:无效
return ERROR;
}
//注意：index是第几个元素，第一个元素，第二个元素...没有第0个元素
return list->data[index-1];
}无序顺序表的插入
- 元素
不存在顺序，直接插到顺序表中即可 参数：插入的顺序表 插入的下标 插入的数据- 顺序表的插入操作就是
数组的插入操作 - 数组实现的数据结构，放进去要考虑
满的状态(链表不需要)，拿出来要考虑空的状态 - 把要插入的元素放在
最后面 - 让最后面的元素一直与前面的元素
依次交换到指定的位置
插入
int insertList(LPList list,int index,DataType data)
{
//大前提：无法插入
if(list==NULL)
{
printf("list is empty......\n");
return ERROR;
}
//满的情况
if(list->curSize == list->maxSize)
{
printf("list is full......\n");
return ERROR;
}
//第一次插入时
if(index==0&&list->curSize==0)
{
list->data[list->curSize++]=data; //插入数据
return OK;
}
//index为其他值，看下标是否满足要求，第一次插入只能是index==0
if(list->curSize<1||list->curSize<index)
{
printf("index is invalid......\n");
return ERROR;
}
//其他情况正常插入
int pos = list->curSize; //pos==最后一个下标
list->data[pos]=data;//插到最后面
//调整位置
while(pos!=index)
{
//交换
DataType temp = list->data[pos];
list->data[pos] = list->data[pos-1];
list->data[pos-1] = temp;
pos--;
}
list->curSize++;//插入成功后数量+1
}打印
void printList(LPList list)
{
if(list == NULL || list->curSize==0)//两种情况为空无法打印
{
printf("list is empty......\n");
return;
}
//打印
for(int i=0;i<list->curSize;i++)
{
printf("%d\t",list->data[i]);
}
printf("\n");
}main函数调试
int main()
{
LPList list = createList(Max);
insertList(list,1,1);//开始只能是下标0
insertList(list,0,2);
insertList(list,0,1);
insertList(list,0,1);
insertList(list,0,1);
insertList(list,0,1);
printList(list);
return 0;
}
//结果
//index is invalid......
//2 1 1 1 1顺序表的删除(伪删除)—数组没有办法释放单一内存
参数：要删除的表 要删除第几个元素(通过序号做删除)25是要删除的位置，先把77挪到25的位置，再把999挪到77的位置- 只是77把25给
覆盖了(逻辑上的删除)，没有处理999的内存，元素999还在 真正的删除是curSize从5变成了4，把记录大小的curSize做- -运算
删除
int deleteList(LPList list,int index)
{
if(list == NULL || list->curSize==0)//表为空，无法删除
{
printf("list is empty......\n");
return ERROR;
}
if(list->curSize<index)//判断下标是否满足规则
{
printf("list is invalid......\n");
return ERROR;
}
for(int i=index-1;i<list->curSize;i++)
{
list->data[i]=list->data[i+1];//把i+1的值移到i的位置
}
list->curSize--;//伪删除
return OK;
}
//测试
deleteList(list,1);
printList(list);
//index is invalid......
//2 1 1 1 1
//1 1 1 1头插&尾插
头插&尾插
//头插
void push_front(LPList list,DataType data)
{
insertList(list,0,data);
}
//尾插
void push_back(LPList list,DataType data)
{
if(list==NULL)//为空无法插入
{
printf("list is empty......\n");
return;
}
if(list->curSize==list->maxSize)//满了也无法插入
{
printf("list is full......\n");
return;
}
list->data[list->curSize++]=data;//能够插入
}
//测试
insertList(list,0,0);
insertList(list,1,1);
insertList(list,2,2);
printList(list);
push_front(list,999);
push_back(list,666);
printList(list);
//结果
0 1 2
999 0 1 2 666头删&尾删
头删&尾删
//头删
void pop_front(LPList list)
{
deleteList(list,0);//删除第一个位置
}
//尾删
void pop_back(LPList list)
{
deleteList(list,list->curSize);
}
//测
pop_front(list);
printList(list);
pop_back(list);
printList(list);
//结果
999 0 1 2 666
0 1 2 666
0 1 2顺序表的查找—通过元素去找下标
通过元素去找下标
int searchList(LPList list,DataType data)
{
if(list==NULL)//为空无法查找
{
printf("list is empty......\n");
return ERROR;
}
//遍历数组
for(int i=0;i<list->curSize;i++)
{
if(list->data[i]==data)//当元素==data
{
return i;//返回下标
}
}
return ERROR;//找不到返回ERROR
}
//测试
insertList(list,0,1);
insertList(list,1,99);
insertList(list,2,6);
printList(list);
int num=searchList(list,99);
printf("%d\n",num);
//结果
1 99 6
1有序顺序表的问题—有序性插入
- 插入后的序号由
元素决定 - 直接插入元素，不需要根据序号做插入，会
自动根据数据做排序 - 注意是在
插入时做排序，不是先插完再排序
有序插入
void insert_sort(LPList list,DataType data)
{
if(list==NULL)
{
printf("list is empty......\n");
return;
}
if(list->curSize==list->maxSize)
{
printf("list is full......\n");
return;
}
if(list->curSize==0)//直接插入
{
list->data[list->curSize++]=data;
return;
}
list->data[list->curSize]=data;
for(int i=list->curSize;i>0;i--)//i等于最后一个下标 k<=0也要退出循环
{
if(list->data[i]<list->data[i-1])//交换
{
DataType temp=list->data[i];
list->data[i]=list->data[i-1];
list->data[i-1]=temp;
}
else
{
break;//其他情况：大于/大于的情况，直接break
}
}
list->curSize++;//插入成功
}
//测试
insert_sort(list,4);
insert_sort(list,1);
insert_sort(list,3);
insert_sort(list,0);
insert_sort(list,-99);
insert_sort(list,300);
//结果
-99 0 1 3 4 300销毁顺序表
销毁顺序表
void destoryList(LPList* list)
{
if(*list==NULL)
{
printf("list is empty......\n");
return;
}
free((*list)->data);
free(*list);
*list=NULL;
}
//测试
destoryList(&list);
printList(list);
//结果
list is empty......优点：
存储密度大（结点本身所占存储量/结点结构所占存 储量）- 可以随机存取表中任一元素
缺点：
- 在插入、删除某一元素时，需要移动大量元素
浪费存储空间- 属于
静态存储形式，数据元素的个数不能自由扩充
链表
链表的概念
-
链式结构可以理解为
内存不连续的数组，通过计算机中的零散内存组合在一起 -
各结点由两个域组成：
数据域：用来存放用户使用的数据指针域：用来存放下一个节点的地址 -
单链表、双链表、循环链表：
① 结点
只有一个指针域的链表，称为单链表或线性链表② 有
两个指针域的链表，称为双链表③
首尾相接的链表称为循环链表 -
头指针是指向链表中第一个结点的指针首元结点是指链表中存储第一个数据元素a1的结点头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，此结点不计入链表长度
Q：1.如何表示空表？
有头结点时，当头结点的指针域为空时表示空表
Q：2. 在链表中设置头结点有什么好处？
① 便于首元结点的处理 首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致，无须进行特殊处理;② 便于空表和非空表的统一处理
优点：
- 数据元素的个数可以自由扩充
- 插入、删除等操作不必移动数据，只需修改链接指针，修改效率较高
缺点：
- 存储密度小
- 存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）
单链表
链表的结构体描述
# include <stdio.h>
# include <stdlib.h>
# include <assert.h> //断言 判空处理
typedef int DataType;
typedef struct Node
{
DataType data; //数据域
struct Node* next; //指针域
}NODE,*LPNODE;创建表头
创建表头：用指针表示 指针要变成一个变量 做动态内存申请
//创建结构体变量
LPNODE createHead()
{
LPNODE headNode = (LPNODE)malloc(sizeof(NODE));
assert(headNode);
//headNode->data 数据不做初始化
headNode->next = NULL;//指针域--->单一的节点通常置为空
return headNode; //返回新节点
}创建节点
插入数据：需要把用户的数据先变成一个节点，只有相同结构的东西才能组合在一起
//和创建表头类似 多了数据的处理--->对新节点的数据做处理
LPNODE createNode(int data)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
assert(newNode);
newNode->data = data; //data为传过来的数据
newNode->next = NULL;
return newNode;
}打印链表
- 以
headNode为头节点的链表，有头节点，从第2个节点headNode->next开始打印
void printList(LPNODE headNode)
{
LPNODE pmove = headNode->next; //从第2个节点开始打印
while (pmove != NULL)
{
printf("%d\t", pmove->data); //当前节点不为空 打印数据
pmove = pmove->next; //打印完当前节点 走到下一个节点的位置
}
printf("\n");
}头插法
参数：要插入的链表(用头节点表示一个链表) 要插入的数据- 插入前需要创建节点，连接时
先连后断
void push_front(LPNODE headNode, int data)
{
LPNODE newNode = createNode(data); //插入前需要创建节点
newNode->next = headNode->next; //先连后断
headNode->next = newNode;
}
//测试代码
LPNODE list = createHead(); //创建链表
//插入
for (int i = 0; i < 3; i++)
{
push_front(list, i); //0 / 1 0 / 2 1 0
}
printList(list); //2 1 0尾插法
参数：要插入的链表 要插入的数据- 要找表尾，定义一个节点
pMove去做移动 - 从headNode开始找，如果 headNode 为空，直接插到 headNode->next，注意不要从第2个节点 headNode->next 开始找，因为第2个节点可能为空，会出现非法访问的情况
while( NULL->next != NULL)
void push_back(LPNODE headNode, int data)
{
LPNODE pmove = headNode;
while (pmove->next != NULL)
{
pmove = pmove->next; //一直往下走
}
LPNODE newNode = createNode(data); //创建节点
pmove->next = newNode; //找到表尾后做插入
}
//测试代码
push_back(list,666);
printlist(list); //2 1 0 666 指定位置插入
- 一般用数据作为指定节点 || 用第几个节点的方式去指定
- 可以选择在指定位置前 || 指定位置后插入
- 把问题转换为找到节点后做插入
void push_appoin(LPNODE headNode, int posData, int data)
{
LPNODE preNode = headNode;
LPNODE curNode = headNode->next; //一前一后
//先查找 当前节点数据!=指定数据 一直往下找 到curNode为空结束
while (curNode != NULL && curNode->data != posData) //短路 前面不成立后面不判断
{
//preNode = preNode->next; //前区节点和当前节点都往下走
//curNode = curNode->next;
preNode = curNode; //当前节点走到后一个节点的位置
curNode = preNode->next; //后一个节点走到原来位置的下一个
//curNode = curNode->next;
}
//分析查找结果
if (curNode == NULL) //未找到指定位置 无法做插入
{
printf("无法插入,没找到指定位置!\n");
}
else
{
LPNODE newNode = createNode(data); //不需要急着创建节点 没找到没必要创建
preNode->next = newNode; //连接
newNode->next = curNode;
}
}
//测试代码
push_appoin(list, 2, 999); //999 2 1 0 666
printList(list);头删法
- 只能删除第2个节点，不能删除第1个节点，因为是有头链表
- frontNode (第一个带数据的节点)—>要删除的节点
- 连接后释放 || 删除
void pop_front(LPNODE headNode)
{
LPNODE frontNode = headNode->next; //要删除的节点
if (frontNode == NULL)
{
printf("无法删除，链表为空!\n"); //为空无法做删除 一定要有一个节点
}
else
{
headNode->next = frontNode->next; //头节点的下一个指向第一个节点的下一个
free(frontNode); //释放后置空即可
frontNode = NULL;
}
}
//测试代码
pop_front(list);
printList(list); //2 1 0 666尾删法(和指定位置插入代码类似)
- 把最后一个节点删除了，注意要处理它的上一个节点的 next 指针
- 把 node3 删掉，要把 node2 的 next 指针置为空，不能让 node2 指向被释放的内存(要对指针做一下初始化)
void pop_back(LPNODE headNode)
{
LPNODE preNode = headNode; //前区节点
LPNODE backNode = headNode->next; //表尾节点
while (backNode != NULL && backNode->next != NULL) //当前节点的next指针!=NULL
{
preNode = backNode; //记录位置
backNode = preNode->next; //往下走
}
//分析查找结果
if (backNode == NULL)
{
printf("链表为空，无法删除!\n");
}
else
{
free(backNode); //释放最后一个节点
backNode = NULL;
preNode->next = NULL; //把上一个节点的next指针置为空
}
}
//测试代码
pop_back(list);
printList(list); //2 1 0指定位置删除
- 以数据作为指定
void pop_appoin(LPNODE headNode, int posData)
{
LPNODE preNode = headNode;
LPNODE curNode = headNode->next;
//先查找
while (curNode != NULL && curNode->data != posData)
{
//preNode = preNode->next;
//curNode = curNode->next;
preNode = curNode;
curNode = preNode->next;
}
//分析查找结果
if (curNode == NULL)
{
printf("未找到，无法删除!");
}
else
{
preNode->next = curNode->next; //把前面那个节点的指针指向当前节点的下一个
free(curNode); //释放当前节点后置空
curNode = NULL;
}
}
//测试代码
pop_appoin(list, 2);
printList(list); //1 0查找链表
- 参数：要找的链表 要找的位置
- 返回空：没找到 返回不是空的节点：找到了
LPNODE searchNode(LPNODE headNode, int posData)
{
LPNODE pmove = headNode; //从第2个节点开始找
while (pmove != NULL && pmove->data != posData)
{
pmove = pmove->next; //往下走
}
return pmove;
}销毁链表
- 需要传
二级指针：干掉所有的内存 - 删除的方式：定义一个移动的指针指向第一个节点，把下面的保存起来再做删除过程，从第1个节点删除到最后一个节点，删到空就结束
void destoryList(LPNODE* headNode) //传二级指针
{
LPNODE nextNode = NULL;
while (*headNode != NULL) //不为空 把下一个节点保存起来持续做删除
{
nextNode = (*headNode)->next; //记录当前移动节点的下一个节点
free(*headNode); //释放表头后把表头置为下一个节点
*headNode = nextNode;
}
}
//测试代码
destoryList(&list);
if (list == NULL) //判断是否为空
{
printf("删除成功！\n");
}有序链表的构建
有序链表的构建过程是怎么样的？以上数据依次插入到链表如何形成有序？需要从原链表中找第一次大于要插入元素的位置，如果没有找到就插在链表的后面 (假设从小到大排序)
//要插入的链表 要插入的数据
void push_sort(struct Node* list, int data)
{
//把用户的数据变成一个节点
struct Node* newNode = createNode(data);
//找第一次大于新节点元素的位置以及前驱节点-> 指定位置插入
struct Node* preNode = list;
//当前节点
struct Node* curNode = list->next;
//当前节点不为空 并且当前节点的数据 <= 指定数据
while (curNode != NULL && curNode->data <= data)
{
//接着往下找
preNode = curNode;
curNode = preNode->next;
}
//当前节点为空 preNode == list 代表没有移动一步
if (curNode == NULL && preNode == list)
{
//链表为空直接把新节点插到 list 后面
list->next = newNode;
}
//当前节点为空 preNode != list
else if (curNode == NULL && preNode != list)
{
//没有找到直接放在链表的最后面
preNode->next = newNode;
}
//在中间
else
{
//做插入
preNode->next = newNode;
newNode->next = curNode;
}
}链表的归并
- 两个有序链表 1 3 5、2 4 6 做归并，把第二个链表遍历一遍，做一次有序插入
//把第一个链表中的值归并到第二个链表中
void mergeList(struct Node* list1, struct Node* list2)
{
//循环遍历第二个链表
struct Node* pmove = list2->next;
//节点不为空
while (pmove != NULL)
{
//插到list1中 要插入的数据
push_sort(list1, pmove->data);
pmove = pmove->next;
}
}
//测试
//创建两个链表
struct Node* list1=createList();
push_sort(list1, 1);
push_sort(list1, 3);
push_sort(list1, 5);
struct Node* list2 = createList();
push_sort(list2, 2);
push_sort(list2, 4);
push_sort(list2, 6);
mergeList(list1, list2);
printList(list1);
//结果
1 2 3 4 5 6双向链表
双链表顾名思义，就是链表由 单向的链变成了双向链。 使用这种数据结构，我们可以不再拘束于单链表的单向创建于遍历等操作， 大大减少了在使用中存在的问题。每一个节点都有两个指针分别指向该节点的 前驱和后继。
代码可以参考CSDN：C语言~无头链表，双向链表，双向循环链表
习题
1.在带头结点的非空单链表中，头结点存储位置由头指针指示，首元素结点由头结点的NEXT域指示。
答案：✔
2.对于顺序表，以下说法错误的是（ ）
A.顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B.顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D.顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
答案：A
3.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
A单链表
B单循环链表
C带尾指针的单循环链表
D带头结点的双循环链表
答案：D
4.在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（ ）
Arear和rear->next->next
Brear->next 和rear
Crear->next->next和rear
Drear和rear->next
答案：B
8.假设顺序表的长度为 n
若在位序 1 处删除元素，则需要移动 n-1 个元素；
若在位序 n 处删除元素，则需要移动 0 个元素；
若在位序 i(1≤i≤n) 处删除元素，则需要移动 n-i 个元素。
假设各位序删除元素的概率相同, 则平均需要移动 (n-1)/2 个元素。
第3章-栈与队列
栈的基本概念
定义
只能在表的一端（栈顶）进行插入和删除运算的线性表逻辑结构
与线性表相同，仍为一对一关系存储结构
用顺序栈或链栈存储均可，但以顺序栈更常见运算规则
只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则实现方式
关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的不同而不同基本操作有入栈、出栈、读栈顶元素值、建栈、判断栈满、栈空等
数组栈
# include <stdio.h>
# include <stdlib.h>
# include <assert.h>
typedef struct
{
int* data;//存整数，需要一个数组，用指针表示
int top;//栈顶标记
int maxSize;//最大元素个数，栈容量
}STACK,*LPSTACK;
//创建栈->创建一个结构体变量
LPSTACK createStack(int maxSize)
{
//用指针表示一个结构体变量做动态内存申请
LPSTACK stack=(LPSTACK)malloc(sizeof(STACK));
assert(stack);//断言
//初始化：描述栈的最初状态 需要数据的内存 申请内存即可
stack->data=(int*)malloc(sizeof(int)*maxSize);
assert(stack->data);
stack->maxSize=maxSize;//记录最大元素个数，判断满的状态
stack->top=-1;//栈顶标记
return stack;
}
//入栈：入的栈 入的元素
void push(LPSTACK pstack,int data)
{
if(pstack==NULL)//为空 无法插入
return;
if(pstack->top+1==pstack->maxSize)//放进去要考虑满的状态：top+1
{
printf("栈满！！！\n");
return;
}
pstack->data[++pstack->top]=data;//top从-1开始赋值 把元素放在数组中即可
}
//出栈
void pop(LPSTACK pstack)
{
if(pstack==NULL||pstack->top==-1)
{
printf("栈为空，无法出栈\n");
}
pstack->top--;//栈不为空top--,伪删除
}
//获取栈顶元素
int top(LPSTACK pstack)
{
return pstack->data[pstack->top];
}
//获取size
int size(LPSTACK pstack)
{
return pstack->top+1;
}
//判断栈是否为空
int empty(LPSTACK pstack)
{
return pstack->top==-1;//返回1表示空
}
int main()
{
int arr[10];
LPSTACK pstack=createStack(10);//创建一个存储10个元素的栈
//入栈
push(pstack,1);
push(pstack,2);
push(pstack,3);
while(!empty(pstack))//不为空
{
printf("%d\t",top(pstack));//获取栈顶元素 3 2 1
pop(pstack);//不断出栈
}
printf("\n");
return 0;
}链式栈
# include <stdio.h>
# include <stdlib.h>
# include <assert.h>
/*
无表头链表再封装写法
栈实现：头插法+头删法
*/
typedef struct Node
{
int data;
struct Node* next;
}NODE,*LPNODE;
//创建节点
LPNODE createNode(int data)
{
LPNODE newNode=(LPNODE)malloc(sizeof(NODE));
assert(newNode);
newNode->data=data;
newNode->next=NULL;
return newNode;
}
typedef struct
{
LPNODE stackTop;//栈顶标记 指针
int curSize;
}STACK,*LPSTACK;
//创建栈
LPSTACK createStack()
{
LPSTACK pstack=(LPSTACK)malloc(sizeof(STACK));//创建一个结构体变量
assert(pstack);
//栈的最初状态
pstack->curSize=0;
pstack->stackTop=NULL;//没有元素 栈顶标记指向空
return pstack;
}
//入栈：入的栈 入的元素
void push(LPSTACK pstack,int data)
{
//表头插入
LPNODE newNode=createNode(data);
if(pstack->curSize==0)//栈顶为空
pstack->stackTop=newNode;//只有一个结点 栈顶标记指向新节点即可
else
{
newNode->next=pstack->stackTop;//新节点的next指针指向原来的栈顶元素
pstack->stackTop=newNode;//把原来的栈顶标记挪到新节点的位置
}
pstack->curSize++;//插入成功size++
}
//大小
int size(LPSTACK pstack)
{
return pstack->curSize;
}
//判断为空
int empty(LPSTACK pstack)
{
return pstack->curSize==0;//和最初状态比较 返回1为空，其他值则不为空
}
//获取栈顶元素
int top(LPSTACK pstack)
{
if(pstack==NULL||pstack->curSize==0)
{
printf("栈为空！！\n");
return;
}
return pstack->stackTop->data;//返回stackTop指向节点的数据
}
//出栈
void pop(LPSTACK pstack)
{
if(pstack==NULL||pstack->curSize==0)
{
printf("栈为空！！\n");
return;
}
//无头链表头删法
LPNODE nextNode=pstack->stackTop->next;//先把栈顶元素的下一个元素保存到nextNode
free(pstack->stackTop);//释放栈顶所指向的位置
pstack->stackTop=nextNode;//把栈顶挪到nextNode
pstack->curSize--;
}
int main()
{
LPSTACK pstack=createStack();
//入栈
push(pstack,1);
push(pstack,2);
push(pstack,3);
while(!empty(pstack))
{
printf("%d\t",top(pstack));//获取栈顶元素 3 2 1
pop(pstack);//不断出栈
}
printf("\n");
return 0;
}栈-进制转换
# include <stdio.h>
# include <stdlib.h>
//实际当中用到栈，直接用数组即可
//用的是栈的思想
int main()
{
int num = 1234;
//通常情况用数组充当栈内存
int stack[20];
int stackTop = -1;//下标充当位置
while (num != 0)
{
//入栈操作
stackTop++;
stack[stackTop] = num % 2;//等同于stack[++stackTop] = num % 2;
num /= 2;
}
//因为栈顶标记正好是等于数组下标
while (stackTop != -1)
{
printf("%d ", stack[stackTop]);//获取栈顶元素
//出栈，伪删除
stackTop--;
}
return 0;
}
//结果是num的二进制
1 0 0 1 1 0 1 0 0 1 0数组队列
队列的特性
- 存储数据的方式：一般情况下为
FIFO先进先出的结构 - 类似
食堂排队打饭，排在前面的先打饭
队列的属性
容量队头标记队尾标记
队列的分类
- 数组队列(普通队列+循环队列)
- 链式队列
- 优先队列(类似 vip 服务)
普通数组队列
- 用一个数组充当容量
- 队头标记 & 队尾标记就是数组下标，可以把它们的初始值等于
-1(保持下标的一致性)或者全部等于 0，无强制性要求，只是在放数据的时候下标的操作不太一样而已 - 刚开始没有元素，队头和队尾都在
同一个位置 - 放数据到队列中，用的是
队尾去操作(队尾往后移动)；拿数据用的是队头去操作(队头往后移动) 弊端：一旦做了出队操作，就会存在伪溢出问题：入完数据做出队操作，相对于以往来说容量改变了原因：做了一个出队操作后(队头往后挪了)，队头对应的下标不再是从 0 开始(队头来到下标[1]的位置)，下标[0]对应的内存无法使用，假设刚开始创建队列时的最大容量是 6 ，出队一个元素后，最大容量变成了 5- 一次性队列，可以把数据都存满，但是不能重复去操作
- 通过
取余 %让队尾 tail 回到前面去，不存在伪溢出问题(循环队列的方式) - 假设 max == 10，一旦队头变化(假设队头到达对应数组下标为1的位置)，就存不了10个元素，如果用 curSize 判断满的状态会引发中断
# include <stdio.h>
# include <stdlib.h>
# include <assert.h>
//抽象结构--->以整型数据为例
typedef struct Queue
{
int* qMem;//队列内存
int front;//队头标记
int tail;//队尾标记
int curSize;//当前元素个数
int maxSize;//最大容量
}QUESE,*LPQUESE;
//创建队列
LPQUESE createQueue(int maxSize)
{
//描述结构的最初结构--->用结构体指针表示一个队列
LPQUESE queue=(LPQUESE)malloc(sizeof(QUESE));//动态内存申请
assert(queue);
//给队列属性做初始化
queue->maxSize=maxSize;
queue->qMem=(int*)malloc(sizeof(int)*maxSize);//数组的二次内存申请
assert(queue->qMem);
queue->curSize=0;
queue->front=0;
queue->tail=0;
return queue;
}
//大小
int size(LPQUESE queue)
{
return queue->curSize;
}
//判断是否为空
int empty(LPQUESE queue)
{
return queue->curSize==0;//返回1为空
}
//入队 把元素放在队列中队尾做变化 入的队 入的数量
void push(LPQUESE queue,int data)
{
//判断是否为满的状态 用数组 放进去必须考虑满
if(queue->curSize==queue->maxSize)
{
printf("满了！！\n");
return;
}
queue->qMem[queue->tail++]=data;//把数据存到队列后队尾++
queue->curSize++;
}
//获取队头元素
int front(LPQUESE queue)
{
return queue->qMem[queue->front];
}
//出队 队头往后走
void pop(LPQUESE queue)
{
//出队要考虑是否为空
if(queue->curSize==0)
{
printf("队列为空\n");
return;
}
queue->front++;
queue->curSize--;
}
int main()
{
LPQUESE queue=createQueue(10);//创建队列，存放10个元素
for(int i=0;i<10;i++)
{
push(queue,i);//入队
}
printf("%d\n",front(queue));//0
pop(queue);
push(queue,100);//入队实际上超过了数组的容量，但是没报错？！
while(!empty(queue))
{
printf("%d ",front(queue));//1 2 3 4 5 6 7 8 9 100(100是溢出的但是还是打印了没报错)
pop(queue);
}
return 0;
}循环队列
循环队列
-
为了避免普通队列做完一次出队后想要重复使用，导致伪溢出问题而存在的
-
数组下标不变，只是改变队列的
front和tail的值去做数组的遍历 -
队列永远都是
先进先出，虽然数组中的顺序不是按照插入的顺序，但是出来仍然按照插入的顺序：不会影响打印结果，打印仍旧是有序的，按照插入的顺序先插入的先出去FIFO先进先出 -
判断队列满的状态的两种方式：
① 当
队尾 == 队头 & 队头 != 0就是满的状态(也有可能是空的状态队头 == 0)②
if(queue->front==(queue->tail+1)%Max）也可以判断满的状态③ 建议用
curSize判断，否则满的状态不太好判断
入队/出队
void push(LPQUEUE queue, int data)
{
if (queue->curSize == queue->maxSize)
{
printf("队列满了，无法入队!\n");
return;
}
queue->qMem[queue->tail] = data; //队尾存数据
queue->tail = (queue->tail + 1) % queue->maxSize; //让它满的时候出队时回到前面去
queue->curSize++;
}
void pop(LPQUEUE queue)
{
if (queue->curSize == 0)
{
printf("队列为空无法出队!\n");
return;
}
queue->front = (queue->front + 1) % queue->maxSize;
queue->curSize--;
}链式队列
- 一般用
无头链表记录头和尾的方式，不需要找表尾，因为 tailNode 永远是指向链表的表尾 入队：链表的尾插法出队：链表的头删法- 空的状态：队列的最初状态，没有节点，两个结构体指针都指向空
- 只有一个节点的情况(既是队头也是队尾)，队头和队尾都是指向
同一个节点 - 两个节点的情况：把原来表尾(原来表尾指向1)的 next指针 指向新节点，再把表尾移到新节点的位置即可
- 链表使用的是零散内存，无大小限制，相比数组队列不需要传maxSize
# include <stdio.h>
# include <stdlib.h>
# include <assert.h>
//节点
typedef struct Node
{
int data; //数据域
struct Node* next; //指针域
}NODE,*LPNODE,*LIST;
//创建节点--->把用户的数据变成一个节点才能插到队列中去
LPNODE createNode(int data)
{
LPNODE newNode = (LPNODE)malloc(sizeof(NODE));
assert(newNode);
newNode->data = data;
newNode->next = NULL;
return newNode;
}
//描述链表
typedef struct Queue
{
int curSize; //大小
LPNODE frontNode; //头节点
LPNODE tailNode; //尾节点
}QUEUE,*LPQUEUE;
//创建队列
LPQUEUE createQueue()
{
LPQUEUE queue = (LPQUEUE)malloc(sizeof(QUEUE)); //用指针表示一个队列
assert(queue);
queue->curSize = 0;
queue->frontNode = NULL; //队列刚开始都指向空
queue->tailNode = NULL;
return queue;
}
//万金油
int size(LPQUEUE queue)
{
return queue->curSize;
}
int empty(LPQUEUE queue)
{
return queue->curSize == 0;
}
//入队 入的队 入的数据
void push(LPQUEUE queue, int data)
{
LPNODE newNode = createNode(data); //入队前需要把用户的数据变成一个节点
//无头链表尾部插入
if (queue->curSize == 0) //第1次插入 插入的链表要成为队头和队尾
{
queue->frontNode = newNode;
//queue->tailNode = newNode;
//queue->curSize++;
}
else //链表有数据
{
queue->tailNode->next = newNode; //把tailNode->next指向新节点
//queue->tailNode = newNode; //把tailNode移到新节点的位置
//queue->curSize++;
}
queue->tailNode = newNode; //相同代码放在外面
queue->curSize++;
}
//获取队头元素
int front(LPQUEUE queue)
{
return queue->frontNode->data;
}
//出队
void pop(LPQUEUE queue)
{
//链表头删法
if (queue == NULL || queue->curSize == 0)
{
printf("队列为空，无法出队!\n");
return;
}
struct Node* nextNode = queue->frontNode->next; //记录下一个节点
free(queue->frontNode); //释放队头
queue->frontNode = nextNode; //把队头移到下一个节点的位置
queue->curSize--;
}
int main()
{
LPQUEUE queue = createQueue(10);
for (int i = 0; i < 10; i++)
{
push(queue, i);
}
while (!empty(queue))
{
printf("%d\t", front(queue));
pop(queue);
}
return 0;
}
//测试
0 1 2 3 4 5 6 7 8 9习题
1.在一个具有n个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以top作为栈顶指针，则作退栈操作时，top的变化是( )
A．top=top-1
B．top=top+1
C．top不变
D．top不确定
答案：B（这里跟正常的数组栈不一样，top是指针，栈底是地址高的那一边，所以最开始的时候top指向栈底，执行入栈操作的时候，top–，地址减小，执行出栈操作，top++，地址增加，向栈底方向移动。（跟正常的正好相反））
2.数组A[1…n]作为栈的存储空间，栈顶top的初值为n+1,在未溢出的情况表，以下（ ）完成入栈X操作。 (2分)
A.top++; A[top]=X;
B.A[top]=X; top++;
C.top–-; A[top]=X;
D.A[top]=X; top–-;
答案：C
3.用链接方式存储的队列，在进行删除运算时( )
A．仅修改头指针
B．仅修改尾指针
C．头、尾指针都要修改
D．头、尾指针可能都要修改
答案： D
4.数组Q［n］用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素个数的公式为（ ）.
A．r-f
B．(n+f-r)%n
C．n+r-f
D．（n+r-f)%n
答案： D（循环队列,r可能小于f,例如n为4时,元素个数有0、1、2、3,r可以为0,f为2,这样实际上有两个元素,但是以r-f得出来的是-2）
6.C语言数组Data[m+1]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为( )
A．front=front+1
B．front=(front+1)%m
C．rear=(rear+1)%m
D．front=(front+1)%(m+1)
答案 ： D（循环队列嘛，又不是双端队列，从头出。）
7.循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列的元素个数是（）；该循环队列最多可放下（）个元素。
答案：(rear-front+m)%m，m-1
第4章-串,广义表
什么是串
- 串（string）：由零个或多个字符组成的有限序列，也称字符串。记为：
S = ‘a1a2a3……an’ (n≥0)如：A= ‘BEIJING’， B= ‘JING’ - 和c++中的字符串是一个意思，C语言中当作数据结构去研究
- 实现串需要
存储空间和当前大小 - 串没有
'\0'，没有把’\0’拷贝进去，c++的 string 不能直接用%s形式打印，自己实现的串也不能用%s打印 - 串没有
'\0'，用curSize作为结束标记：串的连接、串的拷贝、串的比较
串相等：当且仅当两个串的值相等，即只有当两个串的 长度相等，并且各 对应位置的字符都相等 时才相等。通常在程序中使用的串可分为两种∶ 串变量和 串常量。串常量与整常数、实常数一样，在程序中 只能被引用但不能改变其值。
串变量和其它类型的变量一样， 其取值是可以改变的。
- 串的三种基本存储结构：① 定长顺序存储② 堆分配存储③ 块链存储
串的实现
串的结构体描述
# include <stdio.h>
# include <stdlib.h>
# include <assert.h>
# define MAX 1024 //最大容量
typedef struct
{
char mem[MAX];//用数组去存储字符串 char* mem
int curSize;//当前大小
}string,*LPSTR;串的创建
//创建一个结构体变量 通过字符串去创建
LPSTR createString(const char* str)
{
LPSTR pstr=(LPSTR)malloc(sizeof(string));//动态内存申请
assert(pstr);
for(int i=0;i<MAX;i++)//给属性初始化memset
{
pstr->mem[i]='\0';
}
int count=0;
while(str[count]!='\0')//!='\0'，则把字符串东西拷贝进去
{
pstr->mem[count]=str[count];//没有把'\0'拷贝进去 strcpy
count++;
}
pstr->curSize=count;
return pstr;
}串的插入
- 在指定位置 3 后面插入 Love
- 传入要插入的字符串长度，避免要求字符串的长度
- 在第7个位置开始插入字符串，下标大于curSize，直接把字符串放在原字符串后面即可
- 正常插入的情况：插入Love要挪 4 个位置，要插入几个元素，就挪几个位置，注意是从最后一个元素开始挪，如果从前面的元素开始挪，移位置会把后面的元素覆盖
//串的插入 当前串 要插入的串 字符串的长度 指定下标
void insertString(LPSTR pstr,const char* str,int len,int pos)
{
if(pos<0||pos>=MAX)//下标是否满足规则
{
printf("无效下标\n");
return;
}
if(pstr->curSize+len>=MAX)//满的状态
{
printf("太长，无法插入\n");
return;
}
if(pos>pstr->curSize)//下标大于curSize
{
for(int i=0;i<len;i++)//把新字符串放在原字符串后面
{
pstr->mem[pstr->curSize++]=str[i];
}
}
else
{
//腾位置
for(int i=pstr->curSize;i>=pos;i--)
{
pstr->mem[len+i-1]=pstr->mem[i-1];//把i的元素挪到i+len的位置上
}
//插入
for(int i=0;i<len;i++)
{
pstr->mem[pos+i]=str[i];//从pos+i的位置开始插入
}
pstr->curSize+=len;//原字符串的长度需要改变
}
}打印函数
//打印
void printString(LPSTR pstr)
{
for(int i=0;i<pstr->curSize;i++)
{
putchar(pstr->mem[i]);//用putchar打印
}
putchar('\n');
}main函数
int main()
{
LPSTR str1=createString("string");//创建串
insertString(str1,"Love",4,0);//插入串
printString(str1);
return 0;
}
//测试
Lovestring串的删除
- 这里只做
区间删除(通过下标的方式) - 匹配删除(BF算法+KMP算法)
- 数组的伪删除
- 删除中间的 4 个元素 Love，后面的元素都要往前移动4个位置，从前往后移动
- 7 - 4 == 3，实际移动位置为 4，注意移动的位置为
end - start + 1
//要删除的串 删除开始位置 第n个元素 删除的结束位置-->删除这段区间中的元素
void deletestring(LPSTR pstr,int start,int end)
{
if(start>end||end>pstr->curSize||start<=0)//下标是否满足
{
printf("区间有误！\n");
return;
}
int count=end-start+1;//移动的位置
for(int i=end,j=start-1;i<pstr->curSize;i++,j++)
{
pstr->mem[j]=pstr->mem[i];//注意没有把后面的串置'\0'
}
//伪删除，手动置0
for(int i=pstr->curSize;i>=pstr->curSize-count;i--)
{
pstr->mem[i]='\0';
}
pstr->curSize-=count;//注意长度变化
}矩阵的压缩存储
- 压缩矩阵实际上就是将一个
二维矩阵的非零元素单独记录并存储与之对应的行和列。
习题
1.串是一种特殊的线性表，其特殊性体现在（）
A.可以顺序存储
B.数组元素是一个字符
C.可以连续存储
D.数据元素可以是多个字符
答案： B（串又称为字符串，是一种特殊的线性表，其特殊性体现在数据元素是一个字符，也就是说串是一种内容受限的线性表。（栈和队列是操作受限的线性表））
2.若串S=“software”，其子串的个数是（ ）。(2分)
A.8
B.37
C.36
D.9
答案： B（串中n个不同的字符，共有(n(n+1)) /2个真子串，空串也算的话再+1。
题中8个字符，（8x9）÷2=36，加上空串就是37。）
3.假设以行序为主序存储二维数组A―array[1…100，1…100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=( )。
A．808
B．818
C．1010
D．1020
答案：B
4.数组A[0…4,-1…-3,5…7]中含有元素的个数()
A55
B45
C36
D16
答案：B（解析：三维数组：
长的边 个数：4-0+1=5
宽的 边 个数 ：（-1）-（-3）+1=3
高的边个数 ：7-5+1=3
总个数：533）
5.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a1,1为第一元素，其存储地址为1，每个元素占一个地址空间，则a8,5的地址是______。
A．13
B．33
C．18
D．40
答案：B（这里数组下标从1开始，对称矩阵，只存储其下三角形元素，在a8,5的前面有7行，第1行有1个元素，第2行有2个元素，…，第7行有7个元素，这7行共有(1+7)×7/2=28个元素，在第8行中，a8,5的前面有4个元素，所以，a8,5前有28+4=32个元素，其地址为33。）
6.数组A[0…5,0…6]的每个元素占5个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是
答案：1175（这类题目分为两类：行优先和列优先（假设数组为Ａ［ｎ］［ｍ］，数组下标从0开始）
1.行优先：基址＋（行数）∗ *∗ ｍ＋列数）×每个元素所占内存单位
2.列优先：基址＋（列数 ∗ *∗ n＋行数）×每个元素所占内存单位，即1000＋（５×６＋5）×5＝1175）
7.广义表((a,b,c,d))的表头和表尾分别是什么?
显然,广义表((a,b,c,d))中只有1个元素,
即(a,b,c,d)
表头是(a,b,c,d),一个子表
表尾是空表()长度为0
8.设广义表L= ((a, b，c))， 则L的长度和深度分别是（）
A.1和1
B.1和3
C.1和2
D.2和3
答案：C
只有一个元素长度是1.唯一的元素里嵌套一层，所以深度是2
9.下面的说法不正确的是（ ）。
A.广义表的表头总是一个广义表
B.广义表的表尾总是一个广义表
C.广义表难以用顺序存储结构
D.广义表可以是一个多层次的结构
答案：A
第5章-树和二叉树
了解树和二叉树（满二叉树、完全二叉树）的基本概念、术语和性质。
- 根节点、父节点、前驱节点、孩子节点
- 同一个
父节点下相邻的两个孩子节点：兄弟节点、姊妹节点 - 最外层的绿色部分：
叶子节点 - 深度指的是最长的线有几个节点，最长的线有 3 个节点，深度是 3(相当于层数)
- 广度指的是某个节点有几根线出去，F节点有2根线出去，广度是 2
- 一般叶子节点为
空，广度为0 - 无向二叉树，只考虑线即可，不考虑入度，出度
- 在二叉树的第
i层上至多有2^i-1^个结点(i>=1) - 深度为
k的二叉树至多有2^k^-1个结点(k>=1)
二叉树的5种形态：
- 结构体指针赋值为空 - - -
空的二叉树 - 只有
根节点的二叉树 - 只有
左子树的二叉树 - - - 只有左边一支的二叉树 - 只有
右子树的二叉树 - - - 只有右边一支的二叉树 左右子树都齐全的二叉树 - - - 完全二叉树、满二叉树
满二叉树：
- 所有节点当中，只有广度为
0和2的二叉树，所有叶子节点都在同一层上面 - 节点关系用
等比数列求和去求，知道深度(第几层)求最多节点数（指的是深度为k且含有2^k^-1个结点的二叉树） - 3 个节点 2 条边，
n个节点有 n -1 条边 - 特点：每一层上的结点数都是
最大结点数
完全二叉树：
- 最后一个节点之前的所有节点都是
连续性的
二叉树的先序、中序、后序和层次遍历算法
.png)
3个顶点，有6种打印方式，一般只研究从左到右(3种)
根据 根所在的位置 确定使用何种打印方式，根在前面：前(先)序遍历；根在中间：中序遍历；根在后面：后序遍历
前序遍历：根在前面，根左右
中序遍历：左根右
后序遍历：根在后面，左右根
从上往下，3 个 3 个节点遍历，A节点遍历完了(A节点完整遍历后)，ABC，再遍历B节点(B节点也需要完整遍历)，把B用BDE替换，空可以不用写，遍历完左子树后，遍历右子树
层次遍历：通过队列实现，一层一层去遍历，A ----> B、C ----> D、E、F ----> G、H
根据两个顺序遍历的结果还原二叉树：
- 根据前、中序遍历的结果还原二叉树，根据中、后序遍历的结果还原二叉树
- 后序遍历，最后一个节点一定是根节点；前序遍历，第一个节点一定是根节点；在中序遍历中找根，根左边是左子树，根右边是右子树，C在中序遍历的右边，放在右边，中序遍历的H在二叉树中的位置结合后序遍历分析，知道在C的左边还是右边
二叉树的顺序存储
- 二叉树的顺序存储表示是用一组连续存储空间（一维数组）依次
从上到下，从左到右存储完全二叉树中的所有结点，即完全二叉树编号为i的结点存到一维数组的下标为i的位置上。 - 若该二叉树为
非完全二叉树，则必须将相应位置空出来或用0补充，使存放的结果符合完全二叉树形态。
二叉树的链式存储-二叉链表
- 在
n个结点的二叉链表中，有n+1个空指针域，无连接时有2n个，但每个除根都需再向上连接一次
森林转换为二叉树
习题
1.完全二叉树一定存在度为1的结点。
答案： ×（满二叉树也是完全二叉树，其叶子结点的度为0。）
2.哈夫曼树的结点个数不能是偶数
答案： √（假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。）
3.树形结构中元素之间存在一个对多个的关系。
答案： √（树形结构元素之间存在一对多的关系，线性结构元素之间存在一对一的关系，图形结构元素之间存在多对多的关系。）
4.用一维数组存储二叉树时,总是以前序遍历顺序存储结点
答案： ×（总是以层次遍历的顺序存储，并且按照完全二叉树的方式建立，所以有很多空节点，会浪费存储空间，完全二叉树可以非常方便地找到孩子兄弟和双亲）
5.若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的前序序列中的最后一个结点。
答案：√
6.以下说法错误的是 ( )
A哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
B若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
C已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
D在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。
答案： D
7.给定一棵树，可以找到唯一的一棵二叉树与之对应。
答案： √
8.二叉树是一种特殊的树。
答案： ×
9.二叉树的遍历只是为了在应用中找到一种线性次序。
答案： √
10.完全二叉树中,若一个结点没有左孩子,则它必是树叶()
答案： √
11.已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为?
A.CBEFDA
B.FEDCBA
C.CBEDFA
D.不定
答案： A（先序遍历ABCDEF可知A为根节点，然后中序遍历CBAEDF可知CB为A的左子树，EDF为A的右子树，对于左子树，先序遍历为BC，可知B为根节点，中序遍历为CB，C为其左子树，右子树分析一样。）
8.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( )。
A．9
B．11
C．15
D．不确定
答案：B（对任何一棵二叉树，如果终端结点数为n0，度为2的结点数为n2，则一定有n0=n2+1。所以n0=10+1=11，而与n1无关。）
13.一棵二叉树的高度为h，所有结点的度为0，或为2，则此树最少有( )个结点
2h-1
2h+1
h+1
答案： B
第6章-图
图的基本概念
图（graph）并不是指图形图像（image）或地图（map）。通常来说，我们会把图视为一种由“顶点”组成的抽象网络，网络中的各顶点可以通过“边”实现彼此的连接，表示两顶点有关联。注意上面图定义中的两个关键字，由此得到我们最基础最基本的2个概念， 顶点（vertex）和 边（edge）。
如上图所示，节点（vertex）用 红色 标出，通过 黑色的边（edge）连接。
-
度：与结点关联的边数，在有向图中为入度与出度之和。
① 出度：在有向图中以这个结点为起点的有向边的数目。(可形象的理解为离开这个结点的边的数目)
② 入度：在有向图中以这个结点为终点的有向边的数目。(可形象的理解为进入/指向这个结点的边的数目)
注：任意一个图的总度数等于其边数的 2倍
- 连通：如果在同一无向图中两个结点存在一条路径相连，则称这两个结点连通。
- 连通图：如果无向图中任意两个结点都是连通的，则称之为连通图。
- 强连通/强连通图：如果有向图中任意两个结点之间存在两条路径(即(i,j)两点中，既从i到j有一条路径，j到i也有一条路径)，则两点是强连通的。当一个图中任意两点间都是强连通的，则该图称之为强连通图。
注：在强连通图中，必定有一条回路经过所有顶点。
- 强连通分量：非强连通图有向图中的最大子强连通图。
- 回路：起点与相同的路径，又叫“环”。
- 完全图：任意两点间都存在边使其相连的无向图或任意两点间都存在两条不同边的有向图称作完全图
- N个顶点的完全图：① 有向 有
n(n-1)条边
② 无向 有n(n-1)/2条边
图的三种存储结构
邻接矩阵表示法
所谓邻接矩阵存储结构就每个顶点用一个一维数组存储边的信息，这样所有点合起来就是用矩阵表示图中各顶点之间的邻接关系。所谓矩阵其实就是二维数组。
int g[N][N];
int main() {
int n, m; //n个点 m条边
scanf("%d%d", &n, &m);
int u, v; //从u到v
for (int i = 0; i < m; ++i) {
scanf("%d%d", &u, &v);
g[u][v] = 1;
//g[v][u] = 1;//无向图要建双边
//g[u][v] = w; //带权图
}
}邻接表（链式）表示法
# include<bits/stdc++.h>
using namespace std;
# define debug(x) cout<<"# "<<x<<" "<<endl;
typedef long long ll;
const ll mod=2147483647;
const ll N=1e4+7;
vector<ll>G[N];//graph
/*
如果边上有属性（带权图）
struct edge
{
ll to,cost;
};
vector<edge>G[N];
*/
int main()
{
ll V,E;//V个顶点和E条边
scanf("%lld %lld",&V,&E);
for(int i=0;i<E;++i)
{
ll s,t;//从s到t
scanf("%lld %lld",&s,&t);
G[s].push_back(t);
}
/*
**********各种对图的操作
*/
return 0;
}图的遍历
搜索引擎的两种基本抓取策略 —深度优先/广度优先（两种策略结合=先广后深 +权重优先）
先把这个页面所有的链接都抓取一次再根据这些URL的权重来判定URL的权重高，就采用深度优先，URL权重低，就采用宽度优先或者不抓取 。
-
时间戳：按照上述的深度优先遍历的过程，以每一个结点第一次被访问的顺序，依次赋值1~N的整数标记，该标记就被称为时间戳。标记了每一个结点的访问顺序。
-
树的DFS：一般来说，我们在对树的进行深度优先时，对于每个节点，在刚进入递归时和回溯前各记录一次该点的编号，最后会产生一个长度为2N的序列，就成为该树的DFS序。
-
dfs序可以把一棵树区间化，即可以求出每个节点的管辖区间。对于一棵树的dfs序而言，同一棵子树所对应的一定是dfs序中连续的一段。
-
DFS算法效率分析：用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O ( n^2^ ) ；用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O ( n + e )
-
结论：
稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。
-
广度优先遍历是一种按照层次顺序访问的方法。它具有两个重要的性质：
- 在访问完所有的第i层结点后，才会访问第i+1层结点。
- 任意时刻，队列中只会有两个层次的结点，满足“两段性”和“单调性”。
-
BFS算法效率分析：如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O ( n^2^ )；用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O ( n + e )
-
最小生成树：
极小连通子图：该子图是G 的连通子图，在该子图中删除任何一条边，子图不再连通。生成树：包含图G所有顶点的极小连通子图（n-1条边）
首先明确：
- 使用不同的遍历图的方法，可以得到不同的生成树
- 从不同的顶点出发，也可能得到不同的生成树。
- 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。
目标：
在网的多个生成树中，寻找一个各边权值之和最小的生成树。
K r u s k a l 算法可以简单理解为按边贪心。
P r i m 算法是以更新过的节点的连边找最小值
Prim算法适用于稠密图；Kruskal适用于稀疏图
习题
1.下面（ ）方法可以判断出一个有向图是否有环。 (2分)
A.深度优先遍历
B.拓扑排序
C.求最短路径
D.求关键路径
答案： B
对于有向图的拓扑排序：
- 计算图中所有点的入度，把入度为0的点加入栈
- 如果栈非空：取出栈顶顶点a，输出该顶点值，删除该顶点
- 从图中删除所有以a为起始点的边，如果删除的边的另一个顶点入度为0，则把它入栈
- 如果图中还存在顶点，则表示图中存在环否则输出的顶点就是一个拓扑排序序列
2.在图采用邻接表存储时,求最小生成树的Prim算法的时间复杂度为()
A.O ( n )
B.O ( n + e )
C.O ( n ^2^ )
D.O ( n ^3^ )
3.图中有关路径的定义是
A.由顶点和相邻顶点序偶构成的边所形成的序列
B.由不同顶点所形成的序列
C.由不同边所形成的序列
D.上述定义都不是
答案： A
A（正确）. 序偶：两个具有固定次序的客体组成一个序偶。由顶点和相邻顶点序偶构成的边的序列-----一条边对应两个端点，每条边的两个端点之间都有序偶关系----则一系列边的序列，构成有次序关系的一系列顶点的序列-----路径的定义：一个vp vi1 vi2 … vq的顶点序列就是一条路径。 所以很清楚了，A的确能反映路径。
B. 路径分为简单路径和复杂路径，该选项只是简单路径的性质。
C. 这一系列的边之间是否有连接关系？如果只是很多不相连的线段呢？
4.若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。
A．非连通 B．连通 C．强连通 D．有向
答案： B（即从该无向图任意一个顶点出发有到各个顶点的路径，所以该无向图是连通图。强连通图是指的所有的点都连通。）
5.n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。
A．n B．2(n-1) C．n/2 D．n2
答案： B
6.关键路径是事件结点网络中（ ）。 (2分)
A.从源点到汇点的最长路径
B.从源点到汇点的最短路径
C.最长回路
D.最短回路
答案： A（关键路径在实际应用中被当做“参考路径”，即deadline 长度最长的路径）
7.下列关于AOE网的叙述中，不正确的是（ ）。
A.所有的关键活动提前完成，那么整个工程将会提前完成
B.关键活动不按期完成就会影响整个工程的完成时间
C.任何一个关键活动提前完成，那么整个工程将会提前完成
D.某些关键活动提前完成，那么整个工程将会提前完成
答案： C
第7章-排序与查找
基于比较：冒泡 选择 插入 希尔shell- 基于比较，具备
递归特性：分组排序 快排 归并排序 - 不基于比较、利用数组下标天然有序实现的排序算法：基数排序 计数排序
- 桶(箱)排序
- 基于
堆结构：堆排序
打印函数
# include "iostream"
using namespace std;
# define NUM 10
//排序前 排序后
void print_af(int* arr,int len,bool isAfter=false)
{
if(isAfter)
{
cout<<"after sort:";
}
else
{
cout<<"before sort:";
}
for(int i=0;i<len;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}
int main()
{
int arr[NUM]={5,6,1,0,22,888,-1,-5,1,6};
print_af(arr,NUM);
print_af(arr,NUM,true);
while(1);
return 0;
}冒泡排序
- 每一次冒出一个最大的
[升序]，或者每一次冒出一个最小的[降序] 冒泡：每次冒出一个最大的 数据个数为n，要冒n-1次：10个数据，冒9个出来，只剩一个，数据自然有序改良：可以加个count记录一下是否已经排好，排好序则直接退出，不需要一定要循环n-1次
void bubble_sort(int* arr,int len)
{
int count=1;//判断是否已经排序好
//一共要冒n-1次
for(int i=0;i<len-1;i++)
{
count=0;
for(int j=0;j<len-1-i;j++)
{
if(arr[j]>arr[j+1])
{
int temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
count=1;
}
}
if(count==0)//如果已经是排好则不需要再执行后面直接退出
break;
print_af(arr,len);
}
}
//测试
before sort:5 6 1 0 22 888 -1 -5 1 6
before sort:5 1 0 6 22 -1 -5 1 6 888
before sort:1 0 5 6 -1 -5 1 6 22 888
before sort:0 1 5 -1 -5 1 6 6 22 888
before sort:0 1 -1 -5 1 5 6 6 22 888
before sort:0 -1 -5 1 1 5 6 6 22 888
before sort:-1 -5 0 1 1 5 6 6 22 888
before sort:-5 -1 0 1 1 5 6 6 22 888
after sort:-5 -1 0 1 1 5 6 6 22 888选择排序
选择：每次从待排数组中挑出最小的摆放到应当摆放的位置 需要n-1 次，相对于冒泡的优化：冒泡每次冒一个最大的，中间存在交换；选择是每次挑出来一个最小的，但只是过一遍，记录最小的在哪里，只要交换1次
10个数据，选9个出来，只剩一个，数据自然有序
void select_sort(int* arr,int len)
{
int temp,minIndex;
for(int i=0;i<len-1;i++)
{
temp=arr[i];
minIndex=i;
for(int j=i;j<len;j++)
{
minIndex=((arr[j]>arr[minIndex])?minIndex:j);//如果后面的值有比设置的最小值小那么最小值就是后面的值否则最小值保持不变
}
if(arr[minIndex]<temp)
{
arr[i]=arr[minIndex];
arr[minIndex]=temp;
}
print_af(arr,len);
}
}
//测试
before sort:-5 6 1 0 22 888 -1 5 1 6
before sort:-5 -1 1 0 22 888 6 5 1 6
before sort:-5 -1 0 1 22 888 6 5 1 6
before sort:-5 -1 0 1 22 888 6 5 1 6
before sort:-5 -1 0 1 1 888 6 5 22 6
before sort:-5 -1 0 1 1 5 6 888 22 6
before sort:-5 -1 0 1 1 5 6 888 22 6
before sort:-5 -1 0 1 1 5 6 6 22 888
before sort:-5 -1 0 1 1 5 6 6 22 888
after sort:-5 -1 0 1 1 5 6 6 22 888插入排序
插入：每次把待排数组中第一个插入到已序数组中
选择排序需要找完才能找到 最小的，插入排序则不需要，可能 中途就搞定了 [ 根据数据的不同 ]
void insert_sort(int* arr,int len)
{
int temp;
for(int i=1;i<len;i++)
{
temp=arr[i];//当前第0个元素i=5
if(arr[i]<arr[i-1])//如果右边的元素小于左边
{
for(int j=i-1;j>=0&&arr[j]>temp;j--)//在之前排好的地方遍历
{
//找到了开始交换
arr[j+1]=arr[j];
arr[j]=temp;
}
}
print_af(arr,len);
}
}
//测试
before sort:5 6 1 0 22 888 -1 -5 1 6
before sort:5 6 1 0 22 888 -1 -5 1 6
before sort:1 5 6 0 22 888 -1 -5 1 6
before sort:0 1 5 6 22 888 -1 -5 1 6
before sort:0 1 5 6 22 888 -1 -5 1 6
before sort:0 1 5 6 22 888 -1 -5 1 6
before sort:-1 0 1 5 6 22 888 -5 1 6
before sort:-5 -1 0 1 5 6 22 888 1 6
before sort:-5 -1 0 1 1 5 6 22 888 6
before sort:-5 -1 0 1 1 5 6 6 22 888
after sort:-5 -1 0 1 1 5 6 6 22 888希尔排序
void shell_sort(int* arr,int len)
{
//每轮步长都是上次步长的一半
//下面拿原数组举例第一轮时各变量的值
for(int gap=len/2;gap>=1;gap/=2)//5;5>=1;5/=2
{
for(int i=gap;i<len;i++)//5;5<10;5++
{
for(int j=i-gap;j>=0;j-=gap)//0=5-5;0>=0;0-=5
{
if(arr[j+gap]<arr[j])//arr[0+5]<arr[0]
{
int temp=arr[j+gap];
arr[j+gap]=arr[j];
arr[j]=temp;
}
}
}
print_af(arr,len);
}
}
//测试
before sort:5 6 1 0 22 888 -1 -5 1 6
before sort:5 -1 -5 0 6 888 6 1 1 22
before sort:-5 -1 1 0 5 1 6 22 6 888
before sort:-5 -1 0 1 1 5 6 6 22 888
after sort:-5 -1 0 1 1 5 6 6 22 888基数排序
数组下标天然有序
最快 没有之一 时间复杂度：O(n)
限制条件很多：
不能有重复
只能操作正整数
注意空间消耗
void radix_sort(int* arr,int len,int max)
{
//定义一个临时数组--->一定是max+1个，利用数组下标天然有序进行排序
int* pTemp=new int[max+1];
for(int i=0;i<max+1;i++)//给临时数组赋值-1
{
pTemp[i]=-1;
}
//把arr数组中元素依序存到pTemp数组中
for(int i=0;i<len;i++)
{
pTemp[arr[i]]=arr[i];//如果数据是1则放到下标为1的位置，如果数据为2放到下标为2位置...
}
//把pTemp数组覆盖回来
int k=0;
for(int i=0;i<max+1;i++)
{
if(pTemp[i]!=-1)
{
arr[k++]=pTemp[i];
}
}
delete[] pTemp;//释放
}
//测试
int arr[NUM]={3,5,1,8,9,44,67,90,776,0};
int max=arr[0];
for(int i=0;i<NUM;i++)
{
max=arr[i]>max?arr[i]:max;
}
radix_sort(arr,NUM,max);
print_af(arr,NUM,true);桶排序
桶排序：根据某种特性 划分为多个箱子 箱子内用其他排序方式排序，最后整体有序
注意：桶排序不能用于负数，但是可以通过排序前数组元素同时+一个数转化为正数再排序，排完序再-一个数恢复之前的数据
效率取决于分类方式：这里用十进制的方式来分桶，十进制的每一个位都是在 0~9 之间，所以可以把数据分成10个桶，考虑极端情况，每个桶的大小和原大小一样
这里采用科学计数法，按位做排序，从个位到十位，从左往右：
5 放在对应十进制为 5 的桶中，5 的下标为 0，对应在桶的下标为 0；
8 放在对应十进制为 8 的桶中，8 的下标为 2，对应在桶的下标为 1；
用下标天然有序的方式排序，提供效率，空间消耗稍微大：如果数据位数多，循环次数也多；
# define NUM 10
# define SIZE 10 //箱子个数
# define AREA 1000 //数据范围
void bucket_sort(int* arr,int len)
{
int count,k;//count用来做循环次数的循环变量->范围0-999 三位十进制整数箱排序需要循环3次
//做箱子
int* pTemp=new int[SIZE*len];//10个箱子：箱子大小和元素个数相同
for(count=1;count<AREA;count*=10)//1 10 100
{
//初始化10个箱子等于-1
for(int i=0;i<SIZE*len;i++)
{
pTemp[i]=-1;
}
//根据当前要排序的位把a数组中的元素放到对应箱子的对应位置->和count相关，第一次个位，第二次十位...
for(int i=0;i<len;i++)
{
pTemp[(arr[i]/count%10)*len+i]=arr[i];
}
//把箱子的数据覆盖回数组中
k=0;
for(int i=0;i<SIZE*len;i++)
{
if(pTemp[i]!=-1)
{
arr[k++]=pTemp[i];
}
}
print_af(arr,NUM);
}
delete[] pTemp;
}
//测试
略快速排序
快速排序：分组排序 无限分组，在分组的过程中，保证分成的两个组是有序的，左边的每一个元素都比右边的每一个元素要小，组分完后，整个数组就有序了
用 两个指针 实现左右两边有序，如果规定最左边的数据为临时数据，先挪 R，如果规定最右边的数据为临时数据，先挪 L：让两个指针按图中的方式移动，在移动的过程中调整位置，保证两个指针在同一个位置的时候，左边的每一个元素都比右边的每一个元素小
不采用交换而是采用 覆盖 的方式，可以提高效率
void quick_sort(int* arr,int left,int right)
{
if(left>=right)//（0>=9）不成立
return;
//假设arr[left]是中间数据（基数）
int temp=arr[left];//（5）
int L=left;//左（0）
int R=right;//右（9）
//循环让L和R重合
while(L<R)//当L==R代表已经重合了
{
//先移R
//大于基数的放右边小于放左边
while(L<R&&arr[R]>=temp)
{
R--;//大于基数只需移动R即可
}
arr[L]=arr[R];//当找到一个比基数小则覆盖过去
//再移L
while(L<R&&arr[L]<temp)
{
L++;//小于基数只需移动L即可
}
arr[R]=arr[L];//当找到一个比基数大则覆盖过去
}
arr[L]=temp;//覆盖完成后把temp覆盖回来
print_af(arr,NUM);
printf("123\n");
//继续拆
quick_sort(arr,left,L-1);
quick_sort(arr,L+1,right);
}
//测试
before sort:5 6 1 0 22 888 -1 -5 1 6
before sort:1 -5 1 0 -1 5 888 22 6 6
before sort:-1 -5 0 1 1 5 888 22 6 6
before sort:-5 -1 0 1 1 5 888 22 6 6
before sort:-5 -1 0 1 1 5 6 22 6 888
before sort:-5 -1 0 1 1 5 6 22 6 888
before sort:-5 -1 0 1 1 5 6 6 22 888
after sort:-5 -1 0 1 1 5 6 6 22 888归并排序
有序的两个数组合并成一个有序数组 一开始只负责拆，拆到只有一个元素后，自然就有序了，有序后，把有序的两个数组合并成一个有序数组
二分查找
在 有序序列(二叉树、数组、链表 . . .)中，二分查找的前提是有序，如果无序没办法分而治之
效率较高，每次可以排除掉一半
在 1 ~ 100 中找 1个数，先找 50
要找的数如果 > 50，取大的一半
要找的数如果 < 50，取小的一半
直接找下标为一半的位置 - - - 元素个数 / 2
int halfFind(int* arr,int len,const int& findData)//（arr,10,6）
{
int m;//中间的下标
int left=0;//左边下标
int right=len-1;//右边下标（9）
while(1)
{
//把中间的下标算出来
m=left+(right-left)/2;//（0+(9-0)）/2=4
if(findData==arr[m])//判断是否找到（6==5，不成立）
{
return m;//找到了 返回
}
else
{
//没找到 修改left和right的值 继续循环
if(findData>arr[m])//如果要找的的值比中间数据大（6>5）
{
left=m+1;//排除掉左边->右边下标保持不变，左边下标修改为m+1(即左边下标变成中间下标+1)
}
else//如果要找的值比中间数据小
{
right=m-1;//排除掉右边->左边下标保持不变，右边下标修改为m-1
}
}
if(left>right)
break;//找不到直接退出
}
return -1;
}
int main()
{
int num,ret;
int arr[NUM]={1,2,3,4,5,6,7,8,9,10};//有序的！
cout<<"请输入要找的元素：";
cin>>num;
ret=halfFind(arr,NUM,num);
if(ret==-1)
{
printf("没找到！\n");
}
else
{
printf("找到了，数据：%d 的下标为[%d]",arr[ret],ret);
}
while(1);
return 0;
}
//测试
请输入要找的元素：10
找到了，数据：10 的下标为[9]最大值/最小值
普通方式找最大/最小值
void searchMaxMin(int* arr,int len,int* maxIndex,int* minIndex)
{
//假设第一个元素是最大值也是最小值
int max=arr[0];
int min=arr[0];
//最大值和最小值的下标都为0
*maxIndex=0;
*minIndex=0;
//从第二个开始找
for(int i=1;i<len;i++)
{
//如果当前元素>max，那么当前元素就是max
if(arr[i]>max)
{
max=arr[i];
*maxIndex=i;
}
//同理，最小值也是这样
if(arr[i]<min)
{
min=arr[i];
*minIndex=i;
}
}
}
int main()
{
int arr[NUM]={1,2,3,4,5,6,7,8,9,10};
int maxIndex=-1;//最大值下标
int minIndex=-1;//最小值下标
searchMaxMin(arr,NUM,&maxIndex,&minIndex);
printf("最大值是:%d,下标是[%d]，最小值是%d,下标是[%d]\n",arr[maxIndex],maxIndex,arr[minIndex],minIndex);
while(1);
return 0;
}
//测试
最大值是:10,下标是[9]，最小值是1,下标是[0]分而治之的方式找最大值和最小值
每两个元素比较出最大值和最小值，把比较出的最大值、最小值和 前一组的最大值、最小值去比较
会出现元素总个数为奇数的情况需要处理
void searchMaxMin2(int* arr,int len,int* maxIndex,int* minIndex)
{
//只有一个元素，最大值/最小值都是它
if(len==1)
{
*maxIndex=*minIndex=0;
}
//解决数组元素个数奇偶问题
int n=1;
//奇数
if(len%2==1)
{
//第一个元素自己一组
*maxIndex=*minIndex=0;
}
else//偶数
{
//两个元素一组->直接把第0个元素和第1个元素拿出来比较找出最大值和最小值
if(arr[0]>arr[1])
{
*maxIndex=0;
*minIndex=1;
}
else
{
*maxIndex=1;
*minIndex=0;
}
//偶数下一组从2开始
n=2;
}
//每次比较一组(两个)元素
for(int i=n;i<len;i+=2)
{
//一组的左边和右边比较出当前最大值和最小值
if(arr[i]>arr[i+1])
{
if(arr[i]>arr[*maxIndex])//把当前组的最大值和上一组的最大值比
{
*maxIndex=i;//如果比上一组的最大值大就改变最大值
}
if(arr[i+1]<arr[*minIndex])//把当前组最小值和上一组的最小值比
{
*minIndex=i+1;//同理改变最小值
}
}
else
{
if(arr[i+1]>arr[*maxIndex])
{
*maxIndex=i+1;
}
if(arr[i]<arr[*minIndex])
{
*minIndex=i;
}
}
}
}
int main()
{
int arr[NUM]={1,2,3,4,5,6,7,8,9,10};
int maxIndex=-1;//最大值下标
int minIndex=-1;//最小值下标
searchMaxMin2(arr,NUM,&maxIndex,&minIndex);
printf("最大值是:%d,下标是[%d]，最小值是%d,下标是[%d]\n",arr[maxIndex],maxIndex,arr[minIndex],minIndex);
return 0;
}
//测试
最大值是:10,下标是[9]，最小值是1,下标是[0]习题
（1）从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。
A．归并排序 B．冒泡排序 C．插入排序 D．选择排序
答案： C
（2）从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（ ）。
A．归并排序 B．冒泡排序 C．插入排序 D．选择排序
答案： D
（3）对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。
A．从小到大排列好的 B．从大到小排列好的
C．元素无序 D．元素基本有序
答案： B
解释：对关键字进行冒泡排序，关键字逆序时比较次数最多。
（4）对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（ ）。
A．n+1 B．n C．n-1 D．n(n-1)/2
答案： D
解释：比较次数最多时，第一次比较n-1次，第二次比较n-2次……最后一次比较1次，即(n-1)+(n-2)+…+1= n(n-1)/2。
（5）快速排序在下列（ ）情况下最易发挥其长处。
A．被排序的数据中含有多个相同排序码
B．被排序的数据已基本有序
C．被排序的数据完全无序
D．被排序的数据中的最大值和最小值相差悬殊
答案： C
解释：B选项是快速排序的最坏情况。
（6）对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（ ）。
A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)
答案： B
解释：快速排序的平均时间复杂度为O(nlog2n)，但在最坏情况下，即关键字基本排好序的情况下，时间复杂度为O(n2)。
（7）若一组记录的排序码为（46, 79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
A．38，40，46，56，79，84 B．40，38，46，79，56，84
C．40，38，46，56，79，84 D．40，38，46，84，56，79
答案： C
（8）下列关键字序列中，（ ）是堆。
A．16，72，31，23，94，53 B．94，23，31，72，16，53
C．16，53，23，94，31，72 D．16，23，53，31，94，72
答案： D
解释：D选项为小根堆
（9）堆是一种（ ）排序。
A．插入 B．选择 C．交换 D．归并
答案： B
（10）堆的形状是一棵（ ）。
A．二叉排序树 B．满二叉树 C．完全二叉树 D．平衡二叉树
答案： C
（11）若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（ ）。
A．79，46，56，38，40，84 B．84，79，56，38，40，46
C．84，79，56，46，40，38 D．84，56，79，40，46，38
答案： B
（12）下述几种排序方法中，要求内存最大的是（ ）。
A．希尔排序 B．快速排序 C．归并排序 D．堆排序
答案： C
解释：堆排序、希尔排序的空间复杂度为O(1)，快速排序的空间复杂度为O(log2n)，归并排序的空间复杂度为O(n)。
（13）下述几种排序方法中，（ ）是稳定的排序方法。
A．希尔排序 B．快速排序 C．归并排序 D．堆排序
答案： C
解释：不稳定排序有希尔排序、简单选择排序、快速排序、堆排序；稳定排序有直接插入排序、折半插入排序、冒泡排序、归并排序、基数排序。
（14）数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( )算法最节省时间。
A．冒泡排序 B．快速排序 C．简单选择排序 D．堆排序
答案： D
（15）下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A．希尔排序 B．快速排序 C．冒泡排序 D．堆排序
答案：A
解释：快速排序的每趟排序能将作为枢轴的元素放到最终位置；冒泡排序的每趟排序能将最大或最小的元素放到最终位置；堆排序的每趟排序能将最大或最小的元素放到最终位置。