青 岛 理 工 大 学
数据结构课程实验报告
课程名称 姓名 实验名称 实 验 目 的 及 要 求 实 验 环 境 实 验 内 容 数据结构 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];
