第3章链式存储结构.ppt

第3章 链式存储结构 第3章 链式存储结构 3.1线性表的链式存储结构 3.1.1 单链表上的基本运算 3.1.2 循环链表 3.1.3 双向链表 3.2线性表的顺序和链式存储结构的比较 3.3应用举例及分析 习题 单链表的数据结构： type struct node {char data; struct node *next }LINKLIST； 结点的申请、释放： 若LINKLIST head,*new；则可用： head=malloc (sizeof (LINKLIST))；申请结点 free (head); 释放结点 3.1.1单链表上的基本运算 一、建立单链表 假设线性表中结点的数据类型是字符，逐个输入这些字符型的结点，并以 ‘$’为输入结束标记。动态地建立单链表的常用方法有如下两种： 1、头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。算法如下： 2、尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。 算法如下： main( ) {LINKLIST * head , * last , * new ; Char ch ; new=malloc ( sizeof (LINKLIST )) ; head=new ; last=new ; new-next=NULL ; while ( ch=getchar (1) !=’$’) {new=malloc ( sizeof ( LINKLIST)) ; new-data=ch ; last-next=new ; last=new ; new-next=NULL ;} 二、查找运算 1、按序号查找第i个结点 在有头指针的单链表中找第i个结点，算法 为：设head为头，p为当前结点，0为头结点序号，i为计数器，则可使p依次下 移找结点，并使i同时递增记录结点号，找到返回结点地址，找不到返回NULL。 算法如下： LINKLIST *get ( int i , LINKLIST *head ) {int j=0 ; LINKLIST *p=head ; while (cji) (p-next !=NULL ) {p=p-next ; i++ ; } if (i= =j ) return p ; else return NULL ; } 2、按值查找 按值查找是在链表中，查找是否有结点值等于给定值x的结点，若有，则返回首次找到的其值为x的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值x作比较。 其查找流程及算法如下： 按值查找算法： LINKLIST * locate (Char x , LINKLIST * head ) {LINKLIST *p ;； p=head-next ; while ( p-data= = x ) return p ; else p=p-next ; } return NULL ; } 三、插入运算 插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化。 new=malloc ( )； new.data=x ； new.next=p-next ； p.next=new； 四、删除运算 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以首先找到ai-1的存储位置p，然后令p–next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，将其归还给“存储池”。 1、删除已知结点的后继结点 删除*p结点的后继结点示意图 2、在单链表上删除第i个元素 在单链表上删除第i个元素的算法： int delete node ( int ; LINKLIST * head ) { LINKLIST * p , *q ; int j , r ; r=1