线性表的顺序表示

题目：从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。
答案：算法思想：搜索整个顺序表，查找最小值元素并记住其位置，搜索结束后用最后一个元素填补空出的原最小值元素的位置。代码如下：

bool Del_Min(sqList &L,ElemType &value){
//删除顺序表L中最小值元素节点，并通过引用型参数value返回其值
//若删除成功，则返回true；否则返回false
	if(L.length==0)
		return false; //表空，中止操作返回
	value=L.data[0];
	int pos=0; //假定0号元素的值最小
	for(int i=1;i<L.length;i++)  //循环，寻找具有最小值的元素
		if(L.data[i]<value){ //让value记忆当前具有最小值的元素
			value=L.data[i]; 
			pos=i;
		}
	L.data[pos]=L.data[L.length-1]; //空出的位置由最后一个元素填补
	L.length--;
	return true;
}

题目：从有序顺序表中删除其值在给定值s与t之间（要求s<t）的所有元素，若s或t不合理或顺序表为空，则显示出错信息并退出运行。
答案：注意：由于是有序表，所以删除的元素必然是相连的整体。算法思想：先寻找值大于等于s的第一个元素（第一个删除的元素），然后寻找值大于t的第一个元素（最后一个删除的元素的下一个元素），要求将这一段元素删除，只需直接将后面的元素前移。代码如下：

bool Del_s_t(SqList &L,ElemType s,ElemType t){
//删除有序顺序表L中值在给定值s与t之间的所有元素
	int i,j;
	if(s>=t||L.length==0)
		return false;
	for(i=0;i<L.length&&L.data[i]<s;i++); //寻找值大于等于s的第一个元素
	if(i>=L.length)
		return false; //所有元素值均小于s，返回
	for(j=i;j<L.length&&L.data[j]<=t;j++); //寻找值大于t的死一个元素
	for(;j<L.length;i++,j++)
		L.data[i]=L.data[j];
	L.length=i;
	return true;
}

题目：将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结果顺序表
答案：首先，按顺序不断取下两个顺序表表头较小的节点存入新的顺序表。然后，看哪个表还有剩余，将剩下的部分加到新的顺序表后面。代码如下：

bool Merge(SeqList A,SeqList B,SeqList &C){
	//将有序顺序表A与B合并为一个新的有序顺序表C
	if(A.length+B.length>C.maxSize) //大于顺序表的最大长度
		return false;
	int i=0,j=0,k=0;
	while(i<A.length&&j<B.length){ //循环，两两比较，小者存入结果表
		if(A.data[i]<=B.data[j])
			C.data[k++]=A.data[i++];
		else
			C.data[k++]=B.data[j++];
	}
	while(i<A.length) //还剩一个没有比较完的顺序表
		C.data[k++]=A.data[i++];
	while(j<B.length)
		C.data[k++]=B.data[j++];
	C.length=k;
	return true;
}

题目：设将$n(n>1)$个整数存放到一维数组R中。设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移$p(0<p<n)$个位置，即将R中的数据由$(X_0,X_1,...,X_{n-1})$变换为$(X_p,X_{p+1},...,X_{n-1},X_0,X_1,...,X_{p-1})$
答案：
（1）算法思想：
可将这个问题视为把数组 $ab$ 转换成数组 $ba$（a代表数组的前 $p$ 个元素，$b$ 代表数组中余下的 $n-p$ 个元素），先将 $a$ 逆置得到 $a^{-1}b$，再将 $b$ 逆置得到 $a^{-1}{b}^{-1}$，最后将整个 $a^{-1}{b}^{-1}$ 逆置得到$(a^{-1}{b}^{-1}{)}^{-1}=ba$。

• 设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3（p=3）个位置的过程如下：
  Reverse(0,p-1)得到cbadefgh；
  Reverse(p,n-1)得到cbahgfed；
  Reverse(0,n-1)得到defghabc;

（2）代码如下：

void Reverse(int R[],int from,int to){
	int i,temp;
	for(i=0;i<(to-from+1)/2;i++){
		temp=R[from+i];
		R[from+i]=R[to-i];
		R[to-i]=temp;
	}
}
void Converse(int R[],int n,int p){
	Reverse(R,0,p-1);
	Reverse(R,p,n-1);
	Reverse(R,0,n-1);
}

