二叉树性质
- 在非空二叉树的第i层上，至多有2(i - 1)个结点(i>=1)
#include <math.h> //注意引入头文件
printf("请输入层数:");
int i;
scanf("%d", &i);
printf("第%d层最多有%d个结点", i, pow(2, i - 1));
- 在深度为K的二叉树上最多有2k -1 个结点（k>=1)
printf("请输入层数:");
int k;
scanf("%d", &k);
printf("前%d层最多有%d个结点", k, pow(2, k) - 1);
- 在任意一棵二叉树中，叶子结点的数目比度数为2的结点的数目多1，
n0 = n2 + 1
printf("请输入度为1的结点个数，及度为2的结点个数统计总结点个数:");
int n0; //度为0的结点个数
int n1; //度为1的结点个数
int n2; //度为2的结点个数
scanf("%d %d", &n1, &n2);
n0 = n2 + 1; //叶子结点的数目比度数为2的结点的数目多1
printf("总的结点个数是%d\n", n0 + n1 + n2);
- 具有n个结点的完全二叉树的深度为 【log2n】 + 1
printf("请输入完全二叉树的结点个数");
int n;
scanf("%d", &n);
printf("具有%d个结点的完全二叉树的深度为%d", n, (int)log2(n) + 1)
二叉树创建
结点类型为字符型
typedef struct node {
char data; //数据
node *left; //左孩子指针
node *right; //右孩子指针
}node;
//定义创建函数
node* create()
{
printf("请输入结点的值");
char ch;
scanf("%c", &ch);
//注意:如果考试过程中一次性录入所有结点的值（包括#)则不需要吸收回车
//否则如果是一个结点一个结点的录入则选哟吸收
getchar(); //吸收回车
if (ch == '#') //如果输入的#表示为空
{
return NULL;
}
//1.创建根结点
node *root = (node*) malloc(sizeof(node));
if (root == NULL)
{
return NULL;
}
//创建根结点，或者(node*) malloc(100));
root->data = ch; //给根结点赋值
root->left = create(); //递归创建左子树
root->right = create(); //递归创建右子树
return root; //返回根结点
}
结点类型为整型的情况
typedef struct node {
int data; //数据
node *left; //左孩子指针
node *right; //右孩子指针
}node;
//定义创建函数
node* create()
{
printf("请输入结点的值");
int ch;
scanf("%d", &ch);
if (ch == -1) //如果输入的-1表示为空
{
return NULL;
}
//1.创建根结点
node *root = (node*) malloc(sizeof(node));
if (root == NULL)
{
return NULL;
}
//创建根结点，或者(node*) malloc(100));
root->data = ch; //给根结点赋值
root->left = create(); //递归创建左子树
root->right = create(); //递归创建右子树
return root; //返回根结点
}
结点类型为字符串的情况
typedef struct node {
char data[100]; //数据
node *left; //左孩子指针
node *right; //右孩子指针
}node;
//定义创建函数
node* create()
{
printf("请输入结点的值"); //如果考试的时候只出现了一次则放在主函数里面
char str[100];
scanf("%s", str);
if (strcmp(str, "#") == 0) //如果输入的#表示为空
{
return NULL;
}
//1.创建根结点
node *root = (node*) malloc(sizeof(node));
if (root == NULL)
{
return NULL;
}
//创建根结点，或者(node*) malloc(100));
strcpy(root->data, str); //给根结点赋值(必须使用函数的形式)
root->left = create(); //递归创建左子树
root->right = create(); //递归创建右子树
return root; //返回根结点
}
如何调用
//第一种情况:在菜单外面初始化
node *root = create();
//第二种情况
//在case里面初始化
node *root; //这句话放在while(1)的外面
//在case里面吧执行
root = create();
二叉树的遍历
- 先序遍历(先根，再左子树，再右子树)
void preOrder(node *root) //
{
if (root != NULL)
{
printf("%c\t", root->data); //如果是字符串类型则%c改为%s
preOrder(root->left); //递归遍历左子树
preOrder(root->right); //递归遍历右子树
}
}
//调用形式
preOrder(root);
-
中序遍历(先左子树，再根，再右子树)
void inOrder(node *root) { if (root != NULL) { inOrder(root->left); //递归访问左子树 printf("%c\t", root->data); //如果是字符串类型则%c改为%s inOrder(root->right); //递归访问右子树 } } //调用形式 inOrder(root); -
后序遍历(先左子树，再右子树，再根)
void postOrder(node *root) { if (root != NULL) { postOrder(root->left); //递归访问左子树 postOrder(root->right); //递归访问右子树 printf("%c\t", root->data); //如果是字符串类型则%c改为%s } } //调用形式 postOrder(root);判断两棵二叉树是否相同
判断两棵二叉树是否为空，如果都是空则表明相同
如果有一颗为空，另外一颗不为空则表明不相同
-
如果都不为空，则判断根是否相同，如果相同继续判断左子树和右子树是否都相同,如果都相同的情况下则表明两棵二叉树是相同的
//判断两棵二叉树是否相同，如果相同返回1，否则返回0 int isSame(node *root1, node *root2) { if (root1 == NULL && root2 == NULL) { return 1; } else if(root1 == NULL || root2 == NULL) { return 0; //如果有一颗为空，另外一颗不为空则表明不相同 } else //两棵树都不为空 { if (root1->data == root2->data) //比较两棵树的数据域是否相同 { //如果根相同则还要递归比较左子树和右子树 //只有根和左子树和右子树都相同的情况那么整颗树一定是相等 return isSame(root1->left, root2->left) && isSame(root1->right, root2->right); } else { return 0; //如果对应的根不相等则表示不相同 } } }求二叉树的高度
- 求解出左子树的高度
- 求解出右子树的高度
- 比较左子树和右子树的高度，把较大的一个高度 + 1就是整颗二叉树的高度
//求出二叉树的高度 int gao(node *root) { if (root == NULL) { return 0; //为空的二叉树高度为0 } //把根节点的左指针作为参数，求解出左子树的高度 int h1 = gao(root->left); //把根结点右指针作为参数，求解出右子树的高度 int h2 = gao(root->right); if (h1 > h2) { return h1 + 1; //+1因为要加上根结点这一层 } else { return h2 + 1; } }求解二叉树中叶子结点的个数
- 求出左子树的叶子结点个数
- 求出右子树的叶子结点个数
- 把左子树的叶子结点 + 右子树的结点个数 就是整颗树的结点个数
//统计二叉树中叶子结点的个数 int count(node *root) { if (root == NULL) { return 0; } else if(root->left == NULL && root->right == NULL) { return 1; //如果左子树和右子树同时为空则表明找到一个叶子 } else { //总的叶子结点个数等于左子树的叶子结点个数 + 右子树的叶子结点个数 return count(root->left) + count(root->right); } }求出二叉树中所有结点的个数
- 求出左子树的结点个数
- 求出右子树的结点个数
- 总的结点个数 = 左子树的结点个数 + 右子树的结点个数 + 1
//统计所有结点的个数 int count(node *root) { if (root == NULL) { return 0; //如果根为空返回0 } else { return 1 + count(root->left) + count(root->right); } }统计二叉树中所有度为1的结点个数（只有一个孩子)
int count(node *root) { if (root == NULL) { return 0; } if(root->left != NULL && root->right != NULL) { //如果根节点的左子树和右子树都不为空 //则整颗树中度为1的结点个数 = 左边的 + 右边的 return count(root->left) + count(root->right); } else if(root->left == NULL && root->right == NULL) { //如果左右都为空 return 0; } else //要么左子树树为空，要么右子树为空 { return 1 + count(root->left) + count(root->right); } }
图
#define N 8 //表示图中顶点的个数
typedef struct {
char vertex[N][100]; //存储顶点信息
int edge[N][N]; //存储顶点之间边的关系
}graph; // 定义图形结构体
//初始化图
void init(graph *g)
{
//1.先初始化顶点
for (int i = 0; i < N; i++)
{
strcpy(g->vertex[i], "空");
}
//2.初始化所有的边为0
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
g->edge[i][j] = 0;
}
}
}
//插入顶点(插入顶点和插入边要分开)，不然被扣分
void insertVertex(graph *g)
{
for (int i = 0; i < N; i++)
{
printf("请输入第%d个顶点:", i + 1);
scanf("%s", g->vertex[i]);
}
}
//插入边（单词可以随意)
void insertEdge(graph *g)
{
//插入边要考虑到优化
//1.如果是有向图不能优化，最多优化自生到自身的边
//2.如果是无向图可以优化
//无任何优化的版本(即没有优化自身到自身，也没有实现对称的性质)
//下面的三个循环用一个就行了，别全干上去好吧，看效果图到底用哪个
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
printf("若顶点%s到顶点%s之间存在边则输入1,否则输入0:", g->vertex[i], g->vertex[j]);
scanf("%d", &g->edge[i][j]);
}
}
//只过滤自身结点到自身结点的边(过滤对角线的输入)
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (i != j)
{
printf("若顶点%s到顶点%s之间存在边则输入1,否则输入0:", g->vertex[i], g->vertex[j]);
scanf("%d", &g->edge[i][j]);
}
}
}
//全部优化（包括对角线及对称赋值)
for (int i = 0; i < N - 1; i++)
{
for (int j = i + 1; j < N; j++)
{
printf("若顶点%s到顶点%s之间存在边则输入1,否则输入0:", g->vertex[i], g->vertex[j]);
scanf("%d", &g->edge[i][j]);
g->edge[j][i] = g->edge[i][j]; //对称赋值
}
}
}
//打印图的邻接矩阵
void output(graph *g)
{
//打印顶点元素
printf("顶点元素如下:\n");
for (int i = 0; i < N; i++)
{
printf("%s\t", g->vertex[i]);
}
printf("\n");
printf("边矩阵如下:\n");
for (int i = 0; i < N; i++)
{
printf("\t%s", g->vertex[i]);
}
printf("\n");
for (int i = 0; i < N; i++)
{
printf("%s\t", g->vertex[i]);
for (int j = 0; j < N; j++)
{
printf("%d\t", g->edge[i][j]);
}
printf("\n");
}
}
//如何调用图
int main()
{
graph g;
init(&g); //初始化图
insertVertex(&g); //插入顶点
insertEdge(&g); //插入边
output(&g); //打印图
}
计算图中每个顶点的入度(对应粉丝量)
//注意：入度计算邻接矩阵，对应顶点的列之和
void count(graph *g)
{
for (int i = 0; i < N; i++)
{
int sum = 0; //统计入度(统计列之和)
for (int j = 0; j < N; j++)
{
sum = sum + g->edge[j][i]; //按照列遍历二维数组
}
printf("顶点%s的入度是%d\n", g->vertex[i], sum);
//printf("用户%s的粉丝量是%d\n", g->vertex[i], sum);
}
}
计算图中每个顶点的出(对应关注量)
//注意：入度计算邻接矩阵，对应顶点的列之和
void count(graph *g)
{
for (int i = 0; i < N; i++)
{
int sum = 0; //统计出度(统计行之和)
for (int j = 0; j < N; j++)
{
sum = sum + g->edge[i][j]; //按照行遍历二维数组
}
printf("顶点%s的出度是%d\n", g->vertex[i], sum);
//printf("用户%s的关注量是%d\n", g->vertex[i], sum);
}
}
同时统计出每个顶点的入度和出度（粉丝量和关注量)
void count(graph *g)
{
for (int i = 0; i < N; i++)
{
int sum1 = 0; //统计入度
int sum2 = 0; //统计出度
for (int j = 0; j < N; j++)
{
sum1 = sum1 + g->edge[j][i];
sum2 = sum2 + g->edge[i][j]
}
printf("顶点%s的入度是%d\n", g->vertex[i], sum1);
printf("顶点%s的出度是%d\n", g->vertex[i], sum2);
printf("顶点%s的度是%d\n", g->vertex[i], sum1 + sum2); //度=入度+出度
}
}
求出图中度最大值顶点信息
void max(graph *g)
{
//假设第一个顶点的度最大
int max = 0;
int maxi = 0; //记录最大值的下标
for (int i = 0; i < N; i++)
{
max = max + g->edge[0][i] + g->edge[i][0]; //求出第一行和最后一个行
}
for (int i = 0; i < N; i++)
{
int sum = 0; //记录顶点vertex[i]的度（入度和出度)
for (int j = 0; j < N; j++)
{
sum = sum + g->edge[i][j] + g->edge[j][i]; //统计第i行和第i列之和
}
if (sum > max) //求最大值
{
max = sum; //更新最大值
maxi = i; //更新最大值的下标
}
}
printf("度值最大值顶点是%s,他的度是是%d\n", g->vertex[maxi], max);
}
求出图中入度最大的顶点(求出粉丝量多的用户)
void max(graph *g)
{
//假设第一个顶点的入度最大值
int max = 0;
int maxi = 0; //记录最大值的下标
for (int i = 0; i < N; i++)
{
max = max + g->edge[i][0]; //求出第一行和最后一个行
}
for (int i = 0; i < N; i++)
{
int sum = 0;
for (int j = 0; j < N; j++)
{
sum = sum + g->edge[j][i];
}
if (sum > max) //求最大值
{
max = sum; //更新最大值
maxi = i; //更新最大值的下标
}
}
printf("入度值最大值顶点是%s,他的入度是是%d\n", g->vertex[maxi], max);
printf("用户%s的粉丝量最多,他的粉丝量为%d\n", g->vertex[maxi], max);
}
求出图中出度最大的顶点(求出关注量多的用户)
void max(graph *g)
{
//假设第一个顶点的入度最大值
int max = 0;
int maxi = 0; //记录最大值的下标
for (int i = 0; i < N; i++)
{
max = max + g->edge[0][i]; //求出第一行和最后一个行
}
for (int i = 0; i < N; i++)
{
int sum = 0;
for (int j = 0; j < N; j++)
{
sum = sum + g->edge[i][j];
}
if (sum > max) //求最大值
{
max = sum; //更新最大值
maxi = i; //更新最大值的下标
}
}
printf("出度值最大值顶点是%s,他的出度是是%d\n", g->vertex[maxi], max);
printf("用户%s的关注量最多,他的关注量为%d\n", g->vertex[maxi], max);
}
深度优先搜索代码
int v[N]; //默认是0，记录每个顶点是否被访问过的状态
void dfs(graph *g, int start) //start为起始顶点的下标
{
printf("%s\t", g->vertex[start]); //打印下表为start的顶点
v[start] = 1; //表示Vi被访问过了
//下一步，找vi未被访问过的邻接点作为起始点，注意邻接点一定位于start下标这一行
for (int i = 0; i < N; i++)
{
if (g->edge[start][i] == 1 && v[i] == 0)
{
dfs(g, i); //把i下标作为新的起始点出发深度优先搜索
}
}
}
打印图的所有路径
//定义栈
typedef struct {
char data[N][100]; //存放N个顶点
int top
}stack;
//入栈
int push(stack *s, char e[])
{
if (s->top == N - 1)
{
return 0; //栈满
}
s->top++;
strcpy(s->data[s->top], e); //入栈
return 1; //入栈成功
}
//出栈
int pop(stack *s)
{
if (s->top == -1)
{
return 0; //出栈失败
}
s->top--;
return 1;
}
int flag = 0; //标记是否有路径
//打印栈
void outputStack(stack *s)
{
flag = 1; //表示有路径
for (int i = 0; i < s->top; i++) //打印最下面n-1个
{
printf("%s----->", s->data[i]);
}
printf("%s\n", s->data[s->top]); //打印最上面的一个
}
int v[N]; //记录每个顶点是否被访问过
//定义查找所有路径函数
void path(graph *g, stack *s, int start, int end)
{
//把起始点入栈
push(s, g->vertex[start]); //把vertex[start]起始点入栈
v[start] = 1; //把vertex[start] 标记为被访问过
if (start == end)
{
//如果当前的起始点和终止点相同，则表示找到一条路径
//打印栈的内容就是一条完整的路径
outputStack(s);
//把栈顶元素弹出，从新回溯到上一个被访问过的顶点
pop(s); //弹出栈,每次只能够弹出一个
//并且弹出的栈顶元素标记为未被访问过
v[end] = 0; //或者v[start] = 0;
return; //return必须加入，不然不行
}
//那么如果起始点和终止点不一样呢
//则找顶点vertex[start]的邻接点作为起始点出发，找到终止点
//vertex[end]的路径
for (int i = 0; i < N; i++)
{
//找未被访问过的邻接点
if (g->edge[start][i] == 1 && v[i] == 0)
{
//原先是从vertex[start] -> vertex[end]的路径
//现在把问题转换成从vertex[i] -> vertex[end] 的路径
path(g, s, i, end);
}
}
//如果没有找到vertex[start] 的邻接点
//则需要删除栈顶元素回溯到上一个被访问的邻接点
//继续找上一个被访问的顶点的未被访问过的邻接点
pop(s); //出栈
v[strat] = 0; //或者v[s->top] = 0;
}
//调用方式
int main()
{
graph g; //初始化图
stack s;
s.top = -1; //初始化栈
printf("请输入起始和终止的下标:");
int start;
int end;
scanf("%d %d", &start, &end);
path(&g, &s, start, end);
if (flag == 0)
{
printf("顶点%s到顶点%s之间没有路径\n", g->vertex[start], g->vertex[end]);
}
}
顺序表的定义
typedef struct {
char name[100]; //姓名
int age; //年龄
int score; //成绩
}stu;
#define MAX
typedef struct {
stu data[MAX];
int len;
}list;
顺序查找
对数组进行顺序查找(整数数组)
//在数组arr中查找关键词key的位置,并且返回下标
int search(int arr[], int len, int key)
{
for (int i = 0; i < len; i++)
{
if (key == arr[i])
{
return i;
}
}
return -1;
}
对结构体数组进行顺序查找
//在结构体数组中查找特定姓名的下标
int search(stu arr[], int len, char name[])
{
for (int i = 0; i < len; i++)
{
if (strcmp(arr[i].name, name) == 0)
{
return i;
}
}
return -1;
}
对顺序表进行顺序查找
//在顺序表中查找姓名为name的人，并且返回下标
int search(list *l, char name[])
{
for (int i = 0; i < l->len; i++)
{
if (strcmp(l->arr[i].name, name) == 0)
{
return i;
}
}
return -1;
}
顺序表的优化版本（哨兵优化),仅对顺序表进行举例子
//顺序表的哨兵法查找
int search(list *l, char name[])
{
if (strcmp(l->data[0].name, name) == 0)
{
return 0; //如果第一个刚好就是，则返回
}
stu temp = l->data[0];//保存第一元素
strcpy(l->data[0].name, name); //把第一个元素的名称更改为要查找的名称，这样子从右边往左边扫描，如果提前找到则成功，如果没有找到，那么由于我们在第一个位置设置了哨兵元素（即我们要查找的元素），所以当找到一个元素的时候，循环就自动结束了(查找失败)
int j = l->len - 1; //最后一个元素的下标
while (strcmp(l->data[j].name, name) != 0)
{
j--; //只要不相等则不断扫描
}
l->data[0] = temp; //还原我们设置的哨兵位置的元素值
if (j == 0)
{
//如果等于0表示找到的是我们设置的哨兵
return -1; //失败
}
else
{
return j; //成功
}
}
折半查找
- 前提: 数组有序(必须先排序)
对普通数组进行折半查找
//折半查找查找key在数组中的下标
int search(int arr[], int len, int key)
{
int low = 0; //低下标
int high = len - 1; //高下标
while (low <= high)
{
int mid = (low + high) / 2; //计算中间元素的下标
if(key == arr[mid])
{
return mid; //如果要查找的元素刚好位置中间则返回
}
else if (key < arr[mid]) //如果是降序，则改为 >
{
//如果小于中间元素则去左边找，区间范围[low, mid - 1]
high = mid - 1;
}
else
{
//如果大于中间元素则去右边找，区间范围[mid + 1, high]
low = mid + 1; //更新第下标
}
//循环再次回去重新计算中间下标
}
return -1; //查找失败
}
对顺序表进行折半查找
//对顺序表进行折半查找，注意查找之前必须排序
int search(list *l, char name[])
{
int low = 0;
int high = l->len - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (strcmp(name, l->data[mid].name) == 0)
{
return mid;
}
else if(strcmp(name, l->data[mid].name) < 0)
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
return -1;
}
二叉排序树的构造
构造数据类型为整型的二叉排序树
typedef struct node{
int data; //数据
node *left; //左孩子
node *right; //右孩子
}node;
//定义创建二叉排序树根的函数
node *create(int data) //把第一个结点值作为根
{
node *root = (node*) malloc(sizeof(node)); //创建根
if (root == NULL)
{
return NULL; //如果创建失败（几率很小）则返回空
}
root-data = data; //赋值
root->left = root->right = NULL; //左孩子和右孩子均为空
return root; //返回根
}
//定义结点插入函数，插入结点构造二叉排序树
void insert(node *root, int data)
{
if (data < root->data)
{
//如果小于根，则插入到左子树上
//1.如果左子树为空，则直接插入
if (root->left == NULL)
{
node *newNode = (node*)malloc(sizeof(node)); //创建新结点便于插入
newNode->data = data; //给新的结点赋值
newNode->left = newNode->right = NULL; //让新的结点左子树和右子树均为空
root->left = newNode; //把创建完成的新结点的地址赋值给根的左指针
}
else
{
//2.如果左子树不为空，则要递归找一个为空位置
insert(root->left, data); //递归插入到左子树上
}
}
else if (data > root->data)
{
//如果大于根，则插入到右子树上面
//1.如果右子树为空，则直接插入
if (root->right == NULL)
{
node *newNode = (node*)malloc(sizeof(node)); //创建新结点便于插入
newNode->data = data; //给新的结点赋值
newNode->left = newNode->right = NULL; //让新的结点左子树和右子树均为空
root->right = newNode; //把创建完成的新结点的地址赋值给根的右指针
}
else
{
//2.如果右子子树不为空，则要递归找一个为空位置
insert(root->right, data); //递归插入到右子树上
}
}
else
{
printf("和根节点相等，数据不合法\n");
//二叉排序树中不存在相同的结点值
}
}
//二叉树的中序遍历
void inOrder(node *root)
{
if (root != NULL)
{
inOrder(root->left); //递归访问左子树
printf("%d\t", root->data);
inOrder(root->right); //递归访问右子树
}
}
//如何调用
int main()
{
int arr[7] = {19, 14, 22, 66, 21, 83, 10}; //可以从键盘录入
node *root = create(arr[0]); //把第一个结点作为根
//一次把第arr[1] 到 arr[6]插入到二叉树里面
for (int i = 1; i < 7; i++)
{
insert(root, arr[i]); //依次把arr[i]插入到二叉树里面
}
printf("二叉排序树的中序遍历\n");
inOrder(root); //10 14 19 21 22 66 83
}
哈希表代码
//已知一组关键字序列为（25，51，8，22，26，67，11，16，54，41）
//将上述序列存入哈希表中，假设哈希函数: H(key)=key MOD 13
#define M 13 //定义哈希表长度
int hash(int key) //计算关键词得哈希地值
{
return key % M; //到底%多少看题目要求，
}
//把关键词key存放到哈希表里面
void put(int hashTable[], int key)
{
int index = hash(key); //计算关键词key的地址
while (hashTable[index] != 0) //如果不为空
{
//则采用线性探测法解决冲突，即不断往后面找
index = (index + 1) % M; //%M的目的是防止下标越界
//不可能找不到空白位置，因为哈希表的长度大于数组的个数,s
//所以哈希表基本不可能存在满的情况
}
hashTable[index] = key; //只要循环结束，则表明找到空白位置了
}
int count; //统计查找此输出
//查找关键词key在哈希表中的位置（下标）
int search(int hashTable[], int key)
{
int index = hash(key); //计算关键词key的地址
count = 1;
while (hashTable[index] != 0) //如果不为空
{
if (hashTable[index] == key)
{
return index;
}
index = (index + 1) % M; //%M的目的是防止下标越界
count++; //每次计算哈希地址，查找次数 + 1
}
//循环结束表示查找失败
return -1;
}
//如何去调用
int main()
{
int arr[10] = {25, 51, 8, 22, 26, 67, 11, 16, 54, 41};
int hashTable[M] = {0}; //初始化一个哈希表，长度为M
for (int i = 0; i < 10; i++)
{
put(hashTable, arr[i]);
}
printf("哈表的元素值如下\n");
for (int i = 0; i < M; i++)
{
printf("%d\t", hashTable[i]);
}
printf("\n");
for (int i = 0; i < 10; i++)
{
int index = search(hashTable, arr[i]); //查找arr[i]地址
printf("关键词%d的哈希地址是%d,查找次数%d\n", arr[i], index, count);
}
}
排序
插入排序(对数组类型进行排序)
//插入排序
void insertSort(int arr[], int len)
{
for (int i = 1; i < len; i++)
{
int key = arr[i]; //待插入的元素值
int j; //从有序元素的最后一位开始扫描
for (j = i - 1; j >= 0 && key < arr[j]; j--)
{
arr[j + 1] = arr[j]; //把元素往后移动
}
arr[j + 1] = key; //开始插入
}
}
插入排序（对顺序表进行排序)
//插入排序
void insertSort(list *l, int len)
{
for (int i = 1; i < l->len; i++)
{
stu key = l->data[i]; //待插入的元素值
int j; //从有序元素的最后一位开始扫描
for (j = i - 1; j >= 0 && key.age < l->data[j].age; j--)
{
l->data[j + 1] = l->data[j]; //把元素往后移动
}
l->data[j + 1] = key; //开始插入
}
}
希尔排序(对数组类型进行排序)
- 只要把直接插入排序外面套一层循环，然后把所有的1改为外层循环变量k
//希尔排序
void shellSort(int arr[], int len)
{
for (int k = len / 2; k > 0; k /= 2)
{
for (int i = k; i < len; i++)
{
int key = arr[i]; //待插入的元素值
int j; //从有序元素的最后一位开始扫描
for (j = i - k; j >= 0 && key < arr[j]; j -= k)
{
arr[j + k] = arr[j]; //把元素往后移动
}
arr[j + k] = key; //开始插入
}
}
}
希尔排序（对顺序表进行排序)
//希尔排序
void shellSort(list *l, int len)
{
for (int k = l->len / 2; k > 0; k /= 2)
{
for (int i = k; i < l->len; i++)
{
stu key = l->data[i]; //待插入的元素值
int j; //从有序元素的最后一位开始扫描
for (j = i - k; j >= 0 && key.age < l->data[j].age; j -= k)
{
l->data[j + k] = l->data[j]; //把元素往后移动
}
l->data[j + k] = key; //开始插入
}
}
}
冒泡排序(对基本数据类型排序)
void bubbleSort(int arr[], int len)
{
//每经过一趟可以得到一个最大值
//所以只需要(n-1)就可以完成排序
for (int i = 0; i < len - 1; i++)
{
int flag = 0; //标记是否有元素交换
for (int j = 0; j < len - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
flag = 1; //如果有元素交换则更改flag的值
}
}
if (flag == 0) //如果某一趟没有发生元素的交换则表明已经有序了
{
break;
}
}
}
冒泡排序(对顺序表进行排序)
void bubbleSort(list *l)
{
//每经过一趟可以得到一个最大值
//所以只需要(n-1)就可以完成排序
for (int i = 0; i < l->len - 1; i++)
{
int flag = 0; //标记是否有元素交换
for (int j = 0; j < l->len - 1 - i; j++)
{
if (strcmp(l->data[j].name, l->data[j + 1].name) > 0)
{
stu t = l->data[j];
l->data[j] = l->data[j + 1];
l->data[j + 1] = t;
flag = 1; //如果有元素交换则更改flag的值
}
}
if (flag == 0) //如果某一趟没有发生元素的交换则表明已经有序了
{
break;
}
}
}
简单选择排序(对数组进行排序)
void selectionSort(int arr[], int len)
{
//每一趟从无序元素里找最小值和无序的第一个元素交换
for (int i = 0; i < len - 1; i++)
{
int min = i; //假设当前的arr[i]是最小值
//从区间[i + 1, len - 1] 之间找最小值
for (int j = i + 1; j < len; j++)
{
if (arr[j] < arr[min])
{
min = j; //更新最小值下标
}
}
//交换arr[min]和arr[i]
// if (min != i)
// {
// int t = arr[min];
// arr[min] = arr[i];
// arr[i] = t;
// }
//如果不想用if包裹着也可以
int t = arr[min];
arr[min] = arr[i];
arr[i] = t;
}
}
简单选择排序(对顺序表)
void selectionSort(list *l)
{
//每一趟从无序元素里找最小值和无序的第一个元素交换
for (int i = 0; i < l->len - 1; i++)
{
int min = i; //假设当前的arr[i]是最小值
//从区间[i + 1, l->len - 1] 之间找最小值
for (int j = i + 1; j < l->len; j++)
{
if (l->data[j].age < l->data[min].age)
{
min = j; //更新最小值下标
}
}
//如果不想用if包裹着也可以
stu t = l->data[min];
l->data[min] = l->data[i];
l->data[i] = t;
}
}
