计算机软件基础实验1

北京联合大学实验报告课程（项目）名称：计算机软件技术基础实验一（顺序表）学院：自动化专业：信息处理与智能技术班级：0910030204成绩：学号：2009100302440姓名：韩禹辉2010年11月20　日一．实验目的(1)掌握线性表的概念。(2)熟练掌握线性表的顺序存储结构。(3)熟练掌握线性表在顺序存储结构上的运算。(4)了解测试的思想。2．实验内容1.逆序元素——编写算法实现顺序表中元素的逆置。要求按用户输入的数据建立一个顺序表。在逆置的过程中使用最少的辅助存储单元。2.删除多余元素——己知顺序表中的元素非递减有序排列，编写算法删除顺序表中值相同的多余的元素。3.插入元素——编写算法，在非递减有序的顺序表中，插入一个给定的元素，插入后该顺序表仍然递增有序。4.合并顺序表——有两个顺序表A(有m个元素)和B(有n个元素)，其元素均按从小到大的升序排列。编写算法，将这两个顺序表合并成一个顺序表C，要求C也是按从小到大的升序排列。三．算法设计方案1.1）函数名：InputSList1类型：SList2）入口参数：无3）出口参数：L4）功能：初始化线性表5）源程序清单:structSListInitSList(){structSListL;L.Last=-1;returnL;}2.1）函数名：InputSList1类型：SList2）入口参数：L3）出口参数：L4）功能：建立无序顺序表5）设计思路：定义顺序表结构体，从键盘输入数据给x，用指针指向顺序表的表尾元素，在表满之前，每输入一个新的不为一数据时，尾指针后移一位，直到输入的数据为负一或表满时完成建立。6）流程图开始定义intxscanf(%d,&x)Yx=-1？NYL.Last==MAXSIZE-1？结束输入NL.Data[L.Last]=x++L.Last7）源程序清单structSListInputSList1(structSListL){intx=0;printf(\n请输入数据，结束输入-1！\n);scanf(%d,&x);while(x!=-1){L.Data[++L.Last]=x;if(L.Last==MAXSIZE-1){printf(\n顺序表已满!\n);break;}scanf(%d,&x);}returnL;}3.1）函数名：InputSList类型：SList2）入口参数：L3）出口参数；L4）功能：向线性表中输入数据5）设计思路：创建空线性表，从键盘输入数据到线性表中，以-1结束，然后修改表长，输出线性表。6）源程序清单structSListInputSList(structSListL){inti=0;intnumber=0;printf(\n请输入顺序表的初始化数据，以-1表示结束\n);while(i30){scanf(%d,&number);if(number==-1){break;}L.Data[i]=number;L.Last++;i++;}for(intj=0;j=L.Last;j++){printf(%d,L.Data[j]);}returnL;}7）流程图：创建空线性表从键盘输入数据到线性表中输入的数据为-1NY线性表已满NY将该元素存入线性表中，并修改表长结束输入输出线性表中元素4.1）函数名：outputSList类型：SList2）入口参数：L3）出口参数：无4）功能：输出顺序表5）设计思路：定义指针j指向顺序表中下标为0处，当表不为空时，指针依次向后移动，每移动到一个数据所在的位置时将其输出，直到移动到表尾将所有数据输出后为止。6）源程序清单voidoutputSList(structSListL){intj;printf(\n顺序表的数据为：\n);if(L.Last!=-1)for(j=0;j=L.Last;j++)printf(%d,L.Data[j]);elseprintf(顺序表为空!\n);printf(\n);}7）流程图：开始定义intjL.Last==-1？Nj=0;j=L.Lastprintf(%d,L.Data[j])顺序表为空!j++5.1）函数名：reverse类型：SList2）入口参数：*L3）出口参数：无4）功能：将顺序表中元素的逆置5）设计思路：定义两个指针变量i，j和结点t。i指向下标为0处，j指向下标为L.length-1处，i++,j--，利用循环将i、j所指向的数据交换。6）源程序清单voidreverse(SList*L){inti,j;datatypet;for(i=0,j=L-length-1;ij;i++,j--){t=L-data[i];L-data[i]=L-data[j];L-data[j]=t;}}7）流程图：开始定义inti,jdatatypeti=0,j=L-length-1t=L-data[i];L-data[i]=L-data[j];L-data[j]=t;i++,j--6.1）函数名：delete类型：SList2）入口参数：L3）出口参数；无4）功能：删除顺序表中值相同的多余的元素5）设计思路：i++，利用循环，将第i个元素后面的元素和此元素进行比较，若有和此元素想等的元素，利用a[k]=a[k+1]的思想将其删除。6）流程图：开始i=0;i=L.Last;i++j=i+1;jL.Last;j++L.Data[i]==L.Data[j]k=j;kL.Last;k++L.Data[k]=L.Data[k+1]L.Last--;j--;OutputL.Data[j]7）源程序清单：voiddelete(structSListL){inti=0,j=0,k=0;for(i=0;i=L.Last;i++){for(j=i+1;jL.Last;j++){if(L.Data[i]==L.Data[j]){for(k=j;kL.Last;k++)L.Data[k]=L.Data[k+1];L.Last--;j--;}}}for(j=0;j=L.Last;j++){printf(%d,L.Data[j]);}}7.1）函数名：insert类型：SList2）入口参数：L,x3）出口参数：L4）功能：插入元素x到非递减有序的顺序表中5）设计思路：通过一个while循环查找适合x插入的位置，利用一个for循环将该位置后的所有数据后移一位给要插入的x留出位置，再将x放入该位置，最后修改表长。6）源程序清单：voidinsert(SList*L,intx){inti,k;i=0;while((iL-length-1)&&(x=L-data[i]))i++;for(k=L-length-1;k=i;k--)L-data[k+1]=L-data[k];L-data[i]=x;L-length++;}7）流程图：开始查找适合X插入的位置k=ik--，L-data[k+1]=L-data[k]L-data[i]=xL-length++8.1）函数名：unit类型：SList2）入口参数：L,L2,L33）出口参数：L34）功能：将两个有序顺序表合并5）设计思路：6）源程序清单（程序应添加必要的注释）voidunit(structSListL,structSListL1,structSListL2){inti=0,j=0,k=0,m=0;while(i=L1.Last&&j=L2.Last){if(L1.Data[i]L2.Data[j])L.Data[k++]=L1.Data[i++];elseL.Data[k++]=L2.Data[j++];}while(i=L1.Last){L.Data[k++]=L1.Data[i++];}while(j=L2.Last){L.Data[k++]=L2.Data[j++];}L.Last=k-1;for(m=0;m=L.Last;m++){printf(%d,L.Data[m]);}printf(\n);}7）流程图：开始inti=0,j=0,k=0,m=0i=L1.Last&&j=L2.LastYYL1.Data[i]L2.Data[j]NL.Data[k++]=L2.Data[j++]L.Data[k++]=L1.Data[i++]i=L1.Lastj=L2.LastL.Data[k++]=L2.Data[j++]L.Data[k++]=L1.Data[i++]L.Last=k-1for(m=0;m=L.Last;m++)printf(%d,L.Data[m]4．调试过程（1）编译出现的主要问题及解决方法L-data[i]=t;L-data[i]=L-data[j];L-data[j]=tt=L-data[i];L-data[i]=L-data[j];L-data[j]=tfor(i=0;i=L1.length;i++)for(i=0;i=L1.length-1;i++)L.Data[k+1]=L.Data[k];L.Data[k]=L.Data[k+1];scanf(%d,&data)scanf(%d,&data)（2）运行出现的主要问题及解决方法5．运行结果分析（1）运行结果逆置：删除多余元素：插入：合并：（2）运行结果分析逆置测试项输入参数输出参数存在问题空表无无无表长=5（奇数）1234554321无表长=6（偶数）123456654321无删除相同元素测试项输入参数输出参数存在问题空表无无无有1组相同元素12234512345无有2组相同元素1223341234无有3组相同元素11223341234无插入测试项输入参数输出参数存在问题空表无无无在表头插入向34567中插入1134567无在表尾插入向25689中插入4245689无在表中间插入向34678中插入5345678无合并测试项输入参数输出参数存在问题1，2均为空无无无1空2不空1：无2：2345623456无1，2均不空1：135792：2468123456789无6、体会通过本次实验，收获了很多，使我对计算机软件技术有了更深的了解，在学习探索的过程中，更发现了许多自己的不足。在编程过程中，遇到了很多的困难，因为C语言知识不是很扎实，导致这次实验不是很顺利，但是在老师和同学的帮助下，最后终于能及时的完成这次实验，谢谢老师和同学们的帮助！仔细推敲之后，才发现这个实验并不是很难。只要勇敢的面对它，就能克服一切困难。通过这次实验,更深刻的理解并掌握了线性表的概念;熟练掌握线性表的顺序存储结构和线性表在顺序存储结构上的运算;了解测试的思想。