《数据结构与算法实验指导书精品资料.doc》由会员分享，可在线阅读，更多相关《数据结构与算法实验指导书精品资料.doc（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 数据结构与算法实验指导书计算机与信息学院实验一 顺序表【实验目的】熟练掌握线性表在顺序存储结构上的基本操作。【实验平台】操作系统：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 structDataType dataListSize;/向量data用于存放表结点int length;/当前的表长度SeqList;void main()SeqList L;int i,x;int n=10;/欲建立的顺序
3、表长度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=LocateList(L,x);/顺序表查找printf
4、(输入要插入的位置：);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(SeqList L,int n)/在此插入必要的语句/顺序表的查找：int LocateList(
5、SeqList L,DataType x)/在此插入必要的语句/顺序表的插入：void InsertList(SeqList *L,DataType x,int i)/在此插入必要的语句/顺序表的删除：void DeleteList(SeqList *L,int i)/在此插入必要的语句【实验报告】数据结构与算法实验报告一学院： 班级： 学号： 姓名： 日期： 程序名： L2211.CPP 一、上机实验的问题和要求：顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求：5. 从键盘输入10个整数，产生顺序表，并输出结点值。6. 从键盘输入1个
6、整数，在顺序表中查找该结点。若找到，输出结点的位置；若找不到，则显示“找不到”。7. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。8. 从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。二、源程序及注释：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：实验二 链表【实验目的】熟练掌握线性表在链式存储结构上的基本操作。【实验平台】操作系统：Windows2000或Windows XP开发环境：C或C+【实验内容及要求】单链表的查找、插入与删除。设计算法，实现线性结构上
7、的单链表的产生以及元素的查找、插入与删除。具体实现要求：9. 从键盘输入20个整数，产生带表头的单链表，并输出结点值。10. 从键盘输入1个整数，在单链表中查找该结点。若找到，则显示“找到了”；否则，则显示“找不到”。11. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。12. 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。13. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。14. 删除其中所有数据值为偶数的结点，输出单链表所有
8、结点值，观察输出结果。15. 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。16. （）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。【参考框架】#include #include /单链表的定义：typedef int DataType;/DataType可以是任何相应的数据类型如int, float或chartypedef struct node/结点类型定义DataType data;/结点的数据域struct node
9、 *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 head,int i);void InsertList(LinkList head,DataType x,int i);vo
10、id 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(输入要查找的值：);scanf(%d,&key);p=LocateNode(head,key);/单链表查找printf(请输入欲插入元素的位置：
11、);scanf(%d,&i);printf(请输入欲插入的元素：);scanf(%d,&x);InsertList(head,x,i);/单链表插入PrintList(head);/打印单链表printf(请输入欲删除结点的位置：);scanf(%d,&i);DeleteList(head,i);/单链表删除PrintList(head);/打印单链表DeleteManyList(head);/删除重复值PrintList(head);/打印单链表DeleteEvenList(head);/删除偶数值PrintList(head);/打印单链表ChangeCircList(head);/修改为
12、循环单链表PrintCircList(head);/打印循环单链表/*void DivideList(LinkList head,LinkList *A,LinkList *B); /分割成两个单链表DivideList(head, &A, &B);PrintList(A);PrintList(B);*/单链表的建立：LinkList CreateList(void)/在此插入必要的语句/单链表的打印：void PrintList(LinkList head)/在此插入必要的语句/单链表的查找1：LinkList LocateNode(LinkList head,DataType key)/在
13、此插入必要的语句/单链表的查找2：LinkList GetNode(LinkList head,int i)/在此插入必要的语句/单链表的插入：void InsertList(LinkList head,DataType x,int i)/在此插入必要的语句/单链表的删除：void DeleteList(LinkList head,int i)/在此插入必要的语句/删除单链表中重复值：void DeleteManyList(LinkList head)/在此插入必要的语句/删除单链表中偶数值：void DeleteEvenList(LinkList head)/在此插入必要的语句/修改为循环单
14、链表：void ChangeCircList(LinkList head)/在此插入必要的语句/循环单链表的打印：void PrintCircList(LinkList head)/在此插入必要的语句/*/分割成两个单链表void DivideList(LinkList head,LinkList *A,LinkList *B);/在此插入必要的语句*/【实验报告】数据结构与算法实验报告二学院： 班级： 学号： 姓名： 日期： 程序名： L2311.CPP 一、上机实验的问题和要求：单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：1.
15、从键盘输入20个整数，产生带表头的单链表，并输出结点值。2. 从键盘输入1个整数，在单链表中查找该结点。若找到，则显示“找到了”；否则，则显示“找不到”。3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。4. 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。5. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。6. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。7. 把单链表变成带表头结点的循环链表，输出循环单
16、链表所有结点值，观察输出结果。8. （）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。二、源程序及注释：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：实验三 树【实验目的】熟练掌握在链式二叉树在二叉链表存储结构上的基本操作。【实验平台】操作系统：Windows2000或Windows XP开发环境：C或C+【实验内容及要求】要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实
17、现要求：17. 基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。18. 用广义表表示所建二叉树。19. 分别利用前序遍历、中序遍历、后序遍历所建二叉树。20. 求二叉树结点总数，观察输出结果。21. 求二叉树叶子总数，观察输出结果。22. 交换各结点的左右子树，用广义表表示法显示新的二叉树。23. （）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每个结点赋值：（注意要修改DataType类型）a) 叶结点的值为3b) 只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值c) 左、右孩子均有的结点
18、，则其值等于左、右孩子结点的值之和d) 用广义表表示法显示所建二叉树【参考框架】#include #include /二叉树的链式存储表示typedef char DataType;/应由用户定义DataType的实际类型typedef struct nodeDataType data;struct node *lchild, *rchild;/左右孩子指针 BinTNode;/结点类型typedef BinTNode *BinTree;void main()void ListBinTree(BinTree T);/用广义表表示二叉树void DisplayBinTree(BinTree T)
19、;/用凹入表表示二叉树void CreateBinTree(BinTree *T);/构造二叉链表void Preorder(BinTree T);/前序遍历二叉树void Inorder(BinTree T);/中序遍历二叉树void Postorder(BinTree T);/后序遍历二叉树int nodes(BinTree T);/计算总结点数int leafs(BinTree T);/计算总叶子数BinTree swap(BinTree T);/交换左右子树BinTree T;printf(请输入先序序列（虚结点用空格表示）：n);CreateBinTree(&T);ListBinTr
20、ee(T);printf(n);DisplayBinTree(T);printf(前序遍历：n);Preorder(T);printf(n);printf(中序遍历：n);Inorder(T);printf(n);printf(后序遍历：n);Postorder(T);printf(n);printf(二叉树的总结点数为%dn,nodes(T);printf(二叉树的总叶子结点数为%dn,leafs(T);T=swap(T);ListBinTree(T);printf(n);/构造二叉链表void CreateBinTree(BinTree *T)/在此插入必要的语句/用广义表表示二叉树voi
21、d ListBinTree(BinTree T)/在此插入必要的语句/用凹入表表示二叉树void DisplayBinTree(BinTree T)/在此插入必要的语句/前序遍历二叉树void Preorder(BinTree T)/在此插入必要的语句/中序遍历二叉树void Inorder(BinTree T)/在此插入必要的语句/后序遍历二叉树void Postorder(BinTree T)/在此插入必要的语句/计算总结点数int nodes(BinTree T)/在此插入必要的语句/计算总叶子数int leafs(BinTree T)/在此插入必要的语句/交换左右子树BinTree s
22、wap(BinTree T)/在此插入必要的语句【实验报告】数据结构与算法实验报告三学院： 班级： 学号： 姓名： 日期： 程序名： L61.CPP 一、上机实验的问题和要求：要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：i. 基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。ii. 用广义表表示所建二叉树。iii. 分别利用前序遍历、中序遍历、后序遍历所建二叉树。iv. 求二叉树结点总数，观察输出结果。v. 求二叉树叶子总数，观察输出结果。vi. 交
23、换各结点的左右子树，用广义表表示法显示新的二叉树。vii. （）二叉树采用链接存储结构，其根结点指针为T，设计一个算法对这棵二叉树的每个结点赋值：（注意要修改DataType类型）a. 叶结点的值为3b. 只有左孩子或右孩子的结点则其值分别等于左孩子或右孩子的值c. 左、右孩子均有的结点，则其值等于左、右孩子结点的值之和d. 用广义表表示法显示所建二叉树二、源程序及注释：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：实验四 Huffman树【实验目的】理解建立Huffman树的算法。【实验平台】操作系统：Windows2000或Windows XP开发环境：C或C+【实验内
24、容及要求】阅读理解建立Huffman树的算法，对该算法进行运行及调试。具体实现要求：1. 调试并运行Huffman算法。2. （）求Huffman树的带权路径长度WPL。【参考框架】#include #include #include /Huffman树的存储结构#define n 100/叶子数目#define m 2*n-1/树中结点总数typedef struct/结点类型float weight;/权值，不妨设权值均大于零int lchild,rchild,parent;/左右孩子及双亲指针HTNode;typedef HTNode HuffmanTreem;/HuffmanTree是
25、向量类型typedef structchar ch;/存储字符char bitsn+1;/存放编码位串CodeNode;typedef CodeNode HuffmanCoden;void InitHuffmanTree(HuffmanTree T);/初始化Huffman树void InputWeight(HuffmanTree T);/输入权值void SelectMin(HuffmanTree T,int i,int *p1,int *p2);void main()void CreateHuffmanTree(HuffmanTree T);/构造Huffman树void CharSetH
26、uffmanEncoding(HuffmanTree T,HuffmanCode H);HuffmanTree T;HuffmanCode H;CreateHuffmanTree(T);CharSetHuffmanEncoding(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
27、,i-1,&p1,&p2);/在T0.i-1中选择两个权最小的根结点，其序号分别为p1和p2Tp1.parent=Tp2.parent=i;Ti.lchild=p1;/最小权的根结点是新结点的左孩子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(HuffmanT
28、ree 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.weightmin1|min1=-1)if(min1!=-1)min2=min1;*p2=*p1;min1=Tj.weight;*p1=j;elseif(Tj.weig
29、htmin2|min2=-1)min2=Tj.weight;*p2=j;void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H)/根据Huffman树T求Huffman编码表Hint c,p,i;/c和p分别指示T中孩子和双亲的位置char cdn+1;/临时存放编码int start;/指示编码在cd中的起始位置cdn=0;/编码结束符printf(请输入字符：);for(i=0;in;i+)/依次求叶子Ti的编码Hi.ch=getchar();/读入叶子Ti对应的字符start=n;/编码起始位置的初值c=i;/从叶子Ti开始上溯wh
30、ile(p=Tc.parent)!=NULL)/直至上溯到Tc是树根为止/若Tc是Tp的左孩子，则生成代码0；否则生成代码1cd-start=(Tp.lchild=c)?0:1;c=p;/继续上溯strcpy(Hi.bits,&cdstart);/复制编码位串for(i=0;in;i+)printf(第%d个字符%c的编码为%sn,i+1,Hi.ch,Hi.bits);【实验报告】数据结构与算法实验报告四学院： 班级： 学号： 姓名： 日期： 程序名： L62.CPP 一、上机实验的问题和要求：阅读理解建立Huffman树的算法，对该算法进行运行及调试。具体实现要求：1. 调试并运行Huffm
31、an算法。2. （）求Huffman树的带权路径长度WPL。二、源程序及注释：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：实验五 查找（二叉排序树）【实验目的】熟练掌握二叉排序树上的查找算法。【实验平台】操作系统：Windows2000或Windows XP开发环境：C或C+【实验内容及要求】实现二叉排序树上的查找算法。具体实现要求：24. 用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树。25. 用广义表表示所建二叉树。26. 按中序遍历这棵二叉排序树。27. 在二叉排序树上插入结点。28. 删除二叉排序树上的结点。29. 在二叉排序树上实现查找算法。【参考框架】
32、#include #include typedef int InfoType;typedef int KeyType;/假定关键字类型为整数typedef struct node/结点类型KeyType key;/关键字项InfoType otherinfo;/其它数据域，InfoType视应用情况而定 下面不处理它struct node *lchild,*rchild;/左右孩子指针BSTNode;typedef BSTNode *BSTree;/BSTree是二叉排序树的类型void main()void InsertBST(BSTree *Tptr,KeyType key);/将关键字k
33、ey插入二叉排序树中BSTree CreateBST(void);/建立二叉排序树void ListBinTree(BSTree T);/用广义表表示二叉树void DelBSTNode(BSTree *Tptr,KeyType key);/在二叉排序树中删除关键字keyBSTNode *SearchBST(BSTree T,KeyType key);/在二叉排序树中查找关键字keyBSTree T;BSTNode *p;int key;printf(请输入关键字（输入0为结束标志）：n);T=CreateBST();ListBinTree(T);printf(n);printf(请输入欲插入
34、关键字：);scanf(%d,&key);InsertBST(&T,key);ListBinTree(T);printf(n);printf(请输入欲删除关键字：);scanf(%d,&key);DelBSTNode(&T,key);ListBinTree(T);printf(n);printf(请输入欲查找关键字：);scanf(%d,&key);p=SearchBST(T,key);if(p=NULL)printf(没有找到%d！n,key);elseprintf(找到%d！n,key);ListBinTree(p);printf(n);/将关键字key插入二叉排序树中void Inser
35、tBST(BSTree *Tptr,KeyType key)/在此插入必要的语句/建立二叉排序树BSTree CreateBST(void)/在此插入必要的语句/在二叉排序树中删除关键字keyvoid DelBSTNode(BSTree *Tptr,KeyType key)/在此插入必要的语句/用广义表表示二叉树void ListBinTree(BSTree T)/在此插入必要的语句/在二叉排序树中查找关键字keyBSTNode *SearchBST(BSTree T,KeyType key)/在此插入必要的语句【实验报告】数据结构与算法实验报告五学院： 班级： 学号： 姓名： 日期： 程序名
36、： L8.CPP 一、上机实验的问题和要求：实现二叉排序树上的查找算法。具体实现要求：1. 用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树。2. 用广义表表示所建二叉树。3. 按中序遍历这棵二叉排序树。4. 在二叉排序树上插入结点。5. 删除二叉排序树上的结点。6. 在二叉排序树上实现查找算法。二、源程序及注释：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：实验六 排序【实验目的】熟练掌握插入、冒泡、直接选择、快速、归并等排序算法。【实验平台】操作系统：Windows2000或Windows XP开发环境：C或C+【实验内容及要求】实现直接插入、冒泡、直接选择、快速
37、、归并等排序算法。具体实现要求：30. 利用L91.CPP实现直接插入排序算法。31. 利用L92.CPP实现冒泡排序算法。32. 利用L93.CPP实现直接选择排序算法。33. 利用L94.CPP实现快速排序算法。34. 利用L95.CPP实现归并排序算法。【实验报告】数据结构与算法实验报告六学院： 班级： 学号： 姓名： 日期： 程序名：L91.CPP L92.CPP L93.CPP L94.CPP L95.CPP 一、上机实验的问题和要求：实现直接插入、冒泡、直接选择、快速、归并等排序算法。具体实现要求：1. 利用L91.CPP实现直接插入排序算法。2. 利用L92.CPP实现冒泡排序算
38、法。3. 利用L93.CPP实现直接选择排序算法。4. 利用L94.CPP实现快速排序算法。5. 利用L95.CPP实现归并排序算法。二、源程序及注释：三、运行输出结果：四、调试和运行程序过程中产生的问题及采取的措施：附录资料:不需要的可以自行删除 libxml2应用实例Libxml2 是一个xml的c语言版的解析器，本来是为Gnome项目开发的工具，是一个基于MIT License的免费开源软件。它除了支持c语言版以外，还支持c+、PHP、Pascal、Ruby、Tcl等语言的绑定，能在Windows、Linux、Solaris、MacOsX等平台上运行。功能还是相当强大的，相信满足一般用户需求没有任何问题。二、 Libxml2安装：一般如果在安装系统的时候选中了所有开发库和开发工具的话(Fedora Core系列下)，应该不用安装，下面介绍一下手动安装： 1) 从xmlsoft站点或ftp(ftp.xmlsoft.org)站点下载libxml压缩包(libxml2-xxxx.tar.gz)2) 对压缩包进行解压缩 tar xvz