（3）复杂度分析：
上述算法中三个Reverse函数的时间复杂度分别为O(p/2),O((n-p)/2)和O(n/2)，故所设计的算法的时间复杂度为O(n)，空间复杂度为O(1)。

题目：给定一个含 $n(n\ge 1)$ 个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。
答案：算法思想：采用空间换时间的办法。分配一个用于标记的数组B[n]，用来记录A中是否出现了 $1n$ 中的正整数，B[0] 对应正整数1，B[n-1]对应正整数n，初始化B中全部未0。由于A中含有n个整数，因此返回的值是 1到n+1，当A中n个数恰好为 1到n 时返回 n+1。 代码如下：

int findMissMin(int A[],int n)
{
	int i,*B;  //标记数组
	B=(int *)malloc(sizeof(int)*n);  //分配空间
	memset(B,0,sizeof(int)*n);  //赋初值为0
	for(i=0;i<n;i++)
		if(A[i]>0&&A[i]<=n)
			B[A[i]-1]=1;
	for(i=0;i<n;i++)  //扫描数组B，找到目标值
		if(B[i]==0) break;
	return i+1;
}

时间复杂度$O(n)$，空间复杂度$O(n)$。

线性表的链式表示

题目：设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点。
答案：设 f(L, x) 的功能是删除以 L 为首结点指针的单链表中所有值等于 x 的结点，显然有 f(L->next, x) 的功能是删除以 L->next 为首结点指针的单链表中所有值等于 x 的结点。由此，可以推出递归模型如下。
终止条件：$f(L,x)\equiv 不做任何事情；若L为空表$
递归主体：
$f(L,x)\equiv 删除\ast L结点；f(L->next,x)；若L->data==x$
$f(L,x)\equiv 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){
		p=L;	//删除*L，并让L指向下一结点
		L=L->next;
		free(p);
		Del_X_3(L,x);
	}
	else
		Del_X_3(L->next,x);	
}

算法需要借助一个递归工作栈，深度为$O(n)$，时间复杂度为$O(n)$。

题目：设L为带头结点的单链表，编写算法实现从尾到头反向输出每个结点的值。
答案：可以用递归来实现，每当访问一个结点时，先递归输出它后面的结点，再输出该结点自身，这样链表就反向输出了。代码如下：

void R_Print(LinkList L){
//从尾到头输出单链表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);
}

题目：编写算法将带头结点的单链表就地逆置，所谓“就地“是指辅助空间复杂度为 $O(1)$
答案：解法一：将头结点摘下，从第一结点开始头插法建立单链表；代码如下：

LinkList Reverse_1(LinkList L){
	LNode *p,*r;   //p为工作指针，r为p的后继，以防断链
	p=L-next;
	L->next=NULL;
	while(p!=NULL){
		r=p->next; //暂存p的后继
		p->next=L->next;
		L->next=p;
		p=r;
	}
	return L;
}

解法二：依次遍历线性表L，并将结点指针反转。假设pre、p和r指向3个相邻的结点；注意处理第一个结点时，应该将其next域置为NULL，并且最后要将头结点指向最后一个结点。

LinkList Reverse_2(LinkList L){
	LNode *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;
}

上述两个算法的时间复杂度为 $O(n)$ ，空间复杂度为 $O(1)$.
题目：设在一个带表头结点的单链表中数据无序，编写一个函数，删除表中介于给定的两个值之间的元素。
答案：逐个结点检查删除。代码如下：

