实验二、线性表操作
一、实验目的
1．掌握用 C语言调试程序的基本方法。
2．掌握线性表的基本运算，如插入、删除等。
二、实验内容
1．线性表在顺序存储结构上的插入元素，删除元素运算
2．线性表在链式存储结构上的建链表，插入结点，删除结点运算
三、实验要求
1．C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．分析算法，要求给出具体的算法分析结果，包括时间复杂度和空间复杂度，并简要给出算法设计小结和心得。
四、程序实现
写出每个操作的算法（操作过程）
五、程序运行情况
写出输入数据及运行结果
参考:
1. 线性表的顺序存储表示（结构）及实现。
阅读下列程序请注意几个问题：
（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素a i-1, a i，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含‘动态分配’一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。我们采用的是含‘静态’一维数组和线性表长的结构体：
typedef struct
{ ElemType a[MAXSIZE]; /* 一维数组子域 */
int length; /* 表长度子域 */
}SqList; /* 顺序存储的结构体类型 */ （2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料，供学生参考。比如，主函数中简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术。在学习数据结构的初级阶段，并不强要求学生一定使用“菜单设计”技术，同学们可以在main()函数中直接写几个简单的调用语句，就象前面的复数处理程序中的main()一样。但是随着学习的深入，尽早学会使用“菜单设计”技术，会明显提高编程和运行效率。
[源程序]
#include
#include
#define MAXSIZE 20 /* 数组最大界限 */
typedef int ElemType; /* 数据元素类型 */
typedef struct
{ ElemType a[MAXSIZE]; /* 一维数组子域 */
int length; /* 表长度子域 */
}SqList; /* 顺序存储的结构体类型 */ SqList a,b,c;
/* 函数声明 */
void creat_list(SqList *L);
void out_list(SqList L);
void insert_sq(SqList *L,int i,ElemType e);
ElemType delete_sq(SqList *L,int i);
int locat_sq(SqList L,ElemType e);
/* 主函数 */
main()
{ int i,k,loc; ElemType e,x; char ch;
do { printf("\n\n\n");
printf("\n 1. 建立线性表 " );
printf("\n 2. 在i位置插入元素e");
printf("\n 3. 删除第i个元素，返回其值");
printf("\n 4. 查找值为 e 的元素");
printf("\n 6. 结束程序运行");
printf("\n======================================");
printf("\n 请输入您的选择（1，2，3，4，6）");
scanf("%d",&k);
switch(k)
{ case 1:{ creat_list(&a); out_list(a);
} break;
case 2:{ printf("\n i,e=?"); scanf("%d,%d",&i,&e);
insert_sq(&a,i,e); out_list(a);
} break;
case 3:{ printf("\n i=?"); scanf("%d",&i);
x=delete_sq(&a,i); out_list(a);
printf("\n x=%d",x);
} break;
case 4:{ printf("\n e=?"); scanf("%d",&e);
loc=locat_sq(a,e);
if (loc==-1) printf("\n 未找到 %d",loc);
else printf("\n 已找到，元素位置是 %d",loc);
} break;
} /* switch */
}while(k!=6);
printf("\n 再见！");
printf(“\n 打回车键，返回。“); ch=getch();
} /* main */
/* 建立线性表 */
void creat_list(SqList *L)
{ int i;
printf("\n n=?"); scanf("%d",&L->length);
for(i=0;ilength;i++){ printf("\n data %d=?",i);
scanf("%d",&(L->a[i]));
}
} /* creat_list */
/* 输出线性表 */
void out_list(SqList L)
{ int i; char ch;
printf("\n");
for(i=0;i<=L.length-1;i++) printf("%10d",L.a[i]);
printf("\n\n 打回车键，继续。“); ch=getch();
} /* out_list */
/* 在线性表的第i个位置插入元素e */
void insert_sq(SqList *L,int i,ElemType e)
{ int j;
if (L->length==MAXSIZE) printf("\n overflow !");
else if(i<1||i>L->length+1) printf("\n erroe i !");
else { for(j=L->length-1; j>=i-1; j--) L->a[j+1]=L->a[j];
/* 向后移动数据元素 */
L->a[i-1]=e; /* 插入元素 */
L->length++; /* 线性表长加1 */
}
} /* insert_sq */
/* 删除第i个元素，返回其值 */
ElemType delete_sq(SqList *L, int i)
{ ElemType x; int j;
if( L->length==0) printf("\n 是空表。underflow !");
else if(i<1||i> L->length){ printf("\n error i !");
x=-1;}
else { x=L->a[i-1];
for(j=i; j<=L->length-1; j++) L->a[j-1]=L->a[j];
L->length--;
}
return(x);
} /* delete_sq */
/* 查找值为 e 的元素，返回它的位置 */
int locat_sq(SqList L, ElemType e)
{ int i=0;
while(i<=L.length-1 && L.a[i]!=e) i++;
if(i<=L.length-1) return(i+1);
else return(-1);
}/* locat_sq */
2. 线性表的链表存储表示（结构）及实现。
阅读下列程序请注意几个问题：
（1）关于线性表的链表存储结构的本质是：在逻辑上相邻的两个数据元素a i-1, a i，在
