《数据结构》课程设计实验报告

《数据结构》课程设计实验报告数据结构与算法实验一（顺序表的操作）一、实验目的1．掌握线性表的顺序存储结构的表示和实现方法。2．掌握顺序表基本操作的算法实现。3．了解顺序表的应用。二、实验内容1．建立顺序表。2．在顺序表上实现插入、删除和查找操作（验证性内容）。3．删除有序顺序表中的重复元素（设计性内容）。4．完成一个简单学生成绩管理系统的设计（应用性设计内容）。三、实验的软硬件环境要求硬件环境要求：PC机（单机）使用的软件名称、版本号以及模块：Windows环境下的VC++等。四、知识准备前期要求熟练掌握了C语言的编程规则、方法和顺序表的基本操作算法。五、验证性实验1．实验要求编程实现如下功能：（1）根据输入顺序表的长度n和各个数据元素值建立一个顺序表，并输出顺序表中各元素值，观察输入的内容与输出的内容是否一致。（2）在顺序表的第i个元素之前插入一个值为x的元素，并输出插入后的顺序表中各元素值。（3）删除顺序表中第i个元素，并输出删除后的顺序表中各元素值。（4）在顺序表中查找第i个元素，如果查找成功，则显示“查找成功”和该元素在顺序表中的位置，否则显示“查找失败”。2.实验相关原理：线性表的顺序存储结构称为顺序表，顺序表的存储结构描述为：#defineMAXLEN30/*线性表的最大长度*/typedefstruct{Elemtypeelem[MAXLEN];/*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/intlength;/*顺序表的长度，即元素个数*/}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．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回0值。【核心算法描述】。statusSqlist_insert(Sqlist&L,inti,Elemtypex)/*在顺序表L中第i个元素前插入新元素x*/{if(i<1||i>L.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(i<1||i>L.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*/{for(i=0;i<L.length&&L.elem[i]!=x;i++);/*从第一个元素开始依次将每个元素值与给定值x比较*/if(i<L.length)returni;elsereturno;}。3．学生实验代码#include"stdio.h"#defineMaxSize50typedefstructnode{intelem[MaxSize];intlength;}Sqlist;Sqlistcreat(SqlistL,intn){inti=0;for(i=0;i<n;i++){intx;printf("请输入值：");scanf("%d",&x);L.elem[i]=x;}L.length=n;returnL;}voidprint(SqlistL){for(inti=0;i<L.length;i++)printf("%4d",L.elem[i]);printf("\n");}SqlistSqlist_insert(SqlistL,inti,intx){if(i<1||i>L.length)printf("error");if(L.length>=MaxSize)printf("overflow");for(intj=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];L.elem[i-1]=x;L.length++;returnL;}SqlistSqlist_delete(Sqlist&L,inti,inte){if(i<1||i>L.length)printf("error");//if(L.length>=MaxSize)//printf("overflow");for(intj=i;j<=L.length-1;j++)L.elem[j-1]=L.elem[j];L.length--;returnL;}intSqlist_search(SqlistL,intx){inti;for(i=0;i<L.length&&L.elem[i]!=x;++i);if(i<L.length)returni;elsereturn-1;}intmain({Sqlisthead;intn,k,i,x;printf("请输入n的值：");scanf("%d",&n);head=creat(head,n);print(head);printf("请输入插入i位置的值：");scanf("%d",&i);printf("请输入要插入x的值：");scanf("%d",&x);head=Sqlist_insert(head,i,x);print(head);printf("请输入要删除的i位置的值：");scanf("%d",&i);head=Sqlist_delete(head,i,x);print(head);printf("请输入要查找的值：");scanf("%d",&x);k=Sqlist_search(head,x);if(k==-1)printf("NOTfound\n");elseprintf("要查找的%d在%d位置上",x,k+1);return0;}。4．运行结果六、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成)1．编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。⑴实验要求①根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。②删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。⑵核心算法提示要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第1个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。⑶核心算法描述SqlistdelSqlist(SqlistL){inti=0,j;while(i<L.length-1)if(L.elem[i]==L.elem[i+1])/*如果第i个及第i+1个相邻元素值相等*/{for(j=i+1;j<L.length;j++)/*将第i+1个元素及其之后的所有元素前移一个位地置，以达到删除第i个元素的目的*/L.elem[j-1]=L.elem[j];L.length--;/*有序顺序表的表长减1*/}elsei++;returnL;}。2．编程实现一个简单学生成绩表的操作。实验要求此系统的功能包括：①查询：按特定的条件查找学生②