《数据结构》实验指导书(新)

1数据结构实验指导书实验一线性表[实验目的]1．了解顺序表的结构特点及有关概念，掌握顺序表建立、插入、删除的基本操作算法。2．了解单链表的结构特点及有关概念，掌握单链表建立、插入、删除的基本操作算法。[实验内容]1．顺序表的实践。1)建立4个元素的顺序表list[]={2，3，4，5}，实现顺序表建立的基本操作。2)在list[]={2，3，4，5}的元素4和5之间插入一个元素9，实现顺序表插入的基本操作。3)在list[]={2，3，4，9，5}中删除指定位置（i=3）上的元素9，实现顺序表的删除的基本操作。2．单链表的实践。1)建立一个包括头结点和3个结点的（4，2，1）的单链表，实现单链表建立的基本操作。2)在已建好的单链表中的指定位置（x=2）插入一个结点3，实现单链表插入的基本操作。3)在一个包括头结点和4个结点的（4，2，3，1）的单链表的指定位置删除一个结点，实现单链表删除的基本操作。[实验要点及说明]线性表（linearlist）是n（n≥0）个数据元素a1，a2，…an组成的有限序列。其中n称为数据元素的个数或线性表的长度，当n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1，a2，…,an），其中的数据元素ai（1≤i≤n）是一个抽象的符号，ai是第i个数据元素,称i为数据元素ai在线性表中的位置。其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定，本书中，我们将它的类型设定为elemtype，表示某一种具体的已知数据类型。顺序表也称为线性表的顺序存储结构。其存储方式为：在内存中用一组地址连续的存储单元依次存储线性表的数据元素，但该连续存储空间的大小要大于或等于顺序表的长度。一般让线性表中第一个元素存放在连续存储空间第一个位置，第二个元素紧跟着第一个之后，其余依此类推。可定义顺序表如下：#definemaxnumelemtypelist[maxnum];intnum=-1;线性表的链式存贮结构，也称为链表。其存贮方式是：在内存中利用存贮单元(可以不连续)来存放元素值及它在内存的地址，各个元素的存放顺序及位置都可以以任意顺序进行，原来相邻的元素2存放到计算机内存后不一定相邻，从一个元素找下一个元素必须通过地址(指针)才能实现。故不能像顺序表一样可随机访问。常用的链表有单链表、循环链表和双向链表、多重链表等。单链表是线性表的链式存贮结构中每个结点只有一个指针域的链表。顺序表、单链表的建立，选作顺序表、单链表的插入或删除。[参考程序]1．建立顺序表#includestdio.h#definemax10main(){inti=0,x,*num,ch;intlist[max];printf(inputlist:);while((ch=getchar())!='\n'){list[i];i++;}*num=i-1;for(i=0;i=*num;i++)printf(list[%d]=%c,i,list[i]);}2．顺序表插入#includestdio.h#definemax5#definetrue1#definefalse0intinsertq(intlist[],int*num,inti,intx){intj;if((i0)||(i*num+1)){printf(mistake.);return(false);}if(*num=max-1){printf(listisfull.);return(false);}for(j=*num+1;ji;j--)list[j]=list[j-1];list[i]=x;(*num)++;return(true);3}main(){inti=0,x,*num,ch;intlist[max];printf(inputlist:);while((ch=getchar())!='\n'){list[i]=ch;i++;}*num=i-1;printf(insertNo.i:);scanf(%d,&i);getchar();printf(insertdata:);x=getchar();getchar();insertq(list,num,i,x);for(i=0;i=*num;i++)printf(list[%d]=%c,i,list[i]);printf(\n);}3．单链表插入#includestdio.h#definenull0typedefstructnode{intdata;structnode*next;}slnode;void*initiate(slnode**h){*h=(slnode*)malloc(sizeof(slnode));(*h)-next=null;}slnodeappend(slnode*p,intx){slnode*s;s=(slnode*)malloc(sizeof(slnode));s-data=x;s-next=p-next;p-next=s;}slnode*search(slnode*p,intx){slnode*s;s=p-next;4while(s!=null){if(s-data==x)return(s);s=s-next;}return(null);}intinsert(slnode*p,intx,inty){slnode*m,*n;n=(slnode*)malloc(sizeof(slnode));n-data=y;m=search(p,x);if(m!=null){n-next=m-next;m-next=n;return(0);}else{printf(%cnotfound.\n,x);return(-1);}}voidtravel(slnode*p){slnode*s;s=p-next;while(s!=null){putchar(s-data);s=s-next;}putchar('\n');}main(){inti,ch1,ch2,n;slnode*q,*p;initiate(&p);for(i=1;i4;i++){printf(ch%d=,i);ch1=getchar();getchar();append(p,ch1);printf(pointch%d=%c\n,i,ch1);}travel(p);printf(ch1=);5ch1=getchar();getchar();printf(ch2=);ch2=getchar();getchar();insert(p,ch1,ch2);travel(p);}[实验目的]1．了解顺序栈的结构特点及有关概念，掌握顺序栈建立及入栈的基本操作。2．了解顺序栈共用的含义及优点，掌握顺序战的基本操作。[实验内容]进行顺序栈初始化及入栈、出栈、共用，实现顺序栈建立及入栈、出栈、共用的基本操作。[实验要点及说明]栈(stack)：是限定仅在表尾进行插入或删除操作的线性表。栈顶(Top)：允许插入和删除的一端，为变化的一端。栈底(Bottom):栈中固定的一端。空栈：栈中无任何元素。特点：根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。栈的运算：1.初始化栈：Voidinitstack(＆s)将栈S置为一个空栈(不含任何元素)。2.进栈：VoidPush(&s,x)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。3.出栈：elemtypePop(&s)删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。4.取栈顶元素：Elemtypegettop(s)取栈S中栈顶元素。5.判栈空：Intempty(s)判断栈S是否为空，若为空，返回值为1，否则返回值为0。6.置空栈：voidclearstack(&s)顺序栈的数据类型：#definestacksize100//定义栈的最大容量为maxlenTypedefintelemtype;typedefStruct{elemtypedata[stacksize+1];//将栈中元素定义为elemtype类型inttop;//:指向栈顶位置的指针6}sqstack;[参考程序]1．顺序栈初始化及入栈#includestdio.h#definemax10typedefstruct{charstack[max];inttop;}qstype;voidinitiateqs(qstype*s){s-top=-1;}intpush(qstype*s,intx){if(s-top=max-1)return(0);else{s-top++;s-stack[s-top]=x;return(1);}}main(){intch,sign;qstype*s;initiateqs(s);printf();scanf(%d,&ch);while(ch!=-1)if((sign=push(s,ch))==0){printf(overflow\n);break;}elsescanf(%d,&ch);while(s-top!=1){s-top--;printf(stack=%d\n,s-stack[s-top+1]);}printf(\n);}顺序栈初始化及出栈#includestdio.h7#definemax10typedefstruct{charstack[max];inttop;}qstype;voidinitiateqs(qstype*s){s-top=1;}intpush(qstype*s,intx){if(s-top=max-1)return(0);else{s-top++;s-stack[s-top]=x;return(1);}}intpop(qstype*s){if(s-top0)return('\0');else{s-top--;return(s-stack[s-top+1]);}}main(){intch,sign;qstype*s;initiateqs(s);printf();scanf(%d,&ch);while(ch!=-1){if((sign=push(s,ch))!=1)break;scanf(%d,&ch);}while((ch=pop(s))!='\0')printf(%d,ch);printf(\n);}顺序栈的共用#includestdio.h#definem40typedefstruct{inttop[2];intstack[m];8}dqstype;voidinitiatedqs(dqstype*s){s-top[0]=1;s-top[1]=m;}intpushdqs(dqstype*s,inti,intx){if(s-top[0]==s-top[1]-1){printf(full);return(-1);}if(i!=0&&i!=1){printf(mistake);return(-1);}if(i==0){s-top[i]++;s-stack[s-top[i]]=x;}else{s-top[i]--;s-stack[s-top[i]]=x;}return(1);}intpopdqs(dqstype*s,inti){if(i!=0&&i!=1){printf(mistake);return('\0');}if(i==0){if(s-top[i]=-1){printf(\nstrack0empty);return('\0');}s-top[i]--;return(s-stack[s-top[i]+1]);}else{if(s-top[i]==m){printf(\nstrack1empty.);return('\0');}s-top[i]++;9return(s-