第三章 线性表的链式存储结构教案.doc

第3章 线性表的链式存储结构 线性表的链式存储结构 线性表的应用举例 线性表顺序存储结构的特点 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。 暴露的问题 在做插入或删除元素的操作时，会产生大量的数据元素移动； 对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用； 线性表的容量难以扩充。 第一节 线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图所示的形式存储： 存储地址 内容 直接后继存储地址 100 b 120 ... ... ... 120 c 160 ... ... .. 144 a 100 ... ... ... 160 d NULL ... ... ... 术语 表示每个数据元素的两部分信息组合在一起被称为结点； 其中表示数据元素内容的部分被称为数据域（data）； 表示直接后继元素存储地址的部分被称为指针或指针域（next）。 单链表简化的图形描述形式 其中，head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（^）符号表示。 带头结点的单链表 为了简化对链表的操作，人们经常在链表的第一个结点之前附加一个结点，并称为头结点。这样可以免去对链表第一个结点的特殊处理。如下图所示： 链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。 在C语言中，实现线性表的链式存储结构的类型定义 typedef strcut node{ //结点类型 EntryType item; struct node *next; }NODE; typedef struct{ //链表类型 NODE *head; }LINK_LIST; 典型操作的算法实现 （1）初始化链表L int InitList(LINK_LIST *L) { L-head=(*NODE)malloc(sizeof(NODE)); //为头结点分配存储单元 if (L-head) {L-head-next=NULL; return OK;} else return ERROR ; } （2）销毁链表L void DestoryList(LINK_LIST *L) { NODE *p; while (L-head){ //依次删除链表中的所有结点 p=L-head; L-head=L-head-next; free(p); } } （3）清空链表L void ClearList(LINK_LIST *L) { NODE *p; while (L-head-next){ p=L-head-next; //p指向链表中头结点后面的第一个结点 L-head-next=p-next; //删除p结点 free(p); //释放p结点占据的存储空间 } } （4）求链表L的长度 int ListLength(LINK_LIST L) { NODE *p; int len; for(p=L.head, len=0;p-next==NULL; p=p-next,len++); return(len); } （5）判链表L空否。 int IsEmpty(LINK_LIST L) { if (L.head-next==NULL) return TRUE; else return FALSE; } （6）通过e返回链表L中第i个数据元素的内容 void GetElem(LINK_LIST L,int i,EntryType *e) { NODE *p; int j; if (i1||iListLength(L)) exit ERROR; //检测i值的合理性