数据结构之链表课件

SCIE,UniversityofElectronicScienceandTechnologyofChina12.1线性表线性表不同的实现方式：2.1.1顺序表数组存储顺序表定义顺序表基本操作：

遍历、插入、删除

顺序表算法分析2.1.2单链表2.1.3双向链表链接存储2.1.4循环链表SCIE,UniversityofElectronicScienceandTechnologyofChina22.1线性表#include"stdio.h“structlist_seq{intdata[20];intlength;};intmain(){structlist_seqlist;intno,i;

list.length=0;for(i=0;i<10;i++){scanf("%d",&no);if(no==0)break;list.data[i]=no;list.length++;}no=30;insert(list,no,5);delete(list,8)return0;}SCIE,UniversityofElectronicScienceandTechnologyofChina32.1.2单链表一、链表的引入数组结构的缺点:1、在插入、删除时要移动大量的节点2、表的大小固定。 预先在申明数组时指定，无法更改原因：存放的连续性突破离散存放用指针来表示元素之间的关系。SCIE,UniversityofElectronicScienceandTechnologyofChina42.1.2单链表用链表实现线性表（非连续存储）线性表元素：a1、a2、a3、a4....链表链点线性关系：a1a2a3a4指针域，指针关系a1a2a3a4a1a2a3a4顺序存储链式存储SCIE,UniversityofElectronicScienceandTechnologyofChina52.1.2单链表二、

链表的定义

链点datalink元素域链接域数据域（数据元素域）：存放一个数据元素。链接域（关系域）：存放指向下一个元素的指针

——元素间的关系。数据域+链接域=结点（链点）SCIE,UniversityofElectronicScienceandTechnologyofChina62.1.2单链表链表a1a2an……由链点及链点相互间的链接构成head链表头链表尾链表长度（节点数目）taillength^SCIE,UniversityofElectronicScienceandTechnologyofChina72.1.2单链表定义structnode_type{ elemtypedata; structnode_type*next;};structlist_type{ node_type*head; node_type*tail; intlength;};链点的定义链表的定义datanext82.1.2单链表SCIE,UniversityofElectronicScienceandTechnologyofChina8带头节点的单链表a1an……head^带头节点链表的引入是为了使算法对空表和非空表的处理一致普通单链表对链表尾的判断(假定p是链表尾的指针)空表：p==null;非空表：p->next==null;带头节点单链表对链表尾的判断空表：p->next==null;非空表：p->next==null;SCIE,UniversityofElectronicScienceandTechnologyofChina92.1.2单链表初始化算法：elemtypeinitlist(node**h){ *h=(node*)malloc(sizeof(node)); (*h)->next=null;}三、链表的基本操作访问插入删除SCIE,UniversityofElectronicScienceandTechnologyofChina102.1.2单链表访问操作问题描述：访问链表的第i个节点问题分析：输入：链表，i输出：链点——指向链点的指针算法实现分析：只能从链表头开始，一个一个“数”下去，直到第i个。a1an……headtaila2temptemptempSCIE,UniversityofElectronicScienceandTechnologyofChina112.1.2单链表从自然语言到算法语言如何描述我们找到第i个节点的动作。1、先找到链表首结点的地址2、通过“地址”，找到链点3、在链点中找到后继元素的“地址”4、记录这个地址p=list->head;while(){}p->data……p=p->next;p->next……SCIE,UniversityofElectronicScienceandTechnologyofChina122.1.2单链表继续完善描述1、先找到链表首结点的地址2、通过“地址”，找到链点3、在链点中找到后继元素的“地址”4、记录这个地址，回到2p=list->head;while(1){}p->data……p=p->next;p->next……,计数，如果计数到i，就结束counter=1;counter++;if(counter==i)break;SCIE,UniversityofElectronicScienceandTechnologyofChina132.1.2单链表node_type*get_node(list,i){}while(counter<i&&p!=NULL){ counter=counter+1; p=p->next;}intcounter;node_type*p;returnp;if(p==NULL)returnNULL;p=list->head;counter=1;a1nextaiai+1anpa2逐个“数”的动作counter：123设i＝3当i>n时算法结果怎样？思考SCIE,UniversityofElectronicScienceandTechnologyofChina142.1.2单链表注意1、p=p->next;沿链表前进2、循环结束条件counter==i或node==NULLcounter>list->length思考如果希望获得值为x的元素，如何实现？while(p->data==x&&p!=NULL)SCIE,UniversityofElectronicScienceandTechnologyofChina152.1.2单链表链表插入操作问题描述：在元素ai前插入新的元素new_node;问题分析：输入：链表，location，x输出：插入新元素后的链表。算法实现分析SCIE,UniversityofElectronicScienceandTechnologyofChina162.1.2单链表a1aianheadtailai-1......anewa1aianheadtailai-1......anew两个步骤：

