青岛理工大学数据结构第二次实验报告 - 图文

青 岛 理 工 大 学

数据结构课程实验报告

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

算 法 描 述 及 实 验 步 骤 调 试 过 程 及 实 验 结 果 template class SQList//顺序表 template class SQListjcb//顺序表的交叉并 template class SQLnode//单链表 template class SQLnodejcb//链表的交叉并 总 结 本次试验对于顺序表和链表的优缺点的认识更加深刻。顺序表中进行查找操作时较方便，而链表则适合进行插入和删除运算。顺序表存储密度大，存储空间利用率高；链表插入和删除运算时很方便，使用灵活。求集合的交并差运算用顺序表和链表实现时，顺序表的程序比较好做一点，因为是使用另一个数组C来存储运算结果，所以并没有在数组中进行插入和删除运算，程序较简单；而做链表时遇到了困难，再插入新节点时程序总是不能运行。 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERLOW -2 #include #include #include<> using 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() { elem = new T[LIST_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 = &elem[i - 1];

T*q = &elem[length - 1]; for (q; q >= p; q--) { *(q + 1) = *q; } *p = e; length++; return OK; } Status ListAdd(T e) { this->elem[this->length] = e; this->length++; return OK; } Status ListDelete(int i, T &e) { if (i > length || i < 1) return ERROR; T*p = &elem[i - 1]; e = *p; T*q = &elem[this->length - 1]; for (++p; p <= q; p++) { *(p - 1) = *p; } length--; return OK; } Status ListShow() { for (int i = 0; i < length; i++) { cout << elem[i] << 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 (q[i] == p[j]) { (q[i]); break; } } } } else { for (int i = 0; i < (); i++) { for (int j = 0; j < (); j++) { if (q[i] == p[j]) { (q[i]); break; } } } } if () == 0) { cout << \交集为空\ } else { cout << \交集为：\ (); }