软件技术基础.pptx

,段景山,#,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,软件技术基础,制作,主讲,段景山,段景山,线性结构,链接存储的线性表,1.2,、链接存储的线性表（链表）的定义,1.2.1,、链表的引入,数组结构的缺点,:,1,、在插入、删除时要移动大量的节点,2,、表的大小固定。,预先在申明数组时指定，无法更改,原因：,存放的连续性,突破,离散存放,用指针来表示元素之间的关系,。,链接存储的线性表,用链表实现线性表（非连续存储）,线性表元素：,a1,、,a2,、,a3,、,a4.,链表链点,线性关系：,a1,a2,a3,a4,指针域，指针关系,链表的定义,1.2.2,链表的定义,链点,data,link,元素域,链接域,元素域（数据元素域）：存放一个数据元素。,链接域（关系域）：存放指向下一个元素的指针,元素间的关系。,元素域,+,链接域,=,结点（链点）,链表的定义,链表,a,1,a,2,a,n,由链点及链点相互间的链接构成,head,链表头,链表尾,链表长度（节点数目）,tail,length,链表的定义,定义,typedef struct node_type,elemtype data;,struct node_type*next;,node_type;,typedef struct list_type,node_type*head;,node_type*tail;,int length;,list_type;,链点的定义,链表的定义,data,next,元素值的类型，如：,int,整形,char,字符型,long,长整形,链表的定义,链表组织：,list_type*list;,list-head=a1;,a1-next=a2;,a2-next=a3;,an-next=NULL,list-tail=an;,list-length=n;,a,1,a,2,a,n,head,tail,NULL,，表示指针的值为“空”，即指针指向空处,链表的基本操作,1.2.3,链表的基本操作,访问,插入,删除,链表的基本操作,访问操作,问题描述：访问链表的第,i,个节点,问题分析：,输入：链表，,i,输出：链点,指向链点的指针,算法实现分析：,a,1,a,2,a,n,head,tail,只能从链表头开始，一个一个,“,数,”,下去，直到第,i,个。,temp,temp,temp,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,时算法结果怎样？,思考,访问操作,注意,1、,p=p-next;,沿链表前进,2,、循环结束条件,counter=i,或,node=NULL,counter list-length,思考,如果希望获得值为,x,的元素，如何实现？,while(p-data=x&p!=NULL),插入操作,链表插入操作,问题描述：,在元素,ai,前插入新的元素,new_node;,问题分析：,输入：链表，,location,，,x,输出：插入新元素后的链表。,算法实现分析,插入操作,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,;,插入操作,void insertl,（,list,new_node,location,）,找到,a,i-1,执行插入动作,两个步骤：,a,i-1,-next=a,new,;,a,new,-next=a,i,;,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;,法一,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,法二,插入操作,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+;,边界情况：,表首插入,表尾插入,插入操作,a,1,a,i-1,a,i,a,n,list-head,new,node,new_node-next=a1;,list-head;,list-head=new_node;,插入操作 表首插入,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+;,边界情况：,表首插入,表尾插入,插入操作 表尾插入,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,链表长度 时,会造成系统崩溃,插入操作,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+;,从插入算法中对链表操作的体会,1,、链表操作往往从表头开始，逐个找到需要的链点,2,、链表操作的有向性,不能回退；,3,、链表指针小心使用，谨防丢失。,4,、插入过程没有进行链点内容进行搬移。,链表的创建,链表的创建,从链点的生成过程中体会动态内存申请的动作,creat_list(list,x),new_node=malloc(sizeof(node_type);,new_node-data=x;,new_node-next=NULL;,new_node-next=list_head;,list-head=new_node;,问题描述：根据输入的元素，生成一个链点，,并把它插入到链表头,删除操作,链表的删除操作,问题描述：删除元素,a,i,;,问题分析：,输入：链表，,location,输出：删除元素后的链表。,算法实现分析,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;,删除操作,找到,a,i-1,执行删除动作,a,i-1,=,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,删除操作,void,deletel,（,list,location,）,while,(counter 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-;,从链表删除的链点，一般应该释放其空间,删除操作,注意,:,对删除链点的处理,往往需要要,free,（）,思考,如果希望删除值为,x,的元素，如何实现？,while(p-data=x&p!=NULL),1.2.4,链表的特点,、操作的顺序性,有平均次查找过程。,、离散存放,不受链表大小限制,不进行链点内容的搬移,查找操作：数组效率优于链表,插入、删除操作：链表效率优于数组,链表的特点,作业,教材,70,页第,9,题、第,10,题,