顺序表,单链表,栈,队列2011.11.2.doc

实验名称(一):实现顺序表和单链表的基本运算姓名:李秋玉班级:2010计算机一班学号:2010131145一、实验目的:了解顺序表的结构特点及有关概念,掌握顺序表的各种基本操作算法思想及其实现。了解单链表的结构特点及有关概念,掌握单链表的各种基本操作算法思想及其实现。二、实验内容: (1)编写一个程序,实现顺序表的各种基本运算:1、初始化顺序表;2、顺序表的插入;3、顺序表的输出;4、求顺序表的长度5、判断顺序表是否为空;6、输出顺序表的第i位置的个元素;7、在顺序表中查找一个给定元素在表中的位置;8、顺序表的删除;9、释放顺序表(2)编写一个程序,实现单链表的各种基本运算:1、初始化单链表;2、单链表的插入;3、单链表的输出;4、求单链表的长度5、判断单链表是否为空;6、输出单链表的第i位置的元素;7、在单链表中查找一个给定元素在表中的位置;8、单链表的删除;9、释放单链表三、算法思想与算法描述:顺序表:将一个个元素采用尾插入法插入到顺序表中,如ListInsert(L,1,'f');就是将f插入到到单链表的第一个位置,之后按此方法可以插入其他元素。之后完成其他操作,包含了条件语句,循环语句,返回语句等。单链表:由于单链表不像顺序栈那样连续的,而是通过*next来指向结点,首先创立一个空栈来便于插入。来实现之后一系列操作。四、实验步骤与算法实现:(1)顺序表:1、初始化顺序表:构造一个空的线性表,、顺序表的插入:该运算在顺序表L的第i个位置上插入新元素e。如果i值不正确,则显示相应错误信息:否则将顺序表原来第i个元素及以后元素均要向后移一位。3、顺序表的输出;当顺序表不为空的时候,显示L中的元素的值4、求顺序表的长度该运算返回顺序表L的长度,实际只需返回length的值5、判断顺序表是否为空;看元素中的length是否为0,6、输出顺序表的第i位置的个元素;用e返回L中第i个元素的值。7、在顺序表中查找一个给定元素在表中的位置;该运算顺序查找第一个值域与e相等的元素得逻辑顺序。若不存在,则返回08、顺序表的删除;该运算删除顺序表L的第i个元素。如果i值不正确,则显示相应错误信息;否则将线性表第i个元素以后元素均向前移一个位置,移动方向为从左到右。9、释放顺序表:free(L);(2)单链表:1、初始化单链表;建立一个空的单链表,及创建一个头结点2、单链表的插入;先在单链表中找到第i-1个结点*p,若存在这样的结点,将值为e的结点插入*s其后3、单链表的输出;逐一扫描单链表L的每个数据结点,并显示各个结点data的值4、求单链表的长度返回单链表结点的个数5、判断单链表是否为空;若单链表L没有数据结点,则返回真,否返回假6、输出单链表的第i位置的元素;若存在第i个数据结点,则将其data值域赋给变量e7、在单链表中查找一个给定元素在表中的位置;在单链表l中从头开始找一个值域与e相等的结点,若存在这样的结点,则返回位置8、单链表的删除;先在单链表L中找到第i-1个结点*p,若存在这样的结点,且也存在直接后继结点,则删除该直接后继结点9、释放单链表释放单链表L占用的空间,即逐一释放全部结点的空间。五、实验测试及结果:(1)顺序表:#include<>#include<>#include<>#defineMaxSize50typedefcharElemType;typedefstruct{ElemTypeelem[MaxSize];intlength;}SqList;voidInitList(SqList*&L){L=(SqList*)malloc(sizeof(SqList));L->length=0;}voidDestroyList(SqList*L){free(L);}intListEmpty(SqList*L){return(L->length==0);}intListLength(SqList*L){return(L->length);}voidDispList(SqList*L){inti;if(ListEmpty(L))return;for(i=0;i<L->length;i++)printf("%c",L->elem[i]);printf("\n");}intGetElem(SqList*L,inti,ElemType&e){if(i<1||i>L->length)return0;e=L->elem[i-1];return1;}intLocateElem(SqList*L,ElemTypee){inti=0;while(i<L->length&&L->elem[i]!=e)i++;if(i>=L->length)return