实现线表(顺序存储)的按值查找功能.doc

程序设计与算法分析实验报告 学院：通信与信息工程学院班级：电子商务1002姓名：闫树彬 学号：1007100213 程序设计与算法分析实验报告一 设计的目的与内容1.设计目的通过本实验需要掌握顺序表的顺序存储结构，进一步熟悉c语言的函数的基本结构，掌握程序间的相互关系，需要完成建立一个顺序存储结构的线性表，并且通过遍历完成按值查找的过程。2实验内容用C语言编写一个顺序存储结构的线性表程序，实现按值查找功能。二 算法的基本思想1.数据结构的设计从第一个元素L-elem0起依次和x比较，当找到一个与x相等的数据元素后，则返回它在顺序表中的序号；当查找整个线性表一遍没有找到与x相等的元素时，则返回-1.2.算法的基本思想本算法的主要运算是比较。比较的次数与x在表中的位置有关，也与表长有关。当L-elem0=x时，比较一次成功；当L-elemL-last=x时，比较n次成功，平均比较次数为（n+1）/2,时间复杂度为O（n）。三 源程序代码及测试结果1. 源程序代码#include #define MAXLen 100/定义了一个结构体，包含线性表的数组和下标特征typedef struct Linear_list int elemMAXLen; / 定义一个线性表的足够大的一维数组 int last; /线性表中最后一个元素在数组中的位置 SeqList; /线性表的创建过程SeqList *InitList( ) SeqList *L; L=( SeqList *)malloc(sizeof(SeqList); /分配100个空间连续的一维数组 L-last=-1; /数组长度为0 return L; /建立实际的线性表，返回数组的大小SeqList *create (SeqList *L )int i,n,temp;printf(请输入实际数组的大小n:);scanf(%d,&n);printf(n请输入实际数组中的各个数值:);for(i=0;in;i+) /循环输入顺序表中的各个数值 scanf(%d,&temp); (*L).elemi=temp; (*L).last=n; printf(n实际数组大小:); printf(%d, (*L).last); return L;void disp(SeqList *L)int i;printf(nn输出线性表为:);if (*L).last=-1) printf(n输出空线性表); for(i=0;i(*L).last;i+)printf(%d,(*L).elemi); /按值查找的源代码int LocastList(SeqList *L,int x) int i=0; while(ilast &L-elemi!=x) /*查找x在线性表中的位置*/ i+; if(iL-last) /判断是否溢出 return (-1); else return (i+1); /返回x的位置(实际位置，不是存储的位置)/主函数的调用void main() SeqList *L,*t; int flag,x; L= InitList(); t= create (L); printf(n请输入要查找的数x:); scanf(%d,&x); disp(t); flag= LocastList(t,x); if(flag!=-1) disp(t); printf(nx在线性表中的位置是:%dn,flag); /实际位置，不是存储的位置2. 测试结果3.存在的问题及解决刚开始主函数的调用老写错，结果错误很多，后来，把主函数写对了，错误就没了。四 分析与讨论刚开始的时候写出来的程序是x是程序中给定的值，后来我们讨论改进了一下，printf(n请输入要查找的数x:);scanf(%d,&x);加入了这么一小段程序，结果程序变得好多了。可以自己从键盘输入x的值了，不是固定的一个值了。五 心的体会由于c的基础没打好，所以一直感觉程序很难写，这次通过写这个程序，刚开始真的很困难，花费了很多的时间，期间很久都调不通，不过还好，最后通过讨论，