vlambda博客
学习文章列表

一、链表概述

1.数组：静态分配存储单元，容易造成内存浪费。

2.链表：是重要的数据结构，它根据需要，动态分配内存单元 。

⊙数据部分：可有若干项（整、实、字符、结构体类型等）

4.链表各结点的特点：

⊙链表的每个结点实际上是一个结构体变量，它有若干成员组成，包括的内容有两部分：

--数据部分：整、实、字符、结构体等类型。

二、简单链表

例：建立简单链表，它由3个学生数据的结点组成。

               输出各结点中的数据。 

#include <stdio.h>

#define   NULL    0 

struct  student 

{long num; float  score; struct  student *next; }; 

void main(  ) 

{struct   student  a,b,c,*head,*p; 

 a.num=99101;a.score=89.5; b.num=99102;b.score=90; 

 c.num=99103;c.score=85; head=&a;a.next=&b;b.next=&c; 

 c.next=NULL; p=head; 

 do  { printf(“%ld  %5.1f\n”,pnum,pscore); 

          p=pnext; 

        }while(p!=NULL); 

}

 P!=NULL条件不成立，循环结束。

 本例所有结点是在程序中定义的，不是临时开辟的，用完也不能释放，这种链表称“静态链表”。

三、处理动态链表所需的函数

为处理动态链表，C提供了开辟和释放存储单元的函数：

1.malloc函数

⊙函数原型：void  *malloc(unsigned  int  size);

2.calloc函数

⊙函数原型：void  *calloc(unsigned n,unsigned  size);

3.free函数

⊙函数原型：void  free(void  *p);

⊙作用：释放由p指向的内存区，使这部分内存区能被其它变量使用。P所指向的是最近一次calloc或malloc分配的存储区域。free函数无返回值。 

4.注：旧版本提供的malloc和calloc函数得到的是指向字符型数据的指针。

四、建立动态链表

1.建立动态链表：是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。 

例：写一函数建立一个有3名学生数据的单向动态链表。 

思路：

⑴ 设置3个指针变量head、p1、p2

head：指向链表头的指针变量，初始化head=NULL。

p2：指向结点成员next的指针变量。

⑵ 循环方式用malloc函数开辟第1个结点。n=1

输入数据，如果p1num !=0，

                    则head=p1结点链入链表，反之不链入。

⑶ 开辟第2个结点：n=2

输入数据。

如果p1num !=0，链入2结点，

方法：p2next=p1

⑷ 为建立第3个结点做准备：

p2=p1，腾出p1 。

⑸ 重复⑶⑷两步开辟第3个结点，并链入链表。 

⑹ 再开辟新结点，由于num数据为0，退出循环。

并使p2next=NULL，虽然p1指向新结点但没有链入链表。 

1.

#include  “stdio.h”

#include  “malloc.h”

#define  NULL   0 

#define  LEN   sizeof (struct   student) 

struct   student 

 {long  num;  float   score;   struct  student  *next; }; 

int  n;

struct student *creat(void) 

{ struct student  *head;  struct student  *p1, *p2;  

   n=0; p1=p2=(struct student  *) malloc(LEN); 

   scanf(“%ld,%f”,&p1  num, &p1  score); 

   head=NULL; 

  while(p1  num !=0) 

     {n=n+1; 

         if(n==1)head=p1; 

         else  p2  next=p1; 

       p2=p1; p1=(struct  student  *)malloc (LEN); 

       scanf(“%ld,%f”,&p1  num, & p1  score); } 

  p2  next=NULL;  return(head); 

}

2.

#include  “stdio.h”          /*改进后*/

#include  “stdlib.h”

#define  NULL   0 

#define  LEN   sizeof (struct   student) 

struct   student 

 {long  num;  float   score;   struct  student  *next; }; 

int  n;

struct student *creat(void) 

{ struct student  *head;  struct student  *p1, *p2; flot  s; 

   n=0; p1=p2=(struct student  *) malloc(LEN); 

   scanf(“%ld,%f”,&p1  num,&s); p1  score=s; 

   head=NULL; 

  while(p1  num !=0) 

     {n=n+1; 

         if(n==1)head=p1; 

         else  p2  next=p1; 

       p2=p1; p1=(struct  student  *)malloc (LEN); 

       scanf(“%ld ,%f”,&p1  num,&s); p1  score=s; } 

  p2  next=NULL;  return(head); 

}

五、输出链表

思路：

例：写一个输出链表的函数print。 

六、对链表的删除操作

并不真从内存中抹掉，只是把它分离，再前后结点相链接。 

例：  写一函数删除动态链表中指定的结点。 

思路：本例以学号作为删除结点的标志（查找对象）。

⑴ 设两个指针变量p1和p2。从head开始，p1依次指向各结点查找num值是否等于要删除结点的学号。每次下移前使p2=p1。学号相等删除该结点，直至查到表尾。

⑵找到要删除的结点后：

①如果要删除的是第1结点，则head=p1next 。head指向第二结点，第一结点脱离。

②如果要删除的不是第1结点，则p2next=p1next 。P1指向的结点脱离。

③还要考虑链表为空和链表中没有要删除的结点的情况。

struct  student  *del(struct student *head,long num)

{ struct  student   *p1,*p2; 

   if(head = = NULL) {printf(“\n  list  null ! \n”); goto  end; } 

   p1=head; 

   while(num !=p1  num && p1  next != NULL) 

        { p2=p1; p1=p1  next; } 

   if(num == p1  num) 

     { if(p1 = = head) head=p1  next; 

        else p2  next = p1  next; 

        printf(“delete: %d\n”,num); 

        n=n-1; 

     } 

   else printf(“%ld  not  been  found ! \n”,num); 

   return(head); 

}

七、对链表的插入操作

1.假设结点按成员的学号从小到大排列，按排序顺序插入结点。

2.将一个结点插入到链表中算法： 

八、对链表的综合操作

1.用main函数作主调函数，调用前述建立、输出、删除、插入结点的函数。 

共用体