---
title: "01-数据结构实验"
created: 2026-01-13
tags:
  - 博客

---
# 数据结构实验

练习1：请用广度遍历算法，遍历出以下无向图,可以查看附件文件，此文件中包含建立邻接表和队列的基本操作，参考提供的代码，实现图的遍历。

![[image-0d856096.png]]

![[image-a23aea76.png]]

练习2：
请用快速排列算法对序列{ 8,6,3,7,15,12}进行从小到大排序，编写完整代码。

![[image-cc265794.png]]

第三类

请用递归算法中序遍历树t，并求出树t的高度。
t用括号法表示的字符串为“A(B(D(,G)),C(E,F))”。
参考代码如下

```
#include <stdio.h>
#include <stdlib.h>

typedef struct BTNode {
   char data;
   struct BTNode* lchild;
   struct BTNode* rchild;
} BTNode;

void PreOrder(BTNode* b) {
   if (b != NULL) {
       printf("%c ", b->data); // 输出当前节点的值
       PreOrder(b->lchild); // 递归遍历左子树
       PreOrder(b->rchild); // 递归遍历右子树
   }
}

int BTHeight(BTNode* b) {
   if (b == NULL)
       return 0; // 空树的高度为0
   else {
       int lchilddep = BTHeight(b->lchild); // 左子树的高度
       int rchilddep = BTHeight(b->rchild); // 右子树的高度
       return (lchilddep > rchilddep) ? (lchilddep + 1) : (rchilddep + 1); // 返回左右子树中较大的高度加1
   }
}

BTNode* CreateBTree(char* str, int* index) {
   BTNode* newNode = NULL;
   if (str[*index] != '\0' && str[*index] != ')') {
       newNode = (BTNode*)malloc(sizeof(BTNode));
       newNode->data = str[*index];
       newNode->lchild = NULL;
       newNode->rchild = NULL;

       (*index)++;

       if (str[*index] == '(') {
           (*index)++;
           newNode->lchild = CreateBTree(str, index); // 递归创建左子树
       }

       (*index)++;

       if (str[*index] == '(') {
           (*index)++;
           newNode->rchild = CreateBTree(str, index); // 递归创建右子树
       }

       (*index)++;
   }
   return newNode;
}

int main() {
   BTNode* b = NULL;
   char str[20] = "A(B(D(,G)),C(E,F))";
   int index = 0;
   b = CreateBTree(str, &index); // 创建二叉树

   PreOrder(b); // 前序遍历二叉树
   printf("\n");

   int height = BTHeight(b); // 计算二叉树的高度
   printf("%d\n", height);

   return 0;
}
```

请用递归算法（先序、中序、后序）遍历树t，并求出树t的高度。
t用括号法表示的字符串为“A(B(D(E,F),C(G,)))”。
参考代码如下