数据结构线性表.ppt

2.3.2单线性链式的基本操作1建立单链表假设线性表中结点的数据类型是整型，以32767作为结束标志。动态地建立单链表的常用方法有如下两种：头插入法，尾插入法。⑴头插入法建表从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即每次插入的结点都作为链表的第一个结点。第28页，共74页，星期日，2025年，2月5日算法描述LNode*create_LinkList(void)/*头插入法创建单链表,链表的头结点head作为返回值*/{intdata;LNode*head,*p;head=(LNode*)malloc(sizeof(LNode));head-next=NULL;/*创建链表的表头结点head*/while(1){scanf(“%d”,data);if(data==32767)break;p=(LNode*)malloc(sizeof(LNode));p–data=data;/*数据域赋值*/第29页，共74页，星期日，2025年，2月5日p–next=head–next;head–next=p;/*钩链，新创建的结点总是作为第一个结点*/}return(head);}(2)尾插入法建表头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。第30页，共74页，星期日，2025年，2月5日算法描述LNode*create_LinkList(void)/*尾插入法创建单链表,链表的头结点head作为返回值*/{intdata;LNode*head,*p,*q;head=p=(LNode*)malloc(sizeof(LNode));p-next=NULL;/*创建单链表的表头结点head*/while(1){scanf(“%d”,data);if(data==32767)break;q=(LNode*)malloc(sizeof(LNode));q–data=data;/*数据域赋值*/q–next=p–next;p–next=q;p=q;第31页，共74页，星期日，2025年，2月5日/*钩链，新创建的结点总是作为最后一个结点*/}return(head);}无论是哪种插入方法，如果要插入建立的单线性链表的结点是n个，算法的时间复杂度均为O(n)。对于单链表，无论是哪种操作，只要涉及到钩链(或重新钩链)，如果没有明确给出直接后继，钩链(或重新钩链)的次序必须是“先右后左”。第32页，共74页，星期日，2025年，2月5日2单链表的查找(1)按序号查找取单链表中的第i个元素。对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。第33页，共74页，星期日，2025年，2月5日算法描述ElemTypeGet_Elem(LNode*L，inti){intj;LNode*p;p=L-next;j=1;/*使p指向第一个结点*/while(p!=NULLji){p=p–next;j++;}/*移动指针p,j计数*/if(j!=i)return(-32768);elsereturn(p-data);/*p为NULL表示i太大;ji表示i为0*/}移动指针p的频度：i1时：0次;i∈[1,n]：i-1次；in：n次。∴时间复杂度:O(n)。第34页，共74页，星期日，2025年，2月5日(2)按值查找按值查找是在链表中，查找是否有结点值等于给定值key的结点?若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。查找时从开始结点出发，沿