程序员C语言快速上手——高级篇（十一）

arcticfox

发布于 2019-07-30 15:41:11

1.2K2

发布于 2019-07-30 15:41:11

文章被收录于专栏：编程之路的专栏

高级篇
- 数据结构
  - 线性表
    - 基于数组
    - 基于链表
    - 链表的经典运用
  - 栈
    - 栈的简单实现
    - 栈的经典运用

高级篇

数据结构

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 error\n");
            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("%d\n",e);
    }

    // 删除指定位置的元素
    AL_remove(&list,3);
    AL_remove(&list,4);
    AL_remove(&list,5);

    printf("-----------------------*-*-----------------------\n");
    printf("list size is %d\n",list.length);
    printf("-----------------------*-*-----------------------\n");
    
    // 遍历列表
    for (size_t i = 0; i < list.length; i++){
        AL_get(&list,i,&e);
        printf("%d\n",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("%d\n",e);
    }
    LL_remove(&list,9);
    LL_remove(&list,5);
    
    printf("-----------------------*-*-----------------------\n");
    printf("list size is %d\n",list.length);
    printf("-----------------------*-*-----------------------\n");
    
    for (size_t i = 0; i < list.length; i++){
        LL_get(&list,i,&e);
        printf("%d\n",e);
    }
}

基于数组和基于链式的线性表各有特点，这里做一个线性表小结

基于数组的线性表，添加、删除元素性能较差，根据以上代码可知，当频繁添加或删除元素时，需要底层动态数组不断的申请或移动内存，而频繁申请堆内存是非常耗费性能的，但是基于数组的线性表，其具有数组的快速索引特点，查询定位元素时速度非常快
基于链式的线性表，其查询元素时较为耗费性能，且与查询的元素所处的位置相关。当链表元素越多时，被查询的元素越靠后，其速度越慢。这是因为链表的查询必须从头节点开始遍历，如果被查询的元素正好是最后一个，那么就需要将前面所有节点遍历一次。相对的，链表添加、删除元素的性能非常高，因为它不需要移动内存，只需要将指针指向一个新的元素。

链表的经典运用

先来看一道算法题：

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

题干：

/**
 * 结构体原型
 * 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语言整型的范围，溢出了。换个角度，其实就是在问的，超大整数如何在计算机中去表示、去处理、去运算。

为了方便测试和验证，我们先自行实现一下题目中的结构体，并填充一些测试数据

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("%d\n",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;
}

打印结果：

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);
	// …………………省略…………………
}

打印结果：

栈

栈在我们生活中其实也很常见，例如名片盒，圆桶装薯片，我们取东西的时候只能先从顶部取，而放的时候则是先从底部开始放，这种结构的典型特征就是先进后出。关于栈结构，最形象的例子就是枪的弹夹

栈的简单实现

栈的实现也可以分为数组和链式，其中数组实现是最简单的，这里栈实现就以数组为例，基于链式的栈实现可以参照上面的链表示例。

头文件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("%s\n",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 !='\0'; 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 '\0':  // 使用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('\0',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=%d\n",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

计算结果打印：

result=18

以上代码中，需要注意的是strtok字符串分割函数的使用，其他函数在前面的章节中都有涉及，不再说明，关于该函数的具体用法，请点击查看博主的另一篇 博客 : https://blog.csdn.net/yingshukun/article/details/83957696#21_C_Linux___392

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-07-28，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构