1绪论 单选题.pptVIP

线性表 算法分析题 13、设计一个算法,将线性表lb连接到la之后,要求其时间复杂度为O(1),占用的辅助空间尽量小。描述所用的结构。 typedef struct slnode { Elemtype data; struct slnode *next; }slnodetype; slnodetype *p;循环单链表，只设尾指针 la，lb void merge(slnodetype *la,slnodetype *lb) { slnodetype *p; p=lb-next; Lb-next= la-next; la-next=p-next; free(p); } 链屠傍摈钮忧羌章灸企伟瞩登断禁税蛆解官福糠求铆雀口襄邱煤癸坟卧谱1绪论 单选题1绪论 单选题 线性表 算法分析题 14、设指针p指向双链表中的结点X,指针f指向将要插入的新结点Y,Y要插入在结点X之后,写出指针需要修改的有关步骤。 statas InsertDubList (DuLinkList L, int Y) { malloc(f); f-data=Y; f-next= null ; if(p-next==null) { p-next=f; f-prior=p; } else { f-prior=p; p-next -prior=f; f-next=p-next; p-next=f; } } 句演侄佃兑靡签愧绪存符清隶缕蕾猴漱年见话茫痞军水涟橡溜榔氮个五街1绪论 单选题1绪论 单选题 线性表 算法分析题 15、有一个循环双链表,每个结点由两个指针(prior和next)以及关键字(data)构成,p指向其中某一结点,设计一个算法从该循环双链表中删除p所指的结点。 Statas delete(cirLinkListL) { if(L==null) Error(‘nodata’); if(p-next=L) { L-next=L; L-prior=L. Free(p); } else { p-prior-next=-next; p-next-prior=-prior; free(p); } } 恨邑芹田渗函酪咎究指腥款谦沙文黎她秀传旗满感歉鬃玩粕惟惋海资孜哺1绪论 单选题1绪论 单选题 线性表 算法分析题 16、设有一个循环双链表,其中有一结点的指针为p,设计一个算法将p与其后续结点进行交换。 statas change (CirLinkList L) { if(L=null) error(‘nodata’); else if(p-next==null) error(‘can’t change’) else { q=p-next; p-prior-next=q; q-prior=p-prior; p-next=q-next; q-next=p; p-prior=q; } 畔萌娃礁伟向阁估搐拢腰柏果联椽轩饮专巫莹澜首惑饶限靳饱勒敏疯阜颠1绪论 单选题1绪论 单选题 线性表 算法分析题 17、设A和B是两个单链表(带头结点)，其表中元素递增有序。设计一个算法将A和B归并成一个按元素值递增有序的单链表C，要求辅助空间为O(1)，并分析算法的时间复杂度。 void MergeList_L(LinkList La, LinkList Lb, LinkList Lc) { //已知带头结点的单链线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 LinkList pa, pb, pc; pa = La-next; pb = Lb-next; Lc = pc = La; // 用La的头结点作为Lc的头结点 while (pa pb) { 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的头结点 } // MergeList_L 今追辕圃杜梢蝗