青島理工大學(xué)數(shù)據(jù)結(jié)構(gòu)第二次實(shí)驗(yàn)報(bào)告

1、青 島 理 工 大 學(xué)數(shù)據(jù)結(jié)構(gòu)課程實(shí)驗(yàn)報(bào)告課程名稱數(shù)據(jù)結(jié)構(gòu)班級(jí)Abcxxx實(shí)驗(yàn)日期2015.9.25姓名Abc學(xué)號(hào)2014xxxxx實(shí)驗(yàn)成績實(shí)驗(yàn)名稱順序表和鏈表的實(shí)現(xiàn)和應(yīng)用實(shí)驗(yàn)?zāi)康募耙螅?）掌握順序表的順序存儲(chǔ)方法和基本操作；（2）掌握鏈表表的鏈?zhǔn)酱鎯?chǔ)方法和基本操作；（3）了解順序表和鏈表的優(yōu)缺點(diǎn)和適用場合；（3）能夠運(yùn)用順序表或鏈表解決問題。實(shí)驗(yàn)環(huán)境硬件平臺(tái)：普通的PC機(jī)軟件平臺(tái)：Windows 2003操作系統(tǒng) 編程環(huán)境：VisualC+實(shí)驗(yàn)內(nèi)容1. 采用遞增有序的順序表表示集合，求解兩個(gè)集合的交集、并集和差集（1）定義順序表的存儲(chǔ)結(jié)構(gòu)；（2）實(shí)現(xiàn)存儲(chǔ)遞增有序集合的順序表的建立、求交集、

2、并集和差集等運(yùn)算；（3）要求算法的時(shí)間性能在線性時(shí)間復(fù)雜度內(nèi)；（4）和采用無序順序表所表示的集合的有關(guān)運(yùn)算的時(shí)間性能進(jìn)行比較。2. 采用遞增有序的鏈表表示集合，求解兩個(gè)集合的交集、并集和差集（1）定義鏈表的存儲(chǔ)結(jié)構(gòu)；（2）實(shí)現(xiàn)存儲(chǔ)遞增有序集合的鏈表的建立、求交集、并集和差集等運(yùn)算；（3）要求算法的時(shí)間性能在線性時(shí)間復(fù)雜度內(nèi)；（4）和采用無序鏈表所表示的集合的有關(guān)運(yùn)算的時(shí)間性能進(jìn)行比較。3.比較順序表和鏈表的優(yōu)缺點(diǎn)和適用場合算法描述及實(shí)驗(yàn)步驟template class SQList/順序表template class SQListjcb/順序表的交叉并template class SQLnod

3、e/單鏈表template class SQLnodejcb/鏈表的交叉并調(diào)試過程及實(shí)驗(yàn)結(jié)果總結(jié)本次試驗(yàn)對(duì)于順序表和鏈表的優(yōu)缺點(diǎn)的認(rèn)識(shí)更加深刻。順序表中進(jìn)行查找操作時(shí)較方便，而鏈表則適合進(jìn)行插入和刪除運(yùn)算。順序表存儲(chǔ)密度大，存儲(chǔ)空間利用率高；鏈表插入和刪除運(yùn)算時(shí)很方便，使用靈活。求集合的交并差運(yùn)算用順序表和鏈表實(shí)現(xiàn)時(shí)，順序表的程序比較好做一點(diǎn)，因?yàn)槭鞘褂昧硪粋€(gè)數(shù)組C來存儲(chǔ)運(yùn)算結(jié)果，所以并沒有在數(shù)組中進(jìn)行插入和刪除運(yùn)算，程序較簡單；而做鏈表時(shí)遇到了困難，再插入新節(jié)點(diǎn)時(shí)程序總是不能運(yùn)行。附錄#define TRUE 1#define FALSE 0#define OK 1#define ERROR

4、 0#define INFEASIBLE -1#define OVERLOW -2#include#include#includeusing namespace std;typedef int Status;const int LIST_INIT_SIZE = 100;const int LISTINCREMENT = 10;template class SQList/順序表private:T*elem;T*newbase;int length;int listsize;public:T* Getelem()return elem;int Getlength()return this-leng

5、th;SQList()elem = new TLIST_INIT_SIZE;if (!elem)exit(OVERLOW);length = 0;listsize = LIST_INIT_SIZE;Status ListInsert(int i, T e)if (ilength + 1)return ERROR;if (length listsize)newbase = (T*)realloc(elem, listsize + LISTINCREMENT);if (!newbase)exit(OVERLOW);elem = newbase;listsize += LISTINCREMENT;T

