实验项目名称：线性表的存储结构
实验目的与要求：
1.基础知识:掌握数据结构中线性表的相关知识;
掌握C或VC+ +语言中程序设计的方法。
2.程序功能:
(1)参考教材相关算法，分别用顺序式和链式两种存储结构实现线性表的操作;
(2)实现已建立线性表中元素的查找、插入和删除。
实验性质:验证性(4学时，其中顺序表2学时，链表2学时)
说明：程序包含的主要函数:主函数、操作界面、
建立空线性表、获取第i个元素的值、在第i个位
置前插入元素e、删除第i个元素且用e返回删除的
元素值。
注意：
(1) 应有相关注释，尤其是每个子函数的功能注释;
(2) 主函数调用子函数的逻辑顺序一主 函数调用建立线性表子函数应在调用其他子函数之前,这须在主函数中进行条件控制。
(3)在选定存储结构后，需要特别关注“表不存在”和“空表”的语句表达方式以及它们的使用时机和方式。
如:顺序表中，表达表不存在的语句是:L.elem=NULL ;
建立空表语句是:调用lnitList Sq (L) ;
在带头结点的链表中，表达表不存在的语句是:L=NULL;
建立空表语句是: L->next=NULL或者调用InitList_ L (L) ;
顺序式线性表
源代码：
#include<stdio.h>
#include<malloc.h>//动态存储分配函数头文件//
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define List_Init_Size 100
#define List_Increment 10
typedef int Status;
typedef int ElemType;
typedef struct
{
ElemType *elem;
int length;
int listsize;
}SqList;
Status InitList_Sq(SqList &L)//构造一个空线性表
{
L.elem = (ElemType*)malloc(List_Init_Size*sizeof(ElemType));
if(!L.elem)
return(ERROR);//存储分配失败
L.length = 0;//空表长度为0
L.listsize = List_Init_Size;//初始存储容量
return OK;
}
Status ListInsert_Sq(SqList &L,int i,ElemType e)//插入一个元素
{
//在顺序线性表L中第i个位置之前插入新的元素e
//i的合法值为1<=i<=ListLength_Sq(L)+1
int *newbase;
int *q ,*p;
if(i<1 || i>L.length+1)
return ERROR;//i值不合法
if(L.length >= L.listsize)
{
//当前空间已满，增加分配
newbase = (ElemType*)realloc(L.elem,
(L.listsize+List_Increment)*sizeof(ElemType));
if(!newbase)
return (ERROR);//存储分配失败
L.elem = newbase;//新基址
L.listsize = L.listsize + List_Increment;//增加存储容量
}
q = &(L.elem[i-1]);//q为插入位置
for(p = &(L.elem[L.length-1]);p>=q;p--)*(p+1)=*p;//插入位置及之后的元素后移
*q = e;//插入e
++L.length;//表长增1
return OK;
}//插入操作
Status ListDetetle_Sq(SqList &L,int i,ElemType &e)//删除一个元素
{
//在顺序线性表L中删除第i个元素，
//i的合法值为1<=i<=ListLength_Sq(L)
int *p;
int *q;
if(i<1 || i>L.length+1)
return ERROR;//i值不合法
p = &(L.elem[i-1]);//p为被删除元素的位置
e = *p;//被删除的元素的值赋给e
q = L.elem + L.length-1;//表尾元素的位置
for(++p;p<=q;p++) *(p-1)= *p;//被删除元素之后的元素左移
--L.length;//表长减1
return OK;
}
Status GetElem_Sq(SqList &L,int i,ElemType &e)//查找一个元素
{
if(i<1 || i>L.length)
return ERROR;
e = L.elem[i-1];
return e;
}
Status ListLength_Sq(SqList L)//求线性表表长
{
if(L.length==0)
{
return 0;
}
return L.length;
}
Status ClearList_Sq(SqList &L)//将线性表重置为空表
{
L.length=0;
return OK;
}
Status PrintList_Sq(SqList &L)
{
int i;
if(L.length==0)
printf("线性表为空");
else
{
printf("线性表为： ");
for( i=0; i<L.length; i++) printf("%d ",L.elem[i]);
}
printf("\n");
return OK;
}
Status Operatemenu(SqList L) //操作菜单
{
printf("------****操作菜单****------\n\n");
printf("------ 0 退出系统\n");
printf("------ 1 插入一个元素\n");
printf("------ 2 查找一个元素\n");
printf("------ 3 删除一个元素\n");
printf("------ 4 输出线性表表长\n");
printf("------ 5 将线性表重置为空表\n");
printf("------ 6 输出线性表\n");
printf("------ 请选择你所需要的操作\n");
return 0;
}
int main()//主函数
{
SqList L;
int num=-1, i;
ElemType e;
if(InitList_Sq(L))
{printf("------ 线性表创建成功\n");}
while(num!=0)
{
Operatemenu(L);
scanf("%d",&num);
switch(num)
{
case 1:
printf("分别输入储存地址i和储存元素e:\n");
scanf("%d%d",&i,&e);
if(!ListInsert_Sq(L,i,e)) // 判断i值是否合法
printf("i值不合法\n");
else
{ printf("已经将%d存入顺序表\n", e);
PrintList_Sq(L);}
break;
case 2:
printf("请输入查找的位置i:");
scanf("%d",&i);
if(!GetElem_Sq(L,i,e))// 判断i值是否合法
printf("i值不合法\n");
else
{ printf("%d位置的元素为:", i);
printf("%d\n",e);}
break;
case 3:
printf("请输入删除的位置i:");
scanf("%d",&i);
if(!ListDetetle_Sq(L,i,e)) // 判断i值是否合法
printf("i值不合法\n");
else
{ printf("已经将%d位置的元素删除\n", i);
PrintList_Sq(L);}
break;
case 4:ListLength_Sq(L);
printf("线性表表长为");
printf("%d\n",L.length);
break;
case 5:ClearList_Sq(L);
printf("线性表已重置为空表\n");
PrintList_Sq(L);
break;
case 6:PrintList_Sq(L);break;
}
}
}