第二章线性表.ppt

1、第 2 章 线性表,最常用最常见的数据结构,线性表的类型定义,线性表是n个同类数据元素的有限序列,线性表的类型定义,ADT List 数据对象：D=ai|aiElemSet, i=1,2,n数据关系：R=|ai-1,ai D,i=2,3,n基本操作：InitList( Listinsert(Lc,+k,ai); while (j=lb_len)GetElem(Lb,j+,bj); Listinsert(Lc,+k,bj);,小结,线性 灵活常见 长度不固定 名词 线性表 表长度 第一个元素 最后一个元素 空表,线性表的顺序表示和实现,Loc(a1)=bLoc(a2)=b+lLoc(a3)=b+

2、2lLoc(ai+1)=Loc(ai)+lLoc(ai)=Loc(a1)+(i-1)*l线性表的这种机内表示称作线性表的顺序存储结构或顺序映像，这种通常也称顺序表。特点：只要确定了线性表的起始位置，就随机存储线性表的任一元素，故顺序存储结构也是一种随机存储结构。,数组可用于线性表的顺序存取,#define List_init_size 100#define Listincrement 10typedef structElemType *elem;int length;int listsize; SqList;Status initlist_Sq(SqList ,顺序存储结构下的算法(1),St

3、atus Listinsert_sq(Sqlist ,顺序存储结构下的算法(2),Status ListDelete_Sq(Sqlist ,顺序存储结构下的算法(3),Int LocateElem_Sq(Sqlist L,Elemtype e,Status(*compare(ElemType,ElemType)i=1;p=L.elem;while(i=L.length ,顺序存储结构下的算法(4),Void MergeList_Sq(SqList La,Sqlist La,Sqlist ,续上页,while (pa=pa_last) *pc+=*pa+;while (pb=pb_last) *

4、pc+=*pb+;,小结,顺序存储结: 元素在存储器的位置关系也就是元素之间的逻辑关系； 是一种随机存取结构； 插入与删除运算涉及该元素表中位置之后的所有元素，效率很低下； 数据元素最大个数需预先确定； 存储空间不便于扩充。,练习,判断： 1线性表的逻辑顺序与存储顺序总是一致的。 2顺序存储的线性表可以按序号随机存取。 3顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。 4线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 6在线性

5、表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。,2.3线性表的链式表示和实现,用任意一组的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。 数据结构的存储被分为两个部分 数据本身的存储 数据元素和直接后继元素的逻辑关系 一个数据元素的存储称为结点，包含两个数据项： 数据域 指针域 以“结点的序列”表示线性表,线性表单链式存储结构的图示(1),a1,a2,ai,an ,H,以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。,线性表单链式存储结构的图示(2),a1,ai,an ,H,有时为了操作方便，在第一个结点之前虚加一个“头

6、结点”，以指向头结点的指针为链表的头指针。,链表在类C语言中的实现,typedef struct LNodeEelmType data;Struct LNode *next;Lnode, *LinkList; LinkList L; 假设P是指向线性表第i个元素的指针，则：P-next是指向第i+1个元素的指针；P-data是第i个元素本身aiP-next-data则是第i+1个元素本身ai+1,访问单链表的中的第 i 个元素,Status GetElem_L(LinkList L, int I, ,单链表的插入运算,a,b,P,x,S,S-next=P-next; P-next=S,插入算法

7、,Status ListInsert_L(LinkList ,单链表的删除运算,a,b,c,P,P-next = P-next-next;,删除算法,Status ListDelete_L(LinkList ,构造一个单链表,Void CreateList_L(linklist ,合并两个线性表,void MergeList_L(linklist ,静态链表,#define MAXSIZE 1000typedef struct ElemType data;int cur; component,SlinklistMAXSIZE; 地址就是数组下标； 以链表管理空余结点，自己构造malloc和free函数,2.3.2 循环链表,链表中最后一个结点的指针域指向头结点。 从任何一个结点出发均可遍历所有结点。,a1,an,H,H,2.3.3 双向链表,单链表无法从一个结点找到它的直接前驱结点 typedef struct DuLNode ElemType data;struc DuLNode *prior;struc DuLNode *next; DuLNode, *DuLinkList;,双向循环链表,L,L,删除一个结点,p,p-prior-next = p-next;