数据结构实验报告二.doc

数据结构实验报告一、实验名称实验二：线性表二、实验目的通过本实验，掌握线性表的顺序存储和链接存储的表示方法，并能在线性结构的基本操作的基础上，设计合适的算法解决实际问题。三、实验要求（1）学生提前准备好实验报告，预习并熟悉实验步骤；（2）遵守实验室纪律，在规定的时间内完成要求的内容；（3）12人为1小组，实验过程中独立操作、相互学习；四、实验内容及步骤（一）利用线性表的“顺序存储结构”解决两个英文单词比大小问题1、正确设计程序，并编译、链接成可执行文件（1）首先正确写出顺序表初始化操作的子程序InitList_Sq（2）正确写出进行单词大小比较的函数compare（3）写出主程序 main ，提供输入与输出操作本程序的特点是允许用户任意输入两个单词，以 A 和 B 代表，然后利用顺序表进行大小的比较，并输出比较结果。整个算法充分利用了顺序表的基本操作。详见附1。2、进行程序测试（1）输入两个相同的单词（2）输入的第一个单词是第二个单词的前缀（3）输入的两个单词的前几个字母相同图1图 2图 3（二）利用线性表的“链接存储结构”实现逆序创建链表1、正确设计程序，并编译、链接成可执行文件（1）首先正确写出创建逆序链表子程序InitList_Sq（2）写出主程序 main ，提供输入与输出操作本程序的特点是将5个字母 a，b，c，d，e 存储于一个数组中，然后以逆序，即从后往前 e，d，c，b，a 的顺序创建链表，然后从链表的第一个结点开始依次输出创建的链表的数据（data）。整个算法充分利用了单链表的基本操作。详见附2。2、进行程序测试直接运行程序，输入结果如图 4 所示，结果正确。图 4五、实验小结实验进行较为顺利，既了解了顺序表和单链表的基本操作，又进行了二者特点的比较。实验过程中存在以下几个问题：（1）对 C 语言的内存分配操作不熟悉。（2）对“结构体”的操作不是很适应，与一般变量相差较大。经过指导教师的帮助与仔细查阅资料，问题基本得以解决，实验后还需对上面的问题进行深入学习。附1：源程序#include #define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef char ElemType;typedef struct ElemType *elem; int length; int listsize; int incrementsize;SqList;void InitList_Sq(SqList L) L.elem=(ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE); L.length=0; L.listsize=LIST_INIT_SIZE; L.incrementsize=LISTINCREMENT;int compare(SqList A,SqList B) /* if AB return 1 */ int j; j=0; while(jA.length & jB.length)if(A.elemjB.elemj) return(1);else j+; if (A.length=B.length) return(0); else if(A.lengthB); else if(result=-1)printf(the result is:(A=0;i-)LNode s=(LNode)malloc(sizeof(struct Node);s-data=Ai;s-next=L;L=s; return L;main() ElemType A5=a,b,c,d,e; int n; LinkList L; LNode p; n=