数据结构之链表

,EI Dept.,Huazhong University of Science and Technology,*,SCIE,University of Electronic Science and Technology of China,1,2.1,线性表,线性表不同的实现方式：,2.1.1,顺序表 数组存储,顺序表定义,顺序表基本操作：,遍历、插入、删除,顺序表算法分析,2.1.2,单链表,2.1.3,双向链表 链接存储,2.1.4,循环链表,SCIE,University of Electronic Science and Technology of China,2,2.1,线性表,#include stdio.h“,struct list_seq,int data20;,int length;,;,int main(),struct list_seq list;,int no,i;,list.length=0;,for(i=0;inext=null;,带头节点单链表对链表尾的判断,空表：,p-next=null;,非空表：,p-next=null;,SCIE,University of Electronic Science and Technology of China,9,2.1.2,单链表,初始化算法：,elemtype initlist(node*h),*h=(node*)malloc(sizeof(node);,(*h)-next=null;,三、链表的基本操作,访问,插入,删除,SCIE,University of Electronic Science and Technology of China,10,2.1.2,单链表,访问操作,问题描述：访问链表的第,i,个节点,问题分析：,输入：链表，,i,输出：链点,指向链点的指针,算法实现分析：,只能从链表头开始，一个一个,“,数,”,下去，直到第,i,个,。,a,1,a,n,head,tail,a,2,temp,temp,temp,SCIE,University of Electronic Science and Technology of China,11,2.1.2,单链表,从自然语言到算法语言,如何描述我们找到第,i,个节点的动作。,1,、先找到链表首结点的地址,2,、通过“地址”，找到链点,3,、在链点中找到后继元素的“地址”,4,、记录这个地址,p=list-head;,while(),p-data,p=p-next;,p-next,SCIE,University of Electronic Science and Technology of China,12,2.1.2,单链表,继续完善描述,1,、先找到链表首结点的地址,2,、通过“地址”，找到链点,3,、在链点中找到后继元素的“地址”,4,、记录这个地址，,回到,2,p=list-head;,while(1),p-data,p=p-next;,p-next,计数，如果计数到,i,，就结束,counter=1;,counter+;,if(counter=i),break;,SCIE,University of Electronic Science and Technology of China,13,2.1.2,单链表,node_type*get_node(list,i),while(counter next;,int counter;,node_type*p;,return p;,if(p=NULL)return NULL;,p=list-head;,counter=1;,a,1,next,a,i,a,i+1,a,n,p,a,2,逐个“数”的动作,counter,：,1,2,3,设,i,3,当,in,时算法结果怎样？,思考,SCIE,University of Electronic Science and Technology of China,14,2.1.2,单链表,注意,1、,p=p-next;,沿链表前进,2,、循环结束条件,counter=i,或,node=NULL,counter list-length,思考,如果希望获得值为,x,的元素，如何实现？,while(p-data=x&p!=NULL),SCIE,University of Electronic Science and Technology of China,15,2.1.2,单链表,链表插入操作,问题描述：,在元素,ai,前插入新的元素,new_node;,问题分析：,输入：链表，,location,，,x,输出：插入新元素后的链表。,算法实现分析,SCIE,University of Electronic Science and Technology of China,16,2.1.2,单链表,a,1,a,i,a,n,head,tail,a,i-1,.,.,a,new,a,1,a,i,a,n,head,tail,a,i-1,.,.,a,new,两个步骤：,a,i-1,-next=a,new,;,a,new,-next=a,i,;,SCIE,University of Electronic Science and Technology of China,17,2.1.2,单链表,void insertl,（,list,new_node,location,）,找到,a,i-1,执行插入动作,两个步骤：,a,i-1,-next=a,new,;,a,new,-next=a,i,;,SCIE,University of Electronic Science and Technology of China,18,2.1.2,单链表,while(counter next;,void insertl,（,list,new_node,location,）,找到,a,i-1,p-next=new_node;,new_node-next=,?,a,i-1,-next=a,new,;,a,new,-next=a,i,;,a,1,a,i-1,a,i,a,n,p,new,node,a,2,p,list-header;counter=1,q,q,=p-next;,q,;,法一,SCIE,University of Electronic Science and Technology of China,19,2.1.2,单链表,while(counter next;,void insertl,（,list,new_node,location,）,new_node-next=p-next;,p-next=new_node;,a,1,a,i-1,a,i,a,n,p,new,node,a,2,p,list-header;counter=1,法二,SCIE,University of Electronic Science and Technology of China,20,2.1.2,单链表,void insertl,（,list,new_node,location,）,while(counter next;,new_node-next=p-next;,p-next=new_node;,counter=1;,p=list-head;,初始化,list-length+;,边界情况：,表首插入,表尾插入,SCIE,University of Electronic Science and Technology of China,21,2.1.2,单链表,a,1,a,i-1,a,i,a,n,list-head,new,node,new_node-next=a1;,list-head;,list-head=new_node;,SCIE,University of Electronic Science and Technology of China,22,2.1.2,单链表,void insertl,（,list,new_node,location,）,while(counter 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,University of Electronic Science and Technology of China,23,2.1.2,单链表,a,1,a,i-1,a,i,a,n,list-head,注意当循环执行到表尾时,p,的值为,NULL,（空）,p-next,是悬空的值,while(counter next;,new_node-next=p-next;,p-next=new_node;,p-next!=NULL),NULL,p,因此循环结束应以,p-next=NULL,为条件,当,i,链表长度 时,会造成系统崩溃,表尾插入,SCIE,University of Electronic Science and Technology of China,24,2.1.2,单链表,void insertl,（,list,new_node,location,）,while(counter 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,University of Electronic Science and Technology of China,25,2.1.2,单链表,从插入算法中对链表操作的体会,1,、链表操作往往从表头开始，逐个找到需要的链点,2,、链表操作的有向性,不能回退；,3,、链表指针小心使用，谨防丢失。,4,、不能访问空指针的成员,5,、插入过程没有进行链点内容进行搬移。,SCIE,University of Electronic Science and Technology of China,26,2.1.2,单链表,链表的创建,参见教材,P15,问题描述：根据输入的元素，生成一个链点，,把它插入到链表头；逐个插入链点，形成链表,链表的删除操作,问题描述：删除元素,a,i,;,问题分析：,输入：链表，,location,输出：删除元素后的链表。,算法实现分析,SCIE,University of Electronic Science and Technology of China,27,2.1.2,单链表,a,1,a,i+1,a,n,head,tail,a,i-1,.,.,a,i,a,i-1,-next,=a,i,-next;,即,a,i-1,-next=,a,i-1,-next-next;,SCIE,University of Electronic Science and Technology of China,28,2.1.2,单链表,找到,a,i-1,执行删除动作,a,i-1,-next=,a,i-1,-next-next,void deletel,（,list,location,）,注意，从链表上取下的链点,a,i-1,需要挂在一个指针上，,否则可能丢失,a,1,a,i+1,a,n,head,tail,a,i-1,.,.,a,i,temp,SCIE,University of Electronic Science and Technology of China,29,2.1.2,单链表,void de