java算法刷题00——数据结构基础知识回顾

void loveYou（int flag[],int n）
{
    int i;
    for(i=0;flag[i]<n;i++)
    {
        if(flag[i]==n)printf("I love U");
        break;
    }
}

void loveYou(int n;)
{
 	int flag[n];   
    int i;
}

void loveYou(int n)
{
    if(n>1) loveYou(n-1);
    printf("I love U %d\n");
}

int main(void){
    loveYou(5);
    return 0;
}

void loveYou(int n)
{
	int flag[n];
    if(n>1) loveYou(n-1);
    printf("I love U %d\n");
}

int main(void){
    loveYou(5);
    return 0;
}

#define MaxSize 50
typedef struct{
	int data[MaxSize];
	int length;
}SqlList;

void InitList(SqlList &L)
{
	int i;
	for(i=0;i<L.length;i++) L.data[i]=0;
	L.length=0;
}

int main(void)
{
	SqlList L;
	InitList(L);
	int i;
	for(i=0;i<L.length;i++)printf("%d ",L.data[i]);
	return 0;
}

#include<stdio.h>
#include<stdlib.h>
#define InitSize 4 //默认长度
typedef struct{
	int * data;
	int MaxSize;
	int length;
}SeqList;

void InitList(SeqList &L)
{
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.MaxSize=InitSize;
}

void IncreaseSize(SeqList &L,int len)
{
	int * p=L.data;
	L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
	for(int i=0;i<L.MaxSize;i++) L.data[i]=p[i];
	free(p);
	L.MaxSize=L.MaxSize+len;
}
int main(void)
{
	SeqList L;
	InitList(L);
    //这种插入数据的方式不规范，并没有改变length
	L.data[0]=1;
	L.data[1]=2;
	L.data[2]=3;
	L.data[3]=4;
	for(int i=0;i<L.MaxSize;i++) printf("a[%d]=%d,",i,L.data[i]);
	printf("\n");
	IncreaseSize(L,3);
	for(int i=0;i<L.MaxSize;i++) printf("a[%d]=%d,",i,L.data[i]);
	return 0;
}

#include<stdio.h>
#include<stdlib.h>
#define InitSize 10

typedef struct{
int * data;
int length;
int MaxSize;
}SeqList;

void InitList(SeqList &L)
{
	int i=0;
	L.data=(int *)malloc(InitSize*sizeof(int));
	for(i=0;i<L.MaxSize;i++)L.data[i]=0;
	L.length=0;
	L.MaxSize=InitSize;
}

bool ListInsert(SeqList &L,int i,int e)//i是位序,不是数组下标
{
	if(i<1||i>L.length+1) return false;
	if(i>L.MaxSize) return false;
	int j;
	for(j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1];  //1
	L.data[i-1]=e;
	L.length++;
	return true;
}


int main(void)
{
	SeqList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
	printf("\n");
	ListInsert(L,1,0);
	for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10

typedef struct{
int * data;
int MaxSize;
int length;
}SeqList;

void InitList(SeqList &L)
{
	int i;
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.MaxSize=InitSize;
	for(i=0;i<L.MaxSize;i++) L.data[i]=0;
	L.length=0;
}

bool ListInsert(SeqList &L,int i,int e)
{
	int j;
	if(i<1||i>L.length+1)return false;
	if(i>L.MaxSize)return false;
	for(j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;
	L.length++;
	return true;
}
//按位删除
bool ListDelete(SeqList &L,int i,int &e) //此处传入的参数i是位序为i的元素，即删除对应下标为i-1的元素
{
	if(i<1||i>L.length)return false;
	e=L.data[i-1]; 
	int j;
	for(j=i;j<L.length;j++)
		L.data[j-1]=L.data[j];
	L.length--;
	return true;
}

int main(void)
{
	int e=-1;
	SeqList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
	printf("\n");
	if(ListDelete(L,1,e))
		printf("Delete %d\n",e);
	else
		printf("Failure!\n");
	for(int i=0;i<L.length;i++)printf("data[%d]=%d,",i,L.data[i]);
	return 0;
}

#include<stdio.h>
# define MaxSize 10
typedef struct{
	int data[MaxSize];
	int length;
}SeqList;

void InitList(SeqList &L)
{
	int i;
	for(i=0;i<MaxSize;i++)L.data[i]=0;
	L.length=0;
}

bool ListInsert(SeqList &L,int i,int e)
{
	int j;
	if(i<1||i>L.length+1)return false;
	if(i>MaxSize)return false;
	for(j=L.length;j>=i;j--)
		L.data[j]=L.data[j-1];
	L.data[i-1]=e;
	L.length++;
	return true;
}

int GetElem(SeqList L,int i){
	if(i<1||i>L.length) return -1;
	return L.data[i-1];
}

int main(void)
{
	SeqList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	printf("%d,",GetElem(L,1));
	printf("%d\n",GetElem(L,0));
	return 0;
}

int LocateElem(SeqList L,int e)
{
	int i;
	for(i=0;i<L.length;i++)
		if(L.data[i]==e)return i+1;
	return 0;
}

//删除最小元素，并返回该元素的值
bool ListDelete(SeqList &L,int &min)
{
	int i; 
	int index=0;//记录最小元素的位序
	if(L.length==0) return false; //如果链表为空，则返回false
	min=L.data[0];
	//查找最小的元素
	for(i=1;i<L.length;i++)
	{
		if(L.data[i]<min) min=L.data[i];
		index=i+1;
	}
	//将空出来的位置由最小的元素代替
	L.data[index]=L.data[L.length-1];
	L.length--;
	return true; 
}

bool ReverseList(SeqList &L)
{
	if(L.length==0)return false;
	int i;
	int j;
	int temp;
	for(i=0;i<(L.length)/2;i++)
	{
		j=L.length-i-1;
		temp=L.data[i];
		L.data[i]=L.data[j];
		L.data[j]=temp;
	}
	return true;
}

void DeleteByValue(SeqList &L,int x)
{
	int k=0;//用来存储不是x的数的个数
	for(int i=0;i<L.length;i++)
	{
		if(L.data[i]!=x)
		{
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
}

bool DeleteBetweenValue(SeqList &L,int s,int t,int &start,int &end)
{
	if(L.length==0) return false;
	if(s>=t) return false;
	int i;
	for(i=0;i<L.length;i++)
	{
		if(L.data[i]==s)start=i+1;
		if(L.data[i]==t)end=i+1;
	}
	return true;
}

int main(void)
{
	int e=0;
	SeqList L;
	InitList(L);
	int start;
	int end;
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	for(int i=0;i<L.length;i++)printf("%d,",L.data[i]);
	DeleteBetweenValue(L,1,2,start,end);
	printf("\n");
	int k=end-start+1;
	for(int j=0;j<k;j++) ListDelete(L,start,e);
	for(int i=0;i<L.length;i++)printf("%d,",L.data[i]);
	return 0;
}

#include <stdio.h>

typedef struct LNode{
	int data;
	struct LNode * next;
}LNode,*LinkList;

//无头节点
bool InitList(LinkList &L)
{
	L=NULL; //把头指针置空
	return true;
}

//判断链表是否为空，如果为空，头指针指向NULL
bool IsListEmpty(LinkList L)
{
	return (L==NULL);
}

int main(void)
{
	LinkList L; //声明一个指向单链表的指针
	InitList(L);
	printf("%d",IsListEmpty(L));
	return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode{
	int data;
	struct LNode * next;
}LNode,*LinkList;

//带头节点
bool InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL)return false; //上面头指针指向了头结点，头指针还指向NULL,说明内存空间不足，返回false；
	L->next=NULL; //头结点置空
	return true;
}

//判断链表是否为空，如果为空，头指针指向NULL
bool IsListEmpty(LinkList L)
{
	return (L->next==NULL);
}

int main(void)
{
	LinkList L; //声明一个指向单链表的指针
	InitList(L);
	printf("%d",IsListEmpty(L));
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode{
	int data;
	LNode * next;
}LNode,*LinkList;

void InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode)); //分配一个空间作为头结点，头指针指向头结点
	L->next=NULL; //头节点的next域置空
}

//按位序插入
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false;
	LNode * p=L; //指针p指向头结点
	int j=0; //下标j用来记录指针p指向第几个结点
	while(p!=NULL&&j<i-1) //循环找到第i-1个结点
	{
		p=p->next;
		j++;
	}
	if(p==NULL) return false; //i值超过了链表的范围，不合法
	LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点
	s->data=e; //将要插入的数据e存到结点中
	s->next=p->next;
	p->next=s;
	return true;
}

