---

请注意：所包含的头文件如下

#pragma once
#include "targetver.h"
#include <stdio.h>
#include <tchar.h>
#include"LinkList.h"
#include"DLinkedList.h"
#include<stdlib.h>
#include"SqList.h"
#include"preface.h"

链表

题目24

求孪生和： 一个长度为n（n为偶数）的不带头节点的单链表，且结点值都大于0，设计算法求这个单链表的最大孪生和，孪生和定义为第一个结点与其孪生结点之和，对于第i个结点，其孪生结点为第n-i-1个结点

int get_big_sum(LinkList L)
{
	LNode*pre=L->next,*last=L->next;
	while(last)
	{
		pre=pre->next;
		last=last->next->next;
	}//链表长度为偶数，那么last为空时pre就来到了链表的中间位置
	//逆置链表
	LNode*now=NULL;
	while(pre)
	{
		LNode*next=pre->next;
		pre->next=now;
		now=pre;
		pre=next;
	}
	LNode*first=L->next;
	int max=(now->data+first->data);
	while(now)
	{
		if(max<(now->data+first->data))
		{
			max=now->data+first->data;
		}
		first=first->next;
		now=now->next;
	}
	return max;
	
}

注意我只写了带头节点创建链表的方法，但是是按不带头结点的方法进行处理的。

#include "stdafx.h"
int main()
{
	LinkList L;
	initLinkList(L);
	createLinkListBytail(L);
	printLinkList(L);
	
	printf("\nmax=%d\n",get_big_sum(L));
	system("pause");
	return 0;
}

题目25

将链表进行划分，并保持其相对的次序。例如，L={1,5,4,4,2,5,3,2,6,5,3,4}。且target=4
小于目标值的放在左边，大于目标值的放在右边

void divide_linklistL(LinkList &L, int target)
{
	LinkList A,B,C;
	initLinkList(A);
	initLinkList(B);
	initLinkList(C);
	LNode*pre=L,*last=pre->next,*a=A,*b=B,*c=C;
	while(pre->next)
	{
		if(last->data>target)
		{
			pre->next=last->next;
			last->next=a->next;
			a->next=last;
			a=last;
			last=pre->next;
		}else if(last->data<target){
			pre->next=last->next;
			last->next=b->next;
			b->next=last;
			b=last;
			last=pre->next;
		}else{
			pre->next=last->next;
			last->next=c->next;
			c->next=last;
			c=last;
			last=pre->next;
		
		}//保持相对位置不变，用的头插法
	}
	L->next=B->next;
	b->next=C->next;
	c->next=A->next;//将各个链表串起来
	free(A);
	free(B);
	free(C);

}

下面是测试代码：

#include "stdafx.h"
int main()
{
	LinkList L;
	initLinkList(L);
	createLinkListBytail(L);
	printLinkList(L);
	divide_linklistL(L,5);
	printLinkList(L);
	system("pause");
	return 0;
}

---

队列

基本操作

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

SeQueue.h

#pragma once
typedef int ElemType;
#define MAXSIZE 8

typedef struct{
	ElemType data[MAXSIZE];
	int front;
	int rear;
	int size;
}SeQueue;

//初始化队列
void initQueue(SeQueue &Q);

//判断队列是否为空
bool isEmpty(SeQueue Q);

//元素入队
bool enQueue(SeQueue &Q,ElemType x);

//出队
ElemType deQueue(SeQueue &Q);

//获取队头
ElemType getHead(SeQueue Q);

//获取队列长度
int getSize(SeQueue Q);

//打印队列元素
void print(SeQueue Q);

实现函数

#include"All.h"


//初始化队列
void initQueue(SeQueue &Q)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		Q.data[i]=0;
	}
	Q.size=0;
	Q.front=0;
	Q.rear=0;
}

//判断队列是否为空
bool isEmpty(SeQueue Q)
{
	return Q.front==Q.rear;
	//return Q.size==0;

}

//元素入队
bool enQueue(SeQueue &Q,ElemType x)
{
	if(Q.rear>=MAXSIZE)//Q.rear>=MAXSIZE
	{
		return false;
	}
	Q.data[Q.rear++]=x;
	Q.size++;
	return true;
}

//出队
ElemType deQueue(SeQueue &Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		Q.size--;
		return Q.data[Q.front++];
	}

}

//获取队头
ElemType getHead(SeQueue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}
	return Q.data[Q.front];
}

//获取队列长度
int getSize(SeQueue Q)
{
	return Q.size;
	//return Q.rear-Q.front
}

//打印队列元素
void print(SeQueue Q)
{
	if(isEmpty(Q));
	for(int i=Q.front;i<Q.rear;i++)
	{
		printf("%d ",Q.data[i]);
	}
	printf("\n");
	printf("Q.front=%d\n",Q.front);
	printf("Q.rear=%d\n",Q.rear);
	printf("Q.size=%d\n",Q.size);
}

测试结果

#include"All.h"

int main()
{
	SeQueue Q;
	initQueue(Q);
	for(int i=0;i<5;i++)
	{
		enQueue(Q,i);
	}
	print(Q);
	printf("\n");
	for(int i=0;i<3;i++)
	{
		ElemType x=deQueue(Q);
		printf("当前出队的元素值：%d\n",x);
	}
	print(Q);
	printf("\n");
	for(int i=10;i<15;i++)
	{
		enQueue(Q,i);
	}
	print(Q);
	system("pause");
	return 0;
}

结果：

0 1 2 3 4
Q.front=0
Q.rear=5
Q.size=5

当前出队的元素值：0
当前出队的元素值：1
当前出队的元素值：2
3 4
Q.front=3
Q.rear=5
Q.size=2

3 4 10 11 12
Q.front=3
Q.rear=8
Q.size=5
请按任意键继续. .

循环队列

头文件

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

#pragma once
typedef int ElemType;
#define MAXSIZE 8

typedef struct{
	ElemType data[MAXSIZE];
	int front;
	int rear;
	int size;
	int tag;//来标记是空队还是满队0为空1为有元素
}Queue;

//初始化队列
bool initQueue(Queue &Q);

//判断队列是否为满
bool isFull(Queue Q);

//判断队空
bool isEmpty(Queue Q);

//元素x入队
bool enQueue(Queue &Q,ElemType x);

