數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)雙向鏈表的操作

1、安徽省巢湖學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程設(shè)計(jì)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 雙向鏈表 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班級 10計(jì)本2班 學(xué)號10012133 姓名 聯(lián)系方式 指導(dǎo)教師20 11 年 12 月 29日目 錄1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1.1、題目1.2、要求2、總體設(shè)計(jì)2.1、功能模塊設(shè)計(jì)2.2、所有功能模塊的流程圖3、詳細(xì)設(shè)計(jì)3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的說明3.2、算法的設(shè)計(jì)思想3.3、稀疏矩陣各種運(yùn)算的性質(zhì)變換4、調(diào)試與測試：4.1、調(diào)試方法與步驟：4.2、測試結(jié)果的分析與討論：4.3、測試過程中遇到的主要問題及采取的解決措施：5、時(shí)間復(fù)雜度的分析：6、源程序清單和執(zhí)行

2、結(jié)果7、c程序設(shè)計(jì)總結(jié)8、致謝9、參考文獻(xiàn)1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1.1、題目 雙向鏈表的操作1.2、要求1. 建立雙向鏈表l，含n個(gè)結(jié)點(diǎn)且按整數(shù)值遞增排列的（輸入任意）；2. 刪除雙向鏈表中多余的值相同的元素 3. 求出的長度 4. 將雙向鏈表就地逆置 5. 向雙向鏈表中插入值，插入后雙向鏈表仍有序2、總體設(shè)計(jì)2.1、功能模塊設(shè)計(jì)根據(jù)課程設(shè)計(jì)題目的功能要求，各個(gè)功能模塊的組成框圖如下：輸入矩陣1任意輸入建立雙向鏈表>排序刪除相同元素>輸出當(dāng)前列表和長度>插入>刪除相同元素>輸出當(dāng)前列表和長度>逆置并輸出3、詳細(xì)設(shè)計(jì)模塊功能說明：如函數(shù)功能、入口及出口參數(shù)

3、說明，函數(shù)調(diào)用關(guān)系描述等；3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的說明為單向鏈表增加一個(gè)指向前趨的指針，則可以構(gòu)成雙向鏈表/-雙向鏈表存儲(chǔ)表示-typedef struct lnodeint data;struct lnode * next,*prior;/設(shè)置分別指向前后的指針lnode,*linklist;在此，節(jié)點(diǎn)inode中有兩個(gè)指針域，其一指向直接后繼，另一指向直接前趨。3.2、算法的設(shè)計(jì)思想a) 雙向鏈表創(chuàng)建 創(chuàng)建頭結(jié)點(diǎn)，通過插入，實(shí)現(xiàn)有序排列。b）插入插入時(shí)指向頭結(jié)點(diǎn)先進(jìn)行數(shù)據(jù)域的大小比較，在符合條件前向后依次比較，然后插入時(shí)先將其指針分別指向前趨和后繼，再將其前趨的next，

4、和后繼的prior指向該節(jié)點(diǎn) c) 刪除相同元素遍歷鏈表，相同時(shí)刪除節(jié)點(diǎn)，并判斷是否是尾節(jié)點(diǎn)。 d）求長度輸出當(dāng)前鏈表的l頭節(jié)點(diǎn)記錄的表長。 e）逆置指向最后一個(gè)節(jié)點(diǎn)，將其重新定義為頭結(jié)點(diǎn)，從后往前逆置各節(jié)點(diǎn)。4、調(diào)試與測試：4.1、調(diào)試方法與步驟：第一步：隨機(jī)輸入創(chuàng)建雙向鏈表；第二步：通過刪除操作完成其創(chuàng)建，并輸出；第三步：求出長度，插入輸出；第四步：逆置并輸出。4.2、測試結(jié)果的分析與討論：（測試要寫出測試用例及每個(gè)用例結(jié)果的的截圖）5、時(shí)間復(fù)雜度的分析：時(shí)間復(fù)雜度為 o。6、 源程序清單和執(zhí)行結(jié)果#include<iostream>using namespace s

