实验项目名称：线性表的存储结构
实验目的与要求：
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 ERROR 0
#define OK 1
typedef int Status;
typedef int ElemType;
typedef struct Lnode //结点类型
{ ElemType data;
struct Lnode *next;
}Lnode,*LinkList;
Status InitList_L(LinkList &L)//构建一个空链表
{
L=(LinkList)malloc(sizeof(Lnode));
L->next = NULL;
return OK;
}
Status ListLnsert_L(LinkList &L,int i,ElemType e)//插入操作
{
LinkList p,s;
p = L;
int j=0;
while(p&&j<i-1)
{
p=p->next;
++j;
}
if(!p||j>i-1)
return ERROR;
s = (LinkList)malloc(sizeof(Lnode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete_L(LinkList &L,int i,ElemType &e)//删除操作
{
LinkList p,q;
p = L;
int j=0;
while(p->next && j<i-1)
{
p=p->next;
j++;
}
if(!(p->next) || j>i-1)
return ERROR;
q=p->next;
p->next=q->next;
e = p->data;
free(q);
return OK;
}
Status GetElem_L(LinkList &L,int i,ElemType &e)//查找操作
{
LinkList p;
int j=1;
p=L->next;
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
return ERROR;
e=p->data;
return e;
}
Status ClearList_L(LinkList &L)//清空
{
LinkList p = L;
while(p->next)
{
LinkList m = p->next;
free(p);
p=m;
}
L->next = NULL;
return OK;
}
Status PrintList_L(LinkList &L,int len)//输出
{
if (L->next!=NULL)
{
LinkList p = L->next;
printf("单链表为：\n");
for(int i=0;i<len;i++)
{
printf("%d\n",p->data);
p = p->next;
}
}
else
printf("该链表为空表\n");
return 0;
}
Status Operatemenu(LinkList L) //操作菜单
{
printf("------****操作菜单****------\n\n");
printf("------ 0 退出系统\n");
printf("------ 1 插入一个元素\n");
printf("------ 2 查找一个元素\n");
printf("------ 3 删除一个元素\n");
printf("------ 4 输出链表\n");
printf("------ 5 将链表重置为空表\n");
printf("------ 请选择你所需要的操作\n");
return 0;
}
int main()//主函数
{
LinkList L;
ElemType e;
int len=0;
int num=-1, i;
if(InitList_L(L))
{printf("------ 链表创建成功\n");}
while(num!=0)
{
Operatemenu(L);
scanf("%d",&num);
switch(num)
{
case 1:
len++;
printf("分别输入储存地址i和储存元素e:\n");
scanf("%d %d",&i,&e);
if(!ListLnsert_L(L,i,e)) // 判断i值是否合法
{printf("i值不合法\n");break;}
else
printf("已经将%d存入链表\n", e);
PrintList_L(L,len);
printf("\n");
break;
case 2:
printf("请输入查找的位置i:");
scanf("%d",&i);
if(!GetElem_L(L,i,e))// 判断i值是否合法
{printf("i值不合法\n");break;}
else
printf("%d位置的元素为:", i);
printf("%d\n",e);
break;
case 3:
printf("请输入删除的位置i:");
scanf("%d",&i);
if(!ListDelete_L(L,i,e)) // 判断i值是否合法
{printf("i值不合法\n");break;}
else
{printf("已经将%d位置的元素删除\n", i);
len--;
PrintList_L(L,len);}
break;
case 4:
PrintList_L(L,len);break;
case 5:ClearList_L(L);
printf("已重置为空表\n");break;
}
}
}