void RangeDelete(LinkList &L,int min,int max){
	LNode *pr=L,*p=L->next;  //p是检测指针，pr是其前驱
	while(p!=NULL){
		if(p->data>min && p->data<max){
			pr->next=p->next;
			free(p);
			p=pr->next;
		}
		else{
			pr=p;
			p=p->next;
		}
	return true;
}

题目：给定一个带头结点的单链表，设head为头指针，结点结构为（data，next），data为整型元素，next为指针，试写出算法：按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作为辅助空间）。
答案：算法思想：对链表进行遍历，在每次遍历中找出整个链表的最小值元素。时间复杂度为$O(n^2)$，代码如下：

void Min_Delete(LinkList &head){
//head是带头结点的单链表的头指针，本算法按递增顺序输出单链表中的数据元素
	while(head->next!=NULL){  //循环到仅剩头结点
		Lnode *pre=head;  //pre为元素最小值结点的前驱结点指针
		Lnode *p=pre->next;  //p为工作指针
		while(p->next!=NULL){
			if(p->next->data<pre->next->data)
				pre=p;  //记住当前最小值结点的前驱
			p-p->next;
		}
		print(p->next->data);  //输出元素最小值结点的数据
		u=pre->next;  //删除元素值最小的结点，释放结点空间
		pre->next=u->next;
		free(u);
	}
	free(head); //释放头结点
}

题目：将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A表中含有原表中序号为奇数的元素，而B表中含有原表中序号为偶数的元素，且保持其相对位置不变。
答案：方法一：设置两个头指针ha和hb，遍历整个线性表C，设置工作指针p和后继指针r，每次将p的指针指向r的后继结点，代码如下：

LinkList SplitList(LinkList &hc){
	LinkList ha=hc; //a链表的头结点
	LinkList hb=(LinkList)malloc(sizeof(LNode)); //b链表的头结点
	hb->next=NULL;
	hb=hc->next->next; //b链表的第一个结点
	p=ha->next; //a链表的第一个结点
	r=p->next;
	while(p->next!=NULL){
		p->next=r->next;
		p=p->next;
		r->next=p->next;
		r=r->next;
	}
	return hb;
}

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

LinkList DisCreat_1(LinkList &A){
//将表A中结点按序号的奇偶性分解到表A或表B中
	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;
		}
		else{
			ra->next=p; //在表A表尾插入新结点
		}
		p=p->next; //将p恢复为指向新的待处理结点
	}
	ra->next=NULL;
	rb->next=NULL;
	return B;
}

为了保持原来结点的顺序，本题采用尾插法建立单链表。本算法可以不用设置序号变量，参见下一题。

题目：设 C={a1,b1,a2,b2,...,an,bn}C=\{a_1,b_1,a_2,b_2,...,a_n,b_n\}C={a1​,b1​,a2​,b2​,...,an​,bn​}为线性表，采用带头结点的hc单链表存放，设计一个就地算法，将其拆分为两个线性表，使得A={a1,a2,...,an}A=\{a_1,a_2,...,a_n\}A={a1​,a2​,...,an​},B={bn,bn−1,...,b1}B=\{b_n,b_{n-1},...,b_1\}B={bn​,bn−1​,...,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=p->next;
		if(p!=NULL){
			q=p->next; //头插后，*p将断链，因此用q记忆*p的后继
			p->next=B->next;
			B->next=p;
			p=q;
		}
	}
	ra->next=NULL;
	return B;
}

题目：假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素递减次序排列的单链表，并要求利用原来两个单链表结点存放归并后的单链表。
答案：算法思想：合并时依次比较，将小的结点链入链表中，同时后移工作指针，新链表递减，采用头插法建立。代码如下：

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

题目：已知两个链表A和B分别表示两个集合，其元素递增排列。编制函数，求A和B的交集，并存放于A链表中。
答案：算法思想：采用归并的思想，设置两个工作指针pa和pb，对两个链表进行归并扫描，只有同时出现在两个集合中的元素才链接到结果表中且仅保留一个，其他结点全部释放。当一个链表遍历完毕后，释放另一个表中剩下的全部结点。代码如下：

LinkList Union(LinkList &la,LinkList &lb){
	pa=la->next;
	pb=lb->next;
	pc=la;
	while(pa&&pb){
		if(pa->data==pb->data){ //交集并入结果表中
			pc->next=pa;
			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);
		}
	} //while结束
	while(pa){ //B已遍历完，A未完
		u=pa;
		pa=pa->next;
		free(u);
	}
	while(pb){ //A已遍历完，B未完
		u=pb;
		pb=pb->next;
		free(u);
	}
	pc->next=NULL;
	free(lb);
	return la;
}

该算法的时间复杂度为 $O(len1+len2)$，空间复杂度为 $O(1)$.
题目：设计一个算法用于判断带头结点的循环双链表是否对称。
答案：算法思想，p从左向右扫描，q从右向左扫描。代码如下：

