本章主题：线性表的有关概念和基本运算教学目的：掌握线性

本章主题：线性表的有关概念和基本运算教学目的：掌握线性内容摘要：

0/11/23 32 从图中可见，每个结点的存储地址存放在直接前驱的指针域中。 所以要访问链表中数据元素 C， 必须由头指针 head得到第一个结点（数据 A） 的地址，由该结点的指针域得到第二个结点（数据 B）的地址，再由其指针域得到存储数据 C的结点地址，访问该结点的数据域就可以处理数据 C了。 链表这种顺着指针链依次访问数据元素的特点，表明链表是一种 顺序存储结构 ，只能顺序操作链表中元素。 不能像顺序表（数组）那样可以按下标 随机 存取。 为了提高顺序操作的速度，使操作更加灵活方便，对链表中的指针采用了不同的设置，构成了不同的链表。 如只设置一个指向后继结点地址的指针域是单链表；将其首尾相接构成一个环状结构，称为循环链表；增加一个指向前驱的指针就构成双向链表。 在链表存储结构中，不要求存储空间的连续性，数据元素之间的逻辑关系由指针来确定。 由于链式存储的灵活性，这种存储方式既可用于表示线性结构，也可以用来表示非线性结构。 2020/11/23 33 单向链表 在图 27所示的链表中，每个结点只有一个指向后继的指针。 也就是说访问数据元素只能由链表头依次到链表尾，而不能做逆向访问。 称这种链表为单向链表或线性链表。 这是一种最简单的链表。 单链表分为带头结点和不带头结点两种类型。 对于空链表，头结点的指针域为空。 图 28是带头结点的链表示方式： 图 28（ a） 为带头结点的空链 (b)为带头结点的单链表 headheada1a2a3∧(a) 空链表（b) 非空链表∧2020/11/23 34 由于链表是一种动态管理的存储结构，每个结点需动态产生。 1． 初始化链表 initlist(L)的实现 建立一个空的带头结点的单链表。 所谓空链表就是指表长为 0的表。 在这种情况下 ， 链表中没有元素结点。 但应有一个头结点 ， 其指针域为空。 void initlist(LinkList *L) { *L=(LNode *)malloc(sizeof(LNode))。 (*L)next=NULL。 } 在函数调用时，指针 L指向的内容发生了变化，为使得调用函数中头指针变量 head获得头结点地址，需传递头指针变量的地址给 initlist()函数，而函数中定义二级指针变量 L接受该地址值，从而返回改变后的值。 2020/11/23 35 2． 求线性表长度 Getlen(L)的实现 设计思路：设置一个初值为 0的计数器变量和一个跟踪链表结点的指针 p。 初始时 p指向链表中的第一个结点 ， 然后顺着 next域依次指向每个结点 ， 每指向一个结点计数器变量加 1。 当 p为 0时 ， 结束该过程。 其时间复杂度为 O(n)。 int Getlen(LinkList L) { int num=0。 LNode *p。 p=Lnext。 while(p!=NULL) { num++。 p=pnext。 } return(num)。 } 2020/11/23 36 3． 按序号取元素 Getelem(L,i)的实现 根据前面的讨论 ， 对单链表中的结点只能顺序存取 ， 即访问前一个结点后才能接着访问后一个结点。 所以要访问单链表中第 i个元素值 ， 必须从头指针开始遍历链表 ， 依次访问每个结点 ， 直到访问到第 i个结点为止。 同顺序表一样 ， 也需注意存取的位置是否有效。 LNode *Getelem(LinkList L,int i) { LNode *p。 int pos=1。 p=Lnext。 if(i1 || iGetlen(L)) exit(1)。 while(posi) { p=pnext。 pos++。 } return p。 } 2020/11/23 37 4． 查找运算 locate(L,x)的实现 设计思路：设置一个跟踪链表结点的指针 p， 初始时 p指向链表中的第一个结点 ， 然后顺着 next域依次指向每个结点 ， 每指向一个结点就判断其值是否等于 x， 若是则返回该结点地址。 否则继续往后搜索 ， 直到 p为 0， 表示链表中无此元素 ， 返回 NULL。 其时间复杂度为 O(n)。 LNode *Locate(LinkList L,int x) { LNode *p。 p=Lnext。 while(p!=NULL amp。 amp。 pdata!=x) p=pnext。 return p。 } 2020/11/23 38 5． 链表的插入算法 inselem(L,i,x)的实现 单链表结点的插入是利用修改结点指针域的值 ， 使其指向新的链接位置来完成的插入操作 ， 而无需移动任何元素。 假定在链表中值为 ai的结点之前插入一个新结点，要完成这种插入必须首先找到所插位置的前一个结点，再进行插入。 假设指针 q指向待插位置的前驱结点，指针 s指向新结点，则完成该操作的过程如图 29所示。 2020/11/23 39 图 29 p前插入 s结点过程示意图 s=(LNode *)malloc(sizeof(LNode))；sdata=x；( b)申请新结点s，数据域置xxsheada1a2...ai1p...aian∧xsheada1a2...ai1p...aian∧②①(a)找到插入位置snext=qnextqnext=s(c)修改指针域，将新结点s插入关键语句：qq上述指针进行相互赋值的语句顺序不能颠倒。 2020/11/23 40 void Inselem(LinkList L,int i,int x) { LNode *p,*q,*s。 int pos=1。 p=L。 if(i1 || iGetlen(L)+1) exit(1)。 s=(LNode *)malloc(sizeof(LNode))。 sdata=x。 while(pos=i) { q=p。 p=pnext。 pos++。 } snext=qnext。 qnext=s。 } 2020/11/23 41 若传给函数的是待插入结点的地址 ， 可编写如下的算法： void Insnode(LinkList L,int i,LNode *s) { LNode *p,*q。 int pos=1。 if(i1 || iGetlen(L)+1) exit(1)。 p=L。 while(pos=i) { q=p。 p=pnext。 pos++。 } snext=qnext。 qnext=s。 } 2020/11/23 42 6． 链表的删除运算 delelem(L,i)的实现 要删除链表中第 i个结点 ， 首先在单链表中找到删除位置前一个结点 ， 并用指针 q指向它 ， 指针 p指向要删除的结点。 将 *q的指针域修改为待删除结点 *p的后继结点的地址。 删除后的结点需动态的释放。 如下图 210所示。 假定删除的结点是值为 ai的结点。 图 210(c)中虚线表示删除结点 *p后的指针指向。 具体算法描述为： { q=qnext。 pos++。 } p=qnext。 qnext=pnext。 free(p)。 } void Delelem(LinkList L,int i) { int pos=1。 LNode *q=L,*p。 if(i1 || iGetlen(L)) exit(1)。 while(posi) 2020/11/23 43 x=pdata；( b)返回被删除结点数据xxpheada1a2...ai1q...aian∧(a)找到删除位置pheada1...(c)修改指针域，将结点p删除qai1pai...an∧ai+1①②关键语句： qnext=pnext；free(p)图 210 线性链表的删除过程示意图 2020/11/23 44 在插入和删除算法中 ， 都是先查询确定操作位置 ， 然后再进行插入和删除操作。 所以其时间复杂度均为 O(n)。 另外在算法中实行插入和删除操作时没有移动元素的位置 ， 只是修改了指针的指向 ， 所以采用链表存储方式要比顺序存储方式的效率高。 7． 链表元素输出运算 displist(L)的实现 从第一个结点开始 ， 顺着指针链依次访问每一个结点并输出。 void displist(LinkList L) { LNode *p。 p=Lnext。 while(p!=NULL) { printf(%4d,pdata)。 p=pnext。 } printf(\n)。 } 2020/11/23 45 图 211 单链表的倒置 heada1a2... ai1...aian∧headanan1... ai...ai1a1∧(a)倒置前(b)倒置后2020/11/23 46 【 例 24】 利用前面定义的基本运算函数 ， 编写将一已知的单链表H倒置的程序。 如图 211的操作。 (a)为倒置前 ， (b)为倒置后。 【解】算法基本思路：不另外增加新结点，而只是修改原结点的指针。 设置指针 p ， 令其指向 headnext， 并将 headnext置空，然后依次将 p所指链表的结点顺序摘下，插入到 head之后即可。 具体算法如下： void reverse(LinkList L) { LNode *p,*q。 if(Lnext!=NULL) //至少有两个元素 { p=Lnext。 Lnext=NULL。 while(p!=NULL) 2020/11/23 47 { q=p。 p=pnext。 Insnode(L,1,q)。 } } } main() { LNode *head,*p。 int i,x。 initlist(amp。 head)。 for(i=1。 i=5。 i++) { scanf(%d,amp。 x)。 Inselem(head,i,x)。 } reverse(head)。 displist(head)。 } 该算法只是对链表顺序扫描一遍即完成了倒置，所以时间复杂性为O(n)。 2020/11/23 48 循环链表 在单链表中 ， 最后一个结点的指针域为空 （ NULL）。 访问单链表中任何数据只能从链表头开始顺序访问 ， 而不能进行任何位置的随机查询访问。 如要查询的结点在链表的尾部也需遍历整。