template<class T> void Swap(T&a ,T&b) { T temp; temp=a; a=b; b=temp; }
函数原型： template<class T> void Cocktail_sort (T list[],int list_length)；
请每位同学写在纸上交上来 （请写上班学号和姓名）。
参考解答
（1）删除单链表中所有大于min且小于max的元素。 （2）first->7->0->9->2->8。
算法阅读
list是一个顺 序存储的线 性表的非递 减序列，阅 读算法，说 明其功能。 struct SListTable { int *elem; int size; }; void fun(SListTable& list) { int i=1; int j=0; while(i<list.size) { if(list.elem[i]!=list.elem[j]) { j++; list.elem[j]=list.elem[i]; } i++; } size=j; }
Chapter3 线性表（数据描述）
1、线性结构的特点 2、线性表的公式化描述：顺序表
– 插入、删除、查找等基本操作算法
– 如何实现内存的有效使用？动态分配一维数组！
3、线性表的链式描述（链表）
– 插入、删除、查找等基本操作算法
– 头、尾指针的使用，对算法的影响！
线性表（续）
4、循环链表的遍历、双向链表的定义及相关操作
B
4、在双向链表存储结构中，删除p所指的结点时须修改指针 （ ）。 A A． p->llink->rlink=p->rlink; p->rlink->llink=p->llink; B． p->llink=p->llink->llink; p->llink->rlink=p; C． p->rlink->llink=p; p->rlink=p->rlink->rlink
数据结构与算法
授课教师：张剑波 方 芳 授课班级：111081-4班 115081-2班
2009年秋季
阶段小结（一）线性结构
教学内容
相关章节重要知识点回顾 课堂练习 第一阶段作业及实习小结
相关章节
Chapter2 程序性能 Chapter3 数据描述（线性表） Chapter4 数组和矩阵 Chapter5 堆栈 Chapter6 队列 Chapter7 散列 补充数据结构：字符串
D． p->rlink=p->llink->llink; p->llink=p->rlink->rlink;
5、递归过程或函数调用时，处理参数及返回地址，要用一 种称为（ ）的数据结构。 C
A．队列
B．多维数组
C．栈
D. 线性表
6、用I表示入栈操作，O表示出栈操作，若元素入栈顺序为 1234，为了得到1342出栈顺序，相应的I和O操作串为（ ）。 A．IIOOIIOO C．IOIIOIOO B．IOIOIIOO D．IOIIOOIO
2、计算机执行下面的语句时，语句s的执行次数为 for(i=1;i<n-1;i++) for(j=1;j<=i;j++) s;
。
(n 1)( n 2) 1 i 2 i 1 j 1 i 1
n2 i n2
3、下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。
B
2、解答题
a11 a 21 A a12 a22 a32 a23 a33 a34 ... an 1, n 2 an 1, n 1 an , n 1 an 1, n an, n
1、设有三对角矩阵，如上图所示，将带状区域中的元素 ai,j(|i-j|≤1)放在一维数组B中，则 （1）B的大小为多少？ （2）元素ai,j在B中的位置是什么？（B的下标从0开始计， 以行优先方式存储）
堆栈（续）
3、链式栈
– 自定义链式栈的实现：LinkedStack
– 插入与删除仅在栈顶（链头）处执行 – 适合于多栈操作 4、栈的应用 – 表达式计算 – 递归：汉诺塔
– 火车车厢重排算法
Chapter6 队列
1、队列的结构特点：FIFO
2、队列的顺序存储表示——循环队列（重点） – 顺序队列的”假溢出“问题 – 循环队列队空、队满的条件 – 循环队列的插入、删除操作 – 循环队列的实现：Queue
4、矩阵类 – Matrix – 矩阵的基本运算：加、减、乘法
数组和矩阵（续）
5、特殊矩阵的压缩 – 对角矩阵 – 三对角矩阵 – 三角矩阵、对称矩阵 6、稀疏矩阵 – 两种描述形式：三元组表、十字链表 – 掌握：SparseMatrix快速转置算法
Chapter5 栈
1、栈的结构特点：LIFO 2、顺序栈 – 自定义Stack的实现 – 栈空、栈满条件 – 插入、删除操作（压栈、弹栈） – 了解：如何实现多个栈共享存储空间
Chapter2 程序性能
1、简单搜索（查找）算法 – 顺序查找 – 折半查找：针对有序线性表（如数组） 2、简单排序算法：熟练掌握 – 选择排序 – 冒泡排序 – 插入排序
程序性能（续）
3、程序空间复杂度 – 组成及计算 4、程序时间复杂性分析 – 掌握“操作计数”法估算 5、渐近符号O、Ω、Θ – 使用上述符号准确描述算法的时间复杂度 – 以三种简单排序算法为例
9、算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）。 A．ab+cde/* C．abcde/*++ B．abcde/+*+ D．abcde*/++
B
10、设有一组关键码{19，01，23，14，55，20，84，27， 68，11，10，77}，采用散列函数H（key）=key%13，处理 冲突的方法是线性探测再散列的方法（即dj+1=（dj+1）%m） 若在0~18（即m=19）的散列地址空间中对该关键码构造散 列表，则关键码14对应的地址是（ ）。 A．1 B．2 C．3 D．14
队列（续）
3、队列的链式存储表示——链式队列 –插入与删除分别在队尾和队头处执行 – 循环队列的实现：LinkedQueue 4、队列的应用
– 再解：火车车厢重排 – 循环队列的应用：键盘输入缓冲区等
Chapter7 散列
1、字典的线性表描述：有序链表SortedChain
2、散列表
– 散列函数的构造方法：除留取余法
鸡尾酒排序示例
3 3
1
5 1
3
1 4
2
4 5
4
9 6
5
6 7
6
7 2
7
2 9
9
1
2
3
4
5
6
7
9
参考解答
template<class T> void cocktail_sort(T list[], int list_length) { // the first element of list has index 0 int bottom = 0; int top = list_length - 1; bool swapped = true; while(swapped == true) // if no elements have been swapped, then the list is sorted { swapped = false; for(int i = bottom; i < top; i++) { if(list[i] > list[i + 1]) // test whether the two elements are in the correct order { Swap(list[i], list[i + 1]); // let the two elements change places swapped = true; } } // decreases top the because the element with the largest value in the unsorted // part of the list is now on the position top top = top - 1;
7 7
72 68 23 49 8 9 10 11 12 13
3、算法阅读
1、已知一带表头节点的单链表L为（5，7，0，9，4，2，8）， first指针指向表头节点，data为链表的值域，link为指针域。阅 读以下程序，回答问题。 template <class Type> void Chain<Type>::fun(Type min, Type max) { ChainNode<Type> *pr=first, *p=first->link; while(p) { if( p->data>min && p->data<max) { pr->link=p->link; delete p; p=pr->link; } else { pr=p; p=pr->link; } （1）说明该程序的功能； （2）试画出执行L.fun(3,7);调用 } 后的L链表的逻辑示意图。 }