C语言---数据结构实验---哈夫曼树及哈夫曼编码的算法实现---图的基本操作

简介: C语言---数据结构实验---哈夫曼树及哈夫曼编码的算法实现---图的基本操作

写在前面

本篇实验代码非本人写,代码源自外部,经调试解决了部分warning和error后在本地vs上可以正常运行,如有运行失败可换至vs

未来会重构实现该两个实验


哈夫曼树及哈夫曼编码的算法实现

实验内容

内容要求:

1、初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立哈夫曼树

2、建立编码表(CreateTable):利用已经建好的哈夫曼树进行编码,并将每个字符的编码输出。

3、编码(Encoding):根据编码表对输入的字符串进行编码,并将编码后的字符串输出

4、译码(Decoding):利用已经建好的哈夫曼树对编码后的字符串进行译码,并输出译码结果。

测试数据:

输入字符串“thisprogramismyfavourite”,完成这28个字符的编码和译码。

代码实现

#include<iostream>
#include<string.h>
#include<queue>
#define MAX 10000 
using namespace std;
char a[100], buff[1024], p;
typedef struct
{
  char letter, * code;
  int weight;
  int parent, lchild, rchild;
}HTNode, * HuffmanTree;
int n;
char coding[100];
int Min(HuffmanTree& HT, int i)
{
  int j;
  int k = MAX;
  int flag=0;
  for (j = 0; j <= i; ++j)
  {
    if (HT[j].weight < k && HT[j].parent == 0)
    {
      k = HT[j].weight;
      flag = j;
    }
  }
  HT[flag].parent = 1;
  return flag;
}
void Select(HuffmanTree& HT, int i, int& s1, int& s2)
{
  s1 = Min(HT, i);
  s2 = Min(HT, i);
}
void CreateHuffmanTree(HuffmanTree& HT, char t[], int w[])
{
  int m;
  int i, s1, s2;
  if (n <= 1)
    return;
  m = 2 * n - 1; 
  HT = new HTNode[m + 1];
  for (i = 0; i < n; i++)
  {
    char arr[] = "0";
    char* pa = arr;
    HT[i].code = pa;
    HT[i].parent = 0;
    HT[i].lchild = -1;
    HT[i].rchild = -1;
    HT[i].letter = t[i];
    HT[i].weight = w[i];
  }
  for (i = n; i <= m; i++)
  {
    char arr[] = "0";
    char* pa = arr;
    HT[i].code = pa;
    HT[i].parent = 0;
    HT[i].lchild = -1;
    HT[i].rchild = -1;
    HT[i].letter = ' ';
    HT[i].weight = 0;
  }
  cout << "********************************" << endl;
  for (i = n; i < m; i++)
  {
    Select(HT, i - 1, s1, s2);
    HT[s1].parent = i;
    HT[s2].parent = i;
    HT[i].lchild = s1;
    HT[i].rchild = s2;
    HT[i].weight = HT[s1].weight + HT[s2].weight;
  }
}
void CreatHuffmanCode(HuffmanTree HT)
{
  int start, c, f;
  int i;
  char* cd = new char[n];
  cd[n - 1] = '\0';
  cout << "字符编码为:" << endl;
  for (i = 0; i < n; i++)
  {
    start = n - 1;
    c = i;
    f = HT[i].parent;
    while (f != 0) 
    {
      --start;
      if (HT[f].lchild == c) 
      {
        cd[start] = '0';
      }
      else 
      {
        cd[start] = '1';
      }
      c = f;
      f = HT[f].parent;
    }
    HT[i].code = new char[n - start];
    strcpy(HT[i].code, &cd[start]);
    cout << HT[i].letter << ":" << HT[i].code << endl;
  }
  delete[] cd;
}
void HuffmanTreeDecode(HuffmanTree HT, char cod[], int b)  
{
  char sen[100];
  char temp[50];
  char voidstr[] = " ";
  int t = 0;
  int s = 0;
  int count = 0;
  for (int i = 0; i < b; i++)
  {
    temp[t++] = cod[i];
    temp[t] = '\0';
    for (int j = 0; j < n; j++) 
    {
      if (!strcmp(HT[j].code, temp)) 
      {
        sen[s] = HT[j].letter;
        s++;
        count += t;
        strcpy(temp, voidstr);
        t = 0;
        break;
      }
    }
  }
  if (t == 0) 
  {
    sen[s] = '\0';
    cout << "译码为:" << endl;
    cout << sen << endl;
  }
  else 
  {
    cout << "二进制源码有错!从第" << count + 1 << "位开始" << endl;
  }
}
int main()
{
  HuffmanTree HT;
  int b[100]={0};
  int i, j;
  int symbol = 1, x, k;
  cout << "请输入一段文字:";
  cin >> buff;
  int len = (int)strlen(buff);
  for (i = 0; i < len; i++)
  {
    for (j = 0; j < n; j++)
    {
      if (a[j] == buff[i])
      {
        b[j] = b[j] + 1;
        break;
      }
    }
    if (j >= n)
    {
      a[n] = buff[i];
      b[n] = 1;
      n++;
    }
  }
  cout << "字符和权值信息如下" << endl;
  for (i = 0; i < n; i++)
  {
    cout << "字符:" << a[i] << "  权值:" << b[i] << endl;
  }
  CreateHuffmanTree(HT, a, b);
  CreatHuffmanCode(HT);
  cout << "文字编码为:\n";
  for (int i = 0; i < len; i++)
  {
    for (int j = 0; j < n; j++)
    {
      if (buff[i] == HT[j].letter)
      {
        cout << HT[j].code;
        break;
      }
    }
  }
  cout << "\n译码:" << endl;
  while (1)
  {
    cout << "请输入要译码的二进制字符串,输入'#'结束:";
    x = 1;
    k = 0; 
    symbol = 1;
    while (symbol) 
    {
      cin >> p;
      if (p != '1' && p != '0' && p != '#') 
      {
        x = 0;
      }
      coding[k] = p;
      if (p == '#')
        symbol = 0;
      k++;
    }
    if (x == 1) 
    {
      HuffmanTreeDecode(HT, coding, k - 1);
    }
    else 
    {
      cout << "有非法字符!" << endl;
    }
    cout << "是否继续?(Y/N):";
    cin >> p;
    if (p == 'y' || p == 'Y')
      continue;
    else
      break;
  }
  return 0;
}

