2023年鏈表基本操作實驗報告

實驗2鏈表基本操作實驗一、實驗目的.定義單鏈表的結點類型。.熟悉對單鏈表的一些基本操作和具體的函數(shù)定義。.通過單鏈表的定義掌握線性表的鏈式存儲結構的特點。二、實驗內容與規(guī)定該程序的功能是實現(xiàn)單鏈表的定義和重要操作。如：單鏈表建立、輸出、插入、刪除、查找等操作。該程序涉及單鏈表結構類型以及對單鏈表操作的具體的函數(shù)定義和主函數(shù)。程序中的單鏈表(帶頭結點)結點為結構類型，結點值為整型。規(guī)定：同學們可參考指導書實驗2程序、教材算法及其他資料編程實現(xiàn)單鏈表相關操作。必須涉及單鏈表創(chuàng)建、輸出、插入、刪除操作，其他操作根據(jù)個人情況增減。三、算法分析與設計。.創(chuàng)建單鏈表：LinkedListLinkedListCreat()創(chuàng)建鏈表函數(shù)LinkedListL=LinkedListInit(),p,r;調用初始化鏈表函數(shù)r=L;i?指向頭結點使用maHoc函數(shù)動態(tài)分派存儲空間，指針p指向新開辟的結點，并將元素存放到新開辟結點的數(shù)據(jù)域，p=(LinkedList)malloc(sizeof(LNode));p->data=x;。r—>ncxt=p；將新的結點鏈接到頭結點r之后°r=p;i?指向p結點scanf(”%d”,&x);滿足條件循環(huán)輸入鏈表元素while(x!=flag)當輸入不為一1時循環(huán)r->next=NULL；returnL；將鏈表結尾賦空值，返回頭結點Lr二L;Printf("請依次輸入鏈表中的元素,輸入T結束\rT);scanf("%d",&x);whiIe(x!=flag){p=(LinkedList)maIIoc(sizeof(LNode));p->data=x;。r->next=p;r=P；scanf("%d",&x)；}r->next=NULL;returnL；)intscan(){intd;print千(”請選擇要進行的操作\n")；printf("\n").printf("1.初始化2.清空3.求鏈表長度4.檢查鏈表是否為空\n");printf("\n")；printf("5.遍歷鏈表6.從鏈表中查找元素\n”)；?■r/iiprintf(”7.從鏈表中查找與給定元素值相同的元素在順序表中的位置\n”)；printf(\n");printf("8.向鏈表中插入元素9.從鏈表中刪除元素10創(chuàng)建線性表'n");anw\n");printf("其他鍵退出。。。\nH)；printf("輸入：");scanf("%d",&d);return(d);}main(){intquit=0；inti,Iocate；EIemTypee;LinkedListL,p;whiIe(!quit)switch(scan())。{case1:L=LinkedListInit();printf("\n");break;。case2:LinkedListCIear(L);printf("\n");break;。case3:printf("鏈表長度為％d\n",LinkedListLength(L))；break；。case4:if(LinkedListEmpty(L))printf("鏈表為空\rT)；oselseprintf("鏈表非空\n");break；。case5：LinkedListTraverse(L);break;。case6:p「intf("請輸入待查詢元素在鏈表中的位置：")；。。scanf;。。p=LinkedListGet(L,i);。3if(p)printf("鏈表第%d個元素的值為：%d\n",i,p->data);。。elseprintf("查詢位置不對的\rT)；。break;。case7:printf("請輸入待查詢元素的值：”)；。。seanf("%d",&e)；。s。locate=LinkedListLocate(L,e);。if(locate)。。。printf("%d在鏈表中的位置是:％d\n",e,locate);。elseprintf("鏈表中沒有值為%d的元素\n”，e);。。。break;。。case8:printf("請輸入插入元素的位置和值(中間以空格或回車分隔)：\n");…scanf("％d%d"，&i,&e)；。LinkedListInsert(L,i,e);。break;。case9:if(LinkedListLength(L)==0)。。。。printf(“鏈表已經(jīng)為空，不能刪除!\n“)；66else{printf("請輸入待刪除元素的位置：");。scanf("%d",&i);。LinkedListDeI(L,i);}。。break;case10:L=LinkedListCreat0；printf("\n")；break;default:quit=1;)2.單鏈表插入voidLinkedList1nsert(LinkedListL,inti,E1emTypex)鏈表插入函數(shù)(L頭指針，i插入位置,x插入元素)LinkedListp,s;定義結構體類型指針p,sj=1；p=L;定義整型j計數(shù)，尋找插入位置,P指針指向頭結點p=p-^>next：j++;滿足條件時p指針后移，j自加1while(p&&j<i)當p為真且j<i時循環(huán)p=NULL|0<T^^^^^^Nprintf("插入位置不對的'n");s=(LNode*)ma11oc(sizeof(LNode))；使用malloc函數(shù)動態(tài)分派存儲空間，指針s指向新開辟的結點,并將插入元素x存放到新開辟結點s的數(shù)據(jù)域，將結點s指向i+l結點位置，第i個結點指向s,實現(xiàn)了鏈表元素插入。s->data=x;s->next=p->next;p->next=s；3.單鏈表的刪除:p->next=p—>ncxt->next;四、運營結果.單鏈表初始化請選擇要進行的操作二品m二洛不一工吊信雇展—二裝曾踵而醞庭「捻百卷菱一【仄屆菱而百塊品案工仄卷糞市面逅至嬴纂廟相百而品翥瀛屏嘉而應承8前后蝠菽浣纂一；:仄贏美而藤元泰二癡雇函S美RitSW值二二一SeiA?1.創(chuàng)建單鏈表事會次輸火鏈表中的元素，輸入T結束980435-6-1

.求鏈表長度.檢查鏈表是否為空4空三4空三??三k\fex向廢物［八*?5鏈表中的元素為:980435-6.從鏈表中查找元素入:用地人待查詢元素在鏈表中的位置:1懈蓑第1個亓素粉微：9售地入待查詢元素在鏈表中的位置：2暴裝第2個元素就f知8.從鏈表中查找與給定元素值相同的元素在順序表中的位置10己插入到鏈表中插入元素之后的鏈表輸入：5鏈表中的元素為：98100435-6.從鏈表中刪除元素輸入:9請輸入待刪除元素的位第6個元素己從鏈表申刪除位置為6的元素（是3）御入：5鏈表中的元素為:9810045-6.清空單鏈表胸入：2觸表己經(jīng)清空五、實驗體會通過這次單鏈表基本操作實驗，自己的編程能力有了進一步的提高，結識到自己以前在思考一個問題上思緒不夠開闊，不能靈活的表達出自己的想法，雖然在打完源代碼之后出現(xiàn)了一些錯誤，但是通過認真查找、修改，最終將錯誤一一修正，重要是在寫算法分析的時候出現(xiàn)了障礙，通過從網(wǎng)上查找資料，自己也對程序做了仔細的分析，對單鏈表創(chuàng)建、插入、刪除算法畫了具體的N-S流程圖。六、C語言版原代碼incIude<stdio.h>incIude<stdIib.h>/*定義ElemType為int類型*/typedefintEIemType；defineTRUE1defineFALSE0defineNULL0#defineflag_1/*單鏈表的結點類型*/typedefstructLNode(。ElemTypedata;。struetLNode*next；}LNode,*LinkedList；/*初始化單鏈表*/LinkedListLinkedListlnitO(LinkedListL;L=(LinkedList)maIIoc(sizeof(LNode));。L->next=NULL;returnL;)/*清空單鏈表*/voidLinkedListClear(LinkedListL)(L->next=NULL;printf（"鏈表已經(jīng)清空\n”）；/*檢查單鏈表是否為空*/intLinkedListEmpty(LinkedListL){if(L->next=NULL)returnTRUE;。eIsereturnFALSE;}/*遍歷單鏈表*/voidLinkedListTraverse(LinkedListL){LinkedListp；p=L->next;if(p二二NULL)printf("單鏈表為空表\n”)；eIse(。printf("鏈表中的元素為:\n");whiIe(p!=NULL){printf("%d",p->data)；p=p->next；}°}printf("\n");)intLinkedListLength(LinkedListL){LinkedListp;intj;。p=L->next;。j=O;whiIe(p!=NULL)。。{j++;p=p->next;}LinkedListLinkedListGet(LinkedListL,inti){LinkedListp;intj;p=L->next;j=1;while(p!=NULL&&j<i){p=p->next;j++；)if(j=i)returnp;eIsereturnNULL；)intLinkedListLocate(LinkedListL,EIemTypex)(LinkedListp;intj；p=L->next;j=1；whiIe(p!=NULL&&p->data!二x)°{p=p->next;j++;)if(p)returnj；。。。elsereturn0；)voidLinkedListlnsert(LinkedListL,inti,EIemTypex)(LinkedListp,s;intj;j=1；P=L;while(p&&j<i){p=p->next;j++;}if(p==NULL||j>i)print千("插入位置不對的\n");eIse{s二(LNode*)maIIoc(sizeof(LNode));。s->data=x;s->next=p—>next;。p->next=s；Printf("%d已插入到鏈表中、n",x)；})voidLinkedListDeI(LinkedListL,inti)(LinkedListp,q；intj；j