数据结构实验二

1《数据结构》实验报告二学校：班级：学号：姓名：日期：程序名：一、上机实验的问题和要求：单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：1.从键盘输入20个整数，产生不带表头的单链表，并输入结点值。2.从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则，则显示“找不到”。3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。4.从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。5.将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。6.删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。7.把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。8.（★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）这是一个带头结点的线性链表，数据域存放整形数据，由用户输入。头结点数据域存链表长度，所以程序中有个求链表长度的函数intLengthList(LinkListL);//求链表长度L是指向头结点的指针，将长度值存入语句为L-data=LengthList(L);为了实时观察链表情况，程序中有个输出链表数据的函数voidPrintList(LinkListL);//输出链表程序可以实现8种不同的操作，这8种不同的操作由8个函数实现，分别是voidCreateList(LinkList&L);//创建链表voidLocate(LinkListL);//查询数值voidInsertList(LinkList&L);//插入数值2voidDeleteList(LinkList&L);//选择删除voidDeleterepeat(LinkList&L);//删除重复结点voidDeleteEven(LinkList&L);//删除数值为偶数的结点voidRotate(LinkList&L);//变为循环链表voidDivide(LinkList&L);//分解成两个链表这些基本操作的实现算法都比较简单，有些跟书本上一样，有些需要自己稍作思考才能写出，具体程序见第三部分8种不同的操作可以由用户通过按A-H这八个字母键来选择，分别是A:创建B:查询C:插入D:选择删除E:删除重复F:删除偶数G:变为循环链表H:分解为两个链表，见第四部分输出截图，可以清晰的看到整个过程主程序中用开关语句实现:charoperate;printf(\n\n输入字符选择链表操作类型\nA:创建B:查询C:插入D:选择删除E:删除重复F:删除偶数\nG:变为循环链表H:分解为两个链表\n);scanf(%c,&operate);switch(operate){case'a':case'A':CreateList(L);break;case'b':case'B':Locate(L);break;case'c':case'C':InsertList(L);break;case'd':case'D':DeleteList(L);break;case'e':case'E':Deleterepeat(L);break;case'f':case'F':DeleteEven(L);break;case'g':case'G':Rotate(L);break;case'h':case'H':Divide(L);break;case'\n':gotolabel;default:printf(输入有误，请重新输入！);break;}三、源程序及注释：#includestdio.h3#includemalloc.htypedefstructLNode//链表结点{intdata;structLNode*next;}LNode,*LinkList;intover_flag=0;//主函数结束标识符voidCreateList(LinkList&L);//创建链表voidLocate(LinkListL);//查询数值voidInsertList(LinkList&L);//插入数值voidDeleteList(LinkList&L);//选择删除voidDeleterepeat(LinkList&L);//删除重复结点voidDeleteEven(LinkList&L);//删除数值为偶数的结点voidRotate(LinkList&L);//变为循环链表voidDivide(LinkList&L);//分解成两个链表intLengthList(LinkListL);//求链表长度voidPrintList(LinkListL);//输出链表/**********************************************************************主函数**********************************************************************/voidmain(void){charoperate;LinkListL;intn;for(n=0;n40;n++){printf(\n\n输入字符选择链表操作类型\nA:创建B:查询C:插入D:选择删除E:删除重复F:删除偶数\nG:变为循环链表H:分解为两个链表\n);label:scanf(%c,&operate);switch(operate){case'a':case'A':CreateList(L);break;case'b':case'B':Locate(L);break;case'c':case'C':InsertList(L);break;case'd':case'D':DeleteList(L);break;case'e':4case'E':Deleterepeat(L);break;case'f':case'F':DeleteEven(L);break;case'g':case'G':Rotate(L);break;case'h':case'H':Divide(L);break;case'\n':gotolabel;//排除换行键的影响default:printf(输入有误，请重新输入！);break;}if(over_flag)return;}}/**********************************************************************创建链表**********************************************************************/voidCreateList(LinkList&L){inttemp;printf(创建链表：\n请输入创建链表所需的整数值(以-1结束):);L=(LinkList)malloc(sizeof(LNode));L-next=NULL;LinkListq=L;scanf(%d,&temp);while(temp!=-1){LinkListp;p=(LinkList)malloc(sizeof(LNode));p-data=temp;p-next=NULL;q-next=p;q=q-next;scanf(%d,&temp);}L-data=LengthList(L);PrintList(L);}/**********************************************************************查询元素**********************************************************************/voidLocate(LinkListL)5{if(!L)printf(错误：链表未创建！);intelement;printf(查询数值：\n输入要查询的数值：);scanf(%d,&element);LinkListp=L-next;inti=1;while(p){if(p-data==element){printf(找到了，它是链表的第%d个元素。\n,i);return;}p=p-next;i++;}printf(找不到。\n);}/**********************************************************************插入数值**********************************************************************/voidInsertList(LinkList&L){intx,i;printf(插入数值：\n输入要插入的数值和插入的位置：);scanf(%d,&x);scanf(%d,&i);LinkListp=L;intj=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1){printf(输入位置错误!);return;}LinkLists=(LinkList)malloc(sizeof(LNode));s-data=x;s-next=p-next;p-next=s;L-data=LengthList(L);6PrintList(L);}/**********************************************************************选择位置删除节点**********************************************************************/voidDeleteList(LinkList&L){inti;LinkListp=L;printf(选择位置删除结点：\n输入要删除数值的位置：);scanf(%d,&i);intj=0;while(p-next&&ji-1){p=p-next;++j;}if(!(p-next)||ji-1){printf(输入位置错误!);return;}LinkListq=p-next;p-next=q-next;free(q);L-data=LengthList(L);PrintList(L);}/**********************************************************************删除重复结点**********************************************************************/voidDeleterepeat(LinkList&L){printf(删除重复结点后的链表为：\n);intn=1;inta[20];LinkListq=L-next;LinkListp=q-next;a[0]=q-data;while(p){for(inti=0;in;i++){7if(p-data==a[i]){LinkListr=p;q-next=p-next;p=p-next;free(r);break;}}if(i==n){a[n++]=p-data;p=p-next;q=q-next;}}L-data=LengthList(L);PrintList(L);}/************************************************************