int main(void)
{
	LinkList L; //申请一个LinkList类型的头指针
	InitList(L);
	if(ListInsert(L,1,1))
	{
		printf("%d\n",L->next->data);
	}
	else
		printf("Failed!\n");
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
	int data;
	LNode * next;
}LNode,*LinkList;

//不带头结点
bool InitList(LinkList &L)
{
	L=NULL; //将头指针置空
	return true;
}

//按位插入
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false; //非法输入
	if(i=1)
	{
		LNode * s=(LNode *)malloc(sizeof(LNode));
		s->data=e;
		s->next=L;
		L=s;
		return true;
	}
	int j=1; //用来记录p指向第几个结点
	//找到第i-1个结点
	LNode * p=L;
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		j++;
	}
	if(p==NULL) return false;
	LNode * s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

int main(void)
{
	LinkList L;//声明一个头指针
	InitList(L);
	if(ListInsert(L,0,1))
	{
		printf("%d\n",L->data);
	}
	else
		printf("Failed!\n");
	return 0;
}

bool InsertNextNode(LNode * p,int e)
{
	if(p==NULL) return false; //i值超过了链表的范围，不合法
	LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点
	s->data=e; //将要插入的数据e存到结点中
	s->next=p->next;
	p->next=s;
	return true;
}

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
	int data;
	LNode * next;
}LNode,*LinkList;

void InitList(LinkList &L)
{
	LNode * p;
	L=(LNode *)malloc(sizeof(LNode));
	p=L;
	p->next=NULL;
}

//按位插入
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false; //非法输入
	int j=0; //用来记录p指向第几个结点
	//找到第i-1个结点
	LNode * p=L;
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		j++;
	}
	if(p==NULL) return false;
	LNode * s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

//核心代码块，插入制定结点之前
bool InsertPrioList(LNode * p,int e)
{
	if(p==NULL)return false;
	LNode * s=(LNode *)malloc(sizeof(LNode));
	if(s==NULL)return false;
	//把s插入p结点之后
	s->next=p->next;
	p->next=s;
	//把p的数据拷贝到s，再把要插入的数据存入p
	s->data=p->data;
	p->data=e;
	return true;
}

int main(void)
{
	LinkList L;
	InitList(L);
	ListInsert(L,1,1);
	LNode * r=L->next;
	InsertPrioList(r,5);
	printf("%d",L->next->data);
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
typedef struct LNode
{
	int data;
	LNode * next;
}LNode,*LinkList;

bool InitList(LinkList &L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL)return false;
	L->next=NULL;
	return true;
}

