精华内容
下载资源
问答
  • 数据结构c 进制转换问题(栈)

    千次阅读 多人点赞 2017-10-07 17:22:47
    数据结构 进制转换 栈 C语言
       用栈来实现进制进制转换  应使用辗转相除法 注意栈的操作
        #include <stdio.h>    
        #include <stdlib.h>          
        #define S_SIZE 100 
        #define STACKINCREMENT 10      
        typedef struct SqStack{    
           int *base;  
           int top;     
           int stacksize;   
        }SqStack;    
          
      //初始化空栈     
        void InitStack(SqStack &S)    
        {  
            S.base=(int *)malloc(S_SIZE*sizeof(int));  
            S.stacksize=S_SIZE;    
            S.top=-1;  
        }    
      
    //判断空栈  
        int StackEmpty(SqStack &S)    
        {    
           if(S.top==-1)    
               return 1;    
           else    
               return 0;    
        }     
    //判断栈满  
        int  StackFull(SqStack &S)  
        {  
           if(S.top==S.stacksize)    
               return 1;    
           else    
               return 0;    
        }  
       
        //进栈  
        void push(SqStack &S,int x)    
        {   
          if(StackFull(S))  
            printf("栈满\n");  
          S.base[++S.top]=x;   
        }    
        //出栈  
        int pop(SqStack &S)    
        {  
          int x;  
          if(StackEmpty(S))  
             printf("栈空\n");  
          x=S.base[S.top];   
          S.top--;  
          return x;  
        }   
        //进制转化函数  
        void convert(SqStack &S,int N,int n)    
        {    
          int i,x;   
          do     
          {  
            push(S,N%n);    
            N/=n;    
          } while (N!=0);     
            
          while(!StackEmpty(S))    
          {   
            x=pop(S);  
            if(x>9)      
        {   
              if(x==10) x='A';
              if(x==11) x='B';
              if(x==12) x='C';
              if(x==13) x='D';
              if(x==14) x='E';
              if(x==15) x='F';    //16 进制的转换
             
                printf("%c",x);  
            }  
            else    
                printf("%d",x);    
          }    
          printf("\n");    
        }    
       int main()    
        {   
            int n,N;//要转换成的进制数和要转换的数   
            SqStack s;   
            scanf("%d%d",&n,&N) ;  
                    InitStack(s);  
            printf("%d转换为%d进制后为:\n",n,N);    
            convert(s,n,N);      
            
                    return 0;  
     } 
    这样就可以啦..........
    展开全文
  • 小顶堆数据结构C/C++代码实现

    千次阅读 2016-12-23 12:11:42
    一、堆也是一种数据结构,从实际应用意义来说,他是一种最优级别数据永远在第一位的队列,本文皆以最小值为例(小顶堆),即它变相是一种会永远保持最小值先出队的队列。 二、堆的本质是一颗完全二叉树,树根永远为...

    相比队列和栈,很多人可能对堆的概念比较陌生,下面个给出堆的本质概念

    一、堆也是一种数据结构,从实际应用意义来说,他是一种最优级别数据永远在第一位的队列,本文皆以最小值为例(小顶堆),即它变相是一种会永远保持最小值先出队的队列

    二、堆的本质是一颗完全二叉树树根永远为整个树的最小值,这也就是实现了①永远保持最小值先出队的队列这样的功能。

    三、为了便于实现②树根为整个树的最小值堆中某个节点的值总是大于其父节点的值,这样当树根出队以后,次小的值一定是树根的左右子节点的其中一个。并且堆每个结点的左子树和右子树也都是一个堆。即:当某一个节点发生改变之后,取代他的只有可能和他有直系关系的节点。

    四、为了保证②的完全二叉树性质当堆有元素入队时,我们先将其放在队尾,然后再对其做出调整。当有元素出队时,我们把最后一个节点的元素先放在队首,然后再对其做出调整。

    五、结合③和④,我们可以得出结论,无论是入队还是出队,我们实际做的操作都是在某一路径下完成若干次子节点与父节点交换的过程(我们称之为上浮和下沉)


    下面再说一下堆支持的基本操作

    ①入队,插入新元素

    ②出队,删除堆顶

    ③查找最小值(堆顶),其实也可以查找其次小值

    ④建堆,这里建队有两种方法,一种是将值一个一个的插入,另一种是先变成一个堆,再对其进行多次调整。



    下面具体讲实现方法,首先定义一个小顶堆

    /*
     * 使用数组实现堆
     *
     * capacity 数组的最大容量
     * size     数组的长度
     * elements 堆中的元素存放的数组
     */
    struct MinHeap
    {
        int capacity;
        int size;
        ElementType *elements; 
    };



    入队:

    先将要插入的结点x放在最底层的最右边,插入后满足完全二叉树的特点,然后把x依次向上调整到合适位置满足堆的性质,即“结点上浮”。

     for (i = ++pqueue->size; x < pqueue->elements[i / 2]; i /= 2)
                pqueue->elements[i] = pqueue->elements[i / 2]; //上浮
            pqueue->elements[i] = x;


    出队:

    树根出队,然后先把最后的叶子节点放在树根,再逐渐下沉到其合适的位置。

    // 注意对节点进行下沉操作时,要判断该节点是有两个儿子还是一个儿子
        minElement = pqueue->elements[1];
        lastElement = pqueue->elements[pqueue->size--];
        for (i = 1; i * 2 <= pqueue->size; i = child)
        {
            child = i * 2;
             
            // 节点i只有一个儿子时必有i * 2 = pqueue->size
            if (child < pqueue->size && pqueue->elements[child] > pqueue->elements[child + 1])
                child++;
             
            if (lastElement < pqueue->elements[child])
                break;
            else
                pqueue->elements[i] = pqueue->elements[child]; 
        }
        pqueue->elements[i] = lastElement;
         
        return minElement; // 返回被删除的元素


    查找

    直接返回队首就可以了

     return pqueue->elements[1];



    建堆:

    第一种方法:建立一个空堆,然后将一组数据依次做插入操作,时间复杂度O(NlogN)

    pqueue = initialize(n * 2);
    for (int i = 0; i < n; i++)
        insert(arr[i], pqueue);


    第二种方法:先将数组转化为堆,再进行调整,时间复杂度为O(N)

     for (i = 1; i <= n; i++)
            elements[i] = arr[i - 1];
        elements[0] = SentinelElement;//数组转换为堆
         
        for (i = n / 2; i > 0; i--)
            adjust(elements, n + 1, i);//从最后一个非叶子节点开始,做调整处理


    void adjust(int *arr, int len, int i)
    {
        int n = len - 1;
        int tmp;
    if(i * 2 >n)                       //叶子节点跳出
    return;
        if (i * 2 == n && arr[i] > arr[n]) // 只有左儿子的节点,并且左儿子比本节点的值要小,交换
        {
            tmp = arr[i];
            arr[i] = arr[n];
            arr[n] = tmp;
        }
        else // 有两个儿子的节点
        {
            if (arr[i * 2] > arr[i * 2 + 1]) // 右儿子较小
            {
                if (arr[i] > arr[i * 2 + 1]) // 如果本节点比右儿子大,交换
                {
                    tmp = arr[i];
                    arr[i] = arr[i * 2 + 1];
                    arr[i * 2 + 1] = tmp;
    adjust(arr, len, i * 2 + 1);
                }
            }
            else // 左儿子较小
            {
                if (arr[i] > arr[i * 2]) // 如果本节点比左儿子大,交换
                {
                    tmp = arr[i];
                    arr[i] = arr[i * 2];
                    arr[i * 2] = tmp;
    adjust(arr, len, i * 2 );
                }
            }
        }
    }



    再说一下堆排序,其实可以把他当作是原堆所有值都出队就好了。时间复杂度O(NlogN)

    for (i = 1; i <= n; i++)
    elements[i] = deleteMin(pqueue);
    elements[0] = SentinelElement;





    下面给出完整代码


    MinHeap.h  头文件


    #ifndef DataStructures_MinHeap_h
    #define DataStructures_MinHeap_h
    
    struct MinHeap;
    typedef struct MinHeap * MinPriorityQueue;
    typedef int ElementType;
    
    // 初始化堆
    MinPriorityQueue initialize(int maxElements);
    
    // 销毁堆
    void destroy(MinPriorityQueue pqueue);
    
    // 清空堆中的元素
    void makeEmpty(MinPriorityQueue pqueue);
    
    // 插入操作
    void insert(ElementType x, MinPriorityQueue pqueue);
    
    // 删除最小者操作,返回被删除的堆顶元素
    ElementType deleteMin(MinPriorityQueue pqueue);
    
    // 查找最小者(堆顶)
    ElementType findMin(MinPriorityQueue pqueue);
    
    // 判断堆是否为空
    int isEmpty(MinPriorityQueue pqueue);
    
    // 判断堆是否满
    int isFull(MinPriorityQueue pqueue);
    
    // 通过一个数组来建堆,相当于将用数组实现的无序树转换为堆序树——插入法
    MinPriorityQueue buildHeap_insert(int *arr, int n);
    // 通过一个数组来建堆,相当于将用数组实现的无序树转换为堆序树——调整法
    MinPriorityQueue buildHeap_percolate(int *arr, int n);
    
    //堆排序
    MinPriorityQueue buildHeap_sort(MinPriorityQueue pqueue);
    
    // 打印堆
    void printMinPriorityQueue(MinPriorityQueue pqueue);
    
    #endif


    MinHeap.cpp  实现函数


    #include <stdio.h>
    #include <stdlib.h>
    #include "MinHeap.h"
     
    /* 标记节点,类似于链表中的表头节点
     * 该值必须小于所有最小堆中的元素,设其值为-1
     */
    #define SentinelElement -1
     
    /*
     * 使用数组实现堆
     *
     * capacity 数组的最大容量
     * size     数组的长度
     * elements 堆中的元素存放的数组
     */
    struct MinHeap
    {
        int capacity;
        int size;
        ElementType *elements; // 堆的元素个数为size,实际上用来存储的数组的长度为size + 1,还包括一个sentinel元素
    };
     
    void PQueueNULLWarning()
    {
        printf("Warning: Minimum Priority Queue is NULL");
    }
     
    void outOfSpaceFatalError()
    {
        printf("Fatal Error: Out of space");
        abort();
    }
     
    MinPriorityQueue initialize(int maxElements)
    {
        MinPriorityQueue pqueue;
         
        if (maxElements <= 0)
        {
            printf("Fail to initialize: maxElements <= 0");
            return NULL;
        }
         
        pqueue = (MinPriorityQueue)malloc(sizeof(struct MinHeap));
        if (pqueue == NULL)
            outOfSpaceFatalError();
         
        // 数组的第0个元素是个sentinel标记节点,计入数组容量中,但不计入capcaity或size中
        pqueue->size = 0;
        pqueue->capacity = maxElements;
        pqueue->elements =  (ElementType *)malloc(sizeof(ElementType) * (pqueue->capacity + 1));
        if (pqueue->elements == NULL)
            outOfSpaceFatalError();
        else
            pqueue->elements[0] = SentinelElement;
         
        return pqueue;
    }
     
    void destroy(MinPriorityQueue pqueue)
    {
        if (pqueue != NULL)
        {
            // 在GNU99标准中,free(NULL)什么都不做直接返回,所以不用判断pqueue->elements是否为NULL
            free(pqueue->elements);
            free(pqueue);
        }
    }
     
    void makeEmpty(MinPriorityQueue pqueue)
    {
        if (pqueue != NULL)
            pqueue->size = 0;
        else
            PQueueNULLWarning();
    }
     
     
    /*
     * 插入的时间复杂度为O(log N),N为最小堆中的元素个数
     */
    void insert(ElementType x, MinPriorityQueue pqueue)
    {
        if (pqueue == NULL)
            PQueueNULLWarning();
         
        if (isFull(pqueue))
        {
            printf("Fail to insert: Priority Queue is Full");
            return;
        }
        else
        {
            int i;
             
            for (i = ++pqueue->size; x < pqueue->elements[i / 2]; i /= 2)
                pqueue->elements[i] = pqueue->elements[i / 2]; //上浮
            pqueue->elements[i] = x;
        }
    }
     
    /*
     * 删除操作的平均时间为O(log N)
     */
    ElementType deleteMin(MinPriorityQueue pqueue)
    {
        if (pqueue == NULL)
        {
            PQueueNULLWarning();
            return SentinelElement;
        }
         
        if (isEmpty(pqueue))
        {
            printf("Fail to delete: Priority Queue is Empty");
            return SentinelElement;
        }
         
        int i, child;
        ElementType minElement, lastElement;
         
        // 注意对节点进行下沉操作时,要判断该节点是有两个儿子还是一个儿子
        minElement = pqueue->elements[1];
        lastElement = pqueue->elements[pqueue->size--];
        for (i = 1; i * 2 <= pqueue->size; i = child)
        {
            child = i * 2;
             
            // 节点i只有一个儿子时必有i * 2 = pqueue->size
            if (child < pqueue->size && pqueue->elements[child] > pqueue->elements[child + 1])
                child++;
             
            if (lastElement < pqueue->elements[child])
                break;
            else
                pqueue->elements[i] = pqueue->elements[child]; 
        }
        pqueue->elements[i] = lastElement;
         
        return minElement; // 返回被删除的元素
    }
     
    /*
     * 执行时间:O(1)
     */
    ElementType findMin(MinPriorityQueue pqueue)
    {
        if (pqueue == NULL)
        {
            PQueueNULLWarning();
            return SentinelElement;
        }
        else
            return pqueue->elements[1];
    }
     
    int isEmpty(MinPriorityQueue pqueue)
    {
        if (pqueue == NULL)
        {
            PQueueNULLWarning();
            return -1;
        }
        else
            return (pqueue->size == 0);
    }
     
    int isFull(MinPriorityQueue pqueue)
    {
        if (pqueue == NULL)
        {
            PQueueNULLWarning();
            return -1;
        }
        else
            return (pqueue->size == pqueue->capacity);
    }
     
    void adjust(int *arr, int len, int i)
    {
        int n = len - 1;
        int tmp;
    
    	if(i * 2 >n)                       //叶子节点跳出
    		return;
        if (i * 2 == n && arr[i] > arr[n]) // 只有左儿子的节点,并且左儿子比本节点的值要小,交换
        {
            tmp = arr[i];
            arr[i] = arr[n];
            arr[n] = tmp;
        }
        else // 有两个儿子的节点
        {
            if (arr[i * 2] > arr[i * 2 + 1]) // 右儿子较小
            {
                if (arr[i] > arr[i * 2 + 1]) // 如果本节点比右儿子大,交换
                {
                    tmp = arr[i];
                    arr[i] = arr[i * 2 + 1];
                    arr[i * 2 + 1] = tmp;
    				adjust(arr, len, i * 2 + 1);
                }
            }
            else // 左儿子较小
            {
                if (arr[i] > arr[i * 2]) // 如果本节点比左儿子大,交换
                {
                    tmp = arr[i];
                    arr[i] = arr[i * 2];
                    arr[i * 2] = tmp;
    				adjust(arr, len, i * 2 );
                }
            }
        }
    }
     
    /*先将数组转化为堆,再进行调整,时间复杂度为O(N)
    
    正确的证明方法应当如下:
    具有n个元素的平衡二叉树,树高为㏒n,我们设这个变量为h。
    最下层非叶节点的元素,只需做一次线性运算便可以确定大根,而这一层具有2^(h-1)个元素,我们假定O(1)=1,那么这一层元素所需时间为2^(h-1) × 1。
    由于是bottom-top建立堆,因此在调整上层元素的时候,并不需要同下层所有元素做比较,只需要同其中之一分支作比较,而作比较次数则是树的高度减去当前节点的高度。因此,第x层元素的计算量为2^(x-1) × (h-x)。
    又以上通项公式可得知,构造树高为h的二叉堆的精确时间复杂度为: 
    S = 2^(h-1) × 1 + 2^(h-2) × 2 + …… +1 × (h-1) ①
    通过观察第四步得出的公式可知,该求和公式为等差数列和等比数列的乘积,因此用错位想减发求解,给公式左右两侧同时乘以2,可知: 
    2S = 2^h × 1 + 2^(h-1) × 2+ …… +2 × (h-1) ②
    
    用②减去①可知: S =2^h × 1 - h +1 ③
    
    将h = ㏒n 带入③,得出如下结论:
    
    S = n - ㏒n +1 = O(n)
    
    */
    
    MinPriorityQueue buildHeap_percolate(int *arr, int n)
    {
        if (arr == NULL)
        {
            printf("Error: Array is NULL");
            return NULL;
        }
         
        MinPriorityQueue pqueue;
        pqueue = ( MinPriorityQueue)malloc(sizeof(struct MinHeap));
         
        if (pqueue == NULL)
            outOfSpaceFatalError();
        ElementType *elements = ( ElementType *)malloc(sizeof(ElementType) * (n + 1));
        if (elements == NULL)
            outOfSpaceFatalError();
         
        int i;
        for (i = 1; i <= n; i++)
            elements[i] = arr[i - 1];
        elements[0] = SentinelElement;
         
        for (i = n / 2; i > 0; i--)
            adjust(elements, n + 1, i);
         
        pqueue->elements = elements;
        pqueue->size = n;
        pqueue->capacity = n * 2;
         
        return pqueue;
    }
     
    /*
     * 通过n次插入元素建立堆,由于每次插入的平均执行时间为O(logN),所以建堆平均时间为O(NlogN)
     */
    MinPriorityQueue buildHeap_insert(int *arr, int n)
    {
        MinPriorityQueue pqueue;
         
        if (arr == NULL)
        {
            printf("Array is NULL, fail to build heap");
            return NULL;
        }
         
        pqueue = initialize(n * 2);
        for (int i = 0; i < n; i++)
            insert(arr[i], pqueue);
         
        return pqueue;
    }
     
    /*
     *通过n次出队操作把其值输出到另一个堆里,时间复杂度O(NlogN)
     */
    MinPriorityQueue buildHeap_sort(MinPriorityQueue pqueue)
    {
    	MinPriorityQueue pqueuetemp;
    	if (pqueue == NULL)
    	{
    		PQueueNULLWarning();
    	}
    
    
    	int n=pqueue->size;
    
    	pqueuetemp = ( MinPriorityQueue)malloc(sizeof(struct MinHeap));
    
    	if (pqueuetemp == NULL)
    		outOfSpaceFatalError();
    	ElementType *elements = ( ElementType *)malloc(sizeof(ElementType) * (n + 1));
    	if (elements == NULL)
    		outOfSpaceFatalError();
    
    	int i;
    	for (i = 1; i <= n; i++)
    		elements[i] = deleteMin(pqueue);
    	elements[0] = SentinelElement;
    
    	pqueuetemp->elements = elements;
    	pqueuetemp->size = n;
    	pqueuetemp->capacity = n * 2;
    
    
    	return pqueuetemp;
    
    }
    
    
    void printMinPriorityQueue(MinPriorityQueue pqueue)
    {
        if (pqueue == NULL)
        {
            PQueueNULLWarning();
            return;
        }
         
        if (pqueue->elements == NULL)
        {
            printf("Fail to print: Elements of priority queue is NULL");
            return;
        }
         
        if (isEmpty(pqueue))
        {
            printf("Empty Prioirty Queue\n");
            return;
        }
         
        printf("Priority Queue\n");
        for (int i = 1; i <= pqueue->size; i++)
            printf("Element[%d] = %d\n", i, pqueue->elements[i]);
        printf("\n");
    }


    main.cpp   主函数调用

    #include <stdio.h>
    #include <stdlib.h>
    #include "MinHeap.h"
    
    int main(int argc, const char * argv[])
    {
    	int a[5] = {5, 4, 3, 2, 1};
    	MinPriorityQueue pqueue_ins = buildHeap_insert(a, 5);
    	printMinPriorityQueue(pqueue_ins);
    	MinPriorityQueue pqueue_per = buildHeap_percolate(a, 5);
    	printMinPriorityQueue(pqueue_per);
    	MinPriorityQueue pqueue_sort=buildHeap_sort(pqueue_ins);
    	printMinPriorityQueue(pqueue_sort);
    /*
    	deleteMin(pqueue_ins);
    	printMinPriorityQueue(pqueue_ins);
    	deleteMin(pqueue_ins);
    	printMinPriorityQueue(pqueue_ins);
    	insert(9, pqueue_ins);
    	printMinPriorityQueue(pqueue_ins);
    	insert(1, pqueue_ins);
    	printMinPriorityQueue(pqueue_ins);
    	*/
    	system("pause");
    	return 0;
    }
    
    
    /*转载与http://www.2cto.com/kf/201404/293694.html*/


    注:代码部分转载与http://www.2cto.com/kf/201404/293694.html,并对其代码做了一些修正与改进。





    展开全文
  • 结点结构   二叉树的链表中的结点至少包含3个域:数据域和左、右指针域 代码实现 main.cpp #include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define...

    结构

      二叉树的链表中的结点至少包含3个域:数据域和左、右指针域。

    结点结构 二叉链表

    代码实现

    main.cpp

    #include<stdio.h>
    #include<stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW 3
    #define UNDERFLOW 4
    
    typedef int Status;  //Status是函数的类型,其值是函数结果状态代码,如OK等
    typedef int Boolean; //Boolean是布尔类型,其值是TRUE或FALSE
    typedef char TElemType;
    
    //-----二叉树的二叉链表存储表示-----
    typedef struct BiTNode{
    	TElemType	   data;
    	struct BiTNode *lchild, *rchild;	//左右孩子指针
    }BiTNode, *BiTree;
    
    //-----基本操作的函数原型说明-----
    Status CreateBiTree(BiTree &T){
    	//按先序次序输入二叉树中的结点的值(一个字符),空格字符表示空树,
    	//构造二叉链表表示的树T
    	TElemType ch;
    	scanf("%c", &ch);
    	getchar();
    	if(ch == ' '){
    		T = NULL;
    	} else {
    		if( !(T=(BiTree)malloc(sizeof(BiTNode))) ){
    			exit(OVERFLOW);
    		};
    		T->data = ch;					//生成根结点
    		printf("输入%c的左子树:", ch);
    		CreateBiTree(T->lchild);		//构造左子树
    		printf("输入%c的右子树:", ch);
    		CreateBiTree(T->rchild);		//构造右子树
    	}
    	return OK;
    }
    //先序遍历二叉树T
    Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
    	//采用二叉链表表示存储结构,Visit是对结点操作的应用函数。
    	//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
    	//一旦visit()失败,则操作失败。
    	if(T){
    		if(Visit(T->data) == OK){
    			if(PreOrderTraverse(T->lchild, Visit) == OK){
    				if(PreOrderTraverse(T->rchild, Visit) == OK){
    					return OK;
    				}
    			}
    		}
    		return ERROR;
    	}else {
    		return OK;
    	}
    }
    //中序遍历二叉树T
    Status InOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
    	//采用二叉链表表示存储结构,Visit是对结点操作的应用函数。
    	//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
    	//一旦visit()失败,则操作失败。
    	if(T){
    		if(PreOrderTraverse(T->lchild, Visit) == OK){
    			if(Visit(T->data) == OK){
    				if(PreOrderTraverse(T->rchild, Visit) == OK){
    					return OK;
    				}
    			}
    		}
    		return ERROR;
    	}else {
    		return OK;
    	}
    }
    //后序遍历二叉树T
    Status PosOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
    	//采用二叉链表表示存储结构,Visit是对结点操作的应用函数。
    	//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
    	//一旦visit()失败,则操作失败。
    	if(T){
    		if(PreOrderTraverse(T->lchild, Visit) == OK){
    			if(PreOrderTraverse(T->rchild, Visit) == OK){
    				if(Visit(T->data) == OK){
    					return OK;
    				}
    			}
    		}
    		return ERROR;
    	}else {
    		return OK;
    	}
    }
    //层序遍历二叉树T
    Status LevelOrderTraverse(BiTree T, Status (* Visit)(TElemType e)){
    	//采用二叉链表表示存储结构,Visit是对结点操作的应用函数。
    	//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次。
    	//一旦visit()失败,则操作失败。
    	BiTree p = T;
    	return OK;
    }
    //求树的深度
    Status TreeDeep(BiTree T){
    	int deep=0;
    	if(T){
    		int leftDeep = TreeDeep(T->lchild);
    		int rightDeep = TreeDeep(T->rchild);
    		deep = leftDeep>=rightDeep ? leftDeep+1 : rightDeep+1;
    	}
    	return deep;
    }
    //求树叶的个数
    Status LeafCount(BiTree T, int &num){
    	if(T)
    	{
    		if(T->lchild==NULL && T->rchild==NULL){
    			num++;
    		}
    		LeafCount(T->lchild,num);
    		LeafCount(T->rchild,num);
    	}
    	return num;
    }
    //最简单的visit函数
    //调用实例:PreOrderTraverse(T, PrintElement);
    Status PrintElement(TElemType e){	//输出元素e的值
    	printf("%c",e);
    	return OK;
    }
    
    int main(){
    	BiTree T;
    	int    num = 0;
    	printf("输入树根:");
    	CreateBiTree(T);
    	printf("先序遍历:\n");
    	PreOrderTraverse(T, PrintElement);
    	printf("\n");
    	printf("中序遍历:\n");
    	InOrderTraverse(T, PrintElement);
    	printf("\n");
    	printf("后序遍历:\n");
    	PosOrderTraverse(T, PrintElement);
    	printf("\n");
    	printf("层次遍历:\n");
    	LevelOrderTraverse(T, PrintElement);
    	printf("\n");
    	printf("求树的深度:\n");
    	printf("%d\n",TreeDeep(T));
    	printf("求树叶的个数:\n");
    	printf("%d\n",LeafCount(T, num));
    	return 0;
    }
    

    案例

    输入 输出

    参考文献

    [1] 严蔚敏,吴伟民. 数据结构(C语言版)[M]. 清华大学出版社.
    [2] 黑面宝宝. 二叉链表的存储结构和基本操作(各种遍历、求树深度、求树叶个数)[EB/OL]. https://blog.csdn.net/ztp_bb/article/details/52940161

    展开全文
  • 数据结构 C描述】设计一个算法,用于检测给定的字符串是否为对称串。 所谓对称串,就是字符串从左往右读和从右往左读的序列一样。 例如: abccba是对称串。 abcabc不是对称串。 //main.cpp #include &lt;...

    【数据结构 C描述】设计一个算法,用于检测给定的字符串是否为对称串。

    在这里插入图片描述

    所谓对称串,就是字符串从左往右读和从右往左读的序列一样。
    例如:
    abccba是对称串。
    abcabc不是对称串。

    //main.cpp
    #include <iostream>
    #include <malloc.h>
    #include <stdlib.h>
    #include "SqStack.h"
    #include "LinkStack.h"
    using namespace std;
    
    int main()
    {
    	char arr[50];
    	cout << "\n请出入一个对称串:";
    	cin >> arr;
    	cout << "\n\n判断该串是否为对称串的情况:";
    	bool isSymmetryString(char a[]);
    	isSymmetryString(arr);
    
    	system("pause");
    	cout << "\n";
    	return 0;
    }
    
    
    /*
    设计一个算法,用于检测给定的字符串是否为对称串。
    */
    //检测是否为对称串的函数
    bool isSymmetryString(char a[]) {
    	SqStack *S;
    	InitStack(S);
    	ElemType e;//存储元素的变量
    	for (int i = 0; a[i] != '\0'; i++) {
    		Push(S, a[i]);
    	}
    	for (int i = 0; a[i] != '\0'; i++) {
    		Pop(S, e);
    		//将数组中的元素与出栈的元素对比,栈中的元素后进先出
    		if (a[i] != e) {
    			cout << "\n该串不是对称串。\n";
    			DestoryStack(S);
    			return false;
    		}
    	}
    	cout << "\n该串是对称串。\n" << endl;
    	DestoryStack(S);
    	return true;
    }
    
    

    在这里插入图片描述

    展开全文
  • 数据结构 C描述】使用顺序栈编制一个满足下列要求的程序:对于输入的任意一个非负十进制数,打印输出与其等值的二进制数。 //main.cpp #include &amp;lt;iostream&amp;gt; #include &amp;lt;malloc...
  • //假设顶点的数据类型为整型 typedef int ArcType; //假设边的权值类型为整型 typedef struct { VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前点数和边...
  • a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s j 则字符串“encrypt”被加密为“tkzwsdf” 要求:设计程序将输入的文本串进行加密后输出,然后进行解密...
  • 编制一个病人看病模拟程序。 在病人排队过程中,主要重复两件事: 1.病人到达诊室,将病历本交给护士,排到等待队列中候诊。 2.护士从等待队列中取出下一位病人的病历,该病人进入诊室就诊。 ...
  • 这是我的作业题,作业写完后...假设:有两个整数集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即:线性表中的数据元素即为集合中的成员。(A/B为纯集合) 要求:一个新的集合A=A∪B,A仍然为纯集合,线性表采用链...
  • C数据结构

    千次阅读 2016-12-20 20:17:54
     在前几篇的博文中主要讲述的是链式存储这种数据结构,它们的用途非常广泛,但是在实际的应用中,还存在着另一种非常重要的数据结构,它就是树。树的结构示意图如下所示:  上图就是一种数据结构----树,...
  • 基于C实现数据结构之二叉排序树

    万次阅读 2018-09-17 12:09:19
    基于C实现数据结构之二叉排序树 树表查找 树表查找是对树形存储结构所做的查找。树形存储结构是一种多链表,表中每个节点包含有一个数据域和多个指针域。每个指针指向一个后继节点,树形存储结构和树形结构时完全...
  • C/C++泛型编程实现数据结构之栈

    万次阅读 2018-09-14 10:37:05
    C/C++泛型编程实现数据结构之栈 栈是访问受限的线性表,遵循了后进先出的原则,只允许在栈顶进行操作。这里栈是一种数据结构。但是我们仍然可以对其进行存储结构上的划分。 在这里我们会把它分成顺序存储结构和...
  • c/c++ 数据结构与算法

    千次阅读 多人点赞 2019-02-14 11:13:44
    参考;... 程序设计 = 数据结构 + 算法 1.数据结构 数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。... 因此,我们无法孤立数据结构来讲算法,也无法孤立算法来讲数据结构数据结构...
  • C/C++泛型编程实现数据结构之队列

    万次阅读 2018-09-17 08:39:46
    C/C++泛型编程实现数据结构之队列 早在曾经一篇博文中,我曾介绍过顺序存储和链式存储的区别和好处,博文传送门:https://blog.csdn.net/qq_27180763/article/details/82683029 本章将讲诉: 1. 队列的逻辑结构...
  • Objective-C底层数据结构

    千次阅读 2014-09-25 20:21:23
    Objective-C底层数据结构 Objective-C底层数据结构 类的数据结构 Class(指针) typedef struct objc_class *Class; /* 这是由编译器为每个类产生的数据结构,这个结构定义了一个类.这个结构是...
  • C/C++泛型编程实现数据结构之线性表

    万次阅读 2018-09-12 09:52:28
    C/C++泛型编程实现数据结构之线性表 泛型编程与面向对象编程的目标相同,即使重用代码和抽象通用概念的技术更加简单。但是面向对象编程强调编程的数据方面,泛型编程强调的是独立于特定数据类型。侧重点不同。 ...
  • C/C++泛型编程实现数据结构之广义表

    万次阅读 2018-09-18 09:23:58
    C/C++泛型编程实现数据结构之广义表 广义表是线性表的推广,又称列表。线性表的元素只限于原子项,即每个数据元素只能是一个数或一个记录,如果放松对线性表元素的这种限制,允许他们自身具有结构,那么就产生了广义...
  • c++之数据结构

    万次阅读 2018-02-08 18:02:13
    C++ 数据结构C/C++ 数组允许定义可存储相同类型数据项的变量,但是结构是 C++ 中另一种用户自定义的可用的数据类型,它允许您存储不同类型的数据项。结构用于表示一条记录,假设您想要跟踪图书馆中书本的动态,您...
  • 整个视频打包下载地址:史上最全的数据结构视频教程系列分享之《小甲鱼全套教程之C C++数据结构系列教程》,转载请保留出处和链接! 更多优秀资源请访问:我是码农 本人看过,感觉蛮好,与一般的大学视频有较大的...
  • 数据结构

    千次阅读 2017-09-07 22:51:00
    熟记数据结构基础知识: http://www.jianshu.com/nb/6355905 http://www.jianshu.com/p/230e6fde9c75 http://www.jianshu.com/p/42f81846c0fb 简书: 数据结构是以某种形式将数据组织在一起的集合,...
  • C/C++实现数据结构之图的遍历算法

    万次阅读 2018-10-08 09:38:37
    图形结构是一种在生活以及工业中很常用的数据结构。有着关系明确、运算快捷的优点。但是学习难、入门起点高,对数学能力有很高的要求。 图的遍历 图的遍历和树的遍历类似。首先这里就不再赘述图的逻辑结构了。有向图...
  • 【大总结1】数据结构与传统算法总结

    万次阅读 多人点赞 2018-12-18 13:28:38
    由于时间和水平有限,肯定有错误或者写得不好的地方 欢迎在文章下评论指出。 ...c/c++:实现基础数据结构和算法 java:实现较复杂数据结构 一、概述 c语言知识体系 算法体系参考 ...
  • 数据结构数据结构纠错本

    千次阅读 多人点赞 2018-09-15 11:48:34
    数据结构数据结构纠错本 标签(空格分隔):【考研纠错本】 考研数据结构纠错本 考研数据结构纠错本 1. 数据结构绪论 我的微信公众号 1. 数据结构绪论 对数据...
  • 数据结构,一门数据处理的艺术,精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美,在为信息技术打下坚实地基的同时,也令无数开发者和探索者为之着迷。 也因如此,它作为博主大二上学期最重要的...
  • 数据结构基本定义 C/ C++

    千次阅读 2016-11-18 18:07:48
    一、何为数据结构数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及它们之间的关系和操作等相关问题的学科。 基本概念与术语: 数据 何为数据:它是描述客观事物的符号,是计算机中可以...
  • 数据结构——什么是数据结构

    千次阅读 多人点赞 2018-01-23 18:27:01
    什么是数据结构 1.数据结构的有关定义  (1)数据结构:是带有结构数据元素的集合  (2)数据:是客观事物的数值、字符以及能输入机器且能被处理的各种符号的集合  编译 链接  源程序(.c)--------->...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 70,820
精华内容 28,328
关键字:

数据结构c

数据结构 订阅