算法记录

基于线性表的图书信息管理

选用顺序表或链表实现线性表的的基本操作。

图书信息表的创建和输出

InitList()用来初始化链表，CreateList_R(LinkList *L)利用后插法来创建链表链表。

// 初始化链表
LinkList InitList()
{
    LinkList L = (LinkList)malloc(sizeof(LNode));
    if(L == NULL) {
        printf("链表初始化失败！\n");
        exit(0);
    }
    L->next = NULL; // 头指针设置为空
    printf("链表初始化成功！\n");
    return L;
}

// 后插法创建链表
int CreateList_R(LinkList *L)
{
    *L = InitList();
    LinkList r = *L; // 尾指针r指向头结点

    Book book;
    while(1)
    {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        if(p == NULL)
        {
            printf("创建链表时分配内存失败！\n");
            return ERROR;
        }
        scanf("%s %s %f", &book.no, &book.name, &book.price);
        // 吸收回车
        getchar();
        // 检查输入结束标志
        if(strcmp(book.no, "0") == 0 &&strcmp(book.name, "0") == 0 &&book.price == 0) {
            printf("\n");
            break;
        }
        p->data = book;
        p->next = NULL; // 新结点设置为尾结点，也就是新结点的指向NULL
        r->next = p; // 原来的尾结点指向新结点
        r = p; // 尾指针指向新结点
    }
    return 0;
}

测试截图：

图书信息表的修改

// 修改
void ChangePrice(LinkList L)
{
    float sum = 0, average = 0;
    int length = GetLength(L);
    LinkList p = L->next; // p指向首元节点
    while(p != NULL)
    {
        sum += p->data.price;
        p = p->next;
    }
    average = sum / length;
    printf("平均价格: %.2f\n", average);
    //printf("链表长度: %d", length);

    // 重新将p指向头结点
    p = L->next;
    while(p != NULL)
    {
        if( p->data.price < average )
            p->data.price *= 1.2;
        else if( p->data.price > average )
            p->data.price *= 1.1;
        p = p->next;
    }
    PrintList(L);
}

测试截图：

查找最贵图书

// 查找最贵图书
void FindHighPrice(LinkList L)
{
    float max = 0;
    int count = 0;
    LinkList p = L->next;
    // 找最大价格
    while(p != NULL)
    {
        if(p->data.price > max) {
            max = p->data.price;
            count = 1;
        }
        else if(p->data.price == max)
        {
            ++count;
        }
        p = p->next;
    }

    printf("%d\n", count);

    // 找最贵价格图书信息
    p = L->next; // 重置p到首元节点
    while(p != NULL)
    {
        if(p->data.price == max)
        {
            printf("%s %s %.2f\n", p->data.no, p->data.name, p->data.price);
        }
        p = p->next;
    }
}

图书入库

这里涉及到插入链表操作

// 新图书入库(插入)
int BookInsert(LinkList *L, int i, Book e)
{
    // 头指针
    LinkList p = *L;
    int j = 0;
    // 找第i-1个位置
    while(p && (j < i - 1))
    {
        p = p->next;
        ++j;
    }
    if(!p || j > i - 1)
        return ERROR;
    LinkList s = (LinkList)malloc(sizeof(LNode)); // 创建新结点
    if(s == NULL)
        return ERROR;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 0;
}

当插入位置不合法时会报错

旧图书出库

这里涉及删除链表结点操作

int BookDelete(LinkList *L, int i)
{
    // 头指针
    LinkList p = *L;
    int j = 0;
    // 找第i-1位置
    while( (p->next) && (j < i - 1) )
    {
        p = p->next;
        ++j;
    }

    // 当i大于链表长度或者i<1时，位置不合理
    if( !(p->next) || (j > i - 1) )
        return ERROR;
    LNode *q = p->next; // 临时保存被删除结点的地址;
    p->next = q->next;
    free(q);
    return 0;
}

同时删除位置不合法时也会报错

图书去重

思路是用一个二维字符数组来保存不同图书的ISBN号，设置一个前驱指针pre指向头结点，p指针指向首元节点，count做不同图书的数量计数器。然后遍历链表，将每个结点图书的ISBN号与已经保存在字符数组里的ISBN号进行比对，利用flag来确定图书是否找到。如果找到，flag=1，用一个中间指针temp保存这个结点，然后前驱指针跳过当前节点，p指针后移，free掉temp结点。没找到的话就把ISBN保存在数组里，然后count自增，更新前驱结点为当前结点，最后p后移。

// 根据ISBN对图书去重
void BookDuplicateDeleteByISBN(LinkList *L)
{
    char ISBNList[MAXSIZE][20]; // 存储ISBN
    int count = 0;
    // p指向首元节点
    LinkList p = (*L)->next;
    LinkList pre = *L; // 用来保存前驱结点

    while( p != NULL )
    {
        int flag = 0;
        for(int i = 0; i < count; i++)
        {
            if(strcmp(p->data.no, ISBNList[i]) == 0) {
                flag = 1; // 找到，标志设置为1
                break;
            }
        }

        if(flag) {
            LinkList temp = p;
            pre->next = p->next; // 前驱指针跳过当前结点
            p = p->next;
            free(temp);
        }
        else {
            // 如果当前书号没出现过，加入ISBN字符数组里
            strcpy(ISBNList[count], p->data.no);
            ++count; // 已访问书号数量增加
            pre = p; // 更新前驱结点为当前结点
            p = p->next; // 移动到下一个结点
        }
    }
}

一些辅助函数