//按位插入
bool ListInsert(LinkList &L,int i,int e)
{
	if(i<1) return false; //非法输入
	int j=0; //用来记录p指向第几个结点
	//找到第i-1个结点
	LNode * p=L;
	while(p!=NULL&&j<i-1)
	{
		p=p->next;
		j++;
	}
	if(p==NULL) return false;
	LNode * s=(LNode *)malloc(sizeof(LNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}

//核心代码，按位序删除
bool ListDelete(LinkList &L,int i,int &e)
{
	if(L->next==NULL)return false;
	if(i<1)return false;
	//找到第i-1个位置
	LNode * p=L;
	int j=0;
	while(j<i-1&&p!=NULL)
	{
		p=p->next;
		j++;
	}
	if(p==NULL) return false;
	//在第i-1个位置后执行删除操作
	LNode * q=p->next;
	e=q->data;
	p->next=q->next;
	free(q);
	return true;
}

void PrintList(LinkList L)
{
	LNode * p=L;
	while(p->next!=NULL)
	{
		p=p->next;
		printf("%d ",p->data);
	}
	printf("\n");
}

int main(void)
{
	LinkList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	LNode * p=L;
	PrintList(L);
	int e;
	ListDelete(L,2,e);
	p=L;
	PrintList(L);
	return 0;
}

bool DeleteNode(LNode * p)
{
	if(p==NULL) return false;
	LNode * q=p->next;
	p->data=q->data;
	p->next=q->next;
	free(q);
	return true;
}

LNode * GetElem(LinkList L,int i)
{
	if(i<0) return NULL;
	LNode * p=L;
	int j=0;
	while(j<i&&p!=NULL)
	{
		p=p->next;
		j++;
	}
	return p;
}

LNode * GetElem(LinkList L,int i)
{
	if(i<0) return NULL;
	LNode * p=L;
	int j=0;
	while(j<i&&p!=NULL)
	{
		p=p->next;
		j++;
	}
	return p;
}

int ListLength(LinkList L)
{
	int i=0;
	LNode * p=L->next;
	while(p!=NULL)
	{
		p=p->next;
		i++;
	}
	return i;
}

while 循环
{
	//取数据元素
	ListInsert(LinkList,length+1,e); //插至链表尾部
    length++;
}

LinkList Link_TailInsert(LinkList &L) //正向建立单链表
{
	//初始化
	L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点
	LNode * p=L; //指针p指向头结点
	//用户输入数据、并依次生成结点,直至用户输入9999退出
	int x;
	scanf("%d",&x);
	while(x!=9999)
	{
		LNode * q=(LNode *)malloc(sizeof(LNode));
		p->next=q;
		p=q;
		p->data=x;
		scanf("%d",&x);
	}
	p->next=NULL; //尾指针置空，不做这一步，最后尾指针会指向自己
	return L;
}

LinkList Link_HeadInsert(LinkList &L)
{
	int a;
	LNode * p;
	//初始化
	L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点
	L->next=NULL; //必须指向NULL
	//输入数据、并把输入的数据插入到头结点之后
	scanf("%d",&a);
	while(a!=9999)
	{
		p=(LNode *)malloc(sizeof(LNode));
		p->data=a;
		p->next=L->next;
		L->next=p;
		scanf("%d",&a)；
	}
	return L;
}

//法一：通过新建一个链表实现
LinkList ReverseList(LinkList &L)
{
	LNode * p; //指针
	LinkList s=(LNode *)malloc(sizeof(LNode)); //生成一个新的链表
	s->next=NULL;
	while(L->next!=NULL)
	{
		//从头开始依次取下链表L的结点
		p=L->next; //指向要被取下的结点
		L->next=p->next;
		//把取下的数据使用头插法插入到新的链表s
		p->next=s->next;
		s->next=p;
	}
	return s;
}

//法二：就地转置，将头结点摘下，然后从第一结点开始，依次前插入到头结点的后面（头插法），直到最后一个结点为止。 
LinkList ReverseList2(LinkList &L)
{
	LNode *p,*q; //p指针指向位序为一的结点
	p=L->next;
	L->next=NULL; //取下头结点
	//使用头插法把结点从头依次插入头结点后面
	while(p!=NULL)
	{
		q=p->next; 
		p->next=L->next;
		L->next=p;
		p=q;
	}
	return L;
}

typedef struct DNode{
	int data;
	DNode * next,* prior;
}DNode,*DLinkList;

bool InitList(DLinkList &L)
{
	L=(DNode *)malloc(sizeof(DNode));
	if(L==NULL)
		return false;
	L->next=NULL;
	L->prior=NULL;
	return true;
}

bool Empty(DLinkList &L)
{
	return(L->next==NULL);
}

bool ListInsert(DNode * p,DNode * s)
{
	if(p==NULL||s==NULL) return false;
	s->next=p->next; //1
	if(p->next!=NULL)
		p->next->prior=s; //2
	s->prior=p; //3
	p->next=s;  //4  1,2必须在4前
	return true;
}

bool ListDelete(DNode * p) //删除指定结点的后继节点
{
	if(p==NULL) return false;
	DNode * q=p->next; 
	if(q==NULL) return false;
	p->next=q->next;
	if(q->next!=NULL) q->next->prior=p;
	free(q);
	return true;
}

void DestroyList(DLinkList &L)
{
	while(L->next!=NULL) ListDelete(L);
	free(L); //释放头结点
	L->next=NULL; //头指针置空
}

//后向遍历
while(p!=NULL)
{
    //...
    p=p->next;
}

//前向遍历
while(p->pror!=NULL) //跳过了头结点
{
    //...
    p=p->prior;
}

typedef struct LNode
{
	int data;
	LNode * next;
}LNode,*LinkList;

bool InitList(LinkList L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L=NULL) return false;
	L->next=L;
	return true;
}

bool Empty(LinkList L)
{
	if(L->next=L) return true;
	return false;
}

bool isTail(LinkList L,LNode * p) //判断一个结点是否为尾节点
{
	return(p->next==L);
}

typedef struct LNode
{
	int data;
	LNode * next;
	LNode * prior;
}LNode,*LinkList;

bool InitList(LinkList L)
{
	L=(LNode *)malloc(sizeof(LNode));
	if(L=NULL) return false;
	L->next=L;
	L->prior=L;
	return true;
}

bool Empty(LinkList L)
{
	if(L->next=L) return true;
	return false;
}

bool isTail(LinkList L,LNode * p) //判断一个结点是否为尾节点
{
	return(p->next==L);
}

bool ListInsert(DNode * p,DNode * s) 
{
	if(p==NULL||s==NULL) return false;
	s->next=p->next; //1
	p->next->prior=s; //2 尾节点会指向头结点，不会置空，因此不需要条件判断
	s->prior=p; //3
	p->next=s;  //4  1,2必须在4前
	return true;
}


bool ListDelete(DNode * p) //删除指定结点的后继节点
{
	if(p==NULL) return false;
	DNode * q=p->next; 
	p->next=q->next;
    q->next->prior=p;
	free(q);
	return true;
}

#define MaxSize 10

typedef struct Node
{
	int data;
	int next;
}SLinkList[MaxSize];

void InitList()
{
	SLinkList a;
}

//设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点
void Delete_x(LinkList &L,int x)
{
	LNode * p;
	if(L==NULL)return;
	while(L->data!=x)
	{
		Delete_x(L->next,x);
		return;
	}
	p=L;
	L=L->next;
	free(p);
	Delete_x(L,x);
}

//1.count=0,p,q指向链表头结点的后继结点；

//2.若p为空，返回0；

//3.若count<k,count累加，若count=k，指针q后移；

//4.p结点后移，

//5.若count等于k，则查找成功，输出该结点的data域，返回1;

//6.算法结束

#include <stdio.h>
#define MaxSize 10
typedef struct
{
	int data[MaxSize];
	int top;
}SeqStack;
//初始化
void InitStack(SeqStack &S)
{
	S.top=-1;
}
//栈空判断
bool StackEmpty(SeqStack S)
{
	return(S.top==-1);
}
//入栈
bool Push(SeqStack &S,int x)
{
	if(S.top==MaxSize-1) return false;
	S.data[++S.top]=x;
	return true;
}
//出栈
bool Pop(SeqStack &S,int &x)
{
	if(S.top==-1) return false;
	x=S.data[S.top--];
	return true;
}
//读取栈顶元素
bool GetTop(SeqStack S,int &x)
{
	if(S.top==-1) return false;
	x=S.data[S.top];
	return true;
}

//上述代码top指针初始指向栈顶
int main()
{
	SeqStack S;
	InitStack(S);
	printf("%d\n",StackEmpty(S));
	Push(S,2);
	printf("%d\n",StackEmpty(S));
	int x;
	Pop(S,x);
	printf("%d,%d\n",StackEmpty(S),x);
	Push(S,3);
	GetTop(S,x);
	printf("%d,%d\n",StackEmpty(S),x);
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
//定义栈结点
typedef struct SNode{
	int data;
	SNode * next;
}*LinkStack,SNode;
//初始化栈（不带头结点）
bool InitStack(LinkStack &S)
{
	S=NULL;
	return true;
}
//判空
bool StackEmpty(LinkStack S)
{
	return (S==NULL);
}
//入栈操作
bool Push(LinkStack &S,int x)
{
	//在头部插入元素
	SNode * p=(SNode *)malloc(sizeof(SNode));
	//这里并不需要区分是不是第一个结点，两者操作时一致的！！！
	p->data=x;
	p->next=S;
	S=p;
	return true;
}
//出栈操作（不带头结点）
bool Pop(LinkStack &S,int &x)
{
	if(S==NULL) return false;
	SNode * p=S;
	x=S->data;
	S=S->next;
	free(p);
	return true;
}
//打印栈中元素（不带头结点）
void PrintStack(LinkStack S)
{
	if(S==NULL) return;
	while(S!=NULL)
	{
		printf("%d ",S->data);
		S=S->next;
	}
	printf("\n");
}

//对于链式存储结构实现的栈（不带头结点）进行增删改查操作
int main(void)
{
	int x;
	LinkStack S;
	InitStack(S);
	printf("%d\n",StackEmpty(S));
	Push(S,1);
	Push(S,2);
	Push(S,5);
	Push(S,1);
	PrintStack(S);
	Pop(S,x);
	Pop(S,x);
	PrintStack(S);
	return 0;
}

#include <stdio.h>
#define MaxSize 10
typedef struct SeQueue
{
	int data[MaxSize];
	int front,rear;
};
//初始化队列，队头、队尾指针均指0
void InitQueue(SeQueue &Q){
	Q.front=0;
	Q.rear=0;
}
//队列判空:队头与队尾指向相同空间，即差值为0，队空
bool QueueEmpty(SeQueue Q)
{
	return (Q.front==Q.rear);
}
//入队操作：先将数据插入至队尾，再将尾指针后移
bool EnQueue(SeQueue &Q,int x)
{
	if((Q.rear+1)%MaxSize==Q.front) return false; //判断队列是否满，满则返回false,这里牺牲了一个存储空间用来区分队满和队空
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%MaxSize; //这里要注意！由于这种方式实现的队列在逻辑上似乎是循环的，也称作循环队列
	return true;
}
//出队操作：先将数据取出，再将头指针后移
bool DeQueue(SeQueue &Q,int &x)
{
	if(Q.front==Q.rear) return false; //判断是否队空
	x=Q.data[Q.front];
	Q.front=(Q.front+1)%MaxSize;
	return true;
}
//查;获取队头元素
bool GetHead(SeQueue Q,int &data)
{
	if(Q.front==Q.rear) return false;
	data=Q.data[Q.front];
	return true;
}
int main(void)
{
	SeQueue Q;
	int x;
	int data;
	InitQueue(Q);
	printf("队列是否为空：%d\n",QueueEmpty(Q));
	EnQueue(Q,1);
	printf("队列是否为空：%d\n",QueueEmpty(Q));
	GetHead(Q,data);
	printf("队头元素为：%d\n",data);
	DeQueue(Q,x);
	printf("队列是否为空：%d\n",QueueEmpty(Q));
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
//定义链式队列结点
typedef struct LinkNode
{
	int data;
	LinkNode * next;
}LinkNode;
//定义链式队列
typedef struct 
{
	LinkNode * front,* rear;
}LinkQueue;
//初始化(带头结点)
void InitQueue(LinkQueue &Q)
{
	Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode)); 
	Q.front->next=NULL;
}
//队列判空:如果头、尾指针指向同一个结点或者头结点的next指向为NULL则为空
bool QueueEmpty(LinkQueue Q)
{
	return (Q.front->next==NULL);
	//return (Q.front=Q.rear);
}
//入队操作(带头结点)
void EnQueue(LinkQueue &Q,int x)
{
	//申请一个新的结点用于存储待插入的数据
	LinkNode * p=(LinkNode *)malloc(sizeof(LinkNode));
	p->data=x;
	//将新结点入队,即在队尾插入新结点
	p->next=NULL;
	Q.rear->next=p;
	Q.rear=p;
}
//出队操作(带头结点)
void DeQueue(LinkQueue &Q,int &x)
{
	LinkNode * p;
	p=Q.front->next;
	x=p->data;
	Q.front->next=p->next;
	//！！如果删除的元素为表尾结点,要将尾指针指向头结点
	if(Q.rear==p)Q.rear=Q.front;
	free(p);
}
//带头结点版本
int main(void)
{
	int x;
	LinkQueue Q;
	InitQueue(Q);
	printf("队列是否为空：%d\n",QueueEmpty(Q));
	EnQueue(Q,2);
	printf("队列是否为空：%d\n",QueueEmpty(Q));
	DeQueue(Q,x);
	printf("删除的元素为：%d\n",x);
	printf("队列是否为空：%d\n",QueueEmpty(Q));
	return 0;
}

#include <stdio.h>
#include <stdlib.h>
//定义链式队列结点
typedef struct LinkNode
{
	int data;
	LinkNode * next;
}LinkNode;
//定义链式队列
typedef struct 
{
	LinkNode * front,* rear;
}LinkQueue;
//初始化队列（不带头结点）:使front、rear都指向NULL
void InitQueue1(LinkQueue &Q)
{
	Q.front=NULL;
	Q.rear=NULL;
}
//判断队列是否为空（不带头结点）
bool QueueEmpty1(LinkQueue Q)
{
	return (Q.front==NULL);
}
//入队操作(不带头结点)
void EnQueue1(LinkQueue &Q,int x)
{
	//申请一个结点用来存储入队数据
	LinkNode * p=(LinkNode *)malloc(sizeof(LinkNode));
	p->data=x;
	//执行入队操作
	p->next=NULL;
	if(Q.rear==NULL)
	{
		Q.front=p;
		Q.rear=p;
	}
	else
	{
		Q.rear->next=p;
		Q.rear=p;
	}
}
//出队操作(不带头结点)
void DeQueue1(LinkQueue &Q,int &x)
{
	LinkNode * p=Q.front;
	x=p->data;
	Q.front=p->next;
	//如果出队恰好使最后一个结点，那么要把rear恢复为NULL
	if(Q.rear==p)
		Q.rear=NULL;
	free(p);
}

int main(void)
{
	int x;
	LinkQueue Q;
	InitQueue1(Q);
	printf("队列是否为空：%d\n",QueueEmpty1(Q));
	EnQueue1(Q,2);
	printf("队列是否为空：%d\n",QueueEmpty1(Q));
	DeQueue1(Q,x);
	printf("删除的元素为：%d\n",x);
	printf("队列是否为空：%d\n",QueueEmpty1(Q));
	return 0;
}

#include <stdio.h>
#define MaxSize 10		
typedef struct
{
	char data[MaxSize];
	int top;
}SeqStack; 
//初始化栈
void InitStack(SeqStack &S)
{
	for(int i=0;i<MaxSize;i++)
	{
		S.data[i]=NULL;
	}
	S.top=-1; //指栈顶元素，初始时置为-1；
}
//判断栈是否为空
bool StackEmpty(SeqStack S)
{
	return S.top==-1;
}
//入栈
bool Push(SeqStack &S,char  x)
{
	if(S.top==MaxSize-1) return false;
	S.top++;
	S.data[S.top]=x;
	return true;
}
//出栈
bool Pop(SeqStack &S,char &x)
{
	if(S.top==-1) return false;
	x=S.data[S.top];
	S.top--;
	return true;
}
//核心代码，这里为了结果直观，对不同匹配情况进行了打印，考试时可以不用，在调用Push、Pop等时对其简单
//注 释，可直接调用
bool BraketCheck(char Str[],SeqStack S)
{
	//判断是否有括号1
	for(int i=0;i<6;i++)
	{
		//判断是否有左括号
		if(Str[i]=='['||Str[i]=='(')
		{
			//左括号入栈
			Push(S,Str[i]);
		}
		else
		{
			//判断是否栈空
			if(!StackEmpty(S))
			{
				char b;
				Pop(S,b); //弹出栈顶元素b
				//判断括号是否匹配，
				if(Str[i]==')'&&b=='(') { printf("%c %c\n",b,Str[i]);}
				else if(Str[i]==']'&&b=='['){ printf("%c %c\n",b,Str[i]);}
				else 
				{
					printf("Failed!Different type of baracet!\n");return false;
				}
			}
			else
			{
				 printf("Failed!Right Sigle.\n"); return false;
			}
		}
	}
	if(StackEmpty(S)){printf("Sucess!\n"); return true;}
	else{printf("Failed!Left Sigle!\n");return true;}
}
//栈的应用——括号的匹配
int main(void)
{
	SeqStack S;
	InitStack(S);
	char Str[6]={'[','(',')',']',')',')'};
	BraketCheck(Str,S);
	return 0;
}

//算法思想：设置操作数栈OPND，运算符栈OPTR，依次扫描表达式，遇到操作数则进操作数栈，遇到运算符则栈顶元素与运算符栈比较，若栈顶元素优先级低，则进栈，若栈顶元素优先级高则出栈。特别的，界限符'(运算优先级级最高直接入栈，)'则依次弹出运算符栈的元素，直到遇到‘（’，同时弹出操作数栈顶两个元素，第一个元素在运算符后，第二个元素在运算符前进行运算，将运算的结果重新压入操作数栈。
OprandType EvaluateExpression(){
    InitStack(OPND); InitStack(OPTR);
    PUSH(OPTR,'#');
    ch=getchar();
    while(GetTop(OPTR)!='#'||ch!='#'){
        if(!In(ch,OP)) Push(OPND,ch);//不是运算符则进栈
        else
            switch(Precede(GetTop(OPTR),ch)){ //拿栈顶元素与其进行比较
                case '<' : 
                    Push(OPTR,ch);ch=getchar();
                    break;
                case '=': //(,)中间没有其他运算符，脱括号
                    Pop(OPTR,x); ch=getchar();
                    break;
                case '>':
                    Pop(OPTR,theta);
                    pop(OPND,b);pop(OPND,a);
            		Push(OPND,Opread(a,theta,b));
                    break;
            } //switch
    } //while
} //EvalueateExpression

//算法思想：除8、取余倒排
void convention(int n){
    //初始化栈
    InitStack(S);
    //N除以8，取余数，余数入栈，n更新为商，直到商为0
    while(n>0){
    	 Push(S,n%8);
  		 n=n/8; 
    }
    for(!StackEmpty(S)){
        Pop(S,e);
        printf("%d",e);
    }
}

#include <stdio.h>
#define MaxSize 255
typedef struct 
{
	char ch[MaxSize];
	int len;
}MyString;
//从指定位序开始截取串的子串
bool SubString(MyString &Sub,MyString S,int pos,int len)
{
	if(pos+len-1>S.len) return false; //子串范围越界
	for(int i=pos;i<pos+len;i++)
	{
		Sub.ch[i-pos+1]=S.ch[i];
	}
	Sub.len=len;
	return true;
}
//比较两个串的大小
int CompareString(MyString S1,MyString S2)
{
	//逐个字符比较
	for(int i=1;i<=S1.len&&i<=S2.len;i++)
	{
		if(S1.ch[i]!=S2.ch[i]) return S1.ch[i]-S2.ch[i];	
	}
	//扫描过的字符皆相同，比较两字符串长度
	return S1.len-S2.len;
}
//定位子串
int indexString(MyString S,MyString Sub)
{
	//暂存截取串
	int i=1;
	MyString temp;
	temp.len=Sub.len;
	while(i<=S.len-Sub.len+1)
	{
		SubString(temp,S,i,Sub.len);
		if(CompareString(Sub,temp)!=0) ++i;
		else return i;
	}
	return 0;
}
//串的基本操作
int main(void)
{
	MyString S1;
	S1.ch[0]=NULL;
	S1.ch[1]='w';
	S1.ch[2]='z';
	S1.len=2;
	MyString S2;
	S2.ch[0]=NULL;
	S2.ch[1]='z';
	S2.len=1;
	printf("%d\n",indexString(S1,S2));
	return 0;
}

//串的朴素模式匹配算法
int Index(MyString S,MyString Sub)
{
	int i,j,k;//k用于定位S当前匹配到哪个位置,i,j分别用于S与Sub的活动定位
	k=1;
	i=k;
	j=1;
	while(S.len-k+1<=Sub.len)
	{
		if(S.ch[i]==Sub.ch[j])
		{
			++i;
			++j;
		}
		else
		{
			j=1;
			++k;
			i=k;
		}
		if(j>Sub.len) return k;
		else return 0;
	}
}

#include <stdio.h>
#define MaxSize 100
struct TreeNode{
	int value;
	bool isEmpty;
};

void InitTreeNode(TreeNode t[MaxSize])
{
	for(int i=0;i<MaxSize;i++){
		t[i].isEmpty=true;
	}
}
void main(){
	TreeNode t[MaxSize];
	InitTreeNode(t);
}

typedef struct BiTreeNode{
	int value;
	BiTreeNode * rchild,* lchild;
}BiTreeNode,* BiTree;

//插入根节点
	BiTree root=(BiTree)malloc(sizeof(BiTreeNode));
	root->value=1;
	root->lchild=NULL;
	root->rchild=NULL;
	return true;

//插入新节点
	BiTreeNode * p=(BiTreeNode *)malloc(sizeof(BiTreeNode));
	p->value=2;
	p->lchild=NULL;
	p->rchild=NULL;
	root->lchild=p;
	return true;

//先序遍历
void PreOrder(BiTree T)
{
	if(T!=NULL)
	{
		Visit(T);
		PreOrder(T->lchild);
		PreOrder(T->rchild);
	}
}

//求树的深度：后序的应用
int TreeDepth(BiTree T)
{
	if(T==NULL) return 0;
	int l=TreeDepth(T->lchild);
	int r=TreeDepth(T->rchild);
	return l>r?l+1:r+1;
}

//中序遍历（非递归实现）
bool InOrderTraverse(BiTree T)
{
    BiTreeNode * p=T; InitStack(S); //初始化一个栈
    while(p||!ISEmpty(S))
    {
        if(p){push(S,p);p=p->lchild;}
        else
        {
            pop(S,q);
            printf("%d,",q->data);
            p=q->rchild;
        }
    }
    return true;
}

//层次遍历
void LevelOrder(BiTree T)
{
	LinkQueue Q;
	InitQueue(Q);
	BiTree p; //用来存DeQueue后的树结点
	EnQueue(Q,T);
	while(!IsEmpty(Q))
	{
		DeQueue(Q,p);
		Visit(p);
		if(T->lchild!=NULL){EnQueue(Q,p->lchild);}
		if(T->rchild!=NULL){EnQueue(Q,p->rchild);}
	}
	
}

#include <stdio.h>
//定义线索二叉树结点
typedef struct ThreadNode
{
	int data; //数据域存放二叉树数据
	ThreadNode * lchild,*rchild; //左右孩子
	int ltag,rtag; //左右孩子标志位
}ThreadNode,* ThreadTree;

ThreadNode * pre; //全局变量，当前结点的前驱结点

//访问某一个树结点同时进行线索化
void Visit(ThreadNode * p)
{
	if(p->lchild==NULL)
	{
		p->lchild=pre;
		p->ltag=1;
	}
	if(pre!=NULl&&pre->rchild==NULL)
	{
		pre->rchild=p; //建立前驱结点的后继线索
		pre->rtag=1;
	}
	pre=p; //把pre置为当前结点，当下一次调用visit时访问的pre就是当前结点（下一次遍历的前驱）
}
//二叉树中序遍历（并调用Visit进行线索化）
void InThread(ThreadTree T)
{
    if（T！=NULL）
    {
	 InThread(T->lchild);
	 Visit(T);
	 InThread(T->rchild);
    }
}

void CreateInThread(ThreadTree T)
{
    pre=NULL;
    if(T!=NULL)
    {
        InThread(T);
        if(pre->rchild==NULL) pre->rtag=1; //对最后一个结点进行特殊处理
    }  
}

//二叉树先序遍历（并调用Visit进行线索化）
void InThread(ThreadTree T)
{
    if（T！=NULL）
    {
    Visit(T);
    if（T->LTag==0）InThread(T->lchild); //!!!注意此处的判断条件，因为先序遍历访问顺序是根左右，如果根线索化了，无论根有没有左孩子，lchild都有指向，因此必须加此判断条件，判断其到底有没有左孩子
	InThread(T->rchild);
    }
}

//找到以p为根的子树中第一个被中序遍历的结点，即最左下的那个结点
ThreadNode * FirstNode(ThreadNode * p)
{
	while(p->ltag==0) p=p->lchild;
	return p;
}

//找到某个结点的后继节点
ThreadNode * NextNode(ThreadNode * p)
{
	if(p->rtag==1) return p->rchild;
	else if(p->rchild==0) return FirstNode(p->rchild); //返回右子树最左下的那个结点
}

void Inorder(ThreadTree * T)
{
    for(ThreadNode * p=FirstNode(T)；p!=NULL；p=NextNode(p)) //先找到第一个结点，然后不断的找其后继
        visit(p);
}

//平衡二叉树结点
typedef struct AVLNode
{
	int ket; //数据域
	int balance; //平衡因子
	struct AVLNode * lchild,* rchild;
}* AV

//LL平衡旋转（右旋）
f->lchild=p->rchild;
p->rchild=f;
gf->lchild/rchild=p;

//-----图的组（邻接矩阵）存储表示-----
#define INFINITY INT_MAX //最大值∞
#define MAX_VERTEX_NUM 20 //最大的顶点个数
typedef enum {DG,DN,UDG,UDN}GraphKind; //{有向图（Digraph），有向网（DiNet），无向图(UniDigraph),无向网} 
typedef struct ArcCell{
    VRType adj; //VRType是顶点关系类型。对无权图，用1或者0表示相邻与否；对带权图，则为权值类型。
    InfoType *info; //该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
    VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
    AdjMatrix arcs; //邻接矩阵
    int vexnum,arcnum; //图的当前顶点数与边数
    GraphKind kind; //图的种类标志
}MGpraph

//---------图的邻接表存储表示-----------
#define MAX_VERTEX_NUM 20
typedef struct ArcNode{
    int adjvex; //该弧指向的顶点的位置
    struct ArcNode *nextarc; //指向下一条弧的指针
    InfoType *info; //该弧相关信息的指针
}ArcNode;
typedef struct VNode{
    VertexType data; //顶点信息
    ArcNode *firstarc;  //指向的一条依附该顶点的弧的指针
}VNode，AdjList[MAX_VERTEX_NUM]；
typedef struct{
	AdjList vertices;
	int vexnum,arcnum; //图的当前顶点数和弧数
	int kind; //图的种类
}

void BFSTraverse(Graph G,Status(*visit)(int v)){
    //按广度优先搜索遍历非递归遍历图G，使用辅助队列和访问标志数组visited
    for(v=0;v<G.vexnum;v++)	 visited[v]=FALSE;
    InitQueue(Q);
    for(v=0;v<G.vexnum;++v)
        if(!visited[v]){
        	visited[v]=True;
        	visit(v);
            EnQueue(Q,v);
            while(!QueueEmpty(Q)){
                DeQueue(Q,u);
                for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
                      if(!visited[w]){
                          visited[w]=True;
        				visit(w);
                		EnQueue(Q,w);
                      } //if
                } //while
        } //if
} //BFSTraverse

void DFSTraverse(Graph G,Statues(* Visit)(int v)){
    for(v=0;v<G.vexnum;++v) visited[v]=FALSE;
    for(v=0;v<G.vexnum;++v){
        if(!visited[v]) DFS(G,v);
    }
}
void DFS(Graph G,int v){
    if(!visited[v]) {
        visit(G,v);
        visted[v]=TRUE;
    } //if
    while(w=FirstAdjVetex(G,v);w>=0;w=NextAdjVetex(G,v,w)){
        if(!visited[w]){
        	DFS(G,w);
        } //if 
    } //while
} //DFSTraverse

//prim算法的思想：选择一个初始顶点，把它加入辅助数组，计算该顶点到其他顶点的代价，选择其中最小代价对应点加入辅助数组，扫描加入新的顶点有没有使其到各个顶点的代价变化，并更新代价数组；重复进行以上步骤，知道所有顶点都已经加入了辅助数组
//记录顶点集U到V-U的代价最小的边的辅助数组
struct{
    VertexType adjvex;
    VRType lowcost;
}closedge[MAX_VERTEX_NUM];

void MiniSpanTree_PRIM(MGraph G,VetexType u){
    //用prim算法从第v个顶点出发构造网的最小生成树T，并输出最小生成树的各条边
  	k=LocateVex(G,u);
    for(j=0;j<G.vexnum;j++) //辅助数组初始化
        if(j!=k) closedge[j]={u,G.arcs[k][j].adj}; //{adjvex,lowcost}
    closedge[k].lowcost=0; //初始，U={u}
    for(i=1;i<G.vexnum;++i){ //选择其余G.vexnum-1个顶点
        k=minimum(closedge);  //求出T的下一个顶点:第k顶点
        printf(closedge[k].adjvex,G.vexs[k]);
        closedge[k].lowcost=0;
        for(j=0;j<G.vexnum;++j)
            if(G.arcs[k][j]).adj<closedge[j].lowcost)
                closedge[j]={G.vexs[k],G.arcs[k][j].adj};
    }
} //MiniSpanTree

