指針、鏈表的原理和各類操作相關心得以及學生信息管理系統

       伴隨著學期末的到來，C語言程序設計這門課也接近尾聲。經過前兩次的教學，我們對C語言也有了深刻的了解，學習的內容也不斷的加深。這次我們就學習了C語言程序設計里應用最廣泛，也是最難學習的知識——鏈表和指針的應用。

       關于指針和鏈表這兩個的應用和上次的管理系統有著直接的關系，沒有添加鏈表和指針的管理系統無法做到精確的查找。數據存儲方面也顯得不方便。所以指針和鏈表的作用能夠直接指向你所需要的數據地址，使程序更加完善。這次我就利用指針的應用制作了一個管理員工工資等信息的程序。

§1 指向結構體變量的指針變量

    指向結構體變量的指針變量的定義形式與一般指針變量的定義形式相同，只是將其指向類型定義為結構體類型即可。例如：
        struct person
            { charname[20];
             char sex;
             int age;
             float height;
            };
       struct person *p;
則指針變量p，它可以指向struct person類型的結構體變量。

    將一個指針變量指向一個結構體變量后，可以利用指向該結構體的的指針變量引用成員，如：
        （* 指針變量名）．成員名
以上形式也常寫成：
        指針變量名－>成員名
其中，－>為指向運算符，它是由符號“－”和“>”兩部分構成的。指向運算符的優先級和成員運算符相同，也是最高一級。

§2 指向結構體數組的指針變量

    指針變量可以指向整型、字符型、浮點型等基本類型數組。同樣，指針變量也可以指向結構體類型的數組。

    程序L13_2.C功能：使用指向結構體數組的指針變量。

#include <stdio.h>
void main()
{ struct person
{ char name[20];
char sex;
int age;
float height;
}per[3]={{ "Li Ping", 'M ',20,175},
{"Wang Ling", 'F ',19,162.5},
{"Zhao Hui", 'M ',20,178}};
struct person *p;
for (p=per;p<per+3;p++)
printf("%–18s%3c%4d%7.1f\n ", p－>name, p－>sex, p－>age, p－>height);
}

§3 鏈表的概念

    鏈表是動態數據結構中最基本的形式，它的規模大小可以根據需要進行動態變化，達到合理地使用存儲空間。

    鏈表有一個“頭指針”變量，用來指向鏈表的第一個元素。鏈表中的每個元素都稱為“結點”，結點包含兩部分內容：一是實際的數據信息；二是下一結點的指針，。鏈表的最后一個元素置為“NULL”（空地址），標志鏈表結束。

    一個結點可以用一個結構體類型來描述。結構體中包含若干成員，用來表示結點的數據信息。此外必須有一個成員是與結點類型一致的指針，用來指向后續結點。例如，一個鏈表的結點可以定義為以下的結構體類型：
        struct node
            { int data1;
             float data2;
             struct node *next;
            };
其中，成員next是指向結點的指針變量，它指向next所在的struct node結構體類型數據。

C系統的庫函數中提供了動態申請和釋放內存存儲單元的函數。

    （1）malloc函數

    malloc函數的原型為：
        void *malloc(unsigned int size)

    函數的功能是：在動態存儲區域中分配一個size字節的連續空間。函數的返回值為指針，它的值是所分配的存儲區域的起始地址。如沒有足夠的存儲空間分配，則返回0（記為NULL）值。

    （2）calloc函數

    calloc函數的原型為：
        void *calloc(unsigned int n,unsigned int size)

    函數的功能是：在動態存儲區域中分配n個為size字節的連續空間，并將該存儲空間自動置初值0。函數的返回值為指針，它的值是所分配的存儲區域的起始地址。如分配不成功，則返回0值。

    （3）free函數

    free函數的原型為：
        void free(void *ptr)

    函數的功能是：釋放由ptr所指向的存儲空間。ptr的值必須是malloc或calloc函數返回的地址。此函數無返回值。

§5 鏈表的相關操作

    一、建立鏈表

    建立鏈表就是從無到有逐漸增加鏈表結點的過程，即輸入結點數據，并建立前后鏈接的關系。

    下面是建立鏈表的函數creat() ：

