《数据结构》实验指导.doc

此文档收集于网络，如有侵权，请联系网站删除数据结构语言版实验指导 精品文档目录数据结构上机实验的目的和要求1实验一 顺序结构线性表的实现2实验二 单链表的插入和删除8实验三 栈的实现11实验四 二叉树操作实现14实验五 哈夫曼树的建立与编码实现18实验六 图的遍历操作28实验七 排序34实验八 查找40数据结构课程设计45数据结构上机实验的目的和要求通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及调试程序的能力。要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为：1、 需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：（1） 输入的形式和输出值的范围；（2） 输出的形式；（3） 程序所能达到的功能；（4） 测试数据：包括正确的输入输出结果和错误的输入及输出结果。2、 概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。3、 详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。4、 调试分析：（1） 调试过程中所遇到的问题及解决方法；（2） 算法的时空分析；（3） 经验与体会。5、 用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。6、 测试结果：列出对于给定的输入所产生的输出结果。若有可能，测试随输入规模的增长所用算法的实际运行时间的变化。实验一 顺序结构线性表的实现一、目的：掌握顺序表的表示方法，存储结构及其基本操作的实现。二、要求：建立一顺序表，实现其基本操作。三、示例程序：说明：一个完整的程序是由输入，处理，输出三部分组成的，每个部分还可以分为若干小部分，如输入，又可以分为声明，初始化变量，接收数据，预处理数据等。书上列出的算法是解决问题的基本思路，也可以是解决问题的处理过程，并未给出详细的输入与输出，这一部分需要在练习过程中加入，在解决实际问题时，还需要做灵活的处理。语言本身有自身的特点，其基本思想是与机器的指令码相关的。要理解程序时必须明确这些特点，并从算法所根据的数据结构下手，然后才能明白给出的程序中其算法的意义。本例程序用于演示顺序表的基本操作，希望同学们好好掌握。#include #include #include #include #define LIST_INIT_SIZE 50 #define LISTINCREMENT 10 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define CANCEL 0 typedef struct int *elem; int length; int listsize; sqlist; int compare(int X,int Y) if(X=Y) return X; else return FALSE; /compare的关系判断 void visit(int &y) y=2*y; couty ; /将y值增加为原来的2倍 int initlist(sqlist &L) L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int); if(!L.elem) return ERROR; else L.length=0; L.listsize=LIST_INIT_SIZE; return OK; /构造一个空的线性表L int destroylist(sqlist &L) free(L.elem); return OK; /销毁线性表L int clearlist(sqlist &L) L.length=0; return OK; /将L重置为空表 int listempty(sqlist L) if (0=L.length) return TRUE; else return FALSE; /求当前表L是否为空 int listlength(sqlist L) return L.length; /求当前线性表L的长度 int getelem(sqlist L,int i,int &e) if(iL.length) exit(ERROR); e=*(L.elem+i-1); return OK; /用e返回L中第i个数据元素的值 int locateelem(sqlist L,int e,int(*compare)(int x1,int x2) int i=1,j=0,*p; p=L.elem; while(i=L.length&!j) j=compare(*p+,e); +i; if(i=L.length) return i-1; else return FALSE; /求L中第一个与e满足关系compare()的数据元素的位序，若不存在则返回0 int priorelem(sqlist L,int cur_e,int &pre_e) int i=2,*p; p=L.elem+1; while(iL.length) return FALSE; else pre_e=*p-2; return OK; /若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义 int nextelem(sqlist L,int cur_e,int &next_e) int i=1,*p; p=L.elem; while(i=L.length) return FALSE; else next_e=*p; return OK; /若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义 int listinsert(sqlist &L,int i,int e) int *newbase,*p,*q; if(iL.length+1) return ERROR; if (L.length=L.listsize) newbase=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int); if(!newbase) exit(0); L.elem=newbase; L.listsize=L.listsize+LISTINCREMENT; q=L.elem+i-1; for(p=L.elem+L.length-1;p=q;-p) *(p+1)=*p; *q=e; +L.length; return OK; /在线性表L中第i个位置插入元素e int listdelete(sqlist &L,int i,int &e) int *p,*q; if(iL.length) return ERROR; else p=L.elem+i-1; e=*p; q=L.elem+L.length-1; for(+p;p=q;+p) *(p-1)=*p; L.length-; return OK; /将线性表中的第i个元素删除并返回其值 int listtraverse(sqlist L,void(*visit)(int &p) int i=1,*p; p=L.elem; while(i=L.length) visit(*p); p+; i+; return OK; /依次对L中的每一个元素调用函数visit(),一旦visit()失败，则操作失败 void main() sqlist L; int i,j,k,b,n,e,m,a,cur_e,pre_e,next_e; initlist(L); cout初始化后的基值地址:L.elem L.length=:L.length L.listsize=:L.listsizeendl; cout新建一顺序表.endl; cout当前表是否为空表listempty(L)endl; cout定义该线性表长度:a; cout分别输入线性表的各个元素,按ENTERendl; for(k=1;kj; i=listinsert(L,k,j); for(b=1;b=10;b+) coutL.elemb-1endl; listlength(L); cout当前表长:L.lengthendl; cout输入要取的数的位置n(n=10)n; getelem(L,n,e); coutL.elemn-1endl; cout与该数相等的的一个数的位序为:locateelem(L,e,compare)endl; cout输入要取前驱的数的位置m(=10)m; getelem(L,m,cur_e); if(priorelem(L,cur_e,pre_e) coutcur_e的前驱为:pre_eendl; else cout该元素没前驱endl; nextelem(L,cur_e,next_e); if(nextelem(L,cur_e,next_e) coutcur_e的后继为:next_eendl; else cout该元素没后继endl; cout输入要删元素的位序m(=10)m; listdelete(L,m,e); cout被删的元素为:eendl; cout删除元素后表长为L.lengthendl; listtraverse(L,visit); cout置为空表clearlist(L)endl; cout销毁线性表destroylist(L)next=NULL; printf(Input # to end ); /输入“#”代表输入结束 printf(Please input Node_data:); scanf(%s,ch); /输入各结点的字符串 while(strcmp(ch,#)!=0) pp=LocateNode(head,ch); /按值查找结点，返回结点指针 if(pp=NULL) /没有重复的字符串，插入到链表中 s=(ListNode *)malloc(sizeof(ListNode); strcpy(s-data,ch); r-next=s; r=s; r-next=NULL; printf(Input # to end ); printf(Please input Node_data:); scanf(%s,ch); return head; /返回头指针/=按值查找结点，找到则返回该结点的位置，否则返回NULL=ListNode *LocateNode(LinkList head, char *key) ListNode *p=head-next; /从开始结点比较 while(strcmp(p-data,key)!=0 & p) /直到p为NULL或p-data为key止p=p-next; /扫描下一个结点 return p; /若p=NULL则查找失败，否则p指向找到的值为key的结点/=删除带头结点的单链表中的指定结点=void DeleteList(LinkList head,char *key) ListNode *p,*r,*q=head; p=LocateNode(head,key); /按key值查找结点的 if(p=NULL ) /若没有找到结点，退出printf(position error);exit(0); while(q-next!=p) /p为要删除的结点，q为p的前结点q=q-next; r=q-next; q-next=r-next; free(r); /释放结点/=打印链表=void printlist(LinkList head) ListNode *p=head-next; /从开始结点打印 while(p)printf(%s, ,p-data);p=p-next; printf(n);/=删除所有结点，释放空间=void DeleteAll(LinkList head) ListNode *p=head,*r; while(p-next)r=p-next;free(p);p=r; free(p);四、实验内容1、 分析、理解程序。2、 调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。3、 修改程序：(1) 增加插入结点的功能。(2) 将建立链表的方法改为头插入法。五、实验报告要求基本要求见第一页内容。写出实验结果，并画出所建链表的示意图。六、附加实验内容（详细内容略，请同学们自行找相关书籍进行练习）线性表操作掌握线性表的几种存储结构，掌握每种结构的相应算法。实验三 栈的实现一、目的：掌握栈的表示，实现及其针对栈的各种操作。二、要求：建立一个顺序栈，用以实现任意数据的转换。三、示例程序：下述程序演示了将数转换成进制。使用了一个顺序栈，实现了栈常用的基本操作。栈的应用基本上基于这些方法实现的，此外，还有链栈，关于链栈的操作请同学们对应写出一个演示程序吧。#include iostream.h/这里还要加入我们默认的常量头文件#include head.h#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int SElemType;typedef struct SElemType *base; SElemType *top; int stacksize;SqStack;Status InitStack(SqStack &S) S.base=new SElemTypeSTACK_INIT_SIZE; if(!S.base) return OVERFLOW; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status DestroyStack(SqStack &S) S.top=NULL; S.base=NULL; delete S.base; S.stacksize=0; return OK;int StackEmpty(SqStack s) if(s.top=s.base) return 1; else return 0;Status GetTop(SqStack &s,SElemType &e) if(s.top=s.base) return ERROR; e=*(s.top-1); return OK;int StackLength(SqStack s) return s.top-s.base;Status ClearStack(SqStack &S) S.top=S.base; return OK;Status Push(SqStack &s,SElemType e) if(s.top-s.base=s.stacksize) return OVERFLOW; *s.top+=e;return OK;Status Pop(SqStack &s,SElemType &e) if(s.top=s.base) return ERROR; e=*-s.top; return OK;Status StackTraverse(SqStack s,Status(*visit)(SElemType c)/这个函数最好不要用，因为它已经破坏了栈的特性 while(s.tops.base) visit(*s.base+); coutendl; return OK;Status visit(SElemType c) coutc ; return OK;void main() /为进制转换的函数 SqStack S; SElemType N; SElemType e; InitStack(S); coutN; while(N) Push(S,N%8); N=N/8; 转换为八进制的数 while(!StackEmpty(S) Pop(S,e); coute; coutdata=ch;T-lchild=CreatBinTree(); /构造左子树T-rchild=CreatBinTree(); /构造右子树return(T); /=NLR 先序遍历=void Preorder(BinTree T) if(T) printf(%c,T-data); /访问结点Preorder(T-lchild); /先序遍历左子树Preorder(T-rchild); /先序遍历右子树 /=LNR 中序遍历= void Inorder(BinTree T) if(T) Inorder(T-lchild); /中序遍历左子树printf(%c,T-data); /访问结点Inorder(T-rchild); /中序遍历右子树 /=LRN 后序遍历=void Postorder(BinTree T) if(T) Postorder(T-lchild); /后序遍历左子树Postorder(T-rchild); /后序遍历右子树printf(%c,T-data); /访问结点 /=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int TreeDepth(BinTree T) int hl,hr,max; if(T)hl=TreeDepth(T-lchild); /求左深度hr=TreeDepth(T-rchild); /求右深度max=hlhr? hl:hr; /取左右深度的最大值NodeNum=NodeNum+1; /求结点数if(hl=0&hr=0) leaf=leaf+1; /若左右深度为0，即为叶子。return(max+1); else return(0);/=利用“先进先出”（FIFO）队列，按层次遍历二叉树=void Levelorder(BinTree T) int front=0,rear=1; BinTNode *cqMax,*p; /定义结点的指针数组cq cq1=T; /根入队 while(front!=rear) front=(front+1)%NodeNum;p=cqfront; /出队printf(%c,p-data); /出队，输出结点的值 if(p-lchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-lchild; /左子树入队if(p-rchild!=NULL) rear=(rear+1)%NodeNum; cqrear=p-rchild; /右子树入队 /=主函数=void main() BinTree root; int i,depth; printf(n);printf(Creat Bin_Tree； Input preorder:); /输入完全二叉树的先序序列， / 用#代表虚结点，如ABD#CE#F# root=CreatBinTree(); /创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。printf(t* select *n);printf(t1: Preorder Traversaln); printf(t2: Iorder Traversaln);printf(t3: Postorder traversaln);printf(t4: PostTreeDepth,Node number,Leaf numbern);printf(t5: Level Depthn); /按层次遍历之前，先选择4，求出该树的结点数。printf(t0: Exitn);printf(t*n);scanf(%d,&i); /输入菜单序号（0-5）switch (i)case 1: printf(Print Bin_tree Preorder: );Preorder(root); /先序遍历break;case 2: printf(Print Bin_Tree Inorder: );Inorder(root); /中序遍历break;case 3: printf(Print Bin_Tree Postorder: );Postorder(root); /后序遍历break;case 4: depth=TreeDepth(root); /求树的深度及叶子数printf(BinTree Depth=%d BinTree Node number=%d,depth,NodeNum);printf( BinTree Leaf number=%d,leaf);break;case 5: printf(LevePrint Bin_Tree: );Levelorder(root); /按层次遍历break;default: exit(1);printf(n); while(i!=0); 四、实验内容1、 分析、理解程序。2、 调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD#CE#F#，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。五、实验报告要求1、 基本要求见第一页。2、 画出所设计的二叉树，以后序遍历算法为例，画出执行踪迹示意图。3、 给出实验结果。实验五 哈夫曼树的建立与编码实现一、目的：掌握哈夫曼树的表示，实现及其在编码上的应用。二、要求：1） 建立一正文文件(本程序中建立的文件名文test.txt)，向其中输入字符。2） 通过哈夫曼算法求出文件中字符的相应编码。3） 建立一与正文文件(test.txt)对应的编码文件（bainma.txt）三、示例程序：#include #include #include #include #include /*声明两种链表结构-start*/ struct node_a /*链表1-作用：用来统计文件中字符的个数和种类（通过count）*/ char data; int count; struct node_a *next; ; typedef struct node_a node,*list; list head=NULL; struct nodeb /*链表2-作用：用来建立用相应的编码代替字符的新文件*/ char data; struct nodeb *next; ; typedef struct nodeb node_b,*list_b; /*jiang bianma xieru wenjian*/ list_b head_b=NULL; /*声明两种链表结构-end*/ /*哈夫曼算法种相关的3种结构的声明-start*/ struct forest float weight; int root; ; struct alphabet char symbol; float probability; int leaf; char *bianma; ; struct tree int lchild; int rchild; int parent; ; typedef struct tree *tree_ptr,tree_node; typedef struct forest *forest_ptr,forest_node; typedef struct alphabet *alphabet_ptr,alphabet_node; tree_ptr tree1; forest_ptr forest1; alphabet_ptr alphabet1; int lasttree,lastnode; int least,second; /*哈夫曼算法种相关的3种结构的声明-end*/ /*stack difination start*/ struct stacknode char *bian_ma; struct stacknode *next; ; typedef struct stacknode stack_node; typedef stack_node *link; link top=NULL; void push(char *item) link p; if(top!=NULL) p=(link)malloc(sizeof(stack_node); if(p=NULL) printf(Memory allocation error!); return; p-bian_ma=item; p-next=top; top=p; else top=(link)malloc(sizeof(stack_node); if(!top) printf(Memory allocation error!); return; top-bian_ma=item; top-next=NULL; void pop(void) link p; p=top; top=top-next; free(p); void makenull(void) while(top!=NULL) pop(); int empty() if(top=NULL) return 1; else return 0; char* tops(void) return (top-bian_ma); void display_stack(link s) /*显示栈重的内容*/ link ptr; ptr=s; while(ptr!=NULL) printf(%s,ptr-bian_ma); ptr=ptr-next; /*stack_difination is end*/ void display(list h) /*显示链表1*/ list ptr; int i=1; ptr=h-next; while(ptr!=NULL) printf(%d,%c,%dn,i,ptr-data,ptr-