劝学网主页
主页 儒家 道家 佛经 法家
百家 兵法 中医 正史 历史
易经  南怀瑾全集  小雅 民歌 书城

《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语言教程系列  书名:C语言教程  作者:小雅