海南大学数据结构实验参考程序

实验一线性表参考答案参考程序1//************************//*PROGRAM:顺序结构的线性表*//*CONTENT:建立,插入,删除,查找*//*编程语言：Visualc++6.0*//**********************#includestdio.h#includestdlib.h#defineMAXSIZE20typedefintElemType;//数据元素的类型typedefstruct{ElemTypea[MAXSIZE];intlength;}SqList;//顺序存储的结构体类型SqLista,b,c;//函数声明voidcreat_list(SqList*L);voidout_list(SqListL);voidinsert_sq(SqList*L,inti,ElemTypee);ElemTypedelete_sq(SqList*L,inti);intlocat_sq(SqListL,ElemTypee);//主函数voidmain(){inti,k,loc;ElemTypee,x;charch;do{printf(\n\n\n);printf(\n1.建立线性表);printf(\n2.插入元素);printf(\n3.删除元素);printf(\n4.查找元素);printf(\n0.结束程序运行);printf(\n=====================);printf(\n请输入要执行的操作:);scanf(%d,&k);switch(k){case1:{creat_list(&a);out_list(a);}break;case2:{printf(\n请输入插入位置：,a.length+1);scanf(%d,&i);printf(请输入要插入的元素值：);scanf(%d,&e);insert_sq(&a,i,e);out_list(a);}break;case3:{printf(\n请输入要删除元素的位置：,a.length);scanf(%d,&i);x=delete_sq(&a,i);out_list(a);if(x!=-1)printf(\n删除的元素为：%d\n,x);elseprintf(要删除的元素不存在！);}break;case4:{printf(\n请输入要查找的元素值：);scanf(%d,&e);loc=locat_sq(a,e);if(loc==-1)printf(\n未找到指定元素！);elseprintf(\n已找到，元素的位置是:%d,loc);}break;}/*switch*/}while(k!=0);printf(\n按回车键，返回...\n);ch=getchar();}/*main*///建立线性表voidcreat_list(SqList*L){inti;printf(请输入线性表的长度:);scanf(%d,&L-length);for(i=0;iL-length;i++){printf(数据%d=,i);scanf(%d,&(L-a[i]));}}//输出线性表voidout_list(SqListL){inti;for(i=0;i=L.length-1;i++)printf(%10d,L.a[i]);}//在线性表的第i个位置插入元素evoidinsert_sq(SqList*L,inti,ElemTypee){intj;if(L-length==MAXSIZE)printf(线性表已满!\n);else{if(i1||iL-length+1)printf(输入位置错!\n);else{for(j=L-length-1;j=i-1;j--)L-a[j+1]=L-a[j];L-a[i-1]=e;L-length++;}}}//删除第i个元素，返回其值ElemTypedelete_sq(SqList*L,inti){ElemTypex;intj;if(L-length==0)printf(空表!\n);elseif(i1||iL-length){printf(输入位置错！\n);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);}//查找值为e的元素，返回它的位置intlocat_sq(SqListL,ElemTypee){inti=0;while(i=L.length-1&&L.a[i]!=e)i++;if(i=L.length-1)return(i+1);}参考程序2：//************************//*PROGRAM:链式结构的线性表*//*CONTENT:生成,插入,删除,定位,查找*//*编程语言：Visualc++6.0*//**********************#includeconio.h#includedos.h#includestdio.h#includestdlib.h#defineLENsizeof(LNode)//定义LEN为一个//节点的长度enumBOOL{False,True};//定义BOOL型typedefstructnode{chardata;//数据域structnode*next;//指向下一个节点的指针}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(1.显示所有元素\n);//显示链//表元素printf(2.插入一个元素\n);//插入链//表元素printf(3.删除一个元素\n);//删除链//表元素printf(4.按关键字查找元素\n);//按//关键字查找printf(5.按序号查找元素\n);//按序号//查找printf(6.退出程序\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-next==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-next==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-next=NULL;printf(请输入%d个字符：例如：abcdefg\n,n);getchar();for(i=n;i0;--i){p=(LinkList)malloc(LEN);//生成新结点scanf(%c,&p-data);p-next=v-next;v-next=p;}}BOOLListInsert(LinkList&v,inti,chare){//在单链表的第i各位置插入元素e，成功返回//True，失败返回FalseLinkListp,s;intj=0;p=v;while(p&&ji-1){p=p-next;++j;}//查找第//i-1个元素的位置if(!p||ji-1)returnFalse;//没有找到s=(LinkList)malloc(LEN);//生成一个新//结点s-data=e;s-next=p-next;//将新结点插入到单链表中，即修改指针，完成插入操作p-next=s;returnTrue;}BOOLListDelete(LinkList&v,inti,char&e){//在单链表中删除第i个元素，成功删除返回//True，并用e返回该元素值，失败返回FalseLinkListp,q;intj=0;p=v;while(p-next&&ji-1)//查找第i-1个元素位//置{p=p-next;++j;}if(!(p-next)||ji-1)returnFalse;//查找//失败q=p-next;p-next=q-next;//删除该元素e=q-data;//e取得该元素值，即修改指针，删除结点qfree(q);//释放该元素空间returnTrue;}BOOLListFind_keyword(LinkListv,chare,int&i){//在单链表中查找关键字为e的元素，成功返回//True,并用i返回该元素位置，//失败返回Falsei=1;LinkListp;p=v-next;wh