线性表链式存储结构

顺序存储结构最大的缺点就是在插入和删除时需要移动大量的元素耗费较多时间,原因是相邻的两元素的存储位置也是相邻关系,也就是在内存中的位置也是挨着的,中间没有空隙,当然就无法快速介入,删除后当中会留下空隙,需要弥补

通俗思路:我们反正也是要相邻元素之间留有足够余地,干脆所有的元素都不考虑相邻位置了,哪有空位置就到哪里,只是让每个元素知道它下一个元素的位置在哪里,这样,可以在第一个元素就知道第二个元素的位置(内存地址),从而很容易找到它;在第二个元素再找到第三个元素的位置(内存地址),这样所有的元素很容易通过遍历找到

线性表链式存储结构用一组任意的存储单元存储线性表的数据元素,这组存储单元可以是连续的,也可以是不连续的,也就是这些元素可以存在内存未被占用的任意位置,所以这种存储结构除了要存数据元素信息外,还要存储下一个元素的存储地址

许多结点链结成了一个链表,每个结点中指包含一个指针域,为单链表。链表第一个结点的存储位置叫头指针,之后每一个结点就是上一个指针指向的位置。最后一个结点指针为空

单链表结点类型

typedef char DataType;

typedef struct node {

    DataType data;

    struct node *next;

}ListNode;

typedef ListNode *LinkList;

ListNode *p;

LinkList head;

(1)LinkList和ListNode *是不同名字的同一个指针类型

(2)LinkList类型的指针变量head表示它是单链表的头指针

(3)ListNode *类型的指针变量p表示它是指向某一结点的指针

头指针

头指针是链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针;头指针具有标识作用,常用头指针冠以链表的名字;无论链表是否为空,头指针均不为空,是链表的必要元素

发表评论