ai-1->next=anew;anew->next=ai;SCIE,UniversityofElectronicScienceandTechnologyofChina172.1.2单链表voidinsertl（list,new_node,location）｛｝找到ai-1执行插入动作两个步骤：ai-1->next=anew;anew->next=ai;SCIE,UniversityofElectronicScienceandTechnologyofChina182.1.2单链表while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}voidinsertl（list,new_node,location）｛｝找到ai-1p->next=new_node;new_node->next=???ai-1->next=anew;anew->next=ai;a1ai-1aianpnewnodea2p＝list->header;counter=1qq=p->next;q;法一SCIE,UniversityofElectronicScienceandTechnologyofChina192.1.2单链表while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}voidinsertl（list,new_node,location）｛｝new_node->next=p->next;p->next=new_node;a1ai-1aianpnewnodea2p＝list->header;counter=1法二SCIE,UniversityofElectronicScienceandTechnologyofChina202.1.2单链表voidinsertl（list,new_node,location）｛｝while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}new_node->next=p->next;p->next=new_node;counter=1;p=list->head;初始化list->length++;边界情况：

表首插入 表尾插入SCIE,UniversityofElectronicScienceandTechnologyofChina212.1.2单链表a1ai-1aianlist->headnewnodenew_node->next=a1;list->head;list->head=new_node;SCIE,UniversityofElectronicScienceandTechnologyofChina222.1.2单链表voidinsertl（list,new_node,location）｛｝while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}new_node->next=p->next;p->next=new_node;counter=1;p=list->head;初始化if(location==1){}else{}new_node=list->head;list->head=new_node;list->length++;边界情况：

表首插入 表尾插入SCIE,UniversityofElectronicScienceandTechnologyofChina232.1.2单链表a1ai-1aianlist->head注意当循环执行到表尾时p的值为NULL（空）p->next是悬空的值while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}new_node->next=p->next;p->next=new_node;p->next!=NULL){NULLp因此循环结束应以p->next==NULL为条件当i>链表长度时会造成系统崩溃表尾插入SCIE,UniversityofElectronicScienceandTechnologyofChina242.1.2单链表voidinsertl（list,new_node,location）｛｝while(counter<i-1&&p->next!=NULL){ counter=counter+1; p=p->next;}new_node->next=p->next;p->next=new_node;counter=1;p=list->head;if(location=

=1){}else{}new_node->next=list->head;list->head=new_node;list->length++;SCIE,UniversityofElectronicScienceandTechnologyofChina252.1.2单链表从插入算法中对链表操作的体会1、链表操作往往从表头开始，逐个找到需要的链点2、链表操作的有向性不能回退；3、链表指针小心使用，谨防丢失。4、不能访问空指针的成员5、插入过程没有进行链点内容进行搬移。SCIE,UniversityofElectronicScienceandTechnologyofChina262.1.2单链表链表的创建参见教材P15问题描述：根据输入的元素，生成一个链点，把它插入到链表头；逐个插入链点，形成链表链表的删除操作问题描述：删除元素ai;问题分析：输入：链表，location输出：删除元素后的链表。算法实现分析SCIE,UniversityofElectronicScienceandTechnologyofChina272.1.2单链表a1ai+1anheadtailai-1......aiai-1->next

=ai->next;即ai-1->next=

ai-1->next->next;SCIE,UniversityofElectronicScienceandTechnologyofChina282.1.2单链表｝找到ai-1执行删除动作ai-1->next=

ai-1->next->nextvoiddeletel（list,location）｛注意，从链表上取下的链点ai-1需要挂在一个指针上，否则可能丢失a1ai+1anheadtailai-1......aitempSCIE,UniversityofElectronicScienceandTechnologyofChina292.1.2单链表voiddeletel（list,location）｛｝while(counter<i-1&&p!=NULL){ counter=counter+1; p=p->next;}p->next=p->next->next;counter=1;p=list->head;初始化if(location==1){}else{}list->head=list->head->next;temp=p->next;free(temp);temp=list->head;free(temp);list->length--;从链表删除的链点，一般应该释放其空间SCIE,UniversityofElectronicScienceandTechnologyofChina302.1.2单链表注意:对被删除删除链点的处理往往需要要free（）SCIE,UniversityofElectronicScienceandTechnologyofChina312.1.2单链表四、链表的特点１、操作的顺序性有平均Ｎ／２次查找过程。２、离散存放不受链表大小限制不进行链点内容的搬移查找操作：数组效率优于链表插入、删除操作：链表效率优于数组

SCIE,UniversityofElectronicScienceandTechnologyofChina322.1.2单链表作业教材74页第9题（用链表实现）、第10题SCIE,UniversityofElectronicScienceandTechnologyofChina332.1.3双向链表特点：每一个链点包含两个指针，前趋指针后继指针a1……headtailNa2NPanPa1NPP：priorN：nextSCIE,UniversityofElectronicScienceandTechnologyofChina342.1.3双向链表一、双向链表的定义structdouble_link_node_type{ structdouble_link_node_type*prior; structdouble_link_node_type*next; elemtypedata;};structdouble_link_list_type{ dl_node_type*head; dl_node_type*tail; intlength;};链点的定义链表的定义SCIE,UniversityofElectronicScienceandTechnologyofChina352.1.3双向链表二、双向链表的插入操作ai-1ai问题描述：在第i个元素前插入新元素anewp2、anew->next=p;1、p->prior->next=anew;3、anew->prior=p->prior;4、p->prior=anew;