2024年数据结构实验报告

线性表的基本操作实現及其应用一、试验目的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()㈡、函数调用及主函数设计主函数求單链表的長度主函数求單链表的長度LinkedListLength(LinkedListL){}tLinkedListGet(LinkedListL,inti)向單链表中插入元素LinkedListInsert(LinkedListL,inti,DataTypex)從單链表中删除元素LinkedListDel(LinkedListL,DataTypex)用尾插法建立單链表LinkedListLinkedListCreat()试验数据运行時出現：然後选择下列操作：选择8，用尾插法建立链表选则操作2，求链表的長度然後选择操作3，遍历链表然後选择操作4，從链表中查找元素然後选择操作5，從链表中查找与給定元素值相似的元素在表中的位置然後选择個操作6，向链表中插入元素，之後再遍历链表然後选择操作7從链表中删除元素之後再遍历链表㈣试验總結通過這次线性表的基本操作实現及其应用试验的學习，我學會了链表的許多基本操作，懂得怎样用C語言去编程序，懂得了許多链表方面的知识，也认识到了自已的局限性，需要在此後的學习中愈加努力，學好接下来的課程。四、重要算法流程图及程序清單1、重要算法流程图：主函数主函数開始界面求链表長度遍历链表查找节點插入元素删除元素建立链表输出数据結束2、程序清單#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<iostream.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++){ cout<<"pleaseinputtheoperation"<<endl;cout<<"\n1.初始化"<<"\n2.求链表長度"<<"\n3.遍历链表（设為输出元素）";cout<<"\n4.從链表中查找元素"<<"\n5.從链表中查找与給定元素值相似的元素在表中的位置";cout<<"\n6.向链表中插入元素"<<"\n7.從链表中删除元素"<<"\n8.尾插法建立链表"<<"\n9.結束!"<<endl; cout<<"請输入你所需的操作:!"<<endl; cin>>a;if(a==1) { LinkedListInit(); } elseif(a==2) { cout<<"链表長度:"<<LinkedListLength(L)<<endl; } elseif(a==3) { LinkedListTraverse(L); } elseif(a==4) { inti; cout<<"請输入要查找的位置："<<endl; cin>>i; LinkedListGet(L,i); } elseif(a==5) { intx; cout<<"請输入要查找的数据："<<endl; cin>>x; LinkedListLocate(L,x); } elseif(a==6) { inti,x; cout<<"請输入要插入的位置和数据："<<endl; cin>>i>>x; LinkedListInsert(L,i,x); } elseif(a==7) { cout<<"請输入要删除的位置："<<endl; cin>>a; LinkedListDel(L,a); } elseif(a==8) { intn; cout<<"請输入要创立的元素個数："<<endl; cin>>n; 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) { cout<<m->data; m=m->next; }}LinkedListLinkedListGet(LinkedListL,inti)//從單链表表中查找元素{ LinkedListp; p=L->next; intj=1; while(p&&j<i) { p=p->next; j++; } if(!p||j>i) return0; else { cout<<p->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(m>0) returnp; else return0; }}voidLinkedListInsert(LinkedListL,inti,DataTypex)//向單链表中插入元素{ LinkedListp,s; intj=0; p=L; while(p&&j<i-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;//修改指针,删除結點X free(p);}L->data=LinkedListLength(L);}LinkedListLinkedListCreat(LinkedListL,intn)//尾插法建立單链表{ L=(LinkedList)malloc(sizeof(LNode)); L->next=NULL;//先建立一种带頭結點的單链表 LinkedListq=L; f