当前位置：文档之家 › 数据结构 算法与数据结构复习

数据结构 算法与数据结构复习

  • 格式：ppt
  • 大小：380.00 KB
  • 文档页数：13

下载文档原格式

  / 13

合集下载

复习提纲：算法与数据结构

复习提纲：算法与数据结构

1、算法的概念是为了解决某类问题而规定的一个有限长的操作序列。

特性：①有穷性②确定性③可行性④输入⑤输出评价标准：①正确性②可读性③健壮性④高效性2、算法的复杂度: 算法计算量所需资源的大小时间复杂度：T(n)=O(f(n)),他表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的时间复杂度空间复杂度：S（n）=O（f（n）），算法所需空间的度量。

3、数据结构中的逻辑结构分为：线性和非线性结构4、线性表的两种存储方式：顺序存储和链式存储的特点及比较。

顺序存储：指用一组地址连续的存储单元依次存储线性表的数据元素链式存储：用一组任意的存储单元存储线性表的数据元素。

5、线性表的特点①存在唯一的一个被称作“第一个”的数据元素②存在唯一的一个被称作“最后一个”的数据元素③除第一个之外，结构中的每一个数据元素均只有一个前驱④除最后一个之外，结构中的每一个数据元素均只有一个后继6、在长度为n的顺序表中的第i个位置处插入一个元素，需要移动多少个元素？n-i+17、理解算法：线性表La和Lb，将两个表合并成一个新的线性表并存于La中。

8、带头结点的单链表和不带头结点的单链表为空的条件分别是？带头结点的循环单链表为空的条件是？带头结点的单链表为空的条件：没有下一个节点L->next=NULL不带头结点的单链表为空的条件：L=NULL循环单链表为空的条件：head->next=head带头结点的循环单链表为空的条件是9、在单链表中插入结点的算法中，指针如何修改。

P3410、理解单链表中插入新结点的算法p3411、理解双向链表中插入新结点的算法p4012、理解栈和队列的操作特点：先进后出，先进先出。

已知进栈顺序，求可能的出栈顺序。

链栈相对于顺序栈的优点是什么?链栈在入栈前不需要判断栈是否为满，只需要为入栈元素动态分配一个节点空间13、理解算法：执行进栈操作，则先要判断栈S是否为满，若不满再将记录栈顶的下标变量top加1，再将进栈元素放进栈顶位置上。

算法与数据结构期中复习

