线性表问题总结

逆置问题：
例1：
1、将一长度为n的数组的前端K（k<n）个元素逆序后移动到数组后段，要求原数组总数据不丢失。
2、将一长度为n的数组的前端K（k<n）个元素保持原序后移动到数组后段，要求原数组总数据不丢失。
3、将数组中的元素循环左移p（0<p<n）个位置。

void reverse(int a[],int left,int right,int k)
{
	int temp;
	for (int i=left,j=right;i<left+k && i<j;++i,--j) //因为k的长度有可能超过数组长度的一半         
	{                                                //所以i<j这个条件还是要加上去的
		temp=a[i];
		a[i]=a[j];
		a[j]=temp;

	}
}

void moveToEnd(int a [],int n ,int k)
{
	reverse(a,0,k-1,k);
	reverse(a,0,n-1,k);
}

void moveP(int a [],int n,int p)
{
	reverse(a,0,p-1,p);
	reverse(a,p,n-1,n-p);
	reverse(a,0,n-1,n);
}

最值问题：
1：在线性表中找最值

int max=a[0];  
int maxIdx=0;
for(int i=0;i<n;++i)
{
	if (max<a[i])
	{
		max=a[i]; //max值
		maxIdx=i;  //最大值的位置
	}
}

这个是最大值，最小值同理。

2：在链表中找最小值：

LNode *p,*q;
int min=head->next->data;
q=p=head->next;
while(p!=NULL)
{
	if(min>p->data)
	{
		min=p->data;
		q=p;
	}
	p=p->data;
}

在链表中找最大值同理。

例：一双链表非空，有head指针指出，结点结构为{llink,data,rlink},请设计一个将结点数据域data值最大的那个结点（最大值结点只有一个）移动到链表最前边的算法，要求不得申请新结点空间。

void maxFirst(DLNode *head)
{
	DLNode *p=head->rlink,*q=p;
	int max=p->data;

	while(p!=NULL)
	{
		if(max<p->data)
		{
			max=p->data;
			q=p;
		}
		p=p->rlink;
	}

	DLNode *l=q->llink; *r=q->rlink;
	l->rlink=r;
	if(r!=NULL) //防止最大值为最后一个结点
		r->llink=l;

	q->llink=head;
	q->rlink=head->rlink;
	head->rlink=q;
	q->rlink->llink=q;
}

归并问题：
1：顺序表归并

void mergearray(int a [],int m,int b[],int n,int c[])
{
	int i=0,j=0;
	int k=0;
	while(i<m&&j<n)
	{
		if(a[i]<b[j])
			c[k++]=a[i++];  //c[k]=a[i];k++;i++
		else
			c[k++]=b[j++];
	}
	while(i<m)
		c[k++]=a[i++];
	while(j<n)
		c[k++]=b[j++];
}

分别将a[]和b[]的数组有小到大的归并为数组c[]，m,n分别为两个数组的长度，c数组的长度为两个长度的之和，所以不需要再来一个变量来存储了。i,j分别是数组下标用来指出哪个元素在进行比较，k是指向c数组的下标。如果a[i]<b[j]则将a[i]赋值给c[k]，且k向后移一位，i也向后移一位。下一个while是在一个数组全部比较完而另一个数组还有剩余的时候，将剩余的数组中的每一个元素都移动到数组c中去。

2：链表归并
–顺序归并

void merge(LNode *A,LNode *B,LNode *&C)
{
	LNode *p=A->next;
	LNode *q=B->next;
	LNode *r;
	C=A;
	C->next=NULL;
	free(B);
	r=C;
	while(p!=NULL&&q!=NULL)
	{
		if(p->data<=q->data)
		{
			r->next=p;
			p=p->next;
			r=r->next;
		}
		else
		{
			r->next=q;
			q=q->next;
			r=r->next;
		}
		if(p!=NULL)
			r->next=p;
		if(q!=NULL)
			r->next=q;
	}

}

p,q是指向两个链表的指针，C是指向新链表的指针，r是指向新链表表尾的指针。C=A是以A链表的头结点作为新链表的头结点。然后释放B结点（头结点）。此时新链表为空链表，所以r指针指向此时的头结点r=C。

–逆序归并

void mergeR(LNode *A,LNode *B,LNode *&C)
{
	LNode *p=A->next;
	LNode *q=B->next;
	LNode *s;
	C=A;
	C->next=NULL;
	free(B);
	while(p!=NULL&&q!=NULL)
	{
		if(p->data<=q->data)
		{
			s=p;
			p=p->next;
			s->next=C->next;
			C->next=s;
		}
		else
		{
			s=q;
			q=q->next;
			s->nexr=C->next;
			c->next=s;
		}
		while(p!=NULL)
		{
			s=p;
			p=p->next;
			s->next=C->next;
			C->next=s;
		}
			
		while(q!=NULL)
		{
			s=q;
			q=q->next;
			s->next=C->next;
			C->next=s;
		}
	}

}

用头插法的形式重新进行归并，这样就得到了逆序。在一个链表的元素全部取完之后，逆序的话剩余的元素就不能直接修改指针了，要用循环将剩余的元素一个一个的以头插法的形式插入到新链表中。

划分问题：
取什么数作为树轴，这个数的大小是关键，这个数的由来不是关键。
1：以数组中的第一个元素为树轴，左边的元素为小于树轴的元素，右边的元素为大于树轴的元素。

void partition(int arr[],int n)
{
	int temp;
	int i=0;j=n-1;
	temp=arr[i];
	while(i<j)
	{
		while(i<j&&arr[j]>=temp)
			--j;
		if(i<j)
		{
			arr[i]=arr[j];
			++i;
		}
		while(i<j&&arr[i]<temp)
			++i;
		if(i<j)
		{
			arr[j]=arr[i];
			--j;

		}
	}
	arr[i]=temp;
	
}

2：以任意一个数作为树轴，左边的元素为小于树轴的元素，右边的元素为大于树轴的元素。

void partition(int arr[],int n,int comp)
{
	int temp;
	int i=0;j=n-1;
	temp=arr[i];
	while(i<j)
	{
		while(i<j&&arr[j]>=comp)
			--j;
		if(i<j)
		{
			arr[i]=arr[j];
			++i;
		}
		while(i<j&&arr[i]<comp)
			++i;
		if(i<j)
		{
			arr[j]=arr[i];
			--j;

		}
	}
	arr[i]=temp;
	
}

这里i和j共同指向的还是temp，comp只是一个比较大小的标准，comp都不一定是数组中存在的元素。理解最前面的黑体字就懂这个类型了。
3：以数组元素中的任意一个元素作为树轴，左边小于树轴，右边大于树轴。

void partition(int arr[],int n ,int k)
{
	int temp;
	int i=0;j=n-1;
	temp=arr[0]; //区别就在这三句话，1
	arr[0]=arr[k]; //2
	arr[k]=temp; //3
	temp=arr[i];
	while(i<j)
	{
		while(i<j&&arr[j]>=temp)
			--j;
		if(i<j)
		{
			arr[i]=arr[j];
			++i;
		}
		while(i<j&&arr[i]<temp)
			++i;
		if(i<j)
		{
			arr[j]=arr[i];
			--j;

		}
	}
	arr[i]=temp;
	
}

将这个数组中k位置的值直接放在数组中的第一个位置那就行。之所以放在第一个那，只是后面的代码和第一种情况的一个统一，更方便的去操作。