資源描述：
《中南大學數(shù)據(jù)結(jié)構(gòu)實驗報告.docx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、中南大學數(shù)據(jù)結(jié)構(gòu)實驗報告實驗題目：（1）單鏈表的實現(xiàn)（2）棧和隊列（3）二叉樹的遍歷（4）查找與排序?qū)W生姓名：代巍學生學號：指導老師：余臘生所在學院：信息科學與工程學院專業(yè)班級：信息安全1201班指導教師評定：簽名：實驗一單鏈表的實現(xiàn)一、實驗目的了解線性表的邏輯結(jié)構(gòu)和各種存儲表示方法，以及定義在邏輯結(jié)構(gòu)上的各種基本運算及其在某種存儲結(jié)構(gòu)上如何實現(xiàn)這些基本運算。在熟悉上述內(nèi)容的基礎(chǔ)上，能夠針對具體應用問題的要求和性質(zhì)，選擇合適的存儲結(jié)構(gòu)設(shè)計出相應的有效算法，解決與線性表相關(guān)的實際問題二、實驗內(nèi)容用C/C++語言編寫程序，完成以下功能：?
2、????（1）運行時輸入數(shù)據(jù)，創(chuàng)建一個單鏈表????（2）可在單鏈表的任意位置插入新結(jié)點????（3）可刪除單鏈表的任意一個結(jié)點?（4）在單鏈表中查找結(jié)點?????（5）輸出單鏈表三、程序設(shè)計的基本思想，原理和算法描述：?（包括程序的結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，輸入/輸出設(shè)計，符號名說明等）?用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。??以元素(數(shù)據(jù)元素的映象)?+?指針(指示后繼元素存儲位置)?=?結(jié)點(表示數(shù)據(jù)元素?或?數(shù)據(jù)元素的映象)??以“結(jié)點的序列”表示線性表稱作線性鏈表（單鏈表）單鏈表是指數(shù)據(jù)接點是單向排列的。一個單鏈表結(jié)點，其
3、結(jié)構(gòu)類型分為兩部分：??（1）、數(shù)據(jù)域：用來存儲本身數(shù)據(jù)。??（2）、鏈域或稱為指針域：用來存儲下一個結(jié)點地址或者說指向其直接后繼的指針。?1、單鏈表的查找?對單鏈表進行查找的思路為：對單鏈表的結(jié)點依次掃描，檢測其數(shù)據(jù)域是否是我們所要查好的值，若是返回該結(jié)點的指針，否則返回NULL。?2、單鏈表的插入?因為在單鏈表的鏈域中包含了后繼結(jié)點的存儲地址，所以當我們實現(xiàn)的時候，只要知道該單鏈表的頭指針，即可依次對每個結(jié)點的數(shù)據(jù)域進行檢測。??假設(shè)在一個單鏈表中存在2個連續(xù)結(jié)點p、q（其中p為q的直接前驅(qū)），若我們需要在p、q之間插入一個新結(jié)點
4、s，那么我們必須先為s分配空間并賦值，然后使p的鏈域存儲s的地址，s的鏈域存儲q的地址即可。(p-＞link=s;s-＞link=q)，這樣就完成了插入操作。?3、單鏈表的刪除?刪除運算思想方法刪除運算是將表的第i個結(jié)點刪去。具體步驟：找到?i-1?的存儲位置p令p-next指向?i?的直接后繼結(jié)點釋放結(jié)點?i?的空間，將其歸還給"存儲池"。四、源程序及注釋#include#include#include#include#include#
5、defineElemTypeint//鏈表類型typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;intEmptyList(LinkList&L){if(L->next==NULL){return0;}else{return1;}}//手動建立一個帶頭結(jié)點的線性鏈表LvoidSCreateList_L(LinkList&L){LinkListl,p;inti;ElemTyped;l=(LinkList)malloc(sizeof(LNode));L=(Li
6、nkList)malloc(sizeof(LNode));//生成頭結(jié)點l=L;L->next=NULL;cout<<"請依次輸入結(jié)點值，以0為結(jié)束："<>d;if(d!=0){p=(LinkList)malloc(sizeof(LNode));//生成新結(jié)點p->data=d;p->next=l->next;l->next=p;l=l->next;}elsebreak;}if(EmptyList(L))cout<<"生成鏈表成功！！";elsecout<<"鏈表為空，未生成?。?;ci
7、n.get();cin.get();}//SCreate_L//自動建立一個帶頭結(jié)點的線性鏈表LvoidZCreateList_L(LinkList&L,intn){LinkListl,p;l=(LinkList)malloc(sizeof(LNode));L=(LinkList)malloc(sizeof(LNode));//生成頭結(jié)點l=L;L->next=NULL;srand((unsigned)time(NULL));for(inti=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));/
8、/生成新結(jié)點p->data=(rand()%100+1);p->next=l->next;l->next=p;l=l->next;}cout<<"生成鏈表成功！！";cin.get();cin.get();}//ZCre
