当前位置:网站首页>>电脑技术>>C、C++语言>>我的著作 双击自动滚屏
C语言速成(第六章 结构)

发表日期:2006年1月1日      已经有9022位读者读过此文

第六章  结构

    在第五章里已经介绍过,数组是相同数据类型的一批相关数据的集合,数组的元素必需是同一类型的数据。例如定义一个数组:

        int a[10];

表示数组 a 中每个元素都是整数。但在处理实际问题时,我们遇到的许多成组出现的相关数据并不都是相同类型的,在经常要对这些数据进行重复处理时,用数组就显得十分不便。例如处理一个单位的人事信息,对每个人都要用“姓名”、“性别”、“年龄”、“工资”等一组相关数据来描述。在这一组数据里,“姓名”、“性别”要用字符型指针变量或数组来表示,“年龄”要用整形变量表示,而“工资”则需用浮点变量来表示。为此,C语言提供了一个新的数据类型──结构。结构是一组相关但类型不同的数据的集合,它是一种组合成的类型。

第一节  结构的定义

    结构的成员是不同类型的变量,因此对结构成员的访问和数组不同,不是通过下标而是通过它们的名字来进行的。这就要求结构在使用前必须说明其成员和它们的类型。结构和结构变量定义的一般形式为:

        <存储类型> struct <结构名> {
                                          <成员表>
                                       }  <结构变量> ;

    成员表中应对各成员说明其存储类、数据类型和标识符。下面是一个结构定义的例子:

        struct person {                /* 定义一个结构 */
           char name[10];              /* 成员说明 */
           char sex[3];                /* 成员说明 */
           int age;                    /* 成员说明 */
           float salary;               /* 成员说明 */
        };

这里定义了一个结构 person,它有四个成员,其中 name 和 sex 是字符型数组, age 是整数,salary 是单精度浮点数。person 本身不是变量,而仅仅是一个结构的样本。struct person 就象我们前面常用的 int、char 一样表示一种数据类型,但它是由编程者自行定义的类型名。仅仅定义了结构并不分配内存空间,只有用它定义了一个变量后,才为该变量分配存储空间。例如表达式

        struct person s;

定义变量 s 的类型为 struct person。当然也允许同时定义几个变量,如:

        struct person s,k,t;

    对结构变量的定义也可以和对结构的定义结合在一起进行:

        struct person {
           char name[10];
           char sex[3];
           int age;
           float salary;
        } s;

    当结构只在较小的范围内,如函数内使用时,可以把结构名省略掉,但必须在定义结构的同时定义结构变量。例如:

        struct {
           char name[10];
           char sex[3];
           int age;
           float salary;
        } s;

    在结构变量定义时允许结构名与定义的结构变量名重名,如:

        struct person person;

前一个 person 是结构名,后一个 person 是结构变量名。结构名与成员名的重复、不同结构的成员名的重复都是允许的,但同一个结构中的成员名则不允许重复,例如下列结构变量的定义是合法的:

        struct name {
           int i;
           char name[10];
        } name;

        struct city {
           int i;
           char city[10];
        } i;

但不允许:

        struct name {
           int i;
           double i;
        };

    结构变量可以初始化,它初始化的方法类似于数组,只允许对外部或静态存储类型的结构变量进行初始化,如:

        static struct person {
           char name[10];
           char sex[3];
           int age;
           float salary;
        } s={"王林","男",21,180.30};

    对存储类型为自动类型的结构变量,只能在函数执行时分别对其成员进行赋值。结构的成员可以是任何类型的变量,可以是是各种简单类型变量、数组、指针,也可以是另一个结构变量,但结构中各成员的大小必需是已知的。例如我们可以定义一个结构为:

        struct sal {
           char num[10];
           struct person s;
        };

    式中 struct person 是前面已经定义过的结构,s 为具有 struct person 类型的变量。一个结构成员不能是结构本身,即不能自己定义自己,但允许结构通过指针引用自身。也就是说,结构成员可以是正在定义的结构指针。因此不能用:

        struct sal {
           char num[10];
           struct sal x;
        };

    当必须引用自身时,应该定义成:

        struct sal {
           char num[10];
           struct sal *x;
        };

    这在程序实现链表结构和递归等操作时是十分有用的。另外必须指出,和数组一样,结构成员不允许是一个函数,但允许是一个函数指针。除了基本类型的变量外,结构变量也可以是数组或指针形式的。如:

        struct sal p[100]; 或是  struct sal *q;

    关于结构数组和结构指针我们将在后面的章节里再作具体讲述。

