数据结构——基础7

2022-09-13 22:19 作者:技术龙的传人 0人读过 | 我要投稿

链表

练习题：已知一个带有表头结点的双向循环链表L，结点结构为prev data next，其中prev和
next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正
确的语句序列是（）
A p->next->prev = p->prev; p->prev->next = p->prev; free(p);
B p->next->prev = p->next; p->prev->next = p->next; free(p);
C p->next->prev = p->next; p->prev->next = p->prev; free(p);
D p->next->prev = p->prev; p->prev->next = p->next; free(p);

答：D

答：原始链表——c->a->e->b->d

插入后——c->a->f->e->b->d

选D

已知头指针h指向一个带头结点的非空单循环链表，结点结构为 data next，其
中next是指向直接后继结点的指针， p是尾指针， q是临时指针。现要删除该链
表的第一个元素，正确的语句序列是（）
A h->next = h->next->next; q = h->next; free(q);
B q = h->next; h->next = h->next->next; free(q);
C q = h->next; h->next = q->next; if(p != q) p=h; free(q);
D q = h->next; h->next = q->next; if(p == q) p=h; free(q);

答：D

设线性表L=(a1,a2,a3,…,an-2,an-1,an)采用带头结点的单链表保存，链表中的结点定义如下：

typedef struct node{
int data;
struct node *next;
}NODE;
请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=(a1,an,a2,an-1,a3,an-2,…)。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
3）说明你所设计的算法的时间复杂度。

答：1)

找到中间结点——>后半段逆置——>向前插入

2）

NODE *change(NODE *L){

NODE *p,*q,*r,*s;//q插入结点，s指向被插入点，r临时指向未插入结点头部

//步骤一：中间结点

p = q =L;

while(q->next == NULL){//p指向下一个，q下一个指向不为空指向下下一个

p = p->next;

q = q->next;

if(q->next == NULL) q = q->next;

}