数据结构课程设计
目录
注意
本文最后更新于 2024-02-24，文中内容可能已过时。
有一门课叫数据结构与算法，有一句话叫‘思路很简单，细节是魔鬼’。
二分查找
#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
int a[100];
int aim,n,i,j,flag = 0,count = 0;
scanf("%d",&n);int high=n-1,low = 0, mid;;
for (i = 0; i < n; i++) scanf("%d",&a[i]);
scanf("%d",&aim);
while (low <= high)
{
count++;
mid = (low + high) / 2;
if (aim == a[mid])
{
flag = 1;
printf("%d %d ",aim,count);
break;
}
if (aim > a[mid]) low = mid + 1;
if (aim < a[mid]) high = mid - 1;
}
if (flag == 0) printf("not found!");
return 0;
}c赫夫曼树构造
#include<iostream>
#define length 6
using namespace std;
struct Tree{
int data;
Tree *left;
Tree *right;
};
//构造哈夫曼树
Tree *creatHT(char *arr){
Tree *pArr[length] = { NULL }; //结构体指针数组
Tree *p = NULL, *root = NULL;
for (int i = 0; i < length; i++){
pArr[i] = (Tree *)malloc(sizeof(Tree));
pArr[i]->left = NULL;
pArr[i]->right = NULL;
pArr[i]->data = arr[i];
}
for (int i = 0; i < length - 1; i++){ //每次将data最小和次小的结构体地址赋给数组的前两位
for (int m = i; m < length - 1; m++){ //每次循环后，下一次循环就往前移动一位（因为上一位被释放）
for (int j = m + 1; j < length; j++){
if (pArr[m]->data > pArr[j]->data){
Tree *temp = pArr[m];
pArr[m] = pArr[j];
pArr[j] = temp;
}
}
}
int k = i;
Tree *p = root;
root = (Tree *)malloc(sizeof(Tree));
root->left = pArr[k]; //合并每次排序下来最小的两位
root->right = pArr[k + 1];
root->data = pArr[k]->data + pArr[k + 1]->data;
pArr[k] = NULL; //每次合并后森林中的结点数减一，因此每次将数组的指针减一（指向空）并释放
free(pArr[k]); //每次合并的根节点存放在数组删除一个位置后的第一个位置，直到最后最终的根结点存放在数组的最后一个位置中
pArr[k + 1] = root;
}
return root;
}
int countWPL(Tree *root, int height = 0){
Tree *temp = root;
if (temp->left == NULL&&temp->right == NULL){
return temp->data*height;
}
else{
return countWPL(temp->left, height + 1) + countWPL(temp->right, height + 1);
}
}
void HuffmanCoding(Tree *root, int len){ //len为每个叶子的结点与根的路径长度
static int arr[10] = { 0 }; //相当于全局变量，只有第一次被初始化，后面递归会跳过初始化，原来值不变，叶子从左至右
if (root == NULL){
return;
}
if (root->left == NULL ){ //叶子结点，只需判断一个孩子是否为空，如果为空则两个孩子都为空
cout << "value:" << root->data<<"\t"; //打印叶子结点的权值
for (int i = 0; i < len; i++){
cout << arr[i]; //根据叶子高度依次打印出哈夫曼编码
}
cout << endl;
return;
}
else{
arr[len] = 0; //由于是哈夫曼树，所以每个结点的度为0或2不可能为1（即有孩子一定是两个孩子）
HuffmanCoding(root->left, len +1);
arr[len] = 1; //往左走添个0，往右走添1
HuffmanCoding(root->right, len +1);
}
}
void traverse(const Tree *root){ //中序遍历哈夫曼树
const Tree *temp = root;
if (temp == NULL){
return;
}
if (temp->left != NULL){
traverse(temp->left);
}
cout << temp->data << endl;
if (temp->right != NULL){
traverse(temp->right);
}
}
int main(){
char arr[] = {'a','b','c','a','a','a','a','b','b','c','c','c','c','c','c','d','d','e','e','e','e','e','e','e','e','e','e','e','f','f','f','f','f','f','f'};
creatHT(arr);
for (int i = 0; i < length; i++){
cout << arr[i] << endl;
}
cout << "----" << endl;
Tree *root = creatHT(arr);
traverse(root);
int w = countWPL(root);
cout << "WPL:" << w << endl;
HuffmanCoding(root, 0);
}上为网上代码
//修改可用版
#include <iostream>
#include <stdio.h>
#define length 16
//#define NULL 0
using namespace std;
struct Tree
{
int data;
Tree *left;
Tree *right;
};
Tree *creatHT(char *arr)
{
Tree *pArr[length] = {NULL};
Tree *p = NULL, *root = NULL;
for (int i = 0; i < length; i++)
{
pArr[i] = (Tree *)malloc(sizeof(Tree));
pArr[i]->left = NULL;
pArr[i]->right = NULL;
pArr[i]->data = arr[i];
}
for (int i = 0; i < length - 1; i++)
{
for (int m = i; m < length - 1; m++)
{
for (int j = m + 1; j < length; j++)
{
if (pArr[m]->data > pArr[j]->data)
{
Tree *temp = pArr[m];
pArr[m] = pArr[j];
pArr[j] = temp;
}
}
}
int k = i;
Tree *p = root;
root = (Tree *)malloc(sizeof(Tree));
root->left = pArr[k];
root->right = pArr[k + 1];
root->data = pArr[k]->data + pArr[k + 1]->data;
pArr[k] = NULL;
free(pArr[k]);
pArr[k + 1] = root;
}
return root;
}
int countWPL(Tree *root, int height = 0)
{
Tree *temp = root;
if (temp->left == NULL && temp->right == NULL)
{
return temp->data * height;
}
else
{
return countWPL(temp->left, height + 1) + countWPL(temp->right, height + 1);
}
}
void HuffmanCoding(Tree *root, int len)
{
static int arr[10] = {0};
if (root == NULL)
{
return;
}
if (root->left == NULL)
{
printf("%c ", root->data);
for (int i = 0; i < len; i++)
{
cout << arr[i];
}
cout << endl;
return;
}
else
{
arr[len] = 0;
HuffmanCoding(root->left, len + 1);
arr[len] = 1;
HuffmanCoding(root->right, len + 1);
}
}
void traverse(const Tree *root)
{
const Tree *temp = root;
if (temp == NULL)
{
return;
}
if (temp->left != NULL)
{
traverse(temp->left);
}
cout << temp->data << endl;
if (temp->right != NULL)
{
traverse(temp->right);
}
}
int main()
{
char arr[] = {'a', 'b', 'c', 'a', 'a', 'a', 'a', 'b', 'b', 'c', 'c', 'c', 'c', 'c', 'c', 'd', 'd', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'e', 'f', 'f', 'f', 'f', 'f', 'f', 'f'};
creatHT(arr);
for (int i = 0; i < length; i++)
{
cout << arr[i] << endl;
}
Tree *root = creatHT(arr);
traverse(root);
int w = countWPL(root);
cout << "WPL:" << w << endl;
HuffmanCoding(root, 0);
}最小生成树prim
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define inf 2147483647
int mp[105][105];
int low[105],vis[105];
int main()
{
int n,i,j,pos,Min,ans;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&mp[i][j]);
if(mp[i][j]==-1) mp[i][j]=inf;
}
for(i=1;i<=n;i++) low[i]=mp[i][1];
memset(vis,0,sizeof(vis));
vis[1]=1;
ans=0;
for(i=1;i<=n-1;i++)
{
Min=inf;
for(j=1;j<=n;j++)
{
if(low[j]<Min&&vis[j]==0)
{
pos=j;
Min=low[j];
}
}
vis[pos]=1;
ans+=Min;
for(j=1;j<=n;j++)
{
if(mp[pos][j]<low[j]) low[j]=mp[pos][j];
}
}
printf("%d\n",ans);
return 0;
}
//最小生成树prim
kruskal
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
struct node
{
int x;
int y;
int len;
} a[1005];
int rt[1005];
int cmp(node a, node b)
{
return a.len < b.len;
}
int fin(int n)
{
if (rt[n] == n)
return n;
return rt[n] = fin(rt[n]);
}
int main()
{
int n, m, i, j, x, y, ans;
while (scanf("%d%d", &n, &m) != EOF)
{
for (i = 1; i <= n; i++)
rt[i] = i;
for (i = 0; i < m; i++)
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].len);
sort(a, a + m, cmp);
ans = 0;
for (i = 0; i < m; i++)
{
x = fin(a[i].x);
y = fin(a[i].y);
if (x != y)
{
rt[x] = y;
ans += a[i].len;
}
}
printf("%d\n", ans);
system("pause");
return 0;
}
}
//kruskal
冒泡排序
#include<stdio.h>
#include<stdlib.h>
void BubbleSort(int a[], int len)
{
int i, j, temp;
for (j = 0; j < len - 1; j++)
{
for (i = 0; i < len - 1 - j; i++)
if (a[i] > a[i + 1])
{
temp = a[i];
a[i] = a[i + 1];
a[i + 1] = temp;
}
}
}
int main()
{
int a[] = { 9, 8, 7, 6, 5, 4, 3, 2 , 1 };
int len = sizeof(a) / sizeof(a[0]);
int i = 0;
for (i = 0; i < len; i++) printf("%d ", a[i]);
printf("\n");
BubbleSort(a, len);
for (i = 0; i < len; i++) printf("%d ", a[i]);
printf("\n");
system("pause");
return 0;
}
//冒泡排序
直接插入排序
#include <stdio.h>
int i, j;
void InsertSort(int a[], int size)
{
for (i = 0; i < size; i++)
printf("%d ", a[i]);
printf("\n");
int key = a[0];
for (i = 1; i < size; i++)
{
if (a[i] < a[i - 1])
{
key = a[i];
j = i - 1;
while (key < a[j])
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = key;
}
// for (int i = 0; i < size; i++) printf("%d ", a[i]);
// printf("\n");
}
}
int main()
{
int a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
int size = sizeof(a) / sizeof(int);
printf("%d \n", size);
InsertSort(a, size);
for (int i = 0; i < size; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
//直接插入排序