《C语言程序设计》笔记p10
typedef 类型别名
语法
typedef 旧类型 新类型名;
二叉树层次遍历综合练习：
五个文件:
- main.c 主程序文件
- myqueue.c 队列实现文件
- myqueue.h 队列头文件
- bin_tree.c 二叉树实现文件
- bin_tree.h 二叉树头文件
编译
gcc -o myprog main.c bin_tree.c myqueue.c
myqueue.h
#ifndef __MYQUEUE_H__
#define __MYQUEUE_H__
#include "bin_tree.h"typedef struct bnode *data_t;
struct queue {data_t data[100]; // 用来保存数据int tail; // 数据个数。
};
// 1. 初始化队列
void queue_init(struct queue * pq);
// 2. 队列空判断, 空返回1， 否则返回0
int queue_is_empty(struct queue * pq);
// 3. 队列满判断, 满返回1， 否则返回0
int queue_is_full(struct queue * pq);
// 4. 入队, 成功返回1 ,失败返回0
int queue_enqueue(struct queue *pq, data_t value);
// 5. 出队, 成功返回1 ,失败返回0
int queue_dequeue(struct queue *pq, data_t *pvalue);
// 6. 队列内数据元素的个数
int queue_get_data_count(struct queue*pq);
// 7. 销毁队列
void queue_destroy(struct queue*pq); #endif
myqueue.c
// 1. 初始化队列
// 2. 队列空判断
// 3. 队列满判断
// 4. 入队
// 5. 出对
// 6. 对列内数据元素的个数
// 7. 销毁队列
#include <stdio.h>
#include "myqueue.h"// 1. 初始化队列
void queue_init(struct queue * pq) {pq->tail = 0;
}
// 2. 队列空判断, 空返回1， 否则返回0
int queue_is_empty(struct queue * pq) {return 0 == pq->tail;
}
// 3. 队列满判断, 满返回1， 否则返回0
int queue_is_full(struct queue * pq) {return sizeof(pq->data)/sizeof(pq->data[0])==pq->tail;
}
// 4. 入队, 成功返回1 ,失败返回0
int queue_enqueue(struct queue *pq, data_t value) {if (queue_is_full(pq))return 0;pq->data[pq->tail] = value; pq->tail ++;return 1;
}
// 5. 出队, 成功返回1 ,失败返回0
int queue_dequeue(struct queue *pq, data_t *pvalue) {if (queue_is_empty(pq))return 0;*pvalue = pq->data[0];// 向前移动数据for (int i = 0; i < pq->tail -1; i++) {pq->data[i] = pq->data[i+1];}pq->tail--;return 1;
}
// 6. 队列内数据元素的个数
int queue_get_data_count(struct queue*pq) {return pq->tail;
}
// 7. 销毁队列
void queue_destroy(struct queue*pq) {pq->tail = 0;
}bin_tree.h
#ifndef __BIN_TREE_H__
#define __BIN_TREE_H__// 二叉树的节点结构
struct bnode {int data;struct bnode * left;struct bnode * right;
};// 用于定义一棵二叉树
struct bin_tree {struct bnode * root;
};// 创建二叉树的节点，失败返回NULL；
struct bnode * create_node(int value); // 将 new_node 节点挂在 root 指针上。
void insert_node(struct bnode ** proot, struct bnode*new_node);// 递归实现节点的删除.找到并删除返回1，失败返回0
int remove_node(struct bnode ** proot, int value);
// 递归实现删除子树的节点,将指向此子树的指针置空
void free_sub_tree(struct bnode ** proot);
// 先序遍历(递归实现:根、左、右);
void preorder(struct bnode *root);
// 5. 中序遍历(递归实现:左、根、右);
void inorder(struct bnode *root);
// 6. 后序遍历(递归实现:左、右、根);
void postorder(struct bnode *root); // ---------------------------------------------
// 1. 二叉树初始化
void tree_init(struct bin_tree * atree);
// 2. 插入数据,成功返回1，失败返回0
int tree_insert(struct bin_tree * atree, int value);
// 3. 查找数据。根据值查找制定的节点，如果找不到返回NULL.
struct bnode * tree_search(struct bin_tree * atree, int value);
// 4. 先序遍历
void tree_preorder(struct bin_tree *atree);
// 5. 中序遍历
void tree_inorder(struct bin_tree *atree);
// 6. 后序遍历
void tree_postorder(struct bin_tree *atree);
// 6.1 层次遍历
void tree_levelorder(struct bin_tree *atree);
// 7. 删除数据,如果成功删除则返回1，失败返回0
int tree_delete(struct bin_tree *atree, int value);
// 8. 二叉树销毁
void tree_destroy(struct bin_tree *atree);
#endif
bin_tree.c
// 二叉排序树
#include <stdio.h>
#include <stdlib.h>
#include "bin_tree.h"
#include "myqueue.h"// 创建二叉树的节点，失败返回NULL；
struct bnode * create_node(int value) {struct bnode * temp = (struct bnode *)malloc(sizeof(struct bnode));if (NULL == temp)return NULL;temp->data = value;temp->left = temp->right = NULL;return temp;
}// 将 new_node 节点挂在 root 指针上。
void insert_node(struct bnode ** proot, struct bnode*new_node)
{if (NULL == *proot) {*proot = new_node;return;}struct bnode * temp_root = *proot;if (new_node->data < temp_root->data) {// 插入左子树insert_node(&temp_root->left, new_node);} else {// 插入右子树insert_node(&temp_root->right, new_node);}}
// 递归实现节点的删除.找到并删除返回1，失败返回0
int remove_node(struct bnode ** proot, int value) {struct bnode *temp = *proot;if (NULL == temp)return 0;if (temp->data != value) { // 进入下一层删除if (value < temp->data) return remove_node(&temp->left, value);elsereturn remove_node(&temp->right, value);}// 走到此处,temp->data一定等于value,删除temp 指向的节点// 左右都为空if (temp->left == NULL && temp->right == NULL) {*proot = NULL;free(temp);return 1;}if (temp->left != NULL && temp->right == NULL) {*proot = temp->left;free(temp);return 1;}if (temp->left == NULL && temp->right != NULL) {*proot = temp->right;free(temp);return 1;}// 左右都不为空 将右子树插入左子树，insert_node(&temp->left, temp->right);*proot = temp->left;free(temp);return 1;}
// 递归实现删除子树的节点,将指向此子树的指针置空
void free_sub_tree(struct bnode ** proot) {struct bnode * temp = *proot;if (NULL == temp)return ;// 删除左子树free_sub_tree(&temp->left);// 删除右子树free_sub_tree(&temp->right);// 删除当前节点free(temp);// 将指向此节点的指针指控*proot = NULL;
}
// 先序遍历(递归实现:根、左、右);
void preorder(struct bnode *root) {if (NULL == root)return;printf("%d ", root->data);preorder(root->left);preorder(root->right);}
// 5. 中序遍历(递归实现:左、根、右);
void inorder(struct bnode *root) {if (NULL == root)return;inorder(root->left);printf("%d ", root->data);inorder(root->right);
}
// 6. 后序遍历(递归实现:左、右、根);
void postorder(struct bnode *root) {if (NULL == root)return;postorder(root->left);postorder(root->right);printf("%d ", root->data);
}// ---------------------------------------------
// 1. 二叉树初始化
void tree_init(struct bin_tree * atree) {atree->root = NULL;
}
// 2. 插入数据,成功返回1，失败返回0
int tree_insert(struct bin_tree * atree, int value) {struct bnode *temp = create_node(value);if (NULL == temp)return 0;insert_node(&atree->root, temp);// atree->root = temp;
}
// 3. 查找数据。根据值查找制定的节点，如果找不到返回NULL.
struct bnode * tree_search(struct bin_tree * atree, int value) {struct bnode * temp = atree->root;while (NULL != temp) {if (temp->data == value)return temp;// 找到了if (value < temp->data) temp = temp->left; // 去左子树去找elsetemp = temp->right; // 去右子树去找}return NULL; // 没找到
}
// 4. 先序遍历
void tree_preorder(struct bin_tree *atree) {preorder(atree->root);printf("\n");
}
// 5. 中序遍历
void tree_inorder(struct bin_tree *atree) {inorder(atree->root);printf("\n");
}
// 6. 后序遍历
void tree_postorder(struct bin_tree *atree) {postorder(atree->root);printf("\n");
}
// 6.1 层次遍历
void tree_levelorder(struct bin_tree *atree) {struct bnode * temp = atree->root;if (NULL == temp)return;struct queue q;queue_init(&q);queue_enqueue(&q, temp);while (!queue_is_empty(&q)) {struct bnode * t;queue_dequeue(&q, &t);printf("%d ", t->data);if (t->left) queue_enqueue(&q, t->left);if (t->right) queue_enqueue(&q, t->right);}queue_destroy(&q);
}
// 7. 删除数据,如果成功删除则返回1，失败返回0
int tree_delete(struct bin_tree *atree, int value) {return remove_node(&atree->root, value);
}
// 8. 二叉树销毁
void tree_destroy(struct bin_tree *atree) {free_sub_tree(&atree->root);
}
main.c
// 二叉排序树
#include <stdio.h>
#include "bin_tree.h"int main(int argc, char * argv[]) {struct bin_tree bst;tree_init(&bst);tree_insert(&bst, 8);tree_insert(&bst, 6);tree_insert(&bst, 7);tree_insert(&bst, 10);struct bnode * temp = tree_search(&bst, 15);if (temp)printf("finded %d\n", temp->data);elseprintf("not finded\n");tree_preorder(&bst); //8 6 7 10tree_inorder(&bst); // 6 7 8 10tree_postorder(&bst); //7 6 10 8
// int ret = tree_delete(&bst, 8);
// printf("tree_delete return:%d\n", ret);
// tree_preorder(&bst);
//
// tree_destroy(&bst);
// tree_preorder(&bst);tree_levelorder(&bst);printf("程序退出\n");
}
静态库和动态库
库的概念：
C 语言的库是指一系列函数和全局变量的集合。
静态库(Static Library）
静态库是在编译时被连接到可执行程序中库。
特点：
- 生成的可执行程序大。
- 不依赖库文件。
- 链接阶段会选择性的丢弃库中未使用的函数和全局变量（优化策略）。
文件名：
.a(UNIX/Linux).lib(Windows)
动态库(Shared Library）
在运行行时才被加载
动态库是在运行时加载到可执行程序中库。
特点：多个应用程序可以共用。节省内存。
文件名：
.so(UNIX/Linux).dll(Windows)
制作静态库 libdemo.a
gcc -c a.c
gcc -c b.c
ar -rcs -o libdemo.a a.o b.o
ar 选项
| 选项 | 说明 |
|---|---|
-r | 替换 |
-c | 创建库 |
-s | 加入链接符号 |
连接到可执行程序。
gcc -o myprog myprog.c -L. -ldemo
./myprog
gcc 选项
| 选项 | 说明 |
|---|---|
-L<路径> | 库所在的路径 |
-l<库名> | 对应 lib<库名>.a或lib<库名>.so |
制作动态库 libdemo.so
生成和位置无关的目标文件 a.o 和 b.o
gcc -fPIC -c a.c b.c
gcc 选项
| 选项 | 说明 |
|---|---|
-fPIC | 位置无关选项 |
-shared | 输出共享库 |
将目标文件连接成动态库 libdemo.so
gcc -shared -o libdemo.so a.o b.o
编译可执行程序
gcc -o myprog myprog.c -L. -ldemo
./myprog
将动态库复制到系统路径 `/usr/lib`
sudo cp libdemo.so /usr/lib
注意：
静态库和动态库内一定不要含有 main 函数。