二叉樹(shù)性質(zhì)
- 在非空二叉樹(shù)的第i層上衷敌，至多有2(i - 1)個(gè)結(jié)點(diǎn)(i>=1)
#include <math.h> //注意引入頭文件
printf("請(qǐng)輸入層數(shù):");
int i;
scanf("%d", &i);
printf("第%d層最多有%d個(gè)結(jié)點(diǎn)", i, pow(2, i - 1));
- 在深度為K的二叉樹(shù)上最多有2k -1 個(gè)結(jié)點(diǎn)（k>=1)
printf("請(qǐng)輸入層數(shù):");
int k;
scanf("%d", &k);
printf("前%d層最多有%d個(gè)結(jié)點(diǎn)", k, pow(2, k) - 1);
- 在任意一棵二叉樹(shù)中，葉子結(jié)點(diǎn)的數(shù)目比度數(shù)為2的結(jié)點(diǎn)的數(shù)目多1，
n0 = n2 + 1
printf("請(qǐng)輸入度為1的結(jié)點(diǎn)個(gè)數(shù)一屋，及度為2的結(jié)點(diǎn)個(gè)數(shù)統(tǒng)計(jì)總結(jié)點(diǎn)個(gè)數(shù):");
int n0; //度為0的結(jié)點(diǎn)個(gè)數(shù)
int n1; //度為1的結(jié)點(diǎn)個(gè)數(shù)
int n2; //度為2的結(jié)點(diǎn)個(gè)數(shù)
scanf("%d %d", &n1, &n2);
n0 = n2 + 1; //葉子結(jié)點(diǎn)的數(shù)目比度數(shù)為2的結(jié)點(diǎn)的數(shù)目多1
printf("總的結(jié)點(diǎn)個(gè)數(shù)是%d\n", n0 + n1 + n2);
- 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 【log2n】 + 1
printf("請(qǐng)輸入完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)");
int n;
scanf("%d", &n);
printf("具有%d個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為%d", n, (int)log2(n) + 1)
二叉樹(shù)創(chuàng)建
結(jié)點(diǎn)類(lèi)型為字符型
typedef struct node {
char data; //數(shù)據(jù)
node *left; //左孩子指針
node *right; //右孩子指針
}node;
//定義創(chuàng)建函數(shù)
node* create()
{
printf("請(qǐng)輸入結(jié)點(diǎn)的值");
char ch;
scanf("%c", &ch);
//注意:如果考試過(guò)程中一次性錄入所有結(jié)點(diǎn)的值（包括#)則不需要吸收回車(chē)
//否則如果是一個(gè)結(jié)點(diǎn)一個(gè)結(jié)點(diǎn)的錄入則選喲吸收
getchar(); //吸收回車(chē)
if (ch == '#') //如果輸入的#表示為空
{
return NULL;
}
//1.創(chuàng)建根結(jié)點(diǎn)
node *root = (node*) malloc(sizeof(node));
if (root == NULL)
{
return NULL;
}
//創(chuàng)建根結(jié)點(diǎn)擎值，或者(node*) malloc(100));
root->data = ch; //給根結(jié)點(diǎn)賦值
root->left = create(); //遞歸創(chuàng)建左子樹(shù)
root->right = create(); //遞歸創(chuàng)建右子樹(shù)
return root; //返回根結(jié)點(diǎn)
}
結(jié)點(diǎn)類(lèi)型為整型的情況
typedef struct node {
int data; //數(shù)據(jù)
node *left; //左孩子指針
node *right; //右孩子指針
}node;
//定義創(chuàng)建函數(shù)
node* create()
{
printf("請(qǐng)輸入結(jié)點(diǎn)的值");
int ch;
scanf("%d", &ch);
if (ch == -1) //如果輸入的-1表示為空
{
return NULL;
}
//1.創(chuàng)建根結(jié)點(diǎn)
node *root = (node*) malloc(sizeof(node));
if (root == NULL)
{
return NULL;
}
//創(chuàng)建根結(jié)點(diǎn)，或者(node*) malloc(100));
root->data = ch; //給根結(jié)點(diǎn)賦值
root->left = create(); //遞歸創(chuàng)建左子樹(shù)
root->right = create(); //遞歸創(chuàng)建右子樹(shù)
return root; //返回根結(jié)點(diǎn)
}
結(jié)點(diǎn)類(lèi)型為字符串的情況
typedef struct node {
char data[100]; //數(shù)據(jù)
node *left; //左孩子指針
node *right; //右孩子指針
}node;
//定義創(chuàng)建函數(shù)
node* create()
{
printf("請(qǐng)輸入結(jié)點(diǎn)的值"); //如果考試的時(shí)候只出現(xiàn)了一次則放在主函數(shù)里面
char str[100];
scanf("%s", str);
if (strcmp(str, "#") == 0) //如果輸入的#表示為空
{
return NULL;
}
//1.創(chuàng)建根結(jié)點(diǎn)
node *root = (node*) malloc(sizeof(node));
if (root == NULL)
{
return NULL;
}
//創(chuàng)建根結(jié)點(diǎn)鲫忍，或者(node*) malloc(100));
strcpy(root->data, str); //給根結(jié)點(diǎn)賦值(必須使用函數(shù)的形式)
root->left = create(); //遞歸創(chuàng)建左子樹(shù)
root->right = create(); //遞歸創(chuàng)建右子樹(shù)
return root; //返回根結(jié)點(diǎn)
}
如何調(diào)用
//第一種情況:在菜單外面初始化
node *root = create();
//第二種情況
//在case里面初始化
node *root; //這句話放在while(1)的外面
//在case里面吧執(zhí)行
root = create();
二叉樹(shù)的遍歷
- 先序遍歷(先根膏燕，再左子樹(shù)，再右子樹(shù))
void preOrder(node *root) //
{
if (root != NULL)
{
printf("%c\t", root->data); //如果是字符串類(lèi)型則%c改為%s
preOrder(root->left); //遞歸遍歷左子樹(shù)
preOrder(root->right); //遞歸遍歷右子樹(shù)
}
}
//調(diào)用形式
preOrder(root);
-
中序遍歷(先左子樹(shù)悟民，再根坝辫，再右子樹(shù))
void inOrder(node *root) { if (root != NULL) { inOrder(root->left); //遞歸訪問(wèn)左子樹(shù) printf("%c\t", root->data); //如果是字符串類(lèi)型則%c改為%s inOrder(root->right); //遞歸訪問(wèn)右子樹(shù) } } //調(diào)用形式 inOrder(root); -
后序遍歷(先左子樹(shù)，再右子樹(shù)射亏，再根)
void postOrder(node *root) { if (root != NULL) { postOrder(root->left); //遞歸訪問(wèn)左子樹(shù) postOrder(root->right); //遞歸訪問(wèn)右子樹(shù) printf("%c\t", root->data); //如果是字符串類(lèi)型則%c改為%s } } //調(diào)用形式 postOrder(root);判斷兩棵二叉樹(shù)是否相同
判斷兩棵二叉樹(shù)是否為空近忙，如果都是空則表明相同
如果有一顆為空，另外一顆不為空則表明不相同
-
如果都不為空智润，則判斷根是否相同及舍，如果相同繼續(xù)判斷左子樹(shù)和右子樹(shù)是否都相同,如果都相同的情況下則表明兩棵二叉樹(shù)是相同的
//判斷兩棵二叉樹(shù)是否相同，如果相同返回1窟绷，否則返回0 int isSame(node *root1, node *root2) { if (root1 == NULL && root2 == NULL) { return 1; } else if(root1 == NULL || root2 == NULL) { return 0; //如果有一顆為空锯玛，另外一顆不為空則表明不相同 } else //兩棵樹(shù)都不為空 { if (root1->data == root2->data) //比較兩棵樹(shù)的數(shù)據(jù)域是否相同 { //如果根相同則還要遞歸比較左子樹(shù)和右子樹(shù) //只有根和左子樹(shù)和右子樹(shù)都相同的情況那么整顆樹(shù)一定是相等 return isSame(root1->left, root2->left) && isSame(root1->right, root2->right); } else { return 0; //如果對(duì)應(yīng)的根不相等則表示不相同 } } }求二叉樹(shù)的高度
- 求解出左子樹(shù)的高度
- 求解出右子樹(shù)的高度
- 比較左子樹(shù)和右子樹(shù)的高度，把較大的一個(gè)高度 + 1就是整顆二叉樹(shù)的高度
//求出二叉樹(shù)的高度 int gao(node *root) { if (root == NULL) { return 0; //為空的二叉樹(shù)高度為0 } //把根節(jié)點(diǎn)的左指針作為參數(shù)兼蜈，求解出左子樹(shù)的高度 int h1 = gao(root->left); //把根結(jié)點(diǎn)右指針作為參數(shù)攘残，求解出右子樹(shù)的高度 int h2 = gao(root->right); if (h1 > h2) { return h1 + 1; //+1因?yàn)橐由细Y(jié)點(diǎn)這一層 } else { return h2 + 1; } }求解二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)
- 求出左子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)
- 求出右子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)
- 把左子樹(shù)的葉子結(jié)點(diǎn) + 右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù) 就是整顆樹(shù)的結(jié)點(diǎn)個(gè)數(shù)
//統(tǒng)計(jì)二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù) int count(node *root) { if (root == NULL) { return 0; } else if(root->left == NULL && root->right == NULL) { return 1; //如果左子樹(shù)和右子樹(shù)同時(shí)為空則表明找到一個(gè)葉子 } else { //總的葉子結(jié)點(diǎn)個(gè)數(shù)等于左子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù) + 右子樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù) return count(root->left) + count(root->right); } }求出二叉樹(shù)中所有結(jié)點(diǎn)的個(gè)數(shù)
- 求出左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)
- 求出右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)
- 總的結(jié)點(diǎn)個(gè)數(shù) = 左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù) + 右子樹(shù)的結(jié)點(diǎn)個(gè)數(shù) + 1
//統(tǒng)計(jì)所有結(jié)點(diǎn)的個(gè)數(shù) int count(node *root) { if (root == NULL) { return 0; //如果根為空返回0 } else { return 1 + count(root->left) + count(root->right); } }統(tǒng)計(jì)二叉樹(shù)中所有度為1的結(jié)點(diǎn)個(gè)數(shù)（只有一個(gè)孩子)
int count(node *root) { if (root == NULL) { return 0; } if(root->left != NULL && root->right != NULL) { //如果根節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都不為空 //則整顆樹(shù)中度為1的結(jié)點(diǎn)個(gè)數(shù) = 左邊的 + 右邊的 return count(root->left) + count(root->right); } else if(root->left == NULL && root->right == NULL) { //如果左右都為空 return 0; } else //要么左子樹(shù)樹(shù)為空，要么右子樹(shù)為空 { return 1 + count(root->left) + count(root->right); } }
圖
#define N 8 //表示圖中頂點(diǎn)的個(gè)數(shù)
typedef struct {
char vertex[N][100]; //存儲(chǔ)頂點(diǎn)信息
int edge[N][N]; //存儲(chǔ)頂點(diǎn)之間邊的關(guān)系
}graph; // 定義圖形結(jié)構(gòu)體
//初始化圖
void init(graph *g)
{
//1.先初始化頂點(diǎn)
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;
}
}
}
//插入頂點(diǎn)(插入頂點(diǎn)和插入邊要分開(kāi))为狸，不然被扣分
void insertVertex(graph *g)
{
for (int i = 0; i < N; i++)
{
printf("請(qǐng)輸入第%d個(gè)頂點(diǎn):", i + 1);
scanf("%s", g->vertex[i]);
}
}
//插入邊（單詞可以隨意)
void insertEdge(graph *g)
{
//插入邊要考慮到優(yōu)化
//1.如果是有向圖不能優(yōu)化歼郭，最多優(yōu)化自生到自身的邊
//2.如果是無(wú)向圖可以優(yōu)化
//無(wú)任何優(yōu)化的版本(即沒(méi)有優(yōu)化自身到自身，也沒(méi)有實(shí)現(xiàn)對(duì)稱(chēng)的性質(zhì))
//下面的三個(gè)循環(huán)用一個(gè)就行了辐棒，別全干上去好吧病曾，看效果圖到底用哪個(gè)
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
printf("若頂點(diǎn)%s到頂點(diǎn)%s之間存在邊則輸入1,否則輸入0:", g->vertex[i], g->vertex[j]);
scanf("%d", &g->edge[i][j]);
}
}
//只過(guò)濾自身結(jié)點(diǎn)到自身結(jié)點(diǎn)的邊(過(guò)濾對(duì)角線的輸入)
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (i != j)
{
printf("若頂點(diǎn)%s到頂點(diǎn)%s之間存在邊則輸入1,否則輸入0:", g->vertex[i], g->vertex[j]);
scanf("%d", &g->edge[i][j]);
}
}
}
//全部?jī)?yōu)化（包括對(duì)角線及對(duì)稱(chēng)賦值)
for (int i = 0; i < N - 1; i++)
{
for (int j = i + 1; j < N; j++)
{
printf("若頂點(diǎn)%s到頂點(diǎn)%s之間存在邊則輸入1,否則輸入0:", g->vertex[i], g->vertex[j]);
scanf("%d", &g->edge[i][j]);
g->edge[j][i] = g->edge[i][j]; //對(duì)稱(chēng)賦值
}
}
}
//打印圖的鄰接矩陣
void output(graph *g)
{
//打印頂點(diǎn)元素
printf("頂點(diǎn)元素如下:\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");
}
}
//如何調(diào)用圖
int main()
{
graph g;
init(&g); //初始化圖
insertVertex(&g); //插入頂點(diǎn)
insertEdge(&g); //插入邊
output(&g); //打印圖
}
計(jì)算圖中每個(gè)頂點(diǎn)的入度(對(duì)應(yīng)粉絲量)
//注意：入度計(jì)算鄰接矩陣姊途，對(duì)應(yīng)頂點(diǎn)的列之和
void count(graph *g)
{
for (int i = 0; i < N; i++)
{
int sum = 0; //統(tǒng)計(jì)入度(統(tǒng)計(jì)列之和)
for (int j = 0; j < N; j++)
{
sum = sum + g->edge[j][i]; //按照列遍歷二維數(shù)組
}
printf("頂點(diǎn)%s的入度是%d\n", g->vertex[i], sum);
//printf("用戶%s的粉絲量是%d\n", g->vertex[i], sum);
}
}
計(jì)算圖中每個(gè)頂點(diǎn)的出(對(duì)應(yīng)關(guān)注量)
//注意：入度計(jì)算鄰接矩陣，對(duì)應(yīng)頂點(diǎn)的列之和
void count(graph *g)
{
for (int i = 0; i < N; i++)
{
int sum = 0; //統(tǒng)計(jì)出度(統(tǒng)計(jì)行之和)
for (int j = 0; j < N; j++)
{
sum = sum + g->edge[i][j]; //按照行遍歷二維數(shù)組
}
printf("頂點(diǎn)%s的出度是%d\n", g->vertex[i], sum);
//printf("用戶%s的關(guān)注量是%d\n", g->vertex[i], sum);
}
}
同時(shí)統(tǒng)計(jì)出每個(gè)頂點(diǎn)的入度和出度（粉絲量和關(guān)注量)
void count(graph *g)
{
for (int i = 0; i < N; i++)
{
int sum1 = 0; //統(tǒng)計(jì)入度
int sum2 = 0; //統(tǒng)計(jì)出度
for (int j = 0; j < N; j++)
{
sum1 = sum1 + g->edge[j][i];
sum2 = sum2 + g->edge[i][j]
}
printf("頂點(diǎn)%s的入度是%d\n", g->vertex[i], sum1);
printf("頂點(diǎn)%s的出度是%d\n", g->vertex[i], sum2);
printf("頂點(diǎn)%s的度是%d\n", g->vertex[i], sum1 + sum2); //度=入度+出度
}
}
求出圖中度最大值頂點(diǎn)信息
void max(graph *g)
{
//假設(shè)第一個(gè)頂點(diǎn)的度最大
int max = 0;
int maxi = 0; //記錄最大值的下標(biāo)
for (int i = 0; i < N; i++)
{
max = max + g->edge[0][i] + g->edge[i][0]; //求出第一行和最后一個(gè)行
}
for (int i = 0; i < N; i++)
{
int sum = 0; //記錄頂點(diǎn)vertex[i]的度（入度和出度)
for (int j = 0; j < N; j++)
{
sum = sum + g->edge[i][j] + g->edge[j][i]; //統(tǒng)計(jì)第i行和第i列之和
}
if (sum > max) //求最大值
{
max = sum; //更新最大值
maxi = i; //更新最大值的下標(biāo)
}
}
printf("度值最大值頂點(diǎn)是%s,他的度是是%d\n", g->vertex[maxi], max);
}
求出圖中入度最大的頂點(diǎn)(求出粉絲量多的用戶)
void max(graph *g)
{
//假設(shè)第一個(gè)頂點(diǎn)的入度最大值
int max = 0;
int maxi = 0; //記錄最大值的下標(biāo)
for (int i = 0; i < N; i++)
{
max = max + g->edge[i][0]; //求出第一行和最后一個(gè)行
}
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; //更新最大值的下標(biāo)
}
}
printf("入度值最大值頂點(diǎn)是%s,他的入度是是%d\n", g->vertex[maxi], max);
printf("用戶%s的粉絲量最多,他的粉絲量為%d\n", g->vertex[maxi], max);
}
求出圖中出度最大的頂點(diǎn)(求出關(guān)注量多的用戶)
void max(graph *g)
{
//假設(shè)第一個(gè)頂點(diǎn)的入度最大值
int max = 0;
int maxi = 0; //記錄最大值的下標(biāo)
for (int i = 0; i < N; i++)
{
max = max + g->edge[0][i]; //求出第一行和最后一個(gè)行
}
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; //更新最大值的下標(biāo)
}
}
printf("出度值最大值頂點(diǎn)是%s,他的出度是是%d\n", g->vertex[maxi], max);
printf("用戶%s的關(guān)注量最多,他的關(guān)注量為%d\n", g->vertex[maxi], max);
}
深度優(yōu)先搜索代碼
int v[N]; //默認(rèn)是0知态，記錄每個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)的狀態(tài)
void dfs(graph *g, int start) //start為起始頂點(diǎn)的下標(biāo)
{
printf("%s\t", g->vertex[start]); //打印下表為start的頂點(diǎn)
v[start] = 1; //表示Vi被訪問(wèn)過(guò)了
//下一步捷兰，找vi未被訪問(wèn)過(guò)的鄰接點(diǎn)作為起始點(diǎn)，注意鄰接點(diǎn)一定位于start下標(biāo)這一行
for (int i = 0; i < N; i++)
{
if (g->edge[start][i] == 1 && v[i] == 0)
{
dfs(g, i); //把i下標(biāo)作為新的起始點(diǎn)出發(fā)深度優(yōu)先搜索
}
}
}
打印圖的所有路徑
//定義棧
typedef struct {
char data[N][100]; //存放N個(gè)頂點(diǎ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; //標(biāo)記是否有路徑
//打印棧
void outputStack(stack *s)
{
flag = 1; //表示有路徑
for (int i = 0; i < s->top; i++) //打印最下面n-1個(gè)
{
printf("%s----->", s->data[i]);
}
printf("%s\n", s->data[s->top]); //打印最上面的一個(gè)
}
int v[N]; //記錄每個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)
//定義查找所有路徑函數(shù)
void path(graph *g, stack *s, int start, int end)
{
//把起始點(diǎn)入棧
push(s, g->vertex[start]); //把vertex[start]起始點(diǎn)入棧
v[start] = 1; //把vertex[start] 標(biāo)記為被訪問(wèn)過(guò)
if (start == end)
{
//如果當(dāng)前的起始點(diǎn)和終止點(diǎn)相同负敏，則表示找到一條路徑
//打印棧的內(nèi)容就是一條完整的路徑
outputStack(s);
//把棧頂元素彈出贡茅，從新回溯到上一個(gè)被訪問(wèn)過(guò)的頂點(diǎn)
pop(s); //彈出棧,每次只能夠彈出一個(gè)
//并且彈出的棧頂元素標(biāo)記為未被訪問(wèn)過(guò)
v[end] = 0; //或者v[start] = 0;
return; //return必須加入，不然不行
}
//那么如果起始點(diǎn)和終止點(diǎn)不一樣呢
//則找頂點(diǎn)vertex[start]的鄰接點(diǎn)作為起始點(diǎn)出發(fā)其做，找到終止點(diǎn)
//vertex[end]的路徑
for (int i = 0; i < N; i++)
{
//找未被訪問(wèn)過(guò)的鄰接點(diǎn)
if (g->edge[start][i] == 1 && v[i] == 0)
{
//原先是從vertex[start] -> vertex[end]的路徑
//現(xiàn)在把問(wèn)題轉(zhuǎn)換成從vertex[i] -> vertex[end] 的路徑
path(g, s, i, end);
}
}
//如果沒(méi)有找到vertex[start] 的鄰接點(diǎn)
//則需要?jiǎng)h除棧頂元素回溯到上一個(gè)被訪問(wèn)的鄰接點(diǎn)
//繼續(xù)找上一個(gè)被訪問(wèn)的頂點(diǎn)的未被訪問(wèn)過(guò)的鄰接點(diǎn)
pop(s); //出棧
v[strat] = 0; //或者v[s->top] = 0;
}
//調(diào)用方式
int main()
{
graph g; //初始化圖
stack s;
s.top = -1; //初始化棧
printf("請(qǐng)輸入起始和終止的下標(biāo):");
int start;
int end;
scanf("%d %d", &start, &end);
path(&g, &s, start, end);
if (flag == 0)
{
printf("頂點(diǎn)%s到頂點(diǎn)%s之間沒(méi)有路徑\n", g->vertex[start], g->vertex[end]);
}
}
順序表的定義
typedef struct {
char name[100]; //姓名
int age; //年齡
int score; //成績(jī)
}stu;
#define MAX
typedef struct {
stu data[MAX];
int len;
}list;
順序查找
對(duì)數(shù)組進(jìn)行順序查找(整數(shù)數(shù)組)
//在數(shù)組arr中查找關(guān)鍵詞key的位置,并且返回下標(biāo)
int search(int arr[], int len, int key)
{
for (int i = 0; i < len; i++)
{
if (key == arr[i])
{
return i;
}
}
return -1;
}
對(duì)結(jié)構(gòu)體數(shù)組進(jìn)行順序查找
//在結(jié)構(gòu)體數(shù)組中查找特定姓名的下標(biāo)
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;
}
對(duì)順序表進(jìn)行順序查找
//在順序表中查找姓名為name的人顶考，并且返回下標(biāo)
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;
}
順序表的優(yōu)化版本（哨兵優(yōu)化),僅對(duì)順序表進(jìn)行舉例子
//順序表的哨兵法查找
int search(list *l, char name[])
{
if (strcmp(l->data[0].name, name) == 0)
{
return 0; //如果第一個(gè)剛好就是，則返回
}
stu temp = l->data[0];//保存第一元素
strcpy(l->data[0].name, name); //把第一個(gè)元素的名稱(chēng)更改為要查找的名稱(chēng)妖泄，這樣子從右邊往左邊掃描驹沿，如果提前找到則成功，如果沒(méi)有找到蹈胡，那么由于我們?cè)诘谝粋€(gè)位置設(shè)置了哨兵元素（即我們要查找的元素）渊季，所以當(dāng)找到一個(gè)元素的時(shí)候，循環(huán)就自動(dòng)結(jié)束了(查找失敗)
int j = l->len - 1; //最后一個(gè)元素的下標(biāo)
while (strcmp(l->data[j].name, name) != 0)
{
j--; //只要不相等則不斷掃描
}
l->data[0] = temp; //還原我們?cè)O(shè)置的哨兵位置的元素值
if (j == 0)
{
//如果等于0表示找到的是我們?cè)O(shè)置的哨兵
return -1; //失敗
}
else
{
return j; //成功
}
}
折半查找
- 前提: 數(shù)組有序(必須先排序)
對(duì)普通數(shù)組進(jìn)行折半查找
//折半查找查找key在數(shù)組中的下標(biāo)
int search(int arr[], int len, int key)
{
int low = 0; //低下標(biāo)
int high = len - 1; //高下標(biāo)
while (low <= high)
{
int mid = (low + high) / 2; //計(jì)算中間元素的下標(biāo)
if(key == arr[mid])
{
return mid; //如果要查找的元素剛好位置中間則返回
}
else if (key < arr[mid]) //如果是降序罚渐，則改為 >
{
//如果小于中間元素則去左邊找却汉，區(qū)間范圍[low, mid - 1]
high = mid - 1;
}
else
{
//如果大于中間元素則去右邊找，區(qū)間范圍[mid + 1, high]
low = mid + 1; //更新第下標(biāo)
}
//循環(huán)再次回去重新計(jì)算中間下標(biāo)
}
return -1; //查找失敗
}
對(duì)順序表進(jìn)行折半查找
//對(duì)順序表進(jìn)行折半查找荷并，注意查找之前必須排序
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;
}
二叉排序樹(shù)的構(gòu)造
構(gòu)造數(shù)據(jù)類(lèi)型為整型的二叉排序樹(shù)
typedef struct node{
int data; //數(shù)據(jù)
node *left; //左孩子
node *right; //右孩子
}node;
//定義創(chuàng)建二叉排序樹(shù)根的函數(shù)
node *create(int data) //把第一個(gè)結(jié)點(diǎn)值作為根
{
node *root = (node*) malloc(sizeof(node)); //創(chuàng)建根
if (root == NULL)
{
return NULL; //如果創(chuàng)建失敽仙啊（幾率很小）則返回空
}
root-data = data; //賦值
root->left = root->right = NULL; //左孩子和右孩子均為空
return root; //返回根
}
//定義結(jié)點(diǎn)插入函數(shù)源织，插入結(jié)點(diǎn)構(gòu)造二叉排序樹(shù)
void insert(node *root, int data)
{
if (data < root->data)
{
//如果小于根翩伪，則插入到左子樹(shù)上
//1.如果左子樹(shù)為空，則直接插入
if (root->left == NULL)
{
node *newNode = (node*)malloc(sizeof(node)); //創(chuàng)建新結(jié)點(diǎn)便于插入
newNode->data = data; //給新的結(jié)點(diǎn)賦值
newNode->left = newNode->right = NULL; //讓新的結(jié)點(diǎn)左子樹(shù)和右子樹(shù)均為空
root->left = newNode; //把創(chuàng)建完成的新結(jié)點(diǎn)的地址賦值給根的左指針
}
else
{
//2.如果左子樹(shù)不為空谈息，則要遞歸找一個(gè)為空位置
insert(root->left, data); //遞歸插入到左子樹(shù)上
}
}
else if (data > root->data)
{
//如果大于根缘屹，則插入到右子樹(shù)上面
//1.如果右子樹(shù)為空，則直接插入
if (root->right == NULL)
{
node *newNode = (node*)malloc(sizeof(node)); //創(chuàng)建新結(jié)點(diǎn)便于插入
newNode->data = data; //給新的結(jié)點(diǎn)賦值
newNode->left = newNode->right = NULL; //讓新的結(jié)點(diǎn)左子樹(shù)和右子樹(shù)均為空
root->right = newNode; //把創(chuàng)建完成的新結(jié)點(diǎn)的地址賦值給根的右指針
}
else
{
//2.如果右子子樹(shù)不為空黎茎，則要遞歸找一個(gè)為空位置
insert(root->right, data); //遞歸插入到右子樹(shù)上
}
}
else
{
printf("和根節(jié)點(diǎn)相等囊颅，數(shù)據(jù)不合法\n");
//二叉排序樹(shù)中不存在相同的結(jié)點(diǎn)值
}
}
//二叉樹(shù)的中序遍歷
void inOrder(node *root)
{
if (root != NULL)
{
inOrder(root->left); //遞歸訪問(wèn)左子樹(shù)
printf("%d\t", root->data);
inOrder(root->right); //遞歸訪問(wèn)右子樹(shù)
}
}
//如何調(diào)用
int main()
{
int arr[7] = {19, 14, 22, 66, 21, 83, 10}; //可以從鍵盤(pán)錄入
node *root = create(arr[0]); //把第一個(gè)結(jié)點(diǎn)作為根
//一次把第arr[1] 到 arr[6]插入到二叉樹(shù)里面
for (int i = 1; i < 7; i++)
{
insert(root, arr[i]); //依次把a(bǔ)rr[i]插入到二叉樹(shù)里面
}
printf("二叉排序樹(shù)的中序遍歷\n");
inOrder(root); //10 14 19 21 22 66 83
}
哈希表代碼
//已知一組關(guān)鍵字序列為（25当悔，51傅瞻，8，22盲憎，26嗅骄，67，11饼疙，16溺森，54慕爬，41）
//將上述序列存入哈希表中，假設(shè)哈希函數(shù): H(key)=key MOD 13
#define M 13 //定義哈希表長(zhǎng)度
int hash(int key) //計(jì)算關(guān)鍵詞得哈希地值
{
return key % M; //到底%多少看題目要求屏积，
}
//把關(guān)鍵詞key存放到哈希表里面
void put(int hashTable[], int key)
{
int index = hash(key); //計(jì)算關(guān)鍵詞key的地址
while (hashTable[index] != 0) //如果不為空
{
//則采用線性探測(cè)法解決沖突医窿，即不斷往后面找
index = (index + 1) % M; //%M的目的是防止下標(biāo)越界
//不可能找不到空白位置，因?yàn)楣１淼拈L(zhǎng)度大于數(shù)組的個(gè)數(shù),s
//所以哈希表基本不可能存在滿的情況
}
hashTable[index] = key; //只要循環(huán)結(jié)束炊林，則表明找到空白位置了
}
int count; //統(tǒng)計(jì)查找此輸出
//查找關(guān)鍵詞key在哈希表中的位置（下標(biāo)）
int search(int hashTable[], int key)
{
int index = hash(key); //計(jì)算關(guān)鍵詞key的地址
count = 1;
while (hashTable[index] != 0) //如果不為空
{
if (hashTable[index] == key)
{
return index;
}
index = (index + 1) % M; //%M的目的是防止下標(biāo)越界
count++; //每次計(jì)算哈希地址姥卢，查找次數(shù) + 1
}
//循環(huán)結(jié)束表示查找失敗
return -1;
}
//如何去調(diào)用
int main()
{
int arr[10] = {25, 51, 8, 22, 26, 67, 11, 16, 54, 41};
int hashTable[M] = {0}; //初始化一個(gè)哈希表，長(zhǎng)度為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("關(guān)鍵詞%d的哈希地址是%d,查找次數(shù)%d\n", arr[i], index, count);
}
}
排序
插入排序(對(duì)數(shù)組類(lèi)型進(jìn)行排序)
//插入排序
void insertSort(int arr[], int len)
{
for (int i = 1; i < len; i++)
{
int key = arr[i]; //待插入的元素值
int j; //從有序元素的最后一位開(kāi)始掃描
for (j = i - 1; j >= 0 && key < arr[j]; j--)
{
arr[j + 1] = arr[j]; //把元素往后移動(dòng)
}
arr[j + 1] = key; //開(kāi)始插入
}
}
插入排序（對(duì)順序表進(jìn)行排序)
//插入排序
void insertSort(list *l, int len)
{
for (int i = 1; i < l->len; i++)
{
stu key = l->data[i]; //待插入的元素值
int j; //從有序元素的最后一位開(kāi)始掃描
for (j = i - 1; j >= 0 && key.age < l->data[j].age; j--)
{
l->data[j + 1] = l->data[j]; //把元素往后移動(dòng)
}
l->data[j + 1] = key; //開(kāi)始插入
}
}
希爾排序(對(duì)數(shù)組類(lèi)型進(jìn)行排序)
- 只要把直接插入排序外面套一層循環(huán)渣聚，然后把所有的1改為外層循環(huán)變量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; //從有序元素的最后一位開(kāi)始掃描
for (j = i - k; j >= 0 && key < arr[j]; j -= k)
{
arr[j + k] = arr[j]; //把元素往后移動(dòng)
}
arr[j + k] = key; //開(kāi)始插入
}
}
}
希爾排序（對(duì)順序表進(jìn)行排序)
//希爾排序
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; //從有序元素的最后一位開(kāi)始掃描
for (j = i - k; j >= 0 && key.age < l->data[j].age; j -= k)
{
l->data[j + k] = l->data[j]; //把元素往后移動(dòng)
}
l->data[j + k] = key; //開(kāi)始插入
}
}
}
冒泡排序(對(duì)基本數(shù)據(jù)類(lèi)型排序)
void bubbleSort(int arr[], int len)
{
//每經(jīng)過(guò)一趟可以得到一個(gè)最大值
//所以只需要(n-1)就可以完成排序
for (int i = 0; i < len - 1; i++)
{
int flag = 0; //標(biāo)記是否有元素交換
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) //如果某一趟沒(méi)有發(fā)生元素的交換則表明已經(jīng)有序了
{
break;
}
}
}
冒泡排序(對(duì)順序表進(jìn)行排序)
void bubbleSort(list *l)
{
//每經(jīng)過(guò)一趟可以得到一個(gè)最大值
//所以只需要(n-1)就可以完成排序
for (int i = 0; i < l->len - 1; i++)
{
int flag = 0; //標(biāo)記是否有元素交換
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) //如果某一趟沒(méi)有發(fā)生元素的交換則表明已經(jīng)有序了
{
break;
}
}
}
簡(jiǎn)單選擇排序(對(duì)數(shù)組進(jìn)行排序)
void selectionSort(int arr[], int len)
{
//每一趟從無(wú)序元素里找最小值和無(wú)序的第一個(gè)元素交換
for (int i = 0; i < len - 1; i++)
{
int min = i; //假設(shè)當(dāng)前的arr[i]是最小值
//從區(qū)間[i + 1, len - 1] 之間找最小值
for (int j = i + 1; j < len; j++)
{
if (arr[j] < arr[min])
{
min = j; //更新最小值下標(biāo)
}
}
//交換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;
}
}
簡(jiǎn)單選擇排序(對(duì)順序表)
void selectionSort(list *l)
{
//每一趟從無(wú)序元素里找最小值和無(wú)序的第一個(gè)元素交換
for (int i = 0; i < l->len - 1; i++)
{
int min = i; //假設(shè)當(dāng)前的arr[i]是最小值
//從區(qū)間[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; //更新最小值下標(biāo)
}
}
//如果不想用if包裹著也可以
stu t = l->data[min];
l->data[min] = l->data[i];
l->data[i] = t;
}
}
