数据结构报告.docx
- 文档编号:5101970
- 上传时间:2023-05-08
- 格式:DOCX
- 页数:51
- 大小:112.21KB
数据结构报告.docx
《数据结构报告.docx》由会员分享,可在线阅读,更多相关《数据结构报告.docx(51页珍藏版)》请在冰点文库上搜索。
数据结构报告
湖南师范大学工程与设计学院
数据结构实验报告
姓名:
沈毕
年级:
2014
专业:
应用电子技术
学号:
201430181029
任课教师:
肖柳明
开课时间:
2015~2016学年第一学期
实验
(一)
实验时间
2015年
实验地点
中栋603
实验题目
线性表的存储及操作
实验目的
1)掌握顺序存储结构和链式存储结构的特点;
2)掌握常见算法。
实验内容
实验内容:
已知两个按元素值有序的线性表A和B,编程实现:
将A和B有序归并成一个按元素值有序的线性表。
实验步骤:
1)从键盘输入两个按元素值有序的线性表A和B的值;
2)根据输入把数据元素分别以顺序存储结构和线性链表存储;
3)有序归并成一个新的按元素值有序的线性表C;
4)输出显示合并后的线性表C。
测试数据:
A=(3,5,8,11),B=(2,6,8,9,11,15,20)
一、结构定义:
typedefintElemType;
typedefintStatus;
顺序存储结构的定义:
typedefstruct{
ElemType*elem;
intlength;
intlistsize;
}SqList;
线性链表结构的定义:
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
二、算法描述:
先将两个表的元素从键盘输入,然后再将两个表相加,得到第三个表。
在合并后的表中找到值相同的元素,将后面的元素前移以删除值相同的元素,最后将表的长度减1得到最终的结果。
//顺序表LA,LB合为LC
SqlistMergeList_sq(SqlistLa,SqlistLb,SqlistLc){
pa=La.elem,pb=Lb.elem,*pc;
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(int*)malloc(Lc.listsize*sizeof(int));
if(!
Lc.elem)//分配失败
exit(0);
while(pa<=pa_last&&pb<=pb_last){//判断La,Lb是否结尾
if(*pa<=*pb)//比较大小,影响插入的顺序
*pc++=*pa++;
else
*pc++=*pb++;
}
while(pa<=pa_last)//可能存在没有插完的情况
*pc++=*pa++;
while(pb<=pb_last)
*pc++=*pb++;
returnLc;
}
单链表类C
//合并链表La,Lb,Lc
LNode*MergeList_L(LinkListLa,LinkListLb,LinkListLc){
pa=La->next;pb=Lb->next;
Lc=pc=La;
while(pa&&pb){
if(pa->data<=pb->data){
pc->next=pa;
pc=pa;
pa=pa->next;
}
else{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa?
pa:
pb;
free(Lb);
returnLc;
}
三、程序清单:
#include
#include
struct
{int*elem;
intlength;
intlistsize;
}A,B,C;
structnode
{
intdata;
structnode*next;
}*HA,*HB,*HC;
voiddel_order()
{
inti,j;
for(i=0;i { if(C.elem[i]==C.elem[i+1]) { for(j=i+2;j<=C.listsize-1;j++) { C.elem[j-1]=C.elem[j]; } C.listsize--; } } printf("\n删除后线性表C的值: \n"); for(i=0;i { printf("%d",C.elem[i]); } } merge_order() { inti=0,j=0,k=0; C.listsize=A.listsize+B.listsize; C.elem=(int*)malloc(C.listsize*sizeof(int)); if(C.elem==NULL) return0; while(i { if(A.elem[i] C.elem[k++]=A.elem[i++]; else C.elem[k++]=B.elem[j++]; } while(i { C.elem[k++]=A.elem[i++]; } while(j { C.elem[k++]=B.elem[j++]; } printf("线性表C的值为: \n"); for(k=0;k { printf("%d",C.elem[k]); } del_order(); } creat_order() {inti; printf("请输入线性表A和表B的长度: \n"); scanf("%d%d",&A.listsize,&B.listsize); A.length=A.listsize; B.length=B.listsize; A.elem=(int*)malloc(A.listsize*sizeof(int)); B.elem=(int*)malloc(B.listsize*sizeof(int)); if(A.elem==NULL||B.elem==NULL) return0; printf("请有序输入线性表A的值\n"); for(i=0;i { scanf("%d",&(A.elem[i])); } printf("请有序输入线性表B的值\n"); for(i=0;i { scanf("%d",&(B.elem[i])); } merge_order(); } merge_list() { structnode*pa,*pb,*q; HC=q=(structnode*)malloc(sizeof(structnode)); while(HA! =NULL&&HB! =NULL) { if(HA->data<=HB->data) { q->next=HA; HA=HA->next; } else { q->next=HB; HB=HB->next; } q=q->next; } while(HA! =NULL) { q->next=HA; HA=HA->next; q=q->next; } while(HB! =NULL) { q->next=HB; HB=HB->next; q=q->next; } q=NULL; printf("线性表C的值为: \n"); for(q=HC->next;q! =NULL;q=q->next) { printf("%d",q->data); } } creat_list() { structnode*p,*q; intla,lb; printf("\n请输入线性表A和B的长度: \n"); scanf("%d%d",&la,&lb); HA=p=(structnode*)malloc(sizeof(structnode)); if(p==NULL) return; printf("请输入线性表A的值: \n"); while(la-->0) { scanf("%d",&p->data); q=p; p=(structnode*)malloc(sizeof(structnode)); q->next=p; } q->next=NULL; HB=p; printf("请输入线性表B的值: \n"); while(lb-->0) { scanf("%d",&p->data); q=p; p=(structnode*)malloc(sizeof(structnode)); q->next=p; } q->next=NULL; merge_list(); } main() { charch; GO: printf("a: 顺序存储\nb: 线性链表\n"); ch=getchar(); if(ch=='a') creat_order(); elseif(ch=='b') creat_list(); else gotoGO; } 四、 运行结果: 五、分析与总结: 时间复杂度: O(n) 空间复杂度: O (1) 这是第一次上数据结构实验课,虽然之前学过C语言,可是真到了自己编写程序的时候,还是不知道该从何下手,编写的过程中更是错误连连,开始没有使用#define定义,根本就无法运行,后来出来了一个简单的结果,成就感还是有的。 然后继续在现有程序上进行改进,最后出来了这个结果。 编写程序还是需要耐心,注意大小写,中文括号之类的小问题,再多看书,基本就能编出简单的程序,最后在现有程序上进行改进,就能一步步做好。 实验 (二) 实验时间 2015年 实验地点 中栋604 实验题目 栈、队列 实验目的 1)掌握栈、队列的思想及其存储实现; 2)掌握栈、队列的常见算法的程序实现及应用。 实验内容 实验内容: 1)利用栈和算符优先算法,实现表达式求值。 2)采用顺序存储实现循环队列的初始化、入队、出队操作。 测试数据: (1)3×5+9-5×(6-3) 3)循环队列大小为11,d,e,b,g,h入队;d,e出队;i,j,k,l,m入队;b出队;n,o,p,q,r入队 一、结构定义: 栈: #defineSTACK_INIT_SIZE100 #defineSTACKINCREMENT10 typedefstruct{ int*base; int*top; intstacksize; }SqStack; 队列: typedefstructQNode{ intdata; structQNode*next; }QNode,*QueuePtr; typedefstruct{ QueuePtrfront; QueuePtrrear; }LinkQueue; 2、算法描述: (一)、算术表达式 算法基本思想: 1、首先置操作数栈为空栈,表达式起始符’#’为运算符栈的栈底元素。 2、依次读入表达式中每个字符,若是操作数则进OPND栈,若是运算符则和OPTR栈顶运算符比较优先权后进行相应的操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为‘#’。 operandTypeevaluateExpression(){ //算术表达式求值的算符优先算法。 设OPTR和OPND分别为运算符栈和运算数栈 //OP为运算符号的集合 InitState(OPTR);Push(OPTR,’#’); InitState(OPND);c=getchar(); While(c! =‘#’||getop(OPTR)! =‘#’){ If(! In(c,OP)){//当前输入若为运算数则压入OPND栈 Push(OPND,c); c=getchar(); } Else{ Switch(Precede(getop(OPND),c)){//比较输入运算符和运算符栈顶元素的优先级大小 Case‘<’: //栈顶元素优先级低,吧当前运算符压入OPTR Push(OPTR,c);c=getchar(); Break; Case‘=’: //脱括号并接收下一个字符 Pop(OPTR,x);c=getchar(); Break; Case‘>’: //弹出OPTR栈顶元素和OPND的两个栈顶元素进行运算并将结果入OPND栈 Pop(OPTR,theta);//弹出OPTR栈顶元素 Pop(OPND,b);Pop(OPND,a);//弹出OPND的两个栈顶元素 Push(OPND,Operate(a,theta,b));//进行运算并将结果入OPND栈 Break; } } ReturnGeTop(OPND);//返回运算结果,此时OPND的栈顶元素即为最终运算结果。 } 二)、队列 //构造一个空队列Q intInitQueue(SqQueue*Q) { Q->base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(! Q->base)//存储分配失败 exit(0); Q->front=Q->rear=0;//下标初始化为0 return1; } //返回Q的元素个数,即队列的长度 intQueueLength(SqQueueQ) { return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE; } //插入元素e为Q的新的队尾元素 intEnQueue(SqQueue*Q,QElemTypee) { if((Q->rear+1)%MAXQSIZE==Q->front)//队列满 return0; Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%MAXQSIZE; return1; } //若队列不空,则删除Q的队头元素,用e返回其值,并返回1;否则返回0 intDeQueue(SqQueue*Q,QElemType*e) { if(Q->front==Q->rear)//队列空 return0; *e=Q->base[Q->front]; Q->front=(Q->front+1)%MAXQSIZE; return1; } 3、程序清单: 栈 #include #include #include //OPND栈 structND { int*base; int*top; intsize; }OPND; //OPTR栈 structTR { char*base; char*top; intsize; }OPTR; //构建OPND空栈 structNDInitStack_ND(structND*S) { S->base=(int*)malloc(10*sizeof(int)); S->top=S->base; S->size=1; } //构建OPTR空栈 structTRInitStack_TR(structTR*S) { S->base=(char*)malloc(10*sizeof(char)); S->top=S->base; S->size=1; } //用e返回OPND栈的顶元素 structNDTOP_ND(structND*S,int*e) { //if(S->base==S->top) //return0; *e=*(S->top-1); } //用e返回OPTR栈的顶元素 structTRTOP_TR(structTR*S,char*e) { //if(S->base==S->top) //return0; *e=*(S->top-1); } //在OPND栈中插入e structNDPUSH_ND(structND*S,inte) { *(S->top)=e; ++(S->top); } //在OPTR栈中插入e structTRPUSH_TR(structTR*S,chare) { *(S->top)=e; ++(S->top); } //删除OPND顶栈 structNDPOP_ND(structND*S,int*e) { //if(S->base==S->top) //return0; --(S->top); *e=*(S->top); } //删除OPTR顶栈 structTRPOP_TR(structTR*S,char*e) { //if(S->base==S->top) //return0; --(S->top); *e=*(S->top); } //运算符优先级 charPrecede(chara,charb) { inti,j; charc[7][7]={ {'>','>','<','<','<','>','>'}, {'>','>','<','<','<','>','>'}, {'>','>','>','>','<','>','>'}, {'>','>','>','>','<','>','>'}, {'<','<','<','<','<','=',''}, {'>','>','>','>','','>','>'}, {'<','<','<','<','<','','='} }; switch(a) { case'+': i=0;break; case'-': i=1;break; case'*': i=2;break; case'/': i=3;break; case'(': i=4;break; case')': i=5;break; case'#': i=6;break; } switch(b) { case'+': j=0;break; case'-': j=1;break; case'*': j=2;break; case'/': j=3;break; case'(': j=4;break; case')': j=5;break; case'#': j=6;break; } returnc[i][j]; } //计算a和b的值 intOperate(inta,chartheta,intb) { inti,j,result; i=a; j=b; switch(theta) { case'+': result=i+j;break; case'-': result=i-j;break; case'*': result=i*j;break; case'/': result=i/j;break; } returnresult; } intIn(charc) { switch(c) { case'+': case'-': case'*': case'/': case'(': case')': case'#': return1;break; default: return0; } } intC(charz[]) { inti,s=0; for(i=0;z[i]! =0;i++) s=s*10+(z[i]-'0'); returns; } intExpression() { inti,d; charz[5]; charx,theta,c; inta,b; InitStack_TR(&OPTR); PUSH_TR(&OPTR,'#'); InitStack_ND(&OPND); TOP_TR(&OPTR,&x); c=getchar(); while(c! ='#'||x! ='#') { if(In(c)==0) { i=0; do { z[i]=c; i++; c=getchar(); }while(c>='0'&&c<='9'); z[i]=0; d=C(z); PUSH_ND(&OPND,d); } else { switch(Precede(x,c)) { case'<': //栈顶元素优先级低 PUSH_TR(&OPTR,c); c=getchar(); break; case'=': POP_TR(&OPTR,&x);//脱括号并接受下一字符 c=getchar(); break; case'>': //退栈并将运算结果入栈 POP_TR(&OPTR,&theta); POP_ND(&OPND,&b); POP_ND(&OPND,&a);//delete PUSH_ND(&OPND,Operate(a,theta,b)); break; } }TOP_TR(&OPTR,&x); } TOP_ND(&OPND,&d); returnd; } main() { intc; printf("请输入要计算的表达式,以字符#结束: \n"); c=Expression(); printf("Result=%d\n",c); } 队列 #include #include
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 报告