6、*p = &elemi - 1;T*q = &elemlength - 1;for (q; q = p; q-)*(q + 1) = *q;*p = e;length+;return OK;Status ListAdd(T e)this-elemthis-length = e;this-length+;return OK;Status ListDelete(int i, T &e)if (i length | i length - 1;for (+p; p = q; p+)*(p - 1) = *p;length-;return OK;Status ListShow()for (int i =

7、 0; i length; i+)cout elemi endl;return OK;template class SQListjcb/順序表的交叉并public:void JiaoJi(SQList a, SQList b)SQList h;int *p = a.Getelem();int *q = b.Getelem();if (a.Getlength() b.Getlength()for (int i = 0; i b.Getlength(); i+)for (int j = 0; j a.Getlength(); j+)if (qi = pj)h.ListAdd(qi);break;e

8、lsefor (int i = 0; i b.Getlength(); i+)for (int j = 0; j a.Getlength(); j+)if (qi = pj)h.ListAdd(qi);break;if (h.Getlength() = 0)cout 交集為空 endl;elsecout 交集為： endl;h.ListShow();void bingji(SQLista, SQListb)SQListc;int v;int *pa = a.Getelem();int *pb = b.Getelem();int *pc = c.Getelem();while (pa a.Get

9、elem() + a.Getlength() & pb b.Getelem() + b.Getlength()if (*pa = *pb)c.ListAdd(*pa);pa+;elsec.ListAdd(*pb);pb+;if (pa = a.Getelem() + a.Getlength()for (pb; pb b.Getelem() + b.Getlength(); pb+)c.ListAdd(*pb);elsefor (pa; pa a.Getelem() + a.Getlength(); pa+)c.ListAdd(*pa);for (int i = 1; i c.Getlength

10、(); i+)int j = i;int h = j-;if (pcj = pch)c.ListDelete(i + 1, v);cout 并集為： endl;c.ListShow();void chaji(SQLista, SQListb)SQList h;int w;int *p = a.Getelem();int *q = b.Getelem();int *qh = h.Getelem();if (a.Getlength() b.Getlength()for (int i = 0; i b.Getlength(); i+)for (int j = 0; j a.Getlength();

11、j+)if (qi = pj)h.ListAdd(qi);break;for (int i = 0; i h.Getlength(); i+)for (int j = 0; j a.Getlength(); j+)if (qhi = pj)int t = j;t+;a.ListDelete(t, w);break;cout 差集為： endl;a.ListShow();elsefor (int i = 0; i b.Getlength(); i+)for (int j = 0; j a.Getlength(); j+)if (qi = pj)h.ListAdd(qi);break;for (i

12、nt i = 0; i h.Getlength(); i+)for (int j = 0; j b.Getlength(); j+)if (qhi = qj)int t = j;t+;b.ListDelete(t, w);break;cout 差集為： endl;b.ListShow();template struct Lnode/鏈表的節(jié)點(diǎn)結(jié)構(gòu)體T Data;Lnode *next;template class SQLnode/單鏈表public:Lnode *head;SQLnode()this-head = new Lnode();this-head-next = NULL;Status

13、 SQLnodeAdd(T e)Lnode*p = new Lnode();Lnode*q = head;p-Data = e;p-next = NULL;if (head-next = NULL)head-next = p;elsewhile (q-next != NULL)q = q-next;q-next = p;return OK;Status SQLnodeInsert(int i, T e)Lnode *p = head;int j = 0;while (p&jnext;j+;if (!p | ji - 1)return ERROR;Lnode*s = new Lnode();s-

14、Data = e;s-next = p-next;p-next = s;return OK;Status SQLnodeDelete(int i, T&e)Lnode*p = head;int j = 0;while (p-next&jnext;if (p-next | ji - 1)return ERROR;Lnode*q = p-next;p-next = q-next;e = q-Data;delete(q);return OK;Status SQLShow()Lnode*p = head-next;while (p-next != NULL)cout Data next;cout Da

15、ta endl;return OK;int SQLGetLength()int i = 0;Lnode *p = head;while (p-next)p = p-next;i+;return i;template class SQLnodejcb/鏈表的交叉并public:SQLnode Bingji(SQLnodea, SQLnodeb)SQLnodec;Lnode*la = a.head;Lnode*lb = b.head;Lnode*lc = &c.head;Lnode*pb, *pa, *pc;pa = la-next;pb = lb-next;*lc = pc = la;while

16、 (pa&pb)if (pa-Data Data)pc-next = pa;pc = pa;pa = pa-next;elsepc-next = pb;pc = pb;pb = pb-next;pc-next = pa ? pa : pb;free(lb);Lnode*newhead = *lc;Lnode*p;newhead = newhead-next;while (newhead-next)p = newhead-next;if (newhead-Data = p-Data)newhead-next = p-next;delete(p);elsenewhead = newhead-nex

17、t;cout 并集為： endl;c.SQLShow();return c;SQLnode Jiaoji(SQLnodea, SQLnodeb)SQLnodec;Lnode*pa = a.head-next;Lnode*pb = b.head-next;while (pa)while (pb)if (pa-Data = pb-Data)c.SQLnodeAdd(pa-Data);pb = pb-next;pb = b.head-next;pa = pa-next;cout 交集為： endl;c.SQLShow();return c;void chaji(SQLnodea, SQLnodeb)

18、SQLnodejiaoji = Jiaoji(a, b);SQLnodebingji = Bingji(a, b);SQLnodechaji;Lnode*pa = bingji.head-next;Lnode*pb = jiaoji.head-next;while (pa)while (pb)if (pa-Data != pb-Data)chaji.SQLnodeAdd(pa-Data);pb = pb-next;pb = jiaoji.head-next;pa = pa-next;Lnode*newhead = chaji.head;Lnode*p;newhead = newhead-next;while (newhead-next)p = newhead-next;if (newhead-Data = p-Data)newhead-next = p-next;