數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)一 線性表鏈?zhǔn)酱鎯?chǔ)運(yùn)算的算法實(shí)現(xiàn)

1、昆明理工大學(xué)信息工程與自動(dòng)化學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告（ 201 201 學(xué)年 第 一 學(xué)期 ）課程名稱：數(shù)據(jù)結(jié)構(gòu) 開(kāi)課實(shí)驗(yàn)室： 年 月 日年級(jí)、專業(yè)、班 學(xué)號(hào) 姓名 成績(jī)實(shí)驗(yàn)項(xiàng)目名稱線性表鏈?zhǔn)酱鎯?chǔ)運(yùn)算的算法實(shí)現(xiàn)指導(dǎo)教師 教師評(píng)語(yǔ) 教師簽名： 年 月 日一.實(shí)驗(yàn)內(nèi)容：線性表鏈?zhǔn)酱鎯?chǔ)運(yùn)算的算法實(shí)現(xiàn)，實(shí)現(xiàn)鏈表的建立、鏈表的數(shù)據(jù)插入、鏈表的數(shù)據(jù)刪除、鏈表的數(shù)據(jù)輸出。二.實(shí)驗(yàn)?zāi)康模?.掌握線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的C語(yǔ)言描述及運(yùn)算算法的實(shí)現(xiàn)；2.分析算法的空間復(fù)雜度和插入和刪除的時(shí)間復(fù)雜度；3.總結(jié)比較線性表順序存儲(chǔ)存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)的各自特點(diǎn)。三.主要程序代碼分析： LinkList creatListR1() /用尾

2、插入法建立帶頭結(jié)點(diǎn)的單鏈表 char *ch=new char(); LinkList head=(LinkList)malloc(sizeof(ListNode); /生成頭結(jié)點(diǎn)*head ListNode *s,*r,*pp; r=head; /尾指針初值指向頭結(jié)點(diǎn) r->next=NULL; scanf("%s",ch); /讀入第一個(gè)結(jié)點(diǎn)的值 while(strcmp(ch,"#")!=0) /輸入#結(jié)束 pp=LocateNode(head,ch); if(pp=NULL) s=(ListNode *)malloc(sizeof(List

3、Node); /生成新的結(jié)點(diǎn)*s strcpy(s->data,ch); r->next=s; /新結(jié)點(diǎn)插入表尾 r=s; /尾指針r指向新的表尾 r->next=NULL; scanf("%s",ch); /讀入下一個(gè)結(jié)點(diǎn)的值 return head; /返回表頭指針int Insert(ListNode *head) /鏈表的插入 ListNode *in,*p,*q;int wh;in=(ListNode *)malloc(sizeof(ListNode);in->next=NULL;/生成新結(jié)點(diǎn)p=(ListNode *)malloc(siz

4、eof(ListNode);p->next=NULL;q=(ListNode *)malloc(sizeof(ListNode);q->next=NULL;scanf("%s",in->data); /輸入插入的數(shù)據(jù)scanf("%d",&wh); /輸入插入數(shù)據(jù)的位置for(p=head;wh>0;p=p->next,wh-);q=p->next;p->next=in;in->next=q;void DeleteList(LinkList head,char *key) /鏈表的刪除 ListNo

5、de *p,*r,*q=head; p=LocateNode(head,key); /按key值查找結(jié)點(diǎn)的 if(p=NULL) exit(0); /若沒(méi)有找到結(jié)點(diǎn)，退出 while(q->next!=p) /p為要?jiǎng)h除的結(jié)點(diǎn)，q為p的前結(jié)點(diǎn)q=q->next;r=q->next;q->next=r->next;free(r); /釋放結(jié)點(diǎn)*r四.程序運(yùn)行結(jié)果：五.實(shí)驗(yàn)總結(jié)：通過(guò)線性表鏈?zhǔn)酱鎯?chǔ)運(yùn)算的算法實(shí)現(xiàn)的上機(jī)實(shí)驗(yàn)，我了解了鏈?zhǔn)降幕驹砗头椒?，能編程?duì)數(shù)據(jù)進(jìn)行鏈?zhǔn)酱鎯?chǔ)。由于順序儲(chǔ)存是用物理位置上的鄰接關(guān)系來(lái)表示結(jié)點(diǎn)間的邏輯關(guān)系，其插入或刪除運(yùn)算不方便，而且當(dāng)表長(zhǎng)變化較大時(shí)，難以確定合適的存儲(chǔ)規(guī)模，為了解決這些問(wèn)題，我們采用鏈接方式存儲(chǔ)線性表。所以，當(dāng)線性表的長(zhǎng)度變化較大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，以采用動(dòng)態(tài)鏈表作為