7_结构与联合.txt

一些c的经典案例

种规律排好序的。例如，在学生数据链表中， 要求学号顺序插入一
个结点。设被插结点的指针为pi。 可在三种不同情况下插入。1. 原表是空表，只需使head指向被插结点即可。见图7.7(a)2. 被插结点值最小，应插入第一结点之前。这种情况下使head指向
   被插结点，被插结点的指针域指向原来的第一结点则可。即：
    pi->next=pb;
    head=pi;    见图7.7(b)
3. 在其它位置插入，见图7.7(c)。这种情况下，使插入位置的前一
   结点的指针域指向被插结点，使被插结点的指针域指向插入位置
   的后一结点。即为：
    pi->next=pb;
    pf->next=pi；4. 在表末插入，见图7.7(d)。这种情况下使原表末结点指针域指向
   被插结点，被插结点指针域置为NULL。即：
    pb->next=pi;
    pi->next=NULL；    TYPE * insert(TYPE * head,TYPE *pi)
    {
    TYPE *pf,*pb;
    pb=head;
    if(head==NULL)               /*空表插入*/
      (head=pi;
      pi->next=NULL;}
    else
      {
        while((pi->num>pb->num)&&(pb->next!=NULL))
          {pf=pb;
           pb=pb->next;  }/*找插入位置*/
        if(pi->num<=pb->num)
          {if(head==pb)head=pi;/*在第一结点之前插入*/
           else pf->next=pi;/*在其它位置插入*/
            pi->next=pb;  }
        else
          {pb->next=pi;
           pi->next=NULL;}    /*在表末插入*/
      }
    return head;}
    本函数有两个形参均为指针变量，head指向链表，pi 指向被插
结点。函数中首先判断链表是否为空，为空则使head指向被插结点。
表若不空，则用while语句循环查找插入位置。找到之后再判断是否
在第一结点之前插入，若是则使head 指向被插结点被插结点指针域
指向原第一结点，否则在其它位置插入， 若插入的结点大于表中所
有结点，则在表末插入。本函数返回一个指针， 是链表的头指针。
当插入的位置在第一个结点之前时， 插入的新结点成为链表的第一
个结点，因此head的值也有了改变， 故需要把这个指针返回主调函
数。[例7.14]将以上建立链表，删除结点，插入结点的函数组织在一起，
        再建一个输出全部结点的函数，然后用main函数调用它们。#define NULL 0
#define TYPE struct stu
#define LEN sizeof(struct stu)
struct stu
    {
      int num;
      int age;
      struct stu *next;
    };
TYPE * creat(int n)
{
    struct stu *head,*pf,*pb;
    int i;
    for(i=0;i<n;i++)
      {
        pb=(TYPE *)malloc(LEN);
        printf("input Number and  Age\n");
        scanf("%d%d",&pb->num,&pb->age);
        if(i==0)
        pf=head=pb;
        else pf->next=pb;
        pb->next=NULL;
        pf=pb;
      }
    return(head);
}
TYPE * delete(TYPE * head,int num)
{
    TYPE *pf,*pb;
    if(head==NULL)
      { printf("\nempty list!\n");
        goto end;}
    pb=head;
    while (pb->num!=num && pb->next!=NULL)
      {pf=pb;pb=pb->next;}
    if(pb->num==num)
      { if(pb==head) head=pb->next;
          else pf->next=pb->next;
          printf("The node is deleted\n"); }
    else
    free(pb);
      printf("The node not been found!\n");
end:
    return head;
}
TYPE * insert(TYPE * head,TYPE * pi)
{
    TYPE *pb ,*pf;
    pb=head;
    if(head==NULL)
      { head=pi;
      pi->next=NULL; }
    else
    {
    while((pi->num>pb->num)&&(pb->next!=NULL))
      { pf=pb;
        pb=pb->next; }
        if(pi->num<=pb->num)
        { if(head==pb) head=pi;
          else pf->next=pi;
          pi->next=pb; }
        else
          { pb->next=pi;
            pi->next=NULL; }
          }
    return head;
}
void print(TYPE * head)
{
    printf("Number\t\tAge\n");
    while(head!=NULL)
      {
        printf("%d\t\t%d\n",head->num,head->age);
        head=head->next;
      }
}
main()
{
    TYPE * head,*pnum;
    int n,num;
    printf("input number of node:  ");
    scanf("%d",&n);
    head=creat(n);
    print(head);
    printf("Input the deleted number:   ");
    scanf("%d",&num);
    head=delete(head,num);
    print(head);
    printf("Input the inserted number and age:   ");
    pnum=(TYPE *)malloc(LEN);
    scanf("%d%d",&pnum->num,&pnum->age);
    head=insert(head,pnum);
    print(head);
}
    本例中，print函数用于输出链表中各个结点数据域值。函数的
