下载文档原格式
数据结构第二章课后答案数据结构第二章课后答案1. 线性表1.1 数组实现线性表Q1. 请说明线性表的定义，并结合数组实现线性表的特点进行解释。
线性表是由n(n≥0)个数据元素构成的有序序列，其中n表示线性表的长度。
数组实现线性表的特点是使用一组具有相同数据类型的连续存储空间存储线性表中的元素，通过下标访问和操作元素。
A1. 线性表的定义指出，线性表是由若干个数据元素组成的有序序列。
具体地，在数组实现线性表中，我们将元素存储在一组连续的内存空间中，通过下标访问和操作元素。
由于数组的存储空间具有连续性，这样的实现方式可以在O(1)的时间复杂度下进行元素的访问和修改操作。
1.2 链表实现线性表Q2. 请说明链表实现线性表的特点，并与数组实现进行比较。
链表实现线性表的特点是通过指针将线性表中的元素按照节点的形式连接起来，每个节点包含了存储的元素和指向下一个节点的指针。
与数组实现相比，链表的插入和删除操作更为高效，但是访问某个位置的元素需要从头开始遍历，时间复杂度较大。
A2. 链表实现线性表的特点是通过使用节点和指针将线性表中的元素连接起来。
每个节点中包含了一个存储的元素和指向下一个节点的指针。
链表的插入和删除操作的时间复杂度为O(1)，因为只需要改变指针的指向即可。
但是，访问某个位置的元素需要从头开始遍历链表，所以时间复杂度为O(n)。
2. 栈和队列2.1 栈的定义和基本操作Q3. 请给出栈的定义和基本操作。
栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作，该端称为栈顶。
栈的基本操作包括入栈(push)和出栈(pop)，分别用于将元素压入栈和将栈顶元素弹出。
A3. 栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作。
这个特定的一端称为栈顶，而另一端称为栈底。
栈的基本操作包括入栈(push)和出栈(pop)。
入栈操作将一个元素压入栈顶，出栈操作将栈顶元素弹出。
2.2 队列的定义和基本操作Q4. 请给出队列的定义和基本操作。
数据结构第二章参考答案1. 线性表线性表是数据结构中最基本的一种结构，在实际应用中广泛使用。
它是一个有序的数据元素序列，其中每个元素都有唯一的前驱和后继，除了第一个元素没有前驱，最后一个元素没有后继。
2. 顺序存储结构顺序存储结构是线性表最简单的一种实现方式。
它利用一段连续的存储空间依次存储线性表的元素，存储位置是连续的。
在顺序存储结构中，插入和删除操作需要移动大量元素，因此效率较低。
3. 链式存储结构链式存储结构通过指针将线性表的各个元素链接起来。
每个元素都包含一个数据域和一个指针域，数据域用于存储数据元素，指针域用于存储下一个元素的地址。
在链式存储结构中，插入和删除操作只需要修改指针，效率较高。
4. 栈栈是一种特殊的线性表，它只允许在表的一端进行插入和删除操作，这一端称为栈顶。
栈的特点是后进先出，即最后插入的元素最先被删除。
栈的应用场景包括函数调用、表达式求值等。
5. 队列队列也是一种特殊的线性表，它允许在表的一端（队尾）插入元素，在另一端（队首）删除元素。
队列的特点是先进先出，即最先插入的元素最先被删除。
队列的应用场景包括进程调度、打印队列等。
6. 递归递归是一种解决问题的方法，通过调用自身来解决规模较小的子问题。
在数据结构中，递归广泛应用于树和图的操作中。
递归需要注意递归的边界条件和递归的停止条件，以避免无限递归的问题。
7. 树树是一种非线性的数据结构，它由n个节点组成，这些节点通过边连接起来。
树的特点是每个节点最多有一个父节点，但可以有多个子节点。
树的应用场景包括文件系统、组织结构等。
8. 二叉树二叉树是一种特殊的树结构，每个节点最多有两个子节点。
二叉树的遍历有三种方式：前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。
二叉树的应用场景包括查找、排序等。
9. 查找算法查找算法是在数据集合中寻找特定元素的过程。
常用的查找算法有顺序查找、二分查找、哈希查找等。
不同的查找算法有不同的时间复杂度和空间复杂度，对于不同规模的数据集合有不同的效率。
数据结构c语言版耿国华课后习题答案数据结构是计算机科学中的一个重要领域，它涉及到数据的组织、管理和存储方式，以便可以高效地访问和修改数据。
C语言作为一种高级编程语言，提供了丰富的数据结构实现方法。
耿国华教授编写的《数据结构C语言版》一书，为学习者提供了深入理解和实践数据结构的机会。
以下是该书课后习题的一些参考答案。
# 第一章绪论1. 习题1：数据结构的定义是什么？- 参考答案：数据结构是计算机科学中用于组织、管理和存储数据的方式，以便可以高效地访问和修改数据。
2. 习题2：为什么需要学习数据结构？- 参考答案：学习数据结构有助于提高编程效率，优化算法性能，以及更好地解决实际问题。
# 第二章线性表1. 习题1：线性表的特点是什么？- 参考答案：线性表的特点是数据元素之间存在一对一的线性关系，可以顺序存储或链式存储。
2. 习题3：如何实现线性表的插入操作？- 参考答案：线性表的插入操作通常涉及找到插入位置，然后将新元素插入到该位置，并调整后续元素。
# 第三章栈和队列1. 习题1：栈的后进先出（LIFO）特性是什么？- 参考答案：栈的后进先出特性意味着最后插入的元素将是第一个被删除的元素。
2. 习题2：如何用C语言实现一个队列？- 参考答案：可以用数组或链表来实现队列。
队列的基本操作包括入队（enqueue）和出队（dequeue）。
# 第四章树和二叉树1. 习题1：二叉树的定义是什么？- 参考答案：二叉树是每个节点最多有两个子节点的树结构，通常分为左子节点和右子节点。
2. 习题3：二叉树的遍历方法有哪些？- 参考答案：二叉树的遍历方法包括前序遍历、中序遍历、后序遍历和层序遍历。
# 第五章图1. 习题1：图的基本概念有哪些？- 参考答案：图由顶点（节点）和边组成，可以表示对象之间的关系。
2. 习题2：图的存储方式有哪些？- 参考答案：图的存储方式主要有邻接矩阵和邻接表两种。
# 结语通过学习《数据结构C语言版》一书，读者可以掌握各种数据结构的基本概念、特性以及实现方法。
《数据结构》第2章线性表共55题一、单选1. (1)分题目ID号：10545 题目难度：容易在一个长度为n的顺序存储的线性表中，向第i个元素(1≤i≤i十1)位量插入一个新元素时，需要从后向前依次后移【1】个元素。
A. n—iB. n—i十1C. n一i一1 D. i题目答案：B2. (1)分题目ID号：10546 题目难度：容易线性表是【1】。
A. 一个有限序列，可以为空B. 一个有限序列，不能为空C. 一个无限序列，可以为空D. 一个无序序列，不能为空题目答案：A3. (1)分题目ID号：10548 题目难度：容易在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为【1】A. (n十1)／2B. n／2C. nD. n十l题目答案：C4. (1)分题目ID号：10549 题目难度：容易在一个顺序表的表尾插入一个元素的时间复杂度的量级为【1】A. ○(n)B. ○(1)C. ○(n*n)D. ○(lbn)题目答案：B5. (1)分题目ID号：10550 题目难度：容易单链表的存储密度为【1】A. 大于1B. 等于1C. 小于1D. 不能确定题目答案：C题目分析：存储密度=单链表数据项所占空间/结点所占空间结点所占空间由数据项所占空间和存放后继结点地址的链域，所以，存储密度小于1 。
6. (4)分题目ID号：10551 题目难度：难设单链表中指针p指向结点ai，指针q指着将要插入的新结点x，问：[1] 当x插在链表中两个数据元素ai和ai+1之间时，只要先修改【1】后修改【2】即可。
A.p一＞next＝qB.p一＞next＝p一>next->nextC.p->next=q->nextD.q一＞next＝p一＞nextE.q->next＝NULLF.q一＞next＝p[2] 在链表中最后一个结点an之后插入时，只要先修改【3】后修改【4】即可。
第２章1. 名词解释（1）线性表具有相同数据类型的n(n>=0)个数据元素的有限序列，排列方式为“一个接一个的排列”。
通常记为：(a1，a2，… a i-1，a i，a i+1，…a n)其中，n为表长，n=0时称为空表。
（2）顺序表用顺序存储方式存放的线性表叫顺序表，顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。
特点：①用物理上的相邻实现数据元素逻辑关系上的相邻；②可实现随机存取。
（3）线性单链表用链式存储方式存放的线性表叫链表。
链表是通过一组任意的存储单元来存储线性表中的数据元素，对每个数据元素a i，除了存放数据元素的自身的信息a i之外，还需要存放其后继a i+1 所在的存贮单元的地址，这两部分信息组成一个“结点”，存放数据元素信息的称为数据域data，存放其后继地址的称为指针域next。
因此n个元素的线性表通过每个结点的指针域联成了一个“链子”，称之为链表。
其中：线性、单向链结构的叫线性单链表；线性、双向链结构的叫线性双向链表；环形、单向链结构的叫单循环链表；环形、双向链结构的叫双循环链表。
（4）单循环链表在单链表的基础上，链表最后一个结点的指针域不为空，而是指向第一个结点，使得链表头尾结点相连，整个链表形成一个环。
单循环链表特点：从表中任何一个结点出发均可找到其它结点。
（单链表特点：要找链表中任何一个结点，必须从头结点开始遍历该结点以前的整个链表。
）2. 判断题（在各题后填写“√”或“×”）(1) 线性表若采用链式存储表示时所有存储结点之间的地址可连续可不连续( √ )(2) 链式存储在插入和删除时需要保持数据元素原来的物理顺序，不需要保持原来的逻辑顺序。
(×)(3) 链表中每个结点都是两个域。
(×)解析：单链表中每个结点都是两个域，双链表不是两个域。
(4) 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。
(×)(5) 顺序表可以按下标随机（或直接）访问，顺序表还可以从某一指定元素开始，向前或向后逐个元素顺序访问。
数据结构第2章习题参考答案1. 简答题1.1 什么是数据结构？数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括数据的逻辑结构和物理结构。
1.2 数据结构的分类有哪些？数据结构可以分为线性结构和非线性结构。
线性结构包括线性表、栈、队列和串；非线性结构包括树和图。
1.3 数据结构的逻辑结构有哪些？数据结构的逻辑结构包括线性结构、树形结构和图形结构。
1.4 数据结构的物理结构有哪些？数据结构的物理结构包括顺序存储结构和链式存储结构。
1.5 什么是算法？算法是指求解问题的具体步骤和方法。
1.6 算法的特性有哪些？算法应具有有穷性、确定性、可行性和输入输出性。
2. 选择题2.1 在栈的顺序存储结构中，栈的存储位置是：A. 自顶向下递增B. 自底向上递增C. 自底向上递减D. 自顶向下递减答案：D2.2 下列哪个数据结构不适合表示有父子关系的数据？A. 二叉树B. 图C. 链表D. 堆答案：D2.3 对于一棵完全二叉树，叶子节点的个数为n，则树中节点的总数为：A. 2nB. 2n + 1C. nD. n + 1答案：A2.4 假设有一个长度为10的栈，初始时栈为空，若对该栈连续执行5次入栈操作，然后执行4次出栈操作，最后执行1次入栈操作，则栈中剩余的元素个数为：A. 0B. 1C. 4D. 6答案：D3. 编程题3.1 实现一个栈数据结构的基本操作，包括入栈、出栈、获取栈顶元素和判断栈是否为空。
```Pythonclass Stack:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):if self.is_empty():return Nonereturn self.items.pop()def peek(self):if self.is_empty():return Nonereturn self.items[-1]```3.2 实现一个队列数据结构的基本操作，包括入队、出队、获取队首元素和判断队列是否为空。
第2章线性表一、选择题1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。
【＊＊，★】A. (N-1)/2B. NC. N+1D. N-1E. N/2F. (N+1)/2G. (N-2)/22.线性表是具有N 个（）的有限序列。
【＊】A、表元素B、字符C、数据元素D、数据项E、信息3.“线性表的逻辑顺序和物理顺序总是一致的。
”这个结论是（）。
【＊】A、正确的B、错误的C、不一定，与具体结构有关。
4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。
【＊，★】A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。
5.带头结点的单链表为空的判定条件是（）。
【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL6.不带头结点的单链表head 为空的判定条件是（）。
【＊】A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL7.非空的循环单链表head 的尾结点P 满足（）。
（注:带头结点）【＊】A、P->NEXT=NULLB、p=NULLC、p->next==headD、p==head8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。
【＊，★】A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9.在一个单链表中，若删除P 所指结点的后继结点，则执行（）。
【＊，★】A、p->next=p->next->nextB、p=p->next;p->next=p->next->nextC、p->next=p->next;D、p=p->next->next;10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（）。
数据结构第二章习题答案数据结构第二章习题答案第一题：给定一个数组arr，其中包含n个元素，要求编写一个函数，将数组中的所有元素按照奇偶性重新排列。
奇数元素排在偶数元素之前。
请给出实现代码。
解答：```pythondef rearrange(arr):n = len(arr)left = 0right = n - 1while left < right:while arr[left] % 2 != 0 and left < right:left += 1while arr[right] % 2 == 0 and left < right:right -= 1if left < right:arr[left], arr[right] = arr[right], arr[left]left += 1right -= 1return arr```第二题：给定一个字符串，判断其是否为回文串。
回文串是指正读和反读都相同的字符串。
要求不考虑大小写和非字母字符，只考虑字母字符。
解答：```pythondef is_palindrome(s):s = ''.join(filter(str.isalpha, s)).lower()return s == s[::-1]```第三题：给定一个链表，判断链表中是否存在环。
如果链表中存在环，则返回True，否则返回False。
解答：```pythonclass ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextdef has_cycle(head):slow = fast = headwhile fast and fast.next:slow = slow.nextfast = fast.next.nextif slow == fast:return Truereturn False```第四题：给定一个二叉树，判断其是否为平衡二叉树。
数据结构第二章课后答案数据结构第二章课后答案==========================================2.1 题目1：什么是线性表？线性表的特点有哪些？答案：线性表是由n个数据元素组成的有限序列，其中n为表的长度，线性表具有以下特点：1.除第一个元素外，每个元素均有一个直接前驱元素；2.除最后一个元素外，每个元素均有一个直接后继元素；3.线性表具有唯一的一个始元素和终元素。
2.2 题目2：什么是顺序存储结构？顺序存储结构有什么特点？答案：顺序存储结构是指用一组地质连续的存储单元依次存储线性表的数据元素，顺序存储结构具有以下特点：1.线性表的元素在计算机中是连续存储的，可以通过下标直接访问元素；2.插入和删除操作需要移动大量元素，效率较低；3.存储空间需要预先分配大小，固定不变。
2.3 题目3：什么是链式存储结构？链式存储结构有什么特点？答案：链式存储结构是指线性表的元素在计算机内存中非连续存储，而是通过每个元素中的指针起来的结构，链式存储结构具有以下特点：1.线性表的元素在内存中可以是非连续存储，节省存储空间；2.插入和删除操作只需要修改指针，效率较高；3.需要额外的指针域存储信息，增加了存储空间开销。
2.8 题目8：请解释迷宫问题的基本思路。
答案：迷宫问题的基本思路是使用回溯算法，即从某个位置开始进行深度优先搜索，逐步尝试各种可能的路径，直到找到一条通路或者遍历完所有可能的路径。
基本步骤如下：1.选择一个起始位置，并将其标记为已访问；2.检查当前位置的四周是否有未访问的相邻位置；3.如果有未访问的相邻位置，选择其中一个位置继续深度搜索；4.如果所有相邻位置都被访问过或者当前位置是死胡同，回溯到上一个位置；5.重复步骤2-4，直到找到通路或者遍历完所有路径。
附件：无法律名词及注释：1.版权：指对文字、图像、音乐等作品享有法律保护的权利，未经作者许可不得使用；2.知识产权：指人们创造的智力成果所享有的权益，包括专利权、商标权、著作权等；3.公平使用：指在特定情况下，可以在不获得版权所有人许可的情况下使用作品的一定范围。
数据结构第二章课后答案第二章课后答案2·1·理论问题1·什么是数据结构？答：数据结构是指在计算机中存储、组织和管理数据的方式。
它包括了数据的逻辑结构、存储结构和操作方法。
2·逻辑结构和存储结构的关系是什么？答：逻辑结构是指数据之间的逻辑关系，它是从逻辑上描述数据元素之间的关系。
存储结构是指数据在计算机内部的具体存储方式，它是从物理上描述数据元素在计算机内部的存储关系。
逻辑结构与存储结构之间是相互依赖的关系，逻辑结构决定存储结构，而存储结构又反过来影响逻辑结构。
3·请解释顺序存储结构和链式存储结构。
答：顺序存储结构是指将数据元素存储在一块连续的存储空间中，元素的物理地质是连续的。
链式存储结构是将数据元素存储在任意的存储单元中，通过指针相互连接。
4·什么是抽象数据类型(ADT)？答：抽象数据类型(ADT)是指一个数学模型以及定义在该模型上的一组操作。
它只关心数据对象的定义和操作，而不考虑其在计算机内部的表示和运算过程。
5·ADT的特点有哪些？答：（1）封装性：ADT将数据对象的定义和操作封装在一起，只对外界提供有限的操作接口。
（2）数据抽象：ADT关注数据的逻辑结构，而忽略了具体的存储结构和实现细节。
（3）信息隐藏：ADT将数据对象的内部细节隐藏起来，只通过接口暴露给外部使用者。
2·2·应用问题1·请举例描述数据结构的应用场景。
答：（1）栈：在程序设计中，栈常用于实现函数的调用和返回，追踪程序的执行过程。
（2）队列：在操作系统中，队列被广泛应用于任务调度，比如处理作业、进程管理等。
（3）二叉树：在搜索算法中，二叉树常用于实现快速查找、排序和最优化问题。
（4）图：在社交网络中，图被用来表示好友关系、消息传播等复杂的关系网络。
2·描述数组和链表的特点及其应用场景。
答：数组是一种顺序存储结构，它可以随机访问任何一个元素，但插入和删除元素的操作效率较低。
第二章习题与参考解答一单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( A ) 。
(A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。
2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。
插入一个元素时平均要移动表中的（A ）个元素。
(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( D ) 。
(A) 必须是连续的； (B) 部分地址必须是连续的；(C) 一定是不连续的； (D) 连续与否均可以。
4．用链表表示线性表的优点是（ C）。
(A)便于随机存取 (B)花费的存储空间较顺序存储少(C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用(D )存储方式最节省运算时间。
(A)单链表 (B)双链表(C)单循环链表 (D)带头结点的双循环链表6．下面关于线性表的叙述错误的是(B )。
(A)线性表采用顺序存储，必须占用一片地址连续的单元；(B)线性表采用顺序存储，便于进行插入和删除操作；(C)线性表采用链式存储，不必占用一片地址连续的单元；(D)线性表采用链式存储，不便于进行插入和删除操作；7．单链表中，增加一个头结点的目的是为了（C ）。
(A) 使单链表至少有一个结点 (B)标识表结点中首结点的位置（C）方便运算的实现 (D) 说明单链表是线性表的链式存储8．在一个单链表中p所指结点之后插入一个指针为s的结点，正确的操作是：（B）A. p->next =s;s->next= p->next;B. s->next= p->next;p->next =s;C. p->next =s; p->next=s->next;D. s->next= s->next;p->next =s;9．在双向链表存储结构中，删除p所指结点时，必须修改指针（A）A. (p->prior)->next =p->next;(p->next)->prior= p->prior;B. p->prior=(p->prior)->prior;(p->prior)->next= p;C. (p-> next)-> prior =p;p->rlink=(p->next)->next;D. p-> next=(p-> prior)->prior;p->prior=(p->next)->next;10．完成在双向链表结点p之后插入s的操作是（D）A. p->next =s;s->prior= p;p->next->prior=s;s->next=p->next;B. p->next->prior=s;p->next=s;s->prior=p;s->next=p->next;C. s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D. s->next=p;s->next=p->next;p->next->prior=s;(p->next)=s;11．若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（B ）。
(A) 单链表 (B) 顺序表(C) 双链表 (D) 单循环链表12．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D ）存储方式最节省运算时间。
(A) 单链表 (B) 仅有头指针的单循环链表(C) 双链表 (D) 仅有尾指针的单循环链表二判断题1．线性表的逻辑顺序与存储顺序总是一致的。
×2．顺序存储的线性表可以按序号随机存取。
∨3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
×4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。
∨5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
×6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
∨7．线性表的链式存储结构优于顺序存储结构。
×8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。
∨9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
∨10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
×11.静态链表既有顺序存储的优点，又有动态链表的优点。
所以它存取表中第i个的元素的时间与i无关。
×12.线性表的特点是每个元素都有一个前驱和一个后继。
×三算法设计题1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。
试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。
并且分析算法的时间复杂度。
Ⅰ、直接使用数组的写法：#define MAXSIZE 30#include "stdio.h"void inte(int a[],int m,int x){int i=m-1;while(i>=0&&x<a[i]){a[i+1]=a[i];i--;}a[i+1]=x;return(m+1);}由于只有一重循环，查找x最多次数为n 故时间复杂度为O(n) void main(){ int a[MAXSIZE],i,n,x;scanf("%d",&n);printf("\n");for(i=0;i<n;i++){ a[i]=3*i;printf("%d ",a[i]);}printf("\n");scanf("%d",&x);inte(a,n,x);printf("\n");for(i=0;i<n+1;i++)printf("%d ",a[i]);}Ⅱ。
使用线性表结构的程序：#include "stdio.h"#include "alloc.h"#define MAXSIZE 100typedef struct{int data[MAXSIZE];int last;}SeqList;SeqList *init_SeqList( ){ SeqList *L;L=malloc(sizeof(SeqList));L->last=-1; return L;}int Insert_SeqList(SeqList *L,int x) /*主要是这段函数的设计*/{int j;if (L->last==MAXSIZE-1){ printf("＂表满＂"); return(-1); } /*表空间已满，不能插入*/for(j=L->last;x<L->data[j]&&j>0;j--)L->data[j+1]=L->data[j]; /* 结点移动 */L->data[j+1]=x; /*新元素插入*/L->last++; /*last仍指向最后元素*/return (1); /*插入成功，返回*/}main(){int i,j,x;SeqList *L;L=init_SeqList();for(i=0;i<10;i++){x=2*i;Insert_SeqList(L,x);}printf("\n");for(i=0;i<=L->last;i++)printf("%d ",L->data[i]);printf("\ndelete No;\n");scanf("%d",&x);Insert_SeqList(L,x);printf("\n");for(i=0;i<=L->last;i++)printf("%d ",L->data[i]);}2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。
Ⅰ、直接使用数组的写法：#define MAXSIZE 30#include "stdio.h"int dele(int a[],int elenum){int i,j;i=j=0;while(j<elenum)if(a[i]==a[j])j++;elsea[++i]=a[j++];return(i+1);}void main(){ int a[MAXSIZE],i,n,x;scanf("%d",&n);printf("\n");for(i=0;i<n;i++){ a[i]=3*(i/2);printf("%d ",a[i]);}printf("\n");n=dele(a,n);printf("\n");for(i=0;i<n;i++)printf("%d ",a[i]);}Ⅱ。
使用线性表结构的程序：#include "stdio.h"#include "alloc.h"#define MAXSIZE 100typedef struct{int data[MAXSIZE];int last;} SeqList;SeqList *init_SeqList( ){ SeqList *L;L=malloc(sizeof(SeqList));L->last=-1; return L;}int Insert_SeqList(SeqList *L,int x) {int j;if (L->last==MAXSIZE-1){ printf("＂表满＂"); return(-1); } /*表空间已满，不能插入*/for(j=L->last;x<L->data[j]&&j>0;j--)L->data[j+1]=L->data[j]; /* 结点移动 */L->data[j+1]=x; /*新元素插入*/L->last++; /*last仍指向最后元素*/return (1); /*插入成功，返回*/}int dele(SeqList *L) /*这是本题的主要函数*/{int i,j; /*设置两个下标指针*/i=j=0;while(j<=L->last)if( L->data[i]==L->data[j])j++; /*如果相当，则只移动j指针*/elseL->data[++i]=L->data[j++]; /*否则，将j指针数据移动到i位置*/L->last=i;return(i);}main(){int i,j,x;SeqList *L;L=init_SeqList();for(i=0;i<20;i++){x=i/2;Insert_SeqList(L,x);}printf("\n");for(i=0;i<=L->last;i++)printf("%d ",L->data[i]);printf("\ndelete No;\n");dele(L);printf("\n");for(i=0;i<=L->last;i++)printf("%d ",L->data[i]);}3．编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。
