软件技术基础07-多种链表

软件技术基础线性结构——链表制作主讲段景山链表的典型形态请用5分钟快速阅读教材第9页至第12页。回答以下问题：什么是头结点？教材中的单链表插入算法与教案中的插入算法有什么大的区别——即头结点有什么用？链表的典型形态1.2.5链表的典型形态1、单链表如前所述2、带头节点的单链表头节点：是一个特殊的链点，数据内容无效链点指针指向链表头/////a1...头节点aian...a1an......ai头指针链表的典型形态带头节点的单链表几个容易混淆的概念第一个元素节点、头指针、头节点、链表头a1ai+1anheadtailai-1......ai/////a1...aian...第一个元素节点头指针头节点head第一个元素节点、链表头链表的典型形态带头节点单链表的操作特点插入和删除算法不必考虑在表首进行时，需要更改头指针的特殊处理——把第一元素链点地址记录在某个链点的next域内/////a1...aian...headp＝head；p->next=p->next->next;while(location>1&&p!=NULL){…}如果location为1,表首节点将被删除p为什么教材中使用**而教案中没有使用？链表的定义不同教材中仅定义了链点，没有定义链表结构，一个链表仅由一个头指针开始教案中还定义了链表结构在结构中除了有链表头指针，还有……typedefstructlist_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分钟的时间快速阅读教材第12页至15页，回答问题：链表还有哪些形式，有什么特点？双向链表1.3双向链表特点：每一个链点包含两个指针，前趋指针后继指针a1……headtailNa2NPanPa1NPP：priorN：next双向链表1.3.1双向链表的定义typedefstructdouble_link_node_type{ structdouble_link_node_type*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双向链表的插入操作问题描述：在第i个元素前插入新元素试试小纸片的方法能不能帮助思考ai-1NPaiNPanewNP50li55duan61yang66ma70liu61667050NULL44anewNULL66NULL505561head=55双向链表插入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个元素前插入新元素anewp2、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…对循环链表的遍历可以从任何一个节点开始循环链表例，将两个循环链表连接起来a1ai+1antail1ai-1......aib1tail2......node_type*merge_list(tail1,tail2){}tail1->next=tail2->next;tail2->next=tail1->next;???returntail2;temp=tail1->next;tail1->next=tail2->next;tail2->next=temp;扩展：静态链表“在数组内”的链表指针域不是真正的指针，而是记录后继元素在数组内的下标和我们的“小纸条”很相近liduanyangmaliu2340-101234作业作业：5、在一个从小到大按序排列的双向链表中，将新元