2023年计算机本科数据结构与算法实验指导书

实验一线性表的实验一、实验目的1、掌握用Visua1C++6.。上机调试顺序表的基本方法；2、掌握顺序表的基本操作，插入、删除、查找、以及有序顺序表的合并等算法的实现;3、掌握用VisualC++6.0上机调试单链表的基本方法；4、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现；删除、查找算法的实现。请同学们自己设计主函数和部分算法,调用5、进一步掌握循环单链表和双链表的插入二、实验内容删除、查找算法的实现。请同学们自己设计主函数和部分算法,调用下面是顺序表的部分基本操作实现的算法,这些算法,完毕下面的实验任务。/*常用的符号常量定义*/defineOK1defincERROR0defineMAXSIZE10defineLISTJNIT_SIZE10SdefineLISTINCREMENT10defineTRUE1defineFALSE0ttdefineOK1definoERROR0defineSUCCESS1defineUNSUCCESS0defineDUPLICATE-1ttdcfineMLLKEY0//0为无记录标志defineN10//数据元素个数if(n)printf(*SuccesstoCreateaLinkList!\n");elseprintf("ANULLLinkListhavebeencreated!\n");)//endofGreatcList()function1、顺序表基本操作的实现。规定生成顺序表时.，可以键盘上读取元素，用顺序存储结构实现存储。2、已知顺序表la和1b中的数据元素按非递减有序排列，将la和1b表中的数据元素，合并成为•个新的顺序表lc,1c中的数据元素仍按非递减有序排列，并且不破坏la和1b表。3.从有序顺序表A中删除那些在顺序表B和顺序表C中都出现的元素.4、将•顺序存储的线性表(设元素均为整型量)中所有零元素向表尾集中，其他元素则顺序向表头方向集中。若输入：1230050478则输出：12354780005、单链表基本操作的实现。规定生成单链表时，可以键盘上读取元素，用链式存储结构实现存储。6、已知单链表la和1b中的数据元素按非递减有序排列，将la和1b中的数据元素，合并为一个新的单链表1c,lc中的数据元素仍按非递减有序排列。规定①不破坏la表和1b表的结构。②破坏la表和1b表的结构。7、编程实现两个循环单链表的合并。8、线性表的逆置:设有一个线性表(eO,e1,-,en-2,en-|),请编写一个函数将这个线性表原地逆置，即将线性表内容置换为(en-1,en-2,…,el,eO)。线性表中的数据可认为整数、字符或字符串，试分别采用顺序存储结构和链式结构来实现。9、约瑟夫环的实现：设有n个人围坐一圈，用整数序列1,2,3,……,n表达顺序围坐在圆桌周边的人，现从某个位置s上的人开始报数，数到m的人出列，接着从出列的下一个人又从1开始重新报数，数到m的人出列，如此下去，直到所有人都出列为此。试设计拟定他们的出列顺序序列的程序。如n=8,m=4,s=1时，设每个人的编号依次为1,2,3,-开始报数，则得到的出列顺序为4,8.5,2,1,3,7,6。检查程序的对的性和健壮性。(1)采用数组表达作为求解过程中使用的数据结构。采用单向循环链表作为存储结构模拟整个过程，循环链表可不设头节点，必须注意空表和非空表的界线。#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))efineLQ(a,b)((a)<=(b))/*定义ElemType为int或别的自定义类型*/typedefintEIcmType；/*顺序存储类型*/typedefstruct{int*clcm;»int1ength;«intlistsize;}SqList；/*构造一个空线性表算法*/intInitList_Sq(SqList&L)//InitList_Sq()function{//Inititia1aSq_Liste1cm=(E1emType*)ma11oc(LIST_INTT_STZE*sizcof(ElemType));»if(!L.elcm)return(0);»L.Iength=0;L.listsize=LIST_INIT_SIZE;8return(1)；}//endofInitList_Sq()function/*从顺序表中查找与给定元素值相同的元素在顺序表中的位置*/intLocaleE1em_Sq(SqListL,ElemTypee)//LocateElemSq0sub-function{inti=1;int*p=L.elem;whi1e(i<=L.length&&*p++!=e)++i；if(i<=L.1ength)return(i);e1sereturn(ERROR)；}//LocateE1cm_Sq()end/*向顺序表中插入元素*/intListinsert_sq(SqList&L,inti,inte)//ListInsert_sq(){if(i<111i>L.1ength+1)//i(location)isi1legal{printf("Initialfailure!\n11):return(ERROR);)if(L.]cngth>=L1istsize)//insertintotheendoftheSqlist{ElemType*Newbase；Newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(E1emType));if(!Newbase){printf(*0verf1ow!\n*);8return(ERROR);L.elem=Newbase：L.1istsize+=LISTINCREMENT；int*p,*q;q=&(L.elcm[i—1]);//qpointatthee1ementbeforetheinsertedonefor(p=&(L.elcm[L.1cngth-1]);p>=q;—p)•//movethedement*(p+1)=*p;*q=e;++L.1ength：rcturn(OK);}//ListInser_sq()end/*从顺序表中删除元素*/voidListDe1eteSq(SqList&L,inti,int&e)//ListDelete_Sq0function(int*p,*q;if((i<1)||(i>L.1ength))(printf(l4%disOverFlow!\n",i)；gexit(0)；。}p=&(L.elem[i-l]);e=*p;q=L.elem+L.length-1;for(++p：p<=q；++p)*(P—1)=*p；-L.1ength；Printf(*'SuccesstoDe1eteSq_list!\n*);}//endofListDc1ete_Sq()function/*有序顺序表的合并*/intMerge_Sq(SqList&A,SqList&B,SqList&C)//Merge_Sq()function{//MergetheSqListAandBioCC.listsize=C.1ength=A.length+B.1ength；C.clem=(EIcmType*)ma1loc(C.listsizc*sizcof(ElcmType));if(IC.elem){printf("OverF1ow!\n");//fai1uretoa11ocateroominRAMreturn(0);•}；inti=0,j=0://iandjistheSubscriptofA.elem[]ande1cm[]intk=0；//kistheSubscriptofelem[]whi1e((i<A.Iength)&&(j<B.Iength))//Tomergewheni<=A.Iengthandj>=B.1ength。if(A.elem[i]<=B.e1em[j])C.elem[k]=A.e1em[i]：i++;k++;«>}//endofifelse»{C.e1em[k]=B.elem[j];j++:k++；»)//endofelsewhile(i<A.length)//inserttherestofSqListA{«>C.clem[k]=A,c1cm[i];。i++;k++；•}//endofwhi1ewhi1c(j<B.1ength)//inserttherestofSqListB°{£.clem[k]=B.elem[j]；j++；k++：printf(*SuccesstoMergcAandB!\n");return(1)：}//endofMerge_Sq()function下面是链表的部分基本操作实现的算法，请同学们自己设计主函数和部分算法,调用这些算法,完毕下面的实验任务。/*定义ElemType为int或别的自定义类型*/typedefintElemType;/*链式存储类型//typedefstruetLNode{•ElemTypedata；~structLNode*next;}LNode,*LinkList；/*单链表的取元素*/intGetElem_L(LinkListL,inti,int&e)//GetElem_L()function{//ListheHeadPointerofLinkListwithHeadNode,whentheNo.iexist,assignthe//va1uetovariab1eeandreturn"OK!*otherwisereturnError!*LNode*p;intj=l;p=L->next：while(p&&j<i){p=p->next：++j：}if(!plU>i){printf(*TheNO.%delementdoesnotexist!\ni)：cxit(0);}//endofifc=p->data;return(e);}//endofGetE1cm_L()function/*单链表的插入元素*/intListInsert_L(LinkList&L,inti,inte)//ListInsert_L()sub-function{LNode*p=L；intj=0;//findthe1ocation{p=p->next;++j：)if(!p||j>i—l)»//outoflocation{printf(*Error!The1ocationisillegal!\n")：return(ERROR)；)LNode*s;s=(Linklist)malloc(sizeof(LNode));//createnewLNodes->data=e;s->next=p—>next；p->next=s;return(OK)：}//ListInsertL()end/*单链表的蒯除元素*/intListDc1ete_L(1.inkList&L,inti,int&c)//ListDelete_L()function{//DeletetheNO.ielementofLinkListandreturnbyvariableeLNode*p,*q;intj=0：P=L;whi1e(p->next&&j<i-1)(p=p->next;+4-j;}if(!p||j>i-D{pr