第二节  结构成员的引用

    使用结构时必须通过成员名来访问结构的成员。结构成员引用有两种方法,一种是通过直接成员选择符“.”,其表达式的一般形式为:

        <结构变量> . <成员名>

    另一种是用间接成员选择符“->”来完成,这种方式适用于结构指针变量,其表达式的一般形式为:

        <结构指针> -> <成员名>

    运算符“->”是由两个字符组合而成的。关于结构指针我们将在第四节里作较详细的介绍。如果定义了结构变量 s 和结构指针变量 p:

        struct person {
           char name[10];
           char sex[3];
           int age;
           float salary;
        } s,*p;

    s.sex[0]   表示结构变量 s 的成员 sex 数组的第0个元素;
    s.name     表示指向结构变量 s 的成员字符串 name 首字符的指针;       
    s.age      表示结构变量 s 的成员 age;
    p->sex[0]  表示结构指针变量 p 的成员 sex 数组的第0个元素,它等同于
                 (*p).sex[0];
    p->name    表示重新结构指针变量 p 的成员字符串 name 串首的指针,它等同于
                 (*p).name;
    p->age     表示结构指针变量 p 的成员 age,它等同于 (*p).age。

    后面表达式中的括号是不可省略的,因为取结构成员的运算符“.”的优先级高于取指针内容的运算符“*”。对结构成员的赋值和其他运算操作和对一个普通变量基本相同。例如我们能够对结构成员进行赋值运算:

        s.age=21;
        p->salary=180.30;

    假如一个结构的成员为另一个结构,对其成员的访问就需要多次运用取成员运算符。例如有:

        struct X {
           int i;
           char name[10];
        };
        struct Y {
           int j;
           struct X a;
           struct X *b;
        } s,*p;

s.j、p->j 为 Y 的成员,而 s.a.i、p->a.name[0]、p->b->i 为结构 X 的成员。同一类型的结构变量之间可以整体赋值,如定义了:

        struct person *a,*b;

则表达式 a=b; 就是把结构变量 b 的内容赋给 a,相当于把 b 中各成员的值赋给 a 中相应的成员。下面是一个结构运用的例子:

    例7.1  建立一个存放姓名、性别、年龄、工资四项数据的结构,从键盘输入数据,并在屏幕上打印这些数据。

    #include "stdio.h"                 /* 用预处理命令指定包含文件 */
    struct person {                    /* 定义一个结构 */
      char name[10];
      char sex[3];
      int age;
      float sal;
    }
    main()                             /* 主函数 */
    {
      struct person p;                 /* 定义一个 struct person 类型的变量 */
      printf("姓名:");                 /* 屏幕打印输入提示 */
      scanf("%s",p.name);              /* 键盘输入字符串,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("性别:");                 /* 屏幕打印输入提示 */
      scanf("%s",p.sex);               /* 键盘输入字符串,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("年龄:");                 /* 屏幕打印输入提示 */
      scanf("%d",&p.age);              /* 键盘输入一整数,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("工资:");                 /* 屏幕打印输入提示 */
      scanf("%f",&p.sal);              /* 键盘输入浮点数,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("姓名:%s性别:%s年龄:%d工资:%6.2f",p.name,p.sex,p.age,p.sal);
                                       /* 在屏幕上打印结构中各成员 */
    }
    newline()                          /* 吃掉 scanf 输入的多余字符和回车符 */
    {
      while(getchar()!=''''''''\n'''''''');          /* 输入字符不为回车符则继续循环 */
    }

    需要说明一下的是,程序每次用 scanf 函数输入数据后都调用了一个 newline 函数,这个函数的作用在于“吃掉” scanf 输入的多余字符和回车符,以免影响下一个数据的输入。

