线性表的反复查找问题.doc

数据结构实验报告一一、 上机实验的问题：1、 LIST_INIT_SIZE不被计算机程序所认可2、 getchar（）在程序中的作用，是否作用于运行结果中的“Press any key to contiune”二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）基本思想和原理：利用线性表的顺序存储方式和求余运算符的运用，将1000次进洞逐一与线性表中的相应元素对应：先运用for语句将线性表中的所有元素赋值为0，再运用for语句达到随着狐狸进入次数的增加和进入的洞口的改变，改变线性表中相应元素的值的目的（用0标记进入的洞口，用1表示未进入的洞口，并分别赋值给每一个洞口相对应的线性表元素）。利用for语句遍历整个线性表，利用if语句挑选出所需线性表元素，最后再利用printf函数输出结果。算法描述： Status InitList_Sq(SqList &L)/构造一个空的线性表LL.elem = (ElemType *)malloc(LISTSIZE*sizeof(ElemType);if(!L.elem) return(OVERFLOW); /存储分配失败L.length = 0; /空表长度为0L.listsize = LISTSIZE; /初始存储容量return OK;/InitList_SqStatus Where(SqList &L)/构造狐狸逮兔子函数int i,j=1; /i为所找次数，j为所找的洞口号，先初始所找洞口号为1for(j=1;j=LISTSIZE;j+)L.elemj=0; /记未进入的洞为0，进入的洞为1，初始所有洞口为0L.elem1=1; /第一次进入洞口号为1for(i=2;i=1000;i+)j=(j+i)%LISTSIZE; /第i次进入的洞口号L.elemj=1; /标记进入的洞口为1 /第二次隔一个洞找，第三次隔两个洞找，以此类推，经过1000次printf(兔子可能的藏身洞口有：n);for(j=1;j=LISTSIZE;j+)if(*L).elemj=0) printf(第%d号洞n,j); /实现结果的输出return OK;三、源程序及注释：#include#include#define OK 1#define OVERFLOW 0typedef int Status;typedef int ElemType;#define LISTSIZE 10 /线性表存储空间的初始分配量typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储空间（以sizeof(ElemType)为单位）SqList;Status InitList_Sq(SqList *L)/构造一个空的线性表L(*L).elem = (ElemType *)malloc(LISTSIZE*sizeof(ElemType);if(! (*L).elem) return(OVERFLOW); /存储分配失败(*L).length = 0; /空表长度为0(*L).listsize = LISTSIZE; /初始存储容量return OK;/InitList_SqStatus Where(SqList *L)/构造狐狸逮兔子函数int i,j=1; /i为所找次数，j为所找的洞口号，先初始所找洞口号为1for(j=1;j=LISTSIZE;j+)(*L).elemj=0; /记未进入的洞为0，进入的洞为1，初始所有洞口为0(*L).elem1=1; /第一次进入洞口号为1for(i=2;i=1000;i+)j=(j+i)%LISTSIZE; /第i次进入的洞口号(*L).elemj=1; /标记进入的洞口为1 /第二次隔一个洞找，第三次隔两个洞找，以此类推，经过1000次printf(兔子可能的藏身洞口有：n);for(j=1;j=LISTSIZE;j+)if(*L).elemj=0) printf(第%d号洞n,j); /实现结果的输出return OK;void main()SqList L;InitList_Sq(&L);Where(&L);四、运行输出结果：五、调试和运行程序过程中产生的问题及采取的措施：1、产生的问题：将算法直接运用于C程序语言中，导致在调试时没错，运行时出错。 采取的措施：按照C语言的代码规则，将算法中的不符合C语言编程的代码进行修改，如：Status InitList_Sq(SqList &L)修改为Status InitList_Sq(SqList *L)，将L.elem【】修改为(*L).elem【】2、产生的问题：由于未完全掌握C语言，直接带入题目中的代码，导致错误代码的输入： void main() SqList *L; InitList_Sq(L)； Rabbit(L); getch(); 采取的措施：在老师的帮助下将代码修改正确： void main() SqList L; InitList_Sq(&L)； Rabbit(&L); getchar();六、对算法的程序的讨论、分析，改进设想，其它经验教训：1、讨论、分析：此算法运用了线性表顺序存储的存储结构，利用for语句和求余符号实现个线性表的循环遍历，同时，for语句也可用while所代替，例如：for(j=1;j=LISTSIZE;j+) (*L).elemj=0;可替换为：while(j=LISTSIZE) (*L).elemj=0; j+;2、改进设想：减少第一次为所有线性表元素赋值的for循环，将址不是1的元素输出；将 从第二次进入洞口开始循环遍历修改为从第一次进入洞口开始循环遍历，更方便理解。代码如下：Status Where(SqList *L)/构造狐狸逮兔子函数int i,j=0; /i为所找次数，j为所找的洞口号，先初始未开始进入洞口前所找洞口号为0for(i=1;i=1000;i+)j=(j+i)%LISTSIZE; /第i次进入的洞口号(*L).elemj=1; /标记进入的洞口为1 /第二次隔一个洞找，第三次隔两个洞找，以此类推，经过1000次printf(兔子可能的藏身洞口有：n);for(j=1;j=LISTSIZE;j+)if(*L)