顺序存储
#define MaxSize 10 //定义最大长度
typedef struct{
ElemType data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义（静态分配方式）

链式存储
typedef struct LNode{ 
    ElemType data;          
  struct LNode *next;
}LNode,*LinkList;

    逻辑结构都属于线性表都是线性结构
    存储结构
        1.顺序表    优点：支持随机存取，存储密度高    缺点：大片连续空间分配不方便，改变容量不方便
        2.链表      优点：离散的小空间分配方便，改变容量方便     缺点：不可随机存取，存储密度低
    一、基于空间的比较
        1.存储分配的方式:顺序表的存储空间是静态分配的，链表的存储空间是动态分配
        2.存储密度顺序表=1，链表<1（有指针域）
    二、 基于时间的比较
        1.存取方式：顺序表可随机存取，而链表仅能顺序存储
        2.插入/删除元素时移动元素个数·
        顺序表平均要移动近一半元素，链表无需移动元素，仅改变指针
    三、基于场合
        1.顺序表：信息少表长已知.较少需要插入和删除操作但经表中位置去访问元素.
        2.链表信息量大，表长未知，插入删除操作频繁的情况
        顺序存储可用于线性结构，图，树
    四、插入删除操作
        1.线性表操作删除第一个元素（指到头指针）
        2.删除最后一个指针（倒数第二个指针）
        3.在第一个元素之前插入新元素（头指针）
        4.在最后一个元素之后插入新元素（尾指针）
    五、头插法和尾插法
        1.头插法 s->next = L->next;L->next=s
        2.尾插法 r->next = s;r=s

#define MaxSize 100 //定义栈中元素的最大个数
typedef struct SqStack{
    int data[MaxSize]; //存放栈中的元素
    int top; //栈顶指针
}SqStack;

typedef struct LinkNode{
    int data; //数据域
    struct LinkNode *next; //指针域
}*LiStack; //栈类型定义(不带头节点最方便)

        1.初始时 Q.front=Q.rear=0
        2.队首拨针进1:Q.front=(Q.front+1)%Maxsize
        3.队尾指针进1:Q.rear=(Q.rear+1)%Maxsize
        4.队列长度(Q.reart+Maxsize-Q.front)%Maxsize
        5.队满条件(Q.rear+1%Maxsize=Q.front(牺牲一个存储空间)
        6.队空条件仍为Q.front=Q.rear
        7.注意front，rear指向的位置.

using namespace std;
#define MaxSize 10
typedef struct{
  ElemType data[MaxSize];
  int front rear;
}SqQueue;
void testQueue(){
    SqQueue Q;
}

    1.StrAssign(&T, chars): 赋值操作，把串T赋值为chars；
    2.StrCopy(&T, S): 复制操作，把串S复制得到串T
    3.StrEmpty(S): 判空操作，若S为空串，则返回TRUE，否则返回False；
    4.StrLength(S): 求串长，返回串S的元素个数；
    5.ClearString(&S): 清空操作，将S清为空串；
    6.DestroyString(&S): 销毁串，将串S销毁——回收存储空间；
    7.Concat(&T, S1, S2): 串联联接，用T返回由S1和S2联接而成的新串———可能会导致存储空间的扩展；
    8.SubString(&Sub, S, pos, len): 求子串，用Sub返回串S的第pos个字符起长度为len的子串；
    9.Index(S, T): 定位操作，若主串S中存在与串T值相同的子串，则返回它再主串S中第一次出现的位置，否则函数值为0；
    10.StrCompare(S, T): 串的比较操作，参照英文词典排序方式；若S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0;

#define MAXLEN 255   //预定义最大串长为255
typedef struct{
    char ch[MAXLEN];   //静态数组实现（定长顺序存储）
                       //每个分量存储一个字符
                       //每个char字符占1B
    int length;        //串的实际长度
}SString;
typedef struct StringNode{
    char ch;           //每个结点存1个字符
    struct StringNode *next;
}StringNode, * String;

int Index(SString S, SString T){
    int i=1;                //扫描主串S
    int j=1;                //扫描模式串T
    while(i<=S.length && j<=T.length){
        if(S.ch[i] == T.ch[j]){ //如果当前相同，则指示都后移
            ++i;
            ++j;             //继续比较后继字符
        }
        else{       
            i = i-j+2;   //i-j表示指向了当前匹配串的起始位置的前一个，+2表示下一个串的起始位置（+1是当前被匹配串的起始位置）
            j=1;             //指针后退重新开始匹配
        }
    }
    if(j>T.length)
        return i-T.length;
    else
        return 0;
}

1.树的结点数等于所有结点的度数之和加1
2.区分度为m的树，m叉树
度为m的树：各结点的度最大值为m，但是其他结点的度不一定是m
m叉树：每个结点最多只能有m个孩子的树
3. 度为m的树第i层至多有mi-1 个结点（i≥1）
4. m叉树第i层至多有mi-1个结点（i≥1）
4. 高度为h的m叉树至多有 (mh-1) /(m-1)个结点:m0+m1…+mn
5. 高度为h的m叉树至少有h个结点
6. 高度为h，度为m的树至少有h+m-1个结点
7. 具有h个结点的m叉树的最小高度为[logm(n(m-1)+1)]

#define MaxSize 100
struct TreNode{
   ElemType value; //结点中的数据元素
   bool isEmpty;//结点是否为空
};
TreeNode t[MaxSize];

typedef struct BiTNood{
   ElemType value; //结点中的数据元素
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef struct BiTNood{
   ElemType value; //结点中的数据元素
  struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void InOrder(BiTree T){
  if(T!=NULL){
   visit(T);
    InOrder(T->lchild);
    InOrder(T->rchild);
  }
}

  if(T!=NULL){
    InOrder(T->lchild);
    visit(T);
    InOrder(T->rchild);
  }

  if(T!=NULL){
    InOrder(T->lchild);
    InOrder(T->rchild);
    visit(T);
  }

void levelorder(BiTree T){
    initquete(Q);
    BiTree p;
    enqueue(Q,T);
    while(!isEmpty(Q)){
        dequeue(Q,p);
        visit(p);
        if(p->lchild!=NULL)
        enqueue(Q,p->lchild);
        if(p->rchild!=NULL)
        enqueue(Q,p_<rchild);
    }
}

（1）结点的权：有某种现实含有的数值（如：表示结点的重要性等）
（2）结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积。
（3）树的带权路径长度：树中所有叶结点的带权路径长度之和wpl
（4）在含有n个带权也结点的二叉树中，其中带权路径长度最小的二叉树称为哈夫曼树，也称最优二叉树。

typedef struct ANode
{     int adjvex;			//该边的终点编号
      struct ANode *nextarc;	//指向下一条边的指针
      InfoType info;		//该边的权值等信息
}  ArcNode;

typedef struct Vnode
{    Vertex data;			//顶点信息
     ArcNode *firstarc;		//指向第一条边
}  VNode;

typedef struct 
{     VNode adjlist[MAXV] ;	//邻接表
       int n，e;			//图中顶点数n和边数e
} AdjGraph;

void  DFS1(AdjGraph *G)
{　int i;
     for (i=0;i<G->n;i++)     //遍历所有未访问过的顶点
          if (visited[i]==0) 
               DFS(G，i);
}
void DFS(AdjGraph *G，int v)  
{      ArcNode *p; int w;
       visited[v]=1; 		//置已访问标记
       printf("%d  "，v); 		//输出被访问顶点的编号
       p=G->adjlist[v].firstarc;     	//p指向顶点v的第一条边的边头结点
       while (p!=NULL) 
       {      w=p->adjvex;
	if (visited[w]==0) 
	       DFS(G，w);   	//若w顶点未访问，递归访问它
	p=p->nextarc; 　	//p指向顶点v的下一条边的边头结点
      }
}

void  BFS1(AdjGraph *G)
{      int i;
        for (i=0;i<G->n;i++)     //遍历所有未访问过的顶点
             if (visited[i]==0) 
                  BFS(G，i);
}
void BFS(AdjGraph *G，int v)
{        int w， i;
         ArcNode *p;
         SqQueue *qu;		//定义环形队列指针
         InitQueue(qu);		//初始化队列
         int visited[MAXV];            	//定义顶点访问标记数组
         for (i=0;i<G->n;i++) 
	  visited[i]=0;	  	//访问标记数组初始化
         printf("%2d"，v); 		//输出被访问顶点的编号
         visited[v]=1;              	//置已访问标记
         enQueue(qu，v);
    while (!QueueEmpty(qu))       	//队不空循环
       {	deQueue(qu，w);			//出队一个顶点w
	p=G->adjlist[w].firstarc; 	//指向w的第一个邻接点
	while (p!=NULL)		//查找w的所有邻接点
	{     if (visited[p->adjvex]==0) 	//若当前邻接点未被访问
	       {	printf("%2d"，p->adjvex);  //访问该邻接点
		visited[p->adjvex]=1;	//置已访问标记
		enQueue(qu，p->adjvex);	//该顶点进队
           	       }
           	       p=p->nextarc;              	//找下一个邻接点
	}
       }
       printf("\n");
}

//不带权无向连通图G中距离顶点v最远的一个顶点
int Maxdist(ALGraph *G，int v)
{      ArcNode *p;
        int Qu[MAXV]，front=0，rear=0;	//队列及队头、尾指针
        int visited[MAXV]，i，j，k;
        for (i=0;i<G->n;i++)			//初始化访问标志数组
	visited[i]=0;
        rear++;Qu[rear]=v;			//顶点v进队
        visited[v]=1;			//标记v已访问
      while (rear!=front)
      {	front=(front+1)%MAXV;
	k=Qu[front];			//顶点出队
	p=G->adjlist[k].firstarc;		//找第一个邻接点
	while (p!=NULL)		//所有未访问过的邻接点进队
	{      j=p->adjvex;
	       if (visited[j]==0)		//若j未访问过
	       {	visited[j]=1;		//将顶点j进队
		rear=(rear+1)%MAXV;Qu[rear]=j; 
	       }
	       p=p->nextarc;		//找下一个邻接点
	}
        }
        return k;
}、

//结构体
typedef struct 
{       ElemType *elem; 	  	//KeyType为关键字的数据类型
        int tablelen;  		//其他数据项
}SStable;			//查找顺序表元素类型

int search_seq(SStable ST,ElemType key){
    int i;
    for(i=0;i<ST.tablelen&&ST.elem[i]!=key;i++);
        return i==St.tablelen ? -1:i;
}

//查找表的数据结构——顺序表
typedef struct{
	ElemType *elem;		//动态数组的基址
	int TableLen;		//表的长度	
}SSTable;
//折半查找——增序序列（成功返回数组下标，失败返回-1）
int Binary_Search(SSTable L, ElemType key)
{	//准备指针（下标）
	int low = 0;
	int high = L.TableLen - 1;
	int mid;
	while(low<=high)
	{mid = (low + high)/2;
		if(key == L.elem[mid])
		{return mid;}
		else if(key < L.elem[mid])
		{high = mid - 1;}
		else		
		{low = mid + 1;}
		return -1;
	}
}

typedef struct
{  int key;
   float info;
}JD;
void straisort(JD r[],int n)
{  int i,j;
   for(i=2;i<=n;i++)
   {  r[0]=r[i];
      j=i-1;
      while(r[0].key<r[j].key)
      {  r[j+1]=r[j];
         j--;    }
      r[j+1]=r[0];
   }    } 

void binsort(JD r[],int n)
{  int i,j,x,s,m,k;
   for(i=2;i<=n;i++)
   {  r[0]=r[i];
      x=r[i].key;
      s=1; j=i-1;
      while(s<=j)
      {  m=(s+j)/2;
      if(x<r[m].key)  j=m-1;
         else s=m+1;
      }
      for(k=i-1;k>=s;k--)
         r[k+1]=r[k];
      r[s]=r[0];
   }
}

void shellsort(JD r[],int n,int d[T])
{  int i,j,k;
   JD x;
   k=0;
   while(k<T)
   {  for(i=d[k]+1;i<=n;i++)
      {  x=r[i];
         j=i-d[k];       
         while((j>0)&&(x.key<r[j].key))
         {  r[j+d[k]]=r[j];
            j=j-d[k];
         }
         r[j+d[k]]=x;
       }
       k++;
    }
}
  

void BubbleSort(ElemType A[],int n ){
    for(i=0;i<n-1;i++){
        flag=flase;
        for(j=n-1;j>i;j--){
            if(A[j-1]>A[j]);
            flag=true;
        }
    }
    if(flag==flase)
        return;
}

void QucikSort(ElemType A[],int low,int high){
    if(low<high){
        int pivotpos = Partition(A,low,high);
        QucikSort(A,low,pivotpos-1);
        QucikSort(A,pivotpos+1,high);
    }
}
int Partition(ElemType A[],int low,int high){
    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[low]=pivot;
        return low;
    }
}

void smp_selesort(JD r[],int n)
{  int i,j,k;
   JD x;
   for(i=1;i<n;i++)
   {  k=i;
      for(j=i+1;j<=n;j++)
         if(r[j].key<r[k].key)  k=j;
      if(i!=k)
      {  x=r[i];
         r[i]=r[k];
         r[k]=x;     }   }
}

//建立大根堆
void BuildMaxHeap(ElemType A[],int len){
    for(int i= len/2;i>0;i*=2){
        HeadAdjust(A,i,len);
    }
}
void HeadAdjust(ElemType A[],int k,int len){
    A[0]=A[k];
    if(i<len&&A[i]<i[i+1])
        i++;
    if(A[0]>=A[i])
        break;
    else{
        A[k]=A[i];
        k=i;
    }
    A[k]=A[0];
}
void heapsort(ElemType A[],int len){
    BuildMaxHeap(A,len);
    for(i=len;i>1;i--){
        swap(A[i],A[1]);
        HeadAdjust(A,1,i-1);
    }
}

void merge(int arr[], int start, int mid, int end) {
	int result[ArrLen];
	int k = 0;
	int i = start;
	int j = mid + 1;
	while (i <= mid && j <= end) {
		if (arr[i] < arr[j]){
			result[k++] = arr[i++];
        }
		else{
			result[k++] = arr[j++];
        }
	}
	if (i == mid + 1) {
		while(j <= end)
			result[k++] = arr[j++];
	}
	if (j == end + 1) {
		while (i <= mid)
			result[k++] = arr[i++];
	}
	for (j = 0, i = start ; j < k; i++, j++) {
		arr[i] = result[j];
	}
}
 
void mergeSort(int arr[], int start, int end) {
	if (start >= end)
		return;
	int mid = ( start + end ) / 2;
	mergeSort(arr, start, mid);
	mergeSort(arr, mid + 1, end);
	merge(arr, start, mid, end);

void reverse(int A[],int left,int right,int arraysize){
    if(left>=right||right>=arraysize)
        return;
    int mid=(left+right)/2;
    for(int i=0;i<=mid-left;i++){
        int temp = A[left+i];
        A[left+i]=A[right-i];
        A[right-i]=temp;
    }
}
void exchange(int A[],int m,int n,int arraysize){
    reverse(A,0,m+n-1,arraysize);
    reverse(A,0,n-1,arraysize);
    reverse(A,n,m+n-1,arraysize);
}

int deeptree(BiTree *t)
{    int l,r;
    if(t==NULL) return 0;
    else 
    {
        l=deeptree(t->lchhild);
        r=deeptree(t->rchild);
        if(l<r)  
            return r+1;
        else 
            return l+1;
    }
}

int addTnode(Bitree *t)
{
    if(t=NULL) return 0;
    else 
        if(t->rchild==NULL&&t->lchild==NULL)
          n++;
    addTnode(t->rchild);
    addTnode(t->lchild);
    return n;
} 

//度为2
int double(Bitree T){
    if(T==NULL)
    return 0;
    else if(T->lchild!=NULL&&T->rchild!=NULL)
        return double(T->lchild)+double(T->rchild)+1;
    else
         return double(T->lchild)+double(T->rchild);
}
//度为1
    else if(T->lchild!=NULL||T->rchild!=NULL)
//度为0
    else if(T->lchild==NULL&&T->rchild==NULL)

void copytree(BiTree t1,BiTree t2)
{    if(t1==NULL)
       t2=NULL;
     else {
       t2=new BiTNode;
       t2->data=t1->data;
       t2->lchild=NULL;
       t2->rchild=NULL;
       copytree(t1->rchild,t2->rchild);
       copytree(t1->lchild,t2->lchild);
     }
    
}

void preorder(Bitree T){
    initstack(S);
    p=T;
    r=NULL;
    while(p||isEmpty(S)){
        if(p){
            push(S,p);
            p=p->lchild;
        }
        else{
            gettop(s,p);
            if(p->rchild&&p->rchild!=t)
                p=p->rchild;
            else
            pop(S,p);
            visit(p);
            r=p;
            p=NULL;
        }
    }
}

void preorder(Bitree T){
    initstack(S);
    p=T;
    r=NULL;
    while(p||isEmpty(S)){
        if(p){
            visit(p);
            push(S,p);
            p=p->lchild;
        }
        else{
            pop(S,p);
            p=p->rchild;
        }
    }
}

void preorder(Bitree T){
    initstack(S);
    p=T;
    r=NULL;
    while(p||isEmpty(S)){
        if(p){
            push(S,p);
            p=p->lchild;
        }
        else{
            pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }
}

int visited[MAXV];	  //全局变量，所有元素置初值0
void MDFS(MGraph g，int v)
{      int w;
        printf("%d  "，v);	  //访问顶点v
        visited[v]=1;		  //置访问标记
        for (w=0;w<g.n;w++)	  //找顶点v的所有相邻点
	if (g.edges[v][w]!=0 && g.edges[v][w]!=INF && visited[w]==0)
	        MDFS(g，w);  //找顶点v的未访问过的相邻点w
}

int visited[MaxSize];
void DFS2(ALGraph *G，int v，int &vn，int &en)
{      ArcNode *p;
       visited[v]=1;   vn++;		//遍历过的顶点数增1
       p=G->adjlist[v].firstarc;
       while (p!=NULL) 
       {      en++;			//试探过的边数增1
	if (visited[p->adjvex]==0)
	      DFS2(G，p->adjvex，vn，en);
	p=p->nextarc;
       }
}
bool GIsTree(ALGraph *G)      //判断无向图G是否是一棵树
{      int vn=0，en=0，i;
       for (i=0; i<MaxSize; i++)
	visited[i]=0;
       DFS2(G，0，vn，en);
       if (en==2*(vn-1))
	return true;  
       else
	return false;
}

void Cycle(ALGraph *G，int v，bool  &has)
{      //调用时has置初值false
        ArcNode *p;	int w;
        visited[v]=1;			//置已访问标记
        p=G->adjlist[v].firstarc;	//p指向顶点v的第一个邻接点
        while (p!=NULL)
        {	w=p->adjvex;
	if (visited[w]==0)		//若顶点w未访问，递归访问它
	        Cycle(G，w，has);
	else			//又找到了已访问过的顶点说明有回路
	        has=true;
	p=p->nextarc;		//找下一个邻接点
       }
}
bool HasCycle(ALGraph *G)       //判断有向图G中是否有回路
{ 
        bool has=false;
        for (int i=0;i<G->n;i++)
        {
                Cycle(G，i，has);
	if (has) return true;
        }
        return false;
}