bool viisted[Max_VeTex_num];

void BFS_Min_Distance(Graph G,int v){
    //BFS求无向图的单源最短路径
    for(int i=0;i<G.vexNum;i++){
        d[i]=Inifinate; //最短路径大小
        path[i]=-1; //最短路径从哪里过来
    }
    d[v]=0; //起点到自己的距离置为0；
    visited[v]=true;
    EnQueue(Q,v);
    while(!IsEmpty(Q)){
        DeQueue(Q,v);
        for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
            if(!visited[w]){
                visited[w]=true;
                EnQueue(Q,w);
                d[w]=d[v]+1;
                path[w]=u;
              }
        }
    }
}

Status TopologicalOrder(ALGraph G,Stack &T){
    //有向网G采用邻接表存储结构，求各顶点事件最早发生时间ve（全局变量）
    //T为拓扑序列顶点栈，S为零入度顶点栈
    //若G无回路，则栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR
    FindInDegree(G,indegree); //对各顶点求入度indegree[0...vernum-1]
    InitStack(S)； //建立并初始化零入度顶点栈
    count=0;ve[0...G.vexnum-1]=0; //初始化
    while(!StackEmpty(S)){
        Pop(S,j); Push(T,j);++count; //j号顶点入T栈并计数
        for(p=G.vertices[j].firstarc;p;p->nextarc){
            k=p->adjvex; //对j号顶点的每个邻接点的入度减1
            if(--indgree[k]==0) Push(S,k); //若入度减为0，则入栈
            if(ve[j]+*(p->info)>ve[k]) ve[k]=ve[j]+*(p->info) ;
        }
    }
    if(count<G.vexnum) return ERROR; //该有向图有回路
    else retrun OK;
}