第三节  结构数组

    当结构变量是一个数组时,称为结构数组。结构数组的每一个元素都是一个结构变量。定义结构数组的方法和定义结构变量一样,下面定义的就是一个结构数组:

        struct stu {
           char name[10];
           int score;
        } num[5];

    数组 num 有5个元素,每个元素均为 struct stu 类型。结构数组初始化的方法可以在定义结构数组时用初值表进行赋值,例如:

        static struct stu {
           char name[10];
           int score;
        } num[5]={ {"陈  越",91},
                   {"王永华",88},
                   {"李和平",98},
                   {"金家明",77},
                   {"何国炳",81} };

    如果所有的元素均赋初值,初始化时结构数组元素的个数也可以不指明,即方括号中的5可以不写。这个结构数组实际上可以构成一个有两个栏目的表格:

                      name         score
        num[0]       陈  越         91
        num[1]       王永华         88
        num[2]       李和平         98
        num[3]       金家明         77
        num[4]       何国炳         81

    例7.2  在例7.1的基础上建立一个存放4个人人事数据的结构数组,并在屏幕上列表打印。

    #include "stdio.h"                 /* 用预处理命令指定包含文件 */
    #define SIZE 4                     /* 通过宏替换命令用 SIZE 代替 400 */
    struct person {                    /* 定义一个结构 */
      char name[10];
      char sex[3];
      int age;
      float sal;
    };
    main()                             /* 主函数 */
    {
      int i;                           /* 定义一个整形变量 i */
      struct person p[SIZE];           /* 定义一个结构数组 */
      for(i=0;i<SIZE;i++) {            /* 为逐人输入数据建的循环 */
        printf("姓名:");               /* 屏幕打印输入提示 */
        scanf("%s",p[i].name);         /* 屏幕输入字符串,放入结构相应成员中 */
        newline();                     /* 调用函数 newline */
        printf("性别:");               /* 屏幕打印输入提示 */
        scanf("%s",p[i].sex);          /* 屏幕输入字符串,放入结构相应成员中 */
        newline();                     /* 调用函数 newline */
        printf("年龄:");               /* 屏幕打印输入提示 */
        scanf("%d",&p[i].age);         /* 屏幕输入整数,放入结构相应成员中 */
        newline();                     /* 调用函数 newline */
        printf("工资:");               /* 屏幕打印输入提示 */
        scanf("%f",&p[i].sal);         /* 屏幕输入浮点数,放入结构相应成员中 */
        newline();                     /* 调用函数 newline */
      }
      printf(" 姓名      性别  年龄    工资\n"); /* 屏幕打印人事表格栏目 */
      for(i=0;i<SIZE;i++) {            /* 为输出结构数组各元素设的循环 */
         printf("%-10s  %2s    %2d    %6.2f\n",
                               p[i].name,p[i].sex,p[i].age,p[i].sal);
                                       /* 屏幕打印数组一个元素各成员数据 */
      }
    }
    newline()                          /* 吃掉 scanf 输入的多余字符和回车符 */
    {
      while(getchar()!=''''''''\n'''''''');          /* 如输入字符不为回车则继续循环 */
    }

第四节  指向结构的指针

    当结构变量是指针变量时,这个指针变量初始化后所包含的值就是结构变量的起始地址。在第六章讲述指针时就已经指出,未经初始化的指针变量是不能用来进行运算的,对于结构指针来说同样也是这样,在引用结构成员前必须给指向结构的指针变量以一个确定的地址值。

    例7.3  用结构指针形式改写例7.2。

    #include "stdio.h"                 /* 用预处理命令指定包含文件 */
    #include "malloc.h"                /* 用预处理命令指定包含文件 */
    #define SIZE 4                     /* 通过宏替换命令用 SIZE 代替常数 4 */
    struct person {                    /* 定义一个结构 */
      char name[10];
      char sex[3];
      int age;
      float sal;
    };
    main()                             /* 主函数 */
    {
      struct person *p;                /* 定义一个结构指针变量 */
      int i;                           /* 定义一个整形变量 */
      p=(struct person *)malloc(SIZE*sizeof(struct person));
                                       /* 开辟一块存储区,首地址赋给 p */
      for(i=0;i<SIZE;i++,p++) {        /* 为逐人输入设的循环 */
        printf("姓名:");               /* 屏幕打印输入提示 */
        scanf("%s",p->name);           /* 键盘输入字符串,放入结构相应成员中 */
        newline();                     /* 调用函数 newline */
        printf("性别:");               /* 屏幕打印输入提示 */
        scanf("%s",p->sex);            /* 键盘输入字符串,放入结构相应成员中 */
        newline();                     /* 调用函数 newline */
        printf("年龄:");               /* 屏幕打印输入提示 */
        scanf("%d",&p->age);           /* 键盘输入一整数,放入结构相应成员中 */
        newline();                     /* 调用函数 newline */
        printf("工资:");               /* 屏幕打印输入提示 */
        scanf("%f",&p->sal);           /* 键盘输入浮点数,放入结构相应成员中 */
        newline();                     /* 调用函数 newline */
      }
      p-=SIZE;                         /* 结构指针返回起始地址 */
      printf(" 姓名        性别  年龄    工资\n"); /* 屏幕打印表格栏目 */
      for(i=0;i<SIZE;i++,p++)          /* 为输出各人数据设的循环 */
         printf("%-10s    %2s    %2d     %6.2f\n",
                                      p->name,p->sex,p->age,p->sal);
                                       /* 屏幕打印结构各成员数据 */
    }
    newline()                          /* 吃掉 scanf 输入的多余字符和回车符 */
    {
      while(getchar()!=''''''''\n'''''''');          /* 输入的不为回车符则继续循环 */
    }

    上例中结构指针的移动通过 p++ 实现,每循环一次执行一次 p++,每执行一次 p++ 结构指针移动一定的字节数,每次移动的字节数究竟是多少,可以用长度运算符 sizeof 计算出来,如:  sizeof(struct person)  。
    在本例中结构指针变量的初始化是通过用库函数 malloc 分配 SIZE 个该结构占用的字节数来完成的。一旦给结构指针分配了存储区域,结构指针变量所包含的结构起始地址也就确定了,后面程序中对结构成员的赋值、取值都可以合法地进行了。
    编译程序安排变量的存储地址时有不同的对齐方式。通常有按字节对齐和按字对齐两种。在按字节对齐方式下,变量不管是何种类型都定位在下一个可用字节上。但在按字对齐方式下,对非 char 型变量要求定位在偶地址上,在这种情况下,内存中会出现一些“空穴”,因此,往往不能简单地认为结构占用的字节数等于各成员大小之和,而应该用 sizeof 来计算,这样做也有利于程序的移植。

