线性表--链表-1

主要内容

1. 链表基础练习题

一.链表练习题

1.设计一个递归算法，删除不带头结点的单链表 L 中所有值为 X 的结点

代码如下（示例）:

设 f(L,x)的功能是删除以L为首结点指针的单链表中所有值等于x的结点，
显然有f(L->next,x)的功能是删除以L->next 为首结点指针的单链表中所有值等于x 的结点。
由此，可以推出递归模型如下。
终止条件:f(L，x)=不做任何事情;    若L为空表
递归主体:f(L,x)=删除*L结点;f(L->next,x); 若L->data==x
        f(L,x)=f(L->next,x);  其他情况
    
void Del_X_3(Linklist &L,ElemType x){
	//递归实现在单链表L中删除值为x的结点
	 LNode *p; //p指向待删除结点
	 if(L==NULL) //递归出口
	 	return;
	 if(L->data==x){ //若L所指结点的值为X
	 p=L; //删除*L，并
	 L=L->next;
	 free(p);
	 Del_X_3(L,x); //递归调用
	 }
	 else  //若L所指结点的值不为X
	 	Del_X_3(L->next,x);  //递归调用
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.设 L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值

代码如下（示例）:

void R Print(LinkList L){
//从尾到头输出单链表L中每个结点的值
	if(L->next!=NULL){ //递归
		R_Print(L->next);
		) //if
	if(L!=NULL) print(L->data); //输出函数
}
void R_Ignore_Head(LinkList L){
if(L->next!=NULL) R_Print(L->next);
}
1
2
3
4
5
6
7
8
9
10

3.试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为 O(1).

代码如下（示例）:

假设 pre、p和r指向3个相邻的结点，如下图所示。假设经过若干操作后，*pre 之前的结点的指针都已调整完毕，它们的 next 都指向其原前驱结点。现在令*p 结点的 next 域指向pre 结点，注意到一旦调整指针的指向，*p 的后继结点的链就会断开，为此需要用r 来指向原*p 的后继结点。处理时需要注意两点:一是在处理第一个结点时，应将其 next 域置为 NULL，而不是指向头结点(因为它将作为新表的尾结点);二是在处理完最后一个结点后，需要将头结点的指针指向它

1
2

LinkList Reverse(LinkList L){
//依次遍历线性表 L，并将结点指针反转
	INode *pre，*p=L->next，*r=p->next;
	p->next=NULL; //处理第一个结点
	while(r!=NULL){ //r为空，则说明p为最后一个结点
		pre=p; //依次继续遍历
		p=r;
		r=r->next;
		p->next=pre; //指针反转
	}
	L->next=p; //处理最后一个结点
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.有一个带头结点的单链表 L，设计一个算法使其元素递增有序。

代码如下（示例）:

算法思想:采用直接插入排序算法的思想，先构成只含一个数据结点的有序单链表，然后依次扫描单链表中剩下的结点*p (直至 p==NULL 为止)，在有序表中通过比较查找插入*p 的前驱结点*pre，然后将*p 插入到*pre 之后，如下图所示。
1

void Sort(LinkList &L)(
//本算法实现将单链表L的结点重排，使其递增有序
	LNode *p=L->next,*pre;
	LNode *r=p->next; //r保持*p后继结点指针，以保证不断链微
	p->next=NULL; //构造只含一个数据结点的有序表
	p=r;
	while(p!=NULL)(
		r=p->next; //保存*p的后继结点指针
		pre=L;
		while(pre->next!=NULL&&pre->next->data<p->data)
		pre=pre->next; //在有序表中查找插入*p的前驱结点*pre
		p->next=pre->next; //将*p插入到*pre之后
		pre->next=p;
		p=r; //扫描原单链表中剩下的结点
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.设计一个算法用于判断带头结点的循环双链表是否对称

代码如下（示例）:

算法思想:让 p从左向右扫描， 从右向左扫描，直到它们指向同一结点(p==g，当循环双链表中结点个数为奇数时)或相邻(p->next=g或g->prior=p，
当循环双链表中结点个数为偶数时)为止，若它们所指结点值相同，则继续进行下去，否则返回 0。若比较全部相等，则返回1。

int Symmetry(DLinkList L){
//本算法从两头扫描循环双链表，以判断链表是否对称
	DNode *p=L->next，*q=L->prior; //两头工作指针
	while(p!=q&&p->next!=g) //循环跳出条件
		if(p->data==q->data){ //所指结点值相同则继续比较
			p=p->next;
			q=q->prior;
		}
		else //否则，返回0
			return 0;
	return 1; //比较结束后返回1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.有两个循环单链表，链表头指针分别为 h1和h2，编写一个函数将链表 h2 链接到链表h1 之后，要求链接后的链表仍保持循环链表形式

代码如下（示例）:

算法思想:先找到两个链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，再使之成为循环的。

LinkList Link(linklist &hl,LinkList ah2){
//将循环链表h2链接到循环链表h1之后，使之仍保持循环链表的形式
	LNode *p，*q; //分别指向两个链表的尾结点
	p=h1;
	while(p->next!=h1) //寻找h1的尾结点
		p=p->next;
	q=h2;
	while(q->next!=h2) //寻找h2的尾结点
		q=q->next;
	p->next=h2; //将h2链接到h1之后
	q->next=h1; //令h2的尾结点指向 h1
	return hl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

总结

以上是今天要讲的内容，练习了链表相关习题。