//直接插入排序，进行增序排序
void InsertSort(SqlList &L){
    //从第2个元素开始，进行i-1轮插入
    for(int i=2;i<=L.length;i++){
        //如果待插入元素与之前元素比较已经属于有序，无需操作，否则执行操作
        if(L.r[i].key<L.r[i-1].key){
            //复制待插入元素为哨兵
            L.r[0]=L.r[i];
            for(int j=i-1;L.r[0].key<L.r[j].key;j--) //比待插入元素大的都往后移
                    L.r[j+1]=L.r[j];
            L.r[j]=L.r[0];
        } //if
    } //for
} //InsertSort

void BInsertSort(SeqList &L)
{
      //从第二个元素开始把待排序序列插入到有序序列
    for(int i=2;i<=L.length;i++)
    {
        L.r[0]=L.r[i]; 
        int low=1,high=i-1; //从第i-1个元素（有序序列的最后一个元素）开始往前找空
        while(low<=high){ //当low=high,还执行一次，将mid与low，high指向相同位置，并因此会执行else语句，使high+1位置为待插入元素的位置
             mid=(low+high)/2;
             if(L.r[mid].key<L.r[0].key) low=mid+1;
       		 else high=mid-1;
        } //循环结束，high+1为插入位置
        for(int j=i-1;j>high+1;--j) L.r[j+1]=L.r[j];
        L.r[high+1]=L.r[0];
    }
}

