数据结构课程设计实验1-4(C语言)

实验一顺序表的操作1、实验目的和要求：1）了解顺序表的基本概念、顺序表结构的定义及在顺序表上的基本操作(插入、删除、查找以及线性表合并)。2)通过在visualC++实现以上操作的C语言代码。3）提前了解实验相关的知识（尤其是C语言）。2、实验内容：1)顺序表的插入算法,删除算法,顺序表的合并算法2)顺序表应用的实例（二选一）a)利用顺序表的基本运行，实现如果在顺序表A中出现的元素，在顺序表B中也出现，则在顺序表A中将该元素删除。及实现A-B。b)顺序表A和B的元素都是非递减排列，将他们合并成一个顺序表C，要求C也是非递减排列。3、部分参考实验代码：⑴顺序表结构的定义：#includestdio.h#defineListSize100typedefintDataType;typedefstruct{DataTypelist[ListSize];intlength;}SeqList;⑵顺序表插入（在第i号元素前插入一个新的元素）intInsertList(SeqList*L,inti,DataTypee)/*在顺序表的第i个位置插入元素e，插入成功返回1，如果插入位置不合法返回-1，顺序表满返回0*/{intj;if(i1||iL-length+1)/*在插入元素前，判断插入位置是否合法*/{printf(插入位置i不合法！\n);return-1;}elseif(L-length=ListSize)/*在插入元素前，判断顺序表是否已经满，不能插入元素*/{printf(顺序表已满，不能插入元素。\n);return0;}else{for(j=L-length;j=i;j--)/*将第i个位置以后的元素依次后移*/L-list[j]=L-list[j-1];L-list[i-1]=e;/*插入元素到第i个位置*/L-length=L-length+1;/*将顺序表长增1*/return1;}}⑶顺序表删除intDeleteList(SeqList*L,inti,DataType*e){intj;if(L-length=0){printf(顺序表已空不能进行删除!\n);return0;}elseif(i1||iL-length){printf(删除位置不合适!\n);return-1;}else{*e=L-list[i-1];for(j=i;j=L-length-1;j++)L-list[j-1]=L-list[j];L-length=L-length-1;return1;}实验二单链表的操作1、实验目的1）掌握用VisualC++6.0上机调试单链表的基本方法2）理解链表的基本操作、了解链表的建立和输出3）掌握链表的插入、删除、合并和归并等实现方法2、实现内容1、单链表基本操作的实现2、链表应用的实例（二选一）a)利用链表的基本运行，实现如果在链表A中出现的元素，在链表B中也出现，则在链表A中将该元素删除。b)、约瑟夫（Josephus）问题的求解（循环链表的使用，使用C和C++语言均可）。假设有编号为1，2，……，n的n个人围坐成一圈，约定从编号为k（n=k=1）的人开始报数，数到m的那个人出列，他的下一个人从1开始重新报数，数到m的那个人出列，依次类推，直到所有的人全部出列为止，由此产生一个出队编号的序列。1、给定一个8个人的圈（n=8），约定从第3个人开始报数（k＝3），数到第4个人时的那个人出列（m＝4），使用循环链表，产生一个出队编号的序列。2、参考的出队序列为：62743518。3、部分参考实验代码：1、结点定义typedefintDataType;typedefstructNode{DataTypedata;structNode*next;}ListNode,*LinkList;2、单链表初始化voidInitList(LinkList*head)/*将单链表初始化为空。动态生成一个头结点，并将头结点的指针域置为空。*/{if((*head=(LinkList)malloc(sizeof(ListNode)))==NULL)/*为头结点分配一个存储空间*/exit(-1);(*head)-next=NULL;/*将单链表的头结点指针域置为空*/}ListNode*Get(LinkListhead,inti)/*查找单链表中第i个结点。查找成功返回该结点的指针表示成功；否则返回NULL表示失败。*/{ListNode*p;intj;if(ListEmpty(head))/*在查找第i个元素之前，判断链表是否为空*/returnNULL;if(i1)/*在查找第i个元素之前，判断该序号是否合法*/returnNULL;j=0;p=head;while(p-next!=NULL&&ji){p=p-next;j++;}if(j==i)returnp;/*找到第i个结点，返回指针p*/elsereturnNULL;/*如果没有找到第i个元素，返回NULL*/}ListNode*LocateElem(LinkListhead,DataTypee)/*查找线性表中元素值为e的元素，查找成功将对应元素的结点指针返回，否则返回NULL表示失败。*/{ListNode*p;p=head-next;/*指针p指向第一个结点*/while(p){if(p-data!=e)/*找到与e相等的元素，返回该序号*/p=p-next;elsebreak;}returnp;}intLocatePos(LinkListhead,DataTypee)/*查找线性表中元素值为e的元素，查找成功将对应元素的序号返回，否则返回0表示失败。*/{ListNode*p;inti;if(ListEmpty(head))/*在查找第i个元素之前，判断链表是否为空*/return0;p=head-next;/*指针p指向第一个结点*/i=1;while(p){if(p-data==e)/*找到与e相等的元素，返回该序号*/returni;else{p=p-next;i++;}}if(!p)/*如果没有找到与e相等的元素，返回0，表示失败*/return0;}intInsertList(LinkListhead,inti,DataTypee)/*在单链表中第i个位置插入一个结点，结点的元素值为e。插入成功返回1，失败返回0*/{自己完成}intDeleteList(LinkListhead,inti,DataType*e)/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/{ListNode*pre,*p;intj;pre=head;j=0;while(pre-next!=NULL&&pre-next-next!=NULL&&ji-1)/*判断是否找到前驱结点*/{pre=pre-next;j++;}if(j!=i-1)/*如果没找到要删除的结点位置，说明删除位置错误*/{printf(删除位置错误);return0;}/*指针p指向单链表中的第i个结点，并将该结点的数据域值赋值给e*/p=pre-next;*e=p-data;/*将前驱结点的指针域指向要删除结点的下一个结点，也就是将p指向的结点与单链表断开*/pre-next=p-next;free(p);/*释放p指向的结点*/return1;}实验三双链表的操作1、目的理解双链表的基本操作了解双链表的建立和输出掌握双链表的插入、删除等实现方法2、内容和要求基本要求编写一个程序，实现双链表的各种基本运算（假设双链表的元素类型为char），并在此基础上设计一个程序，完成如下功能：（1）初始化双链表h；（2）采用尾插法依次插入元素a，b，c，d，e；（3）输出双链表h；（4）输出双链表h长度；（5）判断双链表h是否为空；（6）输出双链表h的第3个元素；（7）输出元素a的位置；（8）在第4个位置上插入元素f；（9）输出双链表h；（10）删除h的第3个元素；（11）输出双链表h；（12）释放双链表h。#includestdio.h#includemalloc.htypedefcharElemType;typedefstructDNode//定义双链表结点类型{ElemTypedata;structDNode*prior;//指向前驱结点structDNode*next;//指向后继结点}DLinkList;voidInitList(DLinkList*&L){L=(DLinkList*)malloc(sizeof(DLinkList));L-prior=L-next=NULL;}voidDestroyList(DLinkList*&L){DLinkList*p=L,*q=p-next;while(q!=NULL){free(p);p=q;q=q-next;}free(p);}intListEmpty(DLinkList*L){return(L-next==NULL);}intListLength(DLinkList*L){DLinkList*p=L;inti=0;while(p-next!=NULL){i++;p=p-next;}return(i);}voidDispList(DLinkList*L){DLinkList*p=L-next;while(p!=NULL){printf(%c,p-data);p=p-next;}printf(\n);}intGetElem(DLinkList*L,inti,ElemType&e){intj=0;DLinkList*p=L;while(ji&&p!=NULL){i++;p=p-next;}if(p==NULL)return0;elsee=p-data;return1;}intLocateElem(DLinkList*L,ElemTypee){inti=1;DLinkList*p=L-next;while(p!=NULL&&p-data!=e){p=p-next;i++;}if(p==NULL)return(0);elsereturn(i);}intListInsert(DLinkList*&L,inti,ElemTypee){}intListDelete(DLinkList*&L,inti,ElemType&e){}.voidmain(){DLinkList*h;ElemTypee;printf(双链表的基本运算如下:\n);printf((1)初始化双链表h\n);InitList(h);printf((2)依次采用尾插法插入a,b,c,d,e元素\n);ListInsert(h,1,'a');ListInsert(h,2,'b');ListInsert(h,3,'c');ListInsert(h,4,'d');ListInsert(h,5,'e');printf((3)输出双链表h:);DispList(h);printf((4)双链表h长度=%d\n,ListLength(h));printf((5)双链表h为%s\n,(ListEmpty(h)?空:非空));GetElem(h,3,e);printf((6)双链表h的第3个元素=%c\n,e);printf((7)元素a的位置=%d\n,LocateElem(h,'a'));printf((8)在第4个元素位置上插入f元素\n);ListInsert(h,4,'f');printf((9)输出双链表h:);DispList(h);printf((10)删除h的第3个元素\n);ListDelete(h,3,e);printf((11)输出双链表h:);DispList(h);printf((12)释放双链表h\n);DestroyList(h);}实验4：栈的定义及基本操作一、实验目的：.熟练掌握栈和队列的特点.掌握栈的定义和基本操作，熟练掌握顺序栈的操作及