形参head的初值指向链表第一个结点。在while语句中，输出结点值
后，head值被改变，指向下一结点。若保留头指针head， 则应另设
一个指针变量，把head值赋予它，再用它来替代head。
    在main函数中，n为建立结点的数目， num为待删结点的数据域
值；head为指向链表的头指针，pnum为指向待插结点的指针。 main
函数中各行的意义是：
第六行输入所建链表的结点数；
第七行调creat函数建立链表并把头指针返回给head；
第八行调print函数输出链表；
第十行输入待删结点的学号；
第十一行调delete函数删除一个结点；
第十二行调print函数输出链表；
第十四行调malloc函数分配一个结点的内存空间， 并把其地址赋予
pnum;
第十五行输入待插入结点的数据域值；
第十六行调insert函数插入pnum所指的结点；
第十七行再次调print函数输出链表。
    从运行结果看，首先建立起3个结点的链表，并输出其值；再删
103号结点，只剩下105，108号结点；又输入106号结点数据， 插入
后链表中的结点为105，106，108。联合
    “联合”也是一种构造类型的数据结构。 在一个“联合”内可
以定义多种不同的数据类型， 一个被说明为该“联合”类型的变量
中，允许装入该“联合”所定义的任何一种数据。 这在前面的各种
数据类型中都是办不到的。例如， 定义为整型的变量只能装入整型
数据，定义为实型的变量只能赋予实型数据。
    在实际问题中有很多这样的例子。 例如在学校的教师和学生中
填写以下表格：    姓  名    年  龄    职  业    单位    “职业”一项可分为“教师”和“学生”两类。 对“单位”一
项学生应填入班级编号，教师应填入某系某教研室。 班级可用整型
量表示，教研室只能用字符类型。 要求把这两种类型不同的数据都
填入“单位”这个变量中， 就必须把“单位”定义为包含整型和字
符型数组这两种类型的“联合”。
    “联合”与“结构”有一些相似之处。但两者有本质上的不同。
在结构中各成员有各自的内存空间， 一个结构变量的总长度是各成
员长度之和。而在“联合”中，各成员共享一段内存空间， 一个联
合变量的长度等于各成员中最长的长度。应该说明的是， 这里所谓
的共享不是指把多个成员同时装入一个联合变量内， 而是指该联合
变量可被赋予任一成员值，但每次只能赋一种值， 赋入新值则冲去
旧值。如前面介绍的“单位”变量， 如定义为一个可装入“班级”
或“教研室”的联合后，就允许赋予整型值（班级)或字符串（教研
室)。要么赋予整型值，要么赋予字符串，不能把两者同时赋予它。联合类型的定义和联合变量的说明
    一个联合类型必须经过定义之后， 才能把变量说明为该联合类
型。一、联合的定义
定义一个联合类型的一般形式为：    union 联合名  
    {  
      成员表  
    };  成员表中含有若干成员，成员的一般形式为：    类型说明符 成员名  
成员名的命名应符合标识符的规定。例如：    union perdata
    {
      int class;
      char office[10];
    };    定义了一个名为perdata的联合类型，它含有两个成员，一个为
整型，成员名为class；另一个为字符数组，数组名为office。联合
定义之后，即可进行联合变量说明，被说明为perdata类型的变量，
可以存放整型量class或存放字符数组office。
二、联合变量的说明
    联合变量的说明和结构变量的说明方式相同， 也有三种形式。