图的基本操作

实验内容

分别用邻接矩阵和邻接表对如下有向图实现:

1.输出存储结果;

2.计算各结点的出度和入度,并输出;

3.实现图的深度优先遍历和广度优先遍历,并输出。

代码实现

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 50
int visit[MAXVEX];
int in_deg[MAXVEX];//入度
int out_deg[MAXVEX];//出度 
typedef struct
{
  int vertices[MAXVEX];
  int arc[MAXVEX][MAXVEX];
  int vexnum, arcnum;
}MGraph;
typedef struct queue
{
  int* pBase;
  int front, rear;
}QUEUE;
void init_queue(QUEUE* Q)
{
  Q->pBase = (int*)malloc((sizeof(int)) * MAXVEX);
  Q->front = 0;
  Q->rear = 0;
}
bool isfull_queue(QUEUE* Q)
{
  if (((Q->rear + 1) % MAXVEX) == Q->front)
    return true;
  else
    return false;
}
bool isempty_queue(QUEUE* Q)
{
  if (Q->rear == Q->front)
    return true;
  else
    return false;
}
void in_queue(QUEUE* Q, int val)
{
  if (isfull_queue(Q))
    return;
  Q->pBase[Q->rear] = val;
  Q->rear = (Q->rear + 1) % MAXVEX;
}
int out_queue(QUEUE* Q)
{
  int temp = 0;
  if (isempty_queue(Q))
    return 0;
  temp = Q->pBase[Q->front];
  Q->front = (Q->front + 1) % MAXVEX;
  return temp;
}
void BFS(MGraph G, QUEUE* Q, int v)
{
  if (!visit[v]) {
    visit[v] = 1;
    printf("%d  ", G.vertices[v]);
    in_queue(Q, v);
  }
  while (!isempty_queue(Q)) {
    int temp = out_queue(Q);
    for (int i = 0; i < G.vexnum; i++) {
      if (G.arc[temp][i] != 0 && !visit[i]) {
        visit[i] = 1;
        printf("%d  ", G.vertices[i]);
        in_queue(Q, i);
      }
    }
  }
}
void BFST(MGraph G, QUEUE* Q)
{
  printf("\nBFS的遍历:");
  int i = 0;
  for (i = 0; i < G.arcnum; i++)
    visit[i] = 0;
  for (i = 0; i < G.vexnum; i++) {
    if (!visit[i])  BFS(G, Q, i);
  }
}
int LocateVex(MGraph G, int v)
{
  for (int i = 0; i < G.vexnum; i++) {
    if (G.vertices[i] == v)
      return i;
  }
  return 0;
}
void CreatMGraph(MGraph* G)
{
  int i = 0, j = 0;
  printf("请分别输入顶点数和边数: \n");
  scanf("%d%d", &(G->vexnum), &(G->arcnum));
  printf("请输入顶点信息:\n");
  for (i = 0; i < G->vexnum; i++)
    scanf("%d", &(G->vertices[i]));
  for (i = 0; i < G->vexnum; i++) {
    for (j = 0; j < G->vexnum; j++)
      G->arc[i][j] = 0;
  }
  printf("请输入构成边的两个顶点:  \n");
  for (i = 0; i < G->arcnum; i++) {
    int num, num1;
    scanf("%d%d", &num, &num1);
    int j = LocateVex(*G, num);
    int k = LocateVex(*G, num1);
    G->arc[j][k] = 1;
  }
}
void PrintMGraph(MGraph G)
{
  printf("*************************\n");
  printf("邻接矩阵的遍历:\n");
  for (int i = 0; i < G.vexnum; i++) {
    for (int j = 0; j < G.vexnum; j++) {
      printf("%d  ", G.arc[i][j]);
      if (G.arc[i][j] != 0)
        out_deg[i]++;
      if (G.arc[j][i] != 0)
        in_deg[i]++;
    }
    printf("\n");
  }
  printf("*************************\n");
}
void Print_in_out_deg(MGraph G)
{
  printf("\n*************************\n");
  printf("各顶点的度的遍历:\n");
  for (int i = 0; i < G.vexnum; i++) {
    printf("\n第%d条边的入度: %d 与出度: %d\n", i + 1, in_deg[i], out_deg[i]);
  }
  printf("*************************\n");
}
void DFS(MGraph G, int v)
{
  visit[v] = 1;
  printf("%d  ", G.vertices[v]);
  for (int i = 0; i < G.vexnum; i++) {
    if (G.arc[v][i] != 0 && visit[i] == 0)
      DFS(G, i);
  }
}
void DFST(MGraph G)
{
  printf("DFS的遍历:");
  for (int i = 0; i < G.vexnum; i++) {
    if (!visit[i])
      DFS(G, i);
  }
}
int main()
{
  MGraph G;
  QUEUE Q;
  init_queue(&Q);
  CreatMGraph(&G);
  PrintMGraph(G);
  DFST(G);
  BFST(G, &Q);
  Print_in_out_deg(G);
  return 0;
}