struct node *create( )
{ struct node *head, *tail, *p;
int x;
head=tail=NULL;
printf("\n請輸入一個整數：");
scanf("%d",&x);
while(x!=0)
{ p=(struct node *)malloc(sizeof(struct node));
p－>data=x;
p－>next=NULL;
if (head= = NULL)
head=tail=p;
else
{ tail－>next=p;
tail=p;
}
printf("請輸入一個整數：");
scanf("%d",&x);
}
return (head);
}

二、在鏈表中插入結點

    插入結點的操作有以下幾種情況：

（1）鏈表是空鏈表，插入的結點作為鏈表的第一個結點。
（2）鏈表非空，結點插入到鏈表的第一個結點前，使插入的結點成為鏈表第一個結點。
（3）鏈表非空，結點插入到鏈表的末尾，使插入的結點成為鏈表最后一個結點。
（4）鏈表非空，結點插入到鏈表中間某個結點之后。

    下面函數insert (struct node *head, int value)的作用是在已知頭結點head鏈表中按照從小到大的順序插入數據value。

struct node *insert(struct node *head, intvalue )
{
struct node *new, *p, *q;
new=(struct node *)malloc(sizeof(struct node));
new－>data=value;
p=head;
if(head= =NULL) /*鏈表是空鏈表*/
{ head=new; 
new－>next=NULL; 
}
else
{ while((p－>next !=NULL) &&(p－>data<value)) /*尋找插入位置*/
{ q=p; p=p－>next; }
if(p－>data>=value)
{ if(head= =p) /*鏈表非空，插入到第一個結點前*/
{ new－>next=head;
head=new;
}
else /*鏈表非空，插入到鏈表中間*/
{ q－>next=new;
new－>next=p;
}
}
else /*鏈表非空，插入到鏈表末尾*/
{ p－>next=new;
new－>next=NULL;
}
}
return(head);
}

三、刪除鏈表中的結點

    從鏈表中刪除結點，是指把該結點從鏈表中分離出來，即改變鏈表的鏈接關系。從鏈表中刪除的結點有兩種處理情況：一是調用函數free（）來釋放該結點所占的存儲空間，將它從內存中刪除；二是將該結點插入到其它鏈表中等待處理。

    下面函數delete(struct node *head, int value)的作用是在已知頭結點head鏈表中查找一個數據value，并從鏈表中刪除。

struct node *delete(struct node *head, intvalue )
{ struct node *p, *q;
p=head;
if(head= =NULL) /*鏈表是空鏈表*/
{ printf("這是一個空鏈表!\n"); return(head); }
while((p－>next !=NULL) &&(p－>data!=value)) /*尋找刪除結點位置*/
{ q=p; p=p－>next; }
if(value= = p－>data)
{ if(head= =p) head=p－>next; /*刪除鏈表第一個結點*/
else q－>next=p－>next; /*刪除鏈表結點*/
free(p);
}
else
printf("此鏈表沒有數據%d!\n",value); /*鏈表中無此結點*/
return(head);
}

源代碼

#include <stdio.h>  

#include <conio.h>  

#include <string.h>  

#include <stdlib.h>

#define N 3

typedef struct node

{

   char name[20];

   struct node *link;

}stud;

stud * creat(int n) /*建立單鏈表的函數*/

{

   stud *p,*h,*s;

   int i;

   if((h=(stud *)malloc(sizeof(stud)))==NULL)

   {

      printf("不能分配內存空間!");

      exit(0);

   }

   h->name[0]='\0';

   h->link=NULL;

   p=h;

   for(i=0;i<N;i++)

   {

     if((s= (stud *) malloc(sizeof(stud)))==NULL)

     {

        printf("不能分配內存空間!");

        exit(0);

     }

     p->link=s;

     printf("請輸入第%d個人的姓名:",i+1);

     scanf("%s",s->name);

     s->link=NULL;

     p=s;

   }

   return(h);

}

stud * search(stud *h,char *x) /*查找函數*/

{

   stud *p;

   char *y;

   p=h->link;

   while(p!=NULL)

   {

     y=p->name;

     if(strcmp(y,x)==0)

       return(p);

     else p=p->link;

   }

   if(p==NULL)

     printf("沒有查找到該數據!");

}

