2024 王道考研-数据结构（线性表_2）

第二章 线性表算法题(线性表的链式存储)

二、综合应用题

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)
{
	LNode *p;//p指向待删除结点 
	if(L==NULL)//递归出口 
		return;
	if(L->data==x)//若L所指结点的值为x 
	{
		p=L;//删除*L,并让L指向下一个结点 
		L=L->next;
		free(p);
		Del_X_3(L,x);//递归调用 
	}
	else//若L所指结点的值不为x 
	{
		Del_X_3(L->next,x);//递归调用 
	}
}

2.在带头结点的单链表L中，删除所有值为x的结点，并释放其空间，假设值为x的结点不唯一，试编写算法以实现上述操作。

算法思想：用p从头至尾扫描单链表，pre指向*p结点的前驱。若p所指结点的值为x,则删除，并让p移向下一个结点，否则让pre、p指针同步后移一个结点。

void Del_X_1(LinkList &L,ElemType x)
{
	LNode *p=L->next,*pre=L,*q;//置p和pre的初始值 
	while(p!=NULL)
	{
		if(p->data==x)
		{
			q=p;//q指向被删结点 
			p=p->next;
			pre->next=p;//将*q结点从链表中断开 
			free(q);//释放*q结点的空间	
		}
		else//否则，pre和p同步后移 
		{
			pre=p;
			p=p->next;	
		}	
	}	
} 

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

void R_Print(LinkList L)
{
	if(L->next!=NULL)
	{
		R_Print(L->next);//递归 
	}
	if(L!=NULL)
		print(L->data);//输出函数 
}
void R_Ignore_Head(LinkList L)
{
	if(L->next!=NULL)
		R_Print(L->next);
}

4.试编写在头结点的单链表L中删除一个最小值结点的高效算法(假设最小值结点是唯一的)。

算法思想：用p从头至尾扫描单链表，pre指向*p结点的前驱，用minp保存值最小的结点指针（初值为p),minpre指向*minp结点的前驱（初值为pre）。一边扫描，一边比较，若p->data小于minp->data,则将p、pre分别赋值给minp、minpre。当p扫描完毕时，minp指向最小值结点，minpre指向最小值结点的前驱结点，再将minp所指结点删除即可。

LinkList Delete_Min(LinkList &L)
{
	LNode *pre=L,*p=pre->next;//p为工作指针，pre指向其前驱
	LNode *minpre=pre,*minp=p;//保存最小值结点及其前驱 
	while(p!=NULL)
	{
		if(p->data<minp->data)
		{
			minp=p;//找到比之前找到的最小值结点更小的结点 
			minpre=pre;	
		}
		pre=p;//继续扫描下一个结点 
		p=p->next;	
	}
	minpre->next=minp->next;//删除最小值结点 
	free(minp);
	return L;	
} 

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

算法思想：将头结点摘下，然后从第一结点开始，依次插入到头结点的后面（头插法建立单链表），直到最后一个结点为止，这样就实现了链表的逆置。

LinkList Reverse(LinkList L)
{
	LNode *p,*r;//p为工作指针，r为p的后继，以防断链 
	p=L->next;//从第一个元素结点开始 
	L->next=NULL;//先将头结点L的next域值为NULL 
	while(p!=NULL)//依次将元素结点摘下 
	{
		r=p->next;//暂存p的后继 
		p->next=L->next;//将p结点插入到头结点之后 
		L->next=p;
		p=r;
	}
	return L;	
}

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

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

void Sort(LinkList &L)
{
	LNode *p=L->next,*pre;//r保持*p后继结点指针，以保证不断链 
	LNode *r=p->next;//构造只含一个数据结点的有序表 
	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;//扫描原单链表中剩下的结点 
	} 
}

7.设在一个带表头结点的单链表中所有元素结点的数据值无序，试编写一个函数，删除表中所有介于给定的两个值（作为函数参数给出）之间的元素（若存在）。

算法思想：因为链表是无序的，所以只能逐个结点进行检查，执行删除。

