青岛理工大学数据结构第二次实验报告内容

1、青 岛 理 工 大 学数据结构课程实验报告课程名称数据结构班级Abcxxx实验日期姓名Abc学号2014xxxxx实验成绩实验名称顺序表和链表的实现和应用实验目的及要求（1）掌握顺序表的顺序存储方法和基本操作；（2）掌握链表表的链式存储方法和基本操作；（3）了解顺序表和链表的优缺点和适用场合；（3）能够运用顺序表或链表解决问题。实验环境硬件平台：普通的PC机软件平台：Windows 2003操作系统 编程环境：VisualC+实验内容1. 采用递增有序的顺序表表示集合，求解两个集合的交集、并集和差集（1）定义顺序表的存储结构；（2）实现存储递增有序集合的顺序表的建立、求交集、并集和差集等运算；

2、（3）要求算法的时间性能在线性时间复杂度内；（4）和采用无序顺序表所表示的集合的有关运算的时间性能进行比较。2. 采用递增有序的链表表示集合，求解两个集合的交集、并集和差集（1）定义链表的存储结构；（2）实现存储递增有序集合的链表的建立、求交集、并集和差集等运算；（3）要求算法的时间性能在线性时间复杂度内；（4）和采用无序链表所表示的集合的有关运算的时间性能进行比较。3.比较顺序表和链表的优缺点和适用场合算法描述及实验步骤template class SQList/顺序表template class SQListjcb/顺序表的交叉并template class SQLnode/单链表temp

3、late class SQLnodejcb/链表的交叉并调试过程及实验结果总结本次试验对于顺序表和链表的优缺点的认识更加深刻。顺序表中进行查找操作时较方便，而链表则适合进行插入和删除运算。顺序表存储密度大，存储空间利用率高；链表插入和删除运算时很方便，使用灵活。求集合的交并差运算用顺序表和链表实现时，顺序表的程序比较好做一点，因为是使用另一个数组C来存储运算结果，所以并没有在数组中进行插入和删除运算，程序较简单；而做链表时遇到了困难，再插入新节点时程序总是不能运行。附录#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define

4、 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-length;SQList

5、()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*p = &ele

6、mi - 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 = 0; i len

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

8、 = 0)cout 交集为空 endl;elsecout 交集为： endl;();void bingji(SQLista, SQListb)SQListc;int v;int *pa = ();int *pb = ();int *pc = ();while (pa () + () & pb () + ()if (*pa = *pb)(*pa);pa+;else(*pb);pb+;if (pa = () + ()for (pb; pb () + (); pb+)(*pb);elsefor (pa; pa () + (); pa+)(*pa);for (int i = 1; i (); i+)i

9、nt j = i;int h = j-;if (pcj = pch)(i + 1, v);cout 并集为： endl;();void chaji(SQLista, SQListb)SQList h;int w;int *p = ();int *q = ();int *qh = ();if () ()for (int i = 0; i (); i+)for (int j = 0; j (); j+)if (qi = pj)(qi);break;for (int i = 0; i (); i+)for (int j = 0; j (); j+)if (qhi = pj)int t = j;t+;

10、(t, w);break;cout 差集为： endl;();elsefor (int i = 0; i (); i+)for (int j = 0; j (); j+)if (qi = pj)(qi);break;for (int i = 0; i (); i+)for (int j = 0; j (); j+)if (qhi = qj)int t = j;t+;(t, w);break;cout 差集为： endl;();template struct Lnode/链表的节点结构体T Data;Lnode *next;template class SQLnode/单链表public:Lno

11、de *head;SQLnode()this-head = new Lnode();this-head-next = NULL;Status 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;w

12、hile (p&jnext;j+;if (!p | ji - 1)return ERROR;Lnode*s = new Lnode();s-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 SQL

13、Show()Lnode*p = head-next;while (p-next != NULL)cout Data next;cout Data 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 = ;Lnode*lb = ;Lnode*lc = &;Lnode*pb, *p

14、a, *pc;pa = la-next;pb = lb-next;*lc = pc = la;while (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

15、-next = p-next;delete(p);elsenewhead = newhead-next;cout 并集为： endl;();return c;SQLnode Jiaoji(SQLnodea, SQLnodeb)SQLnodec;Lnode*pa = next;Lnode*pb = next;while (pa)while (pb)if (pa-Data = pb-Data)(pa-Data);pb = pb-next;pb = next;pa = pa-next;cout 交集为： endl;();return c;void chaji(SQLnodea, SQLnodeb)S

16、QLnodejiaoji = Jiaoji(a, b);SQLnodebingji = Bingji(a, b);SQLnodechaji;Lnode*pa = next;Lnode*pb = next;while (pa)while (pb)if (pa-Data != pb-Data)(pa-Data);pb = pb-next;pb = next;pa = pa-next;Lnode*newhead = ;Lnode*p;newhead = newhead-next;while (newhead-next)p = newhead-next;if (newhead-Data = p-Data)newhead-next = p-next;delete(p);elsenewhead = newhead-next;cout 差