第2章-部分习题-1.pptVIP

本章主要内容 线性表的类型定义 线性表的两种存储结构的定义 顺序表和链表的各种操作的算法描述及其时间复杂度的分析 有序表类型及有序表操作的实现 如何学会自己编写算法 真正理解学过的算法 利用现有算法的设计思想 利用“图解”分析算法设计的目标 * * 顺序表 查询 插入 删除 i=0; while (iva.length va.elem[i]!=x) i++; for ( j=va.length; j=i; j-- ) va.elem[j]=va.elem[j-1]; va.length++; for (j=i; jva.length; j-- ) va.elem[j-1]=va.elem[j]; va.length--; 单链表 查询 插入 删除 p=ha-next; while ( p!=NULL p-data!=x ) p=p-next; s=new LNode; s-next=p-next; p-next=s; q=p-next; p-next=q-next; delete(q); j=1; j i p=ha; p-next; ++ j； 双向链表 查询 插入 删除 p=ha-next; while ( p!=NULL p-data!=x ) p=p-next; s=new Lnode; s-next=p-next; p-next=s; q=p-next; p-next=q-next; delete(q); s-next-prior=s; s-prior=p; p-next-prior=p; 有序表操作的特点 1. 查询的结果同时得到插入的位置 i=0; while (iva.length va.elem[i]x) i++; 链表 p=ha-next; while ( p!=NULL p-next-datax ) p=p-next; 顺序表 2. 所有操作必须考虑其“有序”的特点 题2.12 题2.19 题2.22 题2.24 题2.30 题2.38 题2.20 题2.11 Status Insert_Sq( SqList va, ElemType x ) { // 已知顺序表 va 中元素依值非递减有序排列，本算法 // 插入新的元素 x 并保持原表的有序性,返回 OK; // 若顺序表空间已满，则不再插入并返回 OVERFLOW if (va.length == va.listsize) return OVERFLOW; i = 0; while (iva.length x=va.elem[i]) i++; for ( j=va.length; ji; j-- ) va.elem[j] = va.elem[j-1]; // 右移所有值x的元素 va.elem[i] = x; va.length++; return OK; } //Insert_Sq 题2.11 顺序表 查询 插入 删除 i=0; while (iva.length va.elem[i]!=x) i++; for ( j=va.length; j=i; j-- ) va.elem[j]=va.elem[j-1]; va.length++; for (j=i; jva.length; j-- ) va.elem[j-1]=va.elem[j]; va.length--; 题2.12 已知 A=(a1, a2, …, am) B=(b1, b2, …, bn) 均为顺序表，试编写一个比较A? B大小的算法。 分析： 1. 算法的目标是分析两个表的大小，则算法中不应当破坏原表； 2. 按题意，表的大小指的是“词典次序”，则不应当先比较两个表的长度； 3. 算法中的基本操作为：同步比较两个表中相应的数据元素。 while (iLa.Length iLb.Length) { } int compare(SqList La, SqList Lb) { if (La.elem[i]==Lb.elem[i]) i++; else if (La.elem[i]Lb.elem[i]) return -1; else return 1; i=0; if ( iLa.length iLb.Length) return 0; else if (iLb.Length) return 1; else return -1; } 题2.19 删除有序表中所有其值大于 mink 且小于maxk的数据元素。 首先分析需要