C语言链表详解ppt.ppt

1、第11章列表详细说明收藏版，2、例子：跳马。根据下图，将每个存储步骤后的位置(x，y)放入“节点”，然后使用“链”形成链。指针将两个节点连接在一起。根据上图，有7个节点。为了显示同时存在数据和指针的情况，引入了这种数据类型的结构。4，11.7用指针处理链表。链表是程序设计中一种重要的动态数据结构，是一种动态存储分配的结构。动态显示如下：链表中的元素数量可以根据需要增加和减少，而数组在声明后是固定的；元素的位置可以改变，也就是说，它可以从某个位置删除，然后插入到新的位置。链表中的元素称为“节点”，每个节点包括两个字段：数据字段和指针字段。2.单向链表通常由一个头部指针组成，用于指向链表的头部；3.单向链表有一个尾部节点，节点的指针部分指向一个空节点。Head1249135614751021，节点中的指针是存储下一个节点的地址，6，链表中节点的定义，链表是由节点组成的，关键是定义节点；链表的节点定义打破了使用前定义的限制，即可以自己定义。递归函数的定义也违反了使用前的定义。这是C语言程序设计中的两个特例。7.链表的基本操作。链表的基本操作是：(1)创建链表是指从零开始建立一个链表，即在一个空链表中依次插入若干个节点，并保持节点之间的前体和后继关系。(2)搜索操作是指根据给定的节点索引号或搜索条件来搜索节点。如果找到指定的节点，检索成功。否则，它被称为检索失败。(3)插入操作是指在节点ki-1和ki之间插入一个新的节点k ,使线性表的长度增加1，ki-1和ki之间的逻辑关系变化如下：在插入之前，ki-1是ki的前身，ki是ki-1的继承者；插入后，新插入的节点k成为ki-1的后继者和ki.8的前身，(4)删除操作是指删除节点ki以将线性表的长度减少1，ki-1、ki和ki-1之间的逻辑关系变化如下：在删除之前，ki是ki-1的前身和ki-1的后继者；缺失后，ki-1成为ki-1的前体，KI-1成为KI-1的后体。(5)打印输出，9。指针类型的成员可以指向其他类型的结构数据以及它自己的结构类型的数据。下一个是structstudent类型的成员，它也指向structstudent类型数据。换句话说：next存储下一个节点的地址，一个简单的链表10，11.7.2，# define null 0 struct student long num；浮动核心；structstudent * next；main()structstudenta，b，c，*head，* p；a.num=99101a .得分=89.5；b.num=99103b .得分=90；c.num=99107c .得分=85；Head=，例11.7，建立并输出一个简单的链表，每个节点都是在程序中定义的，它不是临时打开的，而且它总是占据内容。这个链表被称为“静态链表”。处理动态链表所需的11.11.7.3函数，C语言使用系统函数动态打开和释放存储单元，1.malloc函数，函数原型：void * malloc(unsigneditsize)；角色：在内存的动态存储区中分配一个连续的大小空间。返回值：是指向已分配域的起始地址的指针(基本类型void)。执行失败：空，返回12，函数原型： void * calloc(无符号n，无符号大小)；函数：在内存的动态区域中分配长度为N的连续空间。函数返回值：指向分配域起始地址的指针未能执行：返回null主要用途：为一维数组打开动态存储空间。n是数组元素的个数，每个元素的长度是大小，2.calloc函数，13，3.free函数。该功能的原型是无空隙的(空隙* p)；角色：释放第：页所指向的内存区域。这是最后一次调用calloc或malloc函数时返回的值。没有自由函数返回值的动态分配的存储单元必须在用完之后释放，否则由于应用空间太大导致资源不足，内存将会失效。，14，节点的动态分配，ANSIC的三个函数(头文件malloc.h) void * malloc(无符号intsize) void * calloc(无符号n，无符号的两个函数)voidfree(void*p)C新类型(初始值)delete指针变量/* 表示释放的数组，有或没有)*/使用new的优点：它可以直接按对象的大小分配，而不管对象的具体长度(p340例14.10)，15，11.7基本方法：三个节点(头节点、尾节点NULL和待插入节点p)第一步：定义头节点头、尾节点p2和待插入节点p1，初始化待插入节点的数据部分；步骤2:头节点和尾节点都指向这个节点。P1=p2=(struct student *)malloc(LEN)；表头指针部分为空，表头=空；步骤3:重复申请要插入的节点空间，为节点的数据部分赋值(或输入值)，并将节点插入到前面或后面(插入到书的尾部)。P2-下一个=P1；P2=P1；最后： P2-下一个=空；*head，*p1，*p2，使用malloc(LEN)，P2-下一个=空；16，11.7.4建立动态链表，头，p1p2，1。任务是打开节点并输入数据2。并建立前后相位链之间的关系。要插入的节点p1的数据部分被初始化。头节点和尾节点p2同时指向该节点。17.图11.14，负责人，P2，P1，负责人，P2，P1，(a)、(b)，P1反复申请要插入的节点空间，给节点的数据部分赋值(或输入值)，P2-下一个指向P1新打开的节点。18，图11.14，head，p1，p2，(c)，P2指向新节点p2=p1，19，图11.15，p2，p1，head，p2，P1，head，(a)，(b)，20，图11.16，p2，P1，head，p2，P1，head，21，示例11.8建立包含3个学生数据的单向动态链接表，# define null 0 # define elenzeof(structstudent)structstudent longnum；浮动核心；structstudent * next；intnstruct student * creat(void) struct student * head；structstudent*p1，*p2。n=0；P1=p2=(struct student *)malloc(LEN)；Scanf(，% f ，结构类型数据的长度，sizeof为“字节数运算符”，并定义了一个指针类型的函数。带回链表的起始地址，用LENgth len打开一个存储区，P1和p2是指向结构类型数据的指针变量，并强制转换成结构类型，假设头指向空节点，22，继续，而(p1-num！=0) n=n 1；/*n是节点数*/if(n=1)head=P1；else p2-next=P1；p2=p1P1=(struct student *)malloc(LEN)；Scanf(，% f ，/返回链表的头指针，算法：p1指向新打开的节点： P1=(student *)malloc(len)；p1指向的节点连接在p2指向的节点后面，并由p2-next=p1实现。P2指向链表中的最后一个节点，p2=p1，头部指针指向p1节点，P1在p2后面打开一个新的节点链，P1继续打开新节点，给新节点赋值，23，11.7.5输出链表，链表遍历1。单向链表总是从头节点开始；2.对于每个被访问的节点，当前指针被移动到该节点的下一个节点：p=p-next；3.直到下一个节点为空，P=NULL，24，图11.18，head，P，P，P，25，示例9，void print(struct student * head) struct student * P；printf( n注意，这些% drecordsare: n ，n)；p=head如果(头！=NULL)执行 printf(“% LD % 5 . lf n”，p-num，p-score)；p=p-下一个；同时(p！=空)；，26，11.7.6删除链表，删除节点原则：不改变原排列顺序，只从链表中分离，取消原链接关系。有两种情况：1。如果要删除的节点是头指针指向的节点，则直接操作；2.它不是一个头节点，所以一个一个往下看。此外，还应考虑：找不到空表和要删除的节点；27.删除链表中的节点时，需要两个临时指针：P1:判断被指向的节点是否是要删除的节点(用于搜索)；P2:总是指向P1的前一个节点；图11.19、(a)、(b)、29、图11.20、头、p1、(a)、(b)、头、P2、P1，原始链表P1指向头节点，p2指向P1指向的节点。P1指向一个节点。判断后，第一个节点是要删除的节点，头指向第二个节点，第一个节点被分离。P1找到要删除的节点后，它将被分离。，31，示例10，StructStudent * del(StructStudent * Head，Longnum) StructStudent * P1，* P2；if(head=NULL) printf( nlistnull！ n )；gotoend p1=头部；同时(num！=p1-num，找到，未找到，32，11.7.7向链表插入操作，插入节点：向现有链表插入一个节点插入原则：1、插入操作不应破坏原有的链接关系2、插入节点应在其位置实现方法：应该有一个插入位置搜索子过程，有三种情况：1、插入节点最小值2、插入节点最大值3、插入节点中间值33、操作分析，如删除，需要几个临时指针：P0:指向要插入的节点；初始化：p0=数组stuP1:指向P1之前要插入的节点；初始化：p1=headP2:指向P2后要插入的节点；插入操作：当满足以下条件时：p0-num和p1-num比较并找到位置if(p0-nump1-num)，34，图11.22，head，p1，(a)，p0，35，图11.22，p2，p1，(b)，36，例11，structstudentsert(structstudenthead，structstudentstudentp0，* P1，* p2p1=头部；p0=研究；如果(head=空；) head=p0P0-下一个=空； 其他时候(p0-nump1-num)，原来的链表是一个空表，p0指向要插入的节点，p0指向作为头节点的节点，p2指向p1刚才指向的节点，在原来的第一个节点之前，在p2指向的节点之后，在最后一个节点之后，link，37，head，class示例：已经有一个链表，如图所示；它根据节点中的整数字段从小到大排序。现在要插入一个节点。节点中的数字是10。要插入的节点已经插入到链表中。38.分析：根据三种情况1和1，链表还没有完成(空链表)，要插入的节点P实际上是第一个节点。必须有head=null。只需将指针指向p。语句为，headp，head=p；p-next=空；在第二种情况下，链表已经完成，要插入节点p的数据小于头节点的数据。然后是(p-num)num。当然，p节点必须插入到头节点的前面。39，head，head，p，p-next=head；head=p；语句为，null，40，3，第三种情况，链表已经完成，要插入到节点p的数据大于头节点的数据，需要找到正确的插入位置。此时，借助于两个结构指针r和g，通过循环比较可以找到正确的位置。然后，将节点P插入链表中的正确位置。在这种情况下，节点p已经与链表的第一个节点进行了比较，所以比较从链表的下一个节点开始。138、继续比较。我不确定这是不是真的。我不确定这是不是真的。p-next=g；44，/结构7.c#include/预编译命令#include/内存空间分配#definenull0/定义空指针常量# DEFINELENSIZEOF(STRUCTUNUST)/定义常量，表示结构长度STRUCTUNUMST/结构声明 intnum/下一个整数结构；/numST结构指针；参照程序45，/调用函数insert()，两个形式参数分别表示链表和节点空插入(structnumst * * phead，struct numst * p)/函数体开始structnumST*q，* r；/定义结构指针q，rif(*phead)=null)/在第一种情况下，链表为空 * phead=p；/列表头指向预转；/完成插入操作并返回否则/链表不为空/在第二种情况下，P节点的数值小于链表头节点的数值IF(*-Phead)-NUMP-NUM)/将P节点插入链表头P-next=* Phead；/指针p的下一个指针指向列表头(* phead)* phead=p；/将链表头分配给预转；/return ，46，/在第三种情况下