下载文档原格式
数据结构复习要点(整理版)数据结构复习要点(整理版)数据结构是计算机科学中非常重要的一门课程，它涉及到各种数据的存储和组织方式，对于编程和算法的理解都至关重要。
本文将整理常见的数据结构复习要点，帮助读者回顾和加深对数据结构的理解。
一、线性结构线性结构是最简单的数据结构之一，它包括线性表、栈、队列等。
线性表是具有相同数据类型的一组元素的有限序列，它可以分为顺序表和链表。
顺序表是一种用连续的存储单元依次存储线性表的元素的数据结构，而链表则是通过每个元素中存储下一个元素的地址来实现线性关系。
栈和队列是线性结构的特殊形式。
栈是一种先进后出（LIFO）的数据结构，它可以通过顺序栈或链栈来实现。
队列是一种先进先出（FIFO）的数据结构，它可以通过顺序队列或链队列来实现。
二、树形结构树形结构是一种非线性结构，它具有层次关系，由节点和边组成。
常见的树形结构包括二叉树、二叉搜索树、平衡二叉树和哈夫曼树。
二叉树是每个节点最多只有两个子节点的树，它可以是空树、只有一个根节点的树或者一个根节点连接两棵不相交的二叉树。
二叉搜索树是一种特殊的二叉树，它的左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节点的值。
平衡二叉树是一种特殊的二叉搜索树，它的左子树和右子树的高度差不超过1，这样可以保证在最坏情况下的查找效率。
哈夫曼树是一种特殊的二叉树，它的叶子节点代表字符，而各节点的权值表示字符出现的频率，通过构造哈夫曼树可以实现数据的压缩编码。
三、图形结构图形结构是一种包含节点和边的非线性数据结构，它由顶点集合和边集合组成。
图形结构可以分为无向图和有向图，每个节点可以有一个或多个相邻节点。
图形结构的常见算法有深度优先搜索（DFS）和广度优先搜索（BFS）。
深度优先搜索是一种通过递归或栈实现的搜索算法，它先访问起始节点的一个邻接节点，再依次访问该节点的未被访问过的邻接节点，直到所有节点都被访问过。
广度优先搜索则是一种通过队列实现的搜索算法，它先访问起始节点的所有邻接节点，再依次访问这些邻接节点的邻接节点，以此类推，直到所有节点都被访问过。
数据结构复习资料(亲自整理)1、链表是一种存储数据的链式结构，每个数据之间都是相关联的。
2、线性结构是一个有序数据元素的集合，包括线性表、栈、队列、双队列、数组和串。
3、树是由n（n>=1）个有限节点组成一个具有层次关系的集合，而二叉树是每个结点最多有两个子树的有序树。
二叉树与树的主要差别在于，二叉树结点的最大度数为2，而树中结点的最大度数没有限制；二叉树的结点有左、右之分，而树的结点无左、右之分。
4、堆是一种可以被看做一棵树的数组对象，总是满足某个节点的值总是不大于或不小于其父节点的值，且堆总是一棵完全二叉树。
5、二叉排序树是一种满足以下递归定义的二叉树：若左子树非空，则左子树所有节点的值均小于它的根节点；若右子树非空，则右子树所有节点的值均大于于它的根节点；左右子树也分别为二叉排序树。
1、在已知前序遍历和中序遍历的情况下，可以通过画树的方法求得后序遍历。
具体步骤如下：首先根据前序遍历的特点，确定根节点；然后观察中序遍历，将左子树和右子树分别确定下来；接着对左子树和右子树分别进行递归，直到遍历完所有节点，最后得到后序遍历。
2、树和二叉树之间可以相互转换。
将树转换为二叉树的方法是：对于每个节点，将其第一个孩子作为其左孩子，将其兄弟作为其右孩子。
将二叉树转换为树的方法是：对于每个节点，将其右孩子作为其兄弟。
3、二叉树线索化是将二叉树中的空指针指向该节点在中序遍历中的前驱或后继节点的过程。
在线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1.4、邻接表是图的一种链式存储结构，用于表示图中每个节点的邻居节点。
每个节点都有一个链表，存储着与该节点相邻的节点。
邻接表是一种图的存储结构，对于每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边（对于有向图是以该顶点为尾的弧）。
邻接表中的表结点和头结点分别表示边和顶点，包含信息如下：表结点adjvex（邻接点）。
nextarc（指向下一个表结点）（权值等信息）；头结点data（顶点信息）和firstarc（指向第一个表结点）。
数据结构复习题及答案5篇第一篇：数据结构复习题及答案、数据结构复习题及答案中南大学现代远程教育课程考试（专科）复习题及参考答案数据结构一、判断题：1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
（）2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。
（）3．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。
（）4．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。
（）5．如果两个串含有相同的字符，则这两个串相等。
（）6．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。
（）7．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
（）8．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。
（）9．一个广义表的表尾总是一个广义表。
（）10．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。
（）12．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
（）13．直接选择排序是一种稳定的排序方法。
（）14．闭散列法通常比开散列法时间效率更高。
（）15．有n个结点的不同的二叉树有n!棵。
（）16．直接选择排序是一种不稳定的排序方法。
（）17．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。
（）18．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。
（）19．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。
（）20．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。
数据结构复习资料复习提纲知识要点归纳数据结构复习资料：复习提纲知识要点归纳一、数据结构概述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. 对未来数据结构的发展趋势的展望以上是数据结构复习资料的复习提纲知识要点归纳。
希望能够帮助你进行复习和回顾，加深对数据结构的理解和掌握。
在学习过程中，要注重理论与实践相结合，多进行编程练习和实际应用，提高数据结构的实际运用能力。
祝你复习顺利，取得好成绩！。
（题）数据结构复习题Ch3链表一、选择题（共18题，11道算法设计题）1、设单链表中结点的结构为（data, link）。
已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（1） s->link = p->link； p->link = s；（3） p->link = s->link； s->link = p；Key：（2）2、设单链表中结点的结构为（data, link）。
已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？（1） s->link = p；p->link = s；（2） s->link = p->link；p->link = s；（4） p->link = s；s->link = p；（2） q->link = s； s->link = p；（4） p->link = s； s->link = q；（3） s->link = p->link； p = s；Key：（2）3、设单链表中结点的结构为（data, link）。
若想摘除结点*p的直接后继，则应执行下列哪一个操作？（2） p = p->link； p->link = p->link->link；（4） p = p->link->link；（1） p->link = p->link->link；（3） p->link = p->link；Key：（1）4、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。
若想删除链表第一个结点，则应执行下列哪一个操作？（1） s = rear； rear = rear->link； free（s）；（2） rear = rear->link；free（rear）；（3） rear = rear->link->link； free（rear）；（4） s = rear->link->link； rear->link->link = s->link； free（s）；1Key：（4）5、设双向循环链表中结点的结构为（data, prior, next），且不带表头结点。
数据结构（第4版）习题及实验参考答案数据结构复习资料完整版（c语言版）数据结构基础及深入及考试习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。
即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。
它依赖于计算机。
存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。
它由基本的数据类型构成，并包括一组相关的服务（或称操作）。
它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。
4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。
5、在数据结构中，从逻辑上可以把数据结构分成（C）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（A）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。
2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（E），删除一个元素需要移动的元素的个数为（A）。
A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。
”这个结论是（B）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（D）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（B）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（A）A、head==NULLB、head->ne某t==NULLC、head->ne某t=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（C）A、p->ne某t==NULLB、p==NULLC、p->ne某t==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)数据结构(第4版）习题及实验参考答案9、在一个单链表中，若删除p所指结点的后继结点，则执行（A）A、p->ne某t=p->ne某t->ne某t;B、p=p->ne某t;p->ne某t=p->ne某t->ne某t;C、p->ne某t=p->ne某t;D、p=p->ne某t->ne某t;10、在一个单链表中，若在p所指结点之后插入所指结点，则执行（B）A、->ne某t=p;p->ne某t=;B、->ne某t=p->ne某t;p->ne某t=;C、->ne某t=p->ne某t;p=;D、p->ne某t=;->ne某t=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点，则执行（C）A、->ne某t=p->ne某t;p->ne某t=;B、p->ne某t=->ne某t;->ne某t=p;C、q->ne某t=;->ne某t=p;D、p->ne某t=;->ne某t=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有1个前趋结点。
数据结构复习资料数据结构复习资料数据结构是计算机科学中非常重要的一个领域，它研究的是数据的组织、存储和管理方式。
掌握数据结构的基本概念和常用算法，对于提高程序的效率和性能至关重要。
在这篇文章中，我将为大家提供一些数据结构的复习资料，希望对大家的学习有所帮助。
一、线性结构1. 数组(Array)数组是一种最基本的数据结构，它将一组相同类型的数据元素按照一定顺序存储在连续的内存空间中。
复习数组时，需要掌握数组的定义、初始化、访问和操作等基本操作。
2. 链表(Linked List)链表是一种常见的动态数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
复习链表时，需要了解单链表、双链表和循环链表的定义、插入、删除和遍历等操作。
3. 栈(Stack)栈是一种具有后进先出(LIFO)特性的数据结构，它只允许在栈顶进行插入和删除操作。
复习栈时，需要了解栈的定义、初始化、入栈、出栈和判空等基本操作。
4. 队列(Queue)队列是一种具有先进先出(FIFO)特性的数据结构，它只允许在队尾插入元素，在队头删除元素。
复习队列时，需要了解队列的定义、初始化、入队、出队和判空等基本操作。
二、非线性结构1. 树(Tree)树是一种具有分层结构的数据结构，它由一组节点组成，每个节点可以有零个或多个子节点。
复习树时，需要了解二叉树、平衡二叉树和二叉搜索树的定义、插入、删除和遍历等操作。
2. 图(Graph)图是一种由节点和边组成的数据结构，它用于表示多对多的关系。
复习图时，需要了解图的定义、遍历、最短路径和最小生成树等算法。
三、排序算法排序算法是数据结构中非常重要的一部分，它用于将一组无序的数据按照一定的规则进行排列。
复习排序算法时，需要了解冒泡排序、插入排序、选择排序、快速排序、归并排序和堆排序等常见的排序算法，以及它们的时间复杂度和空间复杂度。
四、查找算法查找算法是数据结构中用于在一组数据中查找特定元素的算法。
数据结构复习资料一、数据结构的基本概念数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
它不仅要考虑数据元素的存储，还要关注数据元素之间的关系以及对这些数据的操作。
数据元素是数据的基本单位，例如整数、字符、字符串等。
而数据项则是数据元素的最小不可分割的部分。
常见的数据结构类型包括线性结构（如数组、链表、栈和队列）、树形结构（如二叉树、二叉搜索树、AVL 树等）、图形结构等。
二、线性结构1、数组数组是一组具有相同数据类型的元素的有序集合。
它的优点是可以通过下标快速访问元素，但插入和删除操作可能比较低效，因为需要移动大量元素。
2、链表链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
链表的插入和删除操作相对简单，但访问特定元素需要遍历链表。
3、栈栈是一种特殊的线性表，遵循后进先出（LIFO）原则。
入栈和出栈操作是栈的基本操作。
4、队列队列遵循先进先出（FIFO）原则，入队和出队操作是队列的主要操作。
三、树形结构1、二叉树二叉树是每个节点最多有两个子节点的树形结构。
它有满二叉树、完全二叉树等特殊形式。
2、二叉搜索树二叉搜索树的左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。
这使得查找、插入和删除操作的平均时间复杂度为 O(log n)。
3、 AVL 树AVL 树是一种自平衡的二叉搜索树，通过旋转操作保持树的平衡，从而保证查找、插入和删除的时间复杂度始终为 O(log n)。
四、图形结构图形由顶点和边组成，可以分为有向图和无向图。
常见的算法包括深度优先搜索和广度优先搜索，用于遍历图形。
五、数据结构的操作对于不同的数据结构，常见的操作包括创建、插入、删除、查找、遍历等。
1、插入操作根据数据结构的特点，选择合适的位置插入新元素。
2、删除操作准确找到要删除的元素，并处理删除后的结构调整。
3、查找操作利用数据结构的特性，提高查找效率。
4、遍历操作如前序遍历、中序遍历、后序遍历对于二叉树；深度优先遍历和广度优先遍历对于图形。
数据结构复习题及答案数据结构复习题及答案数据结构是计算机科学中的重要基础，它涉及到存储、组织和管理数据的方法和技术。
在学习数据结构的过程中，我们经常会遇到各种复习题，通过解答这些题目可以巩固对数据结构的理解和掌握。
本文将给出一些常见的数据结构复习题及其答案，希望对读者的学习有所帮助。
一、数组1. 给定一个整数数组，如何找到数组中的最大值和最小值？答案：可以使用遍历数组的方式，依次比较每个元素与当前的最大值和最小值，更新最大值和最小值即可。
2. 给定一个整数数组和一个目标值，如何判断数组中是否存在两个数的和等于目标值？答案：可以使用两层循环遍历数组，依次判断每两个数的和是否等于目标值。
二、链表1. 如何反转一个单链表？答案：可以使用三个指针prev、curr和next，分别表示当前节点的前一个节点、当前节点和当前节点的下一个节点。
通过遍历链表，每次将当前节点的next指针指向prev节点，然后更新prev、curr和next指针，直到遍历到链表的末尾。
2. 如何判断一个链表是否有环？答案：可以使用快慢指针的方法。
定义两个指针slow和fast，初始时都指向链表的头节点。
slow指针每次移动一步，fast指针每次移动两步。
如果链表中存在环，那么两个指针最终会相遇；如果链表中不存在环，那么fast指针会先到达链表的末尾。
三、栈和队列1. 如何使用栈实现队列？答案：可以使用两个栈来实现队列。
一个栈用来存储入队的元素，另一个栈用来存储出队的元素。
当需要入队时，直接将元素压入第一个栈；当需要出队时，如果第二个栈为空，则将第一个栈中的元素依次弹出并压入第二个栈，然后从第二个栈中弹出元素；如果第二个栈不为空，则直接从第二个栈中弹出元素。
2. 如何使用队列实现栈？答案：可以使用两个队列来实现栈。
一个队列用来存储元素，另一个队列用来辅助操作。
当需要入栈时，直接将元素入队；当需要出栈时，将队列中的元素依次出队并入辅助队列，直到队列中只剩下一个元素，然后将该元素出队；然后交换两个队列的角色，使得辅助队列成为主队列，主队列成为辅助队列。
实验一C语言数据类型的使用[实验目的]复习C语言的使用方法，特别是指针、结构体的内容，同时也为以后的各个实验做准备。
[实验内容及要求]1．建立一个简单链表（静态链表），它由3个学生数据的结点组成，每个结点包括学号和成绩。
输出各结点中的数据。
(根据题目完善程序)#define NULL 0struct student{long num；float score；struct student *next；} stu；typedef struct student stu;main (){ stu a,b,c,*head,*p；a.num=99101；a.score=89.5；b.num=99103；b.score=90；c.num=99107；c.score=85；head=&a；a.next=&b；b.next=&c；c.next=NULL；p=head；do{printf（“%ld%5.1f\n”, ）；/*输出学号和成绩*/p=p->next；}while( )；}输出：2．建立一个动态链表，它由3个学生数据的结点组成，每个结点包括学号和成绩。
输出各结点中的数据。
#define NULL 0#define LEN sizeof(struct student)struct student{long num；float score；struct student *next；}；int n；struct student *creat(void) /*尾插法建立链表*/{struct student *head；struct student *p1, *p2；n=0；p1=p2=(struct student *)malloc(sizeof(struct student))；scanf（“%ld,%f”,&p1->num,&p1->score)；head=NULL；while(p1->num!=0){n=n+1；if (n= =1)head=p1；else p2->next=p1；p2=p2->next ；p1=(struct student *)malloc(LEN)；scanf（“%ld,%f”,&p1->num,&p1->score)；}p2->next=NULL；return( head )；}void print（struct student *head）{struct student *p；printf（“\nNow,These %d records are：\n”,n)；p=head；if(head!=NULL)do{printf（“%ld%5.1f\n”,p->num,p->score)；}while(p!=NULL)；}main(){struct student *head；printf（“input records：\n”）；head=creat()；print(head)；}输入：输出：[思考题]1．将上题链表中学生的成绩从低到高排列输出，要求每行一个，包括学号和成绩。
2．设计一个可进行复数运算的演示程序。
要求：实现下列六种基本运算：1）由输入的实部和虚部生成一个复数；2）两个复数求和；3）两个复数求差；4）两个复数求积；5）从已知复数中分离出实部；6）从已知复数中分离出虚部。
运算结果以相应的复数或实数的表示形式显示。
3．设计一个可进行有理数运算的演示程序。
要求：实现两个有理数相加、相减、相乘以及求分子或求分母的运算(选做)。
[实验报告要求]打印或保存程序清单，分析和总结程序调试过程中获得的经验或不足，记录程序出错位置并分析原因。
[参考资料]1．《数据结构题集》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.122．《数据结构》（第二版）严蔚敏吴伟敏编著北京清华大学出版社1998.123．《C语言程序设计》（第二版）谭浩强编著北京清华大学出版社1999.12实验二线性表[实验目的]1.掌握数据结构中表的基本概念。
2．熟练掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在顺序存储结构和链接存储结构上的实现。
3.熟练掌握链表的各种操作和应用。
[实验内容及要求]顺序表的基本运算的算法：创建顺序表：输出顺序表；插入运算；删除运算；查找运算单链表的基本运算的算法：创建一个单链表；输出一个单链表；求单链表的长度；查找第I个结点；插入一个结点；删除一个结点；1.设有一个顺序表A，包含n个元素，要求写出一个将该表逆置的算法，并只允许在原表的存储空间外再增加一个附加的工作单元。
（根据题目完善程序）#include <stdio.h>#define MaxLen 50typedef int elemtype;typedef elemtype sqlist [MaxLen];int create (sqlist A){int i,n;printf("创建一个顺序表\n");printf("输入元素个数：");scanf("%d",&n);for (i=0;i<n;i++){printf("输入第%d个元素值：",i);scanf("%d",&n);}return n;}void invert(sqlist A,int n){int m=n/2,i;elemtype temp;for (i=0;i<m;i++){temp=A[i];A[i]=A[n-i-1];A[n-i-1]=temp; /*交换*/}}void disp(sqlist A,int n){int i;for(i=0;i<n;i++)printf("%d ",A[i]);printf("\n");}void main(){sqlist A;int n;n=create(A);disp(A,n);invert(A,n);disp(A,n);}创建一个顺序表输入元素个数： 5输入第1个元素值：2输入第2个元素值：6输入第3个元素值：3输入第4个元素值：1输入第5个元素值：8输出一个顺序表输出一个顺序表2.有一个单链表的第一个结点指针为head,编写一个函数将该单链表逆置,即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点。
在逆置中不能建立新的单链表（根据题目填空完善程序）#include <stdio.h>#include <malloc.h>#define NULL 0typedef int elemtype;typedef struct linknode{elemtype data;struct linknode *next;}nodetype;nodetype *create()elemtype d;nodetype *h,*s,*t;int i=1;h=NULL;printf("建立一个单链表\n");while (1){printf("输入第%d节点data域值:",i);scanf("%d",&d);if (d==0)break; /*以0表示输入结束跳出循环，如果return NULL,怎么生成头结点*/ if(i==1) /*建立第一个结点*/{h=(nodetype*)malloc(sizeof(nodetype));h->data=d;h->next=NULL;t=h;}else{s=(nodetype *)malloc(sizeof(nodetype));s->data=d;t->next=s;//注意应该没有s->next=NULL;t=s; /*t始终指向生成的单链表的最后一个结点*/}i++;}t->next=NULL;//加上这一条。
return h;}void disp(nodetype *h){nodetype *p=h;printf("输出一个单链表：\n");if (p==NULL) printf("空表");while (p!=NULL){printf("%d",p->data); p=p->next;printf("\n");getch();}int len(nodetype *h){int i=0;nodetype *p=h;while (p){i++;p=p->next;}return(i);}nodetype *invert(nodetype *h){nodetype *p,*q,*r;if (len(h)<=1){printf("逆置的单链表至少有2个节点\n"); return(NULL);}else{p=h;q=p->next;while (q!=NULL){r=q->next;q->next=p;p=q;q=r;}h->next=NULL;h=p;return h;}}void main()nodetype *head;head=create();disp(head);head=invert(head);disp(head);}建立一个单链表输入第1个节点data 域的值：1输入第2个节点data 域的值：2输入第3个节点data 域的值：3输入第4个节点data 域的值：4输入第5个节点data 域的值：5输入第6个节点data 域的值：0输出一个单链表：3.将两个非递减有序的单链表归并为一个非递减有序的单链表（根据题目填空完善程序）#include “stdio.h”#include “alloc.h”struct node{char data；struct node *next；} listnode；typedef struct node *link；void print(link head){struct node *p；printf（“\n”）；printf（“\n”）；p= head->next；while(p){printf（“%c”, p->data）；；}}link creat()/*头插法建立单链表*/{link head ,s；char ch；head = malloc(sizeof(listnode))；head->next =NULL；while(( ch= getchar())!=’\n’){s= malloc(sizeof(listnode))；s->data= ch；s->next = ；= s；}return head；}link merge(link a , link b){link p , q , s , c；c= malloc(sizeof(listnode))；c->next =NULL；p=a；q=b；while(p->next&&q->next){if (p->next->data<q->next->data){ s = p->next；p->next=s->next；} else{ s = q->next；q->next = s->next；} s->next = c->next；c->next = s；}while (p->next){s = p->next；p->next = s->next；s->next = c->next；c->next = s；}while(q->next){s = q->next；q->next = s->next；s->next = c->next；c->next = s；}free(p)；free(q)；return c；}main(){link a , b , c；a = creat()；b = creat()；print(a)；print(b)；c = merge ( )；print(c)；printf（“\n”）；}输入：ysplhdzyxrmhb输出[思考题]1．设计一个算法求A和B两个单链表表示的集合的交集。
