软件技术与基础课件6

软件技术基础制作主讲段景山段景山线性结构链表的典型形态1.2.5链表的典型形态1、单链表如前所述2、带头节点的单链表头节点：是一个特殊的链点，数据内容无效链点指针指向链表头/////a1...头节点aian...a1an......ai头指针链表的典型形态带头节点的单链表几个容易混淆的概念第一个元素节点\头指针、头节点、链表头第一个元素节点是线性表关系中第一个元素——a1链表头是第一个链点，一般在链表的头部。头指针是指向第一个元素所在链点的指针头节点：是一个特殊的链点，数据内容无效，链点指针指向链表头链表的典型形态带头节点的单链表几个容易混淆的概念第一个元素节点、头指针、头节点、链表头a1ai+1anheadtailai-1......ai/////a1...aian...第一个元素节点、链表头第一个元素节点头指针头节点head链表的典型形态带头节点单链表的操作特点插入和删除算法不必考虑在表首进行时，需要更改头指针的特殊处理/////a1...aian...headp＝head；p->next=p->next->next;while(location>1&&p!=NULL){…}如果location为1,表首节点将被删除p为什么教材中使用**而教案中没有使用？教材中仅定义了链点，没有定义链表结构程序中调用的上下文不同typedef

structlist_type{ node_type*head; node_type*tail;

intlength;}list_type;headtaillengtha1a2为什么教材中使用**而教案中没有使用？教材voidmain（）{node*head;

createsl(&head);……}voidcreatesl(node**h){*h=firstnode;……}教案voidmain（）{

list_typelist;

create_l(&list);……}voidcreate_l(list_type*l){l->head=firstnode;……}headheadheadtaillengthheadtaillengtha1为什么教材中使用**而教案中没有使用？本质是一样的：要在函数调用中改变头指针的指向改变指针的指向，即改变指针变量的内容要改变指针的内容，必须将指针变量的地址传入教材中是将指针的地址传入－－指针的指针教案中将地址所在的结构的地址传入双向链表1.3双向链表特点：每一个链点包含两个指针，前趋指针后继指针a1……headtailNa2NPanPa1NPP：priorN：next双向链表1.3.1双向链表的定义typedef

structdouble_link_node_type{

structdouble_link_node_type*prior;

structdouble_link_node_type*next;

elemtypedata;}dl_node_type;typedef

structdouble_link_list_type{ dl_node_type*head; dl_node_type*tail;

intlength;}dl_list_type;链点的定义链表的定义双向链表插入1.3.2双向链表的插入操作ai-1NPaiNP问题描述：在第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指针法一：双向链表插入1.3.2双向链表的插入操作ai-1ai问题描述：在第i个元素前插入新元素anewp2、anew->next=p;1、p->prior->next=anew;3、anew->prior=p->prior;4、p->prior=anew;法二：双向链表插入1.3.2双向链表的插入操作ai-1ai问题描述：在第i个元素前插入新元素anewpp2、anew->next=p;3、anew->prior=p->prior;1、p->prior=anew;法三：在操作双向链表时同样要注意操作顺序双向链表插入算法实现（略）找到ai执行插入操作体会插入操作有多种方式实现，步骤比较复杂双向链表的使用灵活，可进可退思考：前面的四个步骤的组合顺序里，哪些是正确的，哪些是错误的？双向链表删除1.3.3双向链表的删除操作问题描述：删除第i个元素ai-1aiai＋1ppp（1）（2）（3）（1）当p在ai－1处时p->next->next->prior=p;p->next=p->next->next双向链表删除1.3.3双向链表的删除操作问题描述：删除第i个元素ai-1aiai＋1ppp（1）（2）（3）（2）当p在ai处时课堂作业请完成算法（3）当p在ai+1处时循环链表1.4循环链表a1ai+1anheadtailai-1......ai将链表头尾相接headerai+1antaila1...ai…对循环链表的遍历可以从任何一个节点开始上机练习题例１、读入一组数建立链表，以负数作为输入结束算法实现分析（１）如何读入一组数并以负数为结束建立框架：main(){ x＝0;初始化

while(x>=0){ read(&x)；

插入链表； }}read(int*x){

scanf(“data%d:“，x);}上机练习题（２）如何建立链表——新的元素以怎样的方式插入链表？每次插在表头或者每次插在表尾？决定每次插在表尾！new_node->next=list.tail->next;list.tail->next=new_node;（3）边界问题：第一个节点插入时list.header=new_node;list.tail=new_node;上机练习题list_type*create_list(){}初始化；while(x>=0){}read(&x);生成新元素插入新元素returnlist;上机练习题list_type*create_list(){list_typelist;list->length=0;list->header=NULL;list->tail=NULL;node_type*new_node;intx;x=0;while(x>=0){new_node=(node_type*)malloc(size_of(structnode_type));new_node->data=x;假设elemtype

就是整数类型new_node->next=NULL;生成新链点if(list.length<=0){

list.header=new_node;

list.tail=new_node;}else{ new_node->next=list.tail->next;

list.tail->next=new_node;}list.legth++;read(x);}return&list;}上机练习题例2、检查一个（单向）链表，删除其中数据大于100的元素算法实现分析（1）逐个检查链表的算法框架while(current!=NULL){ ...... current=current->next;}ai+1ai-1......aicurrent上机练习题(2)删除大于100的链点if(current->data>100){

删除该链点}必须找到current的前趋链点才能删除ai+1ai-1......aicurrentlastlast->next=current->next;free(current);current=last->next;删除不删除last=current;current=current->next;上机练习题(3)边界：第一个元素需要删除时if(last=

=NULL){ list->header=current->next; free(current); current=list->header;}ai+1a1...aicurrentlast上机练习题del_over100(list_type*list){}初始化while(current!=NULL){ if(current->data>100){

删除current; } else{

走向下一个链点；

}}voiddel_over100(list_type*list){last=NULL;current=list->header;if(last==NULL){ list->header=current->next; free(current); current=list->header;}else{ last->next=current->next; free(current); current=last->next;}else{ last=current; current=current->next;}while(current!=NULL){

if(current->data>100){}}//while结束}体会last指针的作用思考 如果是双向链表还是否需要last指针？上机练习题例3、将一个单向链表反向连接算法分析（1）逐个进行的基本框架（2）反向操作方法一：header1header2目标上机练习题a1方法二、直接在原链表的基础上操作a2a3a4a1a2a3a4ai-2ai-1aiai+1ai+2currentcontinuelastcurrent->next=lastlast=currentcurrent＝continuecontinue＝continue->next考虑首部的初始化以及尾部的处