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

#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;
}

#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;
}