指針、鏈表的原理和各類操作相關(guān)心得以及學生信息管理系統(tǒng)

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

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

§1 指向結(jié)構(gòu)體變量的指針變量

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

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

§2 指向結(jié)構(gòu)體數(shù)組的指針變量

    指針變量可以指向整型、字符型、浮點型等基本類型數(shù)組。同樣，指針變量也可以指向結(jié)構(gòu)體類型的數(shù)組。

    程序L13_2.C功能：使用指向結(jié)構(gòu)體數(shù)組的指針變量。

#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 鏈表的概念

    鏈表是動態(tài)數(shù)據(jù)結(jié)構(gòu)中最基本的形式，它的規(guī)模大小可以根據(jù)需要進行動態(tài)變化，達到合理地使用存儲空間。

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

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

C系統(tǒng)的庫函數(shù)中提供了動態(tài)申請和釋放內(nèi)存存儲單元的函數(shù)。

    （1）malloc函數(shù)

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

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

    （2）calloc函數(shù)

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

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

    （3）free函數(shù)

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

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

§5 鏈表的相關(guān)操作

    一、建立鏈表

    建立鏈表就是從無到有逐漸增加鏈表結(jié)點的過程，即輸入結(jié)點數(shù)據(jù)，并建立前后鏈接的關(guān)系。

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

struct node *create( )
{ struct node *head, *tail, *p;
int x;
head=tail=NULL;
printf("\n請輸入一個整數(shù)：");
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("請輸入一個整數(shù)：");
scanf("%d",&x);
}
return (head);
}

二、在鏈表中插入結(jié)點

    插入結(jié)點的操作有以下幾種情況：

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

    下面函數(shù)insert (struct node *head, int value)的作用是在已知頭結(jié)點head鏈表中按照從小到大的順序插入數(shù)據(jù)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) /*鏈表非空，插入到第一個結(jié)點前*/
{ new－>next=head;
head=new;
}
else /*鏈表非空，插入到鏈表中間*/
{ q－>next=new;
new－>next=p;
}
}
else /*鏈表非空，插入到鏈表末尾*/
{ p－>next=new;
new－>next=NULL;
}
}
return(head);
}

三、刪除鏈表中的結(jié)點

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

    下面函數(shù)delete(struct node *head, int value)的作用是在已知頭結(jié)點head鏈表中查找一個數(shù)據(jù)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)) /*尋找刪除結(jié)點位置*/
{ q=p; p=p－>next; }
if(value= = p－>data)
{ if(head= =p) head=p－>next; /*刪除鏈表第一個結(jié)點*/
else q－>next=p－>next; /*刪除鏈表結(jié)點*/
free(p);
}
else
printf("此鏈表沒有數(shù)據(jù)%d!\n",value); /*鏈表中無此結(jié)點*/
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) /*建立單鏈表的函數(shù)*/

{

   stud *p,*h,*s;

   int i;

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

   {

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

      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("不能分配內(nèi)存空間!");

        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) /*查找函數(shù)*/

{

   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("沒有查找到該數(shù)據(jù)!");

}

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

/*另一個查找函數(shù)，返回的是上一個查找函數(shù)的直接前驅(qū)結(jié)點的指針，

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

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

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

{

   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("沒有查找到該數(shù)據(jù)!");

}

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

{

   char stuname[20];

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

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

   {

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

     exit(0);

   }

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

   scanf("%s",stuname);

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

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

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

}

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

{

  stud *s;

  s=y;

  x->link=y->link;

  free(s);

}

void print(stud *h)

{

   stud *p;

   p=h->link;

   printf("數(shù)據(jù)信息為：\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語言實現(xiàn)實例\n");

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

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

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

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

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

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

    printf("\t\t| [5] 打 印 數(shù) 據(jù) |\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();

      }

   }

}