数据结构实验

实验一实验内容：(1)输入一组数据存入数组中，并将数据元素的个数动态地由输入函数完成。求输入数据的最大值、最小值，并通过函数参数返回所求结果；(2)用C语言程序中学过的冒泡法对输入的数据进行排序，并输出排序后的结果(算法的类C描述如下)。voidbubble_sort(inta[],intn){for(i=n-1,change=TRUE;i=1&&change;--i){change=FALSE;for(j=0;ji;++j)if(a[j]a[j+1]){a[j]----a[j+1];change=TRUE;}}}//bubblesortC语言源程序代码（TC下环境运行）：includestdio.h#defineN10intMaxIndex(intnArr[],intn);intMinIndex(intnArr[],intn);intMaxIndex(intnArr[],intn){intindex_no=n-1;for(n--;n=0;n--)index_no=(nArr[index_no]=\nArr[n])?index_no:n;returnindex_no;}intMinIndex(intnArr[],intn){intindex_no=n-1;for(n--;n=0;n--)index_no=(nArr[index_no]=\nArr[n])?n:index_no;returnindex_no;}intmain(void){intnArr[N],i,Max,Min,index_no;clrscr();for(i=0;iN;i++){printf(nArr[%d]=,i);scanf(%d,&nArr[i]);printf(\n);}index_no=MaxIndex(nArr,N);Max=nArr[index_no];printf(Themaxis%d\n,Max);index_no=MinIndex(nArr,N);Min=nArr[index_no];printf(Theminis%d\n,Min);return0;}数据结构实验二线性表及其基本操作实验(2010-06-0320:52:40)转载▼标签：杂谈实验内容：(1)一元多项式运算的C语言程序实现(加法必做，其它选做)；(2)有序表的合并；(3)集合的并、交、补运算；(4)约瑟夫问题的求解。算法描述的程序代码：有序表的合并C程序代码如下：#includestdio.h#includestdlib.h#includemalloc.h#defineOK1#defineERROR0#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefintElemType;typedefintStatus;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_sq(SqList*A){A-elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!A-elem)returnERROR;A-length=0;A-listsize=LIST_INIT_SIZE;returnOK;}intInput_Sq(SqList*L){inti;if(L-length==0)printf(TheListisempty!);else{for(i=0;iL-length;i++)printf(%d,L-elem[i]);}printf(\n);returnOK;}SqListMergeList_Sq(SqListA,SqListB,SqListC){ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=A.elem;pb=B.elem;C.listsize=C.length=A.length+B.length;pc=C.elem=(ElemType*)malloc(C.listsize*sizeof(ElemType));if(!C.elem)exit(ERROR);pa_last=A.elem+A.length-1;pb_last=B.elem+B.length-1;while((papa_last)&&(pbpb_last)){if(*pa=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa=pa_last)*pc++=*pa++;while(pb=pb_last)*pc++=*pb++;returnC;}intmain(void){SqListA;SqListB;SqListC;inta,b,i;clrscr();InitList_sq(&A);InitList_sq(&B);InitList_sq(&C);printf(InputA'sgeshu:);scanf(%d,&a);for(i=0;ia;i++){printf(A.elem[%d]=,i);scanf(%d,&A.elem[i]);A.length++;}printf(InputB'sgeshu:);scanf(%d,&b);for(i=0;ib;i++){printf(B.elem[%d]=,i);scanf(%d,&B.elem[i]);B.length++;}printf(\n);printf(ListA:);Input_Sq(&A);printf(ListB:);Input_Sq(&B);C=MergeList_Sq(A,B,C);printf(ListC:);Input_Sq(&C);return0;}一元多项式的加法C程序代码如下：#includestdio.h#includemalloc.h#includestdlib.htypedefstructpolynode{intcoef;intexp;structpolynode*next;}node;create(void){node*h,*r,*s;intc,e;h=(node*)malloc(sizeof(node));r=h;printf(coef:);scanf(%d,&c);printf(exp:);scanf(%d,&e);while(c!=0){s=(node*)malloc(sizeof(node));s-coef=c;s-exp=e;r-next=s;r=s;printf(coef:);scanf(%d,&c);printf(exp:);scanf(%d,&e);}r-next=NULL;return(h);}voidpolyadd(node*polya,node*polyb){node*p,*q,*m,*temp;intsum;p=polya-next;q=polyb-next;m=polya;while(p!=NULL&&q!=NULL){if(p-expq-exp){m-next=p;m=m-next;p=p-next;}elseif(p-exp==q-exp){sum=p-coef+q-coef;if(sum!=0){p-coef=sum;m-next=p;m=m-next;p=p-next;temp=q;q=q-next;free(temp);}else{temp=p-next;free(p);p=temp;temp=q-next;free(q);q=temp;}}else{m-next=q;m=m-next;q=q-next;}}if(p!=NULL)m-next=p;elsem-next=q;}voidprint(node*p){while(p-next!=NULL){p=p-next;printf(%d*x^%d+,p-coef,p-exp);}}intmain(void){node*polya,*polyb;clrscr();printf(\nPleaseinputtheploya'scoefandexp:\n);polya=create();print(polya);printf(\nPleaseinputtheployb'scoefandexp:\n);polyb=create();print(polyb);printf(\nSumofthepolyis:\n);polyadd(polya,polyb);print(polya);printf(\n);return0;}数据结构实验三栈和队列(2010-09-1407:15:34)转载▼标签：杂谈一、实验目的及要求(1)熟练掌握栈和队列的抽象数据类型及其结构特点；(2)实现基本的栈和队列的基本操作算法程序。二、实验内容：(类C算法的程序实现，任选其一)(1)设计与实现基本的堆栈和队列结构下的各种操作（如堆栈的PUSH、POP等操作）(必做)；(2)以表达式计算为例，完成一个可以进行算术表达式计算功能的算法设计与实现（选做）；(3)以迷宫问题为例，以堆栈结构完成迷宫问题的求解算法和程序（选做）。三、实验准备1)计算机设备；2)程序调试环境的准备，如TC环境；3)实验内容的算法分析与代码设计与分析准备。四、实验步骤和实验过程(该部分不够填写.请填写附页)1,对实验问题的描述：堆栈：利用栈的顺序存储表示实现堆栈的基本操作，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。一个较合理的做法是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时再逐段扩大。队列：队列的实现方法类似于堆栈，不同的是队列是一种先进先出的线性表，利用循环队列实现队列的各种基本操作，需要两个分别指示队头和队尾的指针。算术表达式：算术表达式求值是栈应用的一个典型例子。首先要了解算术四则运算的规则，比较运算符之间的优先级别。算法德基本思想为：首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；依次读入表达式中的每个字符，判断是数还是运算符，进行判断。2，算法的数据结构堆栈的顺序存储表示基本数据结构如下：#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack；循环队列---队列的顺序存储结构#defineMAXQSIZE100typedefstruct{QElemType*base;intfront;intrear;}SqQueue;3，算法基本操作的说明及分析堆栈的各种操作算法实现：①，用e返回S的栈顶元素的算法实现：StatusGetTop(SqStackS,SElemType*e){if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}//GetTop②，进栈的操作及算法：进栈的主要操作：1，栈顶下标加一；2，将入栈元素放入到新的栈顶下标所指的位置上。算法如下：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;returnOK;}//Push③,退栈的操作及算法：退栈的主要操作是：1,首先将栈顶元素取出，并由参数返回；2,将栈顶下标减一。算法如下：StatusP