数据结构实训报告

山东科技大学泰山科技学院课程实训说明书课程：数据结构项目实训题目：院系：信息工程系专业班级：计算机科学与技术12-1学号：201243010117学生姓名：刘文婷指导教师：林晓霞亓静徐燕妮2014年5月25日成绩评语：指导教师目录一、设计题目..........................................................31.1顺序表操作.........................................................31.2链表操作..........................................................31.3二叉树的基本操作..................................................3二、运行环境（软、硬件环境）.......................................32.1软件环境..........................................................32.2硬件环境..........................................................3三、数据结构及算法设计的思想.......................................33.1顺序表设计构思.....................................................33.2链表设计构思......................................................43.3二叉树设计构思....................................................4四、源代码............................................................55.1顺序表源代码......................................................55.2链表源代码........................................................65.3二叉树源代码......................................................8五、运行结果分析.....................................................116.1顺序表运行结果...................................................116.2链表运行结果.....................................................136.3二叉树运行结果...................................................15七、实习总结........................................................18一、设计题目1.1链表操作1.1.1设计目的掌握线性表的在顺序结构和链式结构实现。掌握线性表在顺序结构和链式结构上的基本操作。1.1.2设计内容和要求利用顺序表链表的插入运算建立线性链表，然后实现链表的查找、插入、删除、计数、输出、排序、逆置等运算（查找、插入、删除、查找、计数、输出、排序、逆置要单独写成函数），并能在屏幕上输出操作前后的结果。1.2二叉树的基本操作1.2.1设计目的掌握二叉树的概念和性质掌握任意二叉树存储结构。掌握任意二叉树的基本操作。1.2.2设计内容和要求(1)对任意给定的二叉树（顶点数自定）建立它的二叉链表存储结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。(2)求二叉树高度、结点数、度为1的结点数和叶子结点数。二、运行环境（软、硬件环境）2.1软件环境MicrosoftVisualC++6.02.2硬件环境计算机一台：Intelcore2处理器三、数据结构及算法设计的思想3.1顺序表设计构思确立顺序表的存储结构建立顺序表存储的结构体类型sqlist建立菜单函数Menu()。用初始化函数Init_List()，建立一个空表。用locateelem_sq()、listinsert_sq()、Delete()对链表元素进行查找、插入、删除。用printlist0、sort（）、negetive（）对链表元素进行输出、排序、逆置。3.2链表设计构思确立链表存储方式。建立链表结点存储的结构体类型node。建立菜单函数menu()。用listlocate()、listlocate()、listdelete()对链表元素进行查找、插入、删除。用listsort()、listnegetive()、listcount()、listprint()对链表进行排序、逆置、计数及输出。用Destroy_List()销毁链表。3.3二叉树设计构思确立二叉树的存储结构。建立二叉树结点的存储结构体类型bitnode。建立栈的结构体类型sqstack;。建立菜单函数menu()。用initstack()、push()、gettop()、pop()、stackempty()函数实现栈的初始化、压栈、取栈顶元素、弹栈、判栈空等功能。用createbitree()函数建立一棵树。用preordertraverse()、inordertraverse()、postordertraverse()、函数，实现对树的先序遍历、中序遍历、后续遍历。用treenature()、treedepth()函数求树的结点个数、叶子个数、一度结点个数及树的深度等属性。四、源代码5.1链表源代码项目一：顺序表#includestdio.h#includestdlib.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineelemtypeint#definestatusint#defineN5#defineLISTINCREMENT10#defineLISI_INIT_SIZE100typedefstruct{elemtype*elem;intlength;intlistsize;}sqlist;sqlistl;voidmenu();//菜单voidinput(sqlist&l);voidInitList();voidlocateelem_sq(sqlistl);//查找statuslistinsert_sq(sqlist&l);//插入voidDelete(sqlist&l);//删除voidprintlist(sqlistl);//输出voidsort(sqlistl);//排序voidnegetive(sqlistl);//逆置intmain(){intx;InitList();for(;;){menu();scanf(%d,&x);switch(x){case1:input(l);break;case2:locateelem_sq(l);break;case3:listinsert_sq(l);break;case4:Delete(l);break;case5:printlist(l);break;case6:sort(l);break;case7:negetive(l);break;default:printf(pleaseinputanumberagain!\n);}}return0;}voidInitList()//初始化{l.elem=(elemtype*)malloc(LISI_INIT_SIZE*sizeof(elemtype));if(!l.elem)exit(OVERFLOW);l.length=0;l.listsize=LISI_INIT_SIZE;}voidmenu(){printf(**********菜单*************\n);printf(********1、输入************\n);printf(********2、查找************\n);printf(********3、插入************\n);printf(********4、删除************\n);printf(********5、输出************\n);printf(********6、排序************\n);printf(********7、逆置************\n);printf(请输入操作步骤：);}voidinput(sqlist&l)//输入{inti;for(i=0;iN;i++,l.length++)scanf(%d,&l.elem[i]);}voidlocateelem_sq(sqlistl)//查找{intx,i;printf(请输入要查找的数：);scanf(%d,&x);for(i=0;il.length;i++){if(x==l.elem[i])printf(存在%d\n,x);}}statuslistinsert_sq(sqlist&l)//插入{inti;elemtypee;int*q,*p;printf(请输入i的值：);scanf(%d,&i);printf(\n请输入e的值：);scanf(%d,&e);q=&(l.elem[i-1]);for(p=&(l.elem[l.length-1]);p=q;p--)*(p+1)=*p;*q=e;++l.length;printf(线性表的长度为：%d,l.length);printf(\n);printf(插入后的数后的线性表为:\n);for(p=l.elem;pl.elem+l.length;p++)printf(%5d,*p);printf(\n);returnOK;}voidDelete(sqlist&l)//删除{inti;elemtypee;int*q,*p;printf(请输入i的值：);scanf(%d,&i);printf(\n请输入e的值：);scanf(%d,&e);if((i1)||(il.length))return;p=&(l.elem[i-1]);q=l.elem+l.length-1;for(++p;p=q;++p)*(p-1)=*p;--l.length;printf(线性表的的长度为%d,l.length);printf(\n);printf(删除后的线性表为:\n);for(p=l.elem;pl.elem+l.length;p++)printf(%d,*p);printf(\n);}voidprintlist(sqlistl)//输出{inti;if(l.length0){printf(线性表为:\n);for(i=0;il.length;i++){printf(%5d,l.elem[i]);}printf(\n);}elseprintf(Listisempty.\n\n);}voidsort(sqlistl)//排序{inti,j,t;for(i=0;il.length-1;i++)for(j=0;jl.length-i-1;j++)if(l.elem[j]l.elem[j+1]){t=l.elem[j];l.elem[j]=l.elem[j+1];l.elem[j+1]=t;}printf(排序后的线性表为:\n);for(i=0;il.length;i++)printf(%5d,l.ele