Linux C语言编程基础

二叉树广度优先遍历（链队）

算法：

"head.h"

#ifndef _head_h_
#define _head_h_
#include <stdio.h>
#include <stdlib.h>
//二叉树结构封装
typedef char ElementType;
typedef struct TNode * BinTree;
typedef struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
}* Position;

//队列结构封装
typedef BinTree DataType;
typedef struct Node * PtrToNode ;
typedef struct Node{
    DataType Data;
    PtrToNode Next;
};

typedef struct LQueue{
    PtrToNode Front;
    PtrToNode Rear;
}* Queue;

BinTree CreateBinTree();//建立二叉树
void LevelorderTraversal(BinTree BT);//二叉树广度优先遍历
Queue CreatEmptyQuedeLQueue(void);//建立空队列
void enQueue(Queue LQ, DataType X);//入队操作
void deQueue(Queue LQ);//出队操作
DataType GetFrontData(Queue LQ);//获得队头元素
int GetQLength(Queue LQ);//计算队列长度
#endif // _head_h_

"main.c"

#include "head.h"

int main()
{
    BinTree BT;
    printf("请输入二叉树\n");
    BT = CreateBinTree();
    printf("\n二叉树层序遍历结果为：\n");
    LevelorderTraversal(BT);
    return 0;
}

BinTree.c

#include "head.h"

BinTree CreateBinTree()   //树的建立（依照前序遍历）
{
   char ch;
   BinTree BT;
   ch = getchar();  //输入二叉树数据
   if(ch == ' ')//判断二叉树是否为空
   {
        BT = NULL;
   }
   else
   {
        BT = (BinTree)malloc(sizeof(struct TNode));  //二叉树的生成
        BT -> Data = ch;
        BT -> Left = CreateBinTree();
        BT -> Right = CreateBinTree();
    }
    return BT;
}

void LevelorderTraversal(BinTree BT)//广度优先遍历
{
    Queue LQ;
    BinTree T;

    if(!BT)//二叉树为空树则停止遍历
    {
        return;
    }
    LQ = CreatEmptyQuedeLQueue();
    //将二叉树根节点压入队列开始遍历
    enQueue(LQ, BT);

    int QLength = 0;
    while(1)
    {
        QLength = GetQLength(LQ);
        if (QLength == 0)
        {
            break;
        }
        while (QLength > 0)
        {
             T = GetFrontData(LQ);
             deQueue(LQ);
             printf("%c", T -> Data);
            if(T -> Left)
             {
                 enQueue(LQ, T -> Left);
             }
            if(T -> Right)
             {
                 enQueue(LQ, T -> Right);
             }
             QLength--;
        }
        printf("\n");
    }
}

"LQueue.c"

#include "head.h"

Queue CreatEmptyQuedeLQueue(void)
{
    Queue LQ;
    LQ = (Queue)malloc(sizeof(struct LQueue));
    LQ -> Front = NULL;
    LQ -> Rear = NULL;
    return LQ;
}

void enQueue(Queue LQ, DataType X)
{
    PtrToNode p;
    p = (PtrToNode)malloc(sizeof(struct Node));
    p -> Data = X;
    p -> Next = NULL;
    if(LQ -> Front == NULL)//如果队列为空，则直接进入队头
    {
        LQ -> Front = p;
    }
    else
    {
        LQ -> Rear -> Next = p;
    }
    LQ -> Rear = p;
}

void deQueue(Queue LQ)
{
    PtrToNode p;
    p = LQ -> Front;
    LQ -> Front = p -> Next;
    free(p);
}

DataType GetFrontData(Queue LQ)
{
    return (LQ -> Front -> Data);
}

int GetQLength(Queue LQ)
{
    int counter = 0;
    PtrToNode p;
    p = LQ -> Front;
    while (p)
    {
        counter++;
        p = p -> Next;
    }
    return counter;
}

• 文件名：20191323BinTree_LevelOrderTraversal

• 预处理：gcc -E xx.c -o xx.i

• 编译:gcc -s xx.i xx.s

• 汇编:gcc -c xx.s xx.o

• 链接：

  静态链接：gcc -static xx.c -L[dirname] -l[libname]

  动态链接: gcc xx.c -L[dirname] -l[libname]

  普通链接:gcc xx.o xx.o … -o xx.out

练习过程中产生的部分指令：

产生的文件：

使用指令（部分）：

gcc -Iinclude -c src/BinTree.c -o lib/static/BinTree.o
gcc -Iinclude -c src/LQueue.c -o lib/static/LQueue.o
ar rcs libAll.a BinTree.o LQueue.o
gcc -static -Iinclude src/main.c -Llib/static -lAll -o bin/staticMain.out
./staticMain.out

过程截图：

产生静态库文件：

调用生成程序验证：

使用指令（部分）：

gcc -Iinclude -c -fPIC src/BinTree.c -o lib/dynamic/Bintree.o
gcc -Iinclude -c -fPIC src/LQueue.c -o lib/dynamic/LQueue.o
gcc -shared -o lib/dynamic/libAll.so lib/dynamic/Bintree.o lib/dynamic/LQueue.o
gcc -Iinclude src/main.c -Llib/dynamic -lAll -o bin/dynamicMain.out
export  LD_LIBRARY_PATH=./lib/dynamic/
./bin/dynamicMain.out

过程截图：

产生动态库文件：

调用生成程序验证：

程序代码：

#include <stdio.h>
int add();
int main(void){
  int a,b;
  a = 10;
  b = 20;
  int c;
  c = add(a,b);
  printf("%d",c);
  return 0;
}

int add(int a, int b)
{
  return a + b;
}

设置函数断点、行断点、临时断点、条件断点：

跟踪调试：

查看变量值：

LOT: main.o BinTree.o LQueue.o
    gcc -Iinclude lib/main.o lib/BinTree.o lib/LQueue.o -o bin/$@
BinTree.o: src/BinTree.c include/head.h
    gcc -Iinclude -c src/BinTree.c -o lib/$@
LQueue.o: src/LQueue.c include/head.h
    gcc -Iinclude -c src/LQueue.c -o lib/$@
main.o: src/main.c include/head.h
    gcc -Iinclude -c src/main.c -o lib/$@

clean:
    rm lib/*.o
start:
    bin/LOT

生成程序测试：