数据结构教程--链接的线性表.ppt

链接存贮的线性表 顺序存贮的地址公式 Ki K0 i s线性表的容量不易扩充对线性表进行插入或删除非常不方便 线性链表的存储结构 线性链表 单链表 采用链接存贮方式存贮的线性表数据域 存储数据元素信息的字段指针域 用来存放其后继结点的地址的字段头指针 指向链表中的第一个结点 NULL head head 头指针 head a b c d head 把链表画成用箭头相链接的结点的序列结点之间的箭头表示线性链表中的指针 头指针head 31 存储地址数据域指针域1L437Q1313S119WNULL25N3731Z737A1943B25 head Z Q S L B N A W Z Q S L B N A W a b c d head typedefstructnode chardata structnode link NODE 链接存贮的线性表 用链表表示线性表时 数据元素之间的逻辑关系由结点中的指针指示 根据结点ki的链接指针 可以找到ki的后继结点ki 1逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻 a b c d head typedefstructnode chardata structnode link NODE includetypedefstructnode chardata structnode link NODE NODE head p q 1 head NODE malloc sizeof NODE 2 p head 建立具有四个结点的线性链表 3 p data a 4 q node malloc sizeof NODE 5 p link q 6 p q 7 p data b 8 q node malloc sizeof NODE 9 p link q 10 p q 建立具有四个结点的线性链表 11 p data c 12 q node malloc sizeof NODE 13 p link q 14 p q 15 p data d 16 p link NULL 建立具有四个结点的线性链表 建立具有n个结点的链表 NODE create link list n intn inti NODE head p q if n 0 return NULL head NODE malloc sizeof NODE p head for i 1 idata q NODE malloc sizeof NODE p link q p q scanf c 建立具有n个结点的链表 线性链表的插入 head a b c d head a b e c d p q 4 1 3 2 p 线性链表的插入 q NODE malloc sizeof NODE q data e q link p link p link q insert p head a b 在head线性链表中把值为b的结点插在值为a的结点之后若原链表为空 则b为首结点若a不在head线性链表中 则把b插在该链表的最后找到a voidinsert p head a b NODE p head chara b NODE p q q NODE malloc sizeof NODE q data b q link NULL if p head NULL p head q else p p head while p data a insert head a b 线性链表的删除 head a b c d p head a b c d p q 1 2 3 删除前的线性链表 删除后的线性链表 线性链表的删除 删除位于指针p所指的结点后面的结点q p link p link q link free q 线性链表的删除 实现在head链表中删除值为a的结点删除成功返回0删除的结点为第一个结点 删除的结点为线性链表中其它结点删除不成功返回1线性链表为空表a不在线性链表中 2020 3 16 22 可编辑 intdelete p head a NODE p head chara NODE p q q p head if q NULL return 1 if q data a p head q link free q return 0 else while q data a elsereturn 1 i delete head a 若线性链表中存在第i个元素 将其值赋给e intstore p head i e inti NODE p head chare p p head j 1 while p link NULLreturn 0 用线性链表表示多项式 Coefexplink coef 存放系数exp 存放指数link 链接指针 指向多项式的下一个非零项结点 零多项式不包含任何非零项 可用一个空的线性链表表示一个零多项式 A x 8x60 6x50 4x25 2x10 1 860 650 425 210 10 B x 7x60 6x50 3x20 760 650 320 ah bh pa pb structnode intcoef intexp structnode link NODE NODE ah bh ch ah amem am 1em 1 a1e1 a0e0 insert pc c e 产生一个新的结点 并把新结点挂在pc所指的结点之后c 系数e 指数 polyadd l ah bh 由线性链表ah和bh表示的两个多项式相加在进行相加之前 先产生一个附加结点pc 在运行到结果多项式的线性表后 再删除这个附加结点 多项式相加 pa exp pb exp 摘取pa指针所指结点插入到结果多项式链表中pa expexp 摘取pb指针所指结点插入到结果多项式链表中pa exp pb exp 则将两个结点中的系数相加和不为零 则修改pa所指结点的系数值 同时释放pb所指结点和为零 从多项式A的链表中删除相应结点 并释放指针pa和pb所指结点 将两个有序链表合并为一个有序链表 voidlink la lb NODE la lb NODE pa pb pc pa la pb lb pc node malloc sizeof node while pa link NULL 1 在一个链表中 已知q结点是p结点的前驱结点 若在q和p之间插入s结点 则执行 A s link p linkp link sB p link s links link pC q link ss link pD p link ss link q2 在链表中 若删除p结点的后续结点 则执行 A p link p link linkB p p linkp link p link linkC p link p linkD p p link link 有一个单链表 不同结点的数据域值可能相同 头指针为head 编写过程计算数据域为x的结点个数 扫描通过该链表的每个结点 每遇到一个值为x结点 结点个数加1 结点个数存贮在变量n中 1 2 3 4 head intcount head NODE head intn 0 NODE p p head while p link NULL if p data x n n 1 p p link 有一个单链表L 至少有1个结点 其头结点指针为head 编写一个过程将L逆置 1 从头到尾扫描单链表L2 将第一个结点的link域置为NULL3 将第二个结点的link域指向第一个结点4 将第三个结点的link域指向第二个结点5 如此 直到最后个结点 便用head指向它 1 2 3 4 head 4 3 2 1 head voidinvert head NODE head NODE p q r p head q p link while p link NULL r q link q link p p q q r head link NULL head p 几种变形的线性链表 环形链表线性链表的最后一个结点的指针指向第一个结点 head head 空的环形链表 非空的环形链表 head NULL 几种变形的线性链表 带表头结点的链表在链表中增加一个附加结点 称之为表头结点 head head 空的带表头结点的链表 非空的带表头结点的链表 表头结点 表头结点 几种变形的线性链表 带表头结点的环形链表在带表头结点的链表中 链表中最后一个结点的指针指向表头结点 head head 空的带表头结点的环形链表 非空的带表头结点的环形链表 表头结点 表头结点 1 不带头结点的链表head为空的判定条件是 A head NULLB head link NULLC head link headD head NULL2 带头结点的链表head为空的判定条件是 A head NULLB head link NULLC head link headD head NULL3 若p指向非空环形链表head的尾结点 则p满足 A p link NULLB p NULLC p link headC p head 带表头结点的环形链表表示多项式 A x 3x10 5x5 2x