//一趟增量为dk的希尔排序
void ShellSort(SeqList &L,int dk){
    for(i=dk+1;i<=L.length;i++){ //从dk+1个元素开始，把无序子序列的元素插入有序序列
        if(L.r[i]<L.r[i-dk]){ //当第i个元素比他前面子序列的元素要小，则执行，否则已经有序，无需操作
            L.r[0]=L.r[i]; //复制为哨兵
            for(j=i-dk;j>0&&(L.r[0].key<L.r[j].key);j-=dk) //比L.r[i]大的元素后移空位置
                L.r[j+dk]=L.r[j];
             L.r[j]=L.r[0];
        }
    }
}

void BubbleSort(SeqList &L){
    for(int i=0;i<L.length;i++){
        flag=false; //用来记录一趟冒泡排序是否发生了交换
        for(int j=L.length;j>i;j--){
            if(L.r[j-1].key>L.r[j].key) //逆序：前面的比后面的大，则交换
            	{
                	swap(L.r[j-1],L.r[j]);
            		flag=true;
            	}
        }
        if(flag==false) return;
    }
}

void QuickSort(ElemType A[],int low,int high)
{
    if(low<high) //递归跳出条件
    {
        //partition()就是划分操作，将表A[low...high]划分为两个子表
        int pivotopos=partition(A,low,high); //划分
        QuickSort(A,low,privotopos-1); //依次对两个子表进行递归排序
        QuickSort(A,privotopos+1,high);
    }
}