5、td;typedef struct lnodeint data;struct lnode * next,*prior;lnode,*linklist;void create_link(linklist & l); /創(chuàng)建有序雙向鏈表void insert_link(linklist & l,int x); /插入x到鏈表lvoid show_link(const linklist & l); /顯示鏈表int length_link(const linklist & l) return l->data; ; /返回鏈表長void reverse_link(

6、linklist & l); /逆置鏈表void delete_same_link(linklist & l); /刪除相同元素int main() linklist h; cout<<"輸入鏈表中的元素 <字母表示結(jié)束>:" create_link(h); /創(chuàng)建有序雙向鏈表 cout<<"創(chuàng)建的鏈表為:" show_link(h); cout<<"鏈表長度為:"<<length_link(h)<<endl; cout<<"

7、要插入的數(shù) <每次輸入一個(gè)數(shù)字，按字母表示退出>:" int x; while(cin>>x) insert_link(h,x); /插入元素到鏈表 cout<<"當(dāng)前鏈表為：" show_link(h); cout<<"當(dāng)前鏈表長度為："<<length_link(h)<<endl; cout<<"要插入的數(shù) <每次輸入一個(gè)數(shù)字，按字母表示退出>:" cout<<"將鏈表逆置后為:" revers

8、e_link(h); /逆置鏈表 show_link(h); delete_same_link(h); /刪除相同元素 cout<<"刪除鏈表中相同的元素后鏈表為：" show_link(h); cout<<"當(dāng)前鏈表長度為："<<length_link(h)<<endl; return 0;void create_link(linklist & l) lnode *s; int x; s=new lnode; /s為指向頭結(jié)點(diǎn)的指針 s->data=0; s->next=null; s

9、->prior=null; l=s; while(cin>>x) insert_link(l,x); /x元素插入鏈表l cin.clear(); while(cin.get()!='n') continue;void insert_link(linklist & l,int x) /x元素插入鏈表l lnode *p=l->next,*q=l; /p指向當(dāng)前結(jié)點(diǎn)，q指向當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn) lnode *s=new lnode; /生成插入的結(jié)點(diǎn)s s->data=x; while(p!=null) if(p->data < s

10、->data) /插入結(jié)點(diǎn)的元素比鏈表當(dāng)前結(jié)點(diǎn)元素大時(shí)，p、q指向下一個(gè)結(jié)點(diǎn) q=q->next; p=p->next; else /當(dāng)前結(jié)點(diǎn)的元素大于插入結(jié)點(diǎn)的元素時(shí) s->prior=p->prior; /將s插入到p之前 s->next=p; p->prior->next=s; p->prior=s; +l->data; /表長+1 break; if(p=null) /鏈表為空或者插入結(jié)點(diǎn)元素最大時(shí)直接將結(jié)點(diǎn)插入表尾 s->next=q->next; q->next=s; s->prior=q; +l-

11、>data; void show_link(const linklist & l) /顯示鏈表 lnode *p=l->next; while(p!=null) cout<<p->data<<' ' p=p->next; cout<<endl;void reverse_link(linklist & l) /逆置鏈表l lnode *p=l->next,*q=l,*s; while(p->next!=null) p=p->next; /將p定位到最后一個(gè)結(jié)點(diǎn) l->next=p;

12、 /重定位頭結(jié)點(diǎn)指針指向鏈表最后一個(gè)元素 while(p!=l) /逆置各個(gè)結(jié)點(diǎn) s=p->prior; p->next=s; p->prior=q; q=p; p=s; q->next=null; /新鏈表的最后一個(gè)結(jié)點(diǎn)指向nullvoid delete_same_link(linklist & l) /刪除相同元素 lnode *p=l->next,*s=p->next; /p指向當(dāng)前結(jié)點(diǎn)，s指向當(dāng)前結(jié)點(diǎn)的后繼 while(s!=null) /遍歷鏈表 if(p->data = s->data) /相等時(shí)刪除結(jié)點(diǎn) p->next=s->next; delete s; s=p->next; if(s!=null) s->prior=p; /當(dāng)p不是尾結(jié)點(diǎn)。因?yàn)閜為尾結(jié)點(diǎn)時(shí)s=null -l->data; else p=p->next; /后移指針 s=s->next; 7、c程序設(shè)計(jì)總結(jié)在這次設(shè)計(jì)過程中，不僅復(fù)習(xí)課本