C语言线性表链式表示及实现的方法


今天小编给大家分享一下C语言线性表链式表示及实现的方法的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,而线性表的链式存储特点则是用一组任意的存储单元存储线性表的数据元素。这组存储单元既可以是连续的,也可以是不连续的。对于链式存储的每个数据元素而言,除了存储其本身的信息之外,还需要存储一个指示其直接后继的信息,即直接后继的存储位置。这两部分信息组成了数据元素的存储映像,称为结点。链式存储的结构包含两个域:一个用于存储数据元素的信息,另一个用于存储直接后继的存储位置;存储数据元素信息的域称为数据域存储直接后继存储位置的域称为指针域。图示:数据结构中,在单链表的开始结点之前一般要附设一个类型相同的结点,称之为头结点头结点的数据域可以不存储任何信息,头结点的指针域存储指向开始结点的指针,即第一个元素结点的存储位置。附设头结点的作用:防止单链表是空的而设的。当链表为空的时候,带头结点的头指针就指向头结点,如果当链表为空的时候,单链表没有带头结点,那么它的头指针就为NULL方便单链表的特殊操作,插入在表头或者删除第一个结点,加入头结点的话就可以保持单链表操作的统一性当单链表加上头结点之后,无论单链表是否为空,头指针始终指向头结点,因此空表和非空表的处理也就统一了,方便了单链表的操作,也减少了程序的复杂性和出现bug的机会链式表示要实现的功能:实现工具:Dev C++构造一个空的头结点对线性表进行赋值对线性表进行销毁对线性表进行重置判断线性表是否为空获取线性表的长度获取线性表某一位置对应的元素在线性表某一位置插入元素删除线性表某一位置的元素求线性表某一元素的前驱求线性表某一元素的后继打印线性表退出准备工作:打开Dev C++后新建一个Source File文件即可 File>new>Source File在实现线性表的链式存储时导入的头文件有在这里我调用windows头文件是为了在后面的代码中修改控制台的名称,在实现线性表的链式存储时真正用到的只有前三个头文件在写各种函数之前先对一些表示结果状态的字符进行预定义在这里使用了typedef定义了Status和ElemType为int类型,也就是说之后的代码当中如果出现了Status和ElemType,它们与int作用相同代码中的* LinkList指的是结点的类型,在之后的代码中出现了它就相当于出现了指向这个结点的指针在该函数传参时一定要在L之前加”&”符号,表示引用传递,保证形参和实参同时改变。之前在写代码时因为没有输入”&”符号,没有使用引用传递也就意味着没有开辟了新的内存空间,所以在之后赋值的时候会出现无法赋值的情况 在这里要强调一点:“->“是一个指针类型的运算符,它是用于指向结构体子数据的指针因为要实现构造一个单链表,所以在main函数中会循环调用ValueList_L方法,所以通过以下的循环是用来使p指向要赋值的位置while(p->next){之后利用malloc()函数开辟新的结点来存放数据和下一个结点的位置即可,因为malloc()函数开辟空间之后返回的不是LinkList结点类型,所以在利用malloc()函数开辟新的结点时要将其通过强制类型转换使其转换成LinkList类型在对单链表进行销毁操作时,从头结点开始逐一释放,释放前使q指向开始释放的结点,当开始结点不为空时,执行释放过程,先释放头结点,然后将L,q都向后移,依次释放,因为q始终是L的后继,所以最后一定是L留到最后,最后释放L结点L = NULL;为什么在feel(L);之后还要将L赋值为空?因为free函数只是将之前动态分配给L的内存归还给系统,但是指针类型的结点L仍然存在,为了防止之后发生野指针访问,将L赋值为NULL在对线性表进行重置前首先要判断线性表是为空表,当其不为空时构造两个LinkList类型的结点p和q,使p指向L的首元结点,当p不为空即单链表不为空时进入while循环,将p的下一个结点复制给q,将p释放后再将q赋值给p。p为空时说明此时单链表只剩下了头结点,将头结点的指针域设置为NULL,完成单链表的重置(因为LinkList为指针类型的数据,所以赋值的内容都是地址图示:在判断线性表是否为空时,首先判断头结点是否存在,当头结点存在时看头结点的指针域是否为空,当指针域为空时说明首元结点不存在,单链表是空表当指针域不为空时说明存在首元结点,单链表不是空表。如果头结点不存在的话说明单链表不存在,无法判断是否为空表。获取线性表长度的核心思路是遍历单链表,定义LinkList类型的变量p,将单链表的首元结点赋值给p。在该函数中count为计数器,形参count传来的值始终为1,count的值为1代表从首元结点开始计数,所以才将L->next赋值给p,目的是为了让count与存储数据元素的结点位置对应一致。(在单链表中有头结点的存在,所以这种方法计算出的长度最后的值要比线性表的实际长度大1)进入循环后每当p不断向后移动,每当p后移一次,计数器count的值就加1,直到p为空,此时count的位置就对应着最后一个存储着数据元素的结点位置。与获取单链表的长度思路一样,获取单链表某一位置的元素也需要遍历单链表,只不过什么时候停止遍历由自己决定,可能不需要全部遍历。定义LinkList类型的变量p并且将首元结点的地址赋值给p。定义计数器count的初始值为1之后,进入while循环,循环判断有两个:p 因为p一直指向第count个结点,所以此循环判断条件的意思是当第count个结点存在时才能进入循环count 退出循环以后p指向的位置就是我们想要获取的结点位置,这个时候要先进行越界判断,!p的意思是如果在之前的循环中index的值大于单链表的长度,那么退出循环的原因就是p为NULL,那么!p就为true,满足if语句中的条件,返回ERROR,所以 !p的作用就是限制index不大于单链表的长度。 count > index的目的是为了限制index的值小于1与寻找某个位置结点的值思路一致,需要先找到要插入结点的位置。但是这里不同的地方在于要插入结点的话,可以在单链表的表尾插入元素,也可以在头结点和首免费云主机域名元结点间插入元素,所以计数器count的初值为0(为了保证从头结点开始遍历,count的值与实际的结点位置相匹配),所以判断条件变为index – 1。在结束循环和越界判断结束后p之后的位置就是要插入结点的位置,先构造出一个空结点并赋值给q,将p的下一个结点位置赋值给q的指针域,再将p的下一个结点位置赋值给q完成插入操作。图示:删除某一结点的思路仍然是从头结点开始遍历找到要删除的结点的位置的前一个结点,此时p就是要删除结点位置的前一个结点。将p的后一个结点赋值给q,此时q就是要删除的结点,将q的下一个结点与p的下一个结点连接,释放q结点,完成删除操作。和删除结点的思路完全一致,只不过求前驱时不需要进行删除结点,在循环中控制循环条件使p在index – 1位置结束循环,此时p指向的就是第index的前驱,直接将p结点的数据域输出即可在声明LinkList类型变量p时将L的首元结点赋值给p,在循环中p一直指向第index的下一个结点,所以直接将p结点的数据域输出即可打印单链表的思路也是进行对单链表的遍历,在遍历的过程中将每个结点的数据域中存储的值输出为了方便演示,在这里为单链表一次赋值为1,2,3,4,5构造一个空的头结点赋值操作判断此时线性表是否为空获取单链表的长度获取2号位置的元素在3号位置插入520并打印单链表获取此时单链表的长度删除3号位置的元素并打印单链表求3号位置元素的前驱和后继重置单链表并获取长度以及判断是否为空表销毁单链表并进行赋值和判断是否为空以上便是线性表链式表示和实现,由于链表在空间的合理利用上和插入、删除是不需要移动等的优点,因此在很多场合下它是线性表的首选存储结构。然而,它也存在着实现某些基本操作的缺点,比如:求线性表长度时不如顺序存储结构……以上就是“C语言线性表链式表示及实现的方法”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注百云主机行业资讯频道。

相关推荐: react native删除线如何设置

今天小编给大家分享一下react native删除线如何设置的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。 react native设置删除线的…

免责声明:本站发布的图片视频文字,以转载和分享为主,文章观点不代表本站立场,本站不承担相关法律责任;如果涉及侵权请联系邮箱:360163164@qq.com举报,并提供相关证据,经查实将立刻删除涉嫌侵权内容。

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 03/18 19:14
下一篇 03/18 19:14

相关推荐