实验名称（一）：实现顺序表和单链表的基本运算
姓名：李秋玉 班级：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、初始化顺序表：构造一个空的线性表，实际只需分配线性表的存储空间并length为0. 2、顺序表的插入：该运算在顺序表L的第i个位置上插入新元素e。如果i值不正确，则显示相应错误信息：否则将顺序表原来第i个元素及以后元素均要向后移一位。3、顺序表的输出；当顺序表不为空的时候，显示L中的元素的
值 4、求顺序表的长度该运算返回顺序表L的长度，实际只需返回length的值5、判断顺序表是否为空；看元素中的length是否为0, 6、输出顺序表的第i位置的个元素 ；用e返回L中第i个元素的值。 7、在顺序表中查找一个给定元素在表中的位置；该运算顺序查找第一个值域与e相等的元素得逻辑顺序。若不存在，则返回0 8、顺序表的删除；该运算删除顺序表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值域赋给变量e 7、在单链表中查找一个给定元素在表中的位置；在单链表l中从头开始找一个值域与e相等的结点，若存在这样的结点，则返回位置8、单链表的删除； 先在单链表L中找到第i-1个结点*p，若存在这样的结点，且也存在直接后继结点，则删除该直接后继结点9、释放单链表释放单链表L占用的空间，即逐一释放全部结点的空间。
五、实验测试及结果：
（1）顺序表：
#include
#define MaxSize 50
typedef char ElemType; typedef struct {
ElemType elem[MaxSize]; int length; } SqList;
void InitList(SqList *&L) {
L=(SqList *)malloc(sizeof(SqList)); L->length=0; }
void DestroyList(SqList *L) {
free(L); }
int ListEmpty(SqList *L) {
return(L->length==0); }
int ListLength(SqList *L) {
return(L->length); }
void DispList(SqList *L) {
int i;
if (ListEmpty(L)) return; for (i=0;i
int GetElem(SqList *L,int i,ElemType &e) {
if (i<1 || i>L->length) return 0; e=L->elem[i-1]; return 1;
}
int LocateElem(SqList *L, ElemType e) {
int i=0;
while (i
return i+1; }
int ListInsert(SqList *&L,int i,ElemType e) {
int j;
if (i<1 || i>L->length+1) return 0; i--;
for (j=L->length;j>i;j--) L->elem[j]=L->elem[j-1]; L->elem[i]=e; L->length++; return 1; }
int ListDelete(SqList *&L,int i,ElemType &e) {
int j;
if (i<1 || i>L->length) return 0; i--;
e=L->elem[i];
for (j=i;j
void main() {
SqList *L; ElemType e;
printf(\初始化顺序表L\\n\); InitList(L);
printf(\依次采用尾插法插入f,b,f,m,o元素\\n\); ListInsert(L,1,'f'); ListInsert(L,2,'b');
ListInsert(L,3,'f'); ListInsert(L,4,'m'); ListInsert(L,5,'o');
printf(\输出顺序表L:\); DispList(L);
printf(\顺序表L长度=%d\\n\,ListLength(L)); if(ListEmpty(L))
printf(\顺序表L为空\\n\); else
printf(\顺序表L不为空\\n\); GetElem(L,3,e);
printf(\顺序表L的第个元素=%c\\n\,e);
printf(\元素a的位置=%d\\n\,LocateElem(L,'a')); printf(\在第个元素位置上插入f元素\\n\); ListInsert(L,4,'f');
printf(\输出顺序表L:\); DispList(L);
printf(\删除L的第个元素\\n\); ListDelete(L,3,e);
printf(\输出顺序表L:\); DispList(L);
printf(\释放顺序表L\\n\); DestroyList(L); }
调试结果：
(1)初始化顺序表L
(2)依次采用尾插法插入f,b,f,m,o元素 (3)输出顺序表L:fbfmo (4)顺序表L长度=5 顺序表L不为空
(6)顺序表L的第3个元素=f (7)元素a的位置=0
(8)在第4个元素位置上插入f元素 (9)输出顺序表L:fbffmo (10)删除L的第3个元素 (11)输出顺序表L:fbfmo (12)释放顺序表L
请按任意键继续. . . （2）单链表： #include
typedef char ElemType; typedef struct LNode