数据结构常见考点算法详解（C语言版）

admin
计算机
1小时前
8热度
0评论

长文预警，本文介绍了数据结构所有算法的实现

#ifndef __B_S__

#include <math.h>

#include <time.h>

#include <stdlib.h>

#include <stdio.h>

#define MaxSize 100

//二叉树的基本结构

typedef int ElemType;

typedef struct BtNode{

ElemType data; //数据

struct BtNode *lchild; //左指针

struct BtNode *rchild; //右指针

}BtNode,*BiTree;

//线索二叉树的基本结构

typedef struct ThreadNode{

ElemType data; //数据

struct ThreadNode *lchild; //左指针

struct ThreadNode *rchild; //右指针

int ltag; //左线索标志,0表示指示左孩子1表示指示前驱

int rtag; //右线索标志,0表示指示右孩子1表示指示后继

}ThreadNode,*ThreadTree; //这里所说的前驱后期基于中序遍历

//图的基本结构(邻接矩阵版)

typedef int VertexType;

typedef int EdgeType;

typedef struct{

VertexType Vex[MaxSize]; //顶点表

EdgeType Edge[MaxSize][MaxSize];//邻接矩阵，边表

int vexnum,arcnum; //图的当前顶点数和弧数

}Graph;

//图的基本结构(邻接表版)

typedef struct ArcNode{ //边表结点

int adjvex; //该弧所指向顶点的位置

struct ArcNode *next; //指向下一条弧的指针

//InfoType info;

}ArcNode;

typedef struct VNode{ //顶点表结点

VertexType data; //顶点结点

ArcNode *first; //指向的第一条依附该顶点的弧的指针

}VNode,AdjList[MaxSize];

typedef struct{

AdjList vertices; //邻接表

int vexnum,arcnum; //图的顶点数和边数

}ALGraph;

//图的基本结构(十字链表版)

typedef struct ArcNode2{ //边表结点

int tailvex,headvex; //该弧的头尾结点

struct ArcNode *hlink; //指向弧头相同的结点

struct ArcNode *tlink; //指向弧尾相同的结点

//InfoType info;

}ArcNode2;

typedef struct VNode2{

VertexType data;

ArcNode2 *firstin; //指向第一条入弧

ArcNode2 *firstout; //指向第一条出弧

}VNode2;

typedef struct{

VNode xlist[MaxSize]; //邻接表

int vexnum,arcnum; //图的顶点数和弧数

}GLGraph;

//图的基本结构(邻接多重表版)

typedef struct ArcNode3{ //边表结点

bool mark; //访问标记

int ivex,jvex; //指向该弧的两头的2个结点

struct ArcNode *ilink; //指向一个结点的下一条边

struct ArcNode *jlink; //指向另一个结点的下一条边

//InfoType info;

}ArcNode3;

typedef struct VNode3{ //顶点表结点

int data; //顶点信息

struct ArcNode3 *firstedge;//指向第一条依附与该顶点的边

}VNode3;

typedef struct{

VNode adjmulist[MaxSize]; //邻接表

int vexnum,arcnum; //图的顶点数和边数

}AMLGraph;

//栈的基本机构

typedef BiTree ElemType2;

typedef struct Stack{

ElemType2 data[MaxSize]; //数据

int top; //栈只有top,一般初始化时top为-1

}SqStack;

//队列的基本结构

typedef BiTree ElemType3;

typedef struct Queue{

ElemType3 data[MaxSize]; //数据

int front; //队首,一般初始化时front为-1

int rear; //队尾,一般初始化时rear为-1

}SqQueue;

/////////////////

//基础支持函数

void Visit(ElemType t)//访问结点并输出

{

printf("%d ",t);

}

#define __B_S__

#endif

/*---------------排序二叉树的基本操作----------------

----------------------------------------------------*/

#include "BasicStruct.h"

BiTree BiSortTree_Insert(BiTree &T,ElemType k)//排序二叉树插入

{

if(T==NULL)

return 0;

if(T->data==k)

{

printf("\n排序二叉树中已有此数,插入失败\n");

return 0;//有一个等于这个数了,所以不插入了

}

if(k<T->data)

BiSortTree_Insert(T->rchild,k);

if(k>T->data)

BiSortTree_Insert(T->rchild,k);

return 0;

}

void BiSortTree_Create(BiTree &T,ElemType str[],int n)//创建排序二叉树