第五节  结构和函数

    结构能否整体地作为函数的参数,不同的C语言版本有不同的规定。一些老版本的C语言不允许用结构变量作为函数的参数,  只能用指向结构的指针作为实参传递地址。而根据ANSI 标准设计的C语言版本则允许用整个结构作为函数的参数进行传递,不过在传递时必须保持实参和形参类型上的统一。结构作为参数整体传递的效率是不高的,因此在传递一些成员多构成复杂的结构时,仍以传递结构指针为好。先看一个结构整体传递的例子:

    例7.4  将例7.1中的屏幕打印改成一个单独的函数,并将结构变量作为参数传递给它。

    #include "stdio.h"                 /* 用预处理命令指定一个包含文件 */
    struct person {                    /* 定义一个结构 */
      char name[10];
      char sex[3];
      int age;
      float sal;
    }
    main()                             /* 主函数 */
    {
      struct person p;                 /* 定义一个结构变量 */
      printf("姓名:");                 /* 屏幕打印输入提示 */
      scanf("%s",p.name);              /* 键盘输入字符串,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("性别:");                 /* 屏幕打印输入提示 */
      scanf("%s",p.sex);               /* 键盘输入字符串,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("年龄:");                 /* 屏幕打印输入提示 */
      scanf("%d",&p.age);              /* 键盘输入一整数,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("工资:");                 /* 屏幕打印输入提示 */
      scanf("%f",&p.sal);              /* 键盘输入浮点数,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      pstr(p);                         /* 调用函数打印,结构变量作为参数 */
    }
    pstr(pt)                           /* 打印一个结构数据的函数 */
    struct person pt;                  /* 形参说明 */
    {
      printf("姓名:%s 性别:%s 年龄:%d 工资:%6.2f",
                                     pt.name,pt.sex,pt.age,pt.sal);
                                       /* 屏幕打印结构各成员数据 */
    }
    newline()                          /* 吃掉 scanf 输入的多余字符和回车符 */
    {
      while(getchar()!=''''''''\n'''''''');          /* 输入的不为回车符则继续循环 */
    }

    对于不能进行结构整体传递的C语言版本,当然可以把结构每个成员作为一个参数来进行传递,但这样做对于一些较复杂的结构来说无疑太繁琐了,比较好的办法是传递指向结构的指针。

    例7.5  将例7.4中的传值方法改为传递一个结构指针。

    #include "stdio.h"                 /* 用预处理命令指定一个包含文件 */
    struct person {                    /* 定义一个结构 */
      char name[10];
      char sex[3];
      int age;
      float sal;
    }
    main()                             /* 主函数 */
    {
      struct person p;                 /* 定义一个结构变量 */
      printf("姓名:");                 /* 屏幕打印输入提示 */
      scanf("%s",p.name);              /* 键盘输入字符串,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("性别:");                 /* 屏幕打印输入提示 */
      scanf("%s",p.sex);               /* 键盘输入字符串,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("年龄:");                 /* 屏幕打印输入提示 */
      scanf("%d",&p.age);              /* 键盘输入一整数,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      printf("工资:");                 /* 屏幕打印输入提示 */
      scanf("%f",&p.sal);              /* 键盘输入浮点数,放入结构相应成员中 */
      newline();                       /* 调用函数 newline */
      pstr(&p);                        /* 调用函数打印结构,结构指针作为参数 */
    }
    pstr(pt)                           /* 屏幕打印结构数据的函数 */
    struct person *pt;                 /* 定义一个结构指针 */
    {
      printf("姓名:%s  性别:%s  年龄:%d  工资:%6.2f",
                                        pt->name,pt->sex,pt->age,pt->sal);
                                       /* 屏幕打印结构各成员数据 */
    }
    newline()                          /* 吃掉 scanf 输入的多余字符和回车符 */
    {
      while(getchar()!=''''''''\n'''''''');          /* 输入的不为回车符则继续循环 */
    }

    在例7.4里传递给函数 pstr 的实参是整个结构,它的形参是一个结构变量,而在例7.5中则传递结构变量的地址,其形参是一个结构指针。相应地,在打印模块中引用结构元素的形式也就不同了。

