“数据结构”专接本复习纲要(1).doc

“数据结构”专接本复习纲要 第一章 数据结构概论一、数据与信息1、什么是数据数据是对人类各种活动内容的详细记录。（只是事实的记录，没有特定的目的）2、什么是信息信息是指对某一特定目的而言，具有意义的事实与知识。（信息由数据处理而得）3、数据类型数据类型可以认为是对具有相同构造特征和操作特性的数据集合的一种抽象描述。对考试来说，重要的是了解和掌握C语言所提供的各种数据类型的使用。二、数据处理1、什么是数据处理数据处理是通过人力或机器，将收集到的数据加以系统的处理，归纳出有价值的信息。2、常用的数据处理方式(1) 编辑 （2）排序 （3）归并 （4）分配 （5）建档（6）更新 （7）计算 （8）链表 （9）查找 （10）查询（11）其它（如分类、摘要、变换等）三、程序和算法1、 程序产生的五个阶段（1）需求（了解、分析）（2）设计（算法）（3）分析（哪种方案最佳）（4）细化与编码（5）验证2、什么是算法、算法的描述、算法的时间复杂度算法是对解决所处理问题的方法和步骤的一种描述，是一个有限的指令序列。算法的描述方法可以是自然语言、形式化的图表（流程图、N-S图、PAD图等）、伪代码语言、程序设计语言等。算法的时间复杂度是指实现算法所需要花费的时间。3、影响程序执行时间的因素（1）程序所输入的数据量多少（2）程序所使用的算法（3）编译器所产生机器代码的优劣（4）指令在机器中的执行速度显然，（3）和（4）与所使用的具体机器和编译工具有关，而与算法本身的好坏没有直接的联系。所以，在分析算法的时间性能时，不考虑所使用的机器和编译器。4、算法时间复杂度的分析在程序中，算法的实现是通过一个个语句的执行来体现的。而影响语句执行所需要的时间由语句执行的次数和执行一次语句所需要的时间这两个因素确定的。语句执行的时间是以上两者的乘积。显然，语句执行一次的时间与具体使用的编译器和机器硬件有关。由于我们在分析算法的时间复杂度时，不考虑编译器和硬件的因素，所以，在分析算法的时间复杂度时，依据的是语句执行的次数，尤其是嵌套在最内层的基本语句。算法中语句执行的次数又往往是和所处理问题的规模有关，所谓算法的问题规模指的是输入的数据量。所以，算法的时间复杂度往往是算法问题规模的函数。例，求两个N阶方阵的乘积 C=A*B，算法如下：#define N 100 /* 假设N的值是100 */* 这里的N就是下列算法的问题规模 */void mat_mul(int ANN,int BNN,int CNN) int i,j,k; (1) for(i=0; iN; i+) N+1 (2) for(j=0; jN; j+) N(N+1) (3) Cij=0; N2 (4) for(k=0; kN; k+) N2(N+1) (5) Cij+=Aik*Bkj; N3 算法的时间复杂度 T(N)=2N3+3N2+2N+1 当N越来越大，趋向无穷大时，N的低次幂对T(N)的影响越来越小，而2N3和N3是同阶无穷大，所以，一般把时间复杂度写成 T(N)=O(N3)，即随着问题规模的增大，上述算法的时间复杂度按问题规模的立方函数来增长。常见的算法时间复杂度函数表示按时间性能从优到劣有O(1) O(log2N) O(N) O(Nlog2N) O(N2) O(2N) O(N!)练习，分析下列程序段的时间复杂度x=0;for(i=1; i=n; i+) for(j=1; j=i; j+) x+=2*i+3*j;四、数据结构概念1、什么是数据结构数据结构是相互之间存在一种或多种特定关系的数据元素的集合。（摘自严蔚敏著的数据结构）我们目前学习的数据结构涉及的是有限集合。这告诉我们，数据结构所研究的诸元素之间是存在一定的关系的。2、什么是数据的逻辑结构数据的逻辑结构指的是数据结构所研究的数据元素之间的逻辑关系，有时也叫数据结构的逻辑结构。数据的逻辑结构与具体的计算机无关。数据的逻辑结构可以分为线性结构和非线性结构两大类。线性结构体现了元素之间一个挨一个的次序关系。我们所学习的线性结构主要有线性表、栈、队列、一维数组等。我们所学习的非线性结构主要有树型结构、图（网）状结构。树型结构体现了元素之间一对多的层次关系。图（网）状结构体现了元素之间多对多的网状关系。3、什么是数据的物理结构（存储结构）数据的物理结构（又叫存储结构）是指数据结构在计算机中的表示。这里的表示可理解为存储的意思，而这个存储包含了两个方面的含义，一个是存储数据元素的值本身，另一个是这种存储要能体现数据元素之间的逻辑关系。顺序存储结构和链式存储结构是两种常见的存储结构。它们表示数据元素之间逻辑关系的方法是不同的。数据的存储结构是和具体的计算机有关的。4、数据结构研究什么简单地说，数据结构就是研究数据的逻辑结构和存储结构。同时，还研究对于用某种存储结构存储的具有某种逻辑结构的数据元素，如何设计效率（时间、空间）更高的算法。第二章 数组结构一、数组概念1、什么是数组数组是连续的、有限的（数目有限的）、有序的（数目有顺序性）同种元素的集合。2、数组的两个特性（1）数组中元素间的地址是连续的。（请与链表对比）（2）数组中所有元素的数据类型是相同的。（请与结构类型对比）二、数组中元素地址的计算1、一维数组中元素地址的计算假设有如下一维数组A，数组的首地址为a，每个元素占据的空间大小是d。（1）数组元素的下标从0开始 d0 1 2 3 i-1 i i+1 a 则下标是i的元素的地址是 L(Ai)=a+(i-0)*d 在Ai之前有A0 Ai-1共i个元素。（2）数组元素的下标从1开始 d1 2 3 4 i-1 i i+1 a 则下标是i的元素的地址是 L(Ai)=a+(i-1)*d 在Ai之前有A1 Ai-1共i-1个元素。（3）数组元素的下标从j开始 d j+0j+1j+2 j+3 i-1 i i+1 a 则下标是i的元素的地址是 L(Ai)=a+(i-j)*d 在Ai之前有Aj Ai-1共i-j个元素。可以这样来理解，从A0到Aj-1有j个元素，而从A0到Ai-1有i个元素，两者之差就是从Aj到Ai-1的元素个数。例，用C语言定义一个一维数组int A10; 若每个数组元素占用2个字节，数组A的起始地址是50，则A5的地址是 _ 。2、二维数组中元素地址的计算数组中的元素是存放在一片连续的存储空间中，所以二维数组中的元素也要“依次”放入空间中。二维数组中的元素放入连续存储空间中的“依次次序”有两种：“行优先（以行为主）”和“列优先（以列为主）”。所谓“行优先”的次序是指按行由小到大的次序先后依次把各行元素放入，同一行中按列由小到大的顺序存放。所谓“列优先”的次序是指按列由小到大的次序先后依次把各列元素放入，同一列中按行由小到大的顺序存放。假设有如下二维数组A，数组的首地址为a，每个元素占据的空间大小为d，二维数组有m行、n列。（1）以“行优先”次序存放，数组元素的下标从0，0开始 0 1 j-1 j n-10 * * * * *1 * * * * * i-1 * * * * *i * * * * * m-1 * * * * *则计算元素Aij的地址可以考虑如下在Aij之前已存入的整行有第0行到第i-1行共 （i-0） 行，每行的元素个数是n，则在Aij之前已存入的整行元素个数有(i-0)*n个。在Aij所在的i行中，在Aij之前已存入的元素个数有第0列到第j-1列共 (j-0) 个。所以，总的说来，按行优先的次序，在Aij之前已存入的元素个数有 (i-0)*n+(j-0) 个。而每个元素占d个字节，首地址是a。所以,元素Aij的地址是 L(Aij)=a+(i-0)*n+(j-0)*d（2）以“行优先”次序存放，数组元素的下标从1，1开始 L(Aij)=a+(i-1)*n+(j-1)*d 请自己推导（3）以“列优先”次序存放，数组元素的下标从0，0开始 0 1 j-1 j n-10 * * * * *1 * * * * * . i-1 * * * * *i * * * * * m-1 * * * * * L(Aij)=a+(j-0)*m+(i-0)*d 请自己推导（4）以“列优先”次序存放，数组元素的下标从1，1开始 L(Aij)=a+(j-1)*m+(i-1)*d 请自己推导练习，一个二维数组A1:3,1:5，每个数组元素用4个字节,数组的起始地址是1000，若以行优先次序排列，A3,1的地址是 _ ；若以列优先存储，A3,1的地址是 _ ；三、下三角矩阵和上三角矩阵1、什么是下三角矩阵和上三角矩阵下三角矩阵是指对角线上方（行下标小于列下标的元素）的元素都是0的正方矩阵。而上三角矩阵是指对角线下方（行下标大于列下标的元素）的元素都是0的正方矩阵。2、下三角矩阵和上三角矩阵的存储矩阵在计算机中可以用二维数组来表示。因为三角矩阵的对角线上方（下方）的元素为0，所以，在存储时，为了节省空间，0元素就不存了。这也是一种矩阵压缩存储的方式。和前面讨论的一般二维数组一样，存储三角矩阵时，也有“行优先”和“列优先”两种次序之分。3、下三角矩阵的元素地址计算设正方矩阵A的阶数为n。每个元素占d个字节空间。（1）“行优先”存储，元素下标从0，0开始 0 1 2 3 j 5 6 7 8 9 0 *1 * * i=7 j=42 * * *3 * * * *4 * * * * *5 * * * * * *6 * * * * * * *i * * * * * * * *8 * * * * * * * * *9 * * * * * * * * * *在元素Aij之前已存入的“整行”有从0行到i-1行共(i-0)行。元素个数是 1+2+3+i=i*(i+1)/2个在元素Aij所在之i行，在Aij之前已存入 从0列到j-1列共（j-0）个元素。所以，总的说，在元素Aij之前按“行优先”已存入元素i*(i+1)/2+（j-0）个若矩阵存储的首地址为a，则元素Aij的存储地址为 L(Aij)=a+( i*(i+1)/2+（j-0）)*d假设矩阵压缩存储在一维数组D中，则元素Aij在D中的“大排行”为第i*(i+1)/2+（j-0）+1个（设大排行编号从1开始）。若一维数组D的下标从0开始，则，元素Aij在D中的下标是i*(i+1)/2+（j-0）+1-1即存储在一维数组元素Di*(i+1)/2+（j-0）中。若一维数组D的下标从1开始，则，元素Aij在D中的下标是i*(i+1)/2+（j-0）+1即存储在一维数组元素Di*(i+1)/2+（j-0）+1中。（2）“行优先”存储，元素下标从1，1开始 1 2 3 j 5 6 7 8 9 10 1 *2 * * i=7 j=43 * * *4 * * * *5 * * * * *6 * * * * * *i * * * * * * *8 * * * * * * * *9 * * * * * * * * *10 * * * * * * * * * *在元素Aij之前已存入的“整行”有从1行到i-1行共(i-1)行。元素个数是 1+2+3+(i-1)=i*(i-1)/2个在元素Aij所在之i行，在Aij之前已存入 从1列到j-1列共（j-1）个元素。所以，总的说，在元素Aij之前按“行优先”已存入元素i*(i-1)/2+（j-1）个若矩阵存储的首地址为a，则元素Aij的存储地址为 L(Aij)=a+( i*(i-1)/2+（j-1）)*d假设矩阵压缩存储在一维数组D中，则元素Aij在D中的“大排行”为第i*(i-1)/2+（j-1）+1个（设大排行编号从1开始）。若一维数组D的下标从0开始，则，元素Aij在D中的下标是i*(i-1)/2+（j-1）+1-1即存储在一维数组元素Di*(i-1)/2+（j-1）中。若一维数组D的下标从1开始，则，元素Aij在D中的下标是i*(i-1)/2+（j-1）+1即存储在一维数组元素Di*(i-1)/2+（j-0）中。练习，设有一个矩阵为5X5的下三角矩阵A，将其压缩存储在一维数组D，该数组的大小为 _ ，a42所对应的DK的K值为 _ 。（3）“列优先”存储，元素下标从0，0开始 0 1 2 3 j 5 6 7 8 9 0 *1 * * i=7 j=42 * * *3 * * * *4 * * * * *5 * * * * * *6 * * * * * * *i * * * * * * * *8 * * * * * * * * *9 * * * * * * * * * *在元素Aij之前已存入的“整列”有从0列到j-1列共(j-0)列。元素个数是 n+(n-1)+(n-2)+(n-(j-1)=j*(2*n-j+1)/2个在元素Aij所在之j列，在Aij之前已存入 从j行到i-1行共（i-j）个元素。所以，总的说，在元素Aij之前按“列优先”已存入元素j*(2*n-j+1)/2+（i-j）个若矩阵存储的首地址为a，则元素Aij的存储地址为 L(Aij)=a+( j*(2*n-j+1)/2+（i-j）)*d假设矩阵压缩存储在一维数组D中，则元素Aij在D中的“大排行”为第j*(2*n-j+1)/2+（i-j）+1个（设大排行编号从1开始）。若一维数组D的下标从0开始，则，元素Aij在D中的下标是j*(2*n-j+1)/2+（i-j）+1-1即存储在一维数组元素Dj*(2*n-j+1)/2+（i-j）中。若一维数组D的下标从1开始，则，元素Aij在D中的下标是j*(2*n-j+1)/2+（i-j）+1即存储在一维数组元素Dj*(2*n-j+1)/2+（i-j）+1中。（4）“列优先”存储，元素下标从1，1开始 1 2 3 j 5 6 7 8 9 1 *2 * * i=7 j=43 * * *4 * * * *5 * * * * *6 * * * * * *i * * * * * * *8 * * * * * * * *9 * * * * * * * * *10 * * * * * * * * * *在元素Aij之前已存入的“整列”有从1列到j-1列共(j-1)列。元素个数是 n+(n-1)+(n-2)+(n-(j-1)+1)=(j-1)*(2*n-j+2)/2个在元素Aij所在之j列，在Aij之前已存入 从j行到i-1行共（i-j）个元素。所以，总的说，在元素Aij之前按“列优先”已存入元素(j-1)*(2*n-j+2)/2+（i-j）个若矩阵存储的首地址为a，则元素Aij的存储地址为 L(Aij)=a+( (j-1)*(2*n-j+2)/2+（i-j）)*d假设矩阵压缩存储在一维数组D中，则元素Aij在D中的“大排行”为第(j-1)*(2*n-j+2)/2+（i-j）+1个（设大排行编号从1开始）。若一维数组D的下标从0开始，则，元素Aij在D中的下标是(j-1)*(2*n-j+2)/2+1-1即存储在一维数组元素D(j-1)*(2*n-j+2)/2中。若一维数组D的下标从1开始，则，元素Aij在D中的下标是(j-1)*(2*n-j+2)/2+1即存储在一维数组元素D(j-1)*(2*n-j+2)/2+1中。4、上三角矩阵的元素地址计算请自己推导。四、稀疏矩阵1、什么是稀疏矩阵稀疏矩阵是指矩阵中绝大多数元素值为0的那种矩阵。2、稀疏矩阵的存储由于稀疏矩阵中绝大多数元素值为0，所以在存储时，为了节省空间，只存储非0值的元素。这就是稀疏矩阵的压缩存储。用“三元组表”来表示稀疏矩阵是常用的稀疏矩阵压缩存储的方式。矩阵中的非0元素用元素的行号、列号和元素值这三项数据来表示，把这三项数据组成一个结构，而矩阵中诸非0元素用这种结构组成的线性表来表示，三元组表的名称由此而来。例，对于如下稀疏矩阵10 0 0 0 0 0 0 20 0 0 40 0 0 0 30 0 0 0 0 0 0 0 0 0 0 0 0 50 0 0 0 0 50 0 0 70在C语言中用三元组表可表示如下 row col valuea0 6 6 7a1 1 1 10a2 2 2 -20a3 2 5 40a4 3 3 30a5 5 4 50a6 6 3 -60a7 6 6 70其中A0.row 是稀疏矩阵的行数 A0.col 是稀疏矩阵的列数 A0.value 是稀疏矩阵中非0元素的个数五、矩阵乘积算法设有矩阵AMK BKN，矩阵A乘以矩阵B的积为矩阵CMN。则Cij的值为A的i行和B的j列对应位置元素积的和。for(Cij=0,t=0; tK; t+) Cij+=Ait*Btj;六、多项式的表示多项式表示的要点是多项式中的一个项可以用该项的系数和该项的幂指数来表示。若多项式中的每一项（包括系数为0的项）都表示，则可以不必使用幂指数。例如，按升幂的次序把各项的系数（包括系数0）线性排列，则某系数的后继系数所表示的项的幂指数增1。例，P(x)=8x5+6x4+3x2+12P=(12,0,3,0,6,8) MAX=5对于多项式中很多项系数为0的情况，为节省空间，一般只存非0项，此时，该项的幂指数不可少。例，P(x)=8x100-6x4+12P=(3,100,8,4,-6,0,12) 其中4表示非0系数项的个数。至于用顺序表还是用链表（静态链表或动态链表），那是具体的存储结构问题，不同的存储结构在做多项式加法时的算法不同，但要点是一样的，即将幂指数相同的项的系数合并。第三章 链表一、链表概念1、什么是链表链表是一种存储结构，它把每个元素存储在链表的一个结点中，元素之间的逻辑关系通过设在结点中的指针域来表示。例如，对于线性表，结点的指针域记录该元素后继元素的地址。对于二叉树，结点的左指针域记录该结点左孩子的地址。2、静态链表和动态链表所谓静态链表是指链表结点的存储空间是通过预先定义数组的方式来获取的，而预先定义的数组的大小是固定的，在程序运行中不能改变，故称为静态链表。例，有线性表 P=(5,8,1,9,3) 则可以按静态链表存储如下 8 9 5 3 1 2 4 -1 1 0 0 1 2 3 4 这里，指针2等指示的是该元素前驱的位置（地址）。动态链表中结点的存储空间是在程序运行过程中通过动态申请空间的函数得到的。链表中各结点的存储空间在物理上不一定是连续的。例如，对于上述的线性表，可以按链表存储如下 5 8 1 9 3 在C语言中，用于动态申请空间的函数最常用的有malloc( ) ，释放空间的函数有 free( )。二、链表的建立1、链表的建立链表的建立本质上就是在链表为空的情况下，插入一个个结点。下面以不带头结点的单链表为例，说明链表建立的过程。typedef struct node /* 定义链表中结点的构造 */ int data; /* 结点的数据域 */ struct node *next; /* 结点的指针域 */ NODE; /* 结点类型的别名 */ head=NULL; /*设head是链表的头指针，准备一个空链表*/ rear=NULL;/* 准备链表的尾指针rear，其初值也是NULL*/ /* 因为准备通过在链表的尾部插入结点（尾插）来建立链表，所以准备了一个尾指针 */ printf(“请输入第一个结点的数据（=0) /* 当输入的数据不是结束标志，反复处理 */ p=(NODE *)malloc(sizeof(NODE); /* 为新结点申请空间，由指针变量p指示该结点 */ p-data=x; /* 在新结点中存入数据 */ /* 以下处理把新结点插入到链表的尾部 */ if(head=NULL) /* 若当前是空链表 */ head=p; /* 以新结点作为链表第一个结点 */ rear=p; /* 新结点也是链表当前最后一个结点 */ else /* 若新结点不是链表中插入的第一个结点 */ rear-next=p; /* 新结点的地址由链表最后一个结点来记录 */ rear=p; /* 把新结点作为链表当前新的最后一个结点*/ printf(“请输入下一个结点的数据（next=NULL;/*链表最后一个结点的指针域置空指针*/上述操作的示意图如下 head (head=NULL) rear (rear=NULL)p 5 head rear p 5 p-data=x; head=p; rear=p; head 5 p 9 rear head 5 9 rear-next=p; rear p head 5 9 rear=p; rear p以下是通过在链表的首部插入结点（头插）来建立链表head=NULL; /* 设head是链表的头指针，准备一个空链表*/printf(“请输入第一个结点的数据（=0) /* 当输入的数据不是结束标志，反复处理 */ p=(NODE *)malloc(sizeof(NODE); /* 为新结点申请空间，由指针变量p指示该结点 */ p-data=x; /* 在新结点中存入数据 */ /* 以下处理把新结点插入到链表的首部 */p-next=head; /* 由新结点来记录由头指针指示的链表第一个结点*/ head=p; /* 以新结点作为链表当前新的第一个结点 */ printf(“请输下一个结点的数据（next=head; head=p; head 5 p 9 p 9 5 p-next=head; head head 9 5 head=p; p 三、链表的基本遍历1、什么是链表的遍历所谓链表的遍历是指通过循环操作使指针变量获取链表中各个结点的地址，从而能对链表中各个结点进行所需要的处理。链表遍历操作的关键是如何从链表当前结点获取下一个结点的地址以及如何控制遍历循环的结束。例如，假设有以下链表：head a b c x y我们准备用指针变量p来指示链表中各个结点（也就是用p来记录链表中各结点的地址），在链表遍历中，通常把起这种作用的指针变量称为“扫描指针变量”（简称扫描指针）。2、遍历整个链表 /* 以下是扫描整个链表的遍历操作 */p=head; /* 扫描指针置初值为链表的第一个结点，即准备从链表的开头进行遍历 */while(p!=NULL) /* 当扫描指针尚未扫描完链表 */ /* 通过p处理p当前所指的结点 */p=p-next; /* 使p也指向p-next所指的结点 */* 因为p-next指示的当前p所指结点的下一个结点 */* 所以，此操作的含义是由p当前扫描的结点获取即将扫描的下一个结点的地址 */ m n m n p p=p-next; p 3、定位到链表尾指针的遍历 /* 以下是把扫描指针定位到链表尾结点的遍历操作 */p=head;while(p-next!=NULL) /* 当扫描指针所指结点的指针域值不为空，就反复扫描*/ /* 因为链表中只有最后一个结点（尾结点）的指针域是空*/ /* 所以，此判别条件的含义是若扫描指针尚未指向尾结点*/ /* 就循环扫描，而一旦扫描指针指向尾结点，就停止扫描*/ /* 所以，循环扫描结束时，扫描指针正好指向尾结点 */ p=p-next; 四、链表内结点的插入1、在链表中已知地址结点的右面插入（右插）假设有如下由头指针head指示的链表，指针变量p指示链表中某结点b，指针变量r指示即将插入的新结点d。现要把r所指示的结点插入到p所指示的结点的右面。head a b c r d pr-next=p-next; /* 将p所指结点的后继结点的地址交给新插入结点的指针域记录，也就是使p所指结点的后继结点也成为r所指结点的后继结点 ，示意图如下*/head a b c r d pp-next=r; /* 使r所指新插入的结点成为p所指结点的后继结点 */head a b c r d p2、在链表中已知地址结点的左面插入（左插）假设有如下由头指针head指示的链表，指针变量p指示链表中某结点b，指针变量r指示即将插入的新结点d。现要把r所指示的结点插入到p所指示的结点的左面。head a b c r d p分析：根据所插入的位置可以看到，链表中p所指示的结点指针域不需要作调整，倒是p所指示结点的前驱结点的指针域需要调整。在链表中，要操作哪个结点，必须有指针变量获取该结点的地址，通过该指针变量来处理。所以，左插操作的要点是找到p所指结点的前驱结点，把在p所指结点的左面插入转化为在p所指结点的前驱结点的右面插入。那么，如何能找到p所指结点的前驱结点呢？这可以通过遍历链表来实现，只不过要控制扫描指针循环到指向p所指结点的前驱结点时结束。为此，设一个扫描指针变量q，进行以下遍历操作q=head;while(q-next!=p) /* 请自己分析循环判别条件 */ q=q-next; 遍历完成后，问题就变成把r所指的结点插入到q所指结点的右面。请记住，单链表中的“左插”问题最终要化为“右插”来解决。如此，插入操作可如下进行：r-next=q-next; (此时，也可写成 r-next=p;) q-next=r; qhead a b c r d p3、在链表的尾部插入（尾插）通过遍历链表，使扫描指针定位在尾结点，插入操作就和普通的“右插”一样。3、在链表的首部插入（头插）这在链表建立时已做过。设链表的头指针是head，新插入结点由p指示，则操作如下：p-next=head;head=p;五、链表内结点的删除1、删除链表中已知地址结点的后继结点（右删）设有如下由头指针head指示的链表，现要删除p所指结点的后继结点。可操作如下：head a b c pt=p-next; /* 使指针变量t指向被删结点 */p-next=p-next-next; (此时也可写成 p-next=t-next;)/*把被删结点的后记结点的地址交给p所指的结点来记录，*/*这样，被删结点的后继结点就成p所指结点的后继结点 */ free(t);head a b c p若只是把结点从链表中摘除，并不删除它，则不做free操作。2、删除链表中已知地址结点本身设有如下由头指针head指示的链表，现要删除p所指结点本身。可操作如下：head a b c p分析：删除p所指结点后，链表中需要调整指针域的是p所指结点的前驱结点。所以，本删除操作的关键是如何找到p所指结点的前驱结点。同样，可以通过如下的遍历链表来实现。设扫描指针变量是q。q=head;while(q-next!=p) /* 请自己分析循环判别条件 */ q=q-next;如此一来，就变成删除q所指结点的后继结点操作了。q-next=p-next; (或 q-next=q-next-next;)free(p);head a b c q p3、删除链表中已知地址结点的前驱结点（左删）设有如下由头指针head指示的链表，现要删除p所指结点的前驱结点。可操作如下：head a b c p分析：同样，本操作的关键是获取被删结点的前驱结点的地址，从而可以调整该结点的指针域的值。为此，先进行如下链表遍历。设扫描指针变量是q。q=head;while(q-next-next!=p)/*请自己分析循环判别条件*/ q=q-next;t=q-next;q-next=q-next-next; (或 q-next=p; 或 q-next=t-next;)3、删除链表的尾结点（尾删）先通过链表遍历把扫描指针变量定位在尾结点的前驱结点，接下去的操作就和普通的“尾删”一样了。遍历链表的循环判别条件可设成 while(q-next-next!=NULL) 。4、删除链表中第一个结点（头删）此时，操作如下：t=head;head=head-next;free(t);head a b c d t head a b c d t 六、双链表内结点的插入、删除1、双链表中结点的定义设双链表的结点定义如下typedef struct dlist int data; /* 结点的数据域 */ struct dlist *front;/* 结点的左指针域 */ struct dlist *back; /* 结点的右指针域 */ DNODE;从结点定义可以看到，双链表的结点中设置了两个指针域，双链表的“双”字由此而来。结点中的左指针域front(相当于prior或left)指向该结点的前驱结点。结点中的右指针域back(相当于next或right)指向该结点的后继结点。显然，双链表中第一个结点的左指针域（front域）和最后一个结点的右指针域（back域）都为NULL。2、双链表中结点的插入设有如下示意的双链表的一部分，现要在p所指结点的左面（或右面）插入一个由指针变量r所指示的结点，操作如下： A B C p D r分析，为叙述方便，下面把结点成为A结点，B结点，从图上可以清楚地看到，当D结点插入到B结点的左面后，A结点的后继结点和B结点的前驱结点发生了变化，也就是说，A结点的右指针域和B结点的左指针域都要重新调整，当然，对D结点来说，插入到链表中后，D结点的左、右指针域也要填上相应的前驱结点和后继结点的地址。所以，总的来说，在双链表内部插入一个结点，需要调整4个指针域。操作如下，(1) r-back=p; (2) r-front=p-front;(3) p-front-back=r; (4) p-front=r; A B C (1) p D (2) r A B C (1) (3) p D (2) r A B C (1) (3) (4) p D (2) r思考，在B结点的右面插入怎么做？(3)、(4)步的顺序能互换吗？假如语句（4）就在第（3）步写了，该怎么办？3、双链表中结点的删除（1）删除指针变量所指结点本身 A B C p分析，从示意图可以看出，当p所指的B结点被删除后，对于B结点的前驱结点A结点来说，它的后继结点发生了变化，而对于B结点的后继结点C结点来说，它的前驱结点也发生了变化。所以，当B结点被删除后，链表中A结点的后继指针域(back)和C结点的前驱指针域(front)都要重新调整。所以，总的来说，在双链表内部删除一个结点，需要调整2个指针域。删除操作如下。（1）p-front-back=p-back;/* 被删结点的后继结点地址交给它的前驱结点来记录 */ （2）p-back-front=p-front;/* 被删结点的前驱结点地址交给它的后继结点来记录 */若不是仅从链表摘除，而是要删除结点，则再写 free(p); (1) A B C (2) p（2）删除指针变量所指结点的前驱结点 A B C q p分析，可以设一个指针变量q使其指向被删结点。操作如下