{

T=NULL;

int i=0;

while(i<n)

{

BiSortTree_Insert(T,str[i]);

i++;

}

ElemType BiSortTree_pre=-32767;//保存当前节点中序的前驱

int BiSortTree_IsSort(BiTree T)//判断二叉树是否为排序二叉树

{

int b1,b2;

if(T==NULL)

return 0;

else

{

b1=BiSortTree_IsSort(T->lchild);

if(b1==0 || BiSortTree_pre>=T->data)

return 0;//不是排序二叉树

BiSortTree_pre=T->data;

b2=BiSortTree_IsSort(T->rchild);

return b2;

}

void BiSortTree_AVL(BiTree T,int &balance,int &h)//判断二叉树是否为平衡二叉树

{//balance为二叉树的平衡标记，1为平衡，0为不平衡，h为二叉树的高度

int bl,br,hl,hr;//左右子树的平衡标记和高度

if(T==NULL)

{

h=0;

balance=1;

}

else if(T->lchild==NULL&&T->rchild==NULL)

{

h=1;

balance=1;

}

else

{

BiSortTree_AVL(T->lchild,bl,hl);

BiSortTree_AVL(T->rchild,br,hr);

h=hl>hr?hl:hr;//计算高度

if(abs(hl-hr)<2)

balance=bl&br;//逻辑且，如果只差1或者相等值为1或0

else

balance=0;

}

int BiSortTree_Level(BiTree T,BtNode x)//求指定结点在排序二叉树的层数

{

int level=1;

if(T->data == x.data)

return 1;//在第一层

while(T)

{

if(T->data > x.data)

T=T->lchild;

else if(T->data < x.data)

T=T->rchild;

else

return level;

level++;

}

printf("\n排序二叉树中未找到当前结点\n");

return 0;

}

BiTree BiSortTree_CommonAncestor(BiTree T,ElemType a,ElemType b)//寻找排序二叉树两个结点的公共祖先

{//原理就是找到a和b不同时大于或者不同时小于的那个结点

if(T==NULL)

return 0;

BiTree q,p;

q=T,p=T; //工作指针p为工作指针，q指向p的双亲

while(p!=NULL)

{

if(a<p->data && b<p->data)

{

q=p;

p=p->lchild;

}

else if(a>p->data && b>p->data)

{

q=p;

p=p->rchild;

}

else if((a<p->data && b>p->data) || (a>p->data && b<p->data))

return p;

else if(a==p->data || b==p->data)

return q;

}

return 0;

}

BiTree BiSortTree_Search(BiTree t,ElemType x)//排序二叉树查找data为x的结点

{

while(t)

{

if(t&&x==t->data)

return t;

if(x<t->data)

t=t->lchild;

else

t=t->rchild;

}

printf("\n没有结点的值等于");

printf("%d\n",x);

return NULL;

}

ElemType BiSortTree_Max(BiTree t)//查找排序二叉树中最大值

{

if(t==NULL)

{

printf("\n该树为空树\n");

return 0;

}

if(t->rchild==NULL)

return t->data;

else

{

while(t)

t=t->rchild;

}

return t->data;

}

ElemType BiSortTree_Min(BiTree t)//查找排序二叉树中最小值

{

if(t==NULL)

{

printf("\n该树为空树\n");

return 0;

}

if(t->lchild==NULL)

return t->data;

else

{

while(t)

t=t->lchild;

}

return t->data;

}

void BiSortTree_PrintK(BiTree t,ElemType k)//从大到小输出排序二叉树中不小于k的值

{

if(t)

{

while(t->data < k)

t=t->rchild;//找到大于等于k的那个结点

if(t==NULL)

{

printf("\n没有不小于k的结点存在\n");

exit(0);

}

else

{

printf("\n大于k的结点为：");

Stack s;

InitStack(s);

BiTree p=t;

while(p || !IsEmpty(s))

{

if(p!=NULL)

{//走到左边的根

Push(s,p);

p=p->lchild;

}

else

{

Pop(s,p);

Visit(p->data);

p=p->rchild;

}

printf("\n");

}

/* //因为此函数要修改结构体,所以作为例子看,懒得改结构体

BiTree BiSortTree_FindK(BiTree t,int k)//找到二叉树第k小的数，返回该结点指针

{//二叉树结构体增加一个count保存以该结点为根的子树上的结点数

if(k<1 || k>t->count)

return NULL;

if(t->lchild==NULL)

{

if(k==1)

return t;

else

return BiSortTree_FindK(t->rchild,k-1);

}

else

{

if(t->lchild->count==k-1)

return t;

if(t->lchild->count>k-1)

return BiSortTree_FindK(t->lchild,k);

if(t->lchild->count<k-1)

{

return BiSortTree_FindK(t->rchild,k-t->lchild->count-1);

}

}*/

/*-----------------二叉树的基本操作------------------

1.int CreateBiTree(BiTree &T) //手动创建二叉树

2.void AutoCreateBiTree(BiTree &T) //自动创建二叉树(层序创建)

3.void ShowBiTree(BiTree T) //中序显示二叉树

4.int Max(ElemType x,ElemType y) //返回两个data较大的一个

5.int High(BiTree &T) //递归计算二叉树高度

6.int LeafNum(BiTree &T) //计算二叉树中度为0的点

----------------------------------------------------*/

#include "BasicStruct.h"

#define BiTreeLength 4;//二叉树高度，最低1层,最高7层，因为限制了栈的元素最多为100

int CreateBiTree(BiTree &T) //手动创建二叉树

{

int data;

scanf("%d",&data);

if(data==999)

T=NULL;

else

{

T=(BiTree)malloc(sizeof(BtNode));

T->data=data;

printf("左子树");

CreateBiTree(T->lchild);

printf("右子树");

CreateBiTree(T->rchild);

}

return 0;

}

void AutoCreateBiTree(BiTree &T) //自动创建树(层序创建)

{

//借助队列q和一个辅助指针p

Queue q;

InitQueue(q);

BiTree p=NULL;

//随机数时间种子

time_t ts;

srand(time(&ts));

//对根节点赋值

T->data=rand()%100;//根节点赋值

T->lchild=NULL;

T->rchild=NULL;

int num=BiTreeLength;

//num = num -1;

/////////////////////

EnQueue(q,T);//根节点入队

BiTree level=T;//level结点保存每层最后一个

while(num && !IsEmpty(q))

{

if(num==1)

{break;}

DeQueue(q,p);//根节点出队

//给p的左右孩子分配内存

p->lchild=(BiTree)malloc(sizeof(BtNode));

p->lchild->data=rand()%100;

EnQueue(q,p->lchild);

p->rchild=(BiTree)malloc(sizeof(BtNode));

p->rchild->data=rand()%100;

EnQueue(q,p->rchild);

if(level==p)

{//这个是为了控制层数

level=p->rchild;

num--;

}

while(!IsEmpty(q))//设置叶结点的左右孩子为空

{

DeQueue(q,p); //先出栈，不然会多删掉一组数据

p->lchild=NULL;

p->rchild=NULL;

}

void ShowBiTree(BiTree T) //中序显示二叉树

{

if(T)

{

ShowBiTree(T->lchild);

Visit(T->data);

ShowBiTree(T->rchild);

}

int Max(ElemType x,ElemType y)//返回两个数大的那一个

{

return x>y?x:y;

}

int LeafNum(BiTree &T)//计算二叉树中度为0的点

{

if(T==NULL)

return 0;

else if(T->lchild==NULL && T->rchild==NULL)

return 1;

else

return LeafNum(T->lchild)+LeafNum(T->rchild);

}

void DeleteBiTree(BiTree &T)//删除二叉树

{

if(T)

{

DeleteBiTree(T->lchild);

DeleteBiTree(T->rchild);

free(T);

T=NULL;

}

/*-----------------二叉树的复杂操作------------------ //书上或者习题上的二叉树的题

----------------------------------------------------*/

#include "BasicStruct.h"

BiTree CommonAncestor2(BiTree T,BtNode *p,BtNode *q)//寻找非排序二叉树两个结点的公共祖先

{//假设p在q左边

if(T==NULL)

return 0;

Stack s1,s2;//用s2存放p的祖先

int i,j;

InitStack(s1);

InitStack(s2);

BiTree root=T;

BiTree r=NULL;

Push(s1,root);//根节点入栈

while(root || !IsEmpty(s1))

{

if(root)

{

Push(s1,root);

root=root->lchild;

}

else

{

GetTop(s1,root);//进入else就要GetTop

if(root==p)

{

//printf("\n%d\n",1);

CopyStack(s1,s2);//把s1复制给s2

}

//GetTop(s1,root);

if(root==q)

{

for(i=s1.top;i>0;i--)

{

//Push(s2,p);

for(j=s2.top;j>0;j--)

{

//printf("\n%d\n%d\n",s1.top,s2.top);

if(s1.data[i]==s2.data[j])

return s1.data[i];

}

if(root->rchild!=NULL && root->rchild!=r)

{

root=root->rchild;

Push(s1,root);

root=root->lchild;

}

else

{

Pop(s1,root);

r=root;

root=NULL;

}

return NULL;

}

BiTree PreMidCreate(ElemType A[],ElemType B[],int l1,int h1,int l2,int h2)//根据先序和中序的一维数组生成二叉树

{//l1,h1为先序的第一个坐标和最后一个坐标,l2,h2为中序的第一个和最后一个坐标

BiTree root=(BiTree)malloc(sizeof(BtNode));//建立根节点

root->data=A[l1];

int llen,rlen;

for(int i=l2;B[i]!=root->data;i++);//找到在中序一维数组的分割点

llen=i-l2;//左子树长度

rlen=h2-i;//右子树长度

if(llen)

return PreMidCreate(A,B,l1++,l1+llen,l2,l2+llen-1);//递归建立左子树

else

root->lchild=NULL;

if(rlen)

return PreMidCreate(A,B,h1-rlen+1,h1,h2-rlen+1,h2);

else

root->rchild=NULL;

return root;

}

int High(BiTree T)//求二叉树高度

{//借助一个队列来判断

SqQueue q;

InitQueue(q);

BiTree p=T;

EnQueue(q,p);//根节点入队

BiTree end=p;

int high=0;

while(p && !IsEmpty(q))

{

DeQueue(q,p);

if(p->lchild!=NULL)

EnQueue(q,p->lchild);

if(p->rchild!=NULL)

EnQueue(q,p->rchild);

if(p==end)

{

end=p->rchild;

high++;

}

return high;

}

bool IsComplete(BiTree T)//判断二叉树是否为完全二叉树

{

if(!T)

return true;//空树是完全二叉树

SqQueue q;

InitQueue(q);

BiTree p=T;

EnQueue(q,p);

while(p || !IsEmpty(q))

{

DeQueue(q,p);

if(p)//如果p非空

{

EnQueue(q,p->lchild);

EnQueue(q,p->rchild);

}

else//如果p为空那么看队列后面的结点，如果有一个不为空就说明不是完全二叉树

{

while(!IsEmpty(q))

{

DeQueue(q,p);

if(p)

return false;

}

return true;

}

ElemType BiTreeWPL(BiTree T)//计算该颗树的WPL权值和

{

ElemType WPL=0;//WPL值

int level=1;

BiTree rear=T;//记录每层最后一个

Queue q;

BiTree p=T;

InitQueue(q);

EnQueue(q,p);//根节点入栈

///////////

while(p && !IsEmpty(q))

{

DeQueue(q,p);

WPL += level*p->data;

if(p->lchild!=NULL)

EnQueue(q,p->lchild);

if(p->rchild!=NULL)

EnQueue(q,p->rchild);

if(p==rear)

{

rear=p->rchild;//rchild!!

level++;//每当经过最后一个，层数增加

}

return WPL;

}

void SwapBiTree(BiTree &T)//交换二叉树的所有左右子树

{

if(T)

{

SwapBiTree(T->lchild);

SwapBiTree(T->rchild);

BiTree temp=T->lchild;

T->lchild=T->rchild;

T->rchild=temp;

}

void DeleteXNode(BiTree& T,ElemType x)//删除二叉树中结点等于x下面的所有子树

{

Queue q;

InitQueue(q);

BiTree p=T;

//////////

if(p)

{

if(p->data==x)

{

DeleteBiTree(p);

exit(0);

}

EnQueue(q,p);

while(p || !IsEmpty(q))

{

DeQueue(q,p);

if(p->lchild)

{

if(p->lchild->data==x)

{

DeleteBiTree(p->lchild);

p->lchild=NULL;

}

else

EnQueue(q,p->lchild);

}

if(p->rchild)

{

if(p->rchild->data==x)

{

DeleteBiTree(p->rchild);

p->rchild=NULL;

}

else

EnQueue(q,p->rchild);

}

void PrintXAncestor(BiTree T,ElemType x)//打印data为x的结点的所有祖先

{

//实质上就是后序遍历，因为后序遍历栈顶下面的元素都是它的祖先

Stack s;

InitStack(s);

BiTree p=T;

BiTree r=NULL;

Push(s,p);

while(p || !IsEmpty(s))

{

if(p)

{

Push(s,p);

p=p->lchild;

}

if(p->data==x)//如果找到了为x结点就开始出栈最后退出

{

while(!IsEmpty(s))

{

Pop(s,p);

printf("%d ",p->data);

}

printf("\n");

exit(0);

}

else

{

GetTop(s,p);

if(p->rchild!=NULL && p->rchild!=r)

{

p=p->rchild;

Push(s,p->rchild);

p=p->lchild;

}

else

{

Pop(s,p);

r=p;

p=NULL;

}

bool PrintXAncestor2(BiTree T,ElemType x)//打印data为x的结点的所有祖先(递归版)

{

if(!T)

return false;

if(T->data==x)

return true;//排除 T为空和根节点就是x的情况

if(T)

{

if(PrintXAncestor2(T->lchild,x) || PrintXAncestor2(T->rchild,x))

{

printf("%d ",T->data);

return true;

}

return true;

}

//统计二叉树中度为0的结点个数

int BiTreeAPI_ZeroDegree(BiTree T)

{//用先序遍历方式统计每当遇到左右子树为空的点就+1

BiTree p=T;

int num=0;//统计度为0的点

Stack s;

InitStack(s);

if(T==NULL)

{

printf("\n空树，无法统计\n");

return 0;

}

else if(T->lchild==NULL && T->rchild==NULL)

return 1;//只有根节点

else

{

while(p || !IsEmpty(s))

{

if(p)

{

Push(s,p);

p=p->lchild;

}

else

{

Pop(s,p);

p=p->rchild;

if(p==NULL)

{

num++;

}

return num;

}

//统计二叉树中度为1的结点个数

int BiTreeAPI_OneDegree(BiTree T)

{//用层序方式统计，每当遇到度为1的点num就增加

if(T==NULL)

{

printf("\n此树为空树\n");

return 0;

}

if(T->lchild==NULL&&T->rchild==NULL)

return 0;

int num=0;

BiTree p=T;

Queue q;

InitQueue(q);

EnQueue(q,p);

while(!IsEmpty(q))

{

DeQueue(q,p);

if((p->lchild!=NULL&&p->rchild==NULL)||(p->lchild==NULL&&p->rchild!=NULL))

{

num++;

}

if(p->lchild)

EnQueue(q,p->lchild);

if(p->rchild)

EnQueue(q,p->rchild);

}

return num;

}

//统计二叉树中度为2的结点个数

int BiTreeAPI_TwoDegree(BiTree T)

{

if(T==NULL)

{

printf("\n此树为空树\n");

return 0;

}

if(T->lchild==NULL&&T->rchild==NULL)

return 0;

int num=0;

BiTree p=T;

BiTree r=NULL;

Stack s;

InitStack(s);

while(p || !IsEmpty(s))

{

if(p)

{

Push(s,p);

p=p->lchild;

}

else

{

GetTop(s,p);

if(p->rchild!=NULL&&p->rchild!=r)

{

p=p->rchild;

Push(s,p);

p=p->lchild;

}

else

{//因为每个元素仅pop一次,所以在这里检测是否度为2，以免重复或者漏掉

if(p&&(p->lchild!=NULL&&p->rchild!=NULL))

{

num++;

}

Pop(s,p);

r=p;

p=NULL;

}

return num;

}

//统计二叉树的高度(递归)

int BiTreeAPI_High(BiTree T)

{

if(T==NULL)

return 0;

/* if(T->lchild==NULL&&T->rchild==NULL)//这段加不加都一样,为了代码简洁，注释了

return 1;*/

return Max(BiTreeAPI_High(T->lchild),BiTreeAPI_High(T->rchild))+1;

}

//统计二叉树的宽度

int BiTreeAPI_Width(BiTree T)

{

BiTree p=T;

BiTree rear=p;//每行最后一个结点；

int width=0,max=0;//每行的宽度和最大的宽度

Queue q;

InitQueue(q);

EnQueue(q,p);//根节点入栈

if(T==NULL)

return 0;

else if(T->lchild==NULL&&T->rchild==NULL)

return 1;

else

{

while(!IsEmpty(q))

{

DeQueue(q,p);

width++;

if(p->lchild)

EnQueue(q,p->lchild);

if(p->rchild)

EnQueue(q,p->rchild);

if(p==rear)//如果已经到当前行最后一个

{

rear=p->rchild;//等于下一行的最后一个结点

if(max<=width)

max=width;

width=0;

}

return max;

}

//从二叉树删除所有叶结点

void BiTreeAPI_DeleteLeafNode(BiTree &T)

{//用递归

if(T==NULL)

return;

else if(T->lchild==NULL&&T->rchild==NULL)

{

free(T);

T=NULL;

return;

}

else

{

BiTreeAPI_DeleteLeafNode(T->lchild);

BiTreeAPI_DeleteLeafNode(T->rchild);

}

//计算指定结点*p所在的层次

int BiTreeAPI_NodePLevel(BiTree T,BtNode *p)

{

int level=0;

BiTree rear=T;

BiTree p1=T;

Queue q;

InitQueue(q);

EnQueue(q,p1);//根节点入栈

while(!IsEmpty(q))

{

DeQueue(q,p1);

if(p1->lchild)

EnQueue(q,p1->lchild);

if(p1->rchild)

EnQueue(q,p1->rchild);

if(p1==rear)//如果已经到当前行最后一个

{

rear=p1->rchild;//等于下一行的最后一个结点

level++;

}

if(p==p1)

{

break;

}

return level+1;

}

//计算二叉树中各结点中最大的元素值

ElemType BiTreeAPI_MaxData(BiTree T)

{

ElemType max=-100;

BiTree p=T;

Queue q;

InitQueue(q);

EnQueue(q,p);//根节点入栈

while(!IsEmpty(q))

{

if(p->data>=max)

max=p->data;

DeQueue(q,p);

if(p->lchild)

EnQueue(q,p->lchild);

if(p->rchild)

EnQueue(q,p->rchild);

}

return max;

}

//交换二叉树中每个结点子女次序

void BiTreeAPI_ChangeRL(BiTree T)

{

if(T==NULL)

return;

if(T->lchild==NULL&&T->rchild==NULL)

return;

else

{

BiTree p=NULL;

p=T->lchild;

T->lchild=T->rchild;

T->rchild=p;

BiTreeAPI_ChangeRL(T->lchild);

BiTreeAPI_ChangeRL(T->rchild);

}

//以先序次序输出一颗二叉树中所有结点的数据值以及结点所在的层

void BiTreeAPI_PreOrderDateLevel1(BiTree T,BiTree p)

{

if(T)

{

printf("结点%d在第",T->data);

printf("%d层 ",BiTreeAPI_High(p)-BiTreeAPI_High(T)+1);

BiTreeAPI_PreOrderDateLevel1(T->lchild,p);

BiTreeAPI_PreOrderDateLevel1(T->rchild,p);

}

void BiTreeAPI_PreOrderDateLevel(BiTree T)

{//我为了不再写一个判断当前结点在第几层的函数,用根结点的High-当前结点的High=当前结点高度

BiTree p=T;//储存根结点

BiTreeAPI_PreOrderDateLevel1(T,p);

}

int IsSearchTree(Bitree t) //递归遍历二叉树是否为二叉排序树

{

if(!t) //空二叉树情况

return 1;

else if(!(t->lchild) && !(t->rchild)) //左右子树都无情况

return 1;

else if((t->lchild) && !(t->rchild)) //只有左子树情况

{

if(t->lchild->data>t->data)

return 0;

else

return IsSearchTree(t->lchild);

}

else if((t->rchild) && !(t->lchild)) //只有右子树情况

{

if(t->rchild->data<t->data)

return 0;

else

return IsSearchTree(t->rchild);

}

else //左右子树全有情况

{

if((t->lchild->data>t->data) || (t->rchild->data<t->data))

return 0;

else

return ( IsSearchTree(t->lchild) && IsSearchTree(t->rchild) );

}

///////////////////////

//静态链表

typedef struct{

float wt;

int parent,lchild,rchild;

}node

typedef node hftree[2*n-1];

//构造哈夫曼树

void Huffman(int k,float W[k],hftree T)

{//0-k为叶子结点，后面的是非叶子结点

int x,y,i,j;

float m,n;

for(i=0;i<2*k-1;i++)//先把权值给所有叶子结点

{

T[i].parent=-1;

T[i].lchild=-1;

T[i].rchild=-1;

if(i<k)

T[i].wt=W[i];//叶子结点赋权值

else

T[i].wt=0;//非叶子结点定为0

}

for(i=0;i<k-1;i++)

{

//x为未并入哈夫曼树的最小权重结点的序号,y为次小

x=0;

y=0;

//m为x的权重,n为y的权重

m=maxint;

n=maxint;

for(j=0;j<k+i;j++)

{

if((T[j].wt<m) && (T[j].parent==-1))

{

n=m;

y=x;

x=j;

m=T[j].wt;

}

else if((T[j].wt)<n && (T[j].parent==-1))

{

y=j;

n=T[j].wt;

}

T[x].parent=k+i;//应该是这样定义的

T[y].parent=k+i;

T[k+i].wt=T[x].wt+T[y].wt;

T[k+i].lchild=x;

T[k+i].rchild=y;

}

void InThread(ThreadTree &p,ThreadTree &pre)//构建线索二叉树 //线索二叉树类的没有写生成的函数，需要自己写

{

if(p!=NULL)

{

InThread(p->lchild,pre);//递归线索化左子树

}

if(pre!=NULL&&pre->rchild==NULL)

{//如果pre无右，那么pre->rchild就等于p

pre->rchild=p;

pre->rtag=1;

}

pre=p;

InThread(p->rchild,pre);

}

void CreateInThread(ThreadTree T)//创建线索二叉树

{

ThreadTree pre=NULL;

if(T!=NULL)

{

InThread(T,pre);

pre->rchild=NULL;

pre->rtag=1;

}

ThreadNode *FirstNode(ThreadNode *p)//求中序线索二叉树中序下第一个节点

{

while(p->ltag!=1)

p=p->lchild;

return p;

}

ThreadNode *EndNode(ThreadNode *p)//求中序线索二叉树中序下最后一个节点

{

while(p->rtag!=1)

p=p->rchild;

return p;

}

ThreadNode *PriorNode(ThreadNode *p)//求中序线索二叉树中序下前驱的后继

{

if(p->ltag==0)

return EndNode(p->lchild);

else

return p->lchild;

}

ThreadNode *NextNode(ThreadNode *p)//求中序线索二叉树中序下p结点的后继

{

if(p->rtag==0)

return FirstNode(p->rchild);

else

return p->rchild;

}

void MidOrder(ThreadNode *T)//线索二叉树的中序遍历

{

for(ThreadNode *p=FirstNode(T);p!=NULL;p=NextNode(p))

Visit(p->data);

}

/*-----------------二叉树的基本遍历------------------

1.void PreOrder(BiTree T) //前序递归遍历

2.void MidOrder(BiTree T) //中序递归遍历

3.void PostOrder(BiTree T) //后序递归遍历

4.void PreOrder2(BiTree T) //前序非递归遍历

5.void MidOrder2(BiTree T) //中序非递归遍历

6.void PostOrder2(BiTree T) //后序非递归遍历

7.void LevelOrder(BiTree T) //层序遍历

----------------------------------------------------*/

#include "BasicStruct.h"

#include "Stack.h"

#include "Queue.h"

#include "BiTree.h"

#include "BiSortTree.h"

//二叉树的前中后序的递归与非递归遍历方法

///1.递归类

void PreOrder(BiTree T)//前序递归遍历

{

if(T!=NULL)

{

Visit(T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);

}

void MidOrder(BiTree T)//中序递归遍历

{

if(T!=NULL)

{

MidOrder(T->lchild);

Visit(T->data);

MidOrder(T->rchild);

}

void PostOrder(BiTree T)//后序递归遍历

{

if(T!=NULL)

{

PostOrder(T->lchild);

PostOrder(T->rchild);

Visit(T->data);

}

///2.非递归类

void PreOrder2(BiTree T)//前序非递归遍历

{//借助一个栈s 和一个二叉树工作指针p

SqStack s;

InitStack(s);

BiTree p=T;

/////////////////////

Push(s,p);//根结点入栈

while(p || !IsEmpty(s))

{

if(p!=NULL)

{

Visit(p->data);

Push(s,p);

p=p->lchild;

}

if(!IsEmpty(s))

{

Pop(s,p);

p=p->rchild;

}

void MidOrder2(BiTree T)//中序非递归遍历

{//借助一个栈s 和一个二叉树工作指针p

SqStack s;

InitStack(s);

BiTree p=T;

/////////////////////

Push(s,p);//根结点入栈

while(p || !IsEmpty(s))

{

if(p)

{//先入栈，再让p等于左子树

Push(s,p);

p=p->lchild;

}

else

{//先出栈再访问

Pop(s,p);

Visit(p->data);

p=p->rchild;

}

void PostOrder2(BiTree T)//后序非递归遍历

{//借助一个栈s 和一个二叉树工作指针p

SqStack s;

InitStack(s);

BiTree p=T;

BiTree r=NULL;//辅助指针

/////////////////////

Push(s,p);

while(p || !IsEmpty(s))

{

if(p) //p有左子树

{

Push(s,p);

p=p->lchild;

}

else//p的双亲没有左子树,p现在是NULL

{

GetTop(s,p);//p退回到双亲

if(p->rchild!=NULL && p->rchild!=r)//如果p无左子树有右子树

{

p=p->rchild;

Push(s,p);

p=p->lchild;

}

else//p没有左右子树或者无左有访问过的右

{

Pop(s,p);

Visit(p->data);

r=p;

p=NULL;

}

void LevelOrder(BiTree T)//层序遍历

{//借助一个队列q 和一个二叉树工作指针p

Queue q;

InitQueue(q);

BiTree p=T;

/////////////////////

EnQueue(q,p);//根节点入队

while(!IsEmpty(q))

{

DeQueue(q,p);//根节点出队

Visit(p->data);

if(p->lchild!=NULL)

EnQueue(q,p->lchild);

if(p->rchild!=NULL)

EnQueue(q,p->rchild);

}

void ReverseLevelOrder(BiTree T)//反向层序遍历从下往上从右往左

{//借助一个栈，和层序遍历一样，只是出队时同时进栈

if(T==NULL)

return;

SqStack s;

SqQueue q;

InitStack(s);

InitQueue(q);

BiTree p=T;//工作指针

EnQueue(q,p);//根节点入栈

while(p || !IsEmpty(q))

{

DeQueue(q,p);

Push(s,p);//出队的同时进栈

if(p->lchild!=NULL)

EnQueue(q,p->lchild);

if(p->rchild!=NULL)

EnQueue(q,p->rchild);

}

//开始出栈

while(p || !IsEmpty(s))

{

Pop(s,p);

Visit(p->data);

}

/*-------------------图的基本操作--------------------

----------------------------------------------------*/

#include "BasicStruct.h"

bool visited[MaxSize];//访问标记数组

//当前结点第一个邻居结点

int Graph_FirstNeigbor(Graph G,int v)

{

//todo 懒得写了，一般不考,意思下就行了

return 1;

}

//当前结点下一个邻居结点

int Graph_NextNeighbor(Graph G,int v,int w)

{

//todo 同上

return 2;

}

//广度优先搜索(Breadth-First-Search)

void Graph_BFS(Graph G,int v,Queue q)

{

//visite(v)//访问初始v结点

visited[v]=true;//已访问

EnQueue(q,v);

int w;

while(!IsEmpty(q))

{

for(w=Graph_FirstNeigbor(G,v);w>=0;w=Graph_NextNeighbor(G,v,w))

{

if(!visited[w])

{

//visite(w)//访问w结点

visited[w]=true;

EnQueue(q,w);

}

void Graph_BFSTravel(Graph G)

{

int i;

for(i=0;i<G.vexnum;i++)

{//先设置所有访问标记为false

visited[i]=false;

}

Queue q;

InitQueue(q);

for(i=0;i<G.vexnum;i++)

{

if(!visited[i])

{

Graph_BFS(G,i,q);

}

//BFS求单源最短路径

void Graph_BFSMinDistance(Graph G,int u)

{//求u到所有点的路径

int i;

int w;

int d[MaxSize];

Queue q;

InitQueue(q);

for(i=0;i<G.vexnum;i++)

d[i]=-1;//-1代表没有路径

EnQueue(q,u);

d[u]=0;//自己到自己为0;

while(!IsEmpty(q))

{

DeQueue(q,u);

for(w=Graph_FirstNeigbor(G,u);w>=0;w=Graph_NextNeighbor(G,u,w))

{

if(!visited[i])

{

//visite(w)//访问w结点

d[w]=d[u]+1;

visited[w]=true;

EnQueue(q,w);

}

//深度优先遍历(Deapth-First-Search)

void Graph_DFS(Graph G,int v)

{

//visit(v);//访问v

int w;

visited[v]=true;

for(w=Graph_FirstNeigbor(G,v);w>=0;w=Graph_NextNeighbor(G,v,w))

{

if(!visited[w])

Graph_DFS(G,w);

}

void Graph_DFSTravel(Graph G)

{

int i;

for(i=0;i<G.vexnum;i++)

visited[i]=false;

for(i=0;i<G.vexnum;i++)

{

if(!visited[i])

Graph_DFS(G,i);

}

//深度优先遍历(Deapth-First-Search)(非递归版)

void Graph_DFS2(Graph G,int v)

{

int visited[MaxSize];

int i;

int w;

Stack s;

InitStack(s);

for(i=0;i<G.vexnum;i++)

visited[i]=false;

Push(s,v);

visited[v]=true;//v访问过了

while(!isEmpty(s))

{

Pop(s,v);

//visit(v);

for(w=Graph_FirstNeigbor(G,v);w>=0;w=Graph_NextNeighbor(G,v,w))

{

if(!Visited[w])

{

Push(s,w);

visited[w]=true;

}

//邻接表转换为邻接矩阵

void Graph_Convert(ALGraph &G,int arcs[m][n])

{

int i;

ArcNode p;

for(i=0;i<n;i++)

{

p=G.vertices->first; //取出顶点i的第一条出边

while(p)

{

arc[i][p.data]=1; //让这条边能到达的所有顶点的路径为1

p=p.next;

}

//判断无向图是否为一棵树

bool Graph_IsTree(Graph &G,int v,int n)

{//用深度遍历，如果一次遍历了所有的点和所有的边，且边=点-1，就说明是树

int i;

bool visited[MaxSize];

int Vnum=0,Enum=0;//统计这次遍历的边数

for(i=0;i<G.vexnum;i++)

{

visited[i]=false;

}

Graph_DFS(G,v/*,Vnum,Enum,visited*/);

if(Vnum==G.vexnum&&Enum==2*(G.vexnum-1))//无向图的边是两边都连所以*2

return true;

else

return false;

}

//最小生成树(Minimum-Spanning-Tree,MST)

//普里姆算法-Prim算法思想

//算法依赖顶点V,不依赖于边E,时间复杂度为O(V^2),所以适合稠密的图

//一句话说完就是,集合U开始只有一个点u,找集合U的最小边,找到了就把另一头的点加进去，继续找U(此时的集合有2个顶点了，并且一直动态增加)最小边，一直找

1.初始化一颗空树T(Vt,Et)，所需要的图G(V,E)

2.添加一个顶点w进入集合U(w)

3.while(树中不包含全部顶点 V-U!=NULL)

4.找到最小权值的边 (u,v)

{

5.边归入树 ;T=T∪{(u,v)}

6.顶点归入树 ;U=U∪{v}

}

//克鲁斯卡尔算法-Kruskal算法思想

//算法依赖于边E,不依赖于顶点V,时间复杂度为O(E^2),所以适合稀疏的图

//一句话说完就是在E中一直找最小权值的边，只要找到的边不构成回路就加入，否则就不加入，直至T变成树

1.初始化一棵树T=V,且T包含仅仅所有顶点V,所需要的图

2.定义不连通分量数numS=n;顶点的个数

3.while(不连通分量数>1)

4.从E中取出权值最小的边(v,u)

5.如果v和u属于T中不同的连通分量

{

6.边归入树 T=T∪{(u,v)}

7.numS--;//连通分量数减少1一个

}

Kruskal算法：

void Kruskal(Edge E[],int n,int e)

{

int i,j,m1,m2,sn1,sn2,k;

int vset[MAX];

for(i=0;i<n;i++)

vset[i]=i; //因为现在没边加入，所以连通分量为n个，给每个顶点设置一个独立的标号来代表他的连通分量标号

k=1; //k表示当前构造最小生成树的第几条边,初值为1

j=0; //E中边的下标,初值为0

while (k<n) //生成的边数小于n时循环

{

m1=E[j].u;m2=E[j].v; //取一条边的头尾顶点

sn1=vset[m1];sn2=vset[m2]; //分别得到两个顶点所属的集合编号

if(sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边

{

printf(" (%d,%d):%d/n",m1,m2,E[j].w);

k++; //生成边数增1

for(i=0;i<n;i++) //两个集合统一编号

if (vset[i]==sn2) //集合编号为sn2的改为sn1

vset[i]=sn1;

}

j++; //扫描下一条边

}

/*Prim算法：

难点是prim函数中的两个辅助数组的具体含义：

lowcost数组，顾名思义，最小代价。也就是 lowcost[k] 保存着V-U中编号为k的顶点到U中所有顶点的最小权值。

closest数组，顾名思义，距离最近。也就是 closest[k] 保存着U中到V-U中编号为K的顶点权值最小的顶点的编号。

这两个数组的元素是随着顶点不断加入U集合而动态变化的。

程序中采用邻接矩阵法创建图。*/

void prim(Graph G,VertexType u)

{

int i,j,min;

int lowcost[MaxSize];//lowcost[i]记录以i为终点的边的最小权值当lowcost[i]=0表示终点i已加入生成树

int adjvex[MaxSize];//记录对应的lowcost[i]的权值的另一边的顶点当 adjvex[i]=0表示起点i已加入生成树

k=Locate(G,u); // 找出u结点的位置为了当lowcost的下标

/* 开始初始化*/

for(j=0;j<G.vexnum;++j)

{

/* 最短距离初始化为其他节点指向第一个结点k的距离 */

lowcost[j]=G.arcs[k][j];

/* 理所当然,所有结点的开始结点都是第一个结点u */

adjvex[j]=u;

}

lowcost[k]=0; // lowcost的终点k,第一个结点加入树

/* n个结点需要n+1条边 */

for(i=1;i<G.vexnum;++i)

{

/* 先让min等于最大,一般求最小值函数中都这样用 */

min=MaxSize;

//严蔚敏书上用伪代码写的，找出下一个权值最小边对应的结点

k=minimun(closedge);//这里应该是个for循环找边的

/* 输出生成树边的信息，起点，终点，权值 */

printf(adjvex[k],G.vex[k]);

lowcost[k]=0;// 这个结点加入生成树

/* 更新当前结点k到其他节点的权值 */

for(j=0;j<G.vexnum;j++)

{

if(G.arcs[k][j].adj<lowcost[j])

{

/* 更新最小边的权值和起点信息 */

lowcost[j]=G.arcs[k][j];

adjvex[j] =G.vexs[k];

}

//拓扑排序算法

//思想

1.在AOV网中找一个没有前驱(入度为0)的点输出

2.从网中删除该点，并且删除该点出发的所有边

3.重复这两部直到剩余的网中不再存在没有前驱的顶点为止

bool TopologicalSort(ALGraph G)

{

//若G无回路，输出G的拓扑序列返回true，否则返回false

int indegree[MaxSize]; //把各顶点的入度放入数组

int count;//记录输出的点数，如果最后输出的点小于图中的点说明没输出完→图有回路

FindInDegree(G,indegree) //伪代码，功能是对各顶点求入度放入这个数组

Stack s;

InitStack(s);

int i,j;

for(i=0;i<G.vexnum;++i)

if(indegree[i]==0)

Push(s,i);//入度为0的顶点入栈

count=0;//记录输出的顶点数

while(!IsEmpty(s))

{

Pop(s,i);

printf(i,G.vertices[i].data);++count;//输出顶点i并且计数

for(p=G.vertices[i].first;p;p=p->nextarc)//遍历当前边所有指出去的边

{

k=p->adjvex; //k等于这个边的另一头,下面一行就是然后让k代表的另一头的入度-1

if(!(--indegree[k]))

Push(s,k);//如果减完之后入度为0就放入栈里

}

if(count<G.vexnum)

return false;

else

return true;

}

/*---------------循环队列的基本操作-------------------

1.void InitQueue(SqQueue &Q) //初始化队列

2.bool IsEmpty(SqQueue Q) //判断队列是否为空

3.bool EnQueue(SqQueue Q,ElemType3 x) //入队

4.bool DeQueue(SqQueue Q,ElemType3 &x) //出队

----------------------------------------------------*/

#include "BasicStruct.h"

void InitQueue(SqQueue &Q)//初始化队列

{//初始化队列，队首队尾指针都为0

Q.front=0;

Q.rear=0;

}

bool IsEmpty(SqQueue Q)//判断队列是否为空

{

if(Q.front==Q.rear)

return true;

else

return false;

}

bool EnQueue(SqQueue &Q,ElemType3 x)//入队

{

if((Q.rear+1)%MaxSize==Q.front)//这里不能掉了和MaxSize求余

return false;

else

{

Q.data[Q.rear]=x;

Q.rear=(Q.rear+1)%MaxSize;

return true;

}

void EnQueue(SqQueue &Q,int x)//为了图方便使用，在这里重载一个假方法

{

printf("/n假入队/n");

}

bool DeQueue(SqQueue &Q,ElemType3 &x)//出队

{

if(Q.rear==Q.front)//如果队空

return false;

else

{

x=Q.data[Q.front];

Q.front=(Q.front+1)%MaxSize;

return true;

}

void DeQueue(SqQueue &Q,int x)//为了图方便使用，在这里重载一个假方法

{

printf("/n假出队/n");

}

/*-------------------基本查找算法--------------------

----------------------------------------------------*/

#include "BasicStruct.h"

//顺序查找

int Search_Seq(SSTable ST,KeyType key)

{

//在顺序表ST中顺序查找其他关键字等于key的元素

//如果找到，则函数值返回该元素在表中的位置，否则返回0

ST.elem[0].key=key; //哨兵

for(i=ST.length;!EQ(ST.elem[i].key,key);--i);//或者写为ST.elem[i].key!=key

return i;

}

//有序表的折半查找(二分法)

int Search_Bin(SSTable ST,KeyType key)

{

//在有序表ST中折半查找其他关键字等于key的元素

//如果找到，则函数值返回钙元素在表中的位置，否则返回0

int low,high,mid;

low=1;high=ST.length; //初始区间

while(low<=high)

{

mid=(low+high)/2;

if(EQ(key,ST.elem[mid].key))

return mid;

else if(key>ST.elem[mid].key)

low=mid+1;

else if(kye<ST.elem[mid].key)

high=mid-1;

}

//二叉排序树查找算法

BiTree Search_BST(BiTree T,ElemType key)

{

if((!T) || T->data==key)) return(T);

else if(T->data > key)

Search_BST(T->lchild,key);

else

Search_BST(T->rchild,key);

}

/*------------------排序的基本操作-------------------

----------------------------------------------------*/

#include "BasicStruct.h"

///插入排序

1.1直接插入排序

排序思想：从数组后面依次取数，通过对比后插入到前面的有序序列

空间效率：仅使用了常数个辅助单元,O(1)

时间效率：排序中向有序子表逐个插入进行了n-1趟，每趟都分为比较关键字和移动元素

①最好情况下，表中元素有序，此时每插入一个元素比较一次，共n-1次,O(n)

②最坏情况下，表中元素反序，此时总比较次数为∑[i=2,n](i) 总移动次数∑[i=2,n](i+1)

③平均情况下，总的比较次数和移动次数约为n^2/4 O(n^2)

稳定性：每次插入都是稳定的

适用性：链式存储和顺序存储线性表都可以

void Sort_InsertSort(ElemType A[],int length)

{

int i,j;

for(i=2;i<=length;i++)

{

if(A[i].key<A[i-1].key)//如果A[i]比前驱小，那么就需要插入

{

A[0]=A[i];//哨兵

for(j=i-1;A[0].key<A[j].key;--j)//从后往前查找

{//向后挪动

A[j+1]=A[j];

}

A[j+1]=A[0];//插入的是A[0]

}

1.2折半插入

空间效率：仅使用了常数个辅助单元,O(1)

时间效率：折半插入仅仅减少了比较次数，约为O(n*log[2,n])，比较次数与初始状态无关，O(n^2)

稳定性：每次插入都是稳定的

适用性：顺序存储的线性表

void Sort_Binary(ElemType A[],int length)

{

int i,j;

int low,high,mid;

for(i=2;i<=length;i++)

{

A[0]=A[i];

low=1;high=i-1;//折半插入范围

while(low<=high)//找出插入位置

{

mid=(low+high)/2;

if(A[0].key<A[mid].key)

high=mid-1;

if(A[0].key>A[mid].key)

low=high+1;

if(A[0].key==A[mid].key)

break;

}

for(j=i-1;j>high+1;--j)//统一后移后插入

{

A[j+1]=A[j];

}

A[high+1]=A[0];//插入的是A[0]

}

1.3希尔排序(缩小增量排序)

从前面看出直接插入排序仅适用于数据量不大的排序表

空间效率：使用了常数个辅助单元，O(1)

时间效率：复杂度依赖于dk,最坏情况下O(n^2)

稳定性：不稳定

适用性：顺序存储的线性表

void Sort_ShellInsert(ElemType A[],int length,int dk)

{

int i,j;

for(i=dk+1;i<=length;++i)

{

if(A[i].key<A[i-dk].key)//如果比他前一个小那么就得插入

{

A[0]=A[i]; //暂存，不是哨兵

for(j=i-dk;j>0&&A[0].key<A[j].key;j-=dk)//是减不是加

{

A[j+dk]=A[j];

}

A[j+dk]=A[0];

}

void Sort_Shell(ElemType A[],int length)

{

int dlta[k];//增量序列

for(int k=0;k<length;++k)//按照增量序列进行希尔排序

Sort_ShellInsert(A,length,dk);

}

///交换排序

2.1冒泡排序

空间效率：使用了常数个辅助单元,O(1)

时间效率：如果有序,那么只做n-1次比较,移动次数为0，最好情况是O(n).

如果反序,进行n-1趟排序,第i趟比较n-i个元素,比较次数n*(n-1)/2移动次数是比较次数3倍,3*n*(n-1)/2 复杂度O(n^2)

平均情况O(n^2)

稳定性：稳定(if里面是>=就不是稳定)

适用性：顺序存储的线性表

备注：每一趟都会将一个元素放到最终位置，子序列全局有序，快速排序平均性能最优

void Sort_Bubble(ElemType A[],int length)

{

int i,j,temp;

bool flag;//判断本次循环是否交换了元素，如果没有就说明有序直接GG

for(i=0;i<length;i++)

{

flag=false;

for(j=length;j>i;j--)

{

if(A[j-1].key>A[j].key)

{

temp=A[j-1];

A[j-1]=A[j];

A[j]=temp;

flag=true;

}

if(!flag)

return;

}

2.2快速排序

空间效率：由于快排是递归的，需要借助栈，最好情况上界log[2,n+1],最差情况n(单侧二叉树),平均情况,O(log[2,n])

时间效率：与划分对称有关，越平衡的二叉树越快，最坏情况初始逆序O(n^2)，理想情况(n*log[2,n])

稳定性：不稳定

适用性：顺序存储的线性表

备注：每次排序确定一个数的最终位置，快排算法关键在于划分操作

void Sort_Partition(ElemType A[],int low,int high)

{//划分表为两部分，左边的都比mid小，右边的都比mid大

ElemType pivot=A[low];

while(low<high)

{

while(low<high&&A[high]>=pivot)

--high;

A[low]=A[high];

while(low<high&&A[low]<=pivot)

++low;

A[high]=A[low];

}

A[low]=pivot;

return low;

}

void Sort_Quick(ElemType A[],int low,int high)

{

if(low<high)

{

int pivotpos=Sort_Partition(A,low,high);

Sort_Quick(A,low,pivotpos-1);

Sort_Qucik(A,pivotpos+1,high);

}

///选择排序

3.1简单选择排序

空间效率：仅使用常数个辅助单元，O(1)

时间效率：最多移动3(n-1)次，最好情况是移动0次(有序情况),但是比较次数永远是n*(n-1)/2,O(n^2)

稳定性：不稳定,每次交换都有可能导致一个元素的相对次序发生改变

适用性：顺序存储结构和链式存储结构

备注：

void Sort_Select(ElemType A[],int length)

{

int i,j;

int min,temp;//保存最小值和临时变量temp

for(i=0;i<length;i++)//遍历每一个元素

{

min=i;

for(j=i+1;j<n;j++)//再从这个元素后面找一个比他小的

{

if(A[j]<A[min])

{

min=j;

}

if(min!=i)

{

temp=A[i];

A[i]=A[min];

A[min]=temp;

}

3.2堆排序

空间效率：仅用了常数个辅助单元，O(1)

时间效率：建堆时间O(n),n-1次调整,每次调整时间复杂度O(h),O(n*log[2,n])

稳定性：不稳定

适用性：顺序存储的线性表

备注：大根堆就是前一半大于后一半

void Sort_HeadAdjust(ElemType A[],int length,int k)

{//把大的向下调整

A[0]=A[k];//A[0]暂存

for(i=2*k;k<length;i*=2)

{

if(i<length&&A[i]<A[i+1])

i++;

if(A[0]>=A[i])

break;

else

{

A[k]=A[i];

k=i;

}

A[k]=A[0]

}

void Sort_Heap(ElemType A[],int length)

{

for(i=length/2;i>0;i--)

Sort_HeadAdjust(A,length,i);//先构建初试堆

for(i=length;i>1;i--)//每次把最大的放前面

{

printf(A[i]);//输出堆顶元素

//为了找出下一个最大元素，让堆顶元素和1交换

temp=A[i];

A[i]=A[1];

A[1]=temp;

Sort_HeadAdjust(A,length,i-1);

}

///归并排序

4.1归并排序

空间效率：使用了N个单元的辅助数组,O(n)

时间效率：每一趟归并时间复杂度O(n),共进行上界log[2,n]次排序,O(n*log[2,n])

稳定性：Merge不会改变相对次序,稳定

备注：一般来说对N个元素进行K路归并,排序趟数m满足k^m=N,m=上界log[k,N]

Elemtype *B=(ElemType *)malloc((length+1)*sizeof(ElemType));//辅助数组

void Sort_Merge(ElemType A[],int low,int mid,int high)

{//对已排好序的low-mid和mid-high合并为新的有序表

for(int k=low;k<=high;k++)

{

B[k]=A[k];//将A所有元素复制到B

}

for(i=low,j=mid+1;i<mid&&j<high;k++)

{

if(B[i]<=B[j])

A[k]=B[i++];

else

A[k]=B[j++];

}

while(i<mid) A[k++]=B[i++];

while(j<high) A[k++]=B[j++];

}

void Sort_MergeSort(ElemType A[],int low,int high)

{//把数组划分为一个个的单元,从1开始合并

if(low<high)

{

int mid=(low+high)/2;

Sort_MergeSort(A,low,mid);

Sort_MergeSort(A,mid+1,high);

Sort_Merge(A,low,mid,high);

}

///基数排序

5.1技术排序

空间效率：r个辅助队列,O(r)

时间效率：一共进行d趟分配和收集,每一趟分配需要O(n),收集需要O(r),O(d*(n+r))

稳定性：稳定

备注：与初始状态无关

/*-------------------栈的基本操作--------------------

1.void InitStack(SqStack &S) //栈初始化

2.bool IsEmpty(SqStack S) //判断栈是否为空

3.bool Push(SqStack &S,ElemType2 x) //入栈

4.bool Pop(SqStack &S,ElemType2 &x) //出栈

5.bool GetTop(SqStack S,ElemType2 &x) //读栈顶元素

----------------------------------------------------*/

#include "BasicStruct.h"

void InitStack(SqStack &S)//栈初始化

{

S.top=-1;

}

bool IsEmpty(SqStack S)//栈是否为空

{

if(S.top==-1)

return true;

else

return false;

}

bool Push(SqStack &S,ElemType2 x)//入栈

{

if(S.top==MaxSize-1) //MaxSize-1是栈满的条件

return false;

else

{

S.data[++S.top]=x;//这里是先加,并且是S.top不是top

return true;

}

bool Pop(SqStack &S,ElemType2 &x)//出栈

{

if(IsEmpty(S)==true)

return false;

else

{

x=S.data[S.top--];//先出栈再减1

return true;

}

bool GetTop(SqStack S,ElemType2 &x)//读栈顶元素

{

if(IsEmpty(S)==true)

return false;

else

{

x=S.data[S.top];

return true;

}

bool CopyStack(SqStack s1,SqStack &s2)//复制s1的值给s2(s1不改变)

{

ElemType2 temp;

while(!IsEmpty(s1))

{

Pop(s1,temp);

Push(s2,temp);

}

return true;

}