管理阶段小结(一)-线性结构.ppt

内容 一、线性表合并 二、字符串及String类 三、各章重点回顾 四、课堂练习 1、顺序表的合并 将Merge函数设计成为LinearList类的成员函数； 写main( )函数测试Merge的正确性； 可以不写成模板类。 顺序表合并算法思想 函数的不同形式 2、单链表合并 将Merge函数设计成为Chain类的成员函数； 写main( )函数测试Merge的正确性； 可以不写成模板类。 函数的不同形式 示例程序 一个workspace中可有多个project； 一个project中只能有一个main( )； 分散编译； 编码规范； 程序调试。 字符串定义 空串和空格串 主串和子串 字符串的存储结构 字符串的操作 字符串比较 字符串比较 串的特点 常用的C++字符串函数 字符串类（String）及其实现 字符串的模式匹配－Brute-Force算法 Brute-Force算法分析 第2章 程序性能 第3章 数据描述（线性表） 第4章 数组和矩阵 第5章 栈 第6章 队列 第7章 跳表和散列 练习1 练习2 练习3 练习5 练习6 练习7 1、队列的结构特点：FIFO 2、队列的顺序存储表示——循环队列（重点） 循环队列队空、队满的条件 循环队列的插入、删除 3、队列的链式存储表示——链式队列 链式队列无溢出问题，空间可扩充 插入与删除分别在队尾和队头处执行 适合于多队列操作 1、字典的线性表描述：有序链表 2、散列表 散列函数的构造方法 冲突的解决：线性开型寻址、链表散列 四、课堂练习 1、计算机执行下面的语句时，语句s的执行次数为 。 for(i=1;in-1;i++) for(j=1;j=i;j++) s; 2、设双向循环链表中结点的结构为（data，lLink，rLink），且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作 。 A、p-rLink=s; s-lLink=p;p-lLink-lLink=s; s-rLink=p-rLink; B、p-rLink=s; p-rLink-lLink=s; s-lLink=p; s-rLink=p-rLink; C、s-lLink=p; s-rLink=p-rLink; p-rLink=s; p-rLink-lLink=s; D、s-lLink=p; s-rLink=p-rLink; p-rLink-lLink=s; p-rLink=s; D C 3、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是 。 A、6 B、5 C、3 D、2 4、（2004年上半年软件设计师上午试题）已知有一维数组A[0…m-1*n-1]，若要对应为 m 行、n 列的矩阵，则下面的对应关系 可将元素A[k](0≤km*n)表示成矩阵的第 i 行、第j列的元素(0≤im，0≤jn)。　　 A．i=k/n, j=k％m　　 　B．i=k/m, j=k％m 　 C．i=k/n, j=k％n D．i=k/m, j=k％n 解：k＝i*n+j 练习4 5、三维数组a[4][5][6]（下标从0开始，a有4×5×6个元素），每个元素的长度是2，则a[2][3][4]的地址是 （设a[0][0][0]的地址是1000，数据以行序优先的方式存储）。（填空题） 1164 Loc=1000+（2*5*6+3*6+4）*2=1164 *数组和矩阵 * 阶段小结（一） ——线性结构 一、线性表合并 【题目及要求】如果顺序表LA，LB的数据元素按非递减有序排列，现要求将LA和LB表中的数据元素合并为一个新的线性表LC，且LC中的数据元素仍按非递减有序排列。 算法演示 【思想】 1、设三个指针（实际是整型变量）i，j，k分别指向LA，LB和LC中某个元素，初值：i，j为1，k为0； 2、分别从LA和LB中取得i，j所指向的两个元素； 3、比较两元素的大小，谁小就把谁先插入到LC中k所指的位置； 4、LA或LB中剩余部分直接插入LC中即可。 class LinearList { private： …… public： LinearList Merge(const LinearList A,cons