void RangeDelete(LinkList &L,int min,int max)
{
	LNode *pr=L,*p=L->link;//p是检测指针，pr使其前驱 
	while(p!=NULL)
	{
		if(p->data>min&&p->data<max)//寻找到被删结点，删除 
		{
			pr->link=p->link;
			free(p);
			p=pr->link;
		}
		else//否则继续寻找被删结点 
		{
			pr=p;
			p=p->link;
		}
	}
}

8.给定两个单链表，编写算法找出两个链表的公共结点。

LinkList Search_1st_Common(LinkList L1,LinkList L2)
{
	int dist;
	int len1=Length(L1),len2=Length(L2);//计算两个链表的表长
	LinkList longList,shortList;//分别指向表长较长和较短的链表
	if(len1>len2)//L1表长较长 
	{
		longList=L1->next;
		shortList=L2->next;
		dist=len1-len2;	//表长之差 
	} 
	else//L2表长较长
	{
		longList=L2->next;
		shortList=L1->next;
		dist=len2-len1;	//表长之差 
	} 
	while(dist--)//表长的链表先遍历到第dist个结点，然后同步 
		longList=longList->next;
	while(longList!=NULL)//同步寻找共同结点 
	{
		if(longList==shortList)//找到第一个公共结点 
			return longList;
		else//继续同步寻找 
		{
			longList=longList->next;
			shortList=shortList->next;
		}
	}
	return NULL;
}

9.给定一个带表头结点的单链表,设head为头指针，结点结构为（data,next）,data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）。

算法思想：对链表进行遍历，在每次遍历中找出整个链表的最小值元素，输出并释放结点所占空间，再次查找次小值元素，输出并释放空间，如此下去，直至链表为空，最后释放头结点所占存储空间。

void Min_Delete(LinkList &head)
{
	while(head->next!=NULL)//循环到仅剩头结点 
	{
		LNode *pre=head;//pre为元素最小值结点的前驱结点的指针 
		LNode *p=pre->next;//p为工作指针 
		Lnode *u;//指向被删除结点 
		while(p->next!=NULL)
		{
			if(p->next->data<pre->next->data)
				pre=p;//记住当前最小值结点的前驱 
			p=p->next;
		}
		print(pre->next->data);//输出元素最小值结点的数据 
		u=pre->next;//删除元素值最小的结点，释放结点空间 
		pre->next=u->next;
		free(u);
	}
	free(head);//释放头结点 
}

10.将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对顺序不变。

算法思想：设置一个访问序号变量（初值为0）,每访问一个结点序号自动加1，然后根据序号的奇偶性将结点插入到A表或B表中。重复以上操作直到表尾。

LinkList DisCreat_1(LinkList &A)
{
	int i=0;//i记录表A中结点的序号 
	LinkList B=(LinkList)malloc(sizeof(LNode));//创建B表表头 
	B->next=NULL;//B表的初始化 
	LNode *ra=A,*rb=B,*p;//ra和rb将分别指向将创建的A表和B表的尾结点 
	p=A->next;//p为链表工作指针，指向待分解的结点 
	A->next=NULL;//置空新的A表 
	while(p!=NULL)
	{
		i++;//序号加1 
		if(i%2==0)//处理序号为偶数的链表结点 
		{
			rb->next=p;//在B表插入新结点 
			rb=p;//rb指向新的尾结点 
		}
		else//处理序号为奇数的链表结点 
		{
			ra->next=p;//在A表插入新结点
			ra=p;//ra指向新的尾结点 
		}
		p=p->next;//将p恢复为指向新的待处理结点 
	}
	ra->next=NULL;
	rb->next=NULL;
	return B;
}

11.设C={a1,b1,a2,b2,...,an,bn}为线性表，采用带头结点的单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1,a2,...,an},B={bn,...,b2,b1}。

算法思想：采用上题的思路，不设序号变量。二者的差别仅在于对B表建立不采用尾插法，而是采用头插法。