int Partition（SqlList &L,int low,int high){
    L.r[0]=L.r[low];
    privotkey=L.r[low].key;//将当前表中的第一个元素设置为枢轴值，将表进行划分
    while(low<high){ //循环跳出条件
        while(low<high&&L.r[high].key>=privotkey) --high;
        L.r[low]=L.r[high];
        while(low<high&&L.r[low].key<=prvotkey) ++low;
        L.r[high]=L.r[low];
    }
    L.r[low]=L.r[0]; //枢轴纪录到位
    return low; //返回枢轴位置
}

void SeclectSort(SeqList &L){
    for(int i=1;i<L.length;i++){ //让i从1到n-1进行n-1趟选择排序（最后一个位置不用再选择了）
        min=i;
        for(j=i+1;j<L.length;j++){
            if(L.r[j].key<L.r[min].key)
            	min=j;
        }
        if(min!=i) swap(L.r[i]=L.r[min]);
    }
}

void HeapSort(HeapType &H)
{
    //对顺序表进行堆排序
    for(i=H.length/2;i>0;--i) //从最后一个非叶子结点开始建立堆
        HeapAdjust(H,i,H.length); 
    for(i=H.length;i>1;--i){
         //...输出堆顶元素
         H.r[1]<-->H.r[i];  //将堆顶记录和最后一个记录交换
         HeapAdjust(H,1,i-1); //重新建堆
    }
}

