数据结构与算法实验指导书70459.docx

1、数据结构与算法实验指导书70459计算机和信息学院实验一 顺序表【实验目的】熟练掌握线性表在顺序存储结构上的基本操作。【实验平台】操作系统：Windows2000或Windows XP开发环境：C或C+【实验内容及要求】顺序表的查找、插入和删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入和删除。具体实现要求：1. 从键盘输入10个整数，产生顺序表，并输出结点值。2. 从键盘输入1个整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到，则显示“找不到”。3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，

2、观察输出结果。4. 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。【参考框架】#include #include /顺序表的定义：#define ListSize 100 /表空间大小可根据实际需要而定，这里假设为100typedef int DataType; /DataType可以是任何相应的数据类型如int, float或chartypedef struct DataType dataListSize; /向量data用于存放表结点 int length; /当前的表长度SeqList;void main() SeqList L; int i,x; int

3、 n=10; /欲建立的顺序表长度 L.length=0; void CreateList(SeqList *L,int n); void PrintList(SeqList L,int n); int LocateList(SeqList L,DataType x); void InsertList(SeqList *L,DataType x,int i); void DeleteList(SeqList *L,int i); CreateList(&L,n); /建立顺序表 PrintList(L,n); /打印顺序表 printf(输入要查找的值：); scanf(%d,&x); i=L

4、ocateList(L,x); /顺序表查找 printf(输入要插入的位置：); scanf(%d,&i); printf(输入要插入的元素：); scanf(%d,&x); InsertList(&L,x,i); /顺序表插入 PrintList(L,n); /打印顺序表 printf(输入要删除的位置：); scanf(%d,&i); DeleteList(&L,i); /顺序表删除 PrintList(L,n); /打印顺序表/顺序表的建立：void CreateList(SeqList *L,int n) /在此插入必要的语句/顺序表的打印：void PrintList(SeqLis

5、t L,int n) /在此插入必要的语句/顺序表的查找：int LocateList(SeqList L,DataType x) /在此插入必要的语句/顺序表的插入：void InsertList(SeqList *L,DataType x,int i) /在此插入必要的语句/顺序表的删除：void DeleteList(SeqList *L,int i) /在此插入必要的语句【实验报告】数据结构和算法实验报告一学院： 班级： 学号： 姓名： 日期： 程序名： L2211.CPP 一、上机实验的问题和要求：顺序表的查找、插入和删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入和

6、删除。具体实现要求：5. 从键盘输入10个整数，产生顺序表，并输出结点值。6. 从键盘输入1个整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到，则显示“找不到”。7. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。8. 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。二、源程序及注释：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：实验二 链表【实验目的】熟练掌握线性表在链式存储结构上的基本操作。【实验平台】操作系统：Windows2000或Window

7、s XP开发环境：C或C+【实验内容及要求】单链表的查找、插入和删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入和删除。具体实现要求：9. 从键盘输入20个整数，产生带表头的单链表，并输出结点值。10. 从键盘输入1个整数，在单链表中查找该结点。若找到，则显示“找到了”；否则，则显示“找不到”。11. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。12. 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。13. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相

8、同，输出单链表所有结点值，观察输出结果。14. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。15. 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。16. （）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。【参考框架】#include #include /单链表的定义：typedef int DataType; /DataType可以是任何相应的数据类型如int, float或chartypedef st

9、ruct node /结点类型定义 DataType data; /结点的数据域 struct node *next; /结点的指针域ListNode;typedef ListNode *LinkList;void main() int i; DataType key,x; LinkList head; ListNode *p; LinkList CreateList(void); void PrintList(LinkList head); LinkList LocateNode(LinkList head,DataType key); LinkList GetNode(LinkList h

10、ead,int i); void InsertList(LinkList head,DataType x,int i); void DeleteList(LinkList head,int i); void DeleteManyList(LinkList head); void DeleteEvenList(LinkList head); void ChangeCircList(LinkList head); void PrintCircList(LinkList head); head=CreateList(); /建立单链表 PrintList(head); /打印单链表 printf(输

11、入要查找的值：); scanf(%d,&key); p=LocateNode(head,key); /单链表查找 printf(请输入欲插入元素的位置：); scanf(%d,&i); printf(请输入欲插入的元素：); scanf(%d,&x); InsertList(head,x,i); /单链表插入 PrintList(head); /打印单链表 printf(请输入欲删除结点的位置：); scanf(%d,&i); DeleteList(head,i); /单链表删除 PrintList(head); /打印单链表 DeleteManyList(head); /删除重复值 Prin