//出队
ElemType deQueue(Queue &Q);

//取队头元素
ElemType getHead(Queue Q);

//获取队列长度
int getSize(Queue Q);

//打印队列元素
void printQueue(Queue Q);

函数实现

#include"All.h"

//初始化队列
bool initQueue(Queue &Q)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		Q.data[i]=0;
	}
	Q.front=0;
	Q.rear=0;
	Q.size=0;
	Q.tag=0;
	return true;
}

//判断队列是否为满
bool isFull(Queue Q)
{
	return (Q.rear+1)%MAXSIZE==Q.front;
	//reurn size==MAXSIZE;
	//return Q.tag==1&&Q.front==Q.rear;
}

//判断队空
bool isEmpty(Queue Q)
{
	return Q.front==Q.rear;
	//return size==0;
	//return Q.front==Q.rear&&tag==0;
}

//元素x入队
bool enQueue(Queue &Q,ElemType x)
{
	if(isFull(Q))
	{
		return false;
	}
	Q.data[Q.rear]=x;
	Q.rear=(Q.rear+1)%MAXSIZE;
	//Q.size++;
	/*if(Q.rear==Q.front)
	{
		Q.tag=1;
	}*/
	return true;
}

//出队
ElemType deQueue(Queue &Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		ElemType x=Q.data[Q.front];
		Q.front=(Q.front+1)%MAXSIZE;
		Q.size--;
		//if(Q.front==Q.rear)
		//{
		//	Q.tag=0;
		//}
		return x;
	}
}

//取队头元素
ElemType getHead(Queue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}
	ElemType x=Q.data[Q.front];
	return x;
}

//获取队列长度
int getSize(Queue Q)
{
	//return Q.rear-Q.front;//队头在队尾前面
	//return (Q.rear-Q.front+MAXSIZE);//队尾在队头前面
	return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;//合并
	//return Q.tag?((Q.rear-Q.front+MAXSIZE)%MAXSIZE):MAXSIZE;
	//return Q.size;
}

//打印队列元素
void printQueue(Queue Q)
{
	if(isEmpty(Q))
	{
		return;
	}
	int len=getSize(Q);
	int i=Q.front;
	while(len>0)
	{
		printf("%d ",Q.data[i]);
		i=(i+1)%MAXSIZE;
		len--;
	}
	printf("\n");
}

测试

#include"All.h"

int main()
{
	Queue Q;
	initQueue(Q);
	for(int i=0;i<5;i++)
	{
		enQueue(Q,i);
	}
	printQueue(Q);
	for(int i=0;i<2;i++)
	{
		deQueue(Q);
	}
	printQueue(Q);
	for(int i=10;i<15;i++)
	{
		enQueue(Q,i);
	}
	printQueue(Q);
	system("pause");
	return 0;
}

结果

0 1 2 3 4
2 3 4
2 3 4 10 11 12 13
请按任意键继续. . .

---

链队列

头文件

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

结构体+函数声明

#pragma once

typedef int ElemType;

typedef struct LinkQueue{
	ElemType data;
	LinkQueue*next;
}LNode;//结点结构

typedef struct{
	LNode*front;
	LNode*rear;
	int size;
}Queue;//队列结构

//初始化队列
void initQueue(Queue &Q);

//判断队列是否为空
bool isEmpty(Queue Q);

//入队
void enQueue(Queue &Q,ElemType x);

//出队
ElemType deQueue(Queue &Q);

//取队头元素
ElemType getHead(Queue Q);

//获取队列长度
int getSize(Queue Q);

//打印队列元素
void print(Queue Q);

函数实现

#include"All.h"

//初始化队列
void initQueue(Queue &Q)
{
	Q.front=NULL;
	Q.rear=NULL;
	Q.size=0;
}

//判断队列是否为空
bool isEmpty(Queue Q)
{
	return (Q.front==NULL||Q.rear==NULL||Q.size==0);
}

//入队
void enQueue(Queue &Q,ElemType x)
{
	LNode*node=(LNode*)malloc(sizeof(LNode));
	node->data=x;
	node->next=NULL;
	if(isEmpty(Q))
	{
		Q.rear=node;
		Q.front=node;
	}else{
		Q.rear->next=node;
		Q.rear=node;
	}
	Q.size++;
}

//出队
ElemType deQueue(Queue &Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}
	LNode*pre=Q.front;
	Q.front=Q.front->next;
	ElemType x=pre->data;
	free(pre);
	if(Q.front==NULL)
	{
		Q.rear=NULL;
	}
	Q.size--;
	return x;
}

//取队头元素
ElemType getHead(Queue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		return Q.front->data;
	}
}

//获取队列长度
int getSize(Queue Q)
{
	return Q.size;
}

//打印队列元素
void print(Queue Q)
{
	if(isEmpty(Q))
	{
		return;
	}
	LNode*pre=Q.front;
	while(pre)
	{
		printf("%d ",pre->data);
		pre=pre->next;
	}
	printf("\n");
}

测试

#include"All.h"

int main()
{
	Queue Q;
	initQueue(Q);
	for(int i=0;i<10;i++)
	{
		enQueue(Q,i);
	}
	print(Q);
	for(int i=0;i<6;i++)
	{
		deQueue(Q);
	}
	print(Q);
	system("pause");
	return 0;
}

结果

0 1 2 3 4 5 6 7 8 9
6 7 8 9
请按任意键继续. . .

---

双端队列

头文件+结构体+函数声明

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

#pragma once

typedef int ElemType;

typedef struct DNode{
	ElemType data;
	DNode*prior;
	DNode*next;
}DNode;

typedef struct{
	DNode*front;//队尾
	DNode*rear;//队头
	int size;//队列大小
}DeQueue;

//1初始化双端队列//带头结点
void initQueue(DeQueue &Q);

//2判断队列是否为空
bool isEmpty(DeQueue Q);

//3向队头添加元素
void pushHead(DeQueue &Q,ElemType x);

//4从队头移除元素
ElemType popHead(DeQueue &Q);

//5在队尾添加元素
void pushTail(DeQueue &Q,ElemType x);

//6从队尾删除元素
ElemType popTail(DeQueue &Q);

//7获取表头
ElemType peekHead(DeQueue Q);

