第十章 用指针处理链表

第十章用指针处理链表 第一节链表概述 1链表概述 1 数据结构的组织形式 非线性表 树 图等 线性表 线性表 顺序存储 如数组等链式存储 单向链表 双向链表等用指针处理链表 续2 2 链表概念 用结构体作为一个数据单位 每个结构体构成一个结点 用指针把结点一一链接起来 构成链表 结构体的数据组成 两部分 数据 指针例 structnode intnum floatscore structnode p 用指针处理链表 续3 3 链表的特点 链表中各结点具有相同的结构链表的结点由系统随机分配 节点之间的联系通过指针域实现为准确的定位第一个结点 每链表要有一个表头指针链表的节点需要时用mallocz 函数或calloc 函数申请内存 不需要时 使用free 函数释放所占内存段不需实现说明节点数目 只在需要时增加或减少结点 2简单链表 不讲 defineNULL0voidmain structstudent structstudenta b c head p intnum a num 100 a score 89 floatscore b num 101 b score 90 structstudent sp c num 102 c score 95 head 3内存动态分配和释放的函数 1 分配存储空间的函数void malloc unsignedsize 分配一个长度为size字节的连续存储空间 成功执行 返回所分配的存储空间的起始地址 执行失败 返回0地址2 释放所分配的存储空间voidfree void p 释放由p所指向的存储空间例 4建立结点的一般过程 1 向系统申请一个内存段 大小由单个链表结点的数据类型决定 2 给该内存段制定数据类型3 给申请到的结点添加数据 例 structstudent bp bp structstudent malloc sizeof structstudent bp num 100 bp score 95 free p 5建立新链表的一般过程 即将节点一个个按顺序建立 从第一个结点开始 1 向系统申请一个内存段 大小由单个链表结点的数据类型决定 若是第一个结点 链表表头指针head指向该内存地址 若不是 则是上一个结点的指针域指向该内存地址 2 给该内存段制定数据类型3 给申请到的结点添加数据 为结构体变量的各个成员赋值4 若本末结点 其指针域赋空指针值NULL 否则 返回1 继续建立下一个节点 动态链表的建立 例 不讲 defineLstructstudent creat sizeof structstudent structstudent head p defineNULL0head structstudent malloc L structstudenthead sp NULL intnum p structstudent malloc L floatscore scanf d s p num p score structstudent sp while p num 0 p sp head sp head sp p p structstudent malloc L scanf d f p num p score returnhead 第二节链表的基本操作 一链表结点的插入1空链表中插入一个结点1 申请一个new结点 即链表的第一个节点 也是最后一个 如 new structnode malloc sizeof structnode 2 为结点填数据 将要存得到数据对应传给数据域的各个成员3 修改有关的指针指向如 new next NULL head new 2在链表的p结点后插入一个结点 1 使new的指针存d的首地址 new next p next 2 把new的首地址存在p的指针域 p next new head b c d new p 例14 1 二链表结点的删除 把制定的节点从链表中拿出 修改有关结点的指针域释放该结点的内存空间1 若p结点是链表的第一个节点 p指针域的地址保存在head中2 若不是第一个结点 找到p前一个链表q next p next3 释放结点空间 三链表的输出 defineNULL0voidprint structstudent head structstudent structstudent p intnum p head sp floatscore while p structstudent sp printf d f p num p score p p sp 用指针处理链表 续7 四链表的检索和删除 defineNULL0structstudent del structstudent head intnum structstudent structstudent p1 p head sp intnum if p floatscore while p num num 7链表的检索和插入voidinsert structstudent head defineNULL0structstudent ip structstu