12、tList(head); /打印单链表 DeleteEvenList(head); /删除偶数值 PrintList(head); /打印单链表 ChangeCircList(head); /修改为循环单链表 PrintCircList(head); /打印循环单链表 /*void DivideList(LinkList head,LinkList *A,LinkList *B); /分割成两个单链表 DivideList(head, &A, &B); PrintList(A); PrintList(B); */单链表的建立：LinkList CreateList(void) /在此插入必要的

13、语句/单链表的打印：void PrintList(LinkList head) /在此插入必要的语句/单链表的查找1：LinkList LocateNode(LinkList head,DataType key) /在此插入必要的语句/单链表的查找2：LinkList GetNode(LinkList head,int i) /在此插入必要的语句/单链表的插入：void InsertList(LinkList head,DataType x,int i) /在此插入必要的语句/单链表的删除：void DeleteList(LinkList head,int i) /在此插入必要的语句/删除单链

14、表中重复值：void DeleteManyList(LinkList head) /在此插入必要的语句/删除单链表中偶数值：void DeleteEvenList(LinkList head) /在此插入必要的语句/修改为循环单链表：void ChangeCircList(LinkList head) /在此插入必要的语句/循环单链表的打印：void PrintCircList(LinkList head) /在此插入必要的语句/*/分割成两个单链表void DivideList(LinkList head,LinkList *A,LinkList *B); /在此插入必要的语句*/【实验报告

15、】数据结构和算法实验报告二学院： 班级： 学号： 姓名： 日期： 程序名： L2311.CPP 一、上机实验的问题和要求：单链表的查找、插入和删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入和删除。具体实现要求：1. 从键盘输入20个整数，产生带表头的单链表，并输出结点值。2. 从键盘输入1个整数，在单链表中查找该结点。若找到，则显示“找到了”；否则，则显示“找不到”。3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。4. 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出

16、结果。5. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。6. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。7. 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。8. （）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。二、源程序及注释：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：实验三 树【实验目的】熟练掌握在链式二叉树在二叉链表存

17、储结构上的基本操作。【实验平台】操作系统：Windows2000或Windows XP开发环境：C或C+【实验内容及要求】要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：17. 基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。18. 用广义表表示所建二叉树。19. 分别利用前序遍历、中序遍历、后序遍历所建二叉树。20. 求二叉树结点总数，观察输出结果。21. 求二叉树叶子总数，观察输出结果。22. 交换各结点的左右子树，用广义表表示法显示新的二叉树。2

18、3. （）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每个结点赋值：（注意要修改DataType类型）a) 叶结点的值为3b) 只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值c) 左、右孩子均有的结点，则其值等于左、右孩子结点的值之和d) 用广义表表示法显示所建二叉树【参考框架】#include #include /二叉树的链式存储表示typedef char DataType; /应由用户定义DataType的实际类型typedef struct node DataType data; struct node *lchild, *rchild; /左右孩子指

19、针 BinTNode; /结点类型typedef BinTNode *BinTree;void main() void ListBinTree(BinTree T); /用广义表表示二叉树 void DisplayBinTree(BinTree T); /用凹入表表示二叉树 void CreateBinTree(BinTree *T); /构造二叉链表 void Preorder(BinTree T); /前序遍历二叉树 void Inorder(BinTree T); /中序遍历二叉树 void Postorder(BinTree T); /后序遍历二叉树 int nodes(BinTree

20、 T); /计算总结点数 int leafs(BinTree T); /计算总叶子数 BinTree swap(BinTree T); /交换左右子树 BinTree T; printf(请输入先序序列（虚结点用空格表示）：n); CreateBinTree(&T); ListBinTree(T); printf(n); DisplayBinTree(T); printf(前序遍历：n); Preorder(T); printf(n); printf(中序遍历：n); Inorder(T); printf(n); printf(后序遍历：n); Postorder(T); printf(n);

