63数据结构实验报告

线性表的基本操作实现及其应用一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现。2、会用线性链表解决简单的实际问题。二、实验内容题目一、该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示：pleaseinputtheoperation：1.初始化2.清空3.求链表长度4.检查链表是否为空5.检查链表是否为满6.遍历链表（设为输出元素）7.从链表中查找元素8.从链表中查找与给定元素值相同的元素在表中的位置9.向链表中插入元素10.从链表中删除元素其他键退出。。。。。其中黑体部分必做三、实验步骤㈠、数据结构与核心算法的设计描述1、单链表的结点类型定义/*定义DataType为int类型*/typedefintDataType;/*单链表的结点类型*/typedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkedList;2、初始化单链表LinkedListLinkedListInit(){}3、遍历单链表voidLinkedListTraverse(LinkedListL){}4、求单链表的长度intLinkedListLength(LinkedListL){}5、从单链表表中查找元素LinkedListLinkedListGet(LinkedListL,inti){//L是带头结点的链表的头指针，返回第i个元素}6、从单链表表中查找与给定元素值相同的元素在链表中的位置LinkedListLinkedListLocate(LinkedListL,DataTypex){}7、向单链表中插入元素voidLinkedListInsert(LinkedListL,inti,DataTypex){//L为带头结点的单链表的头指针，本算法//在链表中第i个结点之前插入新的元素x}8、从单链表中删除元素voidLinkedListDel(LinkedListL,DataTypex){删除以L为头指针的单链表中第i个结点}9、用尾插法建立单链表LinkedListLinkedListCreat()㈡、函数调用及主函数设计㈢程序调试及运行结果分析实验数据运行时出现：然后选择下列操作：选择8，用尾插法建立链表主函数求单链表的长度LinkedListLength(LinkedListL){}从单链表表中查找元素LinkedListLinkedListGet(LinkedListL,inti)向单链表中插入元素LinkedListInsert(LinkedListL,inti,DataTypex)从单链表中删除元素LinkedListDel(LinkedListL,DataTypex)用尾插法建立单链表LinkedListLinkedListCreat()选则操作2，求链表的长度然后选择操作3，遍历链表然后选择操作4，从链表中查找元素然后选择操作5，从链表中查找与给定元素值相同的元素在表中的位置然后选择个操作6，向链表中插入元素，之后再遍历链表然后选择操作7从链表中删除元素之后再遍历链表㈣实验总结通过这次线性表的基本操作实现及其应用实验的学习，我学会了链表的许多基本操作，懂得如何用C语言去编程序，懂得了许多链表方面的知识，也认识到了自己的不足，需要在今后的学习中更加努力，学好接下来的课程。四、主要算法流程图及程序清单1、主要算法流程图：2、程序清单#includestdio.h#includestdlib.h#includemalloc.h#includeiostream.h#defineMAX_SIZE100//链表的最大长度typedefintDataType;typedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkedList;LinkedListLinkedListInit();//初始化单链表intLinkedListLength(LinkedListL);//求单链表的长度voidLinkedListTraverse(LinkedListL);//主函数开始界面求链表长度遍历链表查找节点插入元素删除元素建立链表输出数据结束遍历单链表LinkedListLinkedListGet(LinkedListL,inti);//从单链表表中查找元素LinkedListLinkedListLocate(LinkedListL,DataTypex);//从单链表表中查找与给定元素值相同的元素在链表中的位置voidLinkedListInsert(LinkedListL,inti,DataTypex);//向单链表中插入元素voidLinkedListDel(LinkedListL,DataTypex);//从单链表中删除元素LinkedListLinkedListCreat(LinkedListL,intn);//尾插法建立单链表voidmain(){inta;LinkedListL;L=(LinkedList)malloc(sizeof(LNode));L-next=NULL;for(a=1;a=10;a++){coutpleaseinputtheoperationendl;cout\n1.初始化\n2.求链表长度\n3.遍历链表（设为输出元素）;cout\n4.从链表中查找元素\n5.从链表中查找与给定元素值相同的元素在表中的位置;cout\n6.向链表中插入元素\n7.从链表中删除元素\n8.尾插法建立链表\n9.结束!endl;cout请输入你所需的操作:!endl;cina;if(a==1){LinkedListInit();}elseif(a==2){cout链表长度:LinkedListLength(L)endl;}elseif(a==3){LinkedListTraverse(L);}elseif(a==4){inti;cout请输入要查找的位置：endl;cini;LinkedListGet(L,i);}elseif(a==5){intx;cout请输入要查找的数据：endl;cinx;LinkedListLocate(L,x);}elseif(a==6){inti,x;cout请输入要插入的位置和数据：endl;cinix;LinkedListInsert(L,i,x);}elseif(a==7){cout请输入要删除的位置：endl;cina;LinkedListDel(L,a);}elseif(a==8){intn;cout请输入要创建的元素个数：endl;cinn;L=LinkedListCreat(L,n);}elseif(a==9)exit(0);else{cout输入错误，请重新选择endl;}}}LinkedListLinkedListInit()//初始化单链表{LinkedListL;L=(LinkedList)malloc(sizeof(LinkedList));//创建头节点L-next=NULL;L-data=0;returnL;}intLinkedListLength(LinkedListL)//求单链表的长度{LinkedListp;inti=0;p=L;while(p){p=p-next;i++;}returni;}voidLinkedListTraverse(LinkedListL)//遍历单链表{LinkedListm;m=L;while(m!=NULL){coutm-data;m=m-next;}}LinkedListLinkedListGet(LinkedListL,inti)//从单链表表中查找元素{LinkedListp;p=L-next;intj=1;while(p&&ji){p=p-next;j++;}if(!p||ji)return0;else{coutp-data;returnp;}}LinkedListLinkedListLocate(LinkedListL,DataTypex)//从单链表表中查找与给定元素值相同的元素在链表中的位置{inti=1,m=0;if(L-next==NULL)return0;else{LinkedListp=L-next;while(p){if(p-data==x){m++;cout位置为第i个结点endl;}i++;p=p-next;}if(m0)returnp;elsereturn0;}}voidLinkedListInsert(LinkedListL,inti,DataTypex)//向单链表中插入元素{LinkedListp,s;intj=0;p=L;while(p&&ji-1){p=p-next;j++;}if(!p||j=i-1)cout插入失败!endl;else{s=(LinkedList)malloc(sizeof(LNode));s-data=x;s-next=p-next;p-next=s;}L-data=LinkedListLength(L);}voidLinkedListDel(LinkedListL,DataTypex)//从单链表中删除元素{LinkedListp,q;//p指针指向待删除结点；q为跟踪指针，指向其前驱。q=p=L;//初始化指针p=p-next;//q指向第一个结点while((p!=NULL)&&(p-data!=x)){q=p;p=p-next;//p!=NULL&&p-data!=x,指针后移，继续向后查找}//q始终指向p的前驱if(p==NULL)printf(Xnotfound);else{q-next=p-next;//修改指针,删除结点Xfree(p);}L-data=LinkedListLength(L);}LinkedListLinkedListCreat(LinkedListL,intn)//尾插法建立单链表{L=(LinkedList)malloc(sizeof(LNode));L-next=NULL;//先建立一个带头结点的单链表LinkedListq=L;for(inti=1;i=n;i++){LinkedListp=(LinkedList)malloc(sizeof(LNode));cout请输入数据：endl;cinp-data;//输入元素值p-next=NULL;q-next=p;//插入表尾q之后q=p;//指针后移，使q始终指向表尾}L-data=LinkedListLength(L);returnL;}