// 获取链表长度
int GetLength(LinkList L)
{
    LinkList p = L->next;
    int length = 0;
    while(p != NULL) {
        ++length;
        p = p->next;
    }
    return length;
}
// 输出
void PrintList(LinkList L)
{
    int length = GetLength(L);
    printf("\n%d\n", length);
    // p重新指向头结点
    LinkList p = L->next;
    while(p != NULL)
    {
        printf("%s %s %.2f\n", p->data.no, p->data.name, p->data.price);
        p = p->next;
    }
}

主函数调用：利用switch-case来让用户通过序号选择不同的操作，每个case的思路大致相同，都是先创建链表CreateList_R()，然后再执行对应的操作函数，最后调用PrintList()输出整个链表。

Trouble Shooting

**问题：**图书去重时，刚开始利用了删除函数BookDelete()对图书删除，并且没有使用temp指针来暂存被删除结点，而且指针 p 和前驱 pre 没有正确更新，执行程序时，程序发生阻塞。

**解决办法：**利用temp指针暂存被删除节点，然后free(temp)删除，删除节点后，立即更新 p 指向下一个未被删除的节点。

基于栈的算术表达式求值

输入一个中缀算术表达式，求解表达式的值。运算符包括“+”、“-”、“*”、“/”、 “(”、“)”、“=”，参加运算的数为整数。

整体思路

定义了两个类型的栈OpStack（用来存储运算符）（char）、NumStack（用来存储操作数）（int）

基本操作有两套：

对于运算符栈：

初始化InitOpStack()

入栈PushOp(opStack s, char e)

出栈PopOp(opStack s, char *e)

取栈顶元素GetOpTop(opStack s)

对于操作数栈：

初始化InitNumStack()

入栈PushNum(numStack s, int e)

出栈PopNum(numStack s, int *e)

取栈顶元素GetOpTop(opStack s)

获取索引getIndex(char theta)

获取优先级getPriority(char theta1, char theta2)、计算函数Operate(int a, int b, char op)

核心是

初始化两个栈OPND和OPTR，一个存操作数另一个运算符，运算符栈初始时先压入一个 #

然后要给字符数组e的结尾追加#作为表达式的结尾识别。

循环读入表达式每一个字符

一、如果是数字就进OPND栈

累加数字组合为一个多位数，标记一个多位数。然后压入OPND栈

二、如果是运算符就进OPTR栈

调用getPriority()，将此时的OPTR栈顶元素与表达式中读入的运算符ch进行优先级比较

1. 如果栈顶运算符优先级高于ch，循环执行以下操作：

弹出OPTR运算符op
弹出OPND两个操作数a，b
调用Operate()函数，传入a，b，op三个元素进行计算，返回结果result
将结果result压入OPND栈

2. 如果栈顶运算符优先级低于ch，则ch入OPTR栈
3. 如果栈顶运算符优先级等于ch，弹出OPTR的括号
4. 最后弹出OPND的栈顶元素，即为运算结果

// 主计算函数
int Calculate(char e[])
{
    numStack OPND = InitNumStack();
    opStack OPTR = InitOpStack();
    PushOp(OPTR, '#');  // 初始化运算符栈

    char ch, op;
    int a, b, result = 0;
    int num = 0;
    int flag = 0; // 检测是否为多位数

    strcat(e, "#");

    for(int i = 0; e[i] != '\0'; i++)
    {
        ch = e[i];
        if (ch >= '0' && ch <= '9') {
            num = num * 10 + (ch - '0'); // 累加组合成多位数
            flag = 1;
        }
        else {
            if(flag) {
                PushNum(OPND, num);  // 压入操作数
                num = 0;
                flag = 0;
            }

            while(getPriority(GetOpTop(OPTR), ch) == '>') {
                PopOp(OPTR, &op);
                PopNum(OPND, &b);
                PopNum(OPND, &a);
                result = Operate(a, b, op);
                PushNum(OPND, result);
            }
            if (getPriority(GetOpTop(OPTR), ch) == '<') {
                PushOp(OPTR, ch);  // 压入当前运算符
            } else if (getPriority(GetOpTop(OPTR), ch) == '=') {
                PopOp(OPTR, &op); // 出栈匹配
            }
        }
    }
    PopNum(OPND, &result);
    return result;
}

主函数

主函数定义一个字符数组e[]存储单条表达式，p[][]存储所有表达式
循环读入单条表达式，去除换行符，如果最终输入是单个=结束循环，然后将所有的单条表达式存储在二维字符数组p中

遍历p，调用Calculate()计算每条表达式的结果，最后输出。

int main()
{
    char e[MAXSIZE]; // 一条表达式 
    char p[MAXSIZE][MAXSIZE]; // 所有表达式
    int count = 0;

    printf("输入表达式，每行一个，以\"=\"结束：\n");
    while(1) {
        gets(e); // 读取一行表达式
        // 去除换行符
        e[strcspn(e,"\n")] = 0;

        if(strcmp(e, "=") == 0) {
            break;
        }

        strcpy(p[count++], e);
    }
    printf("计算结果为：\n");
    for(int i = 0; i <count; i++) {
        int result = Calculate(p[i]);
        printf("%d\n", result);
    }
    return 0;
}

Trouble Shooting

Q1

问题： OPTR栈顶元素与表达式ch操作符优先级比较时，没有循环执行操作，而使用的是switch-case，导致输出结果总是表达式的最后一个数字

解决办法：需要循环执行操作

Q2

问题：刚开始只定义了一个栈的结构体，最后导致字符和数字的转换问题，使程序出现问题。

