数据结构chapter 2linklist（2） 链表 ppt课件

上堂课要点回顾 l单链表 类型定义 基本操作实现 应用* 数据结构课程内容 第第 四四 次次 课课 阅读： 朱战立，第36-44页、第323-328页 练习： Project1 链式存储结构的优缺点链式存储结构的优缺点 优点 （1）无需事先了解线性表的长度，结点空间 动态申请和释放，允许线性表的长度有很大的 变化 （2）插入删除操作无需大量移动元素，只要 修改指针；能够适应经常插入删除元素的情况 缺点 （1）链表的操作算法较复杂 （2）指针域需额外占用空间 （3）非随机存储结构，需从头指针遍历查 找结点 例例2-7 2-7 (P43)(P43) 线性表的就地排序线性表的就地排序 问题描述： 设head是单链表的 头指针，编写算法将 数据元素按照其值递 增有序的顺序进行就 地排序。 例：head=(8,4,10,7) 则 head=(4,7,8,10) 例2-6 自学 辅助空间为O(1)称就地排序，辅助空间为O(n)称非 就地排序 8,4,10,7 head 8,4,10,7 head p 4,10,78head p 10,74,8head p 74,8,10head p 4,7,8,10head p 思想：通过改变结点间的指针链接关系实现就地 排序。从“空表”开始，依次将元素结点逐个插入 到链表中。具体如下： 1、将head表断开，形成两个表：head空表和p表 2、依次从p表中取出第一个结点（q指针），将q结点 移动到head表中合适位置处： 2.1、 在head表中根据数据域大小从头指针开始寻找 q结点的插入位置i（应该找到第i-1个结点才便于删除， 因此定义curr指针寻找第i个结点，pre指针始终指向 curr结点的直接前驱结点）； 2.2、 从p表中删除q结点； 2.3、 将q结点插在head表pre结点之后（curr结点之 前）； 循环第2步直至p表为空 【单链表就地排序算法】 void LinListSort(SLNode *head) /head为带头结点的单链表，就地排序破坏原来的表。 SLNode *curr,*pre,*p,*q;/curr和pre：搜索指针 p=head-next;/p表 head-next=NULL;/head表置为空表 while (p!=NULL) curr=head-next;/curr初始化为指向首元结点 pre=head;/pre始终指向curr结点的直接前驱 while( curr!=NULL /curr和pre后移 curr=curr-next; q=p; p=p-next; q-next=pre-next; pre-next=q; 时间复杂度O(n2） 2.3.5 循环单链表（简称循环链表） 定义：在单链表的尾结点的链域中放入指 向头结点的指针，使整个链表形成一 个环形。 逻辑状态： heada0a1 an-1 head 满足head=head-next 空表： 非空表： 优点： 不增加额外开销开销，却给不少操作带来 方便，从循环表中任一结点出发都能访问 到表中其它结点 循环链表的运算与单链表的基本一致， 差别仅在于算法中的循环条件，不是p或 p-next是否为空，而是它们是否等于head。 2.3.6 双向链表 结点结构 弥补单链表next域仅指向后继结点，不能有效找 到前驱的不足，增加一个指向直接前驱的指针。 nextdataprior 结点描述类型 typedef struct Node DataType data; struct Node *prior,*next; DLNode; /*双向链表结点结构*/ 逻辑状态 带头结点的双向链表 非空表： a0a1 an-1 head head 满足 head-prior =head-next =head 空表： 逻辑状态 带头结点的双向循环链表 head 满足 head-prior =head-next =head 非空表： a0a1 an-1 head 空表： 双向链表中结点的一个重要特征 显然， ppriornext = = pnextprior = = p p CA B 插入一个结点的实现 x p s pprior=s; ai-1ai sprior=pprior; ppriornext=s; snext=p; 删除一个结点的实现 pnextprior=pprior; p ai+1ai-1 ai pproirnext = pnext; free(p); 几种主要链表比较几种主要链表比较 空表 head 单链表： a0a1 an-1 head 非空表 head 空表 heada0a1an-1 非空表 循环单链表： 非空表 a0a1an-1head head空表 非空表： a0a1 an-1 head 双向链表： 双向循环链表： head 空表 a0a1an-1head非空表 应用场合的选择应用场合的选择 l不宜使用顺序表的场合 线性表的最大长度不确定时 经常插入删除时 l不宜使用链表的场合 当读操作比插入删除操作频率大时 当指针存储开销和整个结点内容所占空间相 比，其比例较大时 2.4 静态链表 在一维数组中增加指针域用来存放下一个数据 元素在数组中的下标，从而构成用数组描述的 链表。因为数组内存空间的申请方式是静态的 ，所以称为静态链表，增加的指针称做仿真指 针。便于在没有指针类型的程序设计语言中使 用链表。静态链表结构如下： ABCE head D (a) 常规链表 D 4 E -1 C 3 B 2 A 1 MaxSize1 4 1 2 0 3 (b) 静态链表1 D 1 C 3 B 4 E -1 A 2 MaxSize1 4 1 2 0 3 (C) 静态链表2 JesephRing问题模拟 【问题描述】 已知n个人（编号分别为1，2，.，n）按顺时针 方向围坐一圈，每人持有一个正整数密码。 开始 时任选一个报数上限值m，从编号为1的人按顺时 针方向自1开始报数，报到m时停止报数，报m的 那个人出列；将他的密码作为新的m值，从他在 顺时针方向的下一个人开始重新从1报数，数到m 的那个人又出列；依此规律重复下去，直到所有 人全部出列。输入n，m两个正整数，设计程序来 求出列的序列。 【例如】n = 7, 7个人的密码分别为3,1,7,2,4,8,4。初 始报数上限值m=20。 【解答】出局人的顺序为6, 1, 4, 7, 2, 3, 5 ADT JesephRing 数据元素：ai=(ni，mi)，i=0,1,n-1 (n0)，ni，mi代表第i 个人的编号和持有的密码 ，其中ni不能省略。 结构：是线性结构，对数据元素ai (0in-2)存在次序关系 , a0的直前是an-1 ，an-1的直继是a0。 逻辑操作：设J为 JesephRing型 JesephRingInitiate(J) /构造一个空的约瑟夫环J。 JesephRingInsertEnd(J, x) /*在约瑟夫环J尾部插入新元 素x ，成功返回1，失败返回0。*/ JesephRing(J,m) /*给定初始报数上限m，从1开始循环报 数、删除、输出直至J为空，得到出列序列。*/ 问题的抽象数据类型分析问题的抽象数据类型分析 存储结构分析存储结构分析 l分析逻辑操作特点和空间比例 频繁插入和删除 指针存储开销和整个结点内容所占空间相比，其比 例较小 综上所述，不采用顺序表，而采用链表 经常在尾部插入，因此增设尾指针，始终指向尾部 结点 a0的直前是an-1 ，an-1的直继是a0 ，因此采用循环单 链表 综上所述，采用带尾指针的循环单链表存储结构 目的：有效地组织和处理数据 带尾指针的循环单链表带尾指针的循环单链表 l逻辑状态 l分析逻辑操作 初始化SCListInitiate(L) 在表尾插入新结点SCListInsertEnd(L, x) 删除p结点的下一个结点SCListDeleteAfter(L,p) 判断是否是空表SCListNotEmpty(L) head 空表 rear heada1a2an 非空表 rear 带尾指针的循环单链表实现带尾指针的循环单链表实现 “SCListWithRear.h“ “SCListWithRear.h“ #include “LinkList.h “ typedef struct SLNode * head;/头指针 SLNode * rear;/尾指针 SCListWithRear; /*带尾指针的单链表类型定义*/ void SCListInitiate(SCListWithRear *L) /初始化带尾指针的循环单链表 ListInitiate( L-head-next=L-head;/循环结构 L-rear=L-head;/尾指针处理 int SCListNotEmpty(SCListWithRear *L) if(L-head-next=L-head)return 0; elsereturn 1; int SCListInsertEnd(SCListWithRear *L,DataType x) /*在带尾指针的循环单链表的末尾结点后插入一个新 元素x。*/ SLNode *q; q=(SLNode *)malloc (sizeof(SLNode); /*新结点*/ q-data=x; q-next=L-rear-next; /*插入*/ L-rear-next=q; L-rear=q;/尾指针处理 return 1; 时间复杂度O(1) int SCListDeleteAfter(SCListWithRear *L,SLNode *p) /*删除并释放带尾指针的循环单链表L中p结点的下一个 结点*/ SLNode *s; s=p-next; p-next=p-next-next;/删除p结点的下一个结点 if(s-next=L-head) L-rear=p;/尾指针处理 free(s); return 1; 时间复杂度O(1) 算法设计JesephRing.cpp #include #include typedef struct int number; int cipher; DataType; #include “SCListWithRear.h” void JesephRingInitiate(SCListWithRear *J) /*构造一个空的约瑟夫环J。*/ SCListInitiate(J); int JesephRingInsertEnd(SCListWithRear *J, DataType x) /*在约瑟夫环J尾部插入新元素x */ return SCListInsertEnd(J,x); JesephRing(J,m)基本算法： 1、根据初始报数上限m值，寻找第m个结点（ 应该找到第m-1个结点的地址才便于删除，因 此为便于删除定义curr指针找第m个结点，pre 指针始终指向curr结点的直接前驱结点） 2、输出第m结点的number值 3、把该结点的cipher值赋给m，作为下一次循 环的报数上限m 4、删除第m个结点 如此循环n次或直至表为空时结束。（实际只需循环 n-1次，最后只剩一个结点时，直接输出即可） void JesephRing(SCListWithRear *J, int m) /给定初始报数上限m，从1开始循环报数、删出、输出直至J为空 SLNode *pre,*curr; int i; pre=J-head;curr=J-head-next; while(SCListNotEmpty(J)=1) for (i=1;inext; if(curr=J-head)/跳过头结点 pre=curr;curr=curr-next; printf(“%d “,curr-data.number); m=curr-data.cipher;curr=curr-next; if(curr=J-head)curr=curr-next; /跳过头结点 SCListDeleteAfter(J,pre); 时间复杂度O（nm） void main() SCListWithRear JR; int n=7,m=20; DataType test7=1,3,2,1,3,7,4,2,5,4, 6,8,7,4; int i; SCListInitiate( for(i=0;i表尾逐步建立。 SLNode *l1；SLNode *p; int i; l1=(SLNode *)malloc(sizeof(SLNode); l1-next=null; p=l1; for (i=0;inext=(SLNode *)malloc(sizeof(SLNode); p=p-next; scanf(“%d”, p-next=NULL; return l1; 建带头结点的单链表（补充）建带头结点的单链表（补充） 时间复杂度：O(n) a0 an-2 an-1 head p p p p p-next=head-next; head-next=p; p 下面讨论第二种方法：从表尾表头逐步 建立单链表。新元素插入在头结点之后。 int CreateLinkList1 (SLNode *head, int a, int n) /* 建立以head为头指针的带头结点的单链表 */ i