Rumah >masalah biasa >线性链表是线性表的链式存储结构吗?
根据数据结构中各数据元素之间前后关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。
线性链表,顾名思义类似于一条链子的表,与线性链表相对的是线性顺序表,二者的区别是,线性顺序表需要在内存中开辟一块连续的区域,因此存储的数据在内存中的状态是连续的,而线性链表在内存中的存储是随机的,数据之间的连接靠的是指针。 (推荐学习:web前端视频教程)
如果一个非空的数据结构满足下列两个条件:
①有且只有一个根结点;
②每个结点最多有一个前件,也最多有一个后件。则称该数据结构为线性结构,又称线性表。所以线性表、栈与队列、线性链表都是线性结构,而二叉树是非线性结构。
具有链接存储结构的线性表,它用一组地址任意的存储单元存放线性表中的数据元素,逻辑上相邻的元素在物理上不要求也相邻,不能随机存取。一般用结点描述:结点(表示数据元素) =数据域(数据元素的映象) + 指针域(指示后继元素存储位置)
在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可以用于表示线性结构,也可用于表示非线性结构。
一般来说,在线性表的链式存储结构中,各数据结点的存储符号是不连续的,并且各结点在存储空间中的位置关系与逻辑关系也不一致。对于线性链表,可以从头指针开始,沿各结点的指针扫描到链表中的所有结点。
建立一个线性链表,这是一个动态生成链结点并依次将它们链接到链表中的过程。设线性链表的第1个链结点的指针为list。
当生成第一个链结点时,链表为空,直接将链结点送list即可。每取得一个数据元素,就为该数据元素生成一个链结点,将取得的数据元素的数据信息送给新结点的数据域的同时,将新结点的指针域置为NULL,然后将新结点插入到链表的末尾。
下面的算法中是从一个名为 data.txt 的文件中按行读取字符串作为线性链表的数据元素。算法如下:
LinkList creatList() { LinkList r, p, list = NULL; char data[ 100 ]; FILE *f = fopen( "data.txt", "rb" ); while( fgets( data, 100, f ) ) { p = ( LinkList )malloc( sizeof( LNode ) ); if( p != NULL ){ strcpy( p->data, data ); p->link = NULL; if( list == NULL ) list = p; else r->link = p; r = p; } } fclose( f ); return list; }
Atas ialah kandungan terperinci 线性链表是线性表的链式存储结构吗?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!