//8取表尾
ElemType peekTail(DeQueue Q);

//9从头到尾打印队列
void printHead(DeQueue Q);

//10从尾到头打印
void printTail(DeQueue Q);

//11获取队列长度
int length(DeQueue Q);

函数实现

#include"All.h"

//初始化双端队列//带头结点
void initQueue(DeQueue &Q)
{
	DNode*node=(DNode*)malloc(sizeof(DNode));
	node->next=NULL;
	node->prior=NULL;
	Q.rear=node;
	Q.front=node;
	Q.size=0;
}

//判断队列是否为空
bool isEmpty(DeQueue Q)
{
	return Q.size==0||Q.front==Q.rear;
}

//向队头添加元素
void pushHead(DeQueue &Q,ElemType x)
{
	
	DNode*pre=(DNode*)malloc(sizeof(DNode));
	pre->data=x;
	pre->next=NULL;
	pre->prior=NULL;
	if(isEmpty(Q))
	{
		pre->prior=Q.front;
		Q.front->next=pre;
		Q.rear=pre;
	}else{
		pre->next=Q.front->next;
		Q.front->next->prior=pre;
		Q.front->next=pre;
		pre->prior=Q.front;
	}
	Q.size++;
	}

//从队头移除元素
ElemType popHead(DeQueue &Q)
{
	if(isEmpty(Q))
	{
		return-999;
	}
	ElemType x;
	if(Q.front->next==Q.rear)//只有一个元素时
	{
		x=Q.rear->data;
		free(Q.rear);
	}else{
		DNode*pre=Q.front->next;
		pre->next->prior=Q.front;
		Q.front->next=pre->next;
		x=pre->data;
		free(pre);
	}//不止一个元素时
	Q.size--;	
	return x;
}

//在队尾添加元素
void pushTail(DeQueue &Q,ElemType x)
{
	DNode*pre=(DNode*)malloc(sizeof(DNode));
	pre->data=x;
	pre->next=NULL;
	pre->next=Q.rear->next;
	pre->prior=Q.rear;
	Q.rear->next=pre;
	Q.rear=pre;
	Q.size++;
}

//从队尾删除元素
ElemType popTail(DeQueue &Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}
	DNode*last=Q.rear;
	ElemType x=last->data;
	Q.rear=Q.rear->prior;
	Q.rear->next=NULL;
	free(last);
	Q.size--;
	return x;
}

//获取表头
ElemType peekHead(DeQueue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		return Q.front->next->data;
	}
}

//取表尾
ElemType peekTail(DeQueue Q)
{
	if(isEmpty(Q))
	{
		return -999;
	}else{
		return Q.rear->data;
	}
}


//从头到尾打印队列
void printHead(DeQueue Q)
{
	if(isEmpty(Q))
	{
		return;
	}else{
		DNode*pre=Q.front;
		while(pre->next)
		{
			pre=pre->next;
			printf("%d ",pre->data);
		}
		printf("\n");
	}
}

//从尾到头打印
void printTail(DeQueue Q)
{
	if(isEmpty(Q))
	{
		return;
	}else{
		DNode*last=Q.rear;
		while(last!=Q.front)
		{
			printf("%d ",last->data);
			last=last->prior;
		}
		printf("\n");
	}
	
}

//获取队列长度
int length(DeQueue Q)
{
	return Q.size;
}

测试

#include"All.h"

int main()
{
	DeQueue Q;
	initQueue(Q);
	for(int i=0;i<5;i++)
	{
		pushHead(Q,i);
	}
	printf("从头到尾：");
	printHead(Q);
	printf("从尾到头：");
	printTail(Q);
	printf("队列长度%d",length(Q));
	printf("\n\n");

	for(int i=10;i<13;i++)
	{
		pushTail(Q,i);
	}
	printf("从头到尾：");
	printHead(Q);
	printf("从尾到头：");
	printTail(Q);
	printf("队列长度%d",length(Q));
	printf("\n\n");

	for(int i=0;i<2;i++)
	{
		popHead(Q);
	}
	printf("从头到尾：");
	printHead(Q);
	printf("从尾到头：");
	printTail(Q);
	printf("队列长度%d",length(Q));
	printf("\n\n");

	for(int i=0;i<2;i++)
	{
		popTail(Q);
	}
	printf("从头到尾：");
	printHead(Q);
	printf("从尾到头：");
	printTail(Q);
	printf("队列长度%d",length(Q));
	printf("\n\n");

	system("pause");
	return 0;
}

结果

从头到尾：4 3 2 1 0
从尾到头：0 1 2 3 4
队列长度5

从头到尾：4 3 2 1 0 10 11 12
从尾到头：12 11 10 0 1 2 3 4
队列长度8

从头到尾：2 1 0 10 11 12
从尾到头：12 11 10 0 1 2
队列长度6

从头到尾：2 1 0 10
从尾到头：10 0 1 2
队列长度4

请按任意键继续. . .
    

---

栈

栈的基本操作

我这里记录三种

顺序栈

1. 顺序栈的结构体及基本操作

   头文件，所有的头文件都放在一个头文件All.h里

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

   #pragma once
   #define MAXSIZE 128
   typedef int ElemType;
   
   typedef struct Stack{
   	
   	ElemType data[MAXSIZE];
   	int top;
   	int length;
   }SqStack;
   
   //初始化栈
   void initStack(SqStack &S);
   
   //判断栈是否为空
   bool isEmpty(SqStack S);
   
   //如果栈没有满，将x入栈
   bool push(SqStack &S, ElemType x);
   
   //如果不为空，则将栈顶元素出栈，并返回
   ElemType pop(SqStack &S);
   
   //如果栈不为空，返回栈顶元素
   ElemType peek(SqStack S);
   
   //销毁栈
   void destroy(SqStack &S);
   
   //打印
   void printStack(SqStack S);

​ 函数实现：

​

#include "All.h"

//初始化栈
void initStack(SqStack &S)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		S.data[i]=0;
	}
		S.top=0;
		S.length=0;
}

//判断栈是否为空
bool isEmpty(SqStack S)
{
	return S.top==0?true:false;
}

