指针、链表的原理和各类操作相关心得以及学生信息管理系统

       伴随着学期末的到来，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();

      }

   }

}