stud * search3(stud *h,char *x) 

/*另一個查找函數，返回的是上一個查找函數的直接前驅結點的指針，

h為表頭指針，x為指向要查找的姓名的指針

其實此函數的算法與上面的查找算法是一樣的，只是多了一個指針s，并且s總是指向指針p所指向的結點的直接前驅，

結果返回s即是要查找的結點的前一個結點*/

{

   stud *p,*s;

   char *y;

   p=h->link;

   s=h;

   while(p!=NULL)

   {

     y=p->name;

     if(strcmp(y,x)==0)

       return(s);

     else

     {

       p=p->link;

       s=s->link;

     }

   }

   if(p==NULL)

    printf("沒有查找到該數據!");

}

void insert(stud *p) /*插入函數，在指針p后插入*/

{

   char stuname[20];

   stud *s; /*指針s是保存新結點地址的*/

   if((s= (stud *) malloc(sizeof(stud)))==NULL)

   {

     printf("不能分配內存空間!");

     exit(0);

   }

   printf("請輸入你要插入的人的姓名:");

   scanf("%s",stuname);

   strcpy(s->name,stuname); /*把指針stuname所指向的數組元素拷貝給新結點的數據域*/

   s->link=p->link; /*把新結點的鏈域指向原來p結點的后繼結點*/

   p->link=s; /*p結點的鏈域指向新結點*/

}

void del(stud *x,stud *y) /*刪除函數，其中y為要刪除的結點的指針，x為要刪除的結點的前一個結點的指針*/

{

  stud *s;

  s=y;

  x->link=y->link;

  free(s);

}

void print(stud *h)

{

   stud *p;

   p=h->link;

   printf("數據信息為：\n");

   while(p!=NULL)

   {

     printf("%s \n",&*(p->name));

     p=p->link;

   }

}

void quit()

{

  exit(0);

}

void menu(void)

{

    system("cls"); 

    printf("\t\t\t單鏈表C語言實現實例\n");

    printf("\t\t|----------------|\n");

    printf("\t\t| |\n");

    printf("\t\t| [1] 建 立 新 表 |\n");

    printf("\t\t| [2] 查 找 數 據 |\n");

    printf("\t\t| [3] 插 入 數 據 |\n");

    printf("\t\t| [4] 刪 除 數 據 |\n");

    printf("\t\t| [5] 打 印 數 據 |\n");

    printf("\t\t| [6] 退 出 |\n");

    printf("\t\t| |\n");

    printf("\t\t| 如未建立新表，請先建立！ |\n");

    printf("\t\t| |\n");

    printf("\t\t|----------------|\n");

    printf("\t\t 請輸入你的選項(1-6):");

}

main()

{

    int choose;

    stud *head,*searchpoint,*forepoint;

    char fullname[20];

    while(1)

    {

      menu();

      scanf("%d",&choose);

      switch(choose)

      {

        case 1:

           head=creat(N);

           break;

        case 2:

  printf("輸入你所要查找的人的姓名:");

           scanf("%s",fullname);

           searchpoint=search(head,fullname);

           printf("你所查找的人的姓名為:%s",*&searchpoint->name);

           printf("\n按回車鍵回到主菜單。");

           getchar();getchar();

           break;

        case 3: printf("輸入你要在哪個人后面插入:");

           scanf("%s",fullname);

           searchpoint=search(head,fullname);

           printf("你所查找的人的姓名為:%s",*&searchpoint->name);

           insert(searchpoint);

           print(head);

           printf("\n按回車鍵回到主菜單。");

           getchar();getchar();

           break;

        case 4:

  print(head);

           printf("\n輸入你所要刪除的人的姓名:");

           scanf("%s",fullname);

           searchpoint=search(head,fullname);

           forepoint=search3(head,fullname);

           del(forepoint,searchpoint);

           break;

        case 5:

  print(head);

           printf("\n按回車鍵回到主菜單。");

           getchar();getchar();

           break;

        case 6:quit();

           break;

        default:

  printf("你輸入了非法字符!按回車鍵回到主菜單。");

           system("cls"); 

           menu();

           getchar();

      }

   }

}