LinkList DisCreat_2(LinkList &A)
{
	LinkList B=(LinkList)malloc(sizeof(LNode));//创建B表表头 
	B->next=NULL;//B表的初始化 
	LNode *p=A->next,*q;//p为工作指针 
	LNode *ra=A;//ra始终指向A的尾结点 
	while(p!=NULL)
	{
		ra->next=p;
		ra=p;//将*p链到A的表尾 
		p=p->next;
		if(p!=NULL)
		{
			q=p->next;//头插后，*p将断链，因此用q记忆*p的后继 
			p->next=B->next;//将*p插入到B的前端 
			B->next=p;
			p=q;	
		}	
	} 
	ra->next=NULL;//A表结点的next域置空 
	return B;
}

12.在一个递增有序的现行标准中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素，例如（7，10，10，21，30，42，42，42，51，70）将变为（7，10，21，30，42，51，70）。

算法思想：由于是有序表，所有相同值域的结点都是相邻的。用p扫描递增单链表L,若*p结点等于其后继结点的值域，则删除后者，否则p移向下一个结点。

void Del_Same(LinkList &L)
{
	LNode *p=L->next,*q;//p为扫描工作指针 
	if(p==NULL)
		return;
	while(p->next!=NULL)
	{
		q=p->next;//q指向*p的后继结点 
		if(p->data==q->data)//找到重复值的结点 
		{
			p->next=q->next;//释放*q结点 
			free(q);//释放相同元素值的结点 
		}
		else
		{
			p=p->next;
		}
	}
}

13.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

算法思想：两个链表已经按元素值递增次序排序，将其合并时，均从第一个结点起进行比较，将小的结点链入链表中，同时后移工作指针。该问题要求结果链表按元素值递减次序排列，故新链表的建立应该采用头插法。比较结束后，可能会有一个链表为空，此时用头插法将剩下的结点依次插入到新链表中即可。

void MergeList(LinkList &La,LinkList &Lb)
{
	LNode *r,*pa=La->next,*pb=Lb->next;//分别是表La和Lb的工作指针 
	La->next=NULL;//La作为结果链表的头指针，先将结果链表初始化为空 
	while(pa&&pb)//当两链表均不为空时，循环 
	{
		if(pa->data<=pb->data)
		{
			r=pa->next;//r暂存pa的后继结点指针 
			pa->next=La->next;
			La->next=pa;//将pa结点链于结果表中，同时逆置(头插法) 
			pa=r;//恢复pa为当前待比较结点 
		}
		else
		{
			r=pb->next;//r暂存pb的后继结点指针
			pb->next=La->next;
			La->next=pb;//将pb结点链于结果表中，同时逆置(头插法)
			pb=r;//恢复pb为当前待比较结点 
		}	
		if(pa)
			pb=pa;//通常情况下会剩一个链表非空，处理剩下的部分 
		while(pb)
		{//处理剩下的一个非空链表 
			r=pb->next;//依次插入到La中(头插法) 
			pb->next=La->next;
			La->next=pb;
			pb=r; 
		}
		free(Lb); 
	}	
} 

14.设A和B是两个单链表(带头结点)，其中元素递增有序。设计一个算法从A和B中的公共元素产生单链表C,要求不破坏A、B的结点。

算法思想：表A、B都有序，可从第一个元素起依次比较A、B两表的元素，若元素值不等，则值小的指针往后移，若元素值相等，则创建一个值等于两结点的元素值的新结点，使用尾插法插入到新的链表中，并将两个原表指针后移一位，直到其中一个链表遍历到表尾。

void Get_Common(LinkList A,LinkList B)
{
	LNode *p=A->next,*q=B->next,*r,*s;
	LinkList C=(LinkList)malloc(sizeof(LNode));//建立表C
	r=C;//r始终指向C的尾结点 
	while(p!=NULL&&q!=NULL)//循环跳出条件 
	{
		if(p->data<q->data)
			p=p->next;//若A的当前元素较小，后移指针 
		else if(p->data>q->data)
			q=q->next;//若B的当前元素较小，后移指针
		else//找到公共元素结点 
		{
			s=(LNode *)malloc(sizeof(LNode));
			s->data=p->data;//复制产生结点*s 
			r->next=s;//将*s链接到C上(尾插法) 
			r=s;
			p=p->next;//表A和表B继续先后扫描 
			q=q->next;	
		} 
	}
	r->next=NULL;//置C尾结点指针为空 
}

