種規(guī)律排好序的。例如，在學生數(shù)據(jù)鏈表中， 要求學號順序插入一
個結點。設被插結點的指針為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;}
    本函數(shù)有兩個形參均為指針變量，head指向鏈表，pi 指向被插
結點。函數(shù)中首先判斷鏈表是否為空，為空則使head指向被插結點。
表若不空，則用while語句循環(huán)查找插入位置。找到之后再判斷是否
在第一結點之前插入，若是則使head 指向被插結點被插結點指針域
指向原第一結點，否則在其它位置插入， 若插入的結點大于表中所
有結點，則在表末插入。本函數(shù)返回一個指針， 是鏈表的頭指針。
當插入的位置在第一個結點之前時， 插入的新結點成為鏈表的第一
個結點，因此head的值也有了改變， 故需要把這個指針返回主調函
數(shù)。[例7.14]將以上建立鏈表，刪除結點，插入結點的函數(shù)組織在一起，
        再建一個輸出全部結點的函數(shù)，然后用main函數(shù)調用它們。#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函數(shù)用于輸出鏈表中各個結點數(shù)據(jù)域值。函數(shù)的
形參head的初值指向鏈表第一個結點。在while語句中，輸出結點值
后，head值被改變，指向下一結點。若保留頭指針head， 則應另設
一個指針變量，把head值賦予它，再用它來替代head。
    在main函數(shù)中，n為建立結點的數(shù)目， num為待刪結點的數(shù)據(jù)域
值；head為指向鏈表的頭指針，pnum為指向待插結點的指針。 main
函數(shù)中各行的意義是：
第六行輸入所建鏈表的結點數(shù)；
第七行調creat函數(shù)建立鏈表并把頭指針返回給head；
第八行調print函數(shù)輸出鏈表；
第十行輸入待刪結點的學號；
第十一行調delete函數(shù)刪除一個結點；
第十二行調print函數(shù)輸出鏈表；
第十四行調malloc函數(shù)分配一個結點的內存空間， 并把其地址賦予
pnum;
第十五行輸入待插入結點的數(shù)據(jù)域值；
第十六行調insert函數(shù)插入pnum所指的結點；
第十七行再次調print函數(shù)輸出鏈表。
    從運行結果看，首先建立起3個結點的鏈表，并輸出其值；再刪
103號結點，只剩下105，108號結點；又輸入106號結點數(shù)據(jù)， 插入
后鏈表中的結點為105，106，108。聯(lián)合
    “聯(lián)合”也是一種構造類型的數(shù)據(jù)結構。 在一個“聯(lián)合”內可
以定義多種不同的數(shù)據(jù)類型， 一個被說明為該“聯(lián)合”類型的變量
中，允許裝入該“聯(lián)合”所定義的任何一種數(shù)據(jù)。 這在前面的各種
數(shù)據(jù)類型中都是辦不到的。例如， 定義為整型的變量只能裝入整型
數(shù)據(jù)，定義為實型的變量只能賦予實型數(shù)據(jù)。
    在實際問題中有很多這樣的例子。 例如在學校的教師和學生中
填寫以下表格：    姓  名    年  齡    職  業(yè)    單位    “職業(yè)”一項可分為“教師”和“學生”兩類。 對“單位”一
項學生應填入班級編號，教師應填入某系某教研室。 班級可用整型
量表示，教研室只能用字符類型。 要求把這兩種類型不同的數(shù)據(jù)都
填入“單位”這個變量中， 就必須把“單位”定義為包含整型和字
符型數(shù)組這兩種類型的“聯(lián)合”。
    “聯(lián)合”與“結構”有一些相似之處。但兩者有本質上的不同。
在結構中各成員有各自的內存空間， 一個結構變量的總長度是各成
員長度之和。而在“聯(lián)合”中，各成員共享一段內存空間， 一個聯(lián)
合變量的長度等于各成員中最長的長度。應該說明的是， 這里所謂
的共享不是指把多個成員同時裝入一個聯(lián)合變量內， 而是指該聯(lián)合
變量可被賦予任一成員值，但每次只能賦一種值， 賦入新值則沖去
舊值。如前面介紹的“單位”變量， 如定義為一個可裝入“班級”
或“教研室”的聯(lián)合后，就允許賦予整型值（班級)或字符串（教研
室)。要么賦予整型值，要么賦予字符串，不能把兩者同時賦予它。聯(lián)合類型的定義和聯(lián)合變量的說明
    一個聯(lián)合類型必須經(jīng)過定義之后， 才能把變量說明為該聯(lián)合類