算法与数据结构期中复习
答：如果i<j，则对于pi<pj情况，说明pi在pj入 栈前先出栈。而对于pi>pj的情况，则说明 要将pj压到pi之上，也就是在pj出栈之后pi才 能出栈。这就说明，对于i<j<k，不可能出 现pj<pk<pi的输出序列。
• 试证明:同一棵二叉树的所有叶子结点，在 先序序列、中序序列以及后序序列中都按 相同的相对位置出现（即先后顺序相同）， 例如先序abc,后序bca 中序bac。
试推导求解 n 阶hanoi塔问题至少要执行的移动操作 move 次数。
答：钢设针HXn移为到n个钢盘针子Z，的可Ha借n助oi塔钢的针移Y)动次数。(假定n个盘子从 则移到HZn，=2再H将n-1那+1n-/1/先个将移n到-1Z个盘子从X移到Y，第n个盘子 =2（2Hn-2+1）+1 =22 Hn-2+2+1 =22（2Hn-3+1）+2+1 =23 Hn-3+22+2+1 ·
请在下列算法的横线上填入适当的语句。
typedef struct node {int data; struct node *next; }linknode,*link;
bool inclusion(link ha,link hb) /*以ha和hb为头指针的带头节点单链表分别表示递增有序表A和B，本算法判别表A是否包
赋值语句A[i]执行了一次；最坏情况出现在二进制数各位均为1（最高位为零，因题目 假设无溢出），这时判断n次，循环体执行了n-1次，时间复杂度是O(n)， 平均情况：应该考虑从最低位其连续1的个数。
***0->2(n-1) 循环体判断条件执行1次 **01 -> 2(n-2)循环体判断条件执行2次 **011->2(n-3)循环体判断条件执行3次 **01..1(i个1)- 2(n-i-1)循环体判断条件执行i次 1..1(n个1)->1循环体判断条件执行n次 平均情况时间复杂度为0(n)

数据结构与算法复习题

数据结构与算法复习题

《数据结构与算法》一、选择题1. 组成数据的基本单位是( )。

(A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量2. 线性表的链接实现有利于( )运算。

(A) 插入 (B)读表元 (C)查找 (D)定位3. 串的逻辑结构与( )的逻辑结构不同。

(A) 线性表 (B)栈 (C)队列 (D)树4. 二叉树第i（i≥1）层最多有( )个结点。

(A) 2i (B)2i (C) 2i-1 (D) 2i-15. 设单链表中指针p指向结点A，若要删除A后结点（若存在），则需要修改指针的操作为( )(A) p->next = p->next->next (B)p=p->next(C)p=p->next->next (D)p->next=p6、栈和队列的共同特点是( )。

(A)只允许在端点处插入和删除元素 (B)都是先进后出(C)都是先进先出 (D)没有共同点7、二叉树的第k层的结点数最多为( ).(A)2k+1 (B)2K+1 (C)2K-1(D) 2k-18、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA9、设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-110、下面程序的时间复杂为（）for（i=1,s=0; i<=n; i++）{t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(n3)11、设某强连通图中有n个顶点，则该强连通图中至少有（）条边。

(A) n(n-1) (B) n+1 (C) n (D) n(n+1)12、设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。

数据结构与算法知识点必备

数据结构与算法知识点必备

数据结构与算法知识点必备一、数据结构概述数据结构是计算机存储、组织数据的方式，是计算机科学中的重要基础。

它关注如何将数据以及与数据相关的操作组织起来，以便高效地访问和修改数据。

常见的数据结构有：数组、链表、栈、队列、树、图等。

二、数组数组是一种线性数据结构，用于存储相同类型的数据。

它通过索引来访问元素，具有随机访问的特点。

常见的数组操作有：插入、删除、查找、排序等。

三、链表链表是一种动态数据结构，由节点组成，每一个节点包含数据和指向下一个节点的指针。

常见的链表有：单链表、双向链表、循环链表等。

链表的优点是插入和删除操作效率高，缺点是访问元素需要遍历。

四、栈栈是一种先进后出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。

栈的应用场景有：函数调用、表达式求值、括号匹配等。

五、队列队列是一种先进先出（FIFO）的数据结构，只允许在队尾插入元素，在队头删除元素。

队列的应用场景有：任务调度、缓存管理等。

六、树树是一种非线性数据结构，由节点和边组成，每一个节点可以有多个子节点。

常见的树有：二叉树、二叉搜索树、平衡二叉树、堆、哈夫曼树等。

树的应用场景有：文件系统、数据库索引、路由算法等。

七、图图是一种非线性数据结构，由节点和边组成，每一个节点可以与其他节点之间建立连接。

常见的图有：有向图、无向图、带权图等。

图的应用场景有：社交网络、地图导航、网络拓扑等。

八、算法算法是解决问题的步骤和方法。

良好的算法应具备正确性、可读性、茁壮性和高效性。

常见的算法有：排序算法、搜索算法、动态规划、贪心算法等。

九、排序算法排序算法是将一组数据按照特定顺序重新罗列的算法。

常见的排序算法有：冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。

不同排序算法的时间复杂度和空间复杂度不同，选择合适的排序算法取决于具体问题的要求。

十、搜索算法搜索算法是在给定数据集中查找特定元素的算法。

常见的搜索算法有：线性搜索、二分搜索、广度优先搜索、深度优先搜索等。

数据结构复习资料复习提纲知识要点归纳

数据结构复习资料复习提纲知识要点归纳

数据结构复习资料复习提纲知识要点归纳数据结构复习资料：复习提纲知识要点归纳一、数据结构概述1. 数据结构的定义和作用2. 常见的数据结构类型3. 数据结构与算法的关系二、线性结构1. 数组的概念及其特点2. 链表的概念及其分类3. 栈的定义和基本操作4. 队列的定义和基本操作三、树结构1. 树的基本概念及定义2. 二叉树的性质和遍历方式3. 平衡二叉树的概念及应用4. 堆的定义和基本操作四、图结构1. 图的基本概念及表示方法2. 图的遍历算法：深度优先搜索和广度优先搜索3. 最短路径算法及其应用4. 最小生成树算法及其应用五、查找与排序1. 查找算法的分类及其特点2. 顺序查找和二分查找算法3. 哈希查找算法及其应用4. 常见的排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序六、高级数据结构1. 图的高级算法：拓扑排序和关键路径2. 并查集的定义和操作3. 线段树的概念及其应用4. Trie树的概念及其应用七、应用案例1. 使用数据结构解决实际问题的案例介绍2. 如何选择适合的数据结构和算法八、复杂度分析1. 时间复杂度和空间复杂度的定义2. 如何进行复杂度分析3. 常见算法的复杂度比较九、常见问题及解决方法1. 数据结构相关的常见问题解答2. 如何优化算法的性能十、总结与展望1. 数据结构学习的重要性和难点2. 对未来数据结构的发展趋势的展望以上是数据结构复习资料的复习提纲知识要点归纳。

希望能够帮助你进行复习和回顾，加深对数据结构的理解和掌握。

在学习过程中，要注重理论与实践相结合，多进行编程练习和实际应用，提高数据结构的实际运用能力。

祝你复习顺利，取得好成绩！。

数据结构与算法期末考试复习试题

数据结构与算法期末考试复习试题

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为 C 。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。

A．数据的存储结构 B．数据结构 C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。

A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。

A．数据的处理方法 B．数据元素的类型C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。

A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。

6．以下说法正确的是 D 。

A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。

（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是 O(n2) 。

s =0;for( I =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j]; sum = s ;9．下面程序段的时间复杂度是 O(n*m) 。

for( i =0; i<n; i++)for(j=0;j<m;j++)A[i][j] ＝ 0;10．下面程序段的时间复杂度是 O(log3n) 。

i ＝ 0；while（i<=n）i = i * 3；11．在以下的叙述中，正确的是 B 。

算法与数据结构需要掌握的知识点

算法与数据结构需要掌握的知识点算法与数据结构是计算机科学中非常重要的两个领域，它们是计算机程序设计的基础。

掌握算法与数据结构的知识，对于编写高效、可靠的程序至关重要。

下面将介绍一些算法与数据结构需要掌握的知识点。

一、算法1. 算法的概念：算法是解决问题的一系列步骤或指令的有限序列。

它具有输入、输出和确定性的特点。

2. 时间复杂度和空间复杂度：算法的时间复杂度是指执行算法所需要的时间，空间复杂度是指执行算法所需要的内存空间。

3. 常见的算法设计策略：分治法、贪心算法、动态规划、回溯法等。

4. 常见的算法：排序算法（如冒泡排序、插入排序、选择排序、快速排序、归并排序等）、查找算法（如二分查找、哈希查找等）、图算法（如深度优先搜索、广度优先搜索、最短路径算法等）等。

二、数据结构1. 数据结构的概念：数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括线性结构、树形结构、图形结构等。

2. 线性结构：包括数组、链表、栈、队列等。

数组是一种连续存储的线性结构，链表是一种离散存储的线性结构，栈和队列是特殊的线性结构。

3. 树形结构：包括二叉树、堆、哈夫曼树等。

二叉树是一种每个节点最多有两个子节点的树形结构，堆是一种特殊的二叉树，哈夫曼树是一种用于数据压缩的树形结构。

4. 图形结构：包括有向图和无向图。

有向图中的边有方向，无向图中的边没有方向。

5. 数据结构的存储方式：顺序存储和链式存储。

顺序存储是利用连续的存储单元存储数据，链式存储是利用指针将数据元素按照一定的逻辑关系连接起来。

三、算法与数据结构的应用1. 算法与数据结构在搜索引擎中的应用：搜索引擎需要使用数据结构来存储和索引大量的网页，使用算法来进行网页排序和相关性计算。

2. 算法与数据结构在图像处理中的应用：图像处理需要使用数据结构来表示图像，使用算法来进行图像的处理和分析。

3. 算法与数据结构在人工智能中的应用：人工智能需要使用数据结构来存储和处理大量的数据，使用算法来进行数据的分析和模型的训练。

数据结构复习题090612

《数据结构与算法》复习题一、选择题。

1．在数据结构中，从逻辑上可以把数据结构分为：线性结构和非线性结构。

2．数据结构在计算机内存中的表示是指：数据的存储结构。

3．在数据结构中，与所使用的计算机无关的是数据的：逻辑结构。

4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储：数据元素之间的关系。

5．在决定选取何种存储结构时，普通不考虑：各结点的值如何。

6．以下说法正确的选项是：一些外表上很不相同的数据可以有相同的逻辑结构。

7．算法分析的目的是：分析算法的效率以求改良，算法分析的两个主要方面是空间复杂度和时间复杂度。

11．在以下的表达中，正确的选项是二维数组是其：数据元素为线性表的线性表。

12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着：不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致。

13．链表不具备的特点是：可随机访问任一结点。

14．不带头结点的单链表 head 为空的判定条件是： head == NULL。

15．带头结点的单链表 head 为空的判定条件是： head->next ==NULL。

16．假设某表最常用的操作是在最后一个结点之后插入一个结点或者删除最后一个结点，那末采用：带头结点的双循环链表存储方式最节省运算时间。

17．需要分配较大空间，插入和删除不需要挪移元素的线性表，其存储结构是：静态链表。

18．非空的循环单链表 head 的尾结点〔由 p 所指向〕满足： p->next ==head。

20．如果最常用的操作是取第 i 个结点及其前驱，那末采用：顺序表存储方式最节省时间。

21．在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 O〔n〕。

22．在一个长度为 n〔n>1〕的单链表上，设有头和尾两个指针，执行：删除单链表中的最后一个元素操作与链表的长度有关。

23．与单链表相比，双链表的优点之一是：顺序访问相邻结点更灵便。

算法与数据结构重考复习题(0910)

10．具有10个顶点的无向图，边的总数最多为(45)。有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ 第
i列1的元素之和 ）。对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（ O(n2) ）。连通图
是指图中任意两个顶点之间（都连通的无向图 ）。一个有n个顶点的无向连通图，它所包含的连通分量个数最
保持青春的秘诀，是有一颗不安分的心。
算法与数据结构重考复习题（0910）
一、单选题（斜体为答案）
1．数据结构被形式地定义为（D,R），其中D 是
A. 算法 B. 操作的集合 C. 数据元素的集合 D. 数据关系的集合
2．顺序表是线性表的
A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构
5．已知栈的输入序列为1，2，3...．，n，输出序列为a1，a2，...，an，a2=n的输出序列共有（n-1）种输出序列。
队列的特性是先入先出，栈的特性是（后入先出）。如果以链栈为存储结构，则出栈操作时必须判别（栈空 )。与顺序栈相比，链栈有一个明显的优势是( 不易出现栈满 )。
6．循环队列采用数组data[1．．n]来存储元素的值，并用front和rear分别作为其头尾指针。为区分队列的满和空，约定：队中能够存放的元素个数最大为（n-l），也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是（front） ；入队时，可用语句（rear=rear+1%n）求出新元素在数组data中的下标。
（3）双向链表：q=p－>prior; temp=q－>data; q－>data=p－>data;p－>data=temp;
2．内存中一片连续空间（不妨设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任意一个栈，仅当这部分全满时才发生上溢。(为了尽量利用空间，减少溢出的可能，可采用栈顶相向，栈底分设两端的存储方式，这样，对任何一个栈，仅当整个空间全满时才会发生上溢。)

数据结构与算法考试

数据结构与算法考试（答案见尾页）一、选择题1. 什么是数据结构？请列举几种常见的数据结构。

A. 数组B. 链表C. 栈D. 队列E. 图2. 算法的时间复杂度是如何表示的？请简述其计算方式。

A. 用大O符号表示B. 用大O符号表示C. 用大O符号表示D. 用大O符号表示3. 什么是递归？请举例说明递归在算法中的实现。

A. 一个函数调用自身B. 一个函数调用自身的过程C. 一个函数调用自身的过程D. 一个函数调用自身的过程4. 什么是排序算法？请列举几种常见的排序算法，并简要描述它们的特点。

A. 冒泡排序B. 选择排序C. 插入排序D. 快速排序E. 归并排序5. 什么是哈希表？请简述哈希表的原理和优点。

A. 一种数据结构，它通过将键映射到数组索引来存储和检索数据B. 一种数据结构，它通过将键映射到数组索引来存储和检索数据C. 一种数据结构，它通过将键映射到数组索引来存储和检索数据D. 一种数据结构，它通过将键映射到数组索引来存储和检索数据6. 什么是树形结构？请列举几种常见的树形结构，并简要描述它们的特点。

A. 二叉树B. 二叉树C. B树D. B+树E. 无7. 什么是图数据结构？请列举几种常见的图算法，并简要描述它们的特点。

A. 广度优先搜索B. 深度优先搜索C. 最短路径算法（Dijkstra算法）D. 最长路径算法（Floyd算法）E. 最小生成树算法（Kruskal算法，Prim算法）8. 什么是动态规划？请简述动态规划的基本思想和应用场景。

A. 一种通过分解问题为更小的子问题来求解的方法B. 一种通过分解问题为更小的子问题来求解的方法C. 一种通过分解问题为更小的子问题来求解的方法D. 一种通过分解问题为更小的子问题来求解的方法9. 请简述贪心算法的基本思想以及在哪些问题上可以应用贪心算法。

A. 一种通过局部最优解来达到全局最优解的策略B. 一种通过局部最优解来达到全局最优解的策略C. 一种通过局部最优解来达到全局最优解的策略D. 一种通过局部最优解来达到全局最优解的策略10. 什么是算法的时间复杂度和空间复杂度？请简述它们的含义以及如何计算它们。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

void intersection(list A, list B, list &C) { int ia,ib,ic,x,y; ia=ib=ic=1; while(ia<=A.length()&&ib<=B.length()) { A.get_element(ia,x); B.get_element(ib,y); if(x<y) ia++; else if(x>y) ib++; else { C.insert(ic,x); ia++;ib++; ic++;} } 时间性能：O(|A|+|B|) }
算法与数据结构复习
习题3.3：如果对循环队列采用设置运算标志的方式 来区分队列的满和空的状态，试给出对应的各运算实现。
在队列的类定义里加入一个标志位tag。
queue::queue( ) { count = 0; front = rear = 0; tag=0; } bool queue::empty( ) const { if ( front==rear&&tag==0) return true; else return false; } bool queue::full( )const { if ( front==rear&&tag==1) return true; else return false; }
void subtraction(list &A, list B) { int ia,ib,x,y; ia=ib=1; while(ia<=A.length()&&ib<=B.length()) { A.get_element(ia,x); B.get_element(ib,y); if(x<y) ia++; else if(x>y) ib++; else { A.delete_element(ia); ib++;} } 时间性能：O(|A|+|B|) }
void merge_list(list &A,list &B, list &C) { node *pa,*pb,*pc; node *u,*s; pa=A.get_head()->next; pb=B.get_head()->next; pc=C.get_head(); s=pc; while(pa!=NULL&&pb!=NULL) { if(pa->data<pb->data) { u=pa; s->next=u; s=u; pa=pa->next;} else if(pa->data>pb->data) { u=pb; s->next=u; s=u; pb=pb->next;} else { u=pa; s->next=u; s=u; pa=pa->next; pb=pb->next;} } if(pa!=NULL) {s->next=pa;} if(pb!=NULL) {s->next=pb;} }
习题2：假设递增有序顺序表A、B分别表示一个集合，设计 算法求解C=A∩B，并分析其时间性能。
• data[ia]<data[ib]: A当前元素不在B中，ia++ • data[ia]>data[ib]: A当前元素可能在B中，ib++ • data[ia]=data[ib]: 将该元素插入C表中 ia++,ib++,ic++
error_code queue::append(const elementtype x ){ node* s = new node; s -> data = x; s->next=rear->next; rear -> next = s; rear = s; count ++; return success; } error_code queue::serve(){ if ( empty() ) return underflow; node* front = rear -> next; node * u=front->next; front-> next = u -> next; delete u; count --; if ( front -> next == NULL ) rear = front; return success; }
链表练习2：递增有序链表集合求交、并、差子集，考虑时间复 杂度。
（1）C=AB • pa->data<pb->data : 将A中当前元素插入C表中, pa=pa->next
• pa->data==pb->data : 将A或B中的当前元素插入C表中, pa=pa->next, pb=pb->next • pa->data>pb->data：将B中当前元素插入C表中,pb=pb->next 如果pa!=NULL, 将A中剩余结点接到C表中， 如果pb!=NULL，将B中剩余结点接到C表中。
习题5.5：递增有序顺序表A、B分别表示一个集合，设计算法 求解A=A-B，并分析其时间性能。
• data[ia]<data[ib]: A当前元素不在B中，ia++ • data[ia]>data[ib]: A当前元素可能在B中，ib++ • data[ia]=data[ib]: 删除A当前元or_code queue::append(const elementtype x) { if ( full() ) return overflow; rear = ( rear + 1 ) % maxlen ; data[rear] = x; count ++; tag=1; return success; } error_code queue::serve() { if ( empty() ) return underflow; front = ( front + 1 ) % maxlen; count --; tag=0; return success; }
习题5-4：假设顺序表L中的元素按从小到大的次序排列，设计 算法以删除表中的重复的元素，并要求时间尽可能少。对顺序 表(1,1,2,2,2,3,4,5,5,5,6,6,7,7,8,8,8,9) 模拟执行本算法，统计 移动元素的次数。
void DeleteRepeat(list &L) { int i,j,x,y; if(L.length()==0||L.length()==1) {cout<<"不需删除"; return;} i=1; while(i<L.length()) { L.get_element(i,x); for(j=L.length();j>i;j--) { L.get_element(j, y); if(x==y) L.delete_element(j); } i++; } }
链表练习1： A表分成奇、偶两个子表A、B（A表做删除，B 表 做插入）
void split(list& A, list& B) { node *La, *Lb; node *p, *q, *u, *s; La=A.get_head(); Lb=B.get_head(); q=La; p=La->next; s=Lb; while(p!=NULL) { if(p->data%2==0) //偶数结点 { u=p; p=p->next; q->next=p; //结点从A表删除 s->next=u; s=s->next; //插入B表 } else { p=p->next; q=q->next; } //否则p,q后移 } }
习题4.2：如果采用带尾指针的单循环链表作为队列 的存储结构，设计算法以实现队列的各运算。 rear
队头元素 q1 q2 ... 队尾元素 qn
queue::queue( ){ rear = new node; rear -> next = rear; count = 0; } bool stack::empty( ) const { return rear->next==rear; } error_code queue::get_front(elementtype &x) const { if ( empty() ) return underflow; x = rear -> next->next -> data; return success; }
（2）C=A-B • pa->data<pb->data: A当前元素不在B中，将A中当前元素插入C表中，
pa=pa->next • pa->data<pb->data： A当前元素可能在B中，pb=pb->next • pa->data==pb->data: B当前元素在A中， pa=pa->next,pb=pb->next 如果pa!=NULL, 将A中剩余结点接到C表中。 void subtraction(list &A, list B, list &C) { node *pa,*pb,*pc; node *u,*s; pa=A.get_head()->next; pb=B.get_head()->next; pc=C.get_head(); s=pc; while(pa!=NULL&&pb!=NULL) { if(pa->data<pb->data) {u=pa; s->next=u; s=u; pa=pa->next;} else if(pa->data>pb->data) pb=pb->next; else { pa=pa->next; pb=pb->next;} } if(pa!=NULL) {s->next=pa;} }