15.已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A与B中的公共元素产生单链表C，要求不破坏A、B的结点。

算法思想：采用归并的思想，设置两个工作指针pa和pb，对两个链表进行归并扫描，只有同时出现在两个集合中的元素才链接到结果表中且仅保留一个，其他的结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。

LinkList Union(LinkList &la,LinkList &lb)
{
	LNode *pa=la->next;//设工作指针分别为pa和pb 
	LNode *pb=lb->next;
	LNode *u,*pc=la;//结果表中当前合并结点的前驱指针pc 
	while(pa&&pb)
	{
		if(pa->data==pb->data)//交集并入结果表中 
		{
			pc->next=pa;//A中结点链接到结果表 
			pc=pa;
			pa=pa->next;
			u=pb;//B中结点释放 
			pb=pb->next;
			free(u);	
		}
		else if(pa->data<pb->data)//若A中当前结点值小于B中当前结点值 
		{
			u=pa;
			pa=pa->next;//后移指针 
			free(u);//释放A中当前结点	
		}
		else//若B中当前结点值小于A中当前结点值 
		{
			u=pb;
			pb=pb->next;//后移指针 
			free(u);//释放B中当前结点	
		}	
	}
	while(pa)//B已遍历完，A未完 
	{
		u=pa;
		pa=pa->next;
		free(u);//释放A中剩余结点	
	}
	while(pb)//A已遍历完，B未完 
	{
		u=pb;
		pb=pb->next;
		free(u);//释放B中剩余结点	
	}
	pc->next=NULL;//置结果链表尾指针为NULL 
	free(lb);//释放B表的头结点 
	return la;	
} 

16.两个整数序列Ａ＝ａ1,a2,a3，．．．，am和Ｂ＝b1,b2,b3，．．．，bn已经存入两个单链表中，设计一个算法，判断序列Ｂ是否是序列Ａ的连续子序列。

算法思想：因为两个整数序列已存入两个链表中，操作从两个链表的第一个结点开始，若对应数据相等，则后移指针。若对应的数据不等，则Ａ链表从上次开始比较结点的后继开始，Ｂ链表仍从第一个结点开始比较，直到Ｂ链表到尾表示匹配成功。Ａ链表到尾而Ｂ链表未到表尾表示失败。操作中应记住Ａ链表每次的开始结点，以便下次匹配时好从其后继开始。

int Pattern(LinkList A,LinkList B)
{
	LNode *p=A;//p为A链表的工作指针，本题假定A和B均无头结点 
	LNode *pre=p;//pre记住每趟比较中A链表的开始结点 
	LNode *q=B;//q是B链表的工作指针 
	while(p&&q)
	{
		if(p->data==q->data)//结点值相同 
		{
			p=p->next;
			q=q->next;	
		}
		else
		{
			pre=pre->nexy;
			p=pre;//A链表新的开始比较结点 
			q=B;//q从B链表第一个结点开始	
		}	
		if(q==NULL)//B已经比较结束 
			return 1;//说明B是A的子序列 
		else
			return 0;//说明B不是A的子序列 
	}	
} 

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

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

int Symmetry(DLinkList L)
{
	DNode *p=L->next,*q=L->prior;//两头工作指针 
	while(p!=q&&q->next!=p)//循环跳出条件 
	{
		if(p->data==q->data)//所指结点值相同则继续比较 
		{
			p=p->next;
			q=q->next;
		}
		else//否则，返回0 
			return 0;
	}
	return 1;//比较结束后返回1 
}

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

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

LinkList Link(LinkList &h1,LinkList &h2)
{
	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 h1;
}