数据结构上机指导.docVIP

数 据 结 构 上 机 实 验 指 导 徐晓伟 编 2010年10月 目录 实验一 实现双链表各种基本运算的算法······························2 实验二 停车场管理程序············································5 实验三 构造哈夫曼树··············································9 实验四 实现图的遍历算法··········································11 实验五 实现哈希表的相关运算算法··································13 实验六 实现堆排序算法············································15 课程设计 用二叉树实现家谱的相关运算······························17 实验一 实现双链表各种基本运算的算法 一、实验目的 编写一个程序 algo1.ccp，实现双链表的各种基本运算，并在此基础啊上设计一个主程序完成如下功能： 初始化双链表h。 依次采用尾插入法插入a,b,c,d,e元素。 输出双链表h。 输出双链表h长度。 判断双链表h是否为空。 输出双链表h的第3个元素。 输出元素a的位置。 在第4个元素位置上插入f元素。 输出双链表h。 删除h的第3个元素。 输出双链表h。 释放双链表h。 二、实验内容 本程序的模块结构如图1.1所示，图中方框表示函数，方框中指出函数名，箭头方向表示函数间的调用函数关系，虚线方框表示文件的组成，既指出该虚线方框中的函数存放在哪个文件中。 algo1.ccp程序包含如下函数。 ·InitList(DLinkList *L):初始化双链表L。 ·DestroyList(DLinkList *L)：释放双链表L。 ·ListEmpty(DLinkList *L)：判断双链表L是否为空表。 ·ListLength(DLinkList *L)：返回双链表L的元素个数。 ·DispList(DLinkList *L)：输出双链表L。 ·GetElem(DLinkList *L,int i,ElemType e)：获取双链表L中第i个元素。 ·LocateElem(DLinkList *L,ElemType e)：在双链表L中查找元素e。 ·ListInsert(DLinkList *L,int i,ElemType e)：在双链表L中第i个位置插入元素e。 ·ListDelete(DLinkList *L,int i,ElemType e)：双链表L中删除第i个元素。 程序结构如下： /*文件名:algo1.cpp*/ #include stdio.h #include malloc.h typedef char ElemType; typedef struct DNode { ······ } DLinkList; void InitList(DLinkList *L) { ···贩?k } void DestroyList(DLinkList *L) { 贩贩贩 v } int ListEmpty(DLinkList *L) { 贩贩贩 in} int ListLength(DLinkList *L) { 贩贩贩 nt } void DispList(DLinkList *L) { 贩贩贩voi } int GetElem(DLinkList *L,int i,ElemType e) { 贩贩贩 i } int LocateElem(DLinkList *L,ElemType e) { 贩贩贩 i } int ListInsert(DLinkList *L,int i,ElemType e) { 贩贩贩 i } int ListDelete(DLinkList *L,int i,ElemType e) { 贩贩贩 i } void Sort(DLinkList *head) /*双链表元素排序*/ { ······ } exp1.ccp主程序结构如下： /*文件名:exp1.cpp*/ #include stdio.h #include malloc.h typedef char ElemType; typedef struct DNode { ······ } DLinkList; extern void InitList(DLinkList *L); extern void DestroyList(DLinkList *L); extern int ListEmpty(DLinkLi