学《数据结构》课程实验报告实验名称:线性表基本操作的实现实验室(中心):学生信息:专业班级:指导教师:实验完成时间:2016教师评阅意见:签名:年月日实验成绩:章:线性表提升实验2实验一线性表基本操作的实现一、实验目的1.熟悉C语言的上机环境,进一步掌握C语言的结构特点。2.掌握线性表的顺序存储结构的定义及C语言实现。3.掌握线性表的链式存储结构——单链表的定义及C语言实现。4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。5.掌握线性表在链式存储结构——单链表中的各种基本操作。二、实验内容及要求1.顺序线性表的建立、插入、删除及合并。2.链式线性表的建立、插入、删除及连接。三、实验设备及软件计算机、MicrosoftVisualC++6.0软件四、设计方案(算法设计)㈠采用的数据结构本程序顺序表的数据逻辑结构为线性结构,存储结构为顺序存储;链表的数据逻辑结构依然为线性结构,存储结构为链式结构。㈡设计的主要思路1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度,顺序表的长度和元素由用户输入;2.利用前面建立的顺序表,对顺序表进行插入、删除及合并操作;3.建立一个带头结点的单链表,结点的值域为整型数据,链表的元素由用户输入;章:线性表提升实验34.对前面建立的链表进行插入、删除及连个链表的连接操作;㈢算法描述1、顺序表voidInit(sqlist&);//初始化顺序表BOOLInse(sqlist&,int,char);//在线性表中插入元素BOOLdel(sqlist&,int,char&);//在线性表中删除元素intLoc(sqlist,char);//在线性表中定位元素voidprint(sqlist);//输出顺序表voidcombine(sqlist&,sqlist&,sqlist&);//两个线性表的合并2、链表voidCreaL(LinkList&,int);//生成一个单链表BOOLLInsert(LinkList&,int,char);//在单链表中插入一个元素BOOLLDele(LinkList&,int,char&);//在单链表中删除一个元素BOOLLFind_key(LinkList,char,int&);//按关键字查找一个元素BOOLLFind_order(LinkList,char&,int);//按序号查找一个元素voidLPrint(LinkList);//显示单链表所有元素voidLUnion(LinkList&,LinkList&,LinkList&,int);//两个链表的连接五、程序代码1、顺序表#includestdio.h#includeconio.h章:线性表提升实验4#defineMax116enumBOOL{False,True};typedefstruct{charelem[Max];//线性表intlast;//last指示当前线性表的长度}sqlist;voidInit(sqlist&);BOOLInse(sqlist&,int,char);//在线性表中插入元素BOOLdel(sqlist&,int,char&);//在线性表中删除元素intLoc(sqlist,char);//在线性表中定位元素voidprint(sqlist);voidcombine(sqlist&,sqlist&,sqlist&);voidmain(){sqlistL1;sqlistL2;sqlistL3;intloc,S=1;charj,ch;BOOLtemp;printf(本程序用来实现顺序结构的线性表。\n);printf(可以实现查找、插入、删除、两个线性表的合并等操作。\n);Init(L1);while(S)章:线性表提升实验5{printf(\n请选择:\n);printf(1.显示所有元素\n);printf(2.插入一个元素\n);printf(3.删除一个元素\n);printf(4.查找一个元素\n);printf(5.线性表的合并\n);printf(6.退出程序\n\n);scanf(%c,&j);switch(j){case'1':print(L1);break;case'2':{printf(请输入要插入的元素(一个字符)和插入位置:\n);printf(格式:字符,位置;例如:a,2\n);scanf(%c,%d,&ch,&loc);temp=Inse(L1,loc,ch);if(temp==False)printf(插入失败!\n);else{printf(插入成功!\n);print(L1);}break;}case'3':{printf(请输入要删除元素的位置:);scanf(%d,&loc);temp=del(L1,loc,ch);if(temp==True)printf(删除了一个元素:%c\n,ch);elseprintf(该元素不存在!\n);章:线性表提升实验6printf(删除该元素后的线性表为:);print(L1);break;}case'4':{printf(请输入要查找的元素:);scanf(%c,&ch);loc=Loc(L1,ch);if(loc!=-1)printf(该元素所在位置:%d\n,loc+1);elseprintf(%c不存在!\n,ch);break;}case'5':{printf(请输入要进行合并的第二个线性表:);Init(L2);combine(L1,L2,L3);printf(合并前的两个线性表如下:\n);print(L1);print(L2);printf(输出合并后的线性表如下:\n);print(L3);break;}default:S=0;printf(程序结束,按任意键退出!\n);}}getch();}章:线性表提升实验7voidInit(sqlist&v)//初始化线性表{inti;printf(请输入初始线性表长度:n=);scanf(%d,&v.last);printf(请输入从1到%d的各元素(字符),例如:abcdefg\n,v.last);getchar();for(i=0;iv.last;i++)scanf(%c,&v.elem[i]);}BOOLInse(sqlist&v,intloc,charch)//插入一个元素,成功返回True,失败返回False{inti;if((loc1)||(locv.last+1)){printf(插入位置不合理!\n);returnFalse;}elseif(v.last=Max){printf(线性表已满!\n);returnFalse;}else{for(i=v.last-1;i=loc-1;i--)v.elem[i+1]=v.elem[i];章:线性表提升实验8v.elem[loc-1]=ch;v.last++;returnTrue;}}BOOLdel(sqlist&v,intloc,char&ch)//删除一个元素,成功返回True,并用ch返回该元素值,失败返回False{intj;if(loc1||locv.last)returnFalse;else{ch=v.elem[loc-1];for(j=loc-1;jv.last-1;j++)v.elem[j]=v.elem[j+1];v.last--;returnTrue;}}intLoc(sqlistv,charch)//在线性表中查找ch的位置,成功返回其位置,失败返回-1{inti=0;while(iv.last&&v.elem[i]!=ch)i++;if(v.elem[i]==ch)章:线性表提升实验9returni;elsereturn(-1);}voidprint(sqlistv)//显示当前线性表所有元素{inti;for(i=0;iv.last;i++)printf(%c,v.elem[i]);printf(\n);}voidcombine(sqlist&s1,sqlist&s2,sqlist&s3)//顺序表的连接{inti=0;intj=0;intk=0;while(is1.last&&js2.last){if(s1.elem[i]=s2.elem[j]){s3.elem[k]=s1.elem[i];i++;}else{章:线性表提升实验10s3.elem[k]=s2.elem[j];j++;}k++;}if(i==s1.last){while(js2.last){s3.elem[k]=s2.elem[j];k++;j++;}}if(j==s2.last){while(is1.last){s3.elem[k]=s1.elem[i];k++;}}s3.last=k;}章:线性表提升实验112、链表的操作#includeconio.h#includestdio.h#includestdlib.h#defineLENsizeof(LNode)enumBOOL{False,True};typedefstructnode{chardata;structnode*next;}LNode,*LinkList;voidCreaL(LinkList&,int);//生成一个单链表BOOLLInsert(LinkList&,int,char);//在单链表中插入一个元素BOOLLDele(LinkList&,int,char&);//在单链表中删除一个元素BOOLLFind_key(LinkList,char,int&);//按关键字查找一个元素BOOLLFind_order(LinkList,char&,int);//按序号查找一个元素voidLPrint(LinkList);//显示单链表所有元素voidLUnion(LinkList&,LinkList&,LinkList&,int);//两个链表的连接voidmain(){LinkListL;LinkListT;LinkListH;章:线性表提升实验12BOOLtemp;intnum,num1,loc,flag=1;charj,ch;printf(本程序实现链式结构的线性表的操作。\n);printf(可以进行插入,删除,定位,查找等操作。\n);printf(请输入初始时链表长度:);scanf(%d,&num);CreaL(L,num);LPrint(L);while(flag){printf(请选择:\n);printf(1.显示所有元素\n);printf(2.插入一个元素\n);printf(3.删除一个元素\n);printf(4.按关键字查找元素\n);printf(5.按序号查找元素\n);printf(6.链表的连接\n);printf(7.退出程序\n);scanf(%c,&j);switch(j){case'1':LPrint(L);break;case'2':{printf(请输入元素(一个字符)和要插入的位置:\n);printf(格式:字符,位置;例如:a,3\n);scanf(%c,%d,&ch,&loc);temp=LInsert(L,loc,ch);章:线性表提升实验13if(temp==False)printf(插入失败!\n);elseprintf(插入成功!\n);LPrint(L);break;}case'3':printf(请输入要删除的元素所在位置:);scanf(%d,&loc);temp=LDele(L,loc,ch);if(temp==False)printf(删除失败!\n);elseprintf(成功删除了一个元素:%c\n,ch);LPrint(L);break;case'4':if(L-next==NULL)printf(链表为空!\n);else{printf(请输入要查找的元素(一个字符):);scanf(%c,&ch);temp=LFind_key(L,ch,loc);if(