int Symmetry(DLinkList L){
//扫描循环双链表，判断是否对称
	DNode *p=L->next.*q=L->prior; //两头工作指针
	while(p!=q&&p->next!=q)
		if(p->data==q->data){ //所指结点值相同则继续比较
			p=p->next;
			q=q->prior;
		}
		else
			return 0;
	return 1;
}

题目：设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值最小的结点并输出，然后将该结点从中删除，直到单链表空为止，再删除表头结点。
答案：

void Delete_Min(LinkList &L){
	LinkNode *p=L,*r=L; //p为工作指针，r记录结点值最小的结点的前驱结点
	while(L->next!=L){ //表空则退出循环
		while(p->next!=L){ //遍历到了表尾（一次查找结束）
			if(p->next->data<r->next->data){ //如果当前结点比最小值结点要小，则更新r指针
				r=p; //更新r为最小结点的前驱结点
			}
			p=p->next; //工作指针继续向后遍历
		}
		u=r->next; //u保存当前的最小结点
		r->next=u->next;
		free(u); //删除最小值结点
		p=L; //下一轮再从表头开始遍历
	}
	free(L); //释放头结点
}

题目：单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点。试编写算法判断单链表是否存在环。
答案：
1）算法的基本设计思想
设置快慢两个指针分别为fast和slow，初始时都指向链表头head。slow每次走一步，即slow=slow->next；fast每次走一步，即fast=fast->next->next。由于fast比slow走得快，如果有环，如果有环，那么fast一定会先进入环，而slow后进入环。当两个指针都进入环后，经过若干操作后两指针定能在环上相遇。fast与slow相遇时，slow所走的距离不超过环的长度。
设头结点到环的入口点的距离为a，环的入口点沿着环的方向到相遇点的距离为x，环长为r，相遇时fast绕过了n圈。
则有 $2(a+x)=a+n\times r+x$，即 $a=n\times r-x$，故从头结点到环的入口点的距离等于 n 倍的环长减去环的入口点到相遇点的距离。因此可以设置两个指针，一个指向 head，一个指向相遇点，两个指针同步移动（均为依次走一步），相遇点即为环的入口点。
2）本题的代码如下：

LNode* FindLoopStrat(LNode *head){
	LNode *slow,*fast;
	slow=head;
	fast=head;
	while(fast!=NULL&&fast->next!=NULL){
		slow=slow->next;
		fast=fast->next->next;
		if(slow==fast) break; //相遇
	}
	if(fast==NULL||fast->next==NULL){
		return NULL; //没有环，返回NULL
	}
	LNode *p1=head; //指向开始点
	LNode *p2=slow; //指向相遇点
	while(p1!=p2){
		p1=p1->next;
		p2=p2->next;
	}
	return p1; //返回入口点
}

3）当fast与slow相遇时，slow肯定没有遍历完链表，故算法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$.
题目：采用带头结点的单链表保存单词，设计一个时间上尽可能高效的算法，找出由 str1 和 str2 所指向的两个链表共同后缀的起始位置
答案：
1）算法的基本设计思想
将两个链表以表尾对齐，具体为首先求出两个链表的长度，再将两个指针指向短表达开头，长表的距离表尾的结点等于短表的长度的结点
2）代码如下：

typedef struct LNode{
	char data;
	struct LNode *next;
}LNode, *LinkList; //单链表
//求表长
int ListLength(LinkList &L){
	LNode *p=L;
	int length=0; //头结点算第0个结点
	while(p->next!=NULL){
		p=p->next;
		length=length+1;
	}
	return length;
}
//找共同后缀的起始位置
int FindSuffix(LinkList &str1,LinkList &str2){
	//求出两表的表长
	m=ListLength(str1);
	n=ListLength(str2);
	LNode *p=str1,*q=str2;
	//如果m>n，p指针指向str1的第m-(n-1)个结点，q指针指向str2的第1个结点
	for(p=str1;m>n;m--){
		p=p->next;
	}
	//如果m<=n，p指针指向str1的第1个结点，q指针指向str2的第m-(n-1)个结点
	for(q=str2;m<n;n--){
		q=q->next;
	}
	while(p->next!=q->next&&p->next!=NULL){
		p=p->next;
		q=q->next;
	}
	return p->next;
}

3）时间复杂度为 $O(len1+len2)$