单链表顺序表和二叉树的实验报告.doc

实验题目：顺序表的操作实验日期：2013 11 21实验要求：在VC+6.0的运行环境下，编写C或C+语言程序，利用顺序存储的方式来实现下列功能： (1)根据键盘输入数据建立一个顺序表，并且输出该顺序表。 (2)根据屏幕菜单来选择数据的插入、删除以及查找操作。 (3)完成插入或删除数据操作后，把操作后的线性表进行输出。 (4)在完成插入、删除和查找操作后，选择菜单上的0，退出该程序的运行，结束实验内容。概要设计：在顺序表的第i个位置上要求插入一个数据元素时候，先将顺序表的第i个位置元素后的所有数据元素按顺序后移一个位置，在插入的地方空出一个位置，然后把要插入的新数据元素插入到该位置，同时将表长加一。 在顺序表中删除表中第i个位置的数据元素的时候，先将该位置的数据元素删除，然后将第i个位置后的其他剩余元素按顺序依次向前移动一个位置，同时将表长减一。 顺序表中查找一个数据元素的值，需要遍历整个顺序表，如要找道该值，则返回该值在顺序表中的位置，否则继续查找。如果遍历整个顺序表都没有找到该值，则要求函数返回-1详细设计：/建立线性表void creat_list(SqList *L) int i;printf(请输入线性表的长度：);scanf(%d,&L-length);for(i=0;ilength;i+) printf(数据元素%d=,i);scanf(%d,&(L-ai); begini=0Input线性表长度LiL输入一个数i+end /输出线性表void out_list(SqList L)int i;for(i=0;i=L.length-1;i+)printf(%10d,L.ai); begini=0iL输入一个数i+end/在的第i个位置插入数eint insert_sq(SqList *L,int i,ElemType e) int j; if(iL-length) return 0;for(j=L-length;j=i;j-)L-aj=L-aj-1;L-ai-1=e;L-length+ ; return 1; 定义j=线性表的长度L(iL-length)L-aj=L-aj-1;j-beginL-ai-1=e;输入第插入地址i与输入元素ej=LendL-length+;/删除第i个数据元素 ElemType delete_sq(SqList *L,int i) int j;if(iL-length) return 0;for(j=i;jlength;j+)L-aj=L-aj+1;L-length-; return 1;定义j线性表的长度为L(iL-length)L-aj=L-aj+1j+beginL-length-输入删除第i个元素endj=iJi;j-)改成for(j=L-length;ji;j-)。测试结果：实验成绩：实验题目： 单链表的操作实验日期：2013 11 28实验要求：编写C语言程序，利用链式存储的方式来实现下列功能： (1)根据键盘输入数据建立一个单链表，并且输出该单链表。 (2)根据屏幕菜单来选择数据的插入、删除以及查找操作。 (3)完成插入或删除数据操作后，把操作后的线性表进行输出。 (4)在完成插入、删除和查找操作后，选择菜单上的0，退出该程序的运行，结束实验内容。概要设计：在单链表的第i个位置上要求插入一个数据元素时候，先生成一个存储单元S来存放插入数据元素X的值，其次修改第i个位置结点P的next域值，让其存入是结点S所在存储单元地址的值，再次修改结点S的next域的值，让S的next域的值为第i+1结点的地址值。 在单链表中删除表中第i个位置的数据元素的时候，先修改第i-1个数据元素的next域的地址值，使其值为第i+1个数据元素存储单元的地址值，最后释放第i个存储单元，使用函数free()。 在 单链表中查找一个数据元素的值，需要遍历整个整个单链表，如要找道该值，则返回该值，否则继续查找。如果遍历整个顺序表都没有找到该值，则要求函数返回-1详细设计：/建立线性链表LNode *creat_L() LNode *h,*p,*s;ElemType x;h=(LNode *)malloc(sizeof(LNode);h-next=NULL;p=h;printf(请输入第一个数据元素：);scanf(%d,&x);while(x!=-999)s=(LNode *)malloc(sizeof(LNode);s-data=x;s-next=NULL;p-next=s;p=s;printf(请输入下一个数据元素：（输入-999表示结束。）);scanf(%d,&x);return(h);begin定义 h,p,s,x,成功分配存储空间h-next=NULL;p=h;输入第一个数据元素xx!=-999s=(LNode *)malloc(sizeof(LNode);s-data=x;s-next=NULL;p-next=s;p=s;输入下一个数据元素end调试分析：1.e:c+b1.cpp(118) : error C2065: mallor : undeclared identifier 解决：把mallor改成malloc 2.E:c+b1.cpp(115) : error C2143: syntax error : missing ; before 解决：再加一个3.E:c+b1.cpp(138) : error C2065: SqList : undeclared identifier 解决：把ElemType delete_L(SqList *L,int i) SqList *temp,*p;里的SqList改成LNode。4.E:c+b1.cpp(119) : error C2679: binary = : no operator defined which takes a right-hand operand of type struct LNode * (or there is no acceptable conversion)解决：把LNode node,*temp;改成LNode *node,*temp;测试结果：实验成绩：实验题目：栈的链式存储结构的表示和实现实验日期：2013 12 04实验要求：1.认真阅读和掌握本实验的相关知识。2.编写程序实现栈的链式存储方式。3.编写程序实现对栈空的判断以及栈的入栈和出栈操作、取栈顶元素。4.保存程序的运行结果，结合程序分析链式结构的特点。5.填写实验报告概要设计：(1)初始化栈操作，将栈的栈顶指针置为空值，即设栈S和栈顶指针top，Stop=null。(2)如果所建栈里有数据元素，要将其置空，同样也是将栈顶指针的值置为空值。(3)入栈操作，向栈里插入数据元素。首先要为插入数据元素分配结点，将插入数据元素的值赋值给插入结点的数据域，其次修改栈顶指针的指向关系，即修改插入结点和栈顶指针的地址，最后修改栈顶指针。(4)出栈操作，从栈里删除数据元素。首先要判断栈是否为空栈，如是空栈则操作失败。否则，进行出栈操作，修改删除结点和栈顶指针，最后释放删除结点。(5)取栈顶元素。详细设计：/出栈ElemType popstack(LinkStack *s)ElemType x;StackNode *p;p=s-top;if(s-top=0) printf(栈空,不能出栈!n);return 0;exit(0);x=p-data;printf(%dn,x);s-top=p-next;delete p;return x;begin定义ElemType x;StackNode *p;if(s-top=0)end输出栈空,不能出栈x=p-data;printf(%dn,x);s-top=p-next;返回 x;调试分析：1. E:c+D1.CPP(7) : error C2460: next : uses stacknode, which is being defined解决;把stacknode next;改成stacknode *next;2. E:c+D1.CPP(49) : error C2065: Stacknode : undeclared identifier解决把Stacknode *p;改成StackNode *p;测试结果：实验成绩：实验题目：二叉树遍历算法的设计实验日期：2013 12 6实验要求：1.认真阅读和掌握本实验的相关知识。2.编写程序实现二叉树的链式存储方式。3.编写程序实现对二叉树的先序遍历、中序遍历和后序遍历的算法实现。4.保存程序的运行结果，结合程序分析二叉树的结构特点。5.填写实验报告概要设计：(1)定义二叉树结点值的数据类型，将其定义为字符型数据，定义二叉树中结点的结构类型。(2)利用性质5建立二叉树，设置序号为1的结点为二叉树的根结点，序号为偶数的结点为该二叉树的左孩子，序号为奇数的结点为该二叉树的右孩子。(3)采用递归方式来遍历二叉树，也就是实现二叉树的遍历是利用递归的方法来实现，即先序递归遍历、中序递归遍历、后序递归遍历。先序递归遍历算法描述： 访问二叉树的根结点。 先序遍历左子树。 先序遍历右子树。中序递归遍历算法描述： 中序遍历左子树。 访问根结点。 中序遍历右子树。后序递归遍历算法描述： 后序遍历左子树。 后序遍历右子树。 访问根结点。详细设计：递归后序遍历调试分析：1.E:c+b1.cpp(115) : error C2143: syntax error : missing ; before 解决：再加一个2.E:c+b1.cpp(138) : error C2065: SqList : undeclared identifier 解决：把ElemType delete_L(SqList *L,int i) SqList *temp,*p;里的SqList改成LNode。测试结果：实验成绩：实验题目：采用邻接表实现图的DFS和BFS实验日期：2013 12 12实验要求：1.认真阅读和掌握本实验的相关知识。2.编写程序实现图的邻接表存储方式。3.编写程序实现对图的DFS（递归）和BFS（非