例2-2 已知一个非纯集合B,试构造一个纯集合A,使A中只包含B中所有 值各不相同的数据元素。 仍选用线性表表示集合 集合A 集合B 从集合B取出物件放入集合A要求集合A中同样物件不能有两件 线性 以上 ·因此,算法的策略应该和例2-1相同 计算机教研宦 第11页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第11页 例2-2 • 已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有 值各不相同的数据元素。 • 仍选用线性表表示集合 • 从集合 B 取出物件放入集合 A要求集合A中同样物件不能有两件 以上 • 因此，算法的策略应该和例2-1相同 集合 A 集合 B
@算法22 void purge list &La, List &lb)t //构造线性表La,使其只包含Lb中所有值不相同的数据元素, //操作完成后,线性表Lb不再存在 Initlist(La);La_len=0;//创建一个空的线性表La while(! ListEmpty(Lb){//Lb表的元素尚未处理完 ListDelete( Lb, 1, e //从Lb中删除第一个数据元素赋给e f(! LocateElem( La, e) ListInsert( La, ++La len, e //若La中不存在值和e相等的数据元素,则插入之 // while Destroylist(b);//销毁线性表Lb 3// purge 计算机教研宦 第12页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第12页 算法 2.2 void purge(List &La, List &Lb) { // 构造线性表 La，使其只包含 Lb 中所有值不相同的数据元素， // 操作完成后，线性表 Lb 不再存在 InitList(La); La_len=0; // 创建一个空的线性表La while (!ListEmpty(Lb)) { // Lb 表的元素尚未处理完 ListDelete( Lb, 1, e ); // 从 Lb 中删除第一个数据元素赋给 e if (!LocateElem( La, e) ) ListInsert( La, ++La_len, e ); // 若 La 中不存在值和 e 相等的数据元素，则插入之 } // while DestroyList(Lb); // 销毁线性表 Lb } // purge
22线性表的顺序表示和实现 计算机教研宦 第13页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第13页 2.2 线性表的顺序表示和实现
@221顺序表线性表的顺序存储表示 线性表的顺序存储:用一组地址连续的存储单元依次 存放线性表中的数据元素。 顺序线性表称为顺序表。 在程序设计语言中,采用一维数组来实现 需要考虑数组容量的动态扩充; 线性 a1 a a ●●● 计算机教研宦 第14页 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第14页 2.2.1 顺序表—线性表的顺序存储表示 • 线性表的顺序存储：用一组地址连续的存储单元依次 存放线性表中的数据元素。 • 顺序线性表称为顺序表。 • 在程序设计语言中，采用一维数组来实现。 • 需要考虑数组容量的动态扩充； a1 a2 … ai-1 ai … an
@顺序表的定义 ∥-线性表的动态分配顺序存储结构 # define List NIT size80线性表存储空间的初始分配量 # define istincrement10∥线性表存储空间的分配增量 typedef struct i Elem Type *elem;∥存储空间基址 int length: ∥当前长度 int listsize; ∥￥前分配的数组容量(以 Elem Type为单位) int incrementsize;/约定的增补空间量(以 ElemType为单位) Sqlist; a1 a a n 线性表的起始地址 计算机教研宦 第15页 L. elen称作线性表的基地址 2021/2/19
Data Structure 数 据 结 构—— 第 2 章 线 性 表 胡建华 2021/2/19 计算机教研室 第15页 顺序表的定义 //----- 线性表的动态分配顺序存储结构 ----- #define LIST_INIT_SIZE 80 // 线性表存储空间的初始分配量 #define LISTINCREMENT 10 // 线性表存储空间的分配增量 typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的数组容量(以ElemType为单位) int incrementsize; //约定的增补空间量 (以ElemType为单位) } SqList; a1 a2 … ai-1 ai … an L.elem 线性表的起始地址 称作线性表的基地址