数据结构(C)第2章线性表.ppt

删除的位置i取值的正确范围的保障NCU-ZQP*当i1时：while()循环和if语句都不执行，却执行else语句输出提示：“\ni1,或i太大，不存在。当i=n时（n是假设的表长）：这是正确位置，p会指向最后一个数据结点，所以执行if语句进行结点删除，如图。当in：q会指向最后一个数据结点，而p为空，所以执行else语句输出提示：\ni1,或i太大，不存在。单链表插入和删除算法的时间复杂度分析在顺序存储结构的线性表中插入/删除一个元素时会大量移动数据元素，其时间复杂度为O(n)。而在链表中插入/删除一个元素时却不大量移动数据元素(只移动指针)，其时间复杂度可以视为O(1)。如果每个数据元素占用字节数比较多，链表结构在时间方面具有明显优势。但是，顺序结构可以直接存取，其时间复杂度可以视为O(1)。而链表结构则需设一指针从链表的开头向后查找，如果将指针的移动视为影响时间效率的主要因素，则时间复杂度可以视为O(n)。2.3.4单链表的其他运算NCU-ZQP*单链表除了上述两种基本运算外，还有其他一些不同的或较为复杂的运算。这些算法可以作为类的函数成员实现。主要介绍：根据数据元素的值进行插入/删除单链表的逆置两条单链表的合并1．根据数据元素的值进行插入/删除NCU-ZQP*在线性表中值为x的元素前插入一个值为y的数据元素。如果值为x的结点不存在，则将y插在表尾，如图。根据数据元素的值进行插入算法：NCU-ZQP*voidLinkList::insert2(ElemTypex,ElemTypey){NodeType*p,*q,*s;s=newNodeType;s-data=y;q=head;p=q-next;while((p!=NULL)(p-data!=x)){q=p；p=p-next;}//根据数据的值查找s-next=p;q-next=s;//插入新结点}根据数据元素的值进行删除NCU-ZQP*删除线性表中值为x的数据元素，输出“YES！”；如果x不存在，输出“NO！”。为了查找值为x的结点，设p从头找起；为了删除该结点，设q指向p的前驱结点；根据数据元素的值删除算法：NCU-ZQP*voidLinkList::delet2(ElemTypex){NodeType*p,*q;q=head;p=q-next;while((p!=NULL)(p-data!=x)//查找x结点{q=p;p++;}if(p==NULL)cout\nNO!endl;//x不存在，输出“NO！”else{q-next=p-next;//找到x结点，输出“YES！”deletep;//删除结点cout\nYES!endl;}}2．单链表的逆置NCU-ZQP*单链表的逆置方法不唯一。在此，介绍利用在头结点和与之相邻的数据结点之间不断插入后边元素结点的方法，来实现链表逆置，如图所示。链表逆置算法2.8：NCU-ZQP*voidLinkList::nizhi(){NodeType*h,*p,*q;h=Haed; //Haed是链表类的私有数据成员p=h-next;h-next=NULL;//暂时将头结点与后边数据结点断开while(p!=NULL)//不断地在头结点之后插入结点{q=p-next; p-next=h-next;h-next=p;p=q;}}1．在非递减有序表中插入一个数据元素x，使线性表仍保持非递减有序。算法2.3voidSqList::Insertdz(ElemTypex){inti=length-1;while(i=0elem[i]x){elem[i+1]=elem[i];i--;}elem[i+1]=x;//插入数据元素