即先定义，再说明；定义同时说明和直接说明。以perdata类型为例，
说明如下：    union perdata
    {
      int class;
      char officae[10];
    };
    union perdata a,b;    /*说明a,b为perdata类型*/
或者可同时说明为：    union perdata
    { int class;
      char office[10];  }a,b;或直接说明为：    union
    { int class;
      char office[10]; }a,b    经说明后的a,b变量均为perdata类型。 它们的内存分配示意图
如图7—8所示。
    a,b变量的长度应等于 perdata 的成员中最长的长度， 即等于
office数组的长度，共10个字节。从图中可见，a,b变量如赋予整型
值时，只使用了2个字节，而赋予字符数组时，可用10个字节。
 of  Lesson
联合变量的赋值和使用
    对联合变量的赋值，使用都只能是对变量的成员进行。 联合变
量的成员表示为：    联合变量名.成员名  例如，a被说明为perdata类型的变量之后，可使用    a.class
    a.office    不允许只用联合变量名作赋值或其它操作。 也不允许对联合变
量作初始化赋值，赋值只能在程序中进行。
    还要再强调说明的是，一个联合变量， 每次只能赋予一个成员
值。换句话说，一个联合变量的值就是联合变员的某一个成员值。
[例7.15]设有一个教师与学生通用的表格，教师数据有姓名，年龄，
        职业，教研室四项。学生有姓名，年龄，职业，班级四项。
        编程输入人员数据， 再以表格输出。main()
{
    struct
    {
      char name[10];
      int age;
      char job;
      union
        {
          int class;
          char office[10];
        } depa;
    }body[2];
    int n,i;
    for(i=0;i<2;i++)
    {
      printf("input name,age,job and department\n");
      scanf("%s %d %c",body[i].name,&body[i].age,&body[i].job);
      if(body[i].job=='s')
        scanf("%d",&body[i].depa.class);
      else
        scanf("%s",body[i].depa.office);
    }
    printf("name\tage  job  class/office\n");
    for(i=0;i<2;i++)
    {
      if(body[i].job=='s')
      printf("%s\t%3d  %3c  %d\n",body[i].name,body[i].age
,body[i].job,body[i].depa.class);
      else
        printf("%s\t%3d  %3c  %s\n",body[i].name,body[i].age,
               body[i].job,body[i].depa.office);
    }
}
    本例程序用一个结构数组body来存放人员数据， 该结构共有四
个成员。其中成员项depa是一个联合类型， 这个联合又由两个成员
组成，一个为整型量class，一个为字符数组office。在程序的第一
个for语句中，输入人员的各项数据，先输入结构的前三个成员name,
age和job，然后判别job成员项，如为"s"则对联合depa·class输入
(对学生赋班级编号)否则对depa·office输入(对教师赋教研组名)。
在用scanf语句输入时要注意，凡为数组类型的成员，无论是结构成
员还是联合成员，在该项前不能再加"&"运算符。如程序第 18 行中
body[i].name是一个数组类型，第22行中的body[i].depa.office也
是数组类型，因此在这两项之间不能加"&"运算符。程序中的第二个
for语句用于输出各成员项的值：本章小结
1. 结构和联合是两种构造类型数据，是用户定义新数据类型的重要
   手段。结构和联合有很多的相似之处，它们都由成员组成。成员
   可以具有不同的数据类型。成员的表示方法相同。都可用三种方
   式作变量说明。2. 在结构中，各成员都占有自己的内存空间，它们是同时存在的。
   一个结构变量的总长度等于所有成员长度之和。在联合中，所有
   成员不能同时占用它的内存空间，它们不能同时存在。联合变量
   的长度等于最长的成员的长度。3. “.”是成员运算符，可用它表示成员项，成员还可用“->”运
   算符来表示。4. 结构变量可以作为函数参数，函数也可返回指向结构的指针变量。
   而联合变量不能作为函数参数，函数也不能返回指向联合的指针
   变量。但可以使用指向联合变量的指针，也可使用联合数组。
5. 结构定义允许嵌套，结构中也可用联合作为成员，形成结构和联
   合的嵌套。6. 链表是一种重要的数据结构，它便于实现动态的存储分配。本章
   介绍是单向链表，还可组成双向链表，循环链表等。