//如果栈没有满，将x入栈
bool push(SqStack &S, ElemType x)
{
	if(S.length>MAXSIZE)//S.top>MAXSIZE
	{
		return false;
	}else{
		S.data[S.top]=x;
		S.top++;
	}
	S.length++;
	return true;
}

//如果不为空，则将栈顶元素出栈，并返回
ElemType pop(SqStack &S)
{
	if(isEmpty(S))
	{
		return -999;
	}
	int now=S.data[S.top-1];
	S.top--;
	S.length--;
	return now;
}

//如果栈不为空，返回栈顶元素
ElemType peek(SqStack S)
{
	if(isEmpty)
	{
		return -999;
	}else{
		return S.data[S.top-1];
	}
}

//销毁栈
void destroy(SqStack &S)
{
	for(int i=0;i<S.length;i++)
	{
		S.data[i]=0;
	}
	S.length=0;
	S.top=0;
}

//打印
void printStack(SqStack S)
{
	while(S.top>0)
	{
		printf("%-3d ",S.data[--S.top]);
	}
	printf("\n");
}

测试效果

#include"All.h"

int main()
{
	Stack S;
	initStack(S);
	for(int i=0;i<5;i++)
	{
		push(S,i*10);
	}
	printStack(S);
	for(int i=0;i<3;i++)
	{
		ElemType ret=pop(S);
		printf("当前出栈元素：%d\n",ret);
	}

	system("pause");
	return 0;
}

40  30  20  10  0
当前出栈元素：40
当前出栈元素：30
当前出栈元素：20
请按任意键继续.

---

共享栈

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

#pragma once

#define MAXSIZE 16
typedef int ElemType;

typedef struct{
	ElemType data[MAXSIZE];//共享栈的数据大小
	int top1;//第一个栈的栈顶指针
	int top2;//第二个栈的栈顶指针
	int size;
}SharedStack;

//初始化共享栈
void initStack(SharedStack &S);

//判断第一个栈是否为满
bool isFull1(SharedStack S);

//判断第二个栈是否满了
bool isFull2(SharedStack S);

//判断第一个栈是否为空
bool isEmpty1(SharedStack S);

//判断第二个栈是否为空
bool isEmpty2(SharedStack S);

//在第一个栈中压入元素e
bool push1(SharedStack &S,ElemType e);

//在第二个栈中入栈
bool push2(SharedStack &S,ElemType e);

//再第一个栈中出栈
int pop1(SharedStack &S);

//再第二个栈中出栈
int pop2(SharedStack &S);

//查看第一个栈的栈顶元素值
ElemType peek1(SharedStack S);

//查看第二个栈的栈顶元素值
ElemType peek2(SharedStack S);

//获取第一个栈的长度
int getLength1(SharedStack S);

//获取第二个栈的长度
int getLength2(SharedStack S);

//打印第一个栈
void printStack1(SharedStack S);

//打印第一个栈
void printStack2(SharedStack S);

//打印共享站中的所有元素
void printStack(SharedStack S);

#include"All.h"

//初始化共享栈
void initStack(SharedStack &S)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		S.data[i]=0;
	}
	S.top1=0;
	S.top2=MAXSIZE-1;
	S.size=0;
}

//判断第一个栈是否为满
bool isFull1(SharedStack S)
{
	return S.top1>S.top2;
}

//判断第二个栈是否满了
bool isFull2(SharedStack S)
{
	return S.top1>S.top2;
}

//判断第一个栈是否为空
bool isEmpty1(SharedStack S)
{
	if(S.top1==0)
	{
		return true;
	}else{
		return false;
	}
}

//判断第二个栈是否为空
bool isEmpty2(SharedStack S)
{
	if(S.top2==MAXSIZE)
	{
		return true;
	}else{
		return false;
	}
}

//在第一个栈中压入元素e
bool push1(SharedStack &S,ElemType e)
{
	if(!isFull1(S))
	{
		S.data[S.top1++]=e;
		S.size++;
		return true;
	}else{
		return false;
	}
}

//在第二个栈中入栈
bool push2(SharedStack &S,ElemType e)//top2往下移动
{
	if(!isFull2(S))
	{
		S.data[S.top2--]=e;
		S.size++;
	}else{
		return false;
	}
	return true;
}

//再第一个栈中出栈
int pop1(SharedStack &S)
{
	if(!isEmpty1(S))
	{
		S.size--;
		ElemType x=S.data[--S.top1];//入栈是先放进去，再++，即指针所指的位子是没有元素的
		S.data[S.top1]=0;
		return x;
	}
	else
	{
		return -999;
	}
}

//再第二个栈中出栈
int pop2(SharedStack &S)
{
	if(!isEmpty2(S))
	{
		S.size--;
		ElemType x=S.data[++S.top2];//入栈是先放进去，再++，即指针所指的位子是没有元素的
		S.data[S.top2]=0;
		return x;
	}
	else
	{
		return -999;
	}
}
//查看第一个栈的栈顶元素值
ElemType peek1(SharedStack S)
{
	if(!isEmpty1(S))
	{
		return S.data[S.top1-1];
	}else
	{
		return -999;
	}
}

//查看第二个栈的栈顶元素值
ElemType peek2(SharedStack S)
{
	if(!isEmpty2(S))
	{
		return S.data[S.top2+1];
	}else
	{
		return -999;
	}
}


//获取第一个栈的长度
int getLength1(SharedStack S)
{
	return S.top1;//下标为当前长度-1喔
}

//获取第二个栈的长度
int getLength2(SharedStack S)
{
	return MAXSIZE-1-S.top2;//此处用下标计算长度
}

//打印第一个栈
void printStack1(SharedStack S)
{
	for(int i=S.top1-1;i>=0;i--)
	{
		printf("%d ",S.data[i]);
	}
	printf("\n");
}

//打印第二个栈
void printStack2(SharedStack S)
{
	for(int i= S.top2+1;i<MAXSIZE;i++)//S.top所指的地方是空的，此处的共享站是先入栈后移动指针
	{
		printf("%d ",S.data[i]);
	}
	printf("\n");
}

//打印共享站中的所有元素
void printStack(SharedStack S)
{
	for(int i=0;i<S.size;i++)
	{
		printf("%d ",S.data[i]);
	
	}
	printf("\n");
}

---

链栈

需要的头文件

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

基本操作及实现

#pragma once
typedef int ElemType;