解决办法：分别定义两个栈的结构体，分别存储运算符（char）和操作数（int）

Q3

问题：表达式没有以#结尾，导致运算错误

解决办法：使用strcat()函数，将#放在字符数组的末尾。

基于字符串模式匹配算法的病毒感染检测问题（KMP算法）

研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列，然后检测某种病毒DNA

序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。例如，假设病毒的DNA序列为baa，患者1的DNA序列为aaabbba则感染;患者 2 的DNA序列为 babbba，则未感染。（注意，人的DNA序列是线性的，而病毒的DNA序列是环状的）

预处理模式

因为病毒的DNA是环状的，所以它会存在多种形式。比如病毒环状DNA为abb，则匹配人类DNA时，病毒会出现abb、bba、bab三种情况。这时可以把病毒的DNA扩充一倍，然后通过病毒DNA长度次循环，将环状DNA所有可能出现的形式通过strncpy(patterns[i], v_double + i, *len_v);保存在一个二维数组里作为模式串。

// 输入DNA序列，因为病毒为环状，所以病毒DNA需要拼接
void PreProcess(char h[], char v[], int *len_h, int *len_v, int *num, char patterns[][200])
{
    
    *len_v = strlen(v);

    // 对病毒环状DNA拼接
    char *v_double = (char *)malloc(strlen(v) * 2 + 1);
    if (v_double == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    strcpy(v_double, v); // 病毒DNA复制到新数组
    strcat(v_double, v); // 病毒DNA追加到末尾

    *len_h = strlen(h);

    // 生成所有可能的旋转形式
    *num = *len_v;
    int i = 0;
    for(i; i < *num; i++) {
        strncpy(patterns[i], v_double + i, *len_v); // 从v_double第i个位置复制len_v个字符到patterns[]里
        patterns[i][*len_v]= '\0';
    }

    free(v_double);
}

获取next数组

求next数组分为两种情况，一个是前后缀相同，另一种是前后缀不相同。

首先设置两个指针i和j，一个next[]数组。

next数组第0个元素初始化为-1（初始化-1，则kmp在匹配失败时，就会找匹配失败的字符对应的next数组中对应的值），i和j分别初始化为0和-1。

也就是i指向模式串第0个元素，j指向最前端。

对模式串进行遍历：

以aabaaf为例，求next数组的流程如下

// 获取next数组
void GetNext(int next[], char v[], int len_v)
{
    int i = 0, j = -1;
    next[0] = -1; // next初始化为-1

    while (i < len_v - 1) {
        if ((j == -1) || (v[i] == v[j])) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

KMP算法

首先利用GetNext() 获取模式串的next[]数组。

然后根据next[]数组，模式串（v[]）匹配字符串（h[]）

j指向v[]模式串，i指向h[]字符串。然后循环匹配，当h[i] != v[j]时候，j根据next[]数组进行回退（j = next[j]）

以aabaaf匹配aabaabaaf为例：

// KMP算法
int kmp(char h[], char v[], int len_v)
{
    int *next = (int *)malloc(len_v * sizeof(int));
    if (next == NULL) {
        printf("next数组内存分配失败！");
        exit(0);
    }
    GetNext(next, v, len_v);

    int i = 0, j = 0;
    int len_h = strlen(h);
    while (i < len_h && j < len_v ) {
        if (j == -1 || h[i] == v[j]) {
            i++;
            j++;
        } else {
            j = next[j]; // 根据next数组回退
        }
    }

    free(next);

    return j == len_v;
}

主函数调用

主函数定义 h[],v[]分别用来存储人类DNA和病毒DNA

patterns[][]用来保存环状病毒DNA的不同组合形式的模式串。

循环读入：

病毒DNA和人类DNA,以0，0结束输入。然后调用PreProcess()对病毒DNA进行处理，把所有的模式串情况保存在patterns[][]里。然后调用kmp()对模式串(patterns[i])与人类DNA（h[]）进行匹配，如果匹配成功，found=1

然后新定义一个result[][]用来批量保存匹配结果(YES/NO)，最后遍历result[][]。

int main()
{
    char h[100], v[200];
    char patterns[100][200];
    int len_h, len_v, num;
    int count = 0;
    char result[100][10];

    while(1) {
        scanf("%s %s", v, h);

        if(strcmp(v, "0") == 0 &&strcmp(h, "0") == 0 ) {
            printf("\n");
            break;
        }

        PreProcess(h, v, &len_h, &len_v, &num, patterns);

        int i = 0, found = 0;
        for (i; i < num; i++) {
            if (kmp(h, patterns[i], len_v)) {
                found = 1;
                break;
            }
        }

        if (found) {
            strcpy(result[count], "YES");
        } else {
            strcpy(result[count], "NO");
        }
        count++;
    }

    int k = 0;
    for(k; k < count; k++)
        puts(result[k]);
    return 0;
}

Trouble Shooting

**问题：**在开始时仅仅对病毒DNA进行了扩充，但是没有找环状DNA所有可能出现的形式，导致KMP无法正确匹配。

**解决：**利用循环，寻找扩充后的病毒DNA的所有可能出现的形式。

// 生成所有可能的旋转形式

  *num = *len_v;

  int i = 0;

  for(i; i < *num; i++) {
     strncpy(patterns[i], v_double + i, *len_v); // 从v_double第i个位置复制len_v个字符到patterns[]里
     patterns[i][*len_v]= '\0';
  }

基于二叉树的表达式求值算法

输入一个表达式(表达式中的数均为小于10的正整数)，利用二叉树来表示该表达式，创建表达式树，然后利用二叉树的遍历操作求表达式的值。

基本操作函数

定义二叉树和栈的结构体，注意栈的结构体中，栈顶指针和栈底指针的类型为二叉树指针类型。

typedef struct Node
{
  char data;
  struct Node *leftChild; // 左子树指针
  struct Node *rightChild; // 右子树指针
} BiTreeNode, *BiTree;

typedef struct
{
  BiTree *base;
  BiTree *top;
  int stacksize;
} SqStack, *Stack;

定义栈的基本操作：

初始化InitStack()

入栈Push(Stack s, BiTree e)

出栈Pop(Stack s, BiTree *e)

取栈顶元BiTree GetTop(Stack s)

清空栈DestroyStack(Stack s)

定义获取优先级函数：

获取索引int getIndex(char theta)

比较优先级char getPriority(char theta1, char theta2)

二叉树操作函数：

创建表达式树BiTree CreateExpTree(BiTree a, BiTree b, char ch)

创建节点BiTree CreateNode(char data)

这两个函数类似

递归释放root void FreeTree(BiTree root)

核心函数：

初始化表达式树void InitExpTree(char e[], BiTree *root)

表达式计算int GetValue(int a, int b, char op)

后序遍历表达式树求值int EvaluateExpTree(BiTree T)

核心函数思路

表达式树的创建

实现方法与利用栈计算表达式方法类似

首先把e[]复制到e_copy[]中，操作e_copy[]

初始化两个栈:EXPT用来存储建立好的表达式树的根节点，OPTR用来暂存运算符。刚开始向OPTR压入一个数据域为#的结点（CreateNode(‘#’)）

然后循环读入表达式e_copy[]每一个字符

一、 如果是数字就进EXPT栈

把数字封装为结点压入

二、 如果是运算符

调用getPriority()，将此时的OPTR栈顶指针的数据域与表达式中读入的运算符ch进行优先级比较

1. 如果栈顶运算符结点数据域优先级高于ch，循环执行以下操作：

弹出OPTR运算符结点op_node

弹出EXPT两个操作数结点a，b

调用CreateExpTree(a, b, op_node->data);函数，传入a，b，op_node的数据域三个元素进行表达式树创建，返回其根节点T

将根节点T压入EXPT栈

2. 如果栈顶运算符结点数据域优先级低于ch，则ch结点入OPTR栈
3. 如果栈顶运算符结点数据域优先级等于ch，弹出OPTR的括号结点
4. 最后弹出EXPT的栈顶结点，即为最终表达式树的根节点

最后摧毁两个栈

void InitExpTree(char e[], BiTree *root)
{
  char e_copy[MAXSIZE];
  strcpy(e_copy, e);
  strcat(e_copy, "#");
 
  Stack EXPT = InitStack();
  Stack OPTR = InitStack();
 
  Push(OPTR, CreateNode('#'));
  
  char ch;
  BiTree T = NULL, a, b, op_node;
  int i = 0;
 
  for (i = 0; e_copy[i] != '\0'; i++)
  {
    ch = e_copy[i];
    if (ch >= '0' && ch <= '9')
    {
      T = CreateNode(ch);
     Push(EXPT, T);
    }
   else
   {
      while (getPriority(GetTop(OPTR)->data, ch) == '>')
     {
       Pop(OPTR, &op_node);
       Pop(EXPT, &b);
       Pop(EXPT, &a);
       T = CreateExpTree(a, b, op_node->data);
       Push(EXPT, T);
     }
     if (getPriority(GetTop(OPTR)->data, ch) == '<')
     {
        Push(OPTR, CreateNode(ch));
     }
      else if (getPriority(GetTop(OPTR)->data, ch) == '=')
      {
        Pop(OPTR, &op_node);
      }
    }
  }

  Pop(EXPT, root);
  DestroyStack(EXPT);
  DestroyStack(OPTR);

}

后序遍历表达式树

设置变量lvalue、rvalue记录左子树和右子树的值，初始均为0

如果当前结点为叶子，则返回该结点的值。否则执行以下操作：

• 递归计算左子树的值记为lvalue。
• 递归计算右子树的值记为rvalue。

根据当前结点运算符的类型，将lvalue、rvalue传入计算函数GetValue进行计算。最后返回结果result。

// 后序遍历表达式树求值
int EvaluateExpTree(BiTree T)
{
    if (T == NULL)
    {
        printf("表达式树为空！\n");
        exit(0);
    }

    int lvalue = 0, rvalue = 0;
    if (T->leftChild == NULL && T->rightChild == NULL)
    {
        return T->data - '0'; // 如果结点为操作数，则返回该结点的数值
    }
    else
    {
        lvalue = EvaluateExpTree(T->leftChild);
        rvalue = EvaluateExpTree(T->rightChild);

        int result = GetValue(lvalue, rvalue, T->data);
        return result;
    }
}

主函数

循环输入表达式，然后删除表达式末尾的=，当输入仅为=时停止输入。接着定义一个BiTree指针类型的root，将其设置为NULL。先初始化表达式树InitExpTree(e, &root)，然后后序遍历二叉树计算结果EvaluateExpTree(BiTree T)，将结果保存在results[]数组里。

最后遍历results[]数组，输出答案。

int main()
{
    printf("请输入表达式，最后以 = 结束所有表达式输入:\n");
    int results[MAXSIZE];
    int count = 0;
    while(1)
    {
        char e[MAXSIZE];
        gets(e);
        int len = strlen(e);
        if (len > 0 && e[len - 1] == '=') {
            e[len - 1] = '\0';  // 将 '=' 替换为字符串结束符
        }

        if(len == 1) {
            break;
        }

        BiTree root = NULL;
        InitExpTree(e, &root);
        int result = EvaluateExpTree(root);
        results[count++] = result;
    }
    printf("表达式的值为\n");
    int i = 0;
    for(i; i < count; i++) {
      printf("%d\n", results[i]);
    }
    return 0;
}

Trouble Shooting

Q1

问题1：刚开始时栈结构体栈顶指针和基指针没有选择BiTree而是char类型，并且入栈、出栈和取栈顶元素操作也都是针对char类型的元素，导致创建表达式树时出现的错误 0xC0000005 表示访问冲突错误（即段错误）。

**解决：**栈结构体栈顶指针和基指针设置为BiTree，并且在字符入栈时，先利用BiTree CreateNode(char data)将字符封装成结点，在进行入栈操作。

Q2

**问题2：**初始化表达式树时直接修改表达式字符数组e[]，导致字符数组e直接被更改，最后结果会变成表达式最后一部分的结果。

**解决：**新定义一个字符数组e_copy[]，对e_copy[]进行操作。

Q3

**问题3：**主函数接受表达式时不能正确处理=，导致访问冲突错误。只有没有=的表达式才能正确进行计算。

**解决：**先接受含有=的表达式，然后将表达式的=删除（即替换为\0）。

if (len > 0 && e[len - 1] == '=') 
	e[len - 1] = '\0'; // 将 '=' 替换为字符串结束符

基于哈夫曼树的数据压缩算法

输入一串字符串，根据给定的字符串中字符出现的频率建立相应的哈夫曼树， 构造哈夫曼编码表，在此基础上可以对压缩文件进行压缩(即编码)，同时可以对 压缩后的二进制编码文件进行解压(即译码)。

操作函数

定义结构体

// 哈夫曼树
typedef struct
{
    int weight; // 结点权重
    int parent, lchild, rchild; // 结点的双亲、左孩子、右孩子
}HTNode, *HFTree;

// 哈夫曼编码表
typedef char **HuffmanCode;

// 统计字符出现的次数

void Weight(char *str, int count[])

// 选择函数，选择权值小的两个结点构造哈夫曼树

void Select(HTNode HT[], int m, int *s1, int *s2)

// 构建哈夫曼树

void CreateHuffmanTree(HFTree *HT, int count[], int n)

// 哈夫曼编码

void CreateHuffmanCode(HFTree HT, HuffmanCode *HC, int n)

// 编码字符串

void Encode(HuffmanCode HC, int count[], char *str, char *encoded)

// 译码字符串

void Decode(HFTree HT, char s[], char a[], int n)

各个函数的实现思路

统计字符出现的次数

void Weight(char *str, int count[])

思路：

遍历字符串str，每遇到一个字符，将其和字符a做减法后的结果作为count[]的下标，然后进行自加计数。

选择权值小的两个结点构造哈夫曼树

void Select(HTNode HT[], int m, int *s1, int *s2)

思路：

先初始化两个较大数min1和min2，用于记录最小和次小的权重值。

s1和s2用于记录找到的两个最小权重结点的索引，以便在后续操作中可以方便地访问和处理这两个节点。（在构建哈夫曼树要用到）

然后遍历数组HT，它的长度是m，对于每个没有父节点的结点：

如果它的权重小于min1，那么更新min1和min2以及他们对应的索引s1和s2

如果权重小于min2，只更新min2和*s2

构建哈夫曼树

void CreateHuffmanTree(HFTree *HT, int count[], int n)

count[]记录字频，n表示字符种类的数量，用于确定哈夫曼树的叶子节点数量。

整体思路：

初始化：也就是先动态申请2n个单元（HTNode），然后循环2n – 1次，从1号单元开始，依次将1到2n-1所有单元中的双亲、左孩子、右孩子的下标都初始化为0；最后再循环n次，将count[]中的字频填入到前n个单元中的叶子结点的权值(*HT)[index++].weight = count[i]

创建树：循环n-1次（n+1到2n-1），通过n-1次选择、删除与合并来创建哈夫曼树。

选择就是Select函数实现的功能。在HT[k](1 <= k <= i-1)中选择两个双亲域为0且权值最小的结点，并返回他们在HT中的序号s1和s2

然后得到新结点i，从森林里删除s1，s2，将s1和s2的双亲域从0改成i，改成i以后Select就不会选中他们了。（Select对于每个没有父节点的结点才会执行操作）

接下来s1，s2分别作为i的左右孩子

最后i的权值作为左右孩子权值之和。

哈夫曼编码

void CreateHuffmanCode(HFTree HT, HuffmanCode *HC, int n)

思路：

这里的n表示哈夫曼树的叶子节点个数（即需要编码的字符数量）

首先为HC（存储哈夫曼编码）（分配n+1，存储n个字符编码）和字符串temp（临时存放每个字符编码）分配空间，并且将它的n-1置为结束符

遍历所有节点，逐个字符求哈夫曼编码：

start指向temp数组的末尾，因为编码是逆序生成的。c表示当前结点索引，p指向当前结点c的父结点。

接下来从叶子结点开始向上回溯，直到根节点（根节点的 parent 为 0）

判断如果当前结点是父节点左孩子，则编码为0

判断如果当前结点是父节点右孩子，则编码为1

接下来更新当前结点为父结点（c=p;p=HT[p].parent），继续向上回溯。

这样可以求出第i个在字符的编码

然后为当前结点分配内存存储编码，长度为n – start（就是编码的实际长度），将求得的编码从临时空间temp中复制到HC[i]中

释放临时空间temp

编码字符串

void Encode(HuffmanCode HC, int count[], char *str, char *encoded)

HC保存哈夫曼编码表，count[]保存字频，str为待编码的字符串，encoded保存编码结果

首先将encoded初始化

然后遍历字符串str：

如果当前字符在a到z之间，通过str[i] – ‘a’计算出str[i]在HC中的位置，通过HC[str[i] - ‘a’ + 1] 获取该字符对应的哈夫曼编码（+1 是因为数组 HC 从 1 开始存储编码，而不是从 0 开始）。

然后使用strcat将当前字符的哈夫曼编码追加到encoded字符串末尾。

译码

void Decode(HFTree HT, char s[], char a[], int n)

s[]为哈夫曼编码后的字符串，a[]为解码后的字符，n为哈夫曼树叶节点的数量

首先f指向哈夫曼的根节点2 * n – 1，因为哈夫曼的结点索引从1到2n-1

然后遍历编码字符串：

如果当前字符是 ‘0’，则移动到当前节点的左子树（f = HT[f].lchild）

如果当前字符是 ‘1’，则移动到当前节点的右子树（f = HT[f].rchild）

当f <= n时意味着已经到达叶子，这时已经找到了一个完整的字符编码，打印a[f]即为对应的字符。

然后f重置到根节点索引2 * n – 1

最后i自增，继续解析下一个字符

主函数

定义哈夫曼树HT，哈夫曼编码HC，str[][]保存所有待编码字符串。count[]统计字频。

输入遍历str[][]，每条字符串保存在str[i]里，当用户输入0时，结束输入

输出

遍历str的有效内容：

先调用Weight()统计字频，然后将字符种类个数保存在n中

接着调用CreateHuffmanTree(&HT, count, n)创建哈夫曼树，CreateHuffmanCode(HT, &HC, n)生成哈夫曼编码。

输出字频，遍历count[]即可

输出哈夫曼树的终态，遍历HT即可，访问它的权值、双亲、左右孩子

输出单个字符的编码，根据count[]循环，编码保存在HC中（HC[k+1]）

编码字符串，调用Encoded()

译码字符串，调用Decod()，这里的字符数组a[]需要初始化，它需要存储哈夫曼树叶节点对应的字符。哈夫曼树的叶节点代表的是经过编码的字符，所以 a[i] 存储了哈夫曼树第 i 个叶节点对应的字符

最后释放HT，循环释放HC[i]，最后释放HC

Trouble Shooting

Q1

**问题：**在输出单个字符的哈夫曼编码时出现了重复输出的情况

a:0 a:0 a:0 a:0 a:0 a:0 a:0 b:10 b:10 b:10 b:10 b:10 c:110 c:110 d:111 d:111 d:111 d:111

可以看出输出的次数和单个字符的频率相等

**解决办法：**原因是使用了二维字符数组，可能是循环打印逻辑出现了问题。既然输出的次数和单个字符的频率相等，可以复用输出字符频率的逻辑，输出单个字符的哈夫曼编码。

Q2

**问题：**构建哈夫曼树时传入的是HFTree HT，如果使用 HFTree HT，则是值传递，函数内部对 HT 的任何修改都不会影响到函数外部的原始数据。

解决办法：

• CreateHuffmanTree 使用 HFTree *HT：因为需要在函数内部动态分配内存给哈夫曼树，并将指针传递回调用者。使用指针可以修改调用者传入的指针变量。
• CreateHuffmanCode 使用 HFTree HT：因为此时哈夫曼树已经构建完成，不需要再修改指针本身，只需要访问其内容。直接传递指针即可。

基于Dijsktra算法的最短路径求解

一张地图包括n个城市，假设城市间有m条路径(有向图)，每条路径的长度已知。给定地图的一个起点城市和终点城市，利用 Dijsktra 算法求出起点到终点之间的最短路径。

基本操作函数

定义结构体

#define MVNum 100
#define MaxInt 32767

typedef char VertexType;

// 图
typedef struct
{
  VertexType vex[MVNum]; // 顶点表
  int arcs[MVNum][MVNum]; // 邻接矩阵，权重为整数
  int Vexnum; //顶点数
  int arcnum; // 边数
}MGraph;

函数定义

// 顶点下标查找函数

int LocateVex(MGraph *G, VertexType v)

// 创建有向图

void CreateGraph(MGraph *G)

// 打印图函数

void CreateGraph(MGraph *G)

// 展示最短路径函数

void displayPath(int dist[], int path[], MGraph *G, VertexType start)

// 查找当前最短路径函数

int FindMinDist(int dist[], int s[], int vexnum)

// Dijkstra算法

int FindMinDist(int dist[], int s[], int vexnum)

核心函数：Dijkstra

void Dijkstra(MGraph *G, VertexType start)
{
  int i, num;
  int loc;
  int min;
  int dist[MVNum]; // 最短路径长度数组
  int path[MVNum]; // 最短路径数组
  int s[MVNum]; // 集合S（1表示该顶点已处理，属于集合S； 0代表未处理，不属于集合S， 属于集合V-S）

  // 初始化dist和path
  loc = LocateVex(G, start);
  for(i = 0; i < G->Vexnum; i++)
  {
     dist[i] = G->arcs[loc][i];
     if(dist[i] != MaxInt)
       path[i] = loc;
     else
     	path[i] = -1;
  }

  // 初始化S数组
  for(i = 0; i < G->Vexnum; i++)
       s[i] = 0;
  s[loc] = 1;
  num = 1;

  // 第3步
  while(num < G->Vexnum)
  {
     // 在dist数组中查找其对应的s[i]=0,即未处理的最小值元素
     min = FindMinDist(dist, s, G->Vexnum);
     // 将找到的最短边所对应的顶点加入集合S
     s[min] = 1;

     // 加入新的顶点后，更新dist和path
     for(i = 0; i < G->Vexnum; i++)
     {
       if((s[i] == 0) && (dist[i] > dist[min] + G->arcs[min][i]))
       {
         dist[i] = dist[min] + G->arcs[min][i];
         path[i] = min;
       }
     }
     num++;
  }
  displayPath(dist, path, G, start);
}

几个重要的数组：

dist[]：最短路径长度数组（可以根据这个数组得出起点到终点的路径长度）

path[]：最短路径数组（记录了每个元素的前一个元素是谁，可以根据该数组一个一个向前推出整条路径）

s[]：集合s（1表示该顶点已处理，属于集合S； 0代表未处理，不属于集合S， 属于集合V-S。也就是u数组）

num：用来统计已经处理的顶点数。

min：保存最小顶点

函数整体过程：

以如下图为例

• 初始化dist[]和path[]

根据邻接矩阵初始化dist[]，也就是把邻接矩阵起点所在的那一行填充进dist。

如果dist[]有值，path[]初始化为起点0。dist[]为无穷大时，path[]初始化为-1

• 初始化s数组

先把s全部赋值为0，然后把起点0放进s数组。

s和u的表现形式是哪个元素被放进s数组，哪个元素的值就被赋为1，其他为0的元素就是u数组中的元素。

接下来num = 1，代表此时已经处理了一个顶点，num为1.

• 当已经处理的顶点数(num)小于图中的顶点数时，循环下面的操作：

先在dist[]数组中查找s[i] = 0，也就是说在u集合中找未处理的最小元素

然后把目前找到的最小元素放进s数组。放的操作形式是（比如要放2到s数组中，就把s中下标为为2的元素赋值为1，代表放入的操作）

加入新顶点后，更新dist和path。

从0到顶点数循环：如果该顶点在u集合里并且目前u中的最小顶点的长度与在邻接矩阵中最小顶点到该顶点的长度之和小于dist[]数组中当前顶点的长度时if((s[i] == 0) && (dist[i] > dist[min] + G->arcs[min][i]))，进行下面的操作：

更新当前顶点的长度（dist[i]），然后path数组中当前顶点的值赋值为刚才处理的最小顶点。也就是说当前顶点的前一个顶点是最小顶点。

然后num++，处理下一个顶点。

重要函数

• 在邻接矩阵中遍历查找v的下标

int LocateVex(MGraph *G, VertexType v)

• 创建有向图

void CreateGraph(MGraph *G)

整个过程就是在创建邻接矩阵arcs[][]

先做一些初始化工作：

用户输入图的顶点数和边数，然后输入顶点元素，再初始化邻接矩阵的所有元素为最大数（无穷）。

接下来输入路径以及路径长度：

用户输入两个顶点v1 ，v2以及路径长度，调用LocateVex()找到这两个顶点的下标，赋值给n和m，然后再把长度赋值给邻接矩阵中设置v1到v2的边的权值G->arcs[n][m] = w

• 查找当前最短路径函数

int FindMinDist(int dist[], int s[], int vexnum)

min刚开始初始化为一个很大的数

循环遍历所有顶点：

检查每个顶点是否在s中，即s[i] == 0，如果在s中，那就处理它

如果该顶点i的长度dist[i]小于当前的最小长度min，则更新min为dist[i]，并且将loc设置为当前顶点i的索引

最后返回当前最短路径的顶点loc，即 dist[] 数组中距离起点最近的尚未处理的顶点。

辅助函数

• 打印图

void Print(MGraph G)

也就是打印邻接矩阵，把最大数变为无穷，效果如下

第一行遍历打印顶点表vex[]

第二行先打印顶点vex[i]，然后再打印邻接矩阵arcs[i][j]

• 展示最短路径函数

void displayPath(int dist[], int path[], MGraph *G, VertexType start)

打印dist[]，path[]

打印最短路径：

路径通过path[]回溯，长度保存在dist[]

遍历循环所有顶点

1.通过不断将 loc 的值赋给 temp[j] 数组并更新 loc = path[loc]，我们追溯并记录路径。temp[] 数组存储了从 i 到起点的路径。

j = 0;
while(loc != -1)
{
  temp[j] = loc;
  loc = path[loc];
  j++;
}

2.检查特殊情况

如果 j - 1 == 0，意味着路径的长度为 1，即起点与目标顶点是同一个顶点。

如果 G->vex[temp[j-1]] == start，表示目标顶点与起点相同

如果 G->vex[temp[j-1]] != start，表示目标顶点不可达（path[i] 为 -1，即没有路径到达该顶点）

如果路径长度大于 1，表示从起点到目标顶点有有效路径，打印从起点到该顶点的路径。

从 temp[j-1] 到 temp[0] 输出路径（即倒序输出）

打印路径的总长度 dist[i]，即从起点到顶点 i 的最短路径距离。

在打印每个最短路径后，清空temp数组，以便进行下一个顶点的路径追溯。

主函数

创建图，也就是创建邻接矩阵CreateGraph(&G);

打印图Print(G);

输入起始点`start

然后调用Dijkstra(&G, start)，寻找最短路径。

四、实验实习结果及分析

利用Dijsktra 算法求出了任意起点到终点之间的最短路径。

基于广度优先搜索的六度空间理论验证

基本操作函数

结构体：

#include <stdio.h>
#include <stdlib.h>
#define MVNum 100
#define MaxInt 32767
#define ERROR -1

typedef int VertexType;

typedef struct
{
  int *base; // 队列存储空间
  int front;
  int rear;
} SqQueue, *Queue;

typedef struct
{
  VertexType vex[MVNum];   // 顶点表
  int arcs[MVNum][MVNum];  // 邻接矩阵，无向图
  int Vexnum;        // 顶点数
  int arcnum;        // 边数
} AMGraph;

基本操作函数

队列操作

// 初始化队列

Queue InitQueue()

// 入队

int Push(Queue q, int e)

// 出队

int Pop(Queue q, int *e)

图操作：

// 创建无向图

int CreateAMGraph(AMGraph *G)

核心函数：BFS

// BFS遍历图，计算到目标顶点的距离
// 类似树的层次遍历

float BFS(AMGraph *G, int s)
{
  int *len = (int *)malloc(sizeof(int) * G->Vexnum); // 记录到s的距离
  int state[G->Vexnum];               // 记录顶点是否被访问
  for (int i = 0; i < G->Vexnum; i++)
  {
     state[i] = 0;   // 未访问
     len[i] = MaxInt; // 初始距离设为无穷大
  }

  Queue Q = InitQueue();
  Push(Q, s - 1);  // s从1开始
  state[s - 1] = 1; // 标记已访问
  len[s - 1] = 0;  // 起始顶点距离为0

  while (Q->front != Q->rear)
  {
     int u;
     Pop(Q, &u);
     for (int j = 0; j < G->Vexnum; j++)
     {
       if (G->arcs[u][j] && !state[j])
       {
         state[j] = 1;    // 标记已访问
         len[j] = len[u] + 1; // 更新距离
         Push(Q, j);
       }
     }
  }
 
  int rs = 0;
  for (int i = 0; i < G->Vexnum; i++)
  {
     if (len[i] <= 6) // 只统计到6步的顶点
       rs++;
  }

  free(len);
  free(Q->base);
  free(Q);
  return (float)rs / G->Vexnum * 100;
}

核心函数过程：

先设置两个数组len[]用来保存到s的距离，state[]用来标记该顶点是否被访问过。

初始化一个队列，state[]全部记为0，注意len[]要全部初始化为无穷大，代表到s的距离全部为无穷大。

然后开始确定起点s，即将s - 1入队（代表从1开始），将len[s - 1]赋值为0，代表到起点的距离为0，state[s - 1]赋值为1代表已经访问过起点。

接下来进入循环：

如果队列不为空

u = 队头元素出队，u就是当前正在遍历的顶点

然后进入内层循环j：

如果u和j有边（通过邻接矩阵检查），并且没有被访问过

标记u被访问过（state[j] = 1），然后更新u到j的距离加1（从 s 到 j 的最短路径应该是从 s 到 u 的最短路径（即 len[u]）加上一条边（即从 u 到 j 的这条边）

然后将j入队，进行下一次循环

重要函数

// 创建无向图
int CreateAMGraph(AMGraph *G)
{
  int i, j;
  scanf("%d %d", &G->Vexnum, &G->arcnum); // 输入顶点数和边数
  if (G->Vexnum == 0 && G->arcnum == 0) // 输入结束标志
     return 0;
     
  for (i = 0; i < G->Vexnum; ++i)
     G->vex[i] = i + 1; // 顶点编号从1开始

  // 初始化邻接矩阵
  for (i = 0; i < G->Vexnum; i++)
     for (j = 0; j < G->Vexnum; j++)
       G->arcs[i][j] = 0; 
  // 构建邻接矩阵
  for (int k = 0; k < G->arcnum; ++k)
  {
     int v1, v2;
     scanf("%d %d", &v1, &v2);
     --v1;
     --v2; // 调整索引，因为C数组是从0开始的
     G->arcs[v1][v2] = 1;
     G->arcs[v2][v1] = 1; // 无向图
  }
  return 1;
}

无向图的创建，也就是创建邻接矩阵，有边就赋值为1。

主函数

int main()
{
  AMGraph G;
  int count = 0; // 记录输入的图的个数
  AMGraph graphs[10]; // 假设最多有 10 个图

  // 读取输入数据，直到 0 0
  while (1)
  {
     if (!CreateAMGraph(&G))
       break;
     graphs[count++] = G; // 将当前图保存到数组中
  }
 
  // 统一输出所有图的结果
  for (int g = 0; g < count; g++)
  {
     for (int i = 0; i < graphs[g].Vexnum; i++)
     {
       float p = BFS(&graphs[g], i + 1);
       printf("%d: %.2f%%\n", i + 1, p);
     }
     if (g != count - 1) // 每个图之间输出一个空行
       printf("\n");
  }
  return 0;
}

数据的统一输入和统一输出：

每一组数据就是一个图，保存在graphs[10]，count用来计图的个数。然后使用一个循环，保存用户输入的图。如果输入0 0，这是CreateAMGraph(&G)会返回0，此时输入结束。

然后遍历这几个图，然后对每个图graph[g]进行BFS，最后输出计算结果。

Trouble Shooting

Q1

**问题：**BFS算法中在初始化len数组时，全部初始为0导致最终计算结果错误。len数组用来保存到目标顶点的距离。

**解决：**应该将len数组初始化为无穷大。如果一个顶点的距离被赋值为0，意味着该顶点会被误认为是源顶点，也就是起点。