《C语言教程》22章链表

这一章的范围其实属于数据结构和算法，早已超出小雅的能力，因小雅在SDK教程中用到这些知识，所以只作简单讲解。如果对链表还一无所知，建议先看一点数据结构方面的书，或者干脆跳过这一章。

下面的例子是一个报数游戏，输入a、b、c三个小于20的整数，如果符合勾股定理，即“a平方+b平方=c平方”同得2000分，否则得“a平方+b平方-c平方”分，这个分也可能为负分。超过1000或-1000则算赢或输，游戏结束。


#include <stdio.h>
#include <stdlib.h>

struct TriAngle{
    int a ;            //直角三角形的勾
    int b ;            //直角三角形的股
    int c ;            //直角三角形的弦
    int score ;        //累计得分
    struct TriAngle *next ;    //下一个
} ;

//计算得分
int getScore(unsigned char x,
             unsigned char y,
             unsigned char z)
{
    //得分 = x平方 + y平方 - z平方
    int iret = x * x + y * y - z * z ;

    //如果三个数是勾股弦，则得2000分
    if (iret==0) {
        iret = 2000;
    }

    return iret ;
}

//动态分配一个新节点
struct TriAngle *newNode(void) 
{
    return malloc(sizeof(struct TriAngle));
}

//输出历次结果，并释放内存
void output(struct TriAngle *node, int no)
{
    //显示当前节点的情况
    printf("%2d  %2d,%2d,%2d   %4d\n", no, node->a, node->b, node->c, node->score);

    //如果下一个节点不为空
    if (node->next != NULL) {
        //递归调用下一个节点的输出并释放内存
        output(node->next, no+1);
    }

    //如果不是“头”结点，释放当前节点的内存
    if (no != 1) {
        free(node);
    }
}

int main(void)
{
    struct TriAngle head;        //头部地址固定，这很重要
    struct TriAngle *p = &head ; //p为当前节点，从头部开始

    //初始化
    head.score = 0;
    head.next = NULL;

    //循环输入数据
    while (1) {
        printf("请输入三个小于20的数：");
        scanf("%d,%d,%d", &p->a, &p->b, &p->c);

        //检查输入的数据合法性
        if (p->a > 20 || p->b > 20 || p->c > 20) {
            printf("三个数不能大于20，请重试。\n");
        } else {
            //当前分数进行累加
            p->score += getScore(p->a, p->b, p->c);

            //如果超过正负1000
            if (p->score < -1000 || p->score > 1000) {
                //设置最终结点并退出循环
                p->next = NULL;
                break;
            } else {
                //动态请示下一个节点，并初始化累加分数，然后当前指针移向下一个
                p->next = newNode();
                p->next->score = p->score ;
                p = p->next ;
            }
        }
    }

    //打印输出头部，调用输出并释放内存函数
    printf("No   a  b  c   得分\n");
    output(&head, 1);

    return 0;
}

一、单向链表的定义和赋值

链表的结构多种多样，单向链表是最简单的一种。也就是结构体中有一个元素是一个指针，这个指针的数据类型是自身，用来表示下一个结构体的地址。

struct TriAngle{
    int a ;            //直角三角形的勾
    int b ;            //直角三角形的股
    int c ;            //直角三角形的弦
    int score ;        //累计得分
    struct TriAngle *next ;    //下一个
} ;

二、下一个节点的申请和终止

使用链表就必然要用到动态分配，所以内存泄漏又成了一个麻烦。单向链表在释放内存方面，一个关键地方是要记住链表的头，然后顺着这个“头”的指针一个一个地释放，这时用递归算法是比较好的做法。

            //如果超过正负1000，则终止循环
            if (p->score < -1000 || p->score > 1000) {
                //设置最终结点并退出循环
                p->next = NULL;
                break;
            } else {
                p->next = newNode();         //动态请示下一个节点
                p->next->score = p->score ;  //初始化累加分数
                p = p->next ;                //当前指针移向下一个
            }

三、内存的释放

            //如果超过正负1000，则终止循环
            if (p->score < -1000 || p->score > 1000) {
                //设置最终结点并退出循环
                p->next = NULL;
                break;
            } else {
                p->next = newNode();         //动态请示下一个节点
                p->next->score = p->score ;  //初始化累加分数
                p = p->next ;                //当前指针移向下一个
            }

《C语言教程》22章 链表

《C语言教程》22章链表