数据结构实验题目

《数据结构》实验题目

实验一 客房管理（链表）

? 实验目的：熟练掌握单循环链表操作的基本算法实现。

? 实现功能：以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ? 实验机时：8 ? 设计要求：

(1)定义客房链表结点结构类型，以Hotel和*HLink命名，数据域：客房名称roomN、标准价格Price、入住价格PriceL(默认值=标准价格*80%)、床位数Beds、入住状态State(空闲、入住、预订，默认值为空闲)，指针域：*next；

(2)实现创建客房基本情况链表函数void Build(HLink &H)，输入客房名称、标准价格、床位数，将入住价格、入住状态修改为默认值，建议用文件操作来输入数据；

(3)实现函数void updateH(HLink &H, int beds, char *state)，将床位数为beds的客房入住状态改为state；

(4)实现输出客房基本情况函数void Exp(HLink H)，输出所有客房的客房名称、标准价格、入住价格、床位数、入住状态；

(5)函数void Add(HLink &H)，将该链表中未入住的客房入住价格均加价20%；

(6)函数void upBed(HLink &H,int beds)，将该链表床位数不超过beds的结点都放在床位数超过beds的结点后面；

(7)求出入住价格最高的客房函数HLink FirstH(HLink &H)，该函数内return语句返回入住价格最高的客房结点指针，返回前将该结点在链表中删除；

(8) 函数void MoveK1(HLink &H, int k)，将单链表中倒数第k个结点移到第一个结点位置，注意：严禁采用先计算链表长度n再减k（即n-k）的方法；

(9) 函数void ReverseN2(HLink &H)，将单链表的正中间位置结点之后的全部结点倒置的功能，注意：严禁采用先计算链表长度n再除以2（即n/2）的方法；

(10)主控函数main()调用以上函数，输出（3）(beds=2，state=\入住\、（5）、（6）、（7）、（8）、（9）处理后的链表内容、输出入住价格最高的客房基本情况。

可能用到的函数： 从文件中读取客房数据：fscanf(文件指针,\ 输出客房数据：printf(\ 字符串赋值函数：char* strcpy(char *, const char *); 字符串比较函数：int strcmp(const char *, const char *)

#include #include #include

//定义客房链表结点结构 typedef struct HNode { char roomN[7]; //客房名称 float Price; //标准价格 float PriceL; //入住价格(默认值=标准价格*80%) int Beds; //床位数Beds char State[5]; //入住状态(值域：\空闲\、\入住\、\预订\，默认值为\空闲\ struct HNode *next; //指针域 }Hotel, *HLink;

实验二、串模式匹配算法（串）

? 实验目的：熟练掌握串模式匹配算法。

? 实现功能： 从主串中第K个字符起，求出子串在主串中首次出现的位置，即模式匹配或串匹配。 ? 要求用三种模式匹配算法分别实现：

? 朴素的模式匹配算法（BF算法） ? KMP改进算法(Next[ ]) ? KMP改进算法(NextVal[ ]) ? 实验机时：6 ? 设计要求：

首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。 程序运行后，给出5个菜单项的内容和输入提示：

1．输入主串、子串和匹配起始位置 2．朴素的模式匹配算法 3．KMP改进算法(Next[ ]) 4．KMP改进算法(NextVal[ ]) 0．退出管理系统 请选择0—4：

? 菜单设计要求：使用数字0—4来选择菜单项，其它输入则不起作用。

实验三、求二叉树上结点的路径（二叉树）

? 实验目的：熟练掌握二叉树应用的基本算法实现。

? 实现功能：在采用链式存储结构存储的二叉树上，以bt指向根结点，p指向任一给定的结点，编

程实现求出从根结点bt到给定结点p之间的路径。 ? 实验机时：6 ? 设计思路： 数据结构：

typedef struct node{ char data; //数据域 struct node *lchild , *rchild; //左右孩子指针 }BinTNode; //树中结点类型 typedef BinTNode *BinTree;

主要实现函数：

? 二叉树的建立

? ? ? ?

求指定结点路径

二叉树的前、中、后序遍历算法 查找函数

主控函数及运行环境设置

本文来源：https://www.bwwdw.com/article/up1f.html