2.2 链表 数据结构.ppt

(包括表、栈、队、数组)的定义和特点仅一个首、尾结点,其余元素仅一个直接前驱和一个直接后继。:“一对一”或1:1存储结构:顺序、链式运算:修改、插入、:逻辑上相邻,物理上也相邻;优点:随机查找快O(1)缺点:插入、删除慢O(n)2链式存储结构总结线性表顺序存储结构特点:逻辑关系上相邻的两个元素在物理存储位置上也相邻;优点:可以随机存取表中任一元素,方便快捷缺点:在插入或删除某一元素时,需要移动大量元素。解决问题的思路:改用另一种线性存储方式::即地址。指针变量:是专门用来存放另一个变量的地址的变量,即专门存放地址的,指针变量的值是指针Int*p,*q;/*p,q是变量名,都是指向整型变量的指针变量,*表示该变量为指针变量,(*p)是指指针变量P所指向的变量*/数组指针:是指数组的起始地址,数组元素的指针是数组元素的地址。Int*p,a[10];若p=a,则p+1=a+1指针数组:是指数组元素均为指针类型的数组5链式存储结构特点:其结点在存储器中的位置是随意的,即逻辑上相邻的数据元素在物理上不一定相邻。如何实现?通过指针来实现!让每个存储结点都包含两部分:数据域和指针域指针数据指针数据指针或样式数据域:存储元素数值数据指针域:存储直接后继或者直接前驱的存储位置设计思想::请画出26个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下:解:该字母表的逻辑结构为:(a,b,…,y,z)链表存放示意图如下:a1heada2/\an……讨论1:每个存储结点都包含两部分:数据和。讨论2:在单链表中,除了首元结点外,任一结点的存储位置由指示。其直接前驱结点的链域的值指针域(链域)71)结点:数据元素的存储映像。由数据域和指针域两部分组成;2)链表:n个结点由指针链组成一个链表。它是线性表的链式存储映像,称为线性表的链式存储结构。3)单链表、双链表、多链表、循环链表:结点只有一个指针域的链表,称为单链表或线性链表有两个指针域的链表,称为双链表(但未必是双向链表);有多个指针域的链表,称为多链表;首尾相接的链表称为循环链表。a1heada2an……循环链表示意图:head(2)与链式存储有关的术语:84)头指针、头结点和首元结点的区别头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点(或为头结点、或为首元结点)的指针;;数据域内只放空表标志和表长等信息,它不计入表长度首元结点是指链表中存储线性表第一个数据元素a1的结点示意图如下:9答:??头结点即在链表的首元结点之前附设的一个结点,该结点的数据域可以为空,也可存放表长度等附加信息,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便。答:无头结点时,当头指针的值为空时表示空表;^头指针无头结点^头指针头结点有头结点有头结点时,当头结点的指针域为空时表示空表。头结点不计入链表长度!10