第六节  链表

    结构有着十分广泛的用途,可以用它来实现链表、队列、树等多种数据结构类型,作为一本C语言的入门教材,我们仅简要地介绍其中的一种──单向链表。
    链表是一种可以动态地进行存储分配的结构,能够在内存中建立未知大小的数组。用数组存放数据时,必须先通过定义确定数组的元素个数,即数组的长度。例如,已知一个生产班组有30个工人,在用数组存放每个人的生产产量时,就必须定义一个长度为30的数组。如果事先不能确定班组的工人数,则不得不把数组定义得足够大,这样就难免要占用比较大的内存,造成内存空间的浪费。而用链表则能很好地解决此类问题。
    单向链表是最简单的一种链表。我们把通常把链表中的一个元素称为“结点”,结点分为两部分,一部分用来存放数据,称为数据域;另一部分是一个向后的指针──链指针,存放后一个结点的地址,称为指针域。单向链表有一个“头指针”,它指向链表的第一个结点。第一个结点中的链指针指向第二个结点,……,就象一根链条一样一环扣着一环,直到最后一个元素。最后一个结点的链指针放一个空地址(NULL),链表到此结束,称为“链尾”。图7.1是一个单向链表的示意图:

                  ┏━━━━┓    ┏━━━━┓    ┏━━━━┓
        头指针─→┨ 数  据 ┃┌→┨ 数  据 ┃┌→┨ 数  据 ┃
                  ┣━━━━┫│  ┣━━━━┫│  ┣━━━━┫
                  ┃链指针─╂┘  ┃链指针─╂┘  ┃链指针─╂→ NULL
                  ┗━━━━┛    ┗━━━━┛    ┗━━━━┛
                                                          ( 链尾 )

                         图 7.1  单向链表示意图

    链表中的结点是链表中具有完整意义的最小数据单位,结点中各成员存放在内存里一个连续的区域中。但链表中的各个结点在内存中的存放不一定是连续的。在进行链表操作时,可以根据“头指针”找到链表的第一个元素,再根据这个元素中的链指针包含的地址,找到下一个元素,依次类推,能够对链表里的各元素进行访问。对链表的基本操作主要有插入或添加一个元素、删除一个元素和链表的查询、排序、输出等。执行这些操作时,并不需要物理地改变原有元素在内存里的存放位置,而只要改变相关元素中链指针的指向。
    我们已经知道结构可以包含若干个成员,结构的成员可以是各种基本类型或构造类型的变量,也可以是指向自身所在结构类型的指针。因此,用结构类型的元素来构造一个链表是再恰当不过的了。在建立一个单向链表时,需要先定义一个结构来存放数据和链指针。例如要建立一个存放邮政编码和相应单位名称的单向链表,就需要定义如下的结构:

    struct postcode {
       long code;
       char name[50];
       struct postcode *next;
    }

    在这个结构里,code 和 name 构成了结点的数据域,next 是引用自身结构类型的指针。我们可以用它来建立一个单向链表,这个链表的每个结点都是 struct postcode类型,除链尾外的每个结点中都放着下一个结点的地址。
    在定义一个结构时,并没有分配内存空间。在建立链表的过程中,每增加一个节点都必须用上章第五节中介绍过的用于动态分配内存的库函数 malloc,按照结点的结构类型向系统申请内存,开辟一个存储区域,并返回指向这个存储区首地址的指针。malloc 申请内存的大小可以通过运算符 sizeof 计算出来。ANSI 标准规定 malloc 函数的返回值为 void * 类型,为了返回指向该结构的指针,还必须进行强制类型转换。例如对定义的结构指针变量分配内存可以用:

    struct postcode *p;
    p=(struct postcode *) malloc(sizeof(struct postcode));

    当我们从链表里删除一个节点时,要把这个节点占用的内存归还给系统。这时要用到库函数 free:

    free(p);

    有了上面的知识,我们就可以着手建立一个单向链表了。

    例7.6  建立一个存放邮政编码和相应单位名称的单向链表。

    #define NULL 0                     /* 通过宏替换命令用 NULL 代替 0 */
    struct postcode *head;             /* 定义一个结构指针变量(链表头指针) */
    creat()                            /* 建立单向链表 */
    {
       struct postcode *last,*new;     /* 定义两个结构指针变量,last 为链尾
                                          结点指针,new 为新结点指针 */
       head=last=NULL;                 /* 初始状态令头指针和链尾指针均指向空 */
       while(1){                       /* 为连续建立结点设的循环 */
          new=(struct postcode *)malloc(sizeof(struct postcode));
                                       /* 为新结点分配存储空间 */
          printf("输入邮政编码:");     /* 屏幕打印输入提示 */
          scanf("%ld",&new->code);     /* 键盘输入邮政编码,存入新结点 */
          if(new->code==0) break;      /* 输入 0 退出循环 */
          printf("输入单位名称:");     /* 屏幕打印输入提示 */
          scanf("%s",new->name);       /* 键盘输入单位名称,存入新结点 */
          if(last==NULL) head=new;     /* 如果原为空链表,头指针指向新结点 */
          else last->next=new;         /* 否则原链尾结点的链指针指向新结点 */
          new->next=NULL;              /* 新结点链指针指向空,成为链尾 */
          last=new;                    /* 链尾结点指针改为新结点指针 */
       };
    }

    在这个例子里,定义了三个 struct postcode 类型的指针变量,即头指针 head 和指针 new、last,其中 head 是全局变量。程序中先使 head 和 last 指向空(NULL),用库函数 malloc 函数分配一块存储区,并将该空间的首地址赋给 new,建立一个结点,用 scanf 函数给结点的数据域输入数据,并使结点 new 中的链指针指向 NULL。如果这时 last 指向 NULL,则建立的是单向链表的第一个结点,就须把 new 的值赋给 head,使头指针 head 指向第一个结点。如果建立的不是第一个结点,就令 last->next=new,使原来链尾结点 last 中的链指针指向新建立的结点,同时令 last=new,使 last 后移指向新建立的结点,这样新结点就链入了链表,成为新的链尾。
    依靠一个循环语句,就可以不断地在链表的链尾接入新的结点,直到输入的邮政编码是0时跳出循环。
    下面例子用来说明如何在单向链表中插入一个新的结点:
 
    例7.7  输入一个邮政编码,在已建立的链表里找出存放这个邮政编码的结点,并在其后插入一个新的结点。

    ins()                              /* 插入一个结点 */
    {
       long n;                         /* 定义一个长整形变量 */
       struct postcode *p,*new;        /* 定义两个结构指针变量,p 为当前结点
                                          指针,new 为新结点指针 */
       p=head;                         /* 当前结点指针指向链表头 */
       if(head==NULL) {                /* 如果头指针指向 NULL,链表为空链表 */
          printf("链表为空!");         /* 屏幕打印提示 */
          return;                      /* 返回调用函数 */
       }
       printf("输入拟插入处结点存放的邮政编码:"); /* 屏幕打印输入提示 */
       scanf("%ld",&n);                /* 键盘输入邮政编码,放入变量 n */
       while(n!=p->code) {             /* 结点数据不等于 n 继续循环 */
          if(p->next==NULL) {          /* 如果当前结点是链尾 */
             printf("邮政编码%ld未找到!\n",n);  /* 屏幕打印提示 */
             return;                   /* 返回调用函数 */
          }
          p=p->next;                   /* 当前结点指针移向下一个结点 */
       }
       new=(struct postcode *)malloc(sizeof(struct postcode));
                                       /* 开辟一个新结点,分配存储空间 */
       printf("输入新结点数据:\n");    /* 屏幕打印输入提示 */
       printf("输入邮政编码:");        /* 屏幕打印输入提示 */
       scanf("%ld",&new->code);        /* 键盘输入邮政编码,放入结点中 */
       printf("输入单位名称:");        /* 屏幕打印输入提示 */
       scanf("%s",new->name);          /* 键盘输入单位名称,放入结点中 */
       new->next=p->next;              /* 新结点的链指针指向当前结点后的结点 */
       p->next=new;                    /* 当前结点的链指针指向新结点 */
    }

    在上例中,定义了两个 struct postcode 类型的指针变量 p 和 new。先令 p=head,使 p 指向链表的第一个结点,通过一个循环,对输入的邮政编码和结点存放的邮政编码值进行比较。如果比较不相符,令 p=p->next,再比较下一个结点。找到相符的结点后,用例7.6中相同的方法建立一个新结点。只要把新结点的链指针指向当前结点后的一个结点,当前结点的链指针指向新结点,新结点就插入了链表。新结点插入的过程可以用图7.2表示。

                               new┏━━━━┓
                                →┨  code  ┃
                                  ┠────┨
                                  ┃  name  ┃
                                  ┣━━━━┫
                                  ┃  next─╂
                                  ┗━━━━┛

                 p┏━━━━┓        ┏━━━━┓
                →┨  code  ┃┌──→┨  code  ┃┌→
                  ┠────┨│      ┠────┨│
                  ┃  name  ┃│      ┃  name  ┃│
                  ┣━━━━┫│      ┣━━━━┫│
                  ┃  next─╂┘      ┃  next─╂┘
                  ┗━━━━┛        ┗━━━━┛

                                      (1)

                               new┏━━━━┓
                              ┌→┨  code  ┃
                              │  ┠────┨
                              │  ┃  name  ┃
                              │  ┣━━━━┫
                              │  ┃  next─╂─┐
                              │  ┗━━━━┛  │
                              │  ┌──────┘
                 p┏━━━━┓│  │  ┏━━━━┓
                →┨  code  ┃│  └→┨  code  ┃┌→
                  ┠────┨│      ┠────┨│
                  ┃  name  ┃│      ┃  name  ┃│
                  ┣━━━━┫│      ┣━━━━┫│
                  ┃  next─╂┘      ┃  next─╂┘
                  ┗━━━━┛        ┗━━━━┛

                                      (2)

                        图7.2  插入一个结点的示意图

    理解了上面的程序,也就不难设计一个删除结点的函数了:

    例7.8  输入一个邮政编码,找到存放这个邮政编码的结点,并删除之。

    delete()                           /* 删除一个结点 */
    {
       long n;                         /* 定义一个长整形变量 */
       struct postcode *p,*flont;      /* 定义两个结构指针变量,p 为当前结点
                                          指针,flont 为当前结点前一结点指针 */
       if(head==NULL) {                /* 如果头指针指向空,链表为空链表 */
          printf("链表为空!");         /* 屏幕打印提示字符串 */
          return;                      /* 返回调用函数 */
       }
       p=head;                         /* 当前结点指针指向第一个结点 */
       printf("输入拟删除结点存放的邮政编码:");  /* 屏幕打印输入提示 */
       scanf("%ld",&n);                /* 键盘输入邮政编码 */
       while(n!=p->code) {  /* 比较输入的邮码和结点存放的邮码,不同则继续循环 */
          if(p->next==NULL) {          /* 如果到链尾 */
             printf("邮政编码%ld未找到!\n",n);   /* 屏幕打印提示 */
             return;                   /* 返回调用函数 */
          }
          flont=p;                     /* 保存当前结点的指针 */
          p=p->next;                   /* 当前结点移向下一个结点 */
       }
       if(p==head) head=p->next;  /* 如果删除的是第一个结点,头指针后移一结点 */
       else flont->next=p->next;       /* 否则把当前结点前结点的
                                               链指针指向当前结点后的结点 */
       free(p);                        /* 释放被删除结点占用的内存空间 */
    }

    在这部分程序中,每次对结点存放的邮政编码值比较后,如果与输入的邮政编码不相符,则用结构指针 flont 保存这个结点的指针,然后移至下一个结点继续比较。找出相符的结点后,再进行判断,如果该结点是链表的第一个结点,则令头指针 head 等于这个结点的链指针,即指向第二个结点。如果该结点不是第一个结点,则令它前面一个结点的链指针等于该结点的链指针,即将它前面一个结点的链指针指向它后面的一个结点,这个结点便被排除在链表之外了。用库函数 free 释放该结点所占用的内存空间,这样就完成了结点的删除。图7.3为从链表中间删除一个结点的示意图:
             flont┏━━━━┓   p┏━━━━┓    ┏━━━━┓
                →┨  code  ┃┌→┨  code  ┃┌→┨  code  ┃
                  ┠────┨│  ┠────┨│  ┠────┨
     删除前       ┃  name  ┃│  ┃  name  ┃│  ┃  name  ┃
                  ┣━━━━┫│  ┣━━━━┫│  ┣━━━━┫
                  ┃  next─╂┘  ┃  next─╂┘  ┃  next─╂→
                  ┗━━━━┛    ┗━━━━┛    ┗━━━━┛
                                     (1)

             flont┏━━━━┓   p┏━━━━┓    ┏━━━━┓
                →┨  code  ┃  →┨  code  ┃┌→┨  code  ┃
                  ┠────┨    ┠────┨│  ┠────┨
  改变链指针指向  ┃  name  ┃    ┃  name  ┃│  ┃  name  ┃
                  ┣━━━━┫    ┣━━━━┫│  ┣━━━━┫
                  ┃  next─╂┐  ┃  next─╂│  ┃  next─╂→
                  ┗━━━━┛│  ┗━━━━┛│  ┗━━━━┛
                              └───────┘ 
                                     (2)

                          图7.3  删除一个结点的示意图

    最后,我们把前面建立的几个函数合成一个程序,并将整个链表在屏幕上列表输出:

    例7.9 将例7.6─例7.8合成一个程序,用一个屏幕菜单选择,进行前述各种操作和在屏幕上列表输出链表数据。

    #include "stdio.h"                 /* 用预处理命令指定一个包含文件 */
    #define NULL 0                     /* 通过宏替换命令用 NULL 代替 0 */
    struct postcode {                  /* 定义一个结构 */
       long code;
       char name[50];
       struct postcode *next;
    };
    struct postcode *head;             /* 定义一个结构指针变量(链表头指针) */

    main()                             /* 主函数 */
    {
       int c;                          /* 定义一个自动变量 */
       while(1) {                      /* 为菜单选择设的循环 */
          printf("1. 建立链表\n2. 插入结点\n3. 删除结点\n4. 列表输出\n5. 退出");
                                       /* 屏幕打印选择菜单 */
          c=getchar();                 /* 输入一个击键值赋给 c */
          switch(c) {                  /* 开关选择语句 */
             case ''''''''1'''''''':  creat();       /* 建立链表,见例7.6 */
                        break;         /* 跳出开关语句 */
             case ''''''''2'''''''':  ins();         /* 插入一个新结点,见例7.7 */
                        break;         /* 跳出开关语句 */
             case ''''''''3'''''''':  delete();      /* 删除一个结点,见例7.8 */
                        break;         /* 跳出开关语句 */
             case ''''''''4'''''''':  prt();         /* 屏幕打印链表数据 */
                        break;         /* 跳出开关语句 */
             case ''''''''5'''''''':  exit(0);       /* 退出程序运行 */
          }
          while(getchar()!=''''''''\n'''''''');      /* 吃掉回车符,以免影响下次输入 */
       }
    }

    prt()                              /* 屏幕列表打印链表数据 */
    {
       struct postcode *p;             /* 定义一个结构指针变量(当前结点指针) */
       p=head;                         /* 链表当前结点指针指向链表头 */
       if(head!=NULL) {                /* 如果不是空链表 */
          while(p!=NULL) {             /* 如未超出链尾则继续循环 */
             printf("%ld,%s\n",p->code,p->name);  /* 屏幕打印当前结点数据 */
             p=p->next;                /* 当前结点后移一个结点 */
          }
       }
       else {                          /* 否则为空链表 */
          printf("链表空!");           /* 屏幕打印提示字符串 */
          return;                      /* 返回调用函数 */
       }
    }

    在上面的程序里,先在屏幕上显示一个菜单,键入数字进行选择执行不同的操作。选择是通过开关分支语句来完成的。当选择5时,调用库函数 exit 退出程序运行,回到 DOS 提示符下。习惯约定 exit 后面的参数为0时为正常退出,为其他整数时为非正常退出。
    这里建立了一个把链表列表输出的函数 prt,用一个循环语句来实现逐个结点数据的打印。每打印一个结点的数据后,都把链表的指针后移一个结点。程序通过检查结点的指针是否为 NULL,来判断是否已到链尾,打印完最后一个结点的数据后,跳出循环,结束屏幕打印。
    以上介绍的单向链表的结构里只有一个指向自身的指针。单向链表的缺点在于它只能从一个方向访问链表,而不能反向操作。若在结构中定义多个指向自身结构类型的指针变量,就可以用来构造双向链表和其他链表,以及树、图等数据结构,本书就不作详细叙述了。


相关专题: 我的著作
专题信息:
  C语言速成(第三章 程序控制语句)(2006-1-1 13:51:28)[9642]
  C语言速成(第七章 联合、枚举和自定义数据类型)(2006-1-1 13:51:46)[10355]
  C语言速成(第五章 指针)(2006-1-1 17:28:54)[4777]
  C语言速成(第四章 数组)(2006-1-1 13:52:42)[4937]
  C语言速成(第二章 常量、变量、运算符与表达式)(2006-1-1 13:53:05)[7465]

相关信息:
 没有相关信息
  打印本页
设为首页 | 加入收藏 | 联系我们 | 管理入口
皖ICP备05018956号
Copyright © 2003 J.W.SHEN All Rights Reserved
后台管理系统 V1.0 制作
皖公网安备 34018102340322号