數(shù)據(jù)結構實驗報告實驗一線性表鏈式存儲運算的算法實現(xiàn)

1、昆明理工大學信息工程與自動化學院學生實驗報告(201課程名稱：數(shù)據(jù)結構201學年第一開課實驗室：學期)年月日年級、專業(yè)、班學號姓名成績實驗項目名稱線性表鏈式存儲運算的算法實現(xiàn)指導教師教師評教師簽名：語年月日.實驗內(nèi)容：線性表鏈式存儲運算的算法實現(xiàn)，實現(xiàn)鏈表的建立、鏈表的數(shù)據(jù)插入、鏈表的數(shù)據(jù)刪除、 鏈表的數(shù)據(jù)輸出。二.實驗目的：1. 掌握線性表鏈式存儲結構的C語言描述及運算算法的實現(xiàn);2. 分析算法的空間復雜度和插入和刪除的時間復雜度；3. 總結比較線性表順序存儲存儲與鏈式存儲的各自特點。三.主要程序代碼分析：Lin kList creatListR1()/用尾插入法建立帶頭結點的單鏈表char

2、 *ch=new char();LinkList head=(LinkList)malloc(sizeof(ListNode); /生成頭結點 *headListNode *s,*r,*pp;r=head;/尾指針初值指向頭結點r-n ext=NULL;scan f(%s,ch);/讀入第一個結點的值while(strcmp(ch,#)!=O) /輸入#結束pp=LocateNode(head,ch);if(pp=NULL) s=(ListNode *)malloc(sizeof(ListNode); /生成新的結點 *sstrcpy(s-data,ch);r-n ext=s;/r=s;/r-

3、n ext=NULL;sca nf(%s,ch);/return head;/新結點插入表尾尾指針r指向新的表尾讀入下一個結點的值返回表頭指針int In sert(ListNode *head)/ListNode *in ,*p,*q;鏈表的插入int wh;in=(ListNode *)malloc(sizeof(ListNode);i n- next=NULL; p=(ListNode *)malloc(sizeof(ListNode);p- next=NULL;/生成新結點q=(ListNode *)malloc(sizeof(ListNode);q- next=NULL;sca nf

4、(%s,i n-data);sca nf(%d,&wh);/for(p=head;wh0;p=p-n ext,wh-); q=p-n ext;p-n ext=in;in-n ext=q;/輸入插入的數(shù)據(jù)輸入插入數(shù)據(jù)的位置void DeleteList(L in kList head,char *key)ListNode *p,*r,*q=head; p=LocateNode(head,key);/if(p=NULL)exit(0);/while(q-n ext!=p)/pq=q-n ext;r=q-n ext;q-n ext=r- n ext;free(r);/鏈表的刪除按key值查找結點的若

5、沒有找到結點，退出 為要刪除的結點，q為p的前結點釋放結點*r四.程序運行結果:歡迎下載4LJ_g圭冃主冃主冃主冃圭冃主冃a b c Ju ea b cd eR J s *月居居居居居居入入入入入入入青輸入要刪除的敎據(jù),bbhCCC J.dddreee r G：逐局護5 實卸 Debuglinkli5t. exen請輸入插入的數(shù)據(jù)；XXX:青輸入你數(shù)據(jù)插入的位置,XXX,ddd.eee五.實驗總結：通過線性表鏈式存儲運算的算法實現(xiàn)的上機實驗，我了解了鏈式的基本原理和方法, 能編程對數(shù)據(jù)進行鏈式存儲。由于順序儲存是用物理位置上的鄰接關系來表示結點間的邏 輯關系，其插入或刪除運算不方便，而且當表長變化較大時，難以確定合適的存儲規(guī)模， 為了解決這些問題，我們采用鏈接方式存儲線性表。所以，當線性表的長度變化較大，難 以估計其存儲規(guī)模時，以采用動態(tài)鏈表作