- 高级篇
- 数据结构
- 线性表
- 基于数组
- 基于链表
- 链表的经典运用
- 栈
- 栈的简单实现
- 栈的经典运用
- 线性表
- 数据结构
高级篇
数据结构
C语言标准库是没有提供数据结构的，但数据结构是编程中的基础设施，其他编程语言通常都是自带各种数据结构。这里我们简单实现一下，将数据结构的基础知识与C语言语法综合练习一下。
线性表
线性表是最为常用的数据结构之一，其他高级语言也都有提供，也就是Java、Python中的List
基于数组
基于数组的线性表就是一个动态数组，可以自动增长。这里以int类型元素为例，如需实现泛型，可以参考上一篇的void*指针。
头文件arraylist.h
#ifndef _ARRAY_LIST_H_
#define _ARRAY_LIST_H_
// 默认容量
#define DEFAULT_CAPACITY 8
#define OK 0
#define ERROR -1
typedef int Element;
// 声明动态列表的结构体
typedef struct
{
Element *container;
int length; // 列表长度
int capacity; // 底层数组容量
} ArrayList;
// 初始化动态列表
int AL_init(ArrayList *);
// 添加元素
int AL_add(ArrayList*,Element);
// 删除元素
int AL_remove(ArrayList*,int);
// 获取元素
int AL_get(ArrayList*,int,Element*);
#endif
源码arraylist.c
#include "arraylist.h"
#include <stdlib.h>
int AL_init(ArrayList *lst){
if (lst == NULL){
return ERROR;
}
lst->length = 0;
lst->capacity = DEFAULT_CAPACITY;
lst->container = calloc(DEFAULT_CAPACITY,sizeof(int));
if (lst->container == NULL){
return ERROR;
}
return 0;
}
int AL_add(ArrayList *lst,Element element){
if (lst == NULL){
return ERROR;
}
if (lst->length < lst->capacity){
lst->container[lst->length] = element;
lst->length ;
}else{
int newSize = lst->capacity*2;
int *tmp = realloc(lst->container, newSize*sizeof(int));
if (tmp == NULL){
printf("realloc errorn");
return ERROR;
}
lst->capacity = newSize;
lst->container = tmp;
lst->container[lst->length] = element;
lst->length ;
}
return OK;
}
int AL_remove(ArrayList *lst,int position){
if (lst == NULL || position >= lst->length){
return ERROR;
}
for (int i = position; i < lst->length-1; i ){
lst->container[i] = lst->container[i 1];
}
lst->length --;
return OK;
}
int AL_get(ArrayList *lst,int position,Element *element){
if (position < lst->length){
*element = lst->container[position];
return OK;
}else{
return ERROR;
}
}
创建测试代码 test.c
#include <stdio.h>
#include "arraylist.h"
int main(){
ArrayList list;
// 初始化列表
int r = AL_init(&list);
// 循环添加元素
for (int i = 0; i < 20; i ){
AL_add(&list, i*2);
}
// 获取元素并打印
Element e;
for (size_t i = 0; i < list.length; i ){
AL_get(&list,i,&e);
printf("%dn",e);
}
// 删除指定位置的元素
AL_remove(&list,3);
AL_remove(&list,4);
AL_remove(&list,5);
printf("-----------------------*-*-----------------------n");
printf("list size is %dn",list.length);
printf("-----------------------*-*-----------------------n");
// 遍历列表
for (size_t i = 0; i < list.length; i ){
AL_get(&list,i,&e);
printf("%dn",e);
}
}
gcc编译命令: gcc arraylist.c test.c -o test
需要说明的是，基于数组实现线性表，当删除元素时，被删除元素之后的所有元素都需要向前移动。这就像排队一样，如果队伍中一人突然离开，那么其后的所有人都需要向前走一步。
基于链表
除了基于数组实现，还能通过结构体基于链式来实现。所谓链式，就和铁链子一样，一环扣一环。想像一下一群人手拉手站成一排的样子，假如中间有A、B、C三人，A拉着B，B拉着C，这时候如果B想要离开，那么A、C就需要同时松开手，B离开后，A和C的手再拉在一起。
链表
这里我们简单实现一下单向链表的代码，仅做原理演示
头文件linkedlist.h
#ifndef _LINKED_LIST_H_
#define _LINKED_LIST_H_
#define OK 0
#define ERROR -1
typedef int Element;
// 声明节点的结构体
typedef struct _node
{
Element data;
struct _node *next;
} Node;
// 声明链表结构体
typedef struct
{
int length;
Node *link;
} LinkedList;
int LL_init(LinkedList*);
int LL_add(LinkedList *, Element);
int LL_remove(LinkedList*,int);
int LL_get(LinkedList*,int,Element*);
#endif
源文件linkedlist.c
#include "linkedlist.h"
#include <stdlib.h>
// 声明头节点。静态变量，具有当前文件作用域
static Node *head = NULL;
int LL_init(LinkedList *list){
if (list == NULL){
return ERROR;
}
list->link = head;
list->length = 0;
return OK;
}
int LL_add(LinkedList *list, Element e){
if (list == NULL){
return ERROR;
}
Node *node = (Node*)malloc(sizeof(Node));
if (node == NULL){
return ERROR;
}
node->data = e;
node->next = NULL;
if (list->link == NULL){
head = node;
list->link = head;
}else{
list->link->next = node;
list->link = node;
}
list->length ;
return OK;
}
int LL_remove(LinkedList *list,int pos){
if (list == NULL || pos >= list->length){
return ERROR;
}
Node *pre = head , *cur=NULL;
for (int i = 1; i < pos && pre!=NULL; i ) {
pre = pre->next;
}
if (pre == head){
cur = pre;
}else{
cur = pre->next;
}
pre->next = cur->next;
list->length --;
if (cur !=NULL){
free(cur);
}
return OK;
}
int LL_get(LinkedList *list,int pos,Element *e){
if (list == NULL || pos >= list->length){
return ERROR;
}
Node *cur = head;
for (int i = 0; i < pos && cur!=NULL; i ) {
cur = cur->next;
}
*e = cur->data;
return OK;
}
创建测试代码 test.c
#include <stdio.h>
#include "linkedlist.h"
int main(){
LinkedList list;
// 初始化链表
int r = LL_init(&list);
// 循环添加元素
for (int i = 0; i < 10; i ){
LL_add(&list, i);
}
Element e;
for (size_t i = 0; i < list.length; i ){
LL_get(&list,i,&e);
printf("%dn",e);
}
LL_remove(&list,9);
LL_remove(&list,5);
printf("-----------------------*-*-----------------------n");
printf("list size is %dn",list.length);
printf("-----------------------*-*-----------------------n");
for (size_t i = 0; i < list.length; i ){
LL_get(&list,i,&e);
printf("%dn",e);
}
}
基于数组和基于链式的线性表各有特点，这里做一个线性表小结
- 基于数组的线性表，添加、删除元素性能较差，根据以上代码可知，当频繁添加或删除元素时，需要底层动态数组不断的申请或移动内存，而频繁申请堆内存是非常耗费性能的，但是基于数组的线性表，其具有数组的快速索引特点，查询定位元素时速度非常快
- 基于链式的线性表，其查询元素时较为耗费性能，且与查询的元素所处的位置相关。当链表元素越多时，被查询的元素越靠后，其速度越慢。这是因为链表的查询必须从头节点开始遍历，如果被查询的元素正好是最后一个，那么就需要将前面所有节点遍历一次。相对的，链表添加、删除元素的性能非常高，因为它不需要移动内存，只需要将指针指向一个新的元素。
链表的经典运用
先来看一道算法题：
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
题干：
代码语言：javascript复制/**
* 结构体原型
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
}
示例：
输入：(2 -> 4 -> 3) (5 -> 6 -> 4)
输出：7 -> 0 -> 8
实际表示：342 465 = 807
这个题的坑在于没有明确说明不限制非负整数的位数。实际上30位、40位的整数都是可以的。这样一来，我们就不能去考虑常规的加法运算了，因为直接计算几十位的整数加法，明显超出了C语言整型的范围，溢出了。换个角度，其实就是在问的，超大整数如何在计算机中去表示、去处理、去运算。
为了方便测试和验证，我们先自行实现一下题目中的结构体，并填充一些测试数据
代码语言：javascript复制struct ListNode {
int val;
struct ListNode *next;
};
// 初始化头节点
struct ListNode * LL_init(int e){
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
if (node == NULL) return NULL;
node->val = e;
node->next = NULL;
return node;
}
// 添加数字
void LL_add(struct ListNode *list, int e){
while (list->next != NULL) list = list->next;
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
if (node == NULL) return;
node->next = NULL;
node->val = e;
list->next = node;
}
// 测试
int main(){
struct ListNode *list1 = LL_init(2);
LL_add(list1, 4);
LL_add(list1, 3);
struct ListNode *list2 = LL_init(5);
LL_add(list2, 6);
LL_add(list2, 4);
struct ListNode *result = addTwoNumbers(list1,list2);
while (result !=NULL){
printf("%dn",result->val);
result = result->next;
}
return 0;
}
Ok，准备妥当之后，就差实现题目中的addTwoNumbers函数了，接下来就实现该算法
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
int n1,n2,tmp,carry = 0;
struct ListNode *result = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* pResult= result;
result->next = NULL;
while (l1 != NULL ||l2 !=NULL){
if(l1 != NULL){
n1 = l1->val;
l1 = l1->next;
}else n1 = 0; // 如果l1的位都遍历完了，l2还有位没有遍历，则接下来遍历中，l1的位都用0替代
if(l2 != NULL) {
n2 = l2->val;
l2 = l2->next;
} else n2 = 0;
// 将每个位的数字相加，carry表示是否需要进位
tmp = n1 n2 carry;
// 结果大于9，说明需要进位
if (tmp > 9) carry = 1;
else carry = 0;
// 相加的结果模以10，得到运算后这一位置的数字，存入结果链表中
if (pResult != NULL) pResult->val = tmp % 10;
if (l1 != NULL ||l2 !=NULL){
pResult->next = (struct ListNode*)malloc(sizeof(struct ListNode));
pResult = pResult->next;
pResult->next = NULL;
}
}
// 所有位遍历结束后，如还存在进位，就将最后的结果再进一位
if (carry){
pResult->next = (struct ListNode*)malloc(sizeof(struct ListNode));
pResult = pResult->next;
pResult->val = 1;
pResult->next = NULL;
}
return result;
}
打印结果：
代码语言：javascript复制7
0
8
修改测试用例为：11 9999999999
int main(){
struct ListNode *list1 = LL_init(1);
LL_add(list1, 1);
struct ListNode *list2 = LL_init(9);
LL_add(list2, 9);
LL_add(list2, 9);
LL_add(list2, 9);
LL_add(list2, 9);
LL_add(list2, 9);
LL_add(list2, 9);
LL_add(list2, 9);
LL_add(list2, 9);
LL_add(list2, 9);
struct ListNode *result = addTwoNumbers(list1,list2);
// …………………省略…………………
}
打印结果：
代码语言：javascript复制0
1
0
0
0
0
0
0
0
0
1
栈
栈在我们生活中其实也很常见，例如名片盒，圆桶装薯片，我们取东西的时候只能先从顶部取，而放的时候则是先从底部开始放，这种结构的典型特征就是先进后出。关于栈结构，最形象的例子就是枪的弹夹
栈的简单实现
栈的实现也可以分为数组和链式，其中数组实现是最简单的，这里栈实现就以数组为例，基于链式的栈实现可以参照上面的链表示例。
头文件stack.h
#ifndef _STACK_H_
#define _STACK_H_
#define DEFAULT_CAPACITY 10
typedef int boolean;
#define False 0
#define True 1
typedef struct
{
int top;
char **buf;
int capacity;
} Stack;
int initStack(Stack*);
void push(Stack*,char*);
char *pop(Stack*);
boolean isEmpty(Stack*);
void destroy(Stack**);
#endif
源文件stack.c
#include "stack.h"
#include <stdlib.h>
int initStack(Stack* stack){
if (stack == NULL){
return -1;
}
stack->capacity = DEFAULT_CAPACITY;
stack->top = -1;
stack->buf = (char**)calloc(DEFAULT_CAPACITY,sizeof(char*));
if (stack->buf == NULL){
return -1;
}
return 0;
}
void push(Stack* stack,char* str){
if (stack->top < stack->capacity){
stack->buf[ stack->top] = str;
}else{
int newSize = stack->capacity*2;
char **tmp = (char**)realloc(stack->buf, newSize*sizeof(char*));
if (tmp == NULL){
return;
}
stack->capacity = newSize;
stack->buf = tmp;
stack->buf[ stack->top] = str;
}
}
char *pop(Stack* stack){
return stack->buf[stack->top--];
}
boolean isEmpty(Stack* stack){
return stack->top == -1;
}
// 传入的是二级指针
void destroy(Stack** stack){
free((*stack)->buf);
*stack = NULL;
}
创建测试代码test.c
#include <stdio.h>
#include "stack.h"
int main(){
Stack s;
initStack(&s);
push(&s,"a");
push(&s,"b");
push(&s,"c");
push(&s,"d");
while (!isEmpty(&s)){
printf("%sn",pop(&s));
}
Stack *p = &s;
destroy(&p);
return 0;
}
栈的经典运用
栈的一个经典案例是用来做四则混合运算的计算器算法，例如，编写一个算法，解析字符串"6 (8-3) * 2 10 / 5"，并计算出该表达式的结果。如果使用词法分析、语法分析的思路去处理，则不亚于开发一个编程语言的解析器，但是我们使用两次栈就可以实现。首先将中缀表达式转为后缀表达式，然后再使用栈计算后缀表达式即可。
所谓中缀表达式，即我们通常所写的算式，如："6 (8-3) * 2 10 / 5"而后缀表达式则为："6 8 3 - 2 * 10 5 / "，计算机很难处理中缀表达式，一旦转为后缀表达式，计算机处理起来就非常容易了。后缀表达式又称为逆波兰表达式，相关知识可自行查询。
总的来说，中缀表达式转后缀表达式的规则是：遇数字就输出，运算符进栈，左右括号匹配上一起出栈，栈顶要比较优先级，优先级低的出栈。所谓优先级，即乘除的优先级高于加减运算
以下源码是笔者自行实现的一套算法，代码已尽可能简化，主要实现了整数的四则混合运算。如要包含浮点数，只需很小的改动即可。
首先将我们的栈结构改造一下，让它支持泛型类型，关于C语言泛型处理，参照之前章节的内容。头文件stack.h
#ifndef _STACK_H_
#define _STACK_H_
#define DEFAULT_CAPACITY 10
#include <stdbool.h>
typedef struct
{
int top;
int capacity;
int typeSize; //数据类型的字节数
void *buf;
} Stack;
// 初始化栈
int ST_init(Stack*,int typeSize);
// 压入栈
void ST_push(Stack*,void*);
// 弹出栈
void* ST_pop(Stack*);
// 判空
bool ST_isEmpty(Stack*);
// 查看栈顶
void* ST_top(Stack*);
// 销毁栈
void ST_destroy(Stack*);
#endif
源文件stack.c
#include <stdlib.h>
#include <string.h>
#include "stack.h"
int ST_init(Stack* stack,int typeSize){
if (stack == NULL){
return -1;
}
stack->capacity = DEFAULT_CAPACITY;
stack->top = -1;
stack->typeSize = typeSize;
stack->buf = calloc(DEFAULT_CAPACITY,typeSize);
if (stack->buf == NULL){
return -1;
}
return 0;
}
void ST_push(Stack* stack,void* e){
if (stack->top < stack->capacity){
memcpy(stack->buf ( stack->top) * stack->typeSize, e, stack->typeSize);
}else{
int newSize = stack->capacity*2;
char *tmp = (char*)realloc(stack->buf, newSize*sizeof(char*));
if (tmp == NULL){
return;
}
stack->capacity = newSize;
stack->buf = tmp;
memcpy(stack->buf ( stack->top) * stack->typeSize, e, stack->typeSize);
}
}
void* ST_pop(Stack* stack){
return stack->buf (stack->top--)*stack->typeSize;
}
bool ST_isEmpty(Stack* stack){
return stack->top == -1;
}
void* ST_top(Stack* stack){
if (stack->top == -1) return 0;
else return stack->buf stack->top * stack->typeSize;
}
void ST_destroy(Stack* stack){
free(stack->buf);
}
编写四则混合运算的源码 calculator.c
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include "stack.h"
#define BUF_SIZE 256
#define ST_top_ch(st) *((char *)ST_top(st))
#define ST_pop_ch(st) *((char *)ST_pop(st))
#define ST_pop_int(st) *((int*)ST_pop(st))
// 将字符打印到数组
static void printChar(char ch,char *buf,int *offset){
if (*offset < BUF_SIZE)
*offset = sprintf(buf (*offset),"%c",ch);
}
// 将空格作为分割符，分割字符串，返回字符串数组
static char **splitStr(char *str){
char **arr = (char**)calloc(BUF_SIZE,sizeof(char*));
for (int i = 0; i < BUF_SIZE; i ){
arr[i] = (char*)calloc(50,sizeof(char));
if (arr[i] == NULL) return NULL;
if (i == 0) strcpy(arr[i],strtok(str, " "));
else{
char *p = strtok(NULL, " ");
if (p == NULL) {
free(arr[i]);
arr[i] = NULL;
return arr;
}
strcpy(arr[i],p);
}
}
}
// 扫描数字字符，打印到数组
static bool outDigit(char ch,char *buf,int *offset){
if (isspace(ch)) return true;
bool r = isdigit(ch);
if (!r) ch = ' ';
printChar(ch,buf,offset);
return r;
}
// 解析中缀表达式，并转化为后缀表达式
char **parseExpr(char *s,Stack *stack){
char str[BUF_SIZE]={0};
int offset = 0;
for (; *s !=' '; s ){
while (outDigit(*s,str,&offset)) s ;
switch (*s){
case ' ':
case '-':
while (!ST_isEmpty(stack) && ST_top_ch(stack) != '('){
printChar(ST_pop_ch(stack),str,&offset);
printChar(' ',str,&offset);
}
ST_push(stack,s);
break;
case '*':
case '/':
case '(':
ST_push(stack,s);
break;
case ')':
while (!ST_isEmpty(stack)){
char *ch = (char*)ST_pop(stack);
if (*ch == '(') break;
printChar(*ch,str,&offset);
printChar(' ',str,&offset);
}
break;
case ' ': // 使用goto语句跳出循环
goto end;
default:
printf("nIllegal expression!!!n");
break;
}
}
end:
while (!ST_isEmpty(stack)){
printChar(ST_pop_ch(stack),str,&offset);
printChar(' ',str,&offset);
}
printChar(' ',str,&offset);
return splitStr(str);
}
// 运算处理
static int operate(int a,int b,char op){
int res = 0;
switch (op){
case ' ':
res = a b;
break;
case '-':
res = a - b;
break;
case '*':
res = a*b;
break;
case '/':
res = a/b;
break;
default:
break;
}
return res;
}
// 计算后缀表达式
int calculate(Stack *stack,char **strings){
int num = 0 ,res=0;
for (int i = 0; i < BUF_SIZE; i ){
if (strings[i] == NULL) break;
if (isdigit(strings[i][0])){
num = atoi(strings[i]);
ST_push(stack,&num);
}else{
int a = ST_pop_int(stack);
int b = ST_pop_int(stack);
res = operate(b,a,strings[i][0]);
ST_push(stack,&res);
}
}
return ST_pop_int(stack);
}
int main(){
// 待计算的四则运算表达式
char *expression = "6 (8-3) * 2 10 / 5";
Stack stk;
ST_init(&stk,sizeof(char));
// 将中缀表达式转后缀表达式，并存入字符串数组中返回
char **strArr = parseExpr(expression,&stk);
Stack calcStk;
ST_init(&calcStk,sizeof(int));
// 计算后缀表达式
int result = calculate(&calcStk,strArr);
printf("result=%dn",result);
// 释放堆内存
for (int i = 0; i < BUF_SIZE; i ){
if (strArr[i] != NULL) free(strArr[i]);
}
free(strArr);
ST_destroy(&stk);
ST_destroy(&calcStk);
}
以上代码使用GCC编译器进行编译：gcc calculator.c stack.c -o calculator
计算结果打印：
代码语言：javascript复制result=18
以上代码中，需要注意的是strtok字符串分割函数的使用，其他函数在前面的章节中都有涉及，不再说明，关于该函数的具体用法，请点击查看博主的另一篇 博客 : https://blog.csdn.net/yingshukun/article/details/83957696#21_C_Linux___392
