精华内容
下载资源
问答
  • Play With Data Structure Source Code 大话数据结构C语言源码
  • java 源码结构
  • 严蔚敏编写的《数据结构》一书的源代码,分TC和BC,不过用VC很容易编译通过。
  • 数据结构学习 what the most important thing is Pointer. 堆栈 typedef struct Stack *S; struct Stack { ElementType data[MaxSize]; int top; }; S Init() { S s; s = (struct Stack *)malloc(sizeof(struct...

    what the most important thing is Pointer.

    堆栈

    typedef struct Stack *S;
    struct Stack
    {
        ElementType data[MaxSize];
        int top;
    };
    
    S Init()
    {
        S s;
        s = (struct Stack *)malloc(sizeof(struct Stack));
        s->top=-1;
        return s;
    }
    
    int Push(S s, ElementType e)
    {
        if(s->top==MaxSize-1)
            return 0;
        s->top++;
        s->data[s->top] = e;
        return 1;
    }
    
    ElementType  Pop(S s)
    {
        if(s->top==-1)
        {
            return '0';
        }
        return s->data[s->top--];
    }
    
    int isEmpty(S s)
    {
        if(s->top == -1)
        {
            return 1;
        }
        return 0;
    }
    

    队列

    定义(数据与指针在一起)

    typedef int Position;
    struct QNode {
        ElementType *Data;     /* 存储元素的数组 */
        Position Front, Rear;  /* 队列的头、尾指针 */
        int MaxSize;           /* 队列最大容量 */
    };
    typedef struct QNode *Queue; 
    

    创建

    Queue CreateQueue( int MaxSize )
    {
        Queue Q = (Queue)malloc(sizeof(struct QNode));
        Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));
        Q->Front = Q->Rear = 0;
        Q->MaxSize = MaxSize;
        return Q;
    }
    

    压入队列

    bool AddQ( Queue Q, ElementType X )
    {
        if ( IsFull(Q) ) {
            printf("队列满");
            return false;
        }
        else {
            Q->Rear = (Q->Rear+1)%Q->MaxSize;
            Q->Data[Q->Rear] = X;
            return true;
        }
    }
    

    判断是否空

    bool IsFull( Queue Q )
    {
        return ((Q->Rear+1)%Q->MaxSize == Q->Front);
    }
    

    判断是否满

    bool IsEmpty( Queue Q )
    {
        return (Q->Front == Q->Rear);
    }
    

    删除

    ElementType DeleteQ( Queue Q )
    {
        if ( IsEmpty(Q) ) { 
            printf("队列空");
            return ERROR;
        }
        else  {
            Q->Front =(Q->Front+1)%Q->MaxSize;
            return  Q->Data[Q->Front];
        }
    }
    

    第二种队列

    typedef struct Node *PtrToNode;
    struct Node { /* 队列中的结点 */
        ElementType Data;
        PtrToNode Next;
    };
    typedef PtrToNode Position;
     
    struct QNode {
        Position Front, Rear;  /* 队列的头、尾指针 */
        int MaxSize;           /* 队列最大容量 */
    };
    typedef struct QNode *Queue;
     
    bool IsEmpty( Queue Q )
    {
        return ( Q->Front == NULL);
    }
     
    ElementType DeleteQ( Queue Q )
    {
        Position FrontCell; 
        ElementType FrontElem;
         
        if  ( IsEmpty(Q) ) {
            printf("队列空");
            return ERROR;
        }
        else {
            FrontCell = Q->Front;
            if ( Q->Front == Q->Rear ) /* 若队列只有一个元素 */
                Q->Front = Q->Rear = NULL; /* 删除后队列置为空 */
            else                     
                Q->Front = Q->Front->Next;
            FrontElem = FrontCell->Data;
     
            free( FrontCell );  /* 释放被删除结点空间  */
            return  FrontElem;
        }
    }
    

    栈只是指一种使用堆的方法(即先进后出)

    二叉树

    定义

    typedef struct TNode *Position;
    typedef Position BinTree; /* 二叉树类型 */
    struct TNode{ /* 树结点定义 */
        ElementType Data; /* 结点数据 */
        BinTree Left;     /* 指向左子树 */
        BinTree Right;    /* 指向右子树 */
    };
    
    

    遍历算法

    void InorderTraversal( BinTree BT )
    {
        if( BT ) {
            InorderTraversal( BT->Left );
            /* 此处假设对BT结点的访问就是打印数据 */
            printf("%d ", BT->Data); /* 假设数据为整型 */
            InorderTraversal( BT->Right );
        }
    }
     
    void PreorderTraversal( BinTree BT )
    {
        if( BT ) {
            printf("%d ", BT->Data );
            PreorderTraversal( BT->Left );
            PreorderTraversal( BT->Right );
        }
    }
     
    void PostorderTraversal( BinTree BT )
    {
        if( BT ) {
            PostorderTraversal( BT->Left );
            PostorderTraversal( BT->Right );
            printf("%d ", BT->Data);
        }
    }
     
    void LevelorderTraversal ( BinTree BT )
    { 
        Queue Q; 
        BinTree T;
     
        if ( !BT ) return; /* 若是空树则直接返回 */
         
        Q = CreatQueue(); /* 创建空队列Q */
        AddQ( Q, BT );
        while ( !IsEmpty(Q) ) {
            T = DeleteQ( Q );
            printf("%d ", T->Data); /* 访问取出队列的结点 */
            if ( T->Left )   AddQ( Q, T->Left );
            if ( T->Right )  AddQ( Q, T->Right );
        }
    }
    int GetHeight(BinTree bt)
    {
        int lchild,rchild;
        if(bt==NULL)
            return 0;
        lchild = GetHeight(bt->Left);
        rchild = GetHeight(bt->Right);
        return (lchild>rchild)?(1+lchild):(1+rchild);
    }
    
    

    练习

    还原二叉树
    给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。
    
    输入格式:
    输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。
    
    输出格式:
    输出为一个整数,即该二叉树的高度。
    
    输入样例:
    9
    ABDFGHIEC
    FDHGIBEAC
    
    输出样例:
    5
    
    
    #include<stdio.h>
    typedef struct SNode *Tree;
    char x[51],z[51];
    struct SNode{
        char data;
        Tree left,right;
    };
    Tree CreateTree()
    {
        Tree tree = (Tree*)malloc(sizeof(struct SNode));
        tree->left = tree->right = NULL;
        return tree;
    }
    int Height(Tree tree)
    {
        int lchild,rchild;
        if(tree==NULL){
            return 0;
        }
        lchild = Height(tree->left);
        rchild = Height(tree->right);
        return (lchild>rchild)?(1+lchild):(1+rchild);
    }
    Tree RestoreTree(int x1,int z1,int z2){
        Tree head = CreateTree();
        head->data = x[x1];
        int i=0;
        for(i=z1;i<=z2;i++)
        {
            if(z[i]==x[x1])
            {
                if(i!=z1) head->left = RestoreTree(x1+1,z1,i-1);
                if(i!=z2) head->right = RestoreTree(x1+i-z1+1,i+1,z2);
                break;
            }
        }
        return head;
    }
    int main()
    {
        int n=0;
        scanf("%d",&n);
        scanf("%s%s",&x,&z);
        Tree head = RestoreTree(0,0,n-1);
        printf("%d",Height(head));
    }
    
    
    树的遍历
    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
    
    输入格式:
    输入第一行给出一个正整数N(≤30),是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
    
    输出格式:
    在一行中输出该树的层序遍历的序列。数字间以1个空格分隔,行首尾不得有多余空格。
    
    输入样例:
    7
    2 3 1 5 7 6 4
    1 2 3 4 5 6 7
    输出样例:
    4 1 6 3 5 7 2
    
    
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <list>
    #include <vector>
    #include <cmath>
    #include <cstring>
    #include <map>
    #include <queue>
     
    using namespace std;
     
    int tree[10000],level[10000];//tree记录二叉树,level记录层序遍历
    int sum;
    int lvr[31],lrv[31];//lvr是中序,lrv是后序
     
    void createTree(int *lrv,int *lvr,int n,int index) //后序和中序得到二叉树
    {
        if(n==0) return;
        int k=0;
        while(lrv[n-1]!=lvr[k]) k++;
        tree[index] = lvr[k];
        createTree(lrv,lvr,k,index*2);
        createTree(lrv+k,lvr+k+1,n-k-1,index*2+1);
    }
    void LevelOrder() //层序遍历
        {
            queue <int> Q;
            Q.push(1);
            int p;
            while(!Q.empty())
            {
                p = Q.front(); Q.pop();
                level[sum] = tree[p]; sum++;
                if(tree[p*2]!=0) Q.push(p*2);  //如果为0,说明为NULL
                if(tree[p*2+1]!=0) Q.push(p*2+1);
            }
        }
     
    int main() {
        int n; cin>>n;
        for(int i=0;i<n;i++) cin>>lrv[i];
        for(int i=0;i<n;i++) cin>>lvr[i];
        createTree(lrv,lvr,n,1);
        LevelOrder();
        for(int i=0;i<sum;i++){
            if(i==0) cout<<level[i];
            else cout<<" "<<level[i];
        }
        return 0;
    }
    
    
    #include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    typedef struct SNode *Tree;
    int h[31],z[31];//全局变量,因为数组没有改变
    int n;
    struct SNode  /*树节点定义*/
    {
        int data;/*节点数据*/
        Tree left,right;/*指向左右节点*/
    };
    typedef int Position;
    
    typedef struct QNode * PtrToNode;
    typedef PtrToNode Queue;
    struct QNode
    {
        int * Data;
        Position Front,Rear;
    };
    
    Tree CreateTree()
    {
        Tree tree = (Tree*)malloc(sizeof(struct SNode));
        tree->left = tree->right = NULL;
        return tree;
    }
    
    Queue CreateQueue()
    {
        Queue Q = (Queue)malloc(sizeof(struct QNode));
        Q->Data = (int *)malloc(31*sizeof(int));
        Q->Front=Q->Rear=0;
        return Q;
    }
    
    bool IsEmpty( Queue Q )
    {
        return (Q->Front == Q->Rear);
    }
    
    bool IsFull( Queue Q )
    {
        return ((Q->Rear+1)%31 == Q->Front);
    }
    
    bool AddQ(Queue Q,int x)
    {
        if(IsFull(Q))
        {
            printf("队列满");
            return false;
        }
        else
        {
            Q->Rear=(Q->Rear+1)%31;
            Q->Data[Q->Rear]=x;
            return true;
        }
    }
    
    int DeleteQ( Queue Q )
    {
        if ( IsEmpty(Q) ) {
            printf("队列空");
            return 0;
        }
        else  {
            Q->Front =(Q->Front+1)%31;
            return  Q->Data[Q->Front];
        }
    }
    
    Tree RestoreTree(int a,int b,int c) //a是要找后序片段的首,b是要找中序片段的首,c是要找中序片段的尾
    {
        Tree t = CreateTree();
        t->data = h[a];//找后序中的根
        int i=0;
        for(i=b; i<=c; i++) //找中序中的根
        {
            if(z[i]==h[a])
            {
                if(i!=b)
                    t->left = RestoreTree(a-(c-i)-1,b,i-1);//左子树
                if(i!=c)
                    t->right = RestoreTree(a-1,i+1,c);//右子数
                break;
            }
        }
        return t;
    }
    //遍历算法:从队列中取出一个元素;访问元素所指节点;
    //如果元素所指节点的左、右孩子非空就将其左、右孩子的指针顺序入队
    //不断执行,直至队列为空。
    void LevelorderTraversal(Tree tree)
    {
        int flag=0;
        Queue Q;
        Tree t;
        Q=CreateQueue();
        AddQ(Q,tree);
        while(!IsEmpty(Q))
        {
            t=DeleteQ(Q);
            printf("%d",t->data);
            flag++;
            if(flag!=n)printf(" ");//最后不能多空格
            if(t->left)
                AddQ(Q,t->left);
            if(t->right)
                AddQ(Q,t->right);
        }
    }
    
    int main()
    {
        int i;
        scanf("%d",&n);
        for(i=0; i<n; i++)
            scanf("%d",&h[i]);//后序
        for(i=0; i<n; i++)
            scanf("%d",&z[i]);//中序
        Tree t = RestoreTree(n-1,0,n-1);
        LevelorderTraversal(t);
        printf("\n");
        return 0;
    }
    
    
    列出叶结点
    对于给定的二叉树,本题要求你按从上到下、从左到右的顺序输出其所有叶节点。
    
    输入格式:
    首先第一行给出一个正整数 N(≤10),为树中结点总数。树中的结点从 0 到 N−1 编号。随后 N 行,每行给出一个对应结点左右孩子的编号。如果某个孩子不存在,则在对应位置给出 "-"。编号间以 1 个空格分隔。
    
    输出格式:
    在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔,行首尾不得有多余空格。
    
    输入样例:
    8
    1 -
    - -
    0 -
    2 7
    - -
    - -
    5 -
    4 6
    输出样例:
    4 1 5
    
    
    #include<stdio.h>
    #include<stdio.h>
    #include<stdlib.h>
    //找到没有出现的数字为根节点
    //递归左右子树,以左右子树的根结点的值递归
    //层序输出
    typedef struct Node *node;
    struct Node  					//储存输入数据,并找到父节点
    {
        int on;
        int left;
        int right;
    };
    typedef struct Snode *Tree;
    struct Snode //树
    {
        int data;
        Tree Left;
        Tree Right;
    };
    int flag=1;//判断输出时第一个字母不带空格
    
    //层序输出
    void LevelorderTraversal(Tree t)
    {
        int first=0;
        Tree tep;
        Tree dd[12];
        int top=0,dom=0;
        dd[top]=t;//借数组当队列用
        top++;
        while(dom<top)
        {
            tep=dd[dom];//出队
            dom++;
            if(!tep->Left&&!tep->Right)
            {
                first++;
                if(first==flag)
                    printf("%d",tep->data);
                else
                    printf(" %d",tep->data);
            }
            if(tep->Left)
            {
                dd[top]=tep->Left;    //入队
                top++;
            }
            if(tep->Right)
            {
                dd[top]=tep->Right;
                top++;
            }
        }
    }
    
    Tree CreatTree(int rot,node nod[])
    {
        node t= nod[rot];
        Tree tr=(Tree)malloc(sizeof(struct Snode));
        tr->data=t->on;
        if(t->left!=-1)
        {
            tr->Left=CreatTree(t->left,nod);
        }
        else
            tr->Left=NULL;
        if(t->right!=-1)
        {
            tr->Right=CreatTree(t->right,nod);
        }
        else
            tr->Right=NULL;
        return tr;
    }
    
    int main()
    {
        int n,j=0,num[14]= {0};
        node tr[14];
        char ch;
        scanf("%d",&n);
        scanf("%c",&ch);//清除回车
        char str[5];
        //输入数据,没有孩子的默认为1
        for(int i=0; i<n; i++)
        {
            node t=(node)malloc(sizeof(struct Node));
            gets(str);
            if(str[0]!='-')
            {
                t->left=(int)(str[0]-'0');
                num[t->left]++;
            }
            else
                t->left=-1;
            if(str[2]!='-')
            {
                t->right=str[2]-'0';
                num[t->right]++;
            }
            else
                t->right=-1;
            t->on=i;//记住父节点值
            tr[i]=t;
        }
        //找根结点
        for(j; j<n; j++)
            if(num[j]==0)
                break;
        Tree T=CreatTree(j,tr);
        LevelorderTraversal(T);
        return 0;
    }
    
    
    #include<iostream>
    #include<vector>
    using namespace std;
    struct node {
    	char left, right;
    } ;
    node treenode[11];
    vector <int> leaf[11];
    void cengxubianli(int root, int level) {
    	if (treenode[root].left == '-' && treenode[root].right == '-') {
    		leaf[level].push_back(root);
    		return;
    	}
    	if (treenode[root].left != '-') cengxubianli(treenode[root].left - '0', level + 1);
    	if (treenode[root].right != '-') cengxubianli(treenode[root].right - '0', level + 1);
    }
    int main() {
    	int n, findroot[11], reallyroot = 0;
    	for(int i=0;i<11;i++)
    	findroot[i]=0;
    	cin >> n;
    	for (int i = 0; i < n; i++) {
    		cin >> treenode[i].left >> treenode[i].right;
    		findroot[treenode[i].left - '0'] = findroot[treenode[i].right - '0'] = 1;
    	}
    	for (int i = 0; i < n; i++)
    		if (findroot[i]==0) {
    			reallyroot = i;
    			break;
    		}
    	cengxubianli(reallyroot, 1);
        bool first=false;
    	for (int i = 1; i <= 10; i++) {
    		for (int j = 0; j < leaf[i].size(); j++) {
                if(first)cout<<" ";
                else first=true;
    			cout << leaf[i][j];
    		}
    	}
    	system("pause");
    	return 0;
    }
    
    
    void LevelorderTraversal( BinTree BT ,int n){//层序
        if(!BT) return;
        int len=1,pos,sum=0;
        BinTree a[101],b[101];
        a[0]=BT;
        while(1){
            if(len==0) return;
            pos=0;
            for(int i=0;i<len;i++)
            {
                if(a[i]->Left!=NULL)//如果它的左节点不为空,就存到b数组里
                    b[pos++]=a[i]->Left;
                if(a[i]->Right!=NULL)//如果它的右节点不为空,就存到b数组里
                    b[pos++]=a[i]->Right;
                if(a[i]!=NULL){//不为空输出
                    printf("%d",a[i]->Data);
                    sum++;
                }
                if(sum!=n)
                    printf(" ");
            }
            len=pos;//更新下一层宽度,为下一次循环做准备
            for(int i=0;i<len;i++)//将下层的b赋给a,为下一次循环做准备
                a[i]=b[i];
        }
    }
    
    

    二叉搜索树

    插入算法

    BinTree Insert( BinTree BST, ElementType X )
    {
        if( !BST ){ /* 若原树为空,生成并返回一个结点的二叉搜索树 */
            BST = (BinTree)malloc(sizeof(struct TNode));
            BST->Data = X;
            BST->Left = BST->Right = NULL;
        }
        else { /* 开始找要插入元素的位置 */
            if( X < BST->Data )
                BST->Left = Insert( BST->Left, X );   /*递归插入左子树*/
            else  if( X > BST->Data )
                BST->Right = Insert( BST->Right, X ); /*递归插入右子树*/
            /* else X已经存在,什么都不做 */
        }
        return BST;
    }
    
    

    删除算法

    BinTree Delete( BinTree BST, ElementType X ) 
    { 
        Position Tmp; 
     
        if( !BST ) 
            printf("要删除的元素未找到"); 
        else {
            if( X < BST->Data ) 
                BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
            else if( X > BST->Data ) 
                BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
            else { /* BST就是要删除的结点 */
                /* 如果被删除结点有左右两个子结点 */ 
                if( BST->Left && BST->Right ) {
                    /* 从右子树中找最小的元素填充删除结点 */
                    Tmp = FindMin( BST->Right );
                    BST->Data = Tmp->Data;
                    /* 从右子树中删除最小元素 */
                    BST->Right = Delete( BST->Right, BST->Data );
                }
                else { /* 被删除结点有一个或无子结点 */
                    Tmp = BST; 
                    if( !BST->Left )       /* 只有右孩子或无子结点 */
                        BST = BST->Right; 
                    else                   /* 只有左孩子 */
                        BST = BST->Left;
                    free( Tmp );
                }
            }
        }
        return BST;
    }
    
    

    AVL(平衡二叉树)

    定义

    typedef struct AVLNode *Position;
    typedef Position AVLTree; /* AVL树类型 */
    struct AVLNode{
        ElementType Data; /* 结点数据 */
        AVLTree Left;     /* 指向左子树 */
        AVLTree Right;    /* 指向右子树 */
        int Height;       /* 树高 */
    };
    
    

    平衡算法

    int Max ( int a, int b )
    {
        return a > b ? a : b;
    }
     
    AVLTree SingleLeftRotation ( AVLTree A )
    { /* 注意:A必须有一个左子结点B */
      /* 将A与B做左单旋,更新A与B的高度,返回新的根结点B */     
     
        AVLTree B = A->Left;
        A->Left = B->Right;
        B->Right = A;
        A->Height = Max( GetHeight(A->Left), GetHeight(A->Right) ) + 1;
        B->Height = Max( GetHeight(B->Left), A->Height ) + 1;
      
        return B;
    }
     
    AVLTree DoubleLeftRightRotation ( AVLTree A )
    { /* 注意:A必须有一个左子结点B,且B必须有一个右子结点C */
      /* 将A、B与C做两次单旋,返回新的根结点C */
         
        /* 将B与C做右单旋,C被返回 */
        A->Left = SingleRightRotation(A->Left);
        /* 将A与C做左单旋,C被返回 */
        return SingleLeftRotation(A);
    }
     
    /*************************************/
    /* 对称的右单旋与右-左双旋请自己实现 */
    /*************************************/
    
    

    插入算法

    AVLTree Insert( AVLTree T, ElementType X )
    { /* 将X插入AVL树T中,并且返回调整后的AVL树 */
        if ( !T ) { /* 若插入空树,则新建包含一个结点的树 */
            T = (AVLTree)malloc(sizeof(struct AVLNode));
            T->Data = X;
            T->Height = 0;
            T->Left = T->Right = NULL;
        } /* if (插入空树) 结束 */
     
        else if ( X < T->Data ) {
            /* 插入T的左子树 */
            T->Left = Insert( T->Left, X);
            /* 如果需要左旋 */
            if ( GetHeight(T->Left)-GetHeight(T->Right) == 2 )
                if ( X < T->Left->Data ) 
                   T = SingleLeftRotation(T);      /* 左单旋 */
                else 
                   T = DoubleLeftRightRotation(T); /* 左-右双旋 */
        } /* else if (插入左子树) 结束 */
         
        else if ( X > T->Data ) {
            /* 插入T的右子树 */
            T->Right = Insert( T->Right, X );
            /* 如果需要右旋 */
            if ( GetHeight(T->Left)-GetHeight(T->Right) == -2 )
                if ( X > T->Right->Data ) 
                   T = SingleRightRotation(T);     /* 右单旋 */
                else 
                   T = DoubleRightLeftRotation(T); /* 右-左双旋 */
        } /* else if (插入右子树) 结束 */
     
        /* else X == T->Data,无须插入 */
     
        /* 别忘了更新树高 */
        T->Height = Max( GetHeight(T->Left), GetHeight(T->Right) ) + 1;
         
        return T;
    }
    
    

    堆(树)

    定义

    typedef struct HNode *Heap; /* 堆的类型定义 */
    struct HNode {
        ElementType *Data; /* 存储元素的数组 */
        int Size;          /* 堆中当前元素个数 */
        int Capacity;      /* 堆的最大容量 */
    };
    typedef Heap MaxHeap; /* 最大堆 */
    typedef Heap MinHeap; /* 最小堆 */
    
    

    初始化树

    #define MAXDATA 1000  /* 该值应根据具体情况定义为大于堆中所有可能元素的值 */
     
    MaxHeap CreateHeap( int MaxSize )
    { /* 创建容量为MaxSize的空的最大堆 */
     
        MaxHeap H = (MaxHeap)malloc(sizeof(struct HNode));
        H->Data = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
        H->Size = 0;
        H->Capacity = MaxSize;
        H->Data[0] = MAXDATA; /* 定义"哨兵"为大于堆中所有可能元素的值*/
     
        return H;
    }
    
    

    判断是否满

    bool IsFull( MaxHeap H )
    {
        return (H->Size == H->Capacity);
    }
    
    

    判断是否空

    #define ERROR -1 /* 错误标识应根据具体情况定义为堆中不可能出现的元素值 */
     
    bool IsEmpty( MaxHeap H )
    {
        return (H->Size == 0);
    }
    
    

    插入算法

    bool Insert( MaxHeap H, ElementType X )
    { /* 将元素X插入最大堆H,其中H->Data[0]已经定义为哨兵 */
        int i;
      
        if ( IsFull(H) ) { 
            printf("最大堆已满");
            return false;
        }
        i = ++H->Size; /* i指向插入后堆中的最后一个元素的位置 */
        for ( ; H->Data[i/2] < X; i/=2 )
            H->Data[i] = H->Data[i/2]; /* 上滤X */
        H->Data[i] = X; /* 将X插入 */
        return true;
    }
    
    

    删除最大堆元素

    ElementType DeleteMax( MaxHeap H )
    { /* 从最大堆H中取出键值为最大的元素,并删除一个结点 */
        int Parent, Child;
        ElementType MaxItem, X;
     
        if ( IsEmpty(H) ) {
            printf("最大堆已为空");
            return ERROR;
        }
     
        MaxItem = H->Data[1]; /* 取出根结点存放的最大值 */
        /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */
        X = H->Data[H->Size--]; /* 注意当前堆的规模要减小 */
        for( Parent=1; Parent*2<=H->Size; Parent=Child ) {
            Child = Parent * 2;
            if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
                Child++;  /* Child指向左右子结点的较大者 */
            if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
            else  /* 下滤X */
                H->Data[Parent] = H->Data[Child];
        }
        H->Data[Parent] = X;
     
        return MaxItem;
    } 
    
    

    构造最大堆

    /*----------- 建造最大堆 -----------*/
    void PercDown( MaxHeap H, int p )
    { /* 下滤:将H中以H->Data[p]为根的子堆调整为最大堆 */
        int Parent, Child;
        ElementType X;
     
        X = H->Data[p]; /* 取出根结点存放的值 */
        for( Parent=p; Parent*2<=H->Size; Parent=Child ) {
            Child = Parent * 2;
            if( (Child!=H->Size) && (H->Data[Child]<H->Data[Child+1]) )
                Child++;  /* Child指向左右子结点的较大者 */
            if( X >= H->Data[Child] ) break; /* 找到了合适位置 */
            else  /* 下滤X */
                H->Data[Parent] = H->Data[Child];
        }
        H->Data[Parent] = X;
    }
     
    void BuildHeap( MaxHeap H )
    { /* 调整H->Data[]中的元素,使满足最大堆的有序性  */
      /* 这里假设所有H->Size个元素已经存在H->Data[]中 */
     
        int i;
     
        /* 从最后一个结点的父节点开始,到根结点1 */
        for( i = H->Size/2; i>0; i-- )
            PercDown( H, i );
    }
    
    

    哈夫曼树

    typedef struct TreeNode *HuffmanTree;
    struct TreeNode{
    int Weight;
    HuffmanTree Left, Right;
    }
    HuffmanTree Huffman( MinHeap H )
    { /* 假设H->Size个权值已经存在H->Elements[]->Weight里 */
     int i; HuffmanTree T;
     BuildMinHeap(H); /*将H->Elements[]按权值调整为最小堆*/
     for (i = 1; i < H->Size; i++) { /*做H->Size-1次合并*/
     T = malloc( sizeof( struct TreeNode) ); /*建立新结点*/
     T->Left = DeleteMin(H);
     /*从最小堆中删除一个结点,作为新T的左子结点*/
     T->Right = DeleteMin(H);
     /*从最小堆中删除一个结点,作为新T的右子结点*/
     T->Weight = T->Left->Weight+T->Right->Weight;
     /*计算新权值*/
     Insert( H, T ); /*将新T插入最小堆*/
     }
     T = DeleteMin(H);
     return T;
    }
    
    

    集合及运算

    #define MAXN 1000                  /* 集合最大元素个数 */
    typedef int ElementType;           /* 默认元素可以用非负整数表示 */
    typedef int SetName;               /* 默认用根结点的下标作为集合名称 */
    typedef ElementType SetType[MAXN]; /* 假设集合元素下标从0开始 */
     
    void Union( SetType S, SetName Root1, SetName Root2 )
    { /* 这里默认Root1和Root2是不同集合的根结点 */
        /* 保证小集合并入大集合 */
        if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
            S[Root2] += S[Root1];     /* 集合1并入集合2  */
            S[Root1] = Root2;
        }
        else {                         /* 如果集合1比较大 */
            S[Root1] += S[Root2];     /* 集合2并入集合1  */
            S[Root2] = Root1;
        }
    }
     
    SetName Find( SetType S, ElementType X )
    { /* 默认集合元素全部初始化为-1 */
        if ( S[X] < 0 ) /* 找到集合的根 */
            return X;
        else
            return S[X] = Find( S, S[X] ); /* 路径压缩 */
    
    

    定义(邻接矩阵)

    /* 图的邻接矩阵表示法 */
     
    #define MaxVertexNum 100    /* 最大顶点数设为100 */
    #define INFINITY 65535        /* ∞设为双字节无符号整数的最大值65535*/
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;        /* 边的权值设为整型 */
    typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
     
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
            
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{
        int Nv;  /* 顶点数 */
        int Ne;  /* 边数   */
        WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
        DataType Data[MaxVertexNum];      /* 存顶点的数据 */
        /* 注意:很多情况下,顶点无数据,此时Data[]可以不用出现 */
    };
    typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
     
     
    MGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V, W;
        MGraph Graph;
         
        Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接矩阵 */
        /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
        for (V=0; V<Graph->Nv; V++)
            for (W=0; W<Graph->Nv; W++)  
                Graph->G[V][W] = INFINITY;
                 
        return Graph; 
    }
            
    void InsertEdge( MGraph Graph, Edge E )
    {
         /* 插入边 <V1, V2> */
         Graph->G[E->V1][E->V2] = E->Weight;    
         /* 若是无向图,还要插入边<V2, V1> */
         Graph->G[E->V2][E->V1] = E->Weight;
    }
     
    MGraph BuildGraph()
    {
        MGraph Graph;
        Edge E;
        Vertex V;
        int Nv, i;
         
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
         
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        if ( Graph->Ne != 0 ) { /* 如果有边 */ 
            E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */ 
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
                /* 注意:如果权重不是整型,Weight的读入格式要改 */
                InsertEdge( Graph, E );
            }
        } 
     
        /* 如果顶点有数据的话,读入数据 */
        for (V=0; V<Graph->Nv; V++) 
            scanf(" %c", &(Graph->Data[V]));
     
        return Graph;
    }
    
    

    遍历

    DFS

    void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
    {
        Visited[V]=true;
        Visit(V);
        for(int w=0; w<Graph->Nv; w++)
        {
            if(Graph->G[V][w] == 1&& !Visited[w])
            {
                DFS(Graph, w,Visit);
            }
        }
    }
    
    

    BFS

    /* IsEdge(Graph, V, W)检查<V, W>是否图Graph中的一条边,即W是否V的邻接点。  */
    /* 此函数根据图的不同类型要做不同的实现,关键取决于对不存在的边的表示方法。*/
    /* 例如对有权图, 如果不存在的边被初始化为INFINITY, 则函数实现如下:         */
    bool IsEdge( MGraph Graph, Vertex V, Vertex W )
    {
        return Graph->G[V][W]<INFINITY ? true : false;
    }
     
    /* Visited[]为全局变量,已经初始化为false */
    void BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
    {   /* 以S为出发点对邻接矩阵存储的图Graph进行BFS搜索 */
        Queue Q;     
        Vertex V, W;
     
        Q = CreateQueue( MaxSize ); /* 创建空队列, MaxSize为外部定义的常数 */
        /* 访问顶点S:此处可根据具体访问需要改写 */
        Visit( S );
        Visited[S] = true; /* 标记S已访问 */
        AddQ(Q, S); /* S入队列 */
         
        while ( !IsEmpty(Q) ) {
            V = DeleteQ(Q);  /* 弹出V */
            for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
                /* 若W是V的邻接点并且未访问过 */
                if ( !Visited[W] && IsEdge(Graph, V, W) ) {
                    /* 访问顶点W */
                    Visit( W );
                    Visited[W] = true; /* 标记W已访问 */
                    AddQ(Q, W); /* W入队列 */
                }
        } /* while结束*/
    }
    
    

    定义(邻接表)

    /* 图的邻接表表示法 */
     
    #define MaxVertexNum 100    /* 最大顶点数设为100 */
    typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
    typedef int WeightType;        /* 边的权值设为整型 */
    typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
     
    /* 边的定义 */
    typedef struct ENode *PtrToENode;
    struct ENode{
        Vertex V1, V2;      /* 有向边<V1, V2> */
        WeightType Weight;  /* 权重 */
    };
    typedef PtrToENode Edge;
     
    /* 邻接点的定义 */
    typedef struct AdjVNode *PtrToAdjVNode; 
    struct AdjVNode{
        Vertex AdjV;        /* 邻接点下标 */
        WeightType Weight;  /* 边权重 */
        PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
    };
     
    /* 顶点表头结点的定义 */
    typedef struct Vnode{
        PtrToAdjVNode FirstEdge;/* 边表头指针 */
        DataType Data;            /* 存顶点的数据 */
        /* 注意:很多情况下,顶点无数据,此时Data可以不用出现 */
    } AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */
     
    /* 图结点的定义 */
    typedef struct GNode *PtrToGNode;
    struct GNode{  
        int Nv;     /* 顶点数 */
        int Ne;     /* 边数   */
        AdjList G;  /* 邻接表 */
    };
    typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */ 
     
     
    LGraph CreateGraph( int VertexNum )
    { /* 初始化一个有VertexNum个顶点但没有边的图 */
        Vertex V;
        LGraph Graph;
         
        Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
        Graph->Nv = VertexNum;
        Graph->Ne = 0;
        /* 初始化邻接表头指针 */
        /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
           for (V=0; V<Graph->Nv; V++)
            Graph->G[V].FirstEdge = NULL;
                 
        return Graph; 
    }
            
    void InsertEdge( LGraph Graph, Edge E )
    {
        PtrToAdjVNode NewNode;
         
        /* 插入边 <V1, V2> */
        /* 为V2建立新的邻接点 */
        NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V2;
        NewNode->Weight = E->Weight;
        /* 将V2插入V1的表头 */
        NewNode->Next = Graph->G[E->V1].FirstEdge;
        Graph->G[E->V1].FirstEdge = NewNode;
             
        /* 若是无向图,还要插入边 <V2, V1> */
        /* 为V1建立新的邻接点 */
        NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
        NewNode->AdjV = E->V1;
        NewNode->Weight = E->Weight;
        /* 将V1插入V2的表头 */
        NewNode->Next = Graph->G[E->V2].FirstEdge;
        Graph->G[E->V2].FirstEdge = NewNode;
    }
     
    LGraph BuildGraph()
    {
        LGraph Graph;
        Edge E;
        Vertex V;
        int Nv, i;
         
        scanf("%d", &Nv);   /* 读入顶点个数 */
        Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
         
        scanf("%d", &(Graph->Ne));   /* 读入边数 */
        if ( Graph->Ne != 0 ) { /* 如果有边 */ 
            E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ 
            /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
            for (i=0; i<Graph->Ne; i++) {
                scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
                /* 注意:如果权重不是整型,Weight的读入格式要改 */
                InsertEdge( Graph, E );
            }
        } 
     
        /* 如果顶点有数据的话,读入数据 */
        for (V=0; V<Graph->Nv; V++) 
            scanf(" %c", &(Graph->G[V].Data));
     
        return Graph;
    }
    
    

    遍历

    DFS

    void Visit( Vertex V )
    {
        printf("正在访问顶点%d\n", V);
    }
    /* Visited[]为全局变量,已经初始化为false */
    void **DFS**( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
    {   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
        PtrToAdjVNode W;
         
        Visit( V ); /* 访问第V个顶点 */
        Visited[V] = true; /* 标记V已访问 */
     
        for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
            if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
                DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
    }
    
    
    

    BFS

    void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) )
    {
        int queue[MaxVertexNum];
        int l = 0, r = 0;
        queue[r++] = S;
        Visit(S);
        Visited[S] = true;
        PtrToAdjVNode temp;
        while(l != r)
        {
            temp = Graph->G[queue[l++]].FirstEdge;
            while(temp)
            {
                Vertex pos = temp->AdjV;
                if(!Visited[pos])
                {
                    Visit(pos);
                    Visited[pos] = true;
                    queue[r++] = pos;
                }
                temp = temp->Next;
            }
        }
    }
    
    

    最小生成树

    Prim(邻接矩阵)

    /* 邻接矩阵存储 - Prim最小生成树算法 */
     
    Vertex FindMinDist( MGraph Graph, WeightType dist[] )
    { /* 返回未被收录顶点中dist最小者 */
        Vertex MinV, V;
        WeightType MinDist = INFINITY;
     
        for (V=0; V<Graph->Nv; V++) {
            if ( dist[V]!=0 && dist[V]<MinDist) {
                /* 若V未被收录,且dist[V]更小 */
                MinDist = dist[V]; /* 更新最小距离 */
                MinV = V; /* 更新对应顶点 */
            }
        }
        if (MinDist < INFINITY) /* 若找到最小dist */
            return MinV; /* 返回对应的顶点下标 */
        else return ERROR;  /* 若这样的顶点不存在,返回-1作为标记 */
    }
     
    int Prim( MGraph Graph, LGraph MST )
    { /* 将最小生成树保存为邻接表存储的图MST,返回最小权重和 */
        WeightType dist[MaxVertexNum], TotalWeight;
        Vertex parent[MaxVertexNum], V, W;
        int VCount;
        Edge E;
         
        /* 初始化。默认初始点下标是0 */
           for (V=0; V<Graph->Nv; V++) {
            /* 这里假设若V到W没有直接的边,则Graph->G[V][W]定义为INFINITY */
               dist[V] = Graph->G[0][V];
               parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */ 
        }
        TotalWeight = 0; /* 初始化权重和     */
        VCount = 0;      /* 初始化收录的顶点数 */
        /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
        MST = CreateGraph(Graph->Nv);
        E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */
                
        /* 将初始点0收录进MST */
        dist[0] = 0;
        VCount ++;
        parent[0] = -1; /* 当前树根是0 */
     
        while (1) {
            V = FindMinDist( Graph, dist );
            /* V = 未被收录顶点中dist最小者 */
            if ( V==ERROR ) /* 若这样的V不存在 */
                break;   /* 算法结束 */
                 
            /* 将V及相应的边<parent[V], V>收录进MST */
            E->V1 = parent[V];
            E->V2 = V;
            E->Weight = dist[V];
            InsertEdge( MST, E );
            TotalWeight += dist[V];
            dist[V] = 0;
            VCount++;
             
            for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
                if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
                /* 若W是V的邻接点并且未被收录 */
                    if ( Graph->G[V][W] < dist[W] ) {
                    /* 若收录V使得dist[W]变小 */
                        dist[W] = Graph->G[V][W]; /* 更新dist[W] */
                        parent[W] = V; /* 更新树 */
                    }
                }
        } /* while结束*/
        if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
           TotalWeight = ERROR;
        return TotalWeight;   /* 算法执行完毕,返回最小权重和或错误标记 */
    }
    
    

    Kruskal(邻接表)

    /* 邻接表存储 - Kruskal最小生成树算法 */
     
    /*-------------------- 顶点并查集定义 --------------------*/
    typedef Vertex ElementType; /* 默认元素可以用非负整数表示 */
    typedef Vertex SetName;     /* 默认用根结点的下标作为集合名称 */
    typedef ElementType SetType[MaxVertexNum]; /* 假设集合元素下标从0开始 */
     
    void InitializeVSet( SetType S, int N )
    { /* 初始化并查集 */
        ElementType X;
     
        for ( X=0; X<N; X++ ) S[X] = -1;
    }
     
    void Union( SetType S, SetName Root1, SetName Root2 )
    { /* 这里默认Root1和Root2是不同集合的根结点 */
        /* 保证小集合并入大集合 */
        if ( S[Root2] < S[Root1] ) { /* 如果集合2比较大 */
            S[Root2] += S[Root1];     /* 集合1并入集合2  */
            S[Root1] = Root2;
        }
        else {                         /* 如果集合1比较大 */
            S[Root1] += S[Root2];     /* 集合2并入集合1  */
            S[Root2] = Root1;
        }
    }
     
    SetName Find( SetType S, ElementType X )
    { /* 默认集合元素全部初始化为-1 */
        if ( S[X] < 0 ) /* 找到集合的根 */
            return X;
        else
            return S[X] = Find( S, S[X] ); /* 路径压缩 */
    }
     
    bool CheckCycle( SetType VSet, Vertex V1, Vertex V2 )
    { /* 检查连接V1和V2的边是否在现有的最小生成树子集中构成回路 */
        Vertex Root1, Root2;
     
        Root1 = Find( VSet, V1 ); /* 得到V1所属的连通集名称 */
        Root2 = Find( VSet, V2 ); /* 得到V2所属的连通集名称 */
     
        if( Root1==Root2 ) /* 若V1和V2已经连通,则该边不能要 */
            return false;
        else { /* 否则该边可以被收集,同时将V1和V2并入同一连通集 */
            Union( VSet, Root1, Root2 );
            return true;
        }
    }
    /*-------------------- 并查集定义结束 --------------------*/
     
    /*-------------------- 边的最小堆定义 --------------------*/
    void PercDown( Edge ESet, int p, int N )
    { /* 改编代码4.24的PercDown( MaxHeap H, int p )    */
      /* 将N个元素的边数组中以ESet[p]为根的子堆调整为关于Weight的最小堆 */
        int Parent, Child;
        struct ENode X;
     
        X = ESet[p]; /* 取出根结点存放的值 */
        for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
            Child = Parent * 2 + 1;
            if( (Child!=N-1) && (ESet[Child].Weight>ESet[Child+1].Weight) )
                Child++;  /* Child指向左右子结点的较小者 */
            if( X.Weight <= ESet[Child].Weight ) break; /* 找到了合适位置 */
            else  /* 下滤X */
                ESet[Parent] = ESet[Child];
        }
        ESet[Parent] = X;
    }
     
    void InitializeESet( LGraph Graph, Edge ESet )
    { /* 将图的边存入数组ESet,并且初始化为最小堆 */
        Vertex V;
        PtrToAdjVNode W;
        int ECount;
     
        /* 将图的边存入数组ESet */
        ECount = 0;
        for ( V=0; V<Graph->Nv; V++ )
            for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
                if ( V < W->AdjV ) { /* 避免重复录入无向图的边,只收V1<V2的边 */
                    ESet[ECount].V1 = V;
                    ESet[ECount].V2 = W->AdjV;
                    ESet[ECount++].Weight = W->Weight;
                }
        /* 初始化为最小堆 */
        for ( ECount=Graph->Ne/2; ECount>=0; ECount-- )
            PercDown( ESet, ECount, Graph->Ne );
    }
     
    int GetEdge( Edge ESet, int CurrentSize )
    { /* 给定当前堆的大小CurrentSize,将当前最小边位置弹出并调整堆 */
     
        /* 将最小边与当前堆的最后一个位置的边交换 */
        Swap( &ESet[0], &ESet[CurrentSize-1]);
        /* 将剩下的边继续调整成最小堆 */
        PercDown( ESet, 0, CurrentSize-1 );
     
        return CurrentSize-1; /* 返回最小边所在位置 */
    }
    /*-------------------- 最小堆定义结束 --------------------*/
     
     
    int Kruskal( LGraph Graph, LGraph MST )
    { /* 将最小生成树保存为邻接表存储的图MST,返回最小权重和 */
        WeightType TotalWeight;
        int ECount, NextEdge;
        SetType VSet; /* 顶点数组 */
        Edge ESet;    /* 边数组 */
     
        InitializeVSet( VSet, Graph->Nv ); /* 初始化顶点并查集 */
        ESet = (Edge)malloc( sizeof(struct ENode)*Graph->Ne );
        InitializeESet( Graph, ESet ); /* 初始化边的最小堆 */
        /* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
        MST = CreateGraph(Graph->Nv);
        TotalWeight = 0; /* 初始化权重和     */
        ECount = 0;      /* 初始化收录的边数 */
     
        NextEdge = Graph->Ne; /* 原始边集的规模 */
        while ( ECount < Graph->Nv-1 ) {  /* 当收集的边不足以构成树时 */
            NextEdge = GetEdge( ESet, NextEdge ); /* 从边集中得到最小边的位置 */
            if (NextEdge < 0) /* 边集已空 */
                break;
            /* 如果该边的加入不构成回路,即两端结点不属于同一连通集 */
            if ( CheckCycle( VSet, ESet[NextEdge].V1, ESet[NextEdge].V2 )==true ) {
                /* 将该边插入MST */
                InsertEdge( MST, ESet+NextEdge );
                TotalWeight += ESet[NextEdge].Weight; /* 累计权重 */
                ECount++; /* 生成树中边数加1 */
            }
        }
        if ( ECount < Graph->Nv-1 )
            TotalWeight = -1; /* 设置错误标记,表示生成树不存在 */
     
        return TotalWeight;
    }
    
    

    最短路径问题

    邻接表存储 - 无权图的单源最短路算法

    /* dist[]和path[]全部初始化为-1 */
    void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
    {
        Queue Q;
        Vertex V;
        PtrToAdjVNode W;
         
        Q = CreateQueue( Graph->Nv ); /* 创建空队列, MaxSize为外部定义的常数 */
        dist[S] = 0; /* 初始化源点 */
        AddQ (Q, S);
     
        while( !IsEmpty(Q) ){
            V = DeleteQ(Q);
            for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
                if ( dist[W->AdjV]==-1 ) { /* 若W->AdjV未被访问过 */
                    dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */
                    path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
                    AddQ(Q, W->AdjV);
                }
        } /* while结束*/
    }
    
    

    邻接矩阵存储 - 有权图的单源最短路算法

    Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
    { /* 返回未被收录顶点中dist最小者 */
        Vertex MinV, V;
        int MinDist = INFINITY;
     
        for (V=0; V<Graph->Nv; V++) {
            if ( collected[V]==false && dist[V]<MinDist) {
                /* 若V未被收录,且dist[V]更小 */
                MinDist = dist[V]; /* 更新最小距离 */
                MinV = V; /* 更新对应顶点 */
            }
        }
        if (MinDist < INFINITY) /* 若找到最小dist */
            return MinV; /* 返回对应的顶点下标 */
        else return ERROR;  /* 若这样的顶点不存在,返回错误标记 */
    }
     
    bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
    {
        int collected[MaxVertexNum];
        Vertex V, W;
     
        /* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */
        for ( V=0; V<Graph->Nv; V++ ) {
            dist[V] = Graph->G[S][V];
            if ( dist[V]<INFINITY )
                path[V] = S;
            else
                path[V] = -1;
            collected[V] = false;
        }
        /* 先将起点收入集合 */
        dist[S] = 0;
        collected[S] = true;
     
        while (1) {
            /* V = 未被收录顶点中dist最小者 */
            V = FindMinDist( Graph, dist, collected );
            if ( V==ERROR ) /* 若这样的V不存在 */
                break;      /* 算法结束 */
            collected[V] = true;  /* 收录V */
            for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
                /* 若W是V的邻接点并且未被收录 */
                if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
                    if ( Graph->G[V][W]<0 ) /* 若有负边 */
                        return false; /* 不能正确解决,返回错误标记 */
                    /* 若收录V使得dist[W]变小 */
                    if ( dist[V]+Graph->G[V][W] < dist[W] ) {
                        dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */
                        path[W] = V; /* 更新S到W的路径 */
                    }
                }
        } /* while结束*/
        return true; /* 算法执行完毕,返回正确标记 */
    }
    
    

    邻接矩阵存储 - 多源最短路算法

    bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
    {
        Vertex i, j, k;
     
        /* 初始化 */
        for ( i=0; i<Graph->Nv; i++ )
            for( j=0; j<Graph->Nv; j++ ) {
                D[i][j] = Graph->G[i][j];
                path[i][j] = -1;
            }
     
        for( k=0; k<Graph->Nv; k++ )
            for( i=0; i<Graph->Nv; i++ )
                for( j=0; j<Graph->Nv; j++ )
                    if( D[i][k] + D[k][j] < D[i][j] ) {
                        D[i][j] = D[i][k] + D[k][j];
                        if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
                            return false; /* 不能正确解决,返回错误标记 */
                        path[i][j] = k;
                    }
        return true; /* 算法执行完毕,返回正确标记 */
    }
    
    

    拓扑排序

    /* 邻接表存储 - 拓扑排序算法 */
     
    bool TopSort( LGraph Graph, Vertex TopOrder[] )
    { /* 对Graph进行拓扑排序,  TopOrder[]顺序存储排序后的顶点下标 */
        int Indegree[MaxVertexNum], cnt;
        Vertex V;
        PtrToAdjVNode W;
           Queue Q = CreateQueue( Graph->Nv );
      
        /* 初始化Indegree[] */
        for (V=0; V<Graph->Nv; V++)
            Indegree[V] = 0;
             
        /* 遍历图,得到Indegree[] */
        for (V=0; V<Graph->Nv; V++)
            for (W=Graph->G[V].FirstEdge; W; W=W->Next)
                Indegree[W->AdjV]++; /* 对有向边<V, W->AdjV>累计终点的入度 */
                 
        /* 将所有入度为0的顶点入列 */
        for (V=0; V<Graph->Nv; V++)
            if ( Indegree[V]==0 )
                AddQ(Q, V);
                 
        /* 下面进入拓扑排序 */ 
        cnt = 0; 
        while( !IsEmpty(Q) ){
            V = DeleteQ(Q); /* 弹出一个入度为0的顶点 */
            TopOrder[cnt++] = V; /* 将之存为结果序列的下一个元素 */
            /* 对V的每个邻接点W->AdjV */
            for ( W=Graph->G[V].FirstEdge; W; W=W->Next )
                if ( --Indegree[W->AdjV] == 0 )/* 若删除V使得W->AdjV入度为0 */
                    AddQ(Q, W->AdjV); /* 则该顶点入列 */ 
        } /* while结束*/
         
        if ( cnt != Graph->Nv )
            return false; /* 说明图中有回路, 返回不成功标志 */ 
        else
            return true;
    }
    
    

    排序

    冒泡排序

    void Bubble_ Sort ( ElementType A[],int N )
    { for ( P=N-1; P>=0; P-- ) {
    f1ag = 0;
    for( i=0; i<P; i++ ) { /*一趟冒泡*/
    if(A[i]>A[i+1]){
    Swap(A[i],A[i+1] ) ;
    f1ag = 1; /*标识发生了交换*/
    }
    }
    if ( f1ag==0 ) break; /*全程无交换*/
    }
    }
    
    
    

    插入排序

    void InsertionSort( ElementType A[], int N )
    { /* 插入排序 */
         int P, i;
         ElementType Tmp;
          
         for ( P=1; P<N; P++ ) {
             Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
             for ( i=P; i>0 && A[i-1]>Tmp; i-- )
                 A[i] = A[i-1]; /*依次与已排序序列中元素比较并右移*/
             A[i] = Tmp; /* 放进合适的位置 */
         }
    }
    
    

    希尔排序

    void ShellSort( ElementType A[], int N )
    { /* 希尔排序 - 用Sedgewick增量序列 */
         int Si, D, P, i;
         ElementType Tmp;
         /* 这里只列出一小部分增量 */
         int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};
          
         for ( Si=0; Sedgewick[Si]>=N; Si++ ) 
             ; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */
     
         for ( D=Sedgewick[Si]; D>0; D=Sedgewick[++Si] )
             for ( P=D; P<N; P++ ) { /* 插入排序*/
                 Tmp = A[P];
                 for ( i=P; i>=D && A[i-D]>Tmp; i-=D )
                     A[i] = A[i-D];
                 A[i] = Tmp;
             }
    }
    
    

    堆排序

    void Swap( ElementType *a, ElementType *b )
    {
         ElementType t = *a; *a = *b; *b = t;
    }
      
    void PercDown( ElementType A[], int p, int N )
    { /* 改编代码4.24的PercDown( MaxHeap H, int p )    */
      /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
        int Parent, Child;
        ElementType X;
     
        X = A[p]; /* 取出根结点存放的值 */
        for( Parent=p; (Parent*2+1)<N; Parent=Child ) {
            Child = Parent * 2 + 1;
            if( (Child!=N-1) && (A[Child]<A[Child+1]) )
                Child++;  /* Child指向左右子结点的较大者 */
            if( X >= A[Child] ) break; /* 找到了合适位置 */
            else  /* 下滤X */
                A[Parent] = A[Child];
        }
        A[Parent] = X;
    }
     
    void HeapSort( ElementType A[], int N ) 
    { /* 堆排序 */
         int i;
           
         for ( i=N/2-1; i>=0; i-- )/* 建立最大堆 */
             PercDown( A, i, N );
          
         for ( i=N-1; i>0; i-- ) {
             /* 删除最大堆顶 */
             Swap( &A[0], &A[i] ); /* 见代码7.1 */
             PercDown( A, 0, i );
         }
    }
    
    

    归并排序

    递归实现

    /* 归并排序 - 递归实现 */
     
    /* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
    void Merge( ElementType A[], ElementType TmpA[], int L, int R, int RightEnd )
    { /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
         int LeftEnd, NumElements, Tmp;
         int i;
          
         LeftEnd = R - 1; /* 左边终点位置 */
         Tmp = L;         /* 有序序列的起始位置 */
         NumElements = RightEnd - L + 1;
          
         while( L <= LeftEnd && R <= RightEnd ) {
             if ( A[L] <= A[R] )
                 TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
             else
                 TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
         }
     
         while( L <= LeftEnd )
             TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
         while( R <= RightEnd )
             TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */
              
         for( i = 0; i < NumElements; i++, RightEnd -- )
             A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
    }
     
    void Msort( ElementType A[], ElementType TmpA[], int L, int RightEnd )
    { /* 核心递归排序函数 */ 
         int Center;
          
         if ( L < RightEnd ) {
              Center = (L+RightEnd) / 2;
              Msort( A, TmpA, L, Center );              /* 递归解决左边 */ 
              Msort( A, TmpA, Center+1, RightEnd );     /* 递归解决右边 */  
              Merge( A, TmpA, L, Center+1, RightEnd );  /* 合并两段有序序列 */ 
         }
    }
     
    void MergeSort( ElementType A[], int N )
    { /* 归并排序 */
         ElementType *TmpA;
         TmpA = (ElementType *)malloc(N*sizeof(ElementType));
          
         if ( TmpA != NULL ) {
              Msort( A, TmpA, 0, N-1 );
              free( TmpA );
         }
         else printf( "空间不足" );
    }
    
    

    循环实现

    /* 归并排序 - 循环实现 */
    /* 这里Merge函数在递归版本中给出 */
     
    /* length = 当前有序子列的长度*/
    void Merge_pass( ElementType A[], ElementType TmpA[], int N, int length )
    { /* 两两归并相邻有序子列 */
         int i, j;
           
         for ( i=0; i <= N-2*length; i += 2*length )
             Merge( A, TmpA, i, i+length, i+2*length-1 );
         if ( i+length < N ) /* 归并最后2个子列*/
             Merge( A, TmpA, i, i+length, N-1);
         else /* 最后只剩1个子列*/
             for ( j = i; j < N; j++ ) TmpA[j] = A[j];
    }
     
    void Merge_Sort( ElementType A[], int N )
    { 
         int length; 
         ElementType *TmpA;
          
         length = 1; /* 初始化子序列长度*/
         TmpA = malloc( N * sizeof( ElementType ) );
         if ( TmpA != NULL ) {
              while( length < N ) {
                  Merge_pass( A, TmpA, N, length );
                  length *= 2;
                  Merge_pass( TmpA, A, N, length );
                  length *= 2;
              }
              free( TmpA );
         }
         else printf( "空间不足" );
    }
    
    

    快速排序

    直接调用库函数

    /* 快速排序 - 直接调用库函数 */
     
    #include <stdlib.h>
     
    /*---------------简单整数排序--------------------*/
    int compare(const void *a, const void *b)
    { /* 比较两整数。非降序排列 */
        return (*(int*)a - *(int*)b);
    }
    /* 调用接口 */ 
    qsort(A, N, sizeof(int), compare);
    /*---------------简单整数排序--------------------*/
     
     
    /*--------------- 一般情况下,对结构体Node中的某键值key排序 ---------------*/
    struct Node {
        int key1, key2;
    } A[MAXN];
      
    int compare2keys(const void *a, const void *b)
    { /* 比较两种键值:按key1非升序排列;如果key1相等,则按key2非降序排列 */
        int k;
        if ( ((const struct Node*)a)->key1 < ((const struct Node*)b)->key1 )
            k = 1;
        else if ( ((const struct Node*)a)->key1 > ((const struct Node*)b)->key1 )
            k = -1;
        else { /* 如果key1相等 */
            if ( ((const struct Node*)a)->key2 < ((const struct Node*)b)->key2 )
                k = -1;
            else
                k = 1;
        }
        return k;
    }
    /* 调用接口 */ 
    qsort(A, N, sizeof(struct Node), compare2keys);
    /*--------------- 一般情况下,对结构体Node中的某键值key排序 ---------------*/
    
    

    不用

    /* 快速排序 */
     
    ElementType Median3( ElementType A[], int Left, int Right )
    { 
        int Center = (Left+Right) / 2;
        if ( A[Left] > A[Center] )
            Swap( &A[Left], &A[Center] );
        if ( A[Left] > A[Right] )
            Swap( &A[Left], &A[Right] );
        if ( A[Center] > A[Right] )
            Swap( &A[Center], &A[Right] );
        /* 此时A[Left] <= A[Center] <= A[Right] */
        Swap( &A[Center], &A[Right-1] ); /* 将基准Pivot藏到右边*/
        /* 只需要考虑A[Left+1] … A[Right-2] */
        return  A[Right-1];  /* 返回基准Pivot */
    }
     
    void Qsort( ElementType A[], int Left, int Right )
    { /* 核心递归函数 */ 
         int Pivot, Cutoff, Low, High;
           
         if ( Cutoff <= Right-Left ) { /* 如果序列元素充分多,进入快排 */
              Pivot = Median3( A, Left, Right ); /* 选基准 */ 
              Low = Left; High = Right-1;
              while (1) { /*将序列中比基准小的移到基准左边,大的移到右边*/
                   while ( A[++Low] < Pivot ) ;
                   while ( A[--High] > Pivot ) ;
                   if ( Low < High ) Swap( &A[Low], &A[High] );
                   else break;
              }
              Swap( &A[Low], &A[Right-1] );   /* 将基准换到正确的位置 */ 
              Qsort( A, Left, Low-1 );    /* 递归解决左边 */ 
              Qsort( A, Low+1, Right );   /* 递归解决右边 */  
         }
         else InsertionSort( A+Left, Right-Left+1 ); /* 元素太少,用简单排序 */ 
    }
     
    void QuickSort( ElementType A[], int N )
    { /* 统一接口 */
         Qsort( A, 0, N-1 );
    }
    
    

    表排序

    基数排序

    次位优先

    /* 基数排序 - 次位优先 */
     
    /* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */
    #define MaxDigit 4
    #define Radix 10
     
    /* 桶元素结点 */
    typedef struct Node *PtrToNode;
    struct Node {
        int key;
        PtrToNode next;
    };
     
    /* 桶头结点 */
    struct HeadNode {
        PtrToNode head, tail;
    };
    typedef struct HeadNode Bucket[Radix];
      
    int GetDigit ( int X, int D )
    { /* 默认次位D=1, 主位D<=MaxDigit */
        int d, i;
         
        for (i=1; i<=D; i++) {
            d = X % Radix;
            X /= Radix;
        }
        return d;
    }
     
    void LSDRadixSort( ElementType A[], int N )
    { /* 基数排序 - 次位优先 */
         int D, Di, i;
         Bucket B;
         PtrToNode tmp, p, List = NULL; 
          
         for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
             B[i].head = B[i].tail = NULL;
         for (i=0; i<N; i++) { /* 将原始序列逆序存入初始链表List */
             tmp = (PtrToNode)malloc(sizeof(struct Node));
             tmp->key = A[i];
             tmp->next = List;
             List = tmp;
         }
         /* 下面开始排序 */ 
         for (D=1; D<=MaxDigit; D++) { /* 对数据的每一位循环处理 */
             /* 下面是分配的过程 */
             p = List;
             while (p) {
                 Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
                 /* 从List中摘除 */
                 tmp = p; p = p->next;
                 /* 插入B[Di]号桶尾 */
                 tmp->next = NULL;
                 if (B[Di].head == NULL)
                     B[Di].head = B[Di].tail = tmp;
                 else {
                     B[Di].tail->next = tmp;
                     B[Di].tail = tmp;
                 }
             }
             /* 下面是收集的过程 */
             List = NULL; 
             for (Di=Radix-1; Di>=0; Di--) { /* 将每个桶的元素顺序收集入List */
                 if (B[Di].head) { /* 如果桶不为空 */
                     /* 整桶插入List表头 */
                     B[Di].tail->next = List;
                     List = B[Di].head;
                     B[Di].head = B[Di].tail = NULL; /* 清空桶 */
                 }
             }
         }
         /* 将List倒入A[]并释放空间 */
         for (i=0; i<N; i++) {
            tmp = List;
            List = List->next;
            A[i] = tmp->key;
            free(tmp);
         } 
    }
    
    

    主位优先

    /* 基数排序 - 主位优先 */
     
    /* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */
     
    #define MaxDigit 4
    #define Radix 10
     
    /* 桶元素结点 */
    typedef struct Node *PtrToNode;
    struct Node{
        int key;
        PtrToNode next;
    };
     
    /* 桶头结点 */
    struct HeadNode {
        PtrToNode head, tail;
    };
    typedef struct HeadNode Bucket[Radix];
      
    int GetDigit ( int X, int D )
    { /* 默认次位D=1, 主位D<=MaxDigit */
        int d, i;
         
        for (i=1; i<=D; i++) {
            d = X%Radix;
            X /= Radix;
        }
        return d;
    }
     
    void MSD( ElementType A[], int L, int R, int D )
    { /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */
         int Di, i, j;
         Bucket B;
         PtrToNode tmp, p, List = NULL; 
         if (D==0) return; /* 递归终止条件 */
          
         for (i=0; i<Radix; i++) /* 初始化每个桶为空链表 */
             B[i].head = B[i].tail = NULL;
         for (i=L; i<=R; i++) { /* 将原始序列逆序存入初始链表List */
             tmp = (PtrToNode)malloc(sizeof(struct Node));
             tmp->key = A[i];
             tmp->next = List;
             List = tmp;
         }
         /* 下面是分配的过程 */
         p = List;
         while (p) {
             Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
             /* 从List中摘除 */
             tmp = p; p = p->next;
             /* 插入B[Di]号桶 */
             if (B[Di].head == NULL) B[Di].tail = tmp;
             tmp->next = B[Di].head;
             B[Di].head = tmp;
         }
         /* 下面是收集的过程 */
         i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */
         for (Di=0; Di<Radix; Di++) { /* 对于每个桶 */
             if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */
                 p = B[Di].head;
                 while (p) {
                     tmp = p;
                     p = p->next;
                     A[j++] = tmp->key;
                     free(tmp);
                 }
                 /* 递归对该桶数据排序, 位数减1 */
                 MSD(A, i, j-1, D-1);
                 i = j; /* 为下一个桶对应的A[]左端 */
             } 
         } 
    }
     
    void MSDRadixSort( ElementType A[], int N )
    { /* 统一接口 */
        MSD(A, 0, N-1, MaxDigit); 
    }
    
    

    排序算法的比较

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KcB0QDmp-1591266109980)(E:\错误集锦&心得\1590743717044.png)]

    老师的所有排序算法

    /* bubble sort */
    void bubbleSort(int arr[], int lengthOfArr, int flag) {
        if(lengthOfArr < 2)
            return;
        for(int i=1; i<lengthOfArr; i++) {
            if(arr[i-1]> arr[i]) {
                flag=0;
                int temp = arr[i];
                arr[i] = arr[i-1];
                arr[i-1]= temp;
            }
        }
        if(flag==1)
            return;
        bubbleSort(arr, lengthOfArr-1, 1);
    }
    
    /* selection sort */
    void selectionSort(int *arr, int lengthOfArr) {
        if(lengthOfArr >= 1) {
            for(int i=0; i<lengthOfArr; i++) {
                if(arr[i]< arr[0]) {
                    int temp = arr[i]; 
                    arr[i] = arr[0];
                    arr[0] = temp; 
                }
            }
            selectionSort(&arr[1], lengthOfArr-1); 
        }
    }
    
    /* insert sort */
    void Insert(int *arr, int lengthOfArr) {
        int key=arr[lengthOfArr];
        int j;
        for(j=lengthOfArr-1; j>=0 && key<=arr[j];j--) {
            arr[j+1]=arr[j]; 
            arr[j]=key;
        } 
    }
    void Insert_Sort(int *arr, int lengthOfArr) {
        if(lengthOfArr>0) {
            Insert_Sort(arr, lengthOfArr-1);
            Insert(arr, lengthOfArr); 
        }
        else return;
    }
    
    /* quik sort */
    int Partition(int *arr, int low, int high) { 
        arr[0]=arr[low];
        while(low<high) {
            while(high>low && arr[high]>=arr[0])
                high--;
            arr[low]=arr[high]; 
            while(low<high && arr[low]<=arr[0])
                low++;
            arr[high]=arr[low];
        }
        arr[low]=arr[0]; 
        return low;
    }
    
    void Quiksort(int *arr, int low, int high) {
        if(low < high) {
            int Partition_=Partition(arr, low, high); 
            Quiksort(arr, low, Partition_-1);
            Quiksort(arr, Partition_+1, high); 
        }
    }
    
    /* merge sort*/
    void Merge(int arr[], int low, int mid, int high, int Temp[]) { 
        int P_Left = low, P_Right=mid+1, P_Result=low; 
        while(P_Left<=mid&&P_Right<=high) {
            if(arr[P_Left] <= arr[P_Right]) {
                Temp[P_Result] = arr[P_Left]; 
                P_Left++; P_Result++;
            } else {
                Temp[P_Result]=arr[P_Right]; 
                P_Right++; P_Result++;
            }
        }
        while(P_Left <= mid) {
            Temp[P_Result]=arr[P_Left];
            P_Left++; P_Result++; 
        }
        while(P_Right <= high) {
            Temp[P_Result]=arr[P_Right];
            P_Right++; P_Result++;
        }
        for(int i=low; i<P_Result; i++) {
            arr[i] = Temp[i];
        }
    }
    void MergeSort(int arr[], int low, int high, int Temp[]) {
        if(low < high) {
            int mid = (low+high)/2;
            MergeSort(arr, low, mid, Temp);//递归公式 MSor(t arr,mid+1,high,Temp);//递归公式
            Merge(arr, low, mid, high, Temp); 
        }
    }
    
    

    散列(Hashing)

    散列表

    散列函数的构造方法

    冲突处理方法

    #define MAXTABLESIZE 100000 /* 允许开辟的最大散列表长度 */
    typedef int ElementType;    /* 关键词类型用整型 */
    typedef int Index;          /* 散列地址类型 */
    typedef Index Position;     /* 数据所在位置与散列地址是同一类型 */
    /* 散列单元状态类型,分别对应:有合法元素、空单元、有已删除元素 */
    typedef enum { Legitimate, Empty, Deleted } EntryType;
     
    typedef struct HashEntry Cell; /* 散列表单元类型 */
    struct HashEntry{
        ElementType Data; /* 存放元素 */
        EntryType Info;   /* 单元状态 */
    };
     
    typedef struct TblNode *HashTable; /* 散列表类型 */
    struct TblNode {   /* 散列表结点定义 */
        int TableSize; /* 表的最大长度 */
        Cell *Cells;   /* 存放散列单元数据的数组 */
    };
     
    int NextPrime( int N )
    { /* 返回大于N且不超过MAXTABLESIZE的最小素数 */
        int i, p = (N%2)? N+2 : N+1; /*从大于N的下一个奇数开始 */
     
        while( p <= MAXTABLESIZE ) {
            for( i=(int)sqrt(p); i>2; i-- )
                if ( !(p%i) ) break; /* p不是素数 */
            if ( i==2 ) break; /* for正常结束,说明p是素数 */
            else  p += 2; /* 否则试探下一个奇数 */
        }
        return p;
    }
     
    HashTable CreateTable( int TableSize )
    {
        HashTable H;
        int i;
     
        H = (HashTable)malloc(sizeof(struct TblNode));
        /* 保证散列表最大长度是素数 */
        H->TableSize = NextPrime(TableSize);
        /* 声明单元数组 */
        H->Cells = (Cell *)malloc(H->TableSize*sizeof(Cell));
        /* 初始化单元状态为“空单元” */
        for( i=0; i<H->TableSize; i++ )
            H->Cells[i].Info = Empty;
     
        return H;
    }
    
    Position Find( HashTable H, ElementType Key )
    {
        Position CurrentPos, NewPos;
        int CNum = 0; /* 记录冲突次数 */
     
        NewPos = CurrentPos = Hash( Key, H->TableSize ); /* 初始散列位置 */
        /* 当该位置的单元非空,并且不是要找的元素时,发生冲突 */
        while( H->Cells[NewPos].Info!=Empty && H->Cells[NewPos].Data!=Key ) {
                                               /* 字符串类型的关键词需要 strcmp 函数!! */
            /* 统计1次冲突,并判断奇偶次 */
            if( ++CNum%2 ){ /* 奇数次冲突 */
                NewPos = CurrentPos + (CNum+1)*(CNum+1)/4; /* 增量为+[(CNum+1)/2]^2 */
                if ( NewPos >= H->TableSize )
                    NewPos = NewPos % H->TableSize; /* 调整为合法地址 */
            }
            else { /* 偶数次冲突 */
                NewPos = CurrentPos - CNum*CNum/4; /* 增量为-(CNum/2)^2 */
                while( NewPos < 0 )
                    NewPos += H->TableSize; /* 调整为合法地址 */
            }
        }
        return NewPos; /* 此时NewPos或者是Key的位置,或者是一个空单元的位置(表示找不到)*/
    }
     
    bool Insert( HashTable H, ElementType Key )
    {
        Position Pos = Find( H, Key ); /* 先检查Key是否已经存在 */
     
        if( H->Cells[Pos].Info != Legitimate ) { /* 如果这个单元没有被占,说明Key可以插入在此 */
            H->Cells[Pos].Info = Legitimate;
            H->Cells[Pos].Data = Key;
            /*字符串类型的关键词需要 strcpy 函数!! */
            return true;
        }
        else {
            printf("键值已存在");
            return false;
        }
    }
    
    
    #define KEYLENGTH 15                   /* 关键词字符串的最大长度 */
    typedef char ElementType[KEYLENGTH+1]; /* 关键词类型用字符串 */
    typedef int Index;                     /* 散列地址类型 */
    /******** 以下是单链表的定义 ********/
    typedef struct LNode *PtrToLNode;
    struct LNode {
        ElementType Data;
        PtrToLNode Next;
    };
    typedef PtrToLNode Position;
    typedef PtrToLNode List;
    /******** 以上是单链表的定义 ********/
     
    typedef struct TblNode *HashTable; /* 散列表类型 */
    struct TblNode {   /* 散列表结点定义 */
        int TableSize; /* 表的最大长度 */
        List Heads;    /* 指向链表头结点的数组 */
    };
     
    HashTable CreateTable( int TableSize )
    {
        HashTable H;
        int i;
     
        H = (HashTable)malloc(sizeof(struct TblNode));
        /* 保证散列表最大长度是素数,具体见代码5.3 */
        H->TableSize = NextPrime(TableSize);
     
        /* 以下分配链表头结点数组 */
        H->Heads = (List)malloc(H->TableSize*sizeof(struct LNode));
        /* 初始化表头结点 */
        for( i=0; i<H->TableSize; i++ ) {
             H->Heads[i].Data[0] = '\0';
             H->Heads[i].Next = NULL;
        }
     
        return H;
    }
     
    Position Find( HashTable H, ElementType Key )
    {
        Position P;
        Index Pos;
         
        Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
        P = H->Heads[Pos].Next; /* 从该链表的第1个结点开始 */
        /* 当未到表尾,并且Key未找到时 */ 
        while( P && strcmp(P->Data, Key) )
            P = P->Next;
     
        return P; /* 此时P或者指向找到的结点,或者为NULL */
    }
     
    bool Insert( HashTable H, ElementType Key )
    {
        Position P, NewCell;
        Index Pos;
         
        P = Find( H, Key );
        if ( !P ) { /* 关键词未找到,可以插入 */
            NewCell = (Position)malloc(sizeof(struct LNode));
            strcpy(NewCell->Data, Key);
            Pos = Hash( Key, H->TableSize ); /* 初始散列位置 */
            /* 将NewCell插入为H->Heads[Pos]链表的第1个结点 */
            NewCell->Next = H->Heads[Pos].Next;
            H->Heads[Pos].Next = NewCell; 
            return true;
        }
        else { /* 关键词已存在 */
            printf("键值已存在");
            return false;
        }
    }
     
    void DestroyTable( HashTable H )
    {
        int i;
        Position P, Tmp;
         
        /* 释放每个链表的结点 */
        for( i=0; i<H->TableSize; i++ ) {
            P = H->Heads[i].Next;
            while( P ) {
                Tmp = P->Next;
                free( P );
                P = Tmp;
            }
        }
        free( H->Heads ); /* 释放头结点数组 */
        free( H );        /* 释放散列表结点 */
    }
    
    

    散列表的性能分析

    展开全文
  • 数据结构Java语言描述原书第三版 代码 DataStructures and Other Objects Using Java Third Edition Code(美)Michael Main 著 孔芳 韩月娟译
  • 成功时服务器返回的 json data(成功时没有<code>错误码</code>和 <code>消息</code>): <p><code>{ "id": "123456", "userName": "test", "email": "test.com", ...
  • 这是我在哈工大程序设计实践课程上写的一些代码,包含很多数据结构实现
  • 数据结构data structure

    2013-09-20 22:59:00
    Organization of data structure part of the code
  • NFC学习—— code编译和code结构

    千次阅读 2013-03-26 17:04:35
    对于NFC代码编译,目前为止,我见过两家不同方案商的书写方式,都是在device下的XXXX.mk文件中书写,XXXX不同的方案商不同的...frameworks/native/data/etc/android.hardware.nfc.xml:system/etc/permissions/android.h

          对于NFC代码编译,目前为止,我见过两家不同方案商的书写方式,都是在device下的XXXX.mk文件中书写,XXXX不同的方案商不同的产品名称不同。下面具体来看:

    方式A:

    PRODUCT_COPY_FILES += \
    frameworks/native/data/etc/android.hardware.nfc.xml:system/etc/permissions/android.hardware.nfc.xml
    
    # NFC packages
    PRODUCT_PACKAGES += \
                    libnfc \
                    libnfc_jni \
                    Nfc \
                    Tag
    

    方式B:

    #NXP NFC 
    PRODUCT_COPY_FILES += \
    frameworks/native/data/etc/android.hardware.nfc.xml:system/etc/permissions/android.hardware.nfc.xml
    
    PRODUCT_PACKAGES += \
            nfc.XXXX \
            libnfc \
            libnfc_jni \
            Nfc \
            Tag 
    

           对比这两种方式,可以很明显发现其中的不同点nfc.XXXX,下面就两者的不同之处在分析:

           nfc.XXXX 是nfc_hw.c 编译生成的nfc.XXXX.so包,在out/目录下。方式A中并没有把nfc.XXXX放进去,它放在modules.mk中编译。nfc_hw.c不同的方案也具体放在不同的位置。总之,它的目的是生成nfc.XXXX.so以供调用。

             除了上述之外的东西,还需要在init.rc中配置:

    # NFC
        setprop ro.nfc.port "I2C"
    
             至此,NFC编译部分都配置完毕了。

             通过以上的分析,NFC 在android 中的code 结构都差不多出来了,下面分析下:  

     客户端:android提供了两个API包给apk,分别是android.nfc.techandroid.nfc,实现了NFC的应用接口,代码路径frameworks/base/core/java/android/nfc/techframeworks/base/core/java/android/nfc

     服务端:packages/apps/Nfc是一个类似电话本的应用,这个程序在启动后自动运行,并一直运行,作为NFC的服务进程存在,是NFC的核心。

    在这个程序代码中,有个JNI库,供NfcService调用,代码路径是packages/apps/Nfc/jni/.编译文件中,还有个Tag部分,代码路径是packages/apps/Tag.

      库文件:代码路径是external/libnfc-nxp,C编写的库文件,有两个库,分别是libnfc.solibnfc_ndef.solibnfc.so是一个主要的库,实现了NFC stack的大部分功能,主要提供NFC的服务进程调用。libnfc_ndef是一个很小的库,主要是实现NDEF消息的解析,供framework调用

        nfc_hw.c:这个文件的具体路径不确定。

        pn544.c:这个文件是具体nfc芯片的驱动,一般都是drivers下。


    由于本人初学,能力有限,有错误的地方欢迎指出。

    参考文章:

    NFC framework introduce(一)

    展开全文
  • 这个结构体变量就具有了系统控制寄存器的整体结构了。下面的任务就是将这个变量映射到对应的寄存器地址。通过对比可以知道,SysCtrlRegs变量的映射地址应该是0x7010; 在DSP编程中,用#pragma的编程方式将变量映射...

    相对于传统的宏定义方式,F28335的寄存器定义方式更加复杂。为了说清楚这个问题,以系统控制寄存器为例。

    系统控制寄存器

    名称 地址 大小(*16) 描述
    PLLSTS 0x7011 1 PLL状态寄存器
    保留 0x7012~0x7019 8
    HISPCP 0x701A 1 高速外设时钟分频寄存器
    LOSPCP 0x701B 1 低速外设失踪分频寄存器
    PCLKCR0 0x701C 1 外设时钟控制寄存器0
    PCLKCR1 0x701D 1 外设时钟控制寄存器1
    LPMCR0 0x701E 1 低功模式控制寄存器0
    保留 0x701F 1
    PCLKCR3 0x7020 1 外设时钟控制寄存器
    PLLCR 0x7021 1 PLL控制寄存器
    SCSR 0x7022 1 系统控制和状态寄存器
    WDCNTR 0x7023 1 看门狗计数寄存器
    保留 0x7024 1
    WDKEY 0x7025 1 看门狗复位寄存器
    保留 0x7026~0x7028 3
    WDCR 0x7029 1 看门狗控制寄存器
    保留 0x702A~0x702F 6

    1.相关结构体

    //---------------------------------------------------------------------------
    // System Control Register File:
    //起始地址应该是0x7010
    struct SYS_CTRL_REGS {
       Uint16              rsvd7;     // 0
       union   PLLSTS_REG  PLLSTS;    // 1
       Uint16              rsvd1[8];  // 2-9
       union   HISPCP_REG  HISPCP;    // 10: High-speed peripheral clock pre-scaler
       union   LOSPCP_REG  LOSPCP;    // 11: Low-speed peripheral clock pre-scaler
       union   PCLKCR0_REG PCLKCR0;   // 12: Peripheral clock control register
       union   PCLKCR1_REG PCLKCR1;   // 13: Peripheral clock control register
       union   LPMCR0_REG  LPMCR0;    // 14: Low-power mode control register 0
       Uint16              rsvd2;     // 15: reserved
       union   PCLKCR3_REG PCLKCR3;   // 16: Peripheral clock control register
       union   PLLCR_REG   PLLCR;     // 17: PLL control register
       // No bit definitions are defined for SCSR because
       // a read-modify-write instruction can clear the WDOVERRIDE bit
       Uint16              SCSR;      // 18: System control and status register
       Uint16              WDCNTR;    // 19: WD counter register
       Uint16              rsvd4;     // 20
       Uint16              WDKEY;     // 21: WD reset key register
       Uint16              rsvd5[3];  // 22-24
       // No bit definitions are defined for WDCR because
       // the proper value must be written to the WDCHK field
       // whenever writing to this register.
       Uint16              WDCR;      // 25: WD timer control register
       Uint16              rsvd6[6];  // 26-31
    };
    
    

    此处通过一个结构体,将系统控制寄存器中所有寄存器都包含其中。

    2.定义结构体变量

    volatile struct SYS_CTRL_REGS SysCtrlRegs;
    

    这个结构体变量就具有了系统控制寄存器的整体结构了。下面的任务就是将这个变量映射到对应的寄存器地址。通过对比可以知道,SysCtrlRegs变量的映射地址应该是0x7010;

    在DSP编程中,用#pragma的编程方式将变量映射到对应的地址。其具体的格式为:

    //为变量分配地址
    #ifdef __cplusplus
    #pragma DATA_SECTION("SysCtrlRegsFile")//C++语法
    #else
    #pragma DATA_SECTION(SysCtrlRegs,"SysCtrlRegsFile");//C语言语法,若是C开发,可以只写这一句。
    #endif
    //定义结构体变量
    volatile struct SYS_CTRL_REGS SysCtrlRegs;
    

    上面代码,即通过#pragma的编程方式,将SysCtrlRegs变量与SysCtrlRegsFile文件所连接的地址连接起来。下面就是解决如何将数据块文件与寄存器地址连接起来。这就需要cmd文件来解决了。

    补充
    DATA_SECTION函数
    //在C语言中
    #pragma DATA_SECTION ( symbol , " section name ");
    //在C++语言中
    #pragma DATA_SECTION (" section name ");
    

    在C语言中,这条代码的含义就是为symbol变量申请数据空间。将symbol变量的数据存储在section name对应的地址。
    举例:

    #pragma DATA_SECTION(bufferB, "my_sect")
    char bufferB[512];//此处不可以是指针,是已经分配空间的数据类型。
    
    CODE_SECTION函数
    #pragma CODE_SECTION (symbol , "section name ")
    

    在C语言中,这条代码的含义就是为symbol变量申请程序空间。将symbol变量的数据存储在section name对应的地址。
    举例

    char bufferA[80];
    char bufferB[80];
    #pragma CODE_SECTION(funcA, "codeA")
    char funcA(int i);//fancA放入codeA映射的位置
    char funcB(int i);//fanB放入.txet映射的位置
    void main()
    {
    char c;
    c = funcA(1);
    c = funcB(2);
    }
    char funcA (int i)
    {
    return bufferA[i];
    }
    char funcB (int j)
    {
    return bufferB[j];
    }
    

    3.cmd文件

    MEMORY
    {
     PAGE 0:    /* Program Memory */
       ...
     PAGE 1:    /* Data Memory */
       ...                 
       SYSTEM      : origin = 0x007010, length = 0x000020     /* System control registers */
       ...
    }
    
     
    SECTIONS
    {
       ...
       SysCtrlRegsFile   : > SYSTEM,      PAGE = 1
       ...
    }
    

    如上代码所示,cmd文件中分成MEMORY和SECTIONS两个部分。需要注意的是,在cmd文件中注释方式只能是/**/,不可以为//。(我在CCS6.1上验证发现,//注释方式也是可以的。)
    在MEMORY中,最多可以256个PAGE(PAGE0~PAGE255)。习惯上,将PAGE0作为程序空间,将PAGE作为数据空间。程序中的SYSTEM : origin = 0x007010, length = 0x000020,很容易理解,就是将SYSTEM的实际地址的起始地址为0x7010,长度为0x20(32个字长) 。
    在SECTIONS中,将SysCtrlRegsFile 和SYSTEM链接起来。因而,上面定义的SysCtrlRegs就与系统控制寄存器建立起了以上关系。

    结构体的位定义

    取系统控制的第1个寄存器(锁相环状态寄存器)为例。

    PLLSTS(锁相环状态寄存器)

    名称 描述
    15~9 保留
    8~7 DIVSEL 时钟分频选择;
    00,01:4分频;
    10:2分频;11:1分频
    6 MCLKOFF 时钟检测电路关闭位;
    0:默认模式,时钟检测使能;
    1:时钟检测电路关闭,系统不会进入limp-mode模式
    5 OSCOOF 振荡器时钟禁止位;
    0:晶振时钟信号会被送到PLL电路;
    1:晶振时钟信号不会被送到PLL电路。
    当此位=1时,
    此时不要进入HALT或STANDBY模式,不要写入PLLCR寄存器,否则会倒追不可预知的后果;
    看门狗行为与输入时钟有关,若X1或X1与X2,看门狗不工作。XCLKIN:看门狗工作。
    OSCOFF用于测试时钟监视逻辑电路。
    4 MCLKCLR 时钟丢失状态清除位
    0:写无影响,读取返回0;
    1:强制将时钟检测电路进行复位。如果OSCCLK(晶振时钟)依然丢失,时钟检测电路会再次产生一次系统复位信号,并将MCLKSTS置位,此时CPU的工作时钟为limp-mode模式产生的低速时钟
    3 MALKSTS 对该位写无效,写MCLKCLR或者外部复位时候,该位被清除
    0:正常模式,时钟信号没有丢失;
    1:晶振信号丢失,CPU工作在limp-mode
    2 PLLOFF PLL电路关闭位,只有PLLCR=0时候,才能将PLL电路关闭
    0:PLL电路正常工作
    1:PLL电路关闭
    1 保留
    0 PLLLOCKS PLL电路状态位
    0:表示锁相环依然正在锁相,此时最好等待
    1:PLL电路已经锁相完成

    位区结构体

    struct PLLSTS_BITS   {    // bits  description
       Uint16 PLLLOCKS:1;     // 0     PLL lock status
       Uint16 rsvd1:1;        // 1     reserved
       Uint16 PLLOFF:1;       // 2     PLL off bit
       Uint16 MCLKSTS:1;      // 3     Missing clock status bit
       Uint16 MCLKCLR:1;      // 4     Missing clock clear bit
       Uint16 OSCOFF:1;       // 5     Oscillator clock off
       Uint16 MCLKOFF:1;      // 6     Missing clock detect
       Uint16 DIVSEL:2;       // 7:8   Divide Select
       Uint16 rsvd2:7;        // 15:9  reserved
    };
    

    上面结构体定义了PLL状态寄存器的每一位的名称。位区结构体定义时需要注意:

    • 位定义由低位到高位
    • 每个名称后面带有冒号,冒号后接着是位长。
    • 并不是所有的寄存器都需要定义位区,从前面SYS_CTRL_REGS结构体中也可看出!

    下面需要将位区与整个寄存器链接起来。在DSP的编程中,使用的方法是共同体。

    共同体

    union PLLSTS_REG 
    {
       Uint16              all;
       struct PLLSTS_BITS  bit;
    };
    

    通过共同体,将结构体PLLSTS_REG中all变量和bit变量共享一块存储空间,而此时,通过操作结构体PLLSTS_REG变量即可方便操作整个寄存器或者寄存器的每一位。这里从上篇博客(F28335第二篇——系统控制初始化)中选取一个例子 。

    SysCtrlRegs.PLLSTS.bit.DIVSEL = 0;//保证PLL是4分频
    

    整体操作的也是类似:

    SysCtrlRegs.PLLSTS.all = 0
    
    展开全文
  • keil c51中的data idata xdata code详解

    千次阅读 2014-01-11 11:26:19
    在keilc51中定义了data idata xdata code几种域修饰符。这些修饰符决定了变量访问方式。 data:用mov直接访问的内部RAM idata:用mov @间接访问的内部RAM xdata:用movx访问的外部RAM code:用movc访问的rom ...
    51单片机采用哈佛结构。内存空间编址有重叠。可以在不同总线(本文称其为总线域,简称域)上定义不同的变量。在keilc51中定义了data idata xdata code几种域修饰符。这些修饰符决定了变量访问方式。
    data:用mov直接访问的内部RAM
    idata:用mov @间接访问的内部RAM
    xdata:用movx访问的外部RAM
    code:用movc访问的rom

    这些假定以上以及类型为where。数据类型为type。


    干货:
    变量(包括指针)默认存储在data中。指针能够智能的指向所有的域。
    指定变量(包括指针)在某个域时,域修饰符写在变量类型后面。type where value,type* where point。
    想让指针只能指向某个域type where* point
    指定指针的域并指定指针本身的存储域 type where* where point
    const写在前面const type where* where point
    声明struct类型不用where。定义变量时候用。struct变量不能跨域。


    以下是干货来源
    一下是实验结果
    type value :data中的变量
    where type value :where中的变量
    type where value :where中的变量
    where type where value 是的,没错,这种神经病写法也是在where中的变量
    type * point data中的跨域指针,
    where type * point 存储在where中的跨域指针
    type * where point 存储在where中的跨域指针
    where type * where point 这种更神经病的写法也是存储在where中的跨域指针
    type where* point 存储在内部RAM中只能指向where的指针
    where type where* point 存储在where中指向where的指针
    type where* where point 存储在where中指向where的指针

    很乱是吧?我们整理一下


    聪明的同学已经发现规律了,是不是?
    作为c不得不提的一种变量——指针。keil c51中还存在一个指针,这个指针实际上是sizeof(type*) + 1的。有一个字节来存储指针指向的区域。访问*point时对于不同区域的数据使用不同的指令。也就是说这中指针可以访问所有的总线。暂且称其跨域指针。

    既然指针也是变量“指向什么东西”是指针变量的类型。那么互忽略类型,把这些写法调换顺序。

    发现规律了么?data,idata,xdata,code可以在类型前,也可以在类型之后,或者前后都有。
    定义变量时,c类型最前面最着最后面添加(或者前后都有)总线域修饰符,可以决定该变量存储的位置。前后都不加,默认是
    data。
    我们在单独关心一下指针。

    发现规律了么?type *是可以指向任何区域的指针。决定指针指向位置时候域修饰符必须在type和*之间。
    至于const struct,呵呵自己试试就知道了。
    展开全文
  • Data Structure数据结构

    2009-09-25 11:06:00
     昨天晚上很神奇地做出了一道题目,小乌龟非要我把题目的code写出来,当然自己还是怀疑自己能否一下就搞定,但是还是尝试性的敲起来,一步一步脚踏实地地写,中间因为之前没认真看题,把问题简单化,就停下细看
  • 国外数据结构经典教材 Advanced Data Structures presents a comprehensive look at the ideas, analysis, and implementation details of data structures as a specialized topic in applied algorithms. This ...
  • Program Size: Code=344 RO-data=252 RW-data=100 ZI-data=1024 看了多遍,总是忘,这次还是把它分析透了吧,若有不对的地方还请各位看官指正补充 固定不变的代码存在ROM或flash里;这个固定不变的代码有两种,一种...
  • Oracle Data block 的物理结构

    千次阅读 2009-10-19 22:52:00
    data block物理结构的认识 1.Data Block 物理结构图: 2.一次对block的dump过程: PHP code:SQL> create table t9 (a varchar(10));Table created.SQL> insert into t9 values(a);1 row created
  • 二维码(QR code)基本结构及生成原理

    万次阅读 多人点赞 2016-11-27 00:14:49
    什么是二维码?二维码 (2-dimensional bar code)...在许多种类的二维条码中,常用的码制有:Data Matrix, Maxi Code, Aztec, QR Code, Vericode, PDF417, Ultracode, Code 49, Code 16K等。二维条码/二维码可以分为堆
  • 存储器类型 本C51编译器支持8051及其派生类型的结构能够访问8051的所有存储器空间具有下表列出的存储器类型的变量都可以被分配到某个特定的存储器空间。存储器类型 描述code 程序空间64 Kbytes ;通过MOVC @A+DPTR ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,434
精华内容 973
关键字:

datacode结构