相关文章
|
5天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
64 9
|
20天前
|
存储 算法 C语言
通义灵码在考研C语言和数据结构中的应用实践 1-5
通义灵码在考研C语言和数据结构中的应用实践,体验通义灵码的强大思路。《趣学C语言和数据结构100例》精选了五个经典问题及其解决方案,包括求最大公约数和最小公倍数、统计字符类型、求特殊数列和、计算阶乘和双阶乘、以及求斐波那契数列的前20项和。通过这些实例,帮助读者掌握C语言的基本语法和常用算法,提升编程能力。
|
4天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
43 16
|
4天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
32 8
|
7天前
|
存储 C语言
【数据结构】手把手教你单链表(c语言)(附源码)
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构,每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作,如头插、尾插、头删、尾删、查找、指定位置插入和删除等,并提供了完整的C语言代码示例。通过学习单链表,可以更好地理解数据结构的底层逻辑,提高编程能力。
32 4
|
8天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
32 3
|
9天前
|
存储 算法 C语言
C语言数据结构(2)
【10月更文挑战第21天】
|
20天前
|
存储 算法 C语言
【趣学C语言和数据结构100例】
《趣学C语言和数据结构100例》精选5个编程问题,涵盖求最大公约数与最小公倍数、字符统计、特殊序列求和及阶乘计算等,通过实例讲解C语言基础与算法思维,适合初学者实践学习。
|
26天前
|
算法 搜索推荐 Java
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
这篇文章介绍了如何使用Java后端技术,结合Graphics2D和Echarts等工具,生成包含个性化信息和图表的海报,并提供了详细的代码实现和GitHub项目链接。
91 0
java 后端 使用 Graphics2D 制作海报,画echarts图,带工具类,各种细节:如头像切割成圆形,文字换行算法(完美实验success),解决画上文字、图片后不清晰问题
|
7天前
|
C语言
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
24 0