中南民族大学数据结构.doc

院 系： 计算机科学学院 专 业： 年 级： 2010级 课程名称： 数据结构 学 号： 姓 名： 指导教师： 2012年 6 月 1日年级2010班号 2班学号专业姓名实验名称2 单链表的相关操作演示 实验类型设计型综合型创新型实验目的或要求实验目的：通过上机实践，使学生进一步掌握线性表的逻辑定义、存储结构以及相关应用。 实验要求：自定义存储结构，用C或C+语言编写程序，要求程序模块清晰，菜单界面，有运行结果。四个题目任选一个写入实验报告。实验原理（算法流程）1、单链表的相关操作演示：typedef struct LNodefloat data;struct LNode *next;LNode,*LinkList;/链表节点的定义void CreateList_L(LinkList &L,int n)逆序创建一个链表，L为链表的头结点，n为输入的元素的个数int Length_LinkList(LinkList L)将链表L中的节点个数输出出来（不包括头结点），返回值为输出的节点数；void InsertList_L(LinkList &L,int i,float e)将e插入链表L中的i号位置；核心算法是：现在链表中找到第i-1号位置，然后将要插入的e插到i-1的后面void DeleteList_L(LinkList &L,int i,float e)将链表L中的第i号位置的元素e删除；核心算法：从头结点开始往下找，找到第i-1号位置，然后将第i号节点删除，再把后面的节点接上void DemandList_L(LinkList &L,int i,float e)查询链表L中的第i号位置的元素e；核心算法：找到第i号位置，然后输出出来void OrderList_L(LinkList &L)将链表L中的数据递增排序；核心算法是：新申请一个头结点，将链表L中的元素进行比较，找到最大的元素所在的节点，将它取出来连接到新的头结点的next指针上，然后再找出次大的，再连接到头结点的next指针上，如此循环，直到链表L的next指向空即完成，然后将新的链表的头设置为L，销毁新的头结点指针void PrintList_L(LinkList &L) 打印函数，一次将链表L中的内容输出出来void delLinkList_L(LinkList &L)释放链表L组内分工（可选） 无实验结果分析及心得体会心得体会： 首先我觉得要注意的是创建链表的时候要注意将next指针赋值为空；插入、删除、查询函数关键就是位置的查找，找到后执行相应的操作就可以了，当然还要注意些地方，比如删除不能超出链表的长度，插入不能超出插入的范围等等；其他的一些就是细节上的问题，什么时候用引用传旨，什么时候用形参传值都是要注意的。成绩评定教师签名： 2012年 月 日备注：源代码附后，源代码要求有注释说明#include #include#includetypedef struct LNodefloat data;struct LNode *next;LNode,*LinkList;/链表节点的定义void CreateList_L(LinkList &L,int n)/逆序创建一个链表LinkList p,q;int i;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;q=L;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);coutp-data;coutnext=q-next;q-next=p;q=p;int Length_LinkList(LinkList L)/返回链表的长度的函数int i;LinkList p;p=L;for(i=0;p-next!=NULL;i+)p=p-next;coutSingle Length:inext)coutError!Nothing!m+1&i0)/i要小于链表长度m+1coutInsert Error!endl;exit(1);else/找到第i-1个位置，在后面插入一个元素while(p&jnext;+j;if(!p|ji-1)/判断是否到了链表的末尾coutError!data=e;s-next=p-next;p-next=s;void DeleteList_L(LinkList &L,int i,float e)/删除在链表L第i个位置的元素eLinkList p,q;int j,m;p=L;j=0;m=Length_LinkList(L);if(!L-next)coutError!Nothing!m&i0)/i要小于链表长度mcoutDelete Error!endl;exit(1);elsewhile(p&jnext;+j;if(!p|j=i)/当i=0时不可取coutThis elem is not existed!next;p-next=q-next;coutElem data is removed!next;j=1;m=Length_LinkList(L);if(!L-next)coutError!Nothing!m&i0)/i要小于链表长度mcoutDelete Error!endl;exit(1);elsewhile(p&jnext;+j;if(!p|ji)coutThis elem is not existed!endl;exit(1);cout第j个数是:datanext=NULL;I1=L;I2=L;p=L-next;q=L-next;if(!L-next)coutError!Nothing!next)/找到最大数，将其从链表中取出来放在新的头结点的后面while(q)/找到最大数if(p-data=q-data)I2=q;q=q-next;elsep=q;I1=I2;I2=q;q=q-next;I1-next=p-next;p-next=I-next;I-next=p;I1=L;I2=L;p=L-next;q=L-next;L-next=I-next;/将新形成的链表给Lfree(I);coutOK!next)coutError!Nothing!next;i+)p=p-next;coutPrint i data:dataendl;void delLinkList_L(LinkList &L)/释放内存LinkList p;p=L;for(;p;p+)free(p);void menu(LinkList &L)/菜单函数int x,i,n;float e;cout=endl;cout=endl;cout|1.Creat Single Link|endl;cout|2.Insert New Elem |endl;cout|3.Delete Elem |endl;cout|4.Demand Elem |endl;cout|5.Order Single Link|endl;cout|6.Print Single Link|endl;cout|7.Print Link Length|endl;cout|8.Exit |endl;cout=endl;cout=endl;coutx;switch(x)case 1:coutn;CreateList_L(L,n);menu(L);break; case 2:coutPlease input the position and data that you want to insert:ie;InsertList_L(L,i,e);menu(L);break; case 3:coutPlease input the position and data that you want to delete:ie;DeleteList_L(L,i,e);menu(L);break; case 4:coutPlease input the position and data that you want to demand:ie;DemandList_L(L,i,e);menu(L);break; case 5:OrderList_L(L);menu(L);break; case 6:PrintList_L(L);menu(L);break; case 7:Length_LinkList(L);menu(L);break; case 8:exit(0); default:coutInput Error,Please Input Numbers From 1 To 8!endl;exit(1);break;int main()LinkList L;menu(L);return 1;年级2010级班号 学号专业软件工程姓名实验名称2表达式求值 实验类型设计型综合型创新型实验目的或要求实验目的：通过上机实践，使学生进一步掌握栈这种特殊线性表的逻辑定义、存储结构以及初始化栈、入栈、出栈、栈判空等基本操作的具体实现，使学生能够应用栈的思想解决相关实际问题。 实验要求：自定义存储结构，用C或C+语言编写程序，要求程序应用栈的操作，模块清晰，菜单界面，有运行结果。四个题目任选一个写入实验报告。实验原理（算法流程）2、表达式求值：typedef struct/字符结构体char *base;char *top;int stacksize;SqStack;typedef struct/数字结构体float *base;float *top;int stacksize;SzStack;注：栈的基本操作有构建空栈，入栈，出栈，得到栈顶元素；int In(char e)判断是为运算符或者是数字符，运算符返回1，数字返回0int Suffix(char c,char s)得到数组下表函数，返回符号c在数组s的位置char Precede(char a,char b)a是从栈顶出来的符号，b传入的是从用户输入的符号通过判断，得到是否为同优先级，返回一个大于，小于或等于符号float Operate(float a,char u,float b)返回操作的结果，即a与b经过操作u后的结果float EvaluateExpression()从用户那得到一个表达式，以“#”结尾如果是数字就入数字栈，如果是运算符就入运算符栈，当第二次得到运算符时，和前一次入栈的运算符比较优先级，是大于，数字栈出来的两个数与运算符栈出来的运算符进行运算，另一个则入栈，是小于，则入栈；如果是半括号，则与栈顶的符号比较，可以配对，则将半括号出栈，再出一个运算符，数字栈也出两个数进行运算，运算的结果入栈，知道符号栈没有符号即输出数字栈的结果。组内分工（可选） 无实验结果分析及心得体会心得体会： 经过老师的讲解，我明白了，符号间的优先级可以用大于，小于和等于号来表示，只要将它们存在一个数组里面，根据输入的得到的符号与栈里的运算符进行比较，把比较的优先级返回回来，从而得出是进行出栈，入栈还是运算的操作。最后只要判读运算符栈为空即可输出数字栈中的最后结果。成绩评定教师签名： 2012年 月 日备注：源代码附后，源代码要求有注释说明#include#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10using namespace std;typedef struct/字符结构体char *base;char *top;int stacksize;SqStack;typedef struct/数字结构体float *base;float *top;int stacksize;SzStack;int InitStack_q(SqStack &s)/构造一个char空栈s.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!s.base)return 0;s.top=s.base;s.stacksize=STACK_INIT_SIZE;return 1;int InitStack_z(SzStack &s)/构造一个float空栈s.base=(float *)malloc(STACK_INIT_SIZE*sizeof(float);if(!s.base)return 0;s.top=s.base;s.stacksize=STACK_INIT_SIZE;return 1;char GetTop_q(SqStack s)/栈不空，取出栈顶元素char e;if(s.top=s.base)coutStack empty!endl;exit(0);e= *(s.top-1);return e;float GetTop_z(SzStack s)/栈不空，取出栈顶元素float e;if(s.top=s.base)coutStack empty!=s.stacksize)s.base=(char *)realloc(s.base,(s.stacksize+STACKINCREMENT) * sizeof(char);if(!s.base)coutFailure!=s.stacksize)s.base=(float *)realloc(s.base,(s.stacksize+STACKINCREMENT) * sizeof(float);if(!s.base)coutFailure!endl;exit(1);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;char Pop_q(SqStack &s)/删除栈顶元素（即栈顶指针向栈底指针移动一位）char e;if(s.top=s.base)coutStack empty!endl;exit(0);e=*-s.top;return e;float Pop_z(SzStack &s)/删除栈顶元素（即栈顶指针向栈底指针移动一位）float e;if(s.top=s.base)coutStack empty!, , =;/用一个二维数组装符号的优先级int i,j;i=Suffix(a,c); j=Suffix(b,c);return dij;/返回符号的优先级float Operate(float a,char u,float b)/返回操作的结果float s;switch(u)case +:s=a+b;break;case -:s=a-b;break;case *:s=a*b;break;case /:if(b) s=a/b;elsecoutb=0!;break;return s;/算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集。这是一个整型数相加的算法float EvaluateExpression()float a,b,r,j;char c,u,flag;SqStack OPTR;SzStack OPND;InitStack_q(OPTR);Push_q(OPTR,#);InitStack_z(OPND);coutPlease enter a expression end with #:n;c=getchar();while(c!=#|GetTop_q(OPTR)!=#)/输入的符号和数字须是数字和运算符if(In(c)j=(float)(c-48);Push_z(OPND,j);c=getchar();elseflag=GetTop_q(OPTR);switch(Precede(GetTop_q(OPTR),c)/通过返回的的优先级，来判断符号是入栈还是出栈case :u=Pop_q(OPTR);b=Pop_z(OPND);/将字符数字转换为数字a=Pop_z(OPND);/将字符数字转换为数字Push_z(OPND,Operate(a,u,b);break;r=GetTop_z(OPND);return r;void main()float result;result=EvaluateExpression();coutThe result is:resultendl;年级 2010级班号 2班学号专业软件工程姓名实验名称1二叉树的基本操作演示 实验类型设计型综合型创新型实验目的或要求实验目的：通过上机实践，使学生进一步掌握二叉树的递归结构定义、存储结构、二叉树的创建、遍历等相关操作及其应用。 实验要求： 用C或C+语言编写程序，要求程序模块清晰，菜单界面，有运行结果。1、自定义结点结构，以二叉链表为存储结构(1) 创建二叉树(2) 输出二叉树的先序、中序和后序递归和非递归遍历下的结点访问次序(3) 输出二叉树所有的叶子节点和叶子节点个数(4) 输出二叉树的按层次遍历序列。(5) 输出二叉树的高度2、任意给定一段电文，为其中出现的字符设计赫夫曼编码，使总电文编码长度最短。两个题目任选一个写入实验报告。实验原理（算法流程）1、二叉树的基本操作演示：typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/树节点的定义BiTNode * CreateBiTree()先序输入；难点：定义结构体的一个指针的函数。void PreOrderTraverse(BiTree T)递归先序输出；核心算法为：首先输出根节点，然递归对左树进行输出，再是右树。void InOrderTraverse(BiTree T)递归中序输出；核心算法为：首先输出左树，然后根节点，再是右树。void AfOrderTraverse(BiTree T)递归后序输出；核心算法为：首先是左树，然后是右树，最后是根。typedef structBiTree *base;/注意定义的时候什么时候用指针，什么时候不用BiTree *top;/注意指针和非指针的区别int stacksize;SqStack;/栈的定义注：栈的基本操作有构建空栈，入栈，出栈； 实验原理（算法流程）void InOrderStack(BiTree T)非递归中序遍历；核心算法：进行左树遍历，左孩子不为空则入栈，直到左孩子为空，则出栈，并输出，如果右孩子不为空，则输出右孩子，否则继续出栈。typedef struct QNodeBiTree t;struct QNode *next;QNode,*QueuePtr;/队列节点的定义typedef structQueuePtr front;QueuePtr rear;LinkQueue,*Link_Queue;/队列的定义注：队列的基本操作，入队、出队、队是否为空、摧毁队；void Leaves(BiTree p)求叶子节点；核心算法：先将根节点入队，出队，如果左右孩子不为空则入队，如果为空则输出，并计数。Depth(BiTree t)深度遍历；核心算法：递归左树和右树并计数，取最大的层次。组内分工（可选） 无实验结果分析及心得体会心得体会： 我认为比较难的地方时非递归的中序遍历，什么时候入栈，什么时候出栈都要掌握好，否则就不对了；还有的就是递归的算法，这种算法的代码虽短，但是理解起来有点困难，用好了它对于解决一些问题很有帮助。成绩评定教师签名： 2012年 月 日备注：源代码附后，源代码要求有注释说明#include #include #include #include #include using namespace std;#define OK 1#define FALSE 0#define TRUE 1typedef char TElemType;typedef int status;typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/树节点的定义BiTNode *Left(BiTree e)/得到树的左孩子if(e-lchild)return e-lchild;elsereturn NULL;BiTNode *Right(BiTree e)/得到树的右孩子if(e-rchild)return e-rchild;elsereturn NULL;BiTNode * CreateBiTree()/先序输入；难点：定义结构体的一个指针的函数char ch;BiTNode *T=NULL;scanf(%c,&ch);if(ch= )/难点；没有的要附上一个NULLT=NULL;else T=(struct BiTNode*)(malloc(sizeof(struct BiTNode); T-data=ch; T-lchild=CreateBiTree();/递归创建左树 T-rchild=CreateBiTree();/递归创建右树return T;void PreOrderTraverse(BiTree T)/递归先序输出if(T!=NULL)printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);void InOrderTraverse(BiTree T)/递归中序输出if(T!=NULL)InOrderTraverse(T-lchild);printf(%c,T-data);InOrderTraverse(T-rchild);void AfOrderTraverse(BiTree T)/递归后序输出if(T!=NULL)AfOrderTraverse(T-lchild);AfOrderTraverse(T-rchild);printf(%c,T-data);typedef structBiTree *base;/注意定义的时候什么时候用指针，什么时候不用BiTree *top;/注意指针和非指针的区别int stacksize;SqStack;/栈的定义void InitStack(SqStack &S)/初始化栈S.base=(BiTree *)malloc(100 * sizeof(BiTree);if(!S.base)exit(0);S.top=S.base;S.stacksize=100;void Push(SqStack &S,BiTree e)/入栈，引用的符号一定要用*S.top+=e;BiTNode * Pop(SqStack &S)/出栈BiTree e;if(S.top=S.base)cout lchild;/将左树入栈elseN=Pop(s);p=N;printf(%c,p-data);p=p-rchild;typedef struct QNodeBiTree t;struct QNode *next;QNode,*QueuePtr;/队列节点的定义typedef structQueuePtr front;QueuePtr rear;LinkQueue,*Link_Queue;/队列的定义void InitQueue(Link_Queue Q)/初始化队列Q-front=Q-rear=(QNode *)malloc(sizeof(QNode);if(!Q-front)exit(1);Q-front-next=NULL;void DestroyQueue(Link_Queue &Q)/摧毁队列while(Q-front)Q-rear=Q-front-next;free(Q-front);Q-front=Q-rear;void EnQueue(Link_Queue Q,BiTree p)/树指针入队函数QueuePtr q;if(!p)exit(1);q=(QNode *)malloc(sizeof(QNode);q-t=p;q-next=NULL;Q-rear-next=q;Q-rear=q;BiTNode *DeQueue(Link_Queue Q)/出队列QueuePtr p;if(Q-front=Q-rear)printf(队列为空了！n) ;p=Q-front-next;Q-front-next=p-next;if(Q-rear=p)Q-rear=Q-front;return p-t; int QueueEmpty(Link_Queue p)/判断队列是否为空if(p-front=p-rear)return 1;elsereturn 0;void Leaves(BiTree p)/求叶子节点Link_Queue q;q=(LinkQueue *)malloc(sizeof(LinkQueue);InitQueue(q);BiTNode *e;int n=0;e=(BiTNode *)malloc(sizeof(BiTNode);EnQueue(q,p);while(!QueueEmpty(q)e=DeQueue(q);if(e-lchild=NULL&e-rchild=NULL)/如果为叶子节点则输出printf(%c,e-data);n+;/节点的计数if(e-lchild!=NULL)/不为左树的叶子节点则左树入栈EnQueue(q,e-lchild);if(e-rchild!=NULL)EnQueue(q,e-rchild);/不为右树的叶子节点则右树入栈printf(n叶子节点个数为：%dn,n);int Depth(BiTree t)/深度遍历int hl,hr,max;if(t!=NULL) hl=Depth(t-lchild);/递归左树深度遍历 hr=Depth(t-rchild);/递归右树深度遍历 max=hlhr?hl:hr;/取两树深度的最大值 return (max+1);else return 0;int main()BiTree T;int a;printf( 先序遍历的顺序输入二叉树，空格为空:n);T=CreateBiTree();printf(先序遍历输出二叉树:n);PreOrderTraverse(T);printf( n中序输出二叉树：n);InOrderTraverse(T);printf( n后序输出二叉树：n);AfOrderTraverse(T);printf( n非递归二叉树遍历：n); InOrderStack(T);printf(n二叉树的叶子节点为：n);Leaves(T);printf(n二叉树的深度：n);a=Depth(T);couta;coutendl;return 0;年级2010级班号 2班学号专业软件工程姓名实验名称1图遍历的演示 实验类型设计型综合型创新型实验目的或要求实验目的：通过上机实践，使学生进一步掌握图的逻辑结构、存储结构和图在采用领接表的存储结构下的深度优先搜索和广度优先搜索算法以及图的相关应用。 实验要求： 自定义存储结构，用C或C+语言编写程序，要求程序模块清晰，菜单界面，有运行结果。实验原理（算法流程）1、图遍历的演示：typedef struct ArcNodeint adjvex;/该弧所指向的顶点位置struct ArcNode *nextarc;/指向下一条弧的指针/InfoType *info;/该弧的相关信息ArcNode,*ArcLink;/临接点存储结构定义typedef struct VNodeint data;/顶点信息ArcNode *firstarc;/指向第一条依附该