计算机软件技术编程基础 链表 PPT课件.ppt

顺序表的特点: 运算:简单,时间复杂度好存储特性:静态规模,编译前确定问题:程序的通用性和空间利用率之间的矛盾期望:在实际运行过程中,根据实际问题的需要临时确定存储空间,涉及到动态变量动态变量:在程序运行的过程中产生和释放的变量。与之相反的是静态变量静态变量:在程序运行的过程中一直存在的变量。静态变量是出现在说明语句中的变量; 动态变量由于是在运行中产生的,因而不会事先说明如何实现动态变量? 通过指针来实现:指针变量的说明,动态变量的产生和释放。 线性链表及其运算线性表的链式存储结构称为线性链表,即将表中元素用链地址连接起来。 head 头指针结点对线性表中的每一个数据元素,都需用两部分来存储:一部分用于存放数据元素值,称为数据域;另一部分用于存放直接前驱或直接后继结点的地址(指针),称为指针域,称这种存储单元为结点。链表的存储结构链式存储结构是利用任意的存储单元来存放线性表中的元素,存储数据的单元在内存中可以连续,也可以零散分布。由于线性表中各元素间存在着线性关系,每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系,在这种结构中不仅要存储线性表中的元素,还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息,除了存储每一个数据元素值以外,还需存储其后继或前驱元素所在内存的地址。两部分信息一起构成链表中的一个结点。结点的结构如下所示。 data next 数据域指针域链表结构示意图 4 head 头指针 123456789 10 data next A7 B2 C9 D1 E0 (a)线性链表的物理状态头指针 head ABCDE 47291 ∧(b)线性表的逻辑状从图中可见,每个结点的存储地址存放在直接前驱的指针域中。所以要访问链表中数据元素 C,必须由头指针 head 得到第一个结点(数据 A)的地址,由该结点的指针域得到第二个结点(数据 B)的地址,再由其指针域得到存储数据 C的结点地址,访问该结点的数据域就可以处理数据 C了。链表这种顺着指针链依次访问数据元素的特点,表明链表是一种顺序存储结构,只能顺序操作链表中元素。不能像顺序表(数组)那样可以按下标随机存取。在链表存储结构中,不要求存储空间的连续性,数据元素之间的逻辑关系由指针来确定。每个结点由两部分组成: data 数据域——存放数据值 next 指针域——存放后继结点的首地址链表通过每个指针域将 n个结点按逻辑次序链接成一个整体。&b&c&d ∧ Head &a 头指针结点&b &c &a & data next 表头的地址由 head 指针提供,表尾结点没有直接后继,其指针域应为空指针,指针域为 NULL 单向链表在图所示的链表中,每个结点只有一个指向后继的指针。也就是说访问数据元素只能由链表头依次到链表尾,而不能做逆向访问。称这种链表为单向链表或线性链表。这是一种最简单的链表。对于空链表,头结点的指针域为空。图 2-8 (a)为带头结点的空链(b) 为带头结点的单链表 head heada 1a 2a 3∧(a) 空链表(b ) 非空链表∧定义链表结点结构的一般形式为 Struct 结构体名{数据成员表; 结构体名*指针变量名; } struct student { int num; float score; student * next; }; struct ListNode { ELEM data ; ListNode * next; } 1 67 2 87 3 79 4 86 head tail //建立链表 linklist * create() { linklist * head, * p1, * p2; head=NULL; int x; cin >>x; struct linklist { int num; float score; linklist * next; };