typedef struct LNode{
	ElemType data;
	LNode*next;

}*LinkStack,LNode;

//初始化链栈
void initStack(LinkStack &S);

//判断栈是否为空
bool isEmpty(LinkStack S);

//入栈
void push(LinkStack &S,ElemType x);

//出栈
ElemType pop(LinkStack &S);

//取栈顶元素
ElemType peek(LinkStack S);

//销毁栈
void destroy(LinkStack &S);

//求栈长
int length(LinkStack S);

//打印栈
void print(LinkStack S);

没时间写注释

#include"All.h"

//初始化链栈
void initStack(LinkStack &S)
{
	S=(LinkStack)malloc(sizeof(LNode));
	S->next=NULL;
	S->data=0;//头节点存放链栈的长度
}

//判断栈是否为空
bool isEmpty(LinkStack S)
{
	return S->next==NULL?true:false;
}

//入栈
void push(LinkStack &S,ElemType x)
{
	LNode*last=(LinkStack)malloc(sizeof(LNode));
	last->data=x;
	last->next=S->next;
	S->next=last;
	S->data++;
}

//出栈
ElemType pop(LinkStack &S)
{
	if(S->next==NULL)
	{
		return -999;
	}
	LNode*last=S->next;
	S->next=last->next;
	ElemType x=last->data;
	free(last);
	S->data--;
	return x;
}

//取栈顶元素
ElemType peek(LinkStack S)
{
	if(S->next==NULL)
	{
		return -999;
	}
	return S->next->data;

}

//销毁栈
void destroy(LinkStack &S)
{
	LNode*pre=S->next,*last=S->next->next;
	while(last)
	{
		free(pre);
		pre=last;
		last=last->next;

	}
	S->next=NULL;
	S->data=0;
}

//求栈长
int length(LinkStack S)
{
	/*LNode*pre=S;
	int count=0;
	while(pre->next)
	{
		pre=pre->next;
		count++;
	}
	return count;*/
	return S->data;
}

//打印栈
void print(LinkStack S)
{	if(S->next==NULL||S==NULL)
	{
		return;
	}
	LNode*pre=S;
	while(pre->next)
	{
		pre=pre->next;
		printf("%d-> ",pre->data);
	}
	printf("\n");
}

---

栈的相关算法

1.判断序列是否合法

bool check1(ElemType data[])
{
	SqStack S;
	initStack(S);
	int i=0;
	while(data[i]!='\0')
	{
		if(data[i]=='O')
		{
			if(isEmpty(S))
			{
				return false;
			}else{
				pop(S);
			}
		}else{
			push(S,'a');
		}
		i++;
	}
	return isEmpty(S);
}

测试：

IIIOOO
合法序列
请按任意键继续. .


OIOIOI
非法序列
请按任意键继续. . .

IOIOIOO
非法序列
请按任意键继续. . .

---

二叉树

顺序存储

//顺序存储的结构体
#pragma once
#define MAXSIZE 16
typedef int ElemType;

typedef struct tree{
	ElemType data[MAXSIZE];
	int size;
}Tree;

顺序存储基本操作

#pragma once
#include"struct.h"

//函数声明

//初始化树
void initTree(Tree &T);

//创建树
void createTree(Tree &T);

//打印树
void printTree(Tree T);

//寻找树的左孩子
ElemType find_left_child(Tree T,int i);

//寻找树结点的右孩子
ElemType find_right_child(Tree T,int i);

//需找结点的双亲
ElemType find_parent(Tree T,int i);


//函数实现

//初始化树
void initTree(Tree &T)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		T.data[i]=0;
	}
	T.size=0;
}


//创建树
void createTree(Tree &T)
{
	ElemType x;
	scanf("%d",&x);
	int i=0;
	while(x!=999)
	{
		T.data[i++]=x;
		T.size++;
		scanf("%d",&x);
	}
}

//打印树
void printTree(Tree T)
{
	for(int i=0;i<T.size;i++)
	{
		ElemType x=T.data[i];
		printf("%d ",x);
	}
	printf("\n");

}

//寻找树的左孩子
ElemType find_left_child(Tree T,int i)
{
	int pos=2*i+1;
	if(pos>T.size-1)
	{
		return -999;
	}else{
		return T.data[pos];
	}

}

//寻找树结点的右孩子
ElemType find_right_child(Tree T,int i)
{
	int pos=2+2*i;
	if(pos>T.size-1)
	{
		return -999;
	}else{
		return T.data[pos];
	}
}

//需找结点的双亲
ElemType find_parent(Tree T,int i)
{
	if(i==0)
	{
		return -999;
	}else{
		return T.data[(i-1)/2];
	}
}

题目

已知二叉树按顺序存储方式存储，设计一个算法，求编号i和j两个结点的最近公共祖先结点的值

下面是用递归和非递归来编写的函数（此处顺序存储是从0开始的）

//已知二叉树按顺序存储方式存储，设计一个算法，求编号i和j两个结点的最近公共祖先结点的值
ElemType co_ancestor(Tree T,int i,int j)
{
	if(T.data[i]!=0&&T.data[j]!=0)
	{
		while(i!=j)
		{	//谁的辈分小，谁先找父亲
			if(i>j)
			{
				i=(i-1)/2;
			}else{
				j=(j-1)/2;
			}
		}
	return T.data[j];
	}else{
	return -999;
	}
}


ElemType co_ancestor2(Tree T,int i,int j)
{	
	if(i==j)
	{
		return T.data[i];
	}
	else if(i>j)
	{
		i=(i-1)/2;
		return co_ancestor(T,i,j);
	}else{
		j=(j-1)/2;
		return co_ancestor(T,i,j);
	}
}

链式存储

#pragma once
typedef int ElemType;
//链式存储的结构体
typedef struct BiTNode {
	ElemType data;
	BiTNode *lchild;
	BiTNode *rchild;
}*BiTree,BiTNode;

//基本操作

//初始化二叉树
void initTree(BiTree &T);

//创建二叉树
void createTree(BiTree &T);

//前序遍历
void preOrder(BiTree T);

//中序遍历
void inOrder(BiTree T);

//后序遍历
void postOrder(BiTree T);


//初始化二叉树
void initTree(BiTree &T)
{
	T=NULL;
}

