免疫进化理论 - 超星慕课.pptVIP

* * 算法练习 设线性表La中的数据元素递增有序，试写一算法，将e插入到顺序表的适当位置上，以保持该表的有序性。 已知La与Lb为有序顺序表，编写算法，将La与Lb合并成一个新的有序顺序表Lc。 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。 从顺序表中删除具有给定值x的所有元素。 免疫进化理论 焦李成 * 由于高级程序设计语言中的数组也具有随机存取的特点，因此，通常用数组描述顺序存储结构。 免疫进化理论 焦李成 * 由于高级程序设计语言中的数组也具有随机存取的特点，因此，通常用数组描述顺序存储结构。 免疫进化理论 焦李成 * 由于高级程序设计语言中的数组也具有随机存取的特点，因此，通常用数组描述顺序存储结构。 免疫进化理论 焦李成 * 在计算机内，线性表有两种基本的存储结构： 顺序存储结构和链式存储结构。 下面我们首先讨论这顺序存储结构以及对应存储结构下实现各操作的算法。 免疫进化理论 焦李成 * 免疫进化理论 焦李成 * 免疫进化理论 焦李成 * 免疫进化理论 焦李成 * 免疫进化理论 焦李成 * 免疫进化理论 焦李成 * 免疫进化理论 焦李成 * 算法评价： 在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低 免疫进化理论 焦李成 * 免疫进化理论 焦李成 * 免疫进化理论 焦李成 * 免疫进化理论 焦李成 * 2.2 线性表的顺序表示和实现 用一组地址连续的存储单元依次存储。 例：（34, 23, 67, 43） 34 23 67 43 4 存储要点 用一段地址连续的存储单元 依次存储线性表中的数据元素 2.2 线性表的顺序表示和实现 顺序表——线性表的顺序存储结构 例：（34, 23, 67, 43） 34 23 67 43 存储空间的起始位置 4 用什么属性来描述顺序表？ 顺序表的容量（最大长度） 顺序表的当前长度 2.2 线性表的顺序表示和实现 顺序表——线性表的顺序存储结构 例：（34, 23, 67, 43） 34 23 67 43 4 如何实现顺序表的内存分配？ 顺序表 一维数组 逻辑相邻 位置相邻 如何求得任意元素的存储地址？ 0 … i-2 i-1 … n-1 Listsize-1 a1 … ai-1 ai … an 空闲 长度 2.2 线性表的顺序表示和实现 顺序表 一般情况下，(a1，a2，…, ai-1，ai , …, an)的顺序存储： c Loc(ai) Loc(a1) 0 … i-2 i-1 … n-1 Listsize-1 a1 … ai-1 ai … an 空闲 长度 Loc(ai)=Loc(a1) + (i -1)×l 随机存取：在O(1)时间内存取数据元素 2.2 线性表的顺序表示和实现 顺序表 一般情况下，(a1，a2，…, ai-1，ai , …, an)的顺序存储： c Loc(ai) Loc(a1) C语言中用一维数组来表示顺序表： 2.2 线性表的顺序表示和实现 #define LISTINCREMENT 10 //存储空间的分配增量 typedef struct{ ElemType *elem; //存储空间基址 int length; //线性表当前的大小 int listsize; //当前分配的存储容量 }SqList; #define LIST_INIT_SIZE 100 //线性表初始分配量 线性表的初始化： 2.2 线性表的顺序表示和实现 Status InitList_Sq (SqList L){ L.elem=(ElemType *) malloc (LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } * * 2.2 线性表的顺序表示和实现 数组下标 结点内容 线性表中位序 0 a1 1 1 a2 2 2 a3 3 ∶ ∶ ∶ i-1 ai i ∶ ∶ ∶ n-1 an n * * * 顺序表的