线性表.pptVIP

void ListPart (SqList *sl) { int i,j,x,y; x=sl-data[0]; for(i=1;i=sl-length-1;i++) if(sl-data[i]x) { y = sl-data[i]; for(j=i-1;j=0;j--) sl-data[j+1]=sl-data[j]; sl-data[0]=y; } } 本节小结 线性表顺序存储结构特点：逻辑关系上相邻的 两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素；存储空间使用紧凑; 缺点：在插入，删除某一元素时，需要移动大量元素;预先分配空间需按最大空间分配，利用不充分;表容量难以扩充 为克服这一缺点，我们引入另一种存储形式： 链式存储结构 见2.3节 2.3 线性表的链式存储 效率低，大量时间花费在元素位置的移动上； 临时扩大存储空间有困难，存储分配只能预先进行； 必须占用内存连续的地址空间。 顺序存储结构的缺陷 链表存储结构的特点 不需要用地址连续的存储单元来实现 ； 不要求逻辑上相邻的两个数据元素物理上也相邻 ； 通过“链”建立起数据元素之间的逻辑关系 ； 对线性表的插入、删除不需要移动数据元素。 引言 2.3 线性表的链式存储 什么是单链表？ 基于单链表的相关运算的实现 什么是单链表？ 链表：通过一组任意的存储单元来存储线性表中的数据元素。 ai ai+1的地址 数据域 指针域 由于每个结点都只有一个指针域，如此构成的链表被称为单链表。 怎样表示出数据元素之间的线性关系 ? 对每个数据元素ai，除了存放数据元素的自身的信息 ai 之外，还需要和ai一起存放其后继 ai+1 所在的存贮单元的地址，这两部分信息组成一个“结点” 。 data next 链表中的结点结构 例：线性表(a1,a2,……,ai,……an)的链表存储结构图： a2 a1 …… …… a5 …… a3 a4 …… a1 a2 a3 a4 a5 an ^ …… …… 头结点：置于第一个数据结点之前的一个附加结点，它的数据域闲置不做它用。引入头结点可以使算法简化、规范。 a1 a2 a3 a4 a5 an ^ …… …… 头指针：头结点的地址。找到头指针就找到了整个单链表，失去头指针，单链表的建立毫无意义。 h 头指针 头结点 单链表中的结点的存储结构定义： typedef struct LinkNode { ElemType data; struct LinkNode *next; }LNode,*LinkList; 数据域 指针域 如何开辟一个新(空白)结点 TURBO C:p=(LinkList )malloc(sizeof(LNode)); 如何释放指针p所指向的结点 TURBO C: free(p); C++: p=new LNode; C++: delete(p); p P-data P-next 几种常见的指针操作回顾： p=q; p=q-next; p-next=q; p-next=q-next; p=p-next; …… …… q p …… …… q p …… q p × …… …… q p × …… …… p × p 2.3 线性表的链式存储 什么是单链表？ 基于单链表的相关运算的实现 循环链表 双向链表 typedef struct LinkNode { ElemType data; struct LinkNode *next; }LNode,*LinkList; 结点存储结构定义： 1、单链表初始化 void InitList(LinkList h) { h=new LNode; h-next=NULL; } ^ h 2、创建单链表 void CreateList(LinkList h,int a[ ],int n) { LinkList s,r; int i; r=h; for(i=0;i