//创建二叉树
void createTree(BiTree &T)
{
	ElemType x;
	scanf("%d",&x);
	if(x==0)
	{
		return;
	}else{
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=x;
		T->lchild=NULL;
		T->rchild=NULL;
		createTree(T->lchild);
		createTree(T->rchild);
	}//递归
}

//递归实现二叉树遍历

//前序遍历
void preOrder(BiTree T)
{
	if(T==NULL)
	{
		return;
	}else{
		printf("%d ",T->data);
		preOrder(T->lchild);
		preOrder(T->rchild);
	}

}

//中序遍历
void inOrder(BiTree T)
{
	if(T==NULL)
	{
		return;
	}else{
		inOrder(T->lchild);
		printf("%d ",T->data);
		inOrder(T->rchild);
	}
}

//后序遍历
void postOrder(BiTree T)
{
	if(T==NULL)
	{
		return;
	}else{
		postOrder(T->lchild);
		postOrder(T->rchild);
		printf("%d ",T->data);
	}
}

二叉树遍历（非递归）

//前序和中序都比较简单，后序较难

//前序遍历
void preOrder(BiTree T)
{
	Stack S;
	initStack(S);
	BiTNode *pre=T;
	while(pre!=NULL||!isEmpty(S))
	{
		if(pre!=NULL)
		{
			printf("%d ",pre->data);
			push(S,pre);
			pre=pre->lchild;
		}else{
			BiTNode *top=pop(S);
			pre=top->rchild;
		}
	}

}

//中序遍历
void inOrder(BiTree T)
{
	Stack S;
	initStack(S);
	BiTNode*pre=T;
	while(pre||!isEmpty(S))
	{
		if(pre){
			push(S,pre);
			pre=pre->lchild;
		}else{
			BiTNode *top=pop(S);
			printf("%d ",top->data);
			if(top->rchild)
			{
				pre=top->rchild;
			}//可以直接优化为pre=top->rchild

		}
	}
	
}

层次遍历

结构体（队列+树）

我采用的是顺序队列

#pragma once
typedef int ElemType;
#define MAXSIZE 8

//二叉树
typedef struct BiTNode {
	ElemType data;
	BiTNode *lchild;
	BiTNode *rchild;
}*BiTree,BiTNode;

//队列
typedef BiTNode* Type;
typedef struct{
	Type data[MAXSIZE];
	int front;
	int rear;
	int size;
}SeQueue;

//栈
typedef struct Stack{
	Type data[MAXSIZE];
	int top;
	int length;
}SqStack;

基本操作

#pragma once
#include<stdio.h>
#include"struct.h"

//-------队列----------
//初始化队列
void initQueue(SeQueue &Q);

//判断队列是否为空
bool isEmpty(SeQueue Q);

//元素入队
bool enQueue(SeQueue &Q,Type x);

//出队
Type deQueue(SeQueue &Q);

//获取队头
Type getHead(SeQueue Q);

//获取队列长度
int getSize(SeQueue Q);

//--------------------树----------------------
//初始化二叉树
void initTree(BiTree &T);

//创建二叉树
void createTree(BiTree &T);

//前序遍历
void preOrder(BiTree T);

//中序遍历
void inOrder(BiTree T);

//后序遍历
void postOrder(BiTree T);

//层序遍历
void levekOrder(BiTree T);

队列

#include"basic.h"
#include"struct.h"

//初始化队列
void initQueue(SeQueue &Q)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		Q.data[i]=0;
	}
	Q.size=0;
	Q.front=0;
	Q.rear=0;
}

//判断队列是否为空
bool isEmpty(SeQueue Q)
{
	return Q.front==Q.rear;
	//return Q.size==0;

}

//元素入队
bool enQueue(SeQueue &Q,Type x)
{
	if(Q.rear>=MAXSIZE)//Q.rear>=MAXSIZE
	{
		return false;
	}
	Q.data[Q.rear++]=x;
	Q.size++;
	return true;
}

//出队
Type deQueue(SeQueue &Q)
{
	if(isEmpty(Q))
	{
		return NULL;
	}else{
		Q.size--;
		return Q.data[Q.front++];
	}

}

//获取队头
Type getHead(SeQueue Q)
{
	if(isEmpty(Q))
	{
		return NULL;
	}
	return Q.data[Q.front];
}

//获取队列长度
int getSize(SeQueue Q)
{
	return Q.size;
	//return Q.rear-Q.front
}

栈

#pragma once
#include"basic.h"
#include<stdio.h>
#include<stdlib.h>
#include"struct.h"

//初始化栈
void initStack(SqStack &S)
{
		S.top=0;
		S.length=0;
}

//判断栈是否为空
bool isEmpty(SqStack S)
{
	return S.top==0?true:false;
}

//如果栈没有满，将x入栈
bool push(SqStack &S, Type x)
{
	if(S.length>MAXSIZE)//S.top>MAXSIZE
	{
		return false;
	}else{
		S.data[S.top]=x;
		S.top++;
	}
	S.length++;
	return true;
}

//如果不为空，则将栈顶元素出栈，并返回
Type pop(SqStack &S)
{
	if(isEmpty(S))
	{
		return NULL;
	}
	Type now=S.data[S.top-1];
	S.top--;
	S.length--;
	return now;
}


//销毁栈
void destroy(SqStack &S)
{
	for(int i=0;i<S.length;i++)
	{
		S.data[i]=0;
	}
	S.length=0;
	S.top=0;
}

//满栈
bool isFull(Stack S)
{
	return S.length>=MAXSIZE;
}

树

#include<stdio.h>
#include<stdlib.h>
#include"basic.h"
#include"struct.h"

//初始化二叉树
void initTree(BiTree &T)
{
	T=NULL;
}

//创建二叉树
void createTree(BiTree &T)
{
	ElemType x;
	scanf("%d",&x);
	if(x==0)
	{
		return;
	}else{
		T=(BiTree)malloc(sizeof(BiTNode));
		T->data=x;
		T->lchild=NULL;
		T->rchild=NULL;
		createTree(T->lchild);
		createTree(T->rchild);
	}//递归
}

层序遍历

