//2009、含头指针的单链表，查找其链表中倒数第K个位置上的结点
typedef int ElemType;             //链表数据的结构定义
typedef struct LNode{             //链表结点的结构定义
	ElemType data;                //结点数据
	struct Lnode *link;           //结点链接指针
}*LinkList;
int Search_k(LinkList list ,int k){
	Linklist p = list->link , q = list->link; //指针p、q指向第一个结点
	int count = 0;
	while(p!= NULL){              //遍历链表直到最后一个结点
		if(count < k){
			count ++;
			p = p->link;
		}
		else{
			p = p->link;
			q = q->link;
		}
	}
	if (count < k){               //结点数不足K
		return 0;
	}
	else{
		cout<<q->data;
		return 1;
	}
}

---------------------------------------------------------------------------------------------------------------------------------------
//2010、含n个整数的一维数组R，将R中保存的序列循环左移p个位置，即将R( a0,a1,....,a(n-1) )变换为R( ap,a(p+1),....a(n-1),a0,a1,....,a(p-1) )
//思路同：将字符串分开的两个子串相互倒转
void Reverse(int R[],int from,int to){
	int i,temp;
	for(int 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);
}

---------------------------------------------------------------------------------------------------------------------------------------
//2011、对于长度为L的升序序列S，处在第L/2个位置的数成为S的中位数，求两个等长升序序列A、B的中位数
/*思路：
	1、先分别求出A、B的中位数a、b
	2、若a=b则a或b为所求
	3、若a<b,则舍弃A中较小的一半和B中较大一半(舍弃长度相等)
	4、若a>b,则舍弃A中较大一半和B中较小一半(舍弃长度相等)
	5、重复1234步，直到最后都只剩一个元素，较小者为所求
*/
int M_Search(int A[],int B[],int n){
	int s1=0,d1=n-1,m1,s2=1,d2=n-1,m2;		//分别表示序列A和B的首位数、末位数、中位数
	while(s1 != d1 || s2 != d2 ){
		m1 = (s1+d1)/2;
		m2 = (s2+d2)/2;
		if(A[m1]==B[m2]){
			return A[m1];					//满足条件a=b
		}
		if(A[m1]<B[m2]){					//a<b
			if((s1+d1)%2==0){
				s1=m1;
				d2=m2;
			}
			else{
				s1=m1+1;
				d2=m2;
			}
		}
		else{
			if((s1+d1)%2==0){
				d1=m1;
				s2=m2;
			}
			else{
				d1=m1;
				s2=m2+1;
		}
	}
	return A[s1]<B[S2]? A[s1]:[s2];
}

---------------------------------------------------------------------------------------------------------------------------------------
/*2012
	用带头结点的单链表保存单词，当两个单词有相同的后缀时，可共享相同的后缀存储空间，例如“loading”和“being”
	设str1和str2分别指向两个单词所在的单链表的头结点，找出两个链表共同后缀的起始位置
*/
/*思路：找到共同后缀的第一个结点
	1、分别求出str1和str2所指两个链表的长度m、n
	2、两个链表以表尾对齐：另指针p、q分别指向str1和str2的头结点，若m>=n，则使p指向链表中的第m-n+1个结点；反之则使q指向其第m-n+1个结点
	3、反复将p和q同步向后移动，并判断它们是否指向同一结点。
*/
typedef char ElemType;
typedef struct LNode
{
	ElemType data;
	struct Lnode *link
}LinkList;
LinkNode *Find_1st_common(LinkList str1,LinkList str2){
	int len1=length(str1),len2=length(str2);
	LinkNode *p,*q;
	for(p=str1;len1>len2;len1--){
		p=p->next;
	}
	for(q=str2;len1<len2;len2--){
		q=q->next;
	}
	while(p->next!=NULL&&p->next!=q->next){
		p=p->next;
		q=q->next;
	}
	return p->next;
}

---------------------------------------------------------------------------------------------------------------------------------------
//2013、整数序列A(a0,a1,...,a(n-1) ),其中0<a<n  若存在值相等的元素x且个数m>n/2，则称x为A的主元素，设计算法求A的主元素
/*思路：从前往后扫描数组元素，标记出一个可能成为主元素的元素Num，然后重新计数，确认Num是否是主元素
	1、选取候选的主元素：依次扫描所给数组中的每个证书，将第一个遇到的证整数Num保存到c中，记录Num的出现次数为1；
		若遇到的下一个整数仍等于Num，则计数+1，否则计数减1；
		当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述，扫完全部元素
	2、判断c中元素是否是真正的主元素：再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素
*/
int Majority(int A[],int n){
	int i,c,count=1;
	c = A[0];
	for(i=1;i<n;i++){
		if(A[i] ==c){
			count++;
		}
		else if(count>0){
			count--;
		}
		else{
			c = A[i];
			count = 1;
		}
	}
	if(count>0){
		for(i=count=0;i<n;i++){
			if(A[i] == c){
				count++;
			}
		}	
		if(count>=n/2){
			return c;
		}
		else{
			return -1;
		}
	}
}

---------------------------------------------------------------------------------------------------------------------------------------
/*2014
	二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和。
	给定一棵二叉树，采用二叉链表存储，其中叶结点weight域保存该结点的非负权值，left指向其左孩子，right指向其右孩子
	设root为指向T的根结点，设计求T的WPL的算法
*/
//二叉树结点的数据类型定义
typedef struct BiTNode{
	int weight;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
/*思路：
	方法1(先序遍历递归算法)：用static变量记录WPL
		1、若该结点是叶子结点，那么变量wpl加上该结点的深度与权值之积
		2、若该结点非叶子结点，那么若左子树不空，对左子树调用递归算法，若右子树不空，对右子树调用递归算法，深度参数均为本结点深度参数+1
		3、最后返回计算出的wpl即可
*/
int WPL(BiTree root){
	int wpl_PreOrder(root,0);
}
int wpl_PreOrder(BiTree root,int deep){
		static int wpl = 0;									//定义一个static变量存储wpl
		if(root->lchild == NULL && root->rchild == NULL){
			wpl += deep * root -> weight ;					//若为叶子结点，累计wpl
		}		
		if(root->lchild != NULL){
			wpl_PreOrder(root->lchid,deep+1);
		}
		if(root->rchild !=NULL){
			wpl_PreOrder(root->rchild,deep+1);
		}
		return wpl;
}

/*	
	方法2(基于层次遍历的队列)：
		1、用队列进行层次遍历，记录当前的层数，当遍历到叶子结点时，累计wpl；
		2、当遍历到非叶子结点时把该结点的子树加入队列；
		3、当某结点为该层的最后一个结点时，层数自增1；
		4、队列空时遍历结束，返回wpl
*/
#define MaxSize 100 							//设置队列的最大容量
int wpl_LevelOrder(BiTree root){
	BiTree q[MaxSize];							//声明队列,end1为头指针，end2为尾指针
	int end1,end2;								//队列最多容纳MaxSize-1个元素
	end1 = end2 =0 ;							//头指针指向队头元素，尾指针指向队尾的后一个元素
	int wpl = 0,deep =0;						//初始化wpl和深度
	BiTree lastNode;							//lastNode用来记录当前层的最后一个结点
	BiTree newlastNode;							//newlastNode用来记录下一层的最后一个结点
	lastNode = root;							//lastNode初始化为根结点
	newlastNode = NULL;							//newlastNode初始化为空
	q[end2++] = root;							//根结点入队
	while(end1 != end2){						//层次遍历，若队列不空则循环
		BiTree t = q[end1++];					//拿出队列中的头一个元素
		if(t->lchild == NULL && t->rchild == NULL){		
			wpl += deep*t->weight;				//若为叶子结点，统计wpl
		}
		if(root->lchild != NULL){				//若非叶子结点把左结点入队
			q[end2++] = t->lchild;				
			newlastNode = t->lchild;
		}
		if(root->rchild != NULL){
			q[end2++] = t->rchild;
			newlastNode = t->rchild;
		}
		if(t == lastNode){
			lastNode = newlastNode;
			deep += 1;
		}
	}
	return wpl
}


---------------------------------------------------------------------------------------------------------------------------------------
/*2015
	用单链表保存m个整数，结点的结构为[data][link]，且[data]<=n
	设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点
	如链表：21 -> -15 -> -15 -> -7 -> 15,删除结点后为：21 -> -15 -> -7
*/
/*
	思路：因|data|<=n,故辅助数组q的大小为n+1，各元素的初值均为0.
	依次扫描链表中各结点，同时检查q[|data|]的值，若为0，则保留结点并令q[|data|]=1，否则将该结点删除
*/
//单链表结点的数据类型定义
typedef struct  node{
	int data;
	struct node *link;
}NODE;
typedef NODE *PNODE
//算法实现
void func(PNODE h,int n){
	PNODE p = h , r;
	int *q,m;
	q = (int *)malloc(sizeof(int)*(n+1));			//申请n+1个位置的辅助空间
	for(int i=0;i<n+1;i++){
		*(q+i) = 0;
	}
	while(p->link != NULL){
		m = p->link->data >0 ? p->link->data:-p->link->data;
		if(*(q+m) == 0){							//判断该结点的data是否已出现过
			*(q+m) =1;
			p = p->link;
		}
		else{
			r = p->link;
			p->link = r->link;
			free(r);
		}
	}
	free(q);
}

---------------------------------------------------------------------------------------------------------------------------------------
/*2016
	已知由n(n>=2)个正整数构成的集合A，将其划分为两个不相交的子集A1和A2，元素个数分别为n1和n2
	令A1和A2中元素之和为S1和S2，设计划分算法，满足|n1-n2|最小且|S1-S2|最大
*/
/*思路：
	将最小的n/2(向下取整，下同)个元素放在A1中，其余的元素放在A2中，分组结果即可满足题意
	利用快速排序的思想，基于枢轴将n个整数划分为两个子集，根据划分后枢轴所处的位置i分别处理
	1、若i=n/2,则分组完成，算法结束
	2、若i<n/2,则枢轴及之前的所有元素均属于A1，继续对i之后的元素进行划分
	3、若i>n/2,则枢轴及之后的所有元素均属于A2，继续对i之前的元素进行划分
*/
int setPartition(int a[],int n[]){
	int pivotkey,low=0,low0=0,high=n-1,flag=1,k=n/2,i;
	int s1=0,s2=0;
	while(flag){
		pivotkey=a[low];
		while(low<high && a[high]>=pivotkey){
			--high;
		}
		if(low != high){
			a[low]=a[high];
		}
		while(low<high && a[low]<=pivotkey){
			++low;
		}
		if(low != high){
			a[high]=a[low];
		}
		a[low] = pivotkey;
		if(low == k-1){
			flag = 0;
		}
		else{
			if(low < k-1){
				low0 = ++low;
				high = high0;
			}
			else{
				high0 = --high;
				low = low0;
			}
		}
	}
	for(i=o;i<k;i++){
		s1+=a[i];
	}
	for(i=k;i<n;i++){
		s2+=a[i];
	}
	return s2-s1;
}

---------------------------------------------------------------------------------------------------------------------------------------
/*2017
	设计算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出
	如下列两棵表达树作为算法的输入时，输出的等价中缀表达式分别为(a+b)*(c*(-d))和(a*b)+(-(c-d))
	          *                        +
	       /     \                  /     \
	      +       *                *       -
	    /   \   /   \            /   \       \
	   a     b c     -          a     b       -
	                   \                    /   \
	                    d                  c     d
*/
/*思路：
	表达树的中序序列加上必要的括号即为等价的中缀表达式
	基于二叉树的中序遍历策略
*/
//二叉树结点定义：
typedef struct node{
	char data[10];				//存储操作数或操作符
	struct node *left,*right;
}BTree;
//算法
void BtreeToE(BTree *root){
	BtreeToExp(root,1);			//根的高度为1
}
void BtreeToExp(BTree *root,int deep){
	if(root == NULL){return;}
	else if(root->left == NULL && root->right == NULL){
		printf("%s",root->data );
	}
	else{
		if(deep>1){
			printf("(");		//若有子表达式则加一层括号
		}
		BtreeToExp(root->left,deep+1);
		printf("%s",root->data );
		BtreeToExp(root->right,deep+1);
		if(deep>1){
			printf(")");		//若由子表达式则加一层括号（此处是为了封闭次结点层的运算）
		}
	}
	
}

---------------------------------------------------------------------------------------------------------------------------------------
/*2018
	给定一个含n个整数的数组，设计一个时间上尽可能高效的算法，找出数组中未出现的最小正整数
	例如，数组{-5,3,2,3}中未出现的最小正整数是1；数组{1,2,3}中未出现的最小正整数是4
*/
/*思路：
	由于A中只有n个数，因此若最小的n个正整数全在A内的话，未出现的最小正整数则为n+1，反之，将A中n个数扫一遍后，1~n中有数没被扫到，则最小的那个为所求
	分配一个用于标记的数组B[n],用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应正整数n，初始化B中所有值为0
	从A[0]开始遍历A，若0<A[i]<=n,则令B[A[i]-1]==1,否则不做任何操作(对负数和大于n的数都不做处理)
	对A遍历结束后，开始遍历数组B，找到第一个满足B[i]==0的下标，若找到，返回结果(i+1),否则返回(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++){
 		if(B[i] == 0){
 			break;
 		}
 		return i+1;
 	}
 	return n+1;
 }

---------------------------------------------------------------------------------------------------------------------------------------
 /*2019
 	设线性表L=( a1,a2,a3,...,a(n-2),a(n-1),an )采用带头结点的单链表保存，链表中结点定义如下：
 
 typedef struct node{
 	int data;
 	struct node *next;
 }NODE;

	设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'( a1,an,a2,a(n-1),a3,a(n-2),... )
 */
 /*思路：
	观察俩个线性表，发现L'是由L摘取第一个元素，再摘取倒数第一个元素······依次合并而成的
	为了方便在链表后半段取元素，需要先将L后半段原地逆置，否则每取一个尾部的结点都要几乎完整遍历一遍链表
	1、先找出链表L的中间结点，为此设置两个指针p和q，指针每次走一步，指针q每次走两步，当指针q到达链尾时，指针p正好在链表的中间结点
	2、将L的后半段结点原地逆置
	3、从单链表前后两段中依次各取一个结点，按要求重排
 */

void change_list(NODE *h){
	NODE *p,*q,*r,*s;
	p=q=h;
	while(q->next != NULL){			//寻找中间结点
		p = p->next;
		q = q->next;
		if(q->next != NULL){
			q = q->next;
		}
	}
	q = p->next;					
	p->next = NULL;
	while(q != NULL){				//将链表后半段逆置
		r = q->next;
		q->next = p->next;
		p->next = q;
		q=r;
	}
	s = h->next;					//s指向前半段的第一个数据结点，即插入点
	q = p->next;					//q指向后半段的第一个数据结点
	p->next = NULL;
	while(q != NULL){				//将链表后半段的结点插入到指定位置
		r = q->next;				//r指向后半段的下一个结点
		q->next = s->next;			//将q所指结点插入到s所指结点之后
		s->next = q;				
		s = q->next;				//s指向前半段的下一个插入点
		q = r;
	}
}

---------------------------------------------------------------------------------------------------------------------------------------
/*2020
	定义三元组(a,b,c)(均为整数)的具里D=|a-b|+|b-c|+|c-a|
	给定三个非空整数集合S1、S2、S3,按升序分别存储在3个数组中
	设计算法计算并输出所有可能的三元组(a,b,c)中的最小距离(a,b,c分别为S1,S2,S3中的整数)
	例如S1={-1,0,9},S2={-25,-10,10,11},S3={2,9,17,30,41},则最小距离为2，相应的三元组为(9,10,9)
*/

---------------------------------------------------------------------------------------------------------------------------------------
/*2021
	已知无向连通图G由顶点集V和边集E组成|E|>0
	当G中度为奇数的顶点个数为不大于2的偶数时，G存在包含所有边且长度为|E|的路径(成为EL路径)
	设图G采用邻接矩阵存储，类型定义如下：

	Typedef struct{					//图的定义
		int numVertices,numEdges;	//图中实际的顶点权和边数
		char VertticesList[MAXV];	//顶点表。MAXV为已定义常量
		int Edge[MAXV][MAXV];				//邻接矩阵
	}:MGraph;

	设计算法:int IsExistEL(MGraph G),判断G是否存在EL路径，若存在，则返回1，否则返回0
*/
/*思路
	对于采用邻接矩阵存储的无向图，邻接矩阵每一行(列)中非零元素的个数为本行(列)对应的顶点的度。
	因此可以依次计算连通图G中各顶点的度，并记录度为奇数的顶点个数，若个数为0或2，则返回1，否则返回0
*/
int IsExistEL(MGraph G){
	int degree,i,j,count=0;
	for(i=0;i<G.numVertices;i++){
		degree = 0;
		for(j=0;j<G.numVertices;j++){
			degree += G.Edge[i][j];
			if(degree % 2 != 0){
				count++;
			}
		}
	}
	if(count ==0 || count == 2){
		return 1;
	}
	else 
		return 0;
}