软件技术与基础课件.ppt

《软件技术与基础课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件技术基础制作主讲段景山段景山线性结构链表的典型形态1.2.5链表的典型形态1、单链表如前所述2、带头节点的单链表头节点：是一个特殊的链点，数据内容无效链点指针指向链表头/////a1...头节点aian...a1an......ai头指针链表的典型形态带头节点的单链表几个容易混淆的概念第一个元素节点头指针、头节点、链表头第一个元素节点是线性表关系中第一个元素——a1链表头是第一个链点，一般在链表的头部。头指针是指向第一个元素所在链点的指针头节点：是一个特殊的链点，数据内容无效，链点指针指向链表头链表的典型形态带头节点的单链表几个容易混淆的概念第一个元素节点、头指针

2、、头节点、链表头a1ai+1anheadtailai-1......ai/////a1...aian...第一个元素节点、链表头第一个元素节点头指针头节点head链表的典型形态带头节点单链表的操作特点插入和删除算法不必考虑在表首进行时，需要更改头指针的特殊处理/////a1...aian...headp＝head；p->next=p->next->next;while(location>1&&p!=NULL){…}如果location为1,表首节点将被删除p为什么教材中使用**而教案中没有使用？教材中仅定义了链点，没有定义链表结构程序中调用的上下文不同typedefst

3、ructlist_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;……}headheadheadt

4、aillengthheadtaillengtha1为什么教材中使用**而教案中没有使用？本质是一样的：要在函数调用中改变头指针的指向改变指针的指向，即改变指针变量的内容要改变指针的内容，必须将指针变量的地址传入教材中是将指针的地址传入－－指针的指针教案中将地址所在的结构的地址传入双向链表1.3双向链表特点：每一个链点包含两个指针，前趋指针后继指针a1……headtailNa2NPanPa1NPP：priorN：next双向链表1.3.1双向链表的定义typedefstructdouble_link_node_type{structdouble_link_node_typ

5、e*prior;structdouble_link_node_type*next;elemtypedata;}dl_node_type;typedefstructdouble_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=

6、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

7、->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个