void levekOrder(BiTree T)
{
	SeQueue Q;
	initQueue(Q);
	BiTNode* pre=T;
	if(pre)
	{
		enQueue(Q,pre);
		while(!isEmpty(Q))
		{
			BiTNode *head=deQueue(Q);
			printf("%d ",head->data);
			if(head->lchild)
			{
				enQueue(Q,head->lchild);
			}
			if(head->rchild)
			{
				enQueue(Q,head->rchild);
			}
		}

	}

}

---

题目

1. 给出树自下至上，自右至左的遍历算法

1. 给出树自下至上，自右至左的遍历算法

只需要将原来自上至下，自左至右的层序遍历的结果放入栈中，出栈即可得到

void level_order(BiTree T)
{
	SeQueue Q;
	Stack S;
	initStack(S);
	initQueue(Q);
	BiTNode *pre=T;
	if(pre)
	{
		enQueue(Q,pre);
		while(!isEmpty(Q))
		{
			BiTNode *head=deQueue(Q);
			push(S,head);
			if(head->lchild)
			{
				enQueue(Q,head->lchild);
			}
			if(head->rchild)
			{
				enQueue(Q,head->rchild);
			}
		}
	}
	while(!isEmptyS(S))
	{
		Type x=pop(S);
		printf("%d ",x->data);
	}
}

测试样例及结果

#include<stdio.h>
#include<stdlib.h>
#include"struct.h"
#include"basic.h"

int main()
{
	BiTree T;
	initTree(T);
	createTree(T);
	level_order(T);
	system("pause");
	return 0;
}

10 20 40 0 60 0 0 50 0 0 30 0 0
60 50 40 30 20 10 请按任意键继续. . .

---

2.求二叉树的高度

2.假设采用二叉树存储，设计一个非递归算法求二叉树的高度

思路：利用层次遍历，每遍历完一层高度加一，利用队列，每次可以只进队一层

//2.假设二叉树采用二叉链表来存储，求二叉树的高度
int  tree_height(BiTree T)
{
	if(T==NULL)
	{
		return 0;
	}
	SeQueue Q;
	initQueue(Q);
	BiTNode *pre=T;
	int height=0;//用来记录层数
	enQueue(Q,pre);
	while(!isEmpty(Q))
		{
			int size=Q.size;//每次循环都会初始化
			for(int i=0;i<size;i++)//注意每轮都只会出队一个，但是会入队多个
			{
				BiTNode*head=deQueue(Q);
				if(head->lchild){
					enQueue(Q,head->lchild);
				}
				if(head->rchild){
					enQueue(Q,head->rchild);
				}
			}
			height++;//每遍历完一层高度就加一
		}
		return height;
}

现在没法画图，我目前就口述吧

本二叉树的创建方式是前序遍历创建的： 10 20 40 0 60 0 0 50 0 0 30 0 0

二叉树高度就为4

虽然本体没有要求递归，但是依旧可以用递归实现本算法

//2.递归
int  tree_height1(BiTree T)
{
	if(T==NULL)
	{
		return 0;
	}
	if(T->lchild==NULL&&T->rchild==NULL)
	{
		return 1;
	}
	int lheight=tree_height1(T->lchild);
	int rheight=tree_height1(T->rchild);
	return lheight>rheight?lheight+1:rheight+1;
}

---

图论Grap

本章介绍图的基本操作，请仔细阅读

图的操作

结构体

#pragma once
#define MAXSIZE 16
#define INF 65535

typedef int ElemType;
typedef int VertexType;//顶点类型
typedef int EdgeType;//边的类型

typedef struct graph{
	VertexType Vex[MAXSIZE];//顶点集
	EdgeType Edge[MAXSIZE][MAXSIZE];//边集
	int vernum;//实际顶点数
	int edgenum;//实际边数
}Graph;

初始化

//初始化图
void initGraph(Graph &G)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		G.vertices[i].data=0;
		G.vertices[i].first=NULL;
	}
	G.vexnum=0;
	G.arcnum=0;
}

添加顶点

void addVertex(Graph &G,VertexType v)
{
	if(G.vexnum>=MAXSIZE)
	{return;}
	G.vertices[G.vexnum++].data=v;
}

判断顶点是否存在

//如果顶点在图中存在返回其在顶点表中的下标，否则的话返回-1
int vex_is_exist(Graph G,VertexType v)
{
	for(int i=0;i<G.vexnum;i++)
	{
		if(G.vertices[i].data==v)
		{
			return i;
		}
	}
	return -1;
}

添加边

//添加边
void add_edge(Graph &G,VertexType v1,VertexType v2)
{
	//查找v1 v2在表中的下标
	int index1=vex_is_exist(G,v1);
	int index2=vex_is_exist(G,v2);
	if(index1==-1||index2==-1)	{return;	}

	/*
	//尾插法创建v1的边表结点
	ArcNode*pre=(ArcNode*)malloc(sizeof(ArcNode));
	pre->adjVex=v1;
	pre->next=NULL;
	if(G.vertices[index1].first==NULL){
		G.vertices[index1].first=pre;
	}else{
		ArcNode*tail=G.vertices[index1].first;
		while(tail->next!=NULL)
		{
			tail=tail->next;
		}
		tail->next=pre;
	}
	//创建v2的边表结点
	ArcNode*last=(ArcNode*)malloc(sizeof(ArcNode));
	last->adjVex=v2;
	last->next=NULL;
	if(G.vertices[index2].first==NULL){
		G.vertices[index2].first=last;
	}else{
		ArcNode*tail=G.vertices[index2].first;
		while(tail->next!=NULL)
		{
			tail=tail->next;
		}
		tail->next=last;
	}
	*/

	
	//创建V1边结点并插入
	ArcNode*pre=(ArcNode*)malloc(sizeof(ArcNode));
	pre->adjVex=v2;
	pre->next=G.vertices[index1].first;
	G.vertices[index1].first=pre->next;
	
	//创建V1边结点并插入
	ArcNode*last=(ArcNode*)malloc(sizeof(ArcNode));
	last->adjVex=v1;
	last->next=G.vertices[index2].first;
	G.vertices[index2].first=last;
	G.arcnum++;

}//当前的图为无向图,要V1->V2还要V2->V1

打印图