21、 printf(二叉树的总结点数为%dn,nodes(T); printf(二叉树的总叶子结点数为%dn,leafs(T); T=swap(T); ListBinTree(T); printf(n);/构造二叉链表void CreateBinTree(BinTree *T) /在此插入必要的语句/用广义表表示二叉树void ListBinTree(BinTree T) /在此插入必要的语句/用凹入表表示二叉树void DisplayBinTree(BinTree T) /在此插入必要的语句/前序遍历二叉树void Preorder(BinTree T) /在此插入必要的语句/中序遍历二叉树vo

22、id Inorder(BinTree T) /在此插入必要的语句/后序遍历二叉树void Postorder(BinTree T) /在此插入必要的语句/计算总结点数int nodes(BinTree T) /在此插入必要的语句/计算总叶子数int leafs(BinTree T) /在此插入必要的语句/交换左右子树BinTree swap(BinTree T) /在此插入必要的语句【实验报告】数据结构和算法实验报告三学院： 班级： 学号： 姓名： 日期： 程序名： L61.CPP 一、上机实验的问题和要求：要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子

23、及结点总数的操作等。具体实现要求：i. 基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。ii. 用广义表表示所建二叉树。iii. 分别利用前序遍历、中序遍历、后序遍历所建二叉树。iv. 求二叉树结点总数，观察输出结果。v. 求二叉树叶子总数，观察输出结果。vi. 交换各结点的左右子树，用广义表表示法显示新的二叉树。vii. （）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每个结点赋值：（注意要修改DataType类型）a. 叶结点的值为3b. 只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值

24、c. 左、右孩子均有的结点，则其值等于左、右孩子结点的值之和d. 用广义表表示法显示所建二叉树二、源程序及注释：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：实验四 Huffman树【实验目的】理解建立Huffman树的算法。【实验平台】操作系统：Windows2000或Windows XP开发环境：C或C+【实验内容及要求】阅读理解建立Huffman树的算法，对该算法进行运行及调试。具体实现要求：1. 调试并运行Huffman算法。2. （）求Huffman树的带权路径长度WPL。【参考框架】#include #include #include /Huffman树的存储结

25、构#define n 100 /叶子数目#define m 2*n-1 /树中结点总数typedef struct /结点类型 float weight; /权值，不妨设权值均大于零 int lchild,rchild,parent; /左右孩子及双亲指针HTNode;typedef HTNode HuffmanTreem; /HuffmanTree是向量类型typedef struct char ch; /存储字符 char bitsn+1; /存放编码位串CodeNode;typedef CodeNode HuffmanCoden;void InitHuffmanTree(HuffmanT

26、ree T); /初始化Huffman树void InputWeight(HuffmanTree T); /输入权值void SelectMin(HuffmanTree T,int i,int *p1,int *p2);void main() void CreateHuffmanTree(HuffmanTree T); /构造Huffman树 void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H); HuffmanTree T; HuffmanCode H; CreateHuffmanTree(T); CharSetHuffmanEnc

27、oding(T,H);void CreateHuffmanTree(HuffmanTree T) /构造Huffman树，Tm-1为其根结点 int i,p1,p2; InitHuffmanTree(T); /将T初始化 InputWeight(T); /输入叶子权值至T0.n-1的weight域 for(i=n;im;i+) /共进行n-1次合并，新结点依次存于Ti中 SelectMin(T,i-1,&p1,&p2); /在T0.i-1中选择两个权最小的根结点，其序号分别为p1和p2 Tp1.parent=Tp2.parent=i; Ti.lchild=p1; /最小权的根结点是新结点的左孩

28、子 Ti.rchild=p2; /次小权的根结点是新结点的右孩子 Ti.weight=Tp1.weight+Tp2.weight; void InitHuffmanTree(HuffmanTree T) /初始化Huffman树 int i; for (i=0;im;i+) Ti.weight=0; Ti.lchild=Ti.rchild=Ti.parent=NULL; void InputWeight(HuffmanTree T) /输入权值 int i; for (i=0;in;i+) printf(请输入第%d个权值：,i+1); scanf(%f,&Ti.weight); void SelectMin(HuffmanTree T,int i,int *p1,int *p2) /在T中选择两个权最小的根结点 int j; float min1,min2; min1=min2=-1; for(j=0;j=i;j+) if(Tj.parent=NULL) if(Tj.w