下载文档原格式
第1讲线性表本章主要掌握如下内容：线性表的定义和基本操作，线性表的实现,线性表的顺序存储结构及链式存储结构，线性表的应用。
知识点分析（一）线性表的定义和基本操作1．线性表基本概念1）定义：是由相同类型的结点组成的有限序列。
如：由n个结点组成的线性表（a1, a2, …, a n）a1是最前结点，a n是最后结点。
结点也称为数据元素或者记录。
2）线性表的长度：线性表中结点的个数称为其长度。
长度为0的线性表称为空表。
3）结点之间的关系：设线性表记为（a1,a2,…a i-1 , a i, a i+1 ,…a n），称a i-1是a i的直接前驱结点．．．．（简称前驱），a i+1是a i的直接后继结点．．．．（简称后继）。
4）线性表的性质：①线性表结点间的相对位置是固定．．的，结点间的关系由结点在表中的位置确定。
②如果两个线性表有相同的数据结点，但它们的结点顺序不一致，该两个线性表也是不相等的。
注意：线性表中结点的类型可以是任何数据（包括简单类型和复杂类型），即结点可以有多个成分，其中能唯一标识表元的成分称为关键字（key），或简称键。
以后的讨论都只考虑键，而忽略其它成分，这样有利于把握主要问题，便于理解。
『经典例题解析』线性表的特点是每个元素都有一个前驱和一个后继。
( )【答案】错误。
【解析】线性表的第一个数据元素没有前驱，最后一个元素没有后继。
其余的所有元素都有一个前驱和后继。
2．线性表的抽象数据类型线性表是一个相当灵活的数据结构，其长度可以根据需要增加或减少。
从操作上讲，用户不仅可以对线性表的数据元素进行访问操作，还可以进行插入、删除、定位等操作。
1）线性表的基本操作假设线性表L有数据对象 D＝{ai | ai∈ElemSet，i=1,2,3,…,n，n>=0},数据元素之间的关系R＝{<ai-1,ai>|ai-1,ai∈D,i=1,2,…,n},则线性表L的基本操作如下所示：●InitList(&L)：其作用是构造一个长度为0的线性表（空线性表）；●DestoryList(&L)：其作用是销毁当前的线性表L；●ClearList(&L)：清空线性表L，使之成为空表；●ListLength(L)：返回线性表L的长度，即线性表中数据元素的个数；●ListEmpty(L) ：判断线性表L是否为空表，是则返回True，否则返回False；●GetElem(L,i,&e)：将线性表L中第i个数据元素的值返回到变量e中；●LocateELem(L,e,compare( )) ：判断线性表L中是否存在与e满足compare（）条件的数据元素，有则返回第一个数据元素；●PriorElem(L,cur_e,&pri_e)：返回线性表L中数据元素cur_e的前驱结点；●NextElem(L,cur_e,&next_e)：返回线性表L中数据元素cur_e的后继结点；●ListInsert(&L,i,e)：向线性表L的第i个位置之前插入一个数据元素，其值为e；●ListDelete(&L,i,&e)：删除线性表L的第i个数据元素，并将该数据元素的值返回到e中；●ListTraverse(L,visit())：遍历线性表中的每个数据元素。
【数据结构】线性表的基本操作【数据结构】线性表的基本操作1：定义1.1 线性表的概念1.2 线性表的特点2：基本操作2.1 初始化操作2.1.1 空表的创建2.1.2 非空表的创建2.2 插入操作2.2.1 在指定位置插入元素2.2.2 在表头插入元素2.2.3 在表尾插入元素2.3 删除操作2.3.1 删除指定位置的元素2.3.2 删除表头的元素2.3.3 删除表尾的元素2.4 查找操作2.4.1 按值查找元素2.4.2 按位置查找元素2.5 修改操作2.5.1 修改指定位置的元素 2.5.2 修改指定值的元素3：综合操作3.1 反转线性表3.2 合并两个线性表3.3 排序线性表3.4 删除重复元素3.5 拆分线性表4：线性表的应用场景4.1 数组的应用4.2 链表的应用4.3 栈的应用4.4 队列的应用附件：无法律名词及注释：- 线性表：根据某种规则排列的一组元素的有限序列。
- 初始化操作：创建一个空的线性表，或者创建一个已经包含一定元素的线性表。
- 插入操作：在线性表的指定位置或者表头、表尾插入一个新元素。
- 删除操作：从线性表中删除掉指定位置或者表头、表尾的元素。
- 查找操作：在线性表中按照指定的元素值或者位置查找元素。
- 修改操作：更改线性表中指定位置或者值的元素。
- 反转线性表：将线性表中的元素顺序颠倒。
- 合并线性表：将两个线性表合并成一个新的线性表。
- 排序线性表：按照某种规则对线性表中的元素进行排序。
- 删除重复元素：将线性表中重复的元素删除，只保留一个。
- 拆分线性表：将一个线性表分成多个不重叠的子线性表。
数据结构(线性表)习题与答案数据结构(线性表)习题与答案1. 线性表的定义线性表是一种常用的数据结构，它由一系列元素组成，并且每个元素具有前驱和后继关系。
线性表可以通过顺序存储或链式存储来实现。
2. 线性表的实现方式2.1 顺序存储顺序存储是利用数组来实现线性表的一种方式。
数组的每个元素可以存储一个数据项，通过下标可以快速访问和操作其中的元素。
2.2 链式存储链式存储是通过节点之间的指针关联来实现线性表的一种方式。
每个节点包含数据域和指针域，指针域指向下一个节点。
3. 线性表的基本操作3.1 初始化线性表初始化线性表需要给表头节点分配内存空间，并将头节点的指针域置为空。
3.2 插入元素在线性表的某个位置插入元素，需要先找到插入位置的前一个节点，然后将新节点插入到该位置。
调整节点之间的指针关联即可完成插入操作。
3.3 删除元素删除线性表中的某个元素，需要找到待删除元素的前一个节点，然后将该节点的指针指向待删除节点的下一个节点，释放待删除节点的内存空间即可。
3.4 查找元素查找线性表中某个元素的位置，可以从表头节点开始逐个比较节点的数据域，直到找到目标元素或者遍历结束。
4. 线性表的习题与答案4.1 习题1已知线性表L中的元素按非递减顺序排列，设计一个算法，将元素x插入到L中，保持L的有序性。
解答：1) 从表头节点开始，顺序遍历节点的数据域，找到第一个大于等于x的节点的前一个节点，记为p。
2) 创建新的节点node，将x赋值给node的数据域。
3) 将node的指针域指向p的下一个节点。
4) 将p的指针域指向node。
5) 插入完成。
4.2 习题2已知线性表L中的元素按递减顺序排列，设计一个算法，删除L中所有大于x的元素。
解答：1) 从表头节点开始，顺序遍历节点的数据域，找到第一个小于等于x的节点的前一个节点，记为p。
2) 将p的指针域指向p的下一个节点，删除p的后继节点。
3) 重复执行步骤2，直到遍历结束。
数据结构实验报告线性表数据结构实验报告：线性表引言：数据结构是计算机科学中的重要概念，它涉及到如何组织和存储数据，以及如何有效地操作和管理这些数据。
线性表是数据结构中最基本的一种，它是一种有序的数据元素集合，其中的元素之间存在着一对一的关系。
一、线性表的定义和特点线性表是由n个数据元素组成的有限序列，其中n为表的长度。
这些数据元素可以是相同类型的，也可以是不同类型的。
线性表中的数据元素按照一定的顺序排列，并且每个数据元素都有唯一的前驱和后继。
线性表的特点有以下几个方面：1. 数据元素之间是一对一的关系，即每个数据元素只有一个直接前驱和一个直接后继。
2. 线性表中的元素是有序的，每个元素都有一个确定的位置。
3. 线性表的长度是有限的，它的长度可以是0，也可以是任意正整数。
二、线性表的实现方式线性表可以使用不同的数据结构来实现，常见的实现方式有数组和链表。
1. 数组实现线性表：数组是一种连续存储的数据结构，它可以用来存储线性表中的元素。
数组的优点是可以快速访问任意位置的元素，但是插入和删除操作需要移动其他元素，效率较低。
2. 链表实现线性表：链表是一种非连续存储的数据结构，它通过指针将线性表中的元素链接起来。
链表的优点是插入和删除操作简单高效，但是访问任意位置的元素需要遍历链表，效率较低。
三、线性表的基本操作线性表的基本操作包括插入、删除、查找和修改等。
1. 插入操作：插入操作用于向线性表中插入一个新元素。
具体步骤是先将插入位置后面的元素依次后移，然后将新元素插入到指定位置。
2. 删除操作：删除操作用于从线性表中删除一个元素。
具体步骤是先将删除位置后面的元素依次前移，然后将最后一个元素删除。
3. 查找操作：查找操作用于在线性表中查找指定元素。
具体步骤是从线性表的第一个元素开始逐个比较，直到找到匹配的元素或者到达线性表的末尾。
4. 修改操作：修改操作用于修改线性表中的某个元素的值。
具体步骤是先查找到要修改的元素，然后将其值更新为新值。
数据结构-线性结构非线性结构线性表数据结构线性结构非线性结构线性表在计算机科学的广袤领域中，数据结构就如同建筑的基石，为高效的算法和程序设计提供了坚实的基础。
而在众多的数据结构中，线性结构、非线性结构以及线性表无疑是最为基础和重要的组成部分。
让我们先来聊聊线性结构。
线性结构是一种数据元素之间存在着一对一关系的数据结构。
这就好比一列整齐排列的士兵，每个士兵都有其明确的前一个和后一个，顺序清晰，条理分明。
在这种结构中，数据元素按照特定的顺序依次排列，常见的线性结构包括数组、链表和栈等。
数组，是一块连续的内存空间，用于存储相同类型的元素。
它的优点是可以通过索引快速访问元素，时间复杂度为 O(1)。
但当需要插入或删除元素时，就可能需要移动大量的元素，效率较低。
想象一下在一个坐满人的电影院中，如果要在中间插入一个新的观众，那么后面的观众都得往后移动，这无疑是个麻烦的操作。
链表则与数组不同，它的元素在内存中并不一定连续存储。
每个元素由数据和指向下一个元素的指针组成。
链表在插入和删除元素时非常方便，只需修改指针即可，时间复杂度为 O(1)。
然而，要访问链表中的某个特定元素，就需要从链表的头部开始逐个遍历，时间复杂度为 O(n)。
栈是一种特殊的线性结构，它遵循着“后进先出”的原则。
就像一个只能从一端放入和取出物品的箱子，最后放进去的东西会最先被取出来。
栈在函数调用、表达式求值等场景中有着广泛的应用。
接下来，我们谈谈非线性结构。
与线性结构中一对一的关系不同，非线性结构中数据元素之间存在着一对多或者多对多的关系。
比如树和图。
树是一种分层的数据结构，就像一棵倒立的树，有一个根节点，然后从根节点向下延伸出多个分支。
二叉树是树结构中的一种常见形式，它的每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉搜索树则是一种特殊的二叉树，它的左子树中的节点值都小于根节点的值，右子树中的节点值都大于根节点的值。
这种特性使得在二叉搜索树中查找、插入和删除元素的效率较高。
数据结构实验线性表及其应用在计算机科学的领域中，数据结构是一门极其重要的基础学科，它为我们有效地组织和管理数据提供了理论和方法。
而线性表作为一种常见且基础的数据结构，在实际的程序设计和算法应用中有着广泛的应用。
线性表是一种最基本的数据结构，它是由零个或多个数据元素组成的有限序列。
在这个序列中，每个元素都有其特定的位置和值。
从存储结构上来看，线性表可以分为顺序存储和链式存储两种方式。
顺序存储的线性表，就像是一排紧密排列的格子，每个格子里存放着一个数据元素。
这种存储方式的优点是可以随机访问表中的任意元素，时间复杂度为 O(1)。
比如说，如果我们要获取顺序表中第 5 个元素的值，只需要通过简单的计算就能直接找到对应的位置并获取其值。
然而，顺序存储也有它的不足之处。
当需要插入或删除元素时，可能需要移动大量的元素，以保持数据的连续性，这会导致时间复杂度较高，为 O(n)。
相比之下，链式存储的线性表则更加灵活。
它就像是一串珍珠项链，每个珍珠（数据元素）通过一根线（指针）与下一个珍珠相连。
在链式存储中，插入和删除元素相对较为方便，只需要修改相关指针的指向即可，时间复杂度通常为 O(1)。
但是，由于无法直接通过计算得到某个元素的位置，所以随机访问的效率较低，时间复杂度为 O(n)。
在实际应用中，线性表有着多种多样的用途。
比如，我们可以用线性表来实现一个学生成绩管理系统。
将每个学生的成绩作为一个元素存储在线性表中，可以按照学号或者成绩进行排序。
当有新的学生成绩需要添加时，根据具体的存储方式选择合适的插入操作；当需要删除某个学生的成绩时，也能快速准确地进行删除。
再比如，在一个购物网站的商品列表中，也可以使用线性表来存储商品的信息。
用户可以按照价格、销量、评价等因素对商品进行排序和筛选。
而网站后台在处理商品的上下架、库存管理等操作时，也会频繁地对线性表进行插入、删除和修改等操作。
此外，在文本编辑软件中，我们输入的文字也可以看作是一个线性表。
什么是线性表线性表的结构线性表是最基本、最简单、也是最常用的一种数据结构。
那么你对线性表了解多少呢?以下是由店铺整理关于什么是线性表的内容，希望大家喜欢!线性表的简介线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的(注意，这句话只适用大部分线性表，而不是全部。
比如，循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储)，但是把最后一个数据元素的尾指针指向了首位结点)。
我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。
在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。
一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。
受限线性表主要包括栈和队列，受限表示对结点的操作受限制。
线性表的逻辑结构简单，便于实现和操作。
因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
线性表的结构线性表是一种常用的数据结构，以下介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。
在实际应用中，线性表都是以栈、队列、字符串等特殊线性表的形式来使用的。
由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。
线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。
一般地，一个线性表可以表示成一个线性序列：k1,k2,…,kn，其中k1是开始结点，kn是终端结点。
是一个数据元素的有序(次序)集线性结构的基本特征1、集合中必存在唯一的一个“第一元素”;2、集合中必存在唯一的一个“最后元素” ;3、除最后一个元素之外，均有唯一的后继(后件);4、除第一个元素之外，均有唯一的前驱(前件)。
数据结构---线性表线性表代码主要参考严蔚敏《数据结构（c语言版）》，有部分改动线性表的定义定义•线性表是具有相同的数据类型的n(n >= 0)个数据元素的有限序列，当n=0时线性表为一个空表•用L表示线性表则L = （a1,a2,a3,…,ano a1为表头元素，an为表尾元素o a1无直接前驱，an无直接后继特点•表中元素个数有限•表中元素具有逻辑上的顺序，表中元素有先后次序•表中元素都是数据元素•表中元素的数据类型都相同，每个元素占的空间大小一致要点数据项、数据元素、线性表的关系线性表由若干个数据元素组成，而数据元素又由若干个数据项组成，数据项是数据的不可分割的最小单位。
其中姓名，学号等就是数据项线性表的顺序表示顺序表的定义顺序表是指用一组地址连续的存储单元依次存储信息表中的数据元素，从而使得逻辑相邻的两个元素在物理位置上也相邻预先定义（为了代码可以运行）#define True 1#define False 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;第n个元素的内存地址表示为LOC(A) + (n-1)*sizeof(ElemType)假定线性表的元素类型为ElemType,则线性表的顺序存储类型描述为typedef int ElemType ;#define MaxSize 50typedef struct{ElemType data[MaxSize];int length;}SqList;一维数组可以是静态分配的，也可以是动态分配的。
静态分配后大小和空间都固定了，下面使用动态分配的形式typedef int ElemType ;#define InitSize 100 //表长度的初始大小定义#define ListIncreasement 10 //线性表存储空间的分配增量typedef struct{ElemType *data;int MaxSize,length;}SeqList;顺序表的初始化顺序表的初始化,&是C++的引用，可以使用指针代替Status InitList(SeqList &L){L.data = (ElemType *) malloc(InitSize * sizeof(ElemType));if(! L.data) exit(OVERFLOW);//存储分配失败L.length = 0;L.MaxSize = InitSize;return OK;}顺序表的插入在顺序表L的第i(1<= i <= L.length +1)个位置插入新元素e，需要将第n 个至第i (共n-i+1)个元素向后移动一个位置【最后一个到倒数第n-i+i个元素向后移动一位】。
Status ListInsert(SeqList &L,int i , ElemType e){ElemType * newbase;if(i<1|| i > L.length+1)//判断i是否合法return ERROR;if(L.length >= L.MaxSize){//当前存储空间已满，可直接返回falsenewbase =(ElemType *)realloc(L.data,(L.MaxSize+ListIncreasement)*sizeof(ElemType));if(!newbase){//存储分配失败exit(OVERFLOW);}L.data = newbase;//新基址L.MaxSize += ListIncreasement;}//移动元素for(int j = L.length; j>=i ;j--){L.data[j]= L.data[j-1];}L.data[i-1]= e;//插入eL.length++;//增加长度return OK;}最好情况：在表尾插入，时间复杂度为O(1)最坏情况：在表头插入，时间复杂度为O（n）平均情况：假设Pi(Pi=1/(n+1))是在第i个位置上插入一个节点的概率，则平均移动次数为∑ i = 1 n + 1 p i ( n − i + 1 ) = ∑ i = 1 n + 1 1 n + 1 ( n − i + 1 ) = 1 n + 1 n ( n + 1 ) 2 = n 2\sum_{i=1}^{n+1}p_i(n-i+1)=\sum_{i=1}^{n+1}\frac{1}{n+1}(n-i+1)=\frac{1}{n+1}\frac{n(n+1)}{2}=\fr ac{n}{2}i=1∑n+1pi(n−i+1)=i=1∑n+1n+11(n−i+1)=n+112n(n+1)=2n顺序表的删除删除顺序表L的第i(1< i <= L.length)个位置的元素，需要将第i+1个至第n(共n-1)个元素依次向前移动一个位置。
Status ListDelete(SeqList &L,int i , ElemType &e){if(i<1|| i>L.length) return ERROR;//判断删除位置是否合法e = L.data[i-1];//依次前移，把第i个元素覆盖，相当于是删除for(int j = i ; j < L.length ; j ++){L.data[j-1] = L.data[j];}L.length--;//长度减一return OK;}•最好情况：在表尾删除，时间复杂度为O(1)最坏情况：在表头删除，时间复杂度为O（n）平均情况：假设Pi(Pi=1/(n))是删除在第i个位置上一个节点的概率，则平均移动次数为∑ i = 1 n + 1 p i ( n − 1 ) = ∑ i = 1 n + 1 1 n ( n − i ) = 1 n n ( n − 1 ) 2 = n − 1 2\sum_{i=1}^{n+1}p_i(n-1)=\sum_{i=1}^{n+1}\frac{1}{n}(n-i)=\frac{1}{n}\frac{n(n-1)}{2}=\frac{n-1}{2 }i=1∑n+1pi(n−1)=i=1∑n+1n1(n−i)=n12n(n−1)=2n−1按值查找查找第一个与e相等的元素，并返回其位序。
int LocateElem(SeqList &L,ElemType e){for(int i =0; i < L.length; i++){if(L.data[i]== e){return i+1;//下标为i的元素值等于e,则位序为i+1}}return ERROR;//查找失败}平均情况：∑ i = 1 n + 1 p i × i = ∑ i = 1 n + 1 1 n × i = 1 n n ( n + 1 ) 2 = n + 1 2 \sum_{i=1}^{n+1}p_i\timesi=\sum_{i=1}^{n+1}\frac{1}{n}\times i=\frac{1}{n}\frac{n(n+1)}{2}=\frac{n+1}{2}i=1∑n+1pi×i=i=1∑n+1n1×i=n12n(n+1)=2n+1顺序表例题1、从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删除的元素的值，空出的位由最后一个元素来填补，若顺序表为空则显示出错误并退出运行。
bool ListMinElem(SeqList &L,ElemType &e){if(L.length<1){return false ;}int pos;e = L.data[0];for(int i =0; i < L.length ; i++){if(L.data[i]<e){e=L.data[i];//e就是存的最小值pos = i;}}L.data[pos]= L.data[L.length-1];//用最后一个元素的值填充最小元素的位置L.length--;//长度减一相当于删除了最后一个元素return true ;}2、设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O（1）void ListReverse(SeqList &L){ElemType temp;for(int i =0; i < L.length/2; i++){temp = L.data[i];//保存前面的元素L.data[i]= L.data[L.length -1-i];//和后面的元素交换L.data[L.length -1-i]= temp;}}3、对长度为n的顺序表L，编写一个时间复杂度为O(n),空间复杂度为O（1）的算法，该算法删除线性表中所有值为X的元素。
void ListDeleteX(SeqList &L , ElemType x){int k =0;//记录L不等于x的元素的个数for(int i =0; i < L.length; i++){if(L.data[i]!= x){L.data[k]= L.data[i];//将不等于x的元素向前移k++;//长度增加}}L.length = k;//将最后的不等于x的个数赋值给L.length}线性表的链式表示链表的定义用一组任意的存储单元存储线性表的数据元素（地址不连续），因为地址不连续，所以链表的数据结构中需要存放下一个节点的地址，所以通常一个结点有两个部分（数据域和指针域）一般形式一般需要一个头结点来访问整个链表，头结点的数据域一般不存数据。
typedef struct LNode{ElemType data;struct LNode *next;}LNode;链表的初始化Status InitLinkList(LinkList &L){L =(LinkList)malloc(sizeof(LNode));if(!L)exit(OVERFLOW);return OK;}链表的插入插入时先将要插入的节点P的指针域赋值为上一个节点S的指针域，P->next = S->next;S->next = P;Status ListInsert_L(LinkList &L,int i,ElemType e){//在第i个位置插入LinkList P = L;int j =0;while(P && j < i-1){P = P->next;//寻找到第i-1一个结点j++;}if(!P || j > i -1)return ERROR;//!P是判断是否超出表的长度， j > i -1 判断输入的位置是否小于1 LinkList S =(LinkList)malloc(sizeof(LNode));if(!S)exit(OVERFLOW);S->data = e;S->next = P->next;P->next = S;return OK;}链表的删除同插入一样，先找到第i-1个元素位置，然后用一个变量S保存要删除的节点，再将P的next指向P的next的next；然后用free(S)释放掉删除元素的空间Status ListDelete_L(LinkList &L,int i,ElemType &e){//删除第i个位置的元素LinkList p = L,q;int j =0;while(p->next && j < i-1){//p->next指向第一个元素，j处于第0个元素的位置，为了找到第 i - 1 个元素；p = p->next;j++;}if(!(p->next)|| j > i-1)return ERROR;//删除位置不合理q = p->next;p->next = q->next;e = q->data;free(q);return OK;}头插法建立单链表void CreateList_L(LinkList &L,int n){//n是个数L =(LinkList)malloc(sizeof(LNode));if(!L)exit(OVERFLOW);L->next =NULL;for(int i = n ; i >0; i--){LinkList p =(LinkList)malloc(sizeof(LNode));//创建新结点if(!p)exit(OVERFLOW);scanf("%d",&p->data);//获取值p->next = L->next;L->next = p;//新结点插入到表头}}尾插法Status ListInsertTail_L(LinkList &L,ElemType e){LinkList p = L;while(p->next !=NULL) p = p->next;//获取到最后一个节点LinkList newNode =(LinkList)malloc(sizeof(LNode));//创建新结点if(!newNode)exit(OVERFLOW);newNode->data = e;newNode->next =NULL;p->next = newNode;//插入到最后return OK;}链表的合并了解void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ //已知单链表La,Lb的元素按值非递减排列//归并La,Lb得到Lc也按值非递减排列LinkList pa,pb,pc;pa = La->next;pb = Lb->next;Lc = pc = La;while(pa&&pb){if(pa->data <= pb->data){pc->next = pa;pc = pa;pa = pa->next;}else{pc->next = pb; pc = pb; pb = pb->next;}pc->next = pa ? pa : pb;//插入剩下的片段}free(Lb);}双向链表在单链表的基础上增加了一个指向前一个节点的指针域。
