《数据结构》标准实验报告.doc

内江师范学院实 验 报 告课程名称： 数据结构 实验名称： 线性表操作系、班： 姓名：学号：组别： 同组人：指导教师：实验日期：年月日 实验地点：成绩：一、实验目的要求：实验目的 ：、理解线性表的概念、特点。2、掌握线性表各种运算的实现，包括搜索、插入、删除算法的实现。实验要求：1、实现菜单操作。2、对输入的数据建立链表。3、对建立的链表查找和删除指定位置的元素，在指定位置插入数据元素。4、打印链表。二、实验仪器：计算机三、实验内容及步骤：1、实现菜单操作。2、对输入的数据建立链表。3、对建立的链表查找和删除指定位置的元素，在指定位置插入数据元素。4、打印链表。【C源程序】#include stdio.h#include alloc.h#include ll.hcreatelist(linklist *L) int x=0; linklist p,q;p=(linklist)malloc(sizeof(node); p-next=null;*L=p;printf(please input the data ,-100 is end:n);scanf(%d,&x);while(x!=-100) q=(linklist)malloc(sizeof(node); q-data=x; p-next=q; p=q; scanf(%d,&x); q-next=null ;int list_length(linklist L) int n=0;linklist P=L-next; while(P!=null) n+; P=P-next; printf(n*the linklist lenth is %d*,n) ; return n; insert(linklist L,int i,int x) linklist P=L,S;int k=0; while(k!=i-1&P!=null) P=P-next;k+; if (P=null) printf(the linklist is null,insert errorn ); else S=(linklist)malloc(sizeof(node); S-data=x; S-next=P-next;P-next=S; printf(insertedn) ; delete(linklist L,int i) linklist u,p=L; int k=0; while (k!=i-1&p!=null) p=p-next; k+; if (p=null|p-next=null) printf(there is no node can be deletedn); else u=p-next; p-next=u-next; free(u); printf(deletedn); int pout(linklist L)linklist p=L-next; printf(*print linklist*n) ; while (p) printf(%d - ,p-data); p=p-next; printf(null);void MenuList() printf(nnn=n); printf( 1 * Insert Ln); printf( 2 * Delete Ln); printf( 3 * lenthn); printf( 4 * print linklistn); printf( 5 * Exitn); printf(=n);void MenuSelect(linklist L) int select,done=1; while (done) MenuList( ); printf(n input the operating code : ); scanf(%d,&select); switch(select) case 1: int i=0,x=0; printf(insert i and datan); scanf(%d%d,&i,&x), insert(L,i,x); break; case 2: int i=0; printf(input delete i); scanf(%d,&i); delete(L,i); break; case 3: list_length(L); break; case 4: pout(L); break; case 5: done=0;break; default: printf( not selectedn); main( ) linklist L; printf(CREATE linklist Ln ); createlist(&L); MenuSelect(L);四、作业：1、如何实现两个链表的合并？五、实验结论（讨论）：内江师范学院实 验 报 告课程名称： 数据结构 实验名称： 表达式求值 系、班： 姓名：学号：组别： 同组人：指导教师：实验日期：年月日 实验地点：成绩：一、实验目的要求：实验目的：1、掌握栈的特点和运算。2、能利用栈的特点解决实际应用问题。实验要求：1、求解四则运算式的值。二、实验仪器：计算机三、实验内容及步骤：expression.h #define N 100 #define OK 1 #define Error 0 typedef enum Empty=2,Lbrace=3,Rbrace=4,Plus=5,Minus=6, Divide=7,Times=8,End=9 Operator; typedef struct op_stack int *base; int *top; O_stack;typedef struct Num_stack double *base; double *top; N_stack; O_stack opnd; N_stack number; char chN; /*defien a array for input string*/ double result; void initstack(); int Make_str(); int push_operate(int operate); int push_num(double num); int procede(int operate); int change_opnd(int operate); int push_opnd(int operate); int pop_opnd(); int caculate(int cur_opnd); double pop_num(); express.c #include stdio.h #include string.h #include ctype.h #include math.h #include malloc.h #include process.h #include expression.h int main(void) int returncode; printf(Please input a expression:n); gets(ch); initstack(); returncode=Make_str(); if(returncode=Error) printf(Error expression!n); return Error; printf(results of this expression=%fn,result); return OK;Void initstack() opnd.base=(int *)calloc(N/2,sizeof(int); if(!opnd.base) printf(no memery!); exit(0); opnd.top=opnd.base; number.base=(double *)calloc(N/2+1,sizeof(double); if(!number.base) printf(no memery!); exit (0); number.top=number.base; return;int Make_str() int i=0,j=0,dot=0; char str_num32; push_opnd(Empty); while(chi!=0) if(isdigit(chi) while(isdigit(chi) str_numj=chi; i+; j+; if(chi=.) str_numj=chi; i+; j+;dot+; if(dot1) return Error; str_numj=0; push_num(atof(str_num); j=0; dot=0; i-; else if(chi=( | chi=+ | chi=- | chi = * | chi=/ | chi=) | chi=#)if(push_operate(change_opnd(chi)=Error) return Error; else return Error;i+; return OK;int push_operate(int operate) int cur_opnd; switch(operate) case Lbrace: push_opnd(Lbrace); break;case Rbrace: while(cur_opnd=pop_opnd()!=Lbrace) if(cur_opnd=Empty) return Error;if(caculate(cur_opnd)=Error) return Error; break;case End: while(cur_opnd=pop_opnd()!=Empty) if(caculate(cur_opnd)=Error) return Error; break; default: if(procede(operate)=Error) return Error; return OK; int push_num(double num) *number.top=num; number.top+; return OK; double pop_num() number.top-; return *number.top; int change_opnd(int operate) int op;switch(operate)case +: op=Plus; break;case -: op=Minus; break;case *: op=Times; break;case /: op=Divide; break; case (: op=Lbrace; break; case ): op=Rbrace; break; case #: op=End; break; return op;int procede(int operate) int cur_opnd; if(operate*(opnd.top-1) push_opnd(operate); else cur_opnd=pop_opnd(); if(caculate(cur_opnd)=Error)return Error; procede(operate); return OK;int push_opnd(int operate) *opnd.top=operate; opnd.top+; return OK;int pop_opnd() int cur_opnd; cur_opnd=*(opnd.top-1); if(cur_opnd=Empty)return cur_opnd; opnd.top-; return cur_opnd;int caculate(int cur_opnd) double num1,num2;num1=pop_num(); if(number.base=number.top) return Error;num2=pop_num(); switch(cur_opnd) case Plus: result=num1+num2;break;case Minus: result=num2-num1;break;case Divide: result=num2/num1;break;case Times: result=num1*num2;break;default: return Error; push_num(result); return OK;四、作业：1、栈的特点是什么？2、如何利用栈来判定符号是否匹配？五、实验结论（讨论）：内江师范学院实 验 报 告课程名称： 数据结构 实验名称： 二叉树遍历 系、班： 姓名：学号：组别： 同组人：指导教师：实验日期：年月日 实验地点：成绩：一、实验目的要求：实验目的：1、 掌握树的建立。2、 掌握树的遍历过程。实验要求：采用二叉链表作存储结构，编程实现下列基本操作：1、按先序序列构造一棵二叉链表表示的二叉树T。2、对这棵二叉树进行先序、中序、后序遍历并分别输出遍历序列。3、求二叉树的深度。二、实验仪器：计算机三、实验内容及步骤：#include #include #define MAX 20#define NULL 0typedef char TElemType;typedef int Status;typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;Status CreateBiTree(BiTree *T) char ch; ch=getchar(); if (ch=#) (*T)=NULL; else (*T)=(BiTree) malloc(sizeof(BiTNode);(*T)-data=ch;CreateBiTree(&(*T)-lchild) ;CreateBiTree(&(*T)-rchild) ; return 1;void PreOrder(BiTree T) if (T) printf(%2c,T-data); PreOrder(T-lchild); PreOrder(T-rchild); void InOrder(BiTree T) if (T) InOrder (T-lchild);printf(%2c,T-data);InOrder (T-rchild); void PostOrder(BiTree T) if (T) PostOrder (T-lchild); PostOrder (T-rchild); printf(%2c,T-data); int depth(BiTree T) int dep1,dep2; if (T=NULL) return 0; else dep1=depth(T-lchild); dep2=depth(T-rchild); return dep1dep2?dep1+1:dep2+1; main() BiTree T=NULL; printf(nCreate a Binary Treen); CreateBiTree(&T); printf(nThe preorder is:n); PreOrder(T); printf(nThe inorder is:n); InOrder( T) ; printf(nThe postorder is:n);PostOrder (T); printf(nThe depth is:%dn,depth(T); 【测试数据】1. 输入：#，建立一棵空树，先序，中序，后序遍历没有输出；树的深度输出为0；2. 输入：A先序，中序，后序遍历输出均为A；深度输出为：