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

青青 岛岛 理理 工工 大大 学学 数据结构课程实验报告数据结构课程实验报告 课程名称 姓名 实验名称 实 验 目 的 及 要 求 实 验 环 境 实 验 内 容 数据结构 Abc 班级 学号 Abcxxx 实验日期 2014xxxxx 实验成绩 顺序表和链表的实现和应用 （1）掌握顺序表的顺序存储方法和基本操作； （2）掌握链表表的链式存储方法和基本操作； （3）了解顺序表和链表的优缺点和适用场合； （3）能够运用顺序表或链表解决问题。 硬件平台：普通的 PC 机 软件平台：Windows 2003 操作系统 编程环境：VisualC++ 1. 采用递增有序的顺序表表示集合，求解两个集合的交集、并集和 差集 （1）定义顺序表的存储结构； （（2）实现存储递增有序集合的顺序表的建立、求交集、并集和差集 等运算； （3）要求算法的时间性能在线性时间复杂度内； （4）和采用无序顺序表所表示的集合的有关运算的时间性能进行比 较。 2. 采用递增有序的链表表示集合，求解两个集合的交集、并集和差 集 （1）定义链表的存储结构； （2）实现存储递增有序集合的链表的建立、求交集、并集和差集等 运算； （3）要求算法的时间性能在线性时间复杂度内； （4） 和采用无序链表所表示的集合的有关运算的时间性能进行比较。 3.比较顺序表和链表的优缺点和适用场合 算 法 描 述 及 实 验 步 骤 调 试 过 程 及 实 验 结 果 template template class SQList//class SQList//顺序表顺序表 template template class SQListjcb//class SQListjcb//顺序表的交叉并顺序表的交叉并 template template class SQLnode//class SQLnode//单链表单链表 template template class SQLnodejcb//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 (ilength + 1) return ERROR; if (length listsize) { newbase = (T*)realloc(elem, listsize + LISTINCREMENT); if (!newbase) exit(OVERLOW); elem = newbase; listsize += LISTINCREMENT; } T*p = T*q = 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 for (++p; p ()) { for (int i = 0; i ()) { for (int i = 0; i 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; } else { while (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 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 int j = 0; while (p-next } 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 next) { p = p-next; i++; } return i; } }; template class SQLnodejcb//链表的交叉并 { public: SQLnode Bingji(SQLnodea, SQLnodeb) { SQLnodec; Lnode*la = ; Lnode*lb = ; Lnode**lc = &; Lnode*pb, *pa, *pc; pa = la-next; pb = lb-next; *lc = pc = la; while (pa pc = pa; pa = pa-next; } else { pc-next = pb;