数据结构之线性表(2).ppt

VoidMergeList_L（LinkListLa,LinkListLb,LinkListLc）{pa=La-next;pb=Lb-next;Lc=pc=La;While（papb）if（pa-data=pb-data）{pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}pc-next=pa?pa:pb;//插入剩余段free（Lb）；//释放Lb的头结点}用上述定义的单链表实现线性表的操作时，存在的问题：3．单链表的表长是一个隐含的值；1．在单链表的最后一个元素之后插入元素时，需遍历整个链表；4．在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。2．在单链表中查找第i个元素需要顺序查找；重新定义线性链表的类型：增加“表长”、“表尾指针”和“当前位置的指针”三个数据域；将基本操作中的“位序i”改变为“指针p”。重新定义对线性链表的基本操作：五、带头尾指针结点的线性链表类型typedefstructLNode{//结点类型ElemTypedata;structLNode*next;}*Link,LNode;anaia1lenheadcurrenttail……lenheadcurrenttailtypedefstruct{//头结点类型Linkhead,tail;//分别指向头结点和//最后一个结点的指针intlen;//指示链表长度Linkcurrent;//指向当前被访问的结点//的指针，初始位置指向头结点}LinkList;基本操作:{结构初始化和销毁结构}StatusInitList(LinkListL);//构造一个空的线性链表L，其头指针、//尾指针和当前指针均指向头结点，//表长为零。StatusDestroyList(LinkListL);//销毁线性链表L，L不再存在。O(1)O(n){引用型操作}StatusListEmpty(LinkListL);//判表空intListLength(LinkListL);//求表长StatusPrior(LinkListL);//改变当前指针指向其前驱StatusNext(LinkListL);//改变当前指针指向其后继ElemTypeGetCurElem(LinkListL);//返回当前指针所指数据元素O(1)O(1)O(n)O(1)O(1)StatusLocatePos(LinkListL,inti);//改变当前指针指向第i个结点，//i=0时当前指针指向头结点。StatusLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//若存在与e满足函数compare()判定关系的元//素，则移动当前指针指向第1个满足条件的//元素的前驱，并返回OK;否则返回ERRORStatusListTraverse(LinkListL,Status(*visit)());//依次对L的每个元素调用函数visit()O(n)O(n)O(n){加工型操作}StatusClearList(LinkListL);//重置L为空表StatusSetCurElem(LinkListL,ElemTypee);//更新当前指针所指数据元素StatusAppend(LinkListL,Links);//在表尾结点之后链接一串结点StatusInsAfter(LinkListL,Elemtypee);