《数据结构》实验指导书(C语言版)(浦江学院)

1实验1:顺序表的操作实验一、实验名称和性质所属课程数据结构实验名称顺序表的操作实验学时4实验性质√验证□综合√设计必做/选做√必做□选做二、实验目的1．掌握线性表的顺序存储结构的表示和实现方法。2．掌握顺序表基本操作的算法实现。3．了解顺序表的应用。三、实验内容1．建立顺序表。2．在顺序表上实现插入、删除和查找操作（验证性内容）。3．删除有序顺序表中的重复元素（设计性内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号：Windows环境下的VC++6.0五、知识准备前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。六、验证性实验1．实验要求编程实现如下功能：（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。（4）在顺序表中查找值为e的数据元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。2.实验相关原理线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：#defineMAXLEN30/*线性表的最大长度*/typedefstruct{Elemtypeelem[MAXLEN];/*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/2intlength;/*顺序表的长度，即元素个数*/}Sqlist;/*顺序表的类型*/【核心算法提示】（1）顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。（2）顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i的合法性，i的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。（3）顺序表查找操作的基本步骤：要在顺序表中查找一个给定值为e的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值e进行比较，若相等则查找成功，函数返回该数据元素在顺序表中的位置，若顺序表中所有元素都与给定值e不相片，则查找失败，函数返回0值。【核心算法描述】statusSqlist_insert(Sqlist&L,inti,Elemtypex)/*在顺序表L中第i个元素前插入新元素x*/{if(i1||iL.length+1)returnERROR;/*插入位置不正确则出错*/if(L.length=MAXLEN)returnOVERFLOW;/*顺序表L中已放满元素，再做插入操作则溢出*/for(j=L.length-1;j=i-1;j--)L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/L.elem[i-1]=x;/*在第i个元素位置处插入新元素x*/L.length++;/*顺序表L的长度加1*/returnOK;}statusSqlist_delete(Sqlist&L,inti,Elemtype&e)/*在顺序表L中删除第i个元素*/{if(i1||iL.length)returnERROR;/*删除位置不正确则出错*/for(j=i;j=L.length-1;j++)L.elem[j-1]=L.elem[j];/*将第i+1个元素及后继元素位置向前移一位*/L.length--;/*顺序表L的长度减1*/returnOK；}intSqlist_search(SqlistL,Elemtypex)/*在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/3{for(i=1;i=L.length&&L.elem[i-1]!=x;i++);/*从第一个元素开始依次将每个元素值与给定值x比较*/if(i=L.length)returni;elsereturno;}3．源程序代码参考#includestdio.h#defineMAXLEN50typedefstruct{intelem[MAXLEN];intlength;}Sqlist;SqlistSqlist_insert(SqlistL,inti,intx)/*顺序表插入函数*/{intj;if(i1||iL.length+1)printf(ERROR!);elseif(L.length=MAXLEN)printf(OVERFLOW!);else{for(j=L.length-1;j=i-1;j--)L.elem[j+1]=L.elem[j];L.elem[i-1]=x;L.length++;}returnL;}SqlistSqlist_delete(SqlistL,inti)/*顺序表删除函数*/{intj;if(i1||iL.length)printf(ERROR!);else{for(j=i;j=L.length-1;j++)L.elem[j-1]=L.elem[j];L.length--;}returnL;}intSqlist_search(SqlistL,intx)/*顺序表查找函数*/{inti;for(i=1;i=L.length&&L.elem[i-1]!=x;i++);4if(i=L.length)returni;elsereturn0;}voidSqlist_display(SqlistL)/*顺序表元素输出函数*/{intj;for(j=0;j=L.length-1;j++)printf(%4d,L.elem[j]);printf(\n);}voidmain()/*主函数*/{SqlistL;inti,x,j;printf(\npleaseinputthelength:);/*请求输入顺序表中元素个数*/scanf(%d,&L.length);printf(pleaseinputtheValue:\n);/*请求输入顺序表中各个元素*/for(j=0;j=L.length-1;j++)scanf(%d,&L.elem[j]);printf(pleaseinputtheinsertposition:);/*请求输入插入操作位置*/scanf(%d,&i);printf(pleaseinputtheinsertnode:);/*请求输入需要插入的新元素*/scanf(%d,&x);L=Sqlist_insert(L,i,x);/*调用顺序表插入函数*/Sqlist_display(L);/*调用顺序表元素输出函数*/printf(pleaseinputthedeleteposition:);/*请求输入删除操作位置*/scanf(%d,&i);L=Sqlist_delete(L,i);/*调用顺序表删除函数*/Sqlist_display(L);/*调用顺序表元素输出函数*/printf(pleaseinputthesearchnode:);scanf(%d,&x);if(Sqlist_search(L,x))/*如果查找成功，则显示查找成功和找到的元素位置，否则显示查找不成功*/printf(searchissuccessand%dis%dposition\n,x,Sqlist_search(L,x));elseprintf(searchisunsuccess\n);}54．运行结果参考如图1-1所示图1-1验证性实验运行结果七、设计性实验编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。（1）实验要求①根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。②删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。（2）核心算法提示要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第1个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。（3）非核心源代码提示#includestdio.h#definemaxsize100typedefstructnode{intdata[maxsize];intlast;}seqList;intmain(){inti=0,j,k;seqListL;6scanf(%d,&L.last);for(i=0;iL.last;i++)scanf(%d,&L.data[i]);//核心算法代码for(i=0;iL.last;i++)printf(%d,L.data[i]);return0;}7实验2:链表的操作实验一、实验名称和性质所属课程数据结构实验名称链表的操作实验学时4实验性质√验证□综合√设计必做/选做√必做□选做二、实验目的1．掌握线性表的链式存储结构的表示和实现方法。2．掌握链表基本操作的算法实现。三、实验内容1．建立单链表，并在单链表上实现插入、删除和查找操作（验证性内容）。2．建立带有头结点的单向链表，并计算出该单向链表中各结点数据域之和（设计性内容）。3．建立双向链表，并在双向链表上实现插入、删除和查找操作（设计性内容）。四、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号：Windows环境下的VC++6.0五、知识准备前期要求熟练掌握了C语言的编程规则、方法和单链表和双向链表的基本操作算法。六、验证性实验1．实验要求编程实现如下功能：（1）根据输入的一系列整数，以0标志结束，用头插法建立单链表，并输出单链表中各元素值，观察输入的内容与输出的内容是否一致。（2）在单链表的第i个元素之前插入一个值为x的元素，并输出插入后的单链表中各元素值。（3）删除单链表中第i个元素，并输出删除后的单链表中各元素值。（4）在单链表中查找第i个元素，如果查找成功，则显示该元素的值，否则显示该元素不存在。2.实验相关原理线性表的链式储结构是用一组任意的存储单元依次存放线性表中的元素，这组存储单元可以是连续的，也可以是不连续的。为反映出各元素在线性表中的前后逻辑关系，对每个数据元素来说，除了存储其本身数据值之外，还需增加一个或多个指针域，每个指针域的值称为指针，又称作链，它用来指示它在线性表中的前驱或后继的存储地址。这两个部分的的一起组成一个数据元素的存储映像，称为结点，若干个结点链接成链表。如果一个结点中只含一个指针的链表，则称单链表。单链表的存储结构描述如下：8TypedefstructLnode{Elemtypedata;/*数据域*/StructLnode*next;/*指针域*/}LNODE,*Linklist;/*其中LNODE为结点类型名，Linklist为指向结点的指针类型名*/【核心算法提示】（1）链表建立操作的基本步骤：链表是一个动态的结构，它不需要予分配空间，因此建立链表的过程是一个结点“逐个插入”的过程。先建立一个只含头结点的空单链表，然后依次生成新结点，再不断地将其插入到链表的头部或尾部，分别称其为“头插法”和“尾插法”。（2）链表查找操作的基本步骤：因链表是一种“顺序存取”的结构，则要在带头结点的链表中查找到第i个元素，必须从头结点开始沿着后继指针依次“点数”，直到点到第i个结点为止,如果查找成功，则用e返回第i