void print_graph(Graph G)
{
	printf("图的邻接表存储;\n");
	for(int i=0;i<G.vexnum;i++)
	{	
		printf("%d: ",G.vertices[i].data);
		ArcNode*pre=G.vertices[i].first;
		while(pre!=NULL)
		{
			printf("%d->",pre->adjVex);
			pre=pre->next;
		}
		printf("\n");
	}
}

创建邻接表

void create_graph(Graph &G)
{
	printf("当前图G所包含的顶点为:\n");
	VertexType v;
	scanf("%d",&v);
	while(v!=999)
	{
		addVertex(G,v);
		scanf("%d",&v);
	}

	printf("请输入要创建的G的边集（V1 V2）\n");
	VertexType v1,v2;
	scanf("%d%d",&v1,&v2);
	while(v1!=0||v2!=0)
	{
		add_edge(G,v1,v2);
		add_edge(G,v2,v1);
		scanf("%d%d",&v1,&v2);
	}
}

//列出图中所有与x相邻的顶点
void find_all_neighbors(Graph G,VertexType x,VertexType data[])
{	//data用于存放与x相邻的所有顶点的信息
	int index=vex_is_exist(G,x);
	if(index==-1){return;}//顶点不存在，直接退出
	
	int count=0;
	ArcNode*pre=G.vertices[index].first;
	while(pre)
	{
		data[count++]=pre->adjVex;
		pre=pre->next;
	}
}

求图中顶点的第一个邻接点

VertexType first_neighbor(Graph G,VertexType x)
{
	int index=vex_is_exist(G,x);
	if(index==-1){return -1;}//判断顶点存不存在

	ArcNode*pre=G.vertices[index].first;
	if(pre==NULL){return -1;}else{return pre->adjVex;}
}

求相邻的结点

//假设图G中顶点y是x的一个邻接点，返回除y外的顶点x的
//下一个邻接点的顶点，若y是x的最后一个顶点则返回-1
VertexType next_neighbor(Graph G,VertexType x,VertexType y)
{
	int index=vex_is_exist(G,x);
	if(index==-1){return -1;}//判断顶点存不存在
	
	ArcNode*pre=G.vertices[index].first;
	while(pre&&pre->adjVex!=y)
	{
		pre=pre->next;
	}
	if(pre&&pre->next)	{return pre->next->adjVex;}
	
	return -1;
}

找顶点的入度

int in_degree(Graph G,VertexType x)
{
	int count=0;
	for(int i=0;i<G.vexnum;i++)
	{
		ArcNode*pre=G.vertices[i].first;
		while(pre)
		{
			if(pre->adjVex==x){count++;}
			pre=pre->next;
		}
	}
	return count;
}

广度优先搜索

void BFS(Graph G,VertexType start)
{
	Queue Q;
	initQueue(Q);
	bool visted[MAXSIZE]={false};//记录顶点是否被访问，初始为false，访问过则改为true
	enQueue(Q,start);
	visted[vex_is_exist(G,start)]=true;//入队之后，更新vist表，跟新结点访问情况
	while(!isEmpty(Q))
	{
		VertexType pre=deQueue(Q);
		printf("%d ",pre);
		VertexType near[MAXSIZE];
		find_all_neighbors(G,pre,near);//找出队顶点相邻的顶点，并存放在near数组中，near中元素的个数为该顶点的出度
		for(int i=0;i<de_degree(G,pre);i++)
		{
			if(visted[vex_is_exist(G,near[i])]==false)//没有访问过就让它入队
			{	
				enQueue(Q,near[i]);
				visted[vex_is_exist(G,near[i])]=true;
			}
		}	
	}
}

深度优先搜索

递归

bool vist[MAXSIZE]={false};
void DFS(Graph G,VertexType v)
{
	vist[vex_is_exist(G,v)]=true;
	printf("%d ",v);
	VertexType near[MAXSIZE];
	find_all_neighbors(G,v,near);
	for(int i=0;i<de_degree(G,v);i++)
	{
		if(vist[vex_is_exist(G,near[i])]==false)
		{
			DFS(G,near[i]);
		}
	}
}

非递归

void DFS1(Graph G,VertexType v)
{
	Stack S;
	initStack(S);
	bool visted[MAXSIZE]={false};//判断图中元素是否被访问过
	push(S,v);
	printf("%d",v);
	visted[vex_is_exist(G,v)]=true;
	while(!isEmpty(S))
	{
		VertexType pre=pop(S);
		VertexType near[MAXSIZE];
		find_all_neighbors(G,pre,near);
		for(int i=0;i<de_degree(G,pre);i++)
		{
			if(!visted[vex_is_exist(G,pre)])
			{
				push(S,pre);
				push(S,near[i]);
				printf("%d",near[i]);
				visted[vex_is_exist(G,near[i])]=true;
				break;
			}
		}
	}
}

---

排序

冒泡排序

非递归版

void bubble_sort(SqList &L)
{
	int TwT=1;//标志，用于记录在这一趟数据有没有交换，若没有交换则表明没有
	for(int i=0;i<L.length-1&&TwT==1;i++)
	{
		TwT=0;
		for(int j=1;j<L.length-i;j++)
		{
			if(L.data[j-1]>L.data[j])
			{
				TwT=1;
				swap(L,j-1,j);
			}
		}
	}
}

递归版

//冒泡排序--递归版
void bubble_sort_rec(SqList &L,int n)
{
	if(n==1){return;}

	for(int i=1;i<n;i++)
	{
		if(L.data[i-1]>L.data[i])
			swap(L,i-1,i);
	}
	bubble_sort_rec(L,n-1);
}

选择排序

void select_sort(SqList &L)//时间复杂度(n-1)/2
{
	for(int i=0;i<L.length-1;i++)//最后一个不用排，故经过n-1轮
	{
		int index=i;
		int min=L.data[i];
		for(int j=i+1;j<L.length;j++)//排好序只需要n-1趟
		{
			if(L.data[j]<L.data[i])
			{
				min=L.data[j];
				index=j;
			}
		}
		if(i!=index){
		swap(L,index,i);
		}
	}
}

直接插入排序

void insert_sort(SqList &L)
{	//无暂存元素
	for(int i=0;i<L.length-1;i++)
		for(int j=i+1;L.data[j]<L.data[j-1]&&j>0;j--)
			{swap(L,j,j-1);}
}