数据结构实验一线性表及其应用.pdf

该【数据结构实验一线性表及其应用 】是由【lajie】上传分享，文档一共【10】页，该文档可以免费在线阅读，需要了解更多关于【数据结构实验一线性表及其应用 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。-
实验一线性表及其应用
一、实验目的
,进一步掌握C语言的构造特点。
。
——单链表的定义及C语言实现。
。
——单链表中的各种根本操作。
二、实验容
、插入及删除。
、插入及删除。
三、实验步骤
。
={21,23,14,5,56,17,31},然
后在第i个位置插入元素68。
,结点的值域为整型数据。要求将用户输入的
数据按尾插入法来建立相应单链表。
四、实现提示
,一维数组的机表示就是顺序
构造。因此,可用C语言的一维数组实现线性表的顺序存储。
在此,我们利用C语言的构造体类型定义顺序表:
#defineMA*SIZE1024
typedefintelemtype;/*线性表中存放整型元素*/
typedefstruct
{elemtypevec[MA*SIZE];
intlen;/*顺序表的长度*/
}sequenlist;
,可防止在后面的参考程序中代
码重复书写,另外在该头文件里给出顺序表的建立及常量的定义。
,在插入过程中注意溢出情况以及数组的下标
与位序〔顺序表中元素的次序〕的区别。
,还含有一个指针域。用C语言描述结点构
造如下:
typedefintelemtype;
typedefstructnode
-
{elemtypedata;//数据域
structnode*ne*t;//指针域
}linklist;
注意结点的建立方法及构造新结点时指针的变化。构造一个结点需用到C语言的
标准函数malloc(),如给指针变量p分配一个结点的地址:
p=(linklist*)malloc(sizeof(linklist));该语句的功能是申请分配一个
类型为linklist的结点的地址空间,并将首地址存入指针变量p中。当结点不
需要时可以用标准函数free(p)释放结点存储空间,这时p为空值〔NULL〕。
五、思考与提高
,应如何建立顺序表。
=&a语句,会出现什么结果?
六、完整参考程序
、插入及删除。
#include<>
#include<>
#defineMA*30//定义线性表的最大长度
enumBOOL{False,True};//定义BOOL型
typedefstruct{
charelem[MA*];//线性表
intlast;//last指示当前线性表的长度
}sqlist;
voidinitial(sqlist&);//初始化线性表
BOOLinsert(sqlist&,int,char);//在线性表中插入元素
BOOLdel(sqlist&,int,char&);//在线性表中删除元素
intlocate(sqlist,char);//在线性表中定位元素
voidprint(sqlist);//显示线性表中所有元素
voidmain()
{sqlistS;//S为一线性表
intloc,flag=1;
charj,ch;
BOOLtemp;
printf("本程序用来实现顺序构造的线性表。\n");
printf("可以实现查找、插入、删除等操作。\n");
initial(S);//初始化线性表
-
while(flag)
{printf("请选择:\n");
printf("\n");
printf("\n");
printf("\n");
printf("\n");
printf("\n");
scanf("%c",&j);
switch(j)
{case'1':print(S);break;//显示所有元素
case'2':{printf("请输入要插入的元素(一个字符)和插入位置:\n");
printf("格式:字符,位置;例如:a,2\n");
scanf("%c,%d",&ch,&loc);//输入要插入的元素和插入的位置
temp=insert(S,loc,ch);//插入
if(temp==False)printf("插入失败!\n");//插入失败
else{printf("插入成功!\n");print(S);}//插入成功
break;
}
case'3':{printf("请输入要删除元素的位置:");
scanf("%d",&loc);//输入要删除的元素的位置
temp=del(S,loc,ch);//删除
if(temp==True)printf("删除了一个元素:%c\n",ch);//删除成功
elseprintf("该元素不存在!\n");//删除失败
print(S);
break;
}
case'4':{printf("请输入要查找的元素:");
scanf("%c",&ch);//输入要查找的元素
loc=locate(S,ch);//定位
if(loc!=-1)printf("该元素所在位置:%d\n",loc+1);//显示该元素位置
elseprintf("%c不存在!\n",ch);//当前元素不存在
break;
}
default:flag=0;printf("程序完毕,按任意键退出!\n");
-
}
}
getch();
}
voidinitial(sqlist&v)
{//初始化线性表
inti;
printf("请输入初始线性表长度:n=");//输入线性表初始化时的长度
scanf("%d",&);
printf("请输入从1到%d的各元素(字符),例如:abcdefg\n",);
getchar();
for(i=0;i<;i++)scanf("%c",&[i]);//输入线性表的各元素
}
BOOLinsert(sqlist&v,intloc,charch)
{//插入一个元素,成功返回True,失败返回False
inti;
if((loc<1)||(loc>+1))
{printf("插入位置不合理!\n");//位置不合理
returnFalse;
}
elseif(>=MA*)//线性表已满
{printf("线性表已满!\n");
returnFalse;
}
else{for(i=-1;i>=loc-1;i--)[i+1]=[i];//其后元素依次后移
[loc-1]=ch;//插入元素
++;//线性表长度加一
returnTrue;
}
}
BOOLdel(sqlist&v,intloc,char&ch)
{//删除一个元素,成功返回True,并用ch返回该元素值,失败返回False
intj;
if(loc<1||loc>)//删除位置不合理
-
returnFalse;
else{ch=[loc-1];//ch取得该元素值
for(j=loc-1;j<-1;j++)[j]=[j+1];//其后元素依次前移
--;//线性表长度减一
returnTrue;
}
}
intlocate(sqlistv,charch)
{//在线性表中查找ch的位置,成功返回其位置,失败返回-1
inti=0;
while(i<&&[i]!=ch)i++;//当前位置后移,直到找到为止
if([i]==ch)//找到当前元素
returni;
elsereturn(-1);
}
voidprint(sqlistv)//显示当前线性表所有元素
{inti;
for(i=0;i<;i++)printf("%c",[i]);
printf("\n");
}
、插入及删除。
#include<>
#include<>
#include<>
#defineLENsizeof(LNode)//定义LEN为一个节点的长度
enumBOOL{False,True};//定义BOOL型
typedefstructnode
{chardata;//数据域
structnode*ne*t;//指向下一个节点的指针
}LNode,*LinkList;
voidCreatList(LinkList&,int);//生成一个单链表
BOOLListInsert(LinkList&,int,char);//在单链表中插入一个元素
BOOLListDelete(LinkList&,int,char&);//在单链表中删除一个元素
BOOLListFind_keyword(LinkList,char,int&);//按关键字查找一个元素
-
BOOLListFind_order(LinkList,char&,int);//按序号查找一个元素
voidListPrint(LinkList);//显示单链表所有元素
voidmain()
{LinkListL;
BOOLtemp;
intnum,loc,flag=1;
charj,ch;
printf("本程序实现链式构造的线性表的操作。\n");
printf("可以进展插入,删除,定位,查找等操作。\n");
printf("请输入初始时链表长度:");//输入生成单链表时的元素个数
scanf("%d",&num);
CreatList(L,num);//生成单链表
ListPrint(L);
while(flag)
{printf("请选择:\n");
printf("\n");//显示链表元素
printf("\n");//插入链表元素
printf("\n");//删除链表元素
printf("\n");//按关键字查找
printf("\n");//按序号查找
printf("\n");//退出
scanf("%c",&j);
switch(j)
{case'1':ListPrint(L);break;
case'2':{printf("请输入元素(一个字符)和要插入的位置:\n");
printf("格式:字符,位置;例如:a,3\n");
scanf("%c,%d",&ch,&loc);//输入要插入的元素和要插入的位置
temp=ListInsert(L,loc,ch);//插入
if(temp==False)printf("插入失败!\n");//插入失败
elseprintf("插入成功!\n");//成功插入
ListPrint(L);
break;
}
case'3':printf("请输入要删除的元素所在位置:");
-
scanf("%d",&loc);//输入要删除的节点的位置
temp=ListDelete(L,loc,ch);//删除
if(temp==False)printf("删除失败!\n");//删除失败
elseprintf("成功删除了一个元素:%c\n",ch);//删除成功,显示该元素
ListPrint(L);
break;
case'4':if(L->ne*t==NULL)//链表为空
printf("链表为空!\n");
else{printf("请输入要查找的元素(一个字符):");
scanf("%c",&ch);//输入要查找的元素
temp=ListFind_keyword(L,ch,loc);//按关键字查找
if(temp==False)printf("没有找到该元素!\n");//查找失败
elseprintf("该元素在链表的第%d个位置。\n",loc);
//成功查找,显示该元素位置
}
break;
case'5':if(L->ne*t==NULL)//链表为空
printf("链表为空!\n");
else{printf("请输入要查找的位置:");
scanf("%d",&loc);//输入要查找的元素的位置
temp=ListFind_order(L,ch,loc);//按序号查找
if(temp==False)printf("该位置不存在!\n");//查找失败
elseprintf("第%d个元素是:%c\n",loc,ch);
//成功查找,显示该元素
}
break;
default:flag=0;printf("程序完毕,按任意键退出!\n");
}
}
getch();
}
voidCreatList(LinkList&v,intn)
{//生成一个带头结点的有n个元素的单链表
inti;
-
LinkListp;
v=(LinkList)malloc(LEN);//生成头结点
v->ne*t=NULL;
printf("请输入%d个字符:例如:abcdefg\n",n);
getchar();
for(i=n;i>0;--i)
{p=(LinkList)malloc(LEN);//生成新结点
scanf("%c",&p->data);
p->ne*t=v->ne*t;
v->ne*t=p;
}
}
BOOLListInsert(LinkList&v,inti,chare)
{//在单链表的第i各位置插入元素e,成功返回True,失败返回False
LinkListp,s;
intj=0;
p=v;
while(p&&j<i-1){p=p->ne*t;++j;}//查找第i-1个元素的位置
if(!p||j>i-1)returnFalse;//没有找到
s=(LinkList)malloc(LEN);//生成一个新结点
s->data=e;
s->ne*t=p->ne*t;//将新结点插入到单链表中
p->ne*t=s;
returnTrue;
}
BOOLListDelete(LinkList&v,inti,char&e)
{//在单链表中删除第i个元素,成功删除返回True,并用e返回该元素值,失败返回False
LinkListp,q;
intj=0;
p=v;
while(p->ne*t&&j<i-1)//查找第i-1个元素位置
{p=p->ne*t;++j;}
if(!(p->ne*t)||j>i-1)returnFalse;//查找失败
q=p->ne*t;p->ne*t=q->ne*t;//删除该元素
-
e=q->data;//e取得该元素值
free(q);//释放该元素空间
returnTrue;
}
BOOLListFind_keyword(LinkListv,chare,int&i)
{//在单链表中查找关键字为e的元素,成功返回True,并用i返回该元素位置,
//失败返回False
i=1;
LinkListp;
p=v->ne*t;
while((p->data!=e)&&(p->ne*t!=NULL))//p指针指向下一个,直到
{p=p->ne*t;i++;}//找到或到链表尾为止
if(p->data!=e)//该元素在链表中不存在
returnFalse;
elsereturnTrue;
}
BOOLListFind_order(LinkListv,char&e,inti)
{//在单链表中查找第i个元素,成功返回True,并用e返回该元素值,
//失败返回False
LinkListp;
intj=0;
p=v;
while(p->ne*t&&j<i)//移动指针,直到找到第i个元素
{p=p->ne*t;++j;}
if(j!=i)returnFalse;//查找失败
else{e=p->data;//查找成功,用e取得该元素值
returnTrue;
}
}
voidListPrint(LinkListv)
{//显示链表所有元素
LinkListq;
q=v->ne*t;
printf("链表所有元素:");
-
while(q!=NULL)
{printf("%c",q->data);q=q->ne*t;}
printf("\n");
}