2024年數(shù)據(jù)結(jié)構(gòu)實驗報告

線性表的基本操作實現(xiàn)及其應(yīng)用一、試驗?zāi)康?、純熟掌握線性表的基本操作在兩種存儲構(gòu)造上的實現(xiàn)。2、會用線性鏈表處理簡樸的實際問題。二、試驗內(nèi)容題目一、該程序的功能是實現(xiàn)單鏈表的定義和操作。該程序包括單鏈表構(gòu)造類型以及對單鏈表操作的詳細(xì)的函數(shù)定義和主函數(shù)。其中，程序中的單鏈表（帶頭結(jié)點）結(jié)點為構(gòu)造類型，結(jié)點值為整型。單鏈表操作的選擇以菜單形式出現(xiàn)，如下所示：pleaseinputtheoperation：1.初始化2.清空3.求鏈表長度4.檢查鏈表與否為空5.檢查鏈表與否為滿6.遍歷鏈表（設(shè)為輸出元素）7.從鏈表中查找元素8.從鏈表中查找與給定元素值相似的元素在表中的位置9.向鏈表中插入元素10.從鏈表中刪除元素其他鍵退出。。。。。其中黑體部分必做三、試驗環(huán)節(jié)㈠、數(shù)據(jù)構(gòu)造與關(guān)鍵算法的設(shè)計描述1、單鏈表的結(jié)點類型定義/*定義DataType為int類型*/typedefintDataType;/*單鏈表的結(jié)點類型*/typedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkedList;2、初始化單鏈表LinkedListLinkedListInit(){}3、遍歷單鏈表voidLinkedListTraverse(LinkedListL){}4、求單鏈表的長度intLinkedListLength(LinkedListL){}5、從單鏈表表中查找元素LinkedListLinkedListGet(LinkedListL,inti){//L是帶頭結(jié)點的鏈表的頭指針，返回第i個元素}6、從單鏈表表中查找與給定元素值相似的元素在鏈表中的位置LinkedListLinkedListLocate(LinkedListL,DataTypex){}7、向單鏈表中插入元素voidLinkedListInsert(LinkedListL,inti,DataTypex){//L為帶頭結(jié)點的單鏈表的頭指針，本算法//在鏈表中第i個結(jié)點之前插入新的元素x}8、從單鏈表中刪除元素voidLinkedListDel(LinkedListL,DataTypex){刪除以L為頭指針的單鏈表中第i個結(jié)點}9、用尾插法建立單鏈表LinkedListLinkedListCreat()㈡、函數(shù)調(diào)用及主函數(shù)設(shè)計主函數(shù)求單鏈表的長度主函數(shù)求單鏈表的長度LinkedListLength(LinkedListL){}tLinkedListGet(LinkedListL,inti)向單鏈表中插入元素LinkedListInsert(LinkedListL,inti,DataTypex)從單鏈表中刪除元素LinkedListDel(LinkedListL,DataTypex)用尾插法建立單鏈表LinkedListLinkedListCreat()試驗數(shù)據(jù)運行時出現(xiàn)：然後選擇下列操作：選擇8，用尾插法建立鏈表選則操作2，求鏈表的長度然後選擇操作3，遍歷鏈表然後選擇操作4，從鏈表中查找元素然後選擇操作5，從鏈表中查找與給定元素值相似的元素在表中的位置然後選擇個操作6，向鏈表中插入元素，之後再遍歷鏈表然後選擇操作7從鏈表中刪除元素之後再遍歷鏈表㈣試驗總結(jié)通過這次線性表的基本操作實現(xiàn)及其應(yīng)用試驗的學(xué)習(xí)，我學(xué)會了鏈表的許多基本操作，懂得怎樣用C語言去編程序，懂得了許多鏈表方面的知識，也認(rèn)識到了自已的局限性，需要在此後的學(xué)習(xí)中愈加努力，學(xué)好接下來的課程。四、重要算法流程圖及程序清單1、重要算法流程圖：主函數(shù)主函數(shù)開始界面求鏈表長度遍歷鏈表查找節(jié)點插入元素刪除元素建立鏈表輸出數(shù)據(jù)結(jié)束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.遍歷鏈表（設(shè)為輸出元素）";cout<<"\n4.從鏈表中查找元素"<<"\n5.從鏈表中查找與給定元素值相似的元素在表中的位置";cout<<"\n6.向鏈表中插入元素"<<"\n7.從鏈表中刪除元素"<<"\n8.尾插法建立鏈表"<<"\n9.結(jié)束!"<<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<<"請輸入要查找的數(shù)據(jù)："<<endl; cin>>x; LinkedListLocate(L,x); } elseif(a==6) { inti,x; cout<<"請輸入要插入的位置和數(shù)據(jù)："<<endl; cin>>i>>x; LinkedListInsert(L,i,x); } elseif(a==7) { cout<<"請輸入要刪除的位置："<<endl; cin>>a; LinkedListDel(L,a); } elseif(a==8) { intn; cout<<"請輸入要創(chuàng)立的元素個數(shù)："<<endl; cin>>n; L=LinkedListCreat(L,n); } elseif(a==9)exit(0); else { cout<<"輸入錯誤，請重新選擇"<<endl; }}}LinkedListLinkedListInit()//初始化單鏈表{ LinkedListL;L=(LinkedList)malloc(sizeof(LinkedList));//創(chuàng)立頭節(jié)點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<<"個結(jié)點"<<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指針指向待刪除結(jié)點；q為跟蹤指針，指向其前驅(qū)。q=p=L;//初始化指針p=p->next;//q指向第一種結(jié)點while((p!=NULL)&&(p->data!=x)){ q=p; p=p->next;//p!=NULL&&p->data!=x,指針後移，繼續(xù)向後查找 }//q一直指向p的前驅(qū)if(p==NULL)printf("Xnotfound");else{ q->next=p->next;//修改指針,刪除結(jié)點X free(p);}L->data=LinkedListLength(L);}LinkedListLinkedListCreat(LinkedListL,intn)//尾插法建立單鏈表{ L=(LinkedList)malloc(sizeof(LNode)); L->next=NULL;//先建立一種帶頭結(jié)點的單鏈表 LinkedListq=L; f