型。一、聯(lián)合的定義
定義一個聯(lián)合類型的一般形式為：    union 聯(lián)合名  
    {  
      成員表  
    };  成員表中含有若干成員，成員的一般形式為：    類型說明符 成員名  
成員名的命名應符合標識符的規(guī)定。例如：    union perdata
    {
      int class;
      char office[10];
    };    定義了一個名為perdata的聯(lián)合類型，它含有兩個成員，一個為
整型，成員名為class；另一個為字符數(shù)組，數(shù)組名為office。聯(lián)合
定義之后，即可進行聯(lián)合變量說明，被說明為perdata類型的變量，
可以存放整型量class或存放字符數(shù)組office。
二、聯(lián)合變量的說明
    聯(lián)合變量的說明和結構變量的說明方式相同， 也有三種形式。
即先定義，再說明；定義同時說明和直接說明。以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    經(jīng)說明后的a,b變量均為perdata類型。 它們的內存分配示意圖
如圖7—8所示。
    a,b變量的長度應等于 perdata 的成員中最長的長度， 即等于
office數(shù)組的長度，共10個字節(jié)。從圖中可見，a,b變量如賦予整型
值時，只使用了2個字節(jié)，而賦予字符數(shù)組時，可用10個字節(jié)。
 of  Lesson
聯(lián)合變量的賦值和使用
    對聯(lián)合變量的賦值，使用都只能是對變量的成員進行。 聯(lián)合變
量的成員表示為：    聯(lián)合變量名.成員名  例如，a被說明為perdata類型的變量之后，可使用    a.class
    a.office    不允許只用聯(lián)合變量名作賦值或其它操作。 也不允許對聯(lián)合變
量作初始化賦值，賦值只能在程序中進行。
    還要再強調說明的是，一個聯(lián)合變量， 每次只能賦予一個成員
值。換句話說，一個聯(lián)合變量的值就是聯(lián)合變員的某一個成員值。
[例7.15]設有一個教師與學生通用的表格，教師數(shù)據(jù)有姓名，年齡，
        職業(yè)，教研室四項。學生有姓名，年齡，職業(yè)，班級四項。
        編程輸入人員數(shù)據(jù)， 再以表格輸出。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);
    }
}
    本例程序用一個結構數(shù)組body來存放人員數(shù)據(jù)， 該結構共有四
個成員。其中成員項depa是一個聯(lián)合類型， 這個聯(lián)合又由兩個成員
組成，一個為整型量class，一個為字符數(shù)組office。在程序的第一
個for語句中，輸入人員的各項數(shù)據(jù)，先輸入結構的前三個成員name,
age和job，然后判別job成員項，如為"s"則對聯(lián)合depa·class輸入
(對學生賦班級編號)否則對depa·office輸入(對教師賦教研組名)。
在用scanf語句輸入時要注意，凡為數(shù)組類型的成員，無論是結構成
員還是聯(lián)合成員，在該項前不能再加"&"運算符。如程序第 18 行中
body[i].name是一個數(shù)組類型，第22行中的body[i].depa.office也
是數(shù)組類型，因此在這兩項之間不能加"&"運算符。程序中的第二個
for語句用于輸出各成員項的值：本章小結
1. 結構和聯(lián)合是兩種構造類型數(shù)據(jù)，是用戶定義新數(shù)據(jù)類型的重要
   手段。結構和聯(lián)合有很多的相似之處，它們都由成員組成。成員
   可以具有不同的數(shù)據(jù)類型。成員的表示方法相同。都可用三種方
   式作變量說明。2. 在結構中，各成員都占有自己的內存空間，它們是同時存在的。
   一個結構變量的總長度等于所有成員長度之和。在聯(lián)合中，所有
   成員不能同時占用它的內存空間，它們不能同時存在。聯(lián)合變量
   的長度等于最長的成員的長度。3. “.”是成員運算符，可用它表示成員項，成員還可用“->”運
   算符來表示。4. 結構變量可以作為函數(shù)參數(shù)，函數(shù)也可返回指向結構的指針變量。
   而聯(lián)合變量不能作為函數(shù)參數(shù)，函數(shù)也不能返回指向聯(lián)合的指針
   變量。但可以使用指向聯(lián)合變量的指針，也可使用聯(lián)合數(shù)組。
5. 結構定義允許嵌套，結構中也可用聯(lián)合作為成員，形成結構和聯(lián)
   合的嵌套。6. 鏈表是一種重要的數(shù)據(jù)結構，它便于實現(xiàn)動態(tài)的存儲分配。本章
   介紹是單向鏈表，還可組成雙向鏈表，循環(huán)鏈表等。