# 数据结构课程设计


有一门课叫数据结构与算法，有一句话叫‘思路很简单，细节是魔鬼’。

<!--more-->

### 二分查找

```c++
#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
```

### 赫夫曼树构造

```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);
}
```

上为网上代码

```c++
//修改可用版
#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

```c++
#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
```c++
#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
```
### 冒泡排序

```c++
#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;
}
//冒泡排序
```



### 直接插入排序

```c++
#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;
}
//直接插入排序
```