青岛理工大学数据结构第二次实验报告(共14页).doc

精选优质文档-倾情为你奉上青 岛 理 工 大 学数据结构课程实验报告课程名称数据结构班级Abcxxx实验日期2015.9.25姓名Abc学号2014xxxxx实验成绩实验名称顺序表和链表的实现和应用实验目的及要求（1）掌握顺序表的顺序存储方法和基本操作；（2）掌握链表表的链式存储方法和基本操作；（3）了解顺序表和链表的优缺点和适用场合；（3）能够运用顺序表或链表解决问题。实验环境硬件平台：普通的PC机软件平台：Windows 2003操作系统 编程环境：VisualC+实验内容1. 采用递增有序的顺序表表示集合，求解两个集合的交集、并集和差集（1）定义顺序表的存储结构；（2）实现存储递增有序集合的顺序表的建立、求交集、并集和差集等运算；（3）要求算法的时间性能在线性时间复杂度内；（4）和采用无序顺序表所表示的集合的有关运算的时间性能进行比较。2. 采用递增有序的链表表示集合，求解两个集合的交集、并集和差集（1）定义链表的存储结构；（2）实现存储递增有序集合的链表的建立、求交集、并集和差集等运算；（3）要求算法的时间性能在线性时间复杂度内；（4）和采用无序链表所表示的集合的有关运算的时间性能进行比较。3.比较顺序表和链表的优缺点和适用场合算法描述及实验步骤template <class T>class SQList/顺序表template <class T>class SQListjcb/顺序表的交叉并template <class T>class SQLnode/单链表template <class T>class SQLnodejcb/链表的交叉并调试过程及实验结果总结本次试验对于顺序表和链表的优缺点的认识更加深刻。顺序表中进行查找操作时较方便，而链表则适合进行插入和删除运算。顺序表存储密度大，存储空间利用率高；链表插入和删除运算时很方便，使用灵活。求集合的交并差运算用顺序表和链表实现时，顺序表的程序比较好做一点，因为是使用另一个数组C来存储运算结果，所以并没有在数组中进行插入和删除运算，程序较简单；而做链表时遇到了困难，再插入新节点时程序总是不能运行。附录#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERLOW -2#include<iostream>#include<string>#include<windows.h>using namespace std;typedef int Status;const int LIST_INIT_SIZE = 100;const int LISTINCREMENT = 10;template <class T>class SQList/顺序表private:T*elem;T*newbase;int length;int listsize;public:T* Getelem()return elem;int Getlength()return this->length;SQList()elem = new TLIST_INIT_SIZE;if (!elem)exit(OVERLOW);length = 0;listsize = LIST_INIT_SIZE;Status ListInsert(int i, T e)if (i<1 | i>length + 1)return ERROR;if (length > listsize)newbase = (T*)realloc(elem, listsize + LISTINCREMENT);if (!newbase)exit(OVERLOW);elem = newbase;listsize += LISTINCREMENT;T*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 < 1)return ERROR;T*p = &elemi - 1;e = *p;T*q = &elemthis->length - 1;for (+p; p <= q; p+)*(p - 1) = *p;length-;return OK;Status ListShow()for (int i = 0; i < length; i+)cout << elemi << endl;return OK;template <class T>class SQListjcb/顺序表的交叉并public:void JiaoJi(SQList<T> a, SQList<T> b)SQList<int> 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;elsefor (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(SQList<T>a, SQList<T>b)SQList<int>c;int v;int *pa = a.Getelem();int *pb = b.Getelem();int *pc = c.Getelem();while (pa < a.Getelem() + 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(); i+)int j = i;int h = j-;if (pcj = pch)c.ListDelete(i + 1, v);cout << "并集为：" << endl;c.ListShow();void chaji(SQList<T>a, SQList<T>b)SQList<int> 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(); 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 (int 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 <class T>struct Lnode/链表的节点结构体T Data;Lnode *next;template <class T>class SQLnode/单链表public:Lnode<T> *head;SQLnode<T>()this->head = new Lnode<T>();this->head->next = NULL;Status SQLnodeAdd(T e)Lnode<T>*p = new Lnode<T>();Lnode<T>*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<T> *p = head;int j = 0;while (p&&j<i - 1)/当i为0或1时，都在第一个节点前插入一个元素，p决定表是否遍历完，j决定i是否合法p = p->next;j+;if (!p | j>i - 1)return ERROR;Lnode<T>*s = new Lnode<T>();s->Data = e;s->next = p->next;p->next = s;return OK;Status SQLnodeDelete(int i, T&e)Lnode<T>*p = head;int j = 0;while (p->next&&j<i - 1)p = p->next;if (p->next | j>i - 1)return ERROR;Lnode<T>*q = p->next;p->next = q->next;e = q->Data;delete(q);return OK;Status SQLShow()Lnode<T>*p = head->next;while (p->next != NULL)cout << p->Data << endl;p = p->next;cout << p->Data << endl;return OK;int SQLGetLength()int i = 0;Lnode<T> *p = head;while (p->next)p = p->next;i+;return i;template <class T>class SQLnodejcb/链表的交叉并public:SQLnode<T> Bingji(SQLnode<T>a, SQLnode<T>b)SQLnode<T>c;Lnode<T>*la = a.head;Lnode<T>*lb = b.head;Lnode<T>*lc = &c.head;Lnode<T>*pb, *pa, *pc;pa = la->next;pb = lb->next;*lc = pc = la;while (pa&&pb)if (pa->Data <= pb->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<T>*newhead = *lc;Lnode<T>*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 << "并集为：" << endl;c.SQLShow();return c;SQLnode<T> Jiaoji(SQLnode<T>a, SQLnode<T>b)SQLnode<T>c;Lnode<T>*pa = a.head->next;Lnode<T>*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(SQLnode<T>a, SQLnode<T>b)SQLnode<T>jiaoji = Jiaoji(a, b);SQLnode<T>bingji = Bingji(a, b);SQLnode<T>chaji;Lnode<T>*pa = bingji.head->next;Lnode<T>*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<T>*newhead = chaji.head;Lnode<T>*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 << "差集为：" << endl;chaji.SQLShow();int main()SQListjcb<int> shun;SQList<int> a1;SQList<int> b1;cout << "顺序表：" << endl;b1.ListAdd(1);b1.ListAdd(2);b1.ListAdd(3);b1.ListAdd(4);b1.ListAdd(5);b1.ListAdd(6);a1.ListAdd(2);a1.ListAdd(4);a1.ListAdd(6);a1.ListAdd(8);a1.ListAdd(10);shun.bingji(a1, b1);shun.JiaoJi(a1, b1);shun.chaji(a1, b1);SQLnodejcb<int> lian;SQLnode<int>a2, b2;cout << "链表：" << endl;a2.SQLnodeAdd(1);a2.SQLnodeAdd(2);a2.SQLnodeAdd(3);a2.SQLnodeAdd(4);a2.SQLnodeAdd(5);a2.SQLnodeAdd(6);b2.SQLnodeAdd(2);b2.SQLnodeAdd(4);b2.SQLnodeAdd(6);b2.SQLnodeAdd(8);b2.SQLnodeAdd(10);lian.chaji(a2, b2);system("pause");专心-专注-专业