数据结构试验报告

..数据结构实验报告学院：数理与信息工程学院姓名：班级：学号：..一、线性表实验一：顺序表的删除（一）实验目的：1.掌握使用C++上机调试线性表的基本方法；2.掌握线性表的基本操作：插入、删除、查找等运算在顺序存储结构上的实现。（二)实验内容：实现一个线性表，对一个n不超过1000的线性表进行删除操作。（三）实验程序：#includestdio.h#includestdlib.htypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;intmain(){intn,m;while(scanf(%d,&n)!=EOF){LinkListL=(LinkList)malloc(sizeof(LNode));L-next=NULL;..LinkListp=L,q;for(inti=1;i=n;i++){q=(LinkList)malloc(sizeof(LNode));scanf(%d,&q-data);q-next=NULL;p-next=q;p=q;}scanf(%d,&m);for(intj=1;j=m;j++){intnum;scanf(%d,&num);p=L;intk;inte=-1;if(num=1&&num=n){for(k=1;knum;k++){p=p-next;}q=p-next;p-next=q-next;e=q-data;..n--;free(q);}printf(%d\n,e);}}}（四）运行结果：（五）实验总结：初次接触数据结构，心理有些期待，也有些畏惧。因为没学习过这种程序，心里总担心着能不能把它学好呢？当我们把该章节学完就尝试着做这个实验，说实话突然从理论到实验还是消化不了呢，后来，通过慢慢的揣摩和问老师和同学，慢慢的做完了。实验二：链表及其多项式相加（一）实验目的：1.掌握使用C++上机调试线性表的基本方法；..2.掌握线性表的基本操作：插入、删除、查找等运算在链式存储结构上的实现。3.掌握基于链表的多项式相加的算法。（二）实验内容：通过有序对输入多项式的各个项，利用单链表存储该一元多项式，并建立的2个存储一元多项式的单链表，然后完成2个一元多项式的相加，并输出相加后的多项式。（三）实验程序:#includestdio.h#includestdlib.h#includemalloc.h#includeconio.htypedefstructLnode{intcof;intexpn;structLnode*next;}Lnode,*LinkList;voidCreatpolyn(LinkList&La,intm){inti;LinkListp,q;La=(LinkList)malloc(sizeof(Lnode));La-next=NULL;..p=La;for(i=1;i=m;i++){q=(LinkList)malloc(sizeof(Lnode));q-next=NULL;scanf(%d%d,&q-cof,&q-expn);p-next=q;p=q;}}LinkListaddpolyn(LinkList&A,LinkList&B){LinkListpa,pb,pc,Lb,p1,p2;pc=Lb=A;pa=A-next;pb=B-next;while(pa&&pb){if(pa-expn==pb-expn){pa-cof=pa-cof+pb-cof;if(pa-cof!=0){pc-next=pa;pc=pa;p2=pb;..pa=pa-next;pb=pb-next;free(p2);}else{p1=pa;p2=pb;pa=pa-next;pb=pb-next;free(p1);free(p2);}}elseif(pa-expnpb-expn){pc-next=pb;pc=pb;pb=pb-next;}elseif(pb-expnpa-expn){pc-next=pa;pc=pa;pa=pa-next;..}}pc-next=pa?pa:pb;free(B);return(Lb);}voidprintfpolyn(LinkList&p){while(p-next!=NULL){p=p-next;printf(%d%d\n,p-cof,p-expn);}}intmain(){intn1,n2;LinkListA,B,C;scanf(%d,&n1);Creatpolyn(A,n1);..scanf(%d,&n2);Creatpolyn(B,n2);C=addpolyn(A,B);printfpol（四）运行结果：（五）实验总结：在学习C语言的时候，我就对指针类型概念很模糊，更加不用说怎样运用他了。这个线性表的链式存储也是这样的。掌握了指针应该怎么指向，做实验并不是想像中的这么难，只要你自己理清楚了自己的思绪，一步一步的来，不要太急于成功了，那么，到了最后，你就会发现真的很容易。二、栈实验三：括号匹配判断算法（一）实验目的：1.掌握使用C++上机调试栈的基本方法；2.深入了解栈的特性，掌握栈的各种基本操作。..（二）实验内容：假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）或（［（））或(()])均为不正确的格式。基于栈设计一个判断括号是否正确匹配的算法。（三）实验程序:#includestdio.h#includestdlib.htypedefstructsnode{chardata;structsnode*next;}snode,*Linkstack;voidLinkstackpush(Linkstack*ls,chare){Linkstackp=(Linkstack)malloc(sizeof(snode));p-data=e;p-next=*ls;*ls=p;}intLinkstackpop(Linkstack*ls){Linkstackp;p=*ls;if(*ls==NULL)return0;(*ls)=(*ls)-next;..free(p);return1;}intLinkstackgettop(Linkstackls,char*e){if(ls==NULL)return0;*e=(ls)-data;return1;}voidinitLinkstack(Linkstack*ls){*ls=NULL;}voidmatching(charstr[]){chare;intk,flag=1;Linkstacks;initLinkstack(&s);for(k=0;str[k]!='\0'&&flag;k++){if(str[k]!='('&&str[k]!=')'&&str[k]!='['&&str[k]!=']'&&str[k]!='{'&&str[k]!='}')continue;switch(str[k]){..case'(':case'[':case'{':Linkstackpush(&s,str[k]);break;case')':if(s){Linkstackgettop(s,&e);if(e=='(')Linkstackpop(&s);elseflag=0;}elseflag=0;break;case']':if(s){Linkstackgettop(s,&e);if(e=='[')Linkstackpop(&s);elseflag=0;}elseflag=0;break;case'}':if(s){Linkstackgettop(s,&e);if(e=='}')Linkstackpop(&s);elseflag=0;}elseflag=0;break;}..}if(flag==1&&s==NULL){printf(yes\n);}elseprintf(no\n);}intmain(){charstr[8000];while(gets(str)){matching(str);}return0;}（四）运行结果：实验五：四则运算表达式求值（一）实验目的：1.掌握顺序栈的实现；2.掌握顺序栈的应用；..3.利用栈实现算法优先算法。（二）实验内容：按中缀形式输入一个四则运算的表达式，利用算法优选算法把其转换为后缀表达式输出，并求表达式的值。（三）实验程序:#includestdio.h#includestdlib.h#defineSTACK_INIT_SIZE10000#defineSTACKINCREMENT10#defineTURE1#defineFALSE0#defineINFEASIBLE-1#defineOVERFLOW-2#defineOK1#defineERROR0typedefintSelemtype;typedefintStatus;typedefstruct{Selemtype*base;Selemtype*top;intstacksize;..}Sqstack;Statusinitstack(Sqstack&s){s.base=(Selemtype*)malloc(STACK_INIT_SIZE*sizeof(Selemtype));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return0;}Statustravelstack(Sqstacks){Selemtype*p;p=s.base;printf(%c,*p++);while(p!=s.top){printf(%c,*p++);..}return0;}StatusGettop(Sqstacks){if(s.base==s.top)returnERROR;return*(s.top-1);}Statuspush(Sqstack&s,Selemtypee){if(s.top-s.base=s.stacksize){s.base=(Selemtype*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(Selemtype));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}..*s.top=e;s.top++;returnOK;}Statuspop(Sqstack&s,Selemtype&e){if(s.base==s.top)returnERROR;s.top--;e=*s.top;returnOK;}Statusbijiao(Selemtypea,Selemtypeb){switch(a){case'+':switch(b){case'+':case')':case'#':..case'-':return'';case'*':case'/':case'(':return'';}case'-':switch(b){case'+':case')':case'#':case'-':return'';case'*':case'/':case'(':return'';}case'*':switch(b){case'(':return'';case'+':case')':..case'#':case'-':case'*':case'/':return'';}case'/':switch(b){case'(':return'';case'+':case'#':case')':case'*':case'-':case'/':return'';}case'(':switch(b){case')':return'=';case'(':case'+':..case'-':case'*':case'/':return'