10/25
算法分析
衡量、比较算法优劣的指标主要有两个：
空间复杂度S(n) ——根据算法写成的程序在执行时占用的存储 空间的大小。该存储空间一般包括三个方面： （1）指令常数变量所占用的存储空间; （2）输入数据所占用的存储空间; （3）辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。
结构）在计算机存储器中的存储形式。
例如：数据的物理结构包括 答案：数据元素 ， 数据元素间关系 的表示和 。 的表示。
逻辑结构---划分方法一
（1）线性结构（ 如：线性表、栈、队列、串） （2）非线性结构（如：树、图） 逻辑结构---划分方法二
（1）集合 结构中的数据元素除了同属于一种类型外，别无其它关系。 （2）线性结构 结构中的数据元素之间存在一对一的关系。 （3）树型结构 结构中的数据元素之间存在一对多的关系。 （4）图状结构或网状结构 结构中的数据元素之间存在多对多的关系。
• 题型小结：
– 链表逆置 – 删除链表中重复元素
拆分+逆置 例：有一个带头结点的单链表L={a1，b1，a2，b2，……，an，bn}，请设计一个函数将
其拆成两个带头结点的单链表A和B，正序链表A={a1，a2，…，an}逆序链表B={bn，bn1，……，b2，b1}。 注：函数的头部为void split（Linklist *L， LinkList * A， LinkList * B）。
答：算法思想：扫描单链表L，将奇数位置的元素添加到链表A中，将偶数位置 的元素逆向添加到链表B中。 void split（Linklist *L， LinkList * A， LinkList * B） { Linklist *pL=L->next, * pA=A, *pB=B, *temp; while(pL!=NULL) { pA->next=pL; pA=pL; //把奇数位置的结点正向添加到链表A中 pL=pL->next; //pL指向下一个结点 pA->next=NULL;（注意这两句顺序不能颠倒） temp=pL->next; //把PL的下一个结点的地址先保存下来 pL->next=pB->next; //把偶数位置的结点逆向添加到链表B中 pB->next=pL; （注意：实际上是链表逆置的主要操作） pL=temp; } 链表A的建立过程类似于尾插入法， } 链表B的建立过程类似于头插入法。
第二部分 线性表、栈、队列
线性表
“线性表(Linear List)”是由同一类型的数据元素构成的序列的线性结
构。 线性表中元素的个数称为线性表的长度； 当一个线性表中没有元素（长度为0）时，称为空表。
线性表的顺序存储实现
在内存中用地址连续的一块存储空间顺序存放线性表的各元 素。一维数组在内存中占用的存储空间就是一组连续的存储区域。
第一部分 数据结构与算法
什么是数据结构？
定义1--是相互之间存在一种或多种特定关系的数据元素
的集合。 定义2----
按某种逻辑关系组织起来的一批数据（或称带结构 的数据元素的集合）应用计算机语言并按一定的存 储方式把它们存储在计算机的存储器中，并在其上 定义了一个运算的集合。
逻辑结构--数据元素间的相互关系。 存储结构（物理结构）---数据元素及其关系（数据的逻辑
(2) 输出：至少产生一个输出；
(3) 确定性：算法的每一步必须有充分明确的含义，不可以有歧义； (4) 有穷性：算法是一个有限指令集，并一定在有限步骤之后终止； (5) 可行性：算法的每一步必须在计算机能处理的范围之内
算法的描述不依赖于任何一种计算机语言以及具体的实现手段。 可以用自然语言、流程图，伪代码等方法来描述。
时间复杂度 T(n) ——根据算法写成的程序在执行时耗费时间的长 度。常用程序中最深层循环内的语句的原操作的执行频度(重复执行 的次数)来表示
12/25
例如：一个算法具有以下5个重要特性。( ) A．有穷性、确定性、可行性、输入、输出 B．可行性、可移植性、可扩充性、输入、输出 C．确定性、有穷性、稳定性、输入、输出 D．易读性、稳定性、安全性、输入、输出 答案：A 例如：下面叙述正确的是（ ） A、算法的执行效率与数据的存储结构无关 B、算法的空间复杂度是指算法程序中指令（或语句）的条数 C、算法的有穷性是指算法必须能在执行有限个步骤之后终止 D、以上三种描述都不对 答案：C
答案：D
编程题 1、有一个带头结点的单链表L={a1，b1，a2，b2，……，an，bn}，请 设计一个函数将其拆成两个带头结点的单链表A和B，正序链表A={a1， a2，…，an}逆序链表B={bn，bn-1，……，b2，b1}。 注：函数的头部为void split（Linklist *L， LinkList * A， LinkList * B）。
void RecDelete_Node (LNode *L) { // 删除以L为头结点的单链表中所有值相同的结点 if(L= =NULL) return; LNode *pre=L, *cur=pre->next; // pre始终指向当前结点cur的前一个 位置 while ( cur!=NULL) // 检查链表中所有结点 { if (cur->data= =L->data) { pre->next=cur->next; free( cur ); >next; } else { pre=cur; cur=cur->next; } } L=L->next; RecDeleteNote(L); }
（1）顺序存储结构
（2）链式存储结构 （3）散列存储结构 （4）索引存储结构
例如：下面哪个不是数据结构的基本存储方法（ ） A 顺序方法 答案：C B链接方法 C 随机方法 D 索引方法
抽象数据类型
抽象数据类型(Abstract Data Type ，简称ADT)：是指一个数 学模型以及定义在该模型上的一组操作。 ADT的定义仅是一组逻辑特性描述， 与其在计算机内的 表示和实现无关。因此，不论ADT的内部结构如何变化，只要 其数学特性不变，都不影响其外部使用。 ADT的形式化定义是三元组：ADT=(D，S，P) 其中：D是数据对象，S是D上的关系集，P是对D的基本操作 集。
删除重复元素 例：假设用单链表方式来存储整数序列，如下形式：
请编写一个递归算法，对这样的链表进行处理，重复结点（值相同的结点）仅保 留排在最前面的一个，最后返回新链表的首地址。例如，若有上述链表，则处理 后的新链表如下： 算法思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表 中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一 个结点，直到所有的结点都检查。 递归算法：
例如
1、若某线性表最常用的操作是存取任一个指定序号的元素和在最后进行插入 和删除运算，则利用（ ）存储方式最节省时间。 A、顺序表 B、单链表 C、带头结点的双循环链表 D、单循环链表
答案：A
2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新 元素的算法的时间复杂度为( )(1<=i<=n+1)。 A．0(O) B．0(1) C．0(n) D．0(n2) 3、如果最常用的操作是取第i个结点及其前驱，则采用( )存储方式最 节省时间。 A．单链表 B．双链表 C．单循环链表 D．顺序表
最坏： 当i=1,需移动n-1个结点（O(n)） 最好：当i=n（删除表尾元素）,无需用移动结点。（O(1)）
顺序存储的优缺点
优点 1）无须为表示结点间的逻辑关系而增加额外的存储空间（紧凑结构）。 2）可以方便地随机存取表中的任一结点。 缺点 1）插入和删除平均须移动一半结点。 2）存储分配只能预先进行（静态）
栈
堆栈的定义
“堆栈（Stack）”可以认为是操作受到一定约束的线性表， 插入和删除操作都作用在一个称为栈顶(Top)的端点位置。
入栈（Push）：把数据插入栈顶位置； 出栈（Pop） ： 从栈顶中取出数据。 栈的特点：先进后出（后进先出） 栈的应用：数制转换，表达式求值，括号匹配，函数（递归）调用
栈
例如 1、设栈S和队列Q的初始状态为空，元素a1，a2，a3，a4，a5，a6，a7和a8 依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的顺序是a3， 答案：5 a6，a7，a5，a8，a4，a2，a1，则栈的容量至少应该是_______. 2、若5个元素的出栈序列为“e1，e2，e3，e4，e5”，则可能的入栈序列为（ ） A、e2，e3, e4, e1, e5 B、e3, e1, e4, e5, e2 C、e5, e3, e4, e2, e1 D、e4, e1, e3, e2, e5 答案：D 3、设计一个判别表达式中左、右括号是否配对出现的算法，采用下列哪种数 据结构最好？（ ） A、栈 B、队列 C、线性表的顺序存储结构 D、线性表的链式存储结构 答案：A 4．一个栈的进栈序列是a b c d e，则栈的输出序列不可能的是( )。 A. e d c b a B. d e c b a C. d c e a b D. a b c d e 5．表达式a*(b+c)-d的后缀表;*d- C． abc*+d-
2、假设用单链表方式来存储整数序列，如下形式： 请编写一个递归算法，对这样的链表进行处理，重复结点（值相同的结 点）仅保留排在最前面的一个，最后返回新链表的首地址。
3、设有一个表头指针为first的单链表（不带头结点），请设计算法通过一趟 遍历将链表就地逆转（例如a->b->c->d变为d->c->b->a),要求逆转后表头 指针first指向原链表的最后一个结点，请写出C语言程序。
例如： 数据结构的二元组定义DS={D,S}，D是数据元素的有限 集合，而S则是D上的（ ）的有限集合。 A. 数组 B. 数据项 C. 关系 D.操作 答案：C