void HeapAdjust(HeapAdjust &H,int s,int m){ //调整为大顶堆
    rc=H.r[s]; //暂存堆顶元素
    for(j=2*s;j<=m;j*=2){ //从上到下调整。让j指向堆顶左孩子，对其子树依次执行循环体（j*=2）
        if(j<m&&LT(H.r[j].key,H.r[j+1].key)) ++j; //如果左孩子小于右孩子，那么把j指右孩子，如果j==m，说明j已经是最后一个结点了，没有右孩子
        if(!LT(rc.key,H.r[j].key)) break; //比较堆顶与孩子结点大小，如果堆顶已经比孩子大，break；
        H.r[s]=H.r[j];  //否则，把堆顶置换为孩子结点元素 
        s=j; //对其子树进行判断调整，以调整由于之前置换导致的子树下坠情况
    }
    H.r[s]=rc; //把暂存的元素插入最后空出的位置
}

void Merge(RcdType SR[],RcdType TR[],int i,int m,int n){
    //两个有序子序列的归并，SR中存待归并数据，TR是数据暂存的临时空间，i是SR第一个序列开始，m是第1个子序列结尾位置，n是第2个子序列结束位置
    for(j=m+1,k=i;i<=m&&j<=n;++k){//j指向第二个子序列开始位置,k指向i指针对应位置（即让TR插入元素的起始位置与SR相同）
        if(LQ(SR[i].key,SR[j].key)) TR[k]=SR[i++];
        else TR[k]=SR[j++];
    }
    //判断哪个子序列还有剩余元素，全部复制到TR
    if(i<=m) TR[k...n]=SR[i...m]; //伪代码，可以用while循环实现
    if(j<=n) TR(k...n)=SR[j...n];
}

void MSort(RcdType SR[],RcdType &TR1[],int s,int t){
    if(s==t) TR1[s]=SR[s];
    else{
        m=s+t/2;
        MSort(SR,TR2,s,m);
        MSort(SR,TR2,m+1,t);
        Merge(TR2,TR1,s,m,t);
    }
}

void MergeSort(SqlList &L){
    Msort(L.r,L.r,1,L.length);
}

        if(flag==false) return;
    }
}

void QuickSort(ElemType A[],int low,int high)
{
    if(low<high) //递归跳出条件
    {
        //partition()就是划分操作，将表A[low...high]划分为两个子表
        int pivotopos=partition(A,low,high); //划分
        QuickSort(A,low,privotopos-1); //依次对两个子表进行递归排序
        QuickSort(A,privotopos+1,high);
    }
}

int Partition（SqlList &L,int low,int high){
    L.r[0]=L.r[low];
    privotkey=L.r[low].key;//将当前表中的第一个元素设置为枢轴值，将表进行划分
    while(low<high){ //循环跳出条件
        while(low<high&&L.r[high].key>=privotkey) --high;
        L.r[low]=L.r[high];
        while(low<high&&L.r[low].key<=prvotkey) ++low;
        L.r[high]=L.r[low];
    }
    L.r[low]=L.r[0]; //枢轴纪录到位
    return low; //返回枢轴位置
}