软件技术基础07.pptx

链表的典型形态1.2.5 链表的典型形态1、单链表如前所述2、带头节点的单链表头节点：是一个特殊的链点，数据内容无效链点指针指向链表头/a1.头节点头节点aian.a1an.ai头指针头指针第1页/共31页链表的典型形态带头节点的单链表几个容易混淆的概念第一个元素节点头指针、头节点、链表头第一个元素节点是线性表关系中第一个元素a1链表头是第一个链点，一般在链表的头部。头指针是指向第一个元素所在链点的指针头节点：是一个特殊的链点，数据内容无效，链点指针指向链表头第2页/共31页链表的典型形态带头节点的单链表几个容易混淆的概念第一个元素节点、头指针、头节点、链表头a1ai+1anheadtailai-1.ai/a1.aian.第一个元素节点、链表头第一个元素节点、链表头第一个元素节点第一个元素节点头指针头指针头节点头节点head第3页/共31页链表的典型形态带头节点单链表的操作特点插入和删除算法不必考虑在表首进行时，需要更改头指针的特殊处理/a1.aian.headp p headhead；p-next=p-next-next;p-next=p-next-next;while(location 1&p!=NULL)while(location 1&p!=NULL)如果如果locationlocation为为1,1,表首节点将被删除表首节点将被删除p p第4页/共31页为什么教材中使用*而教案中没有使用？教材中仅定义了链点，没有定义链表结构程序中调用的上下文不同typedef struct list_typenode_type*head;node_type*tail;int length;list_type;headheadtailtaillengthlengtha1a1a2a2第5页/共31页为什么教材中使用*而教案中没有使用？教材教材void mainvoid main（）（）node*head;node*head;createsl(createsl(&head);head);void createsl(node*h)void createsl(node*h)*h=*h=first nodefirst node;教案教案void mainvoid main（）（）list_type list;list_type list;create_l(create_l(&list);list);void create_l(list_type*l)void create_l(list_type*l)l-head=l-head=first nodefirst node;headheadheadheadheadheadtailtaillengthlengthheadheadtailtaillengthlengtha1a1第6页/共31页为什么教材中使用*而教案中没有使用？本质是一样的：要在函数调用中改变头指针的指向改变指针的指向，即改变指针变量的内容要改变指针的内容，必须将指针变量的地址传入教材中是将指针的地址传入指针的指针教案中将地址所在的结构的地址传入第7页/共31页双向链表1.3双向链表特点：每一个链点包含两个指针，前趋指针后继指针a1headtailNa2NPanPa1NPP：priorN：next第8页/共31页双向链表1.3.1双向链表的定义typedef struct double_link_node_typestruct double_link_node_type*prior;struct double_link_node_type*next;elemtype data;dl_node_type;typedef struct double_link_list_typedl_node_type*head;dl_node_type*tail;int length;dl_list_type;链点的定义链点的定义链表的定义链表的定义第9页/共31页双向链表插入1.3.2 双向链表的插入操作ai-1NPaiNP问题描述：在第问题描述：在第i i个元素前插入新元素个元素前插入新元素anewNP1、anew-next=ai2、ai-1 -next=anew3、anew-prior=ai-14、ai-prior=anewpanew-next=p;p-prior-next=anew;anew-prior=p-prior;p-prior=anew;仅使用仅使用p p指针指针法一：法一：第10页/共31页双向链表插入1.3.2 双向链表的插入操作ai-1ai问题描述：在第问题描述：在第i i个元素前插入新元素个元素前插入新元素anewp2、anew-next=p;1、p-prior-next=anew;3、anew-prior=p-prior;4、p-prior=anew;法二：法二：第11页/共31页双向链表插入1.3.2 双向链表的插入操作ai-1ai问题描述：在第问题描述：在第i i个元素前插入新元素个元素前插入新元素anewpp2、anew-next=p;3、anew-prior=p-prior;1、p-prior=anew;法三：法三：在操作双向链表时在操作双向链表时同样要注意操作顺序同样要注意操作顺序第12页/共31页双向链表插入算法实现（略）找到ai执行插入操作体会插入操作有多种方式实现，步骤比较复杂双向链表的使用灵活，可进可退思考：前面的四个步骤的组合顺序里，哪些是正确的，哪些是错误的？第13页/共31页双向链表删除1.3.3 双向链表的删除操作问题描述：删除第i个元素ai-1aiai1ppp（1）（2）（3）（1）当p在ai1处时p-next-next-prior=p;p-next-next-prior=p;p-next=p-next-nextp-next=p-next-next第14页/共31页双向链表删除1.3.3 双向链表的删除操作问题描述：删除第i个元素ai-1aiai1ppp（1）（2）（3）（2）当p在ai处时课堂作业课堂作业请完成算法请完成算法（3）当p在ai+1处时第15页/共31页循环链表1.4循环链表a1ai+1anheadtailai-1.ai将链表头尾相接将链表头尾相接headerai+1antaila1.ai对循环链表的遍历可以从任何一个节点开始对循环链表的遍历可以从任何一个节点开始第16页/共31页上机练习题例、读入一组数建立链表，以负数作为输入结束例、读入一组数建立链表，以负数作为输入结束算法实现分析算法实现分析（）如何读入一组数并以负数为结束（）如何读入一组数并以负数为结束建立框架：main()x 0;初始化while(x=0)read(&x)；插入链表；read(int*x)scanf(“data%d:“，x);第17页/共31页上机练习题（）如何建立链表（）如何建立链表新的元素以怎样的方式新的元素以怎样的方式插入链表？插入链表？每次插在表头或者每次插在表尾？决定每次插在表尾！new_node-next=list.tail-next;list.tail-next=new_node;（3 3）边界问题：）边界问题：第一个节点插入时第一个节点插入时list.header=new_node;list.tail=new_node;第18页/共31页上机练习题list_type*create_list()初始化；while(x=0)read(&x);生成新元素插入新元素return list;第19页/共31页上机练习题list_type*create_list()list_type list;list-length=0;list-header=NULL;list-tail=NULL;node_type*new_node;int x;x=0;第20页/共31页while(x=0)new_node=new_node=(node_type*)malloc(size_of(struct node_type);(node_type*)malloc(size_of(struct node_type);new_node-data=x;假设elemtype 就是整数类型new_node-next=NULL;生成新链点生成新链点if(list.length next=list.tail-next;list.tail-next=new_node;list.legth+;read(x);return&list;第21页/共31页上机练习题例例2 2、检查一个（单向）链表，删除其中数据大于、检查一个（单向）链表，删除其中数据大于100100的元素的元素算法实现分析算法实现分析（1 1）逐个检查链表的算法框架）逐个检查链表的算法框架while(current!=NULL).current=current-next;ai+1ai-1.aicurrent第22页/共31页上机练习题(2)(2)删除大于删除大于100100的链点的链点if(current-data 100)if(current-data 100)删除该链点删除该链点 必须找到必须找到currentcurrent的前趋链点才能删除的前趋链点才能删除ai+1ai-1.aicurrentlastlast-next=current-next;free(current);current=last-next;删除删除不删除不删除last=current;current=current-next;第23页/共31页上机练习题(3)(3)边界：第一个元素需要删除时边界：第一个元素需要删除时if(last=NULL)list-header=current-next;free(current);current=list-header;ai+1a1.aicurrentlast第24页/共31页上机练习题del_over100(list_type*list)初始化while(current!=NULL)if(current-data 100)删除current;else走向下一个链点；第25页/共31页voidvoid del_over100(list_type*list)del_over100(list_type*list)last=NULL;last=NULL;current=list-header;current=list-header;if if(last=NULL)(last=NULL)list-header=current-next;list-header=current-next;free(current);free(current);current=list-header;current=list-header;elseelse last-next=current-next;last-next=current-next;free(current);free(current);current=last-next;current=last-next;elseelse last=current;last=current;current=current-next;current=current-next;whilewhile(current!=NULL)(current!=NULL)if if(current-data 100)(current-data 100)/whilewhile结束结束 第26页/共31页体会last指针的作用思考如果是双向链表还是否需要last指针？第27页/共31页上机练习题例3、将一个单向链表反向连接算法分析（1）逐个进行的基本框架（2）反向操作方法一：header1header2目标第28页/共31页上机练习题a1方法二、直接在原链表的基础上操作a2a3a4a1a2a3a4ai-2ai-1aiai+1ai+2currentcontinuelastcurrent-next=lastlast=currentcurrent continuecontinue continue-next考虑首部的初始化 以及尾部的处理第29页/共31页上机练习题void invert_list(list_type*list)last=NULL;current=list-header;continue=current;while(current!=NULL)continue=current-next;current-next=last;last=current;current=continue;list-tail=list-header;list-header=last;第30页/共31页感谢您的观看！第31页/共31页