目录

一、分类

1.静态链表

（1）使用条件：

（2）实例：

2.动态链表（用各个函数来实现----模块化思想）

（1）函数要求

（2）功能：链表的建立、插入、删除

一、分类

1.静态链表

（1）使用条件：

链表长度固定且结点个数较少时使用

（2）实例：

《注：静态链表 就是以  结构体  为结点组成的链表 结构体中 包含 数据域  和指针域  指针域用  指向下一个结点》

#include
struct student
{
    int num;
    char name[20];
    float score;
    struct student * next;
};
void main()
{
    struct student a = { 1011,"zhangsan",562},b = { 1012,"lisi",520},c = { 1013,"wangyusheng",542};
    struct student *head,*p;
    head = &a;
    a.next = &b;
    b.next = &c;
    c.next = NULL;
    for (p = head;p!=NULL; p= p->next)
    {
        printf("%5d %8s %6.1fn",p->num,p->name,p->score);
    }
}

 注：在静态链表中就是将一个结构体来当做一个结点 ，以此来实现静态链表的组成

2.动态链表（用各个函数来实现----模块化思想）

（1）函数要求

<1> malloc 函数

函数原型： void * malloc（unsinged size）

功能：在内存中动态存储区中分配 size字节的连续空间 ，成功时：返回值为分配存储区的起始地址  分配不成功时：返回 null

实例：

char *p;
p = (char*) malloc (8);

<2> calloc 函数

函数原型：void * calloc（unsinged  n ,unsinged unsinged size）

功能：在内存的动态存储区中分配n个长度size 字节的连续空间，成功时：返回值为分配存储区的起始地址  分配不成功时：返回 null

例如：

char *p;
p = (char * p) calloc (2,20);

<3>free 函数

函数原型：void free（void * p）

功能：释放p所指向的内存空间

int n ,*p;
scanf("%d",&n);
p = (int * ) malloc ( n * sizeof(int));
free ( p );

（2）功能：链表的建立、插入（头插法、尾插法）、删除

<1>链表的建立

思想：开辟N个结点，没开辟一个结点，每个结点都让p1指向新节点，p2 指向当前的表尾结点，把p1所指向的节点连接到p2所指向结点的后面

实例：

#include 
struct student * create(int n )
{
 struct student * head =NULL,*p1,*p2;
 int i;
 for (i = 1;i <= n; i ++)
 {
  p1 = (struct student *) malloc (sizeof (struct student));
  printf("请输入第%d 个学生的学号和成绩：n",i);
  scanf("%d%f",&p1 ->num,&p1-> score);
  p1 ->next= NULL;
  if (i == 1):
    head = p1;
  else
    p2 -> next = p1;
   p2 = p1;
 }
return(head);
}

<2> 链表的动态删除

想法：

要删除一个结点，只需要从第一个结点出发沿着链表搜索，找到待删除的点后，修改该节点的前驱结点（前一个结点）的指针域，使其指向待删除结点的后继结点（后一个结点）

 实例：（删除指定学号的学生结点，以头指针和学号作为参数）

#include
struct student * del(struct student *head,int num)
{
    struct student *p1,*p2;
    if (head == NULL)
    {
        printf("原链表为空！ n");
        return (NULL);
    }
    else
    {
        p1 = head;
        while(p1->num != num  &&  p1->next != NULL)
        {
            p2 = p1;
            p1 = p1->next;
        }
        if (p1->num == num)
        {
            if (p1 == head)
                head = p1->next;
            else
                p2->next = p1->next;
            printf("学号为 %d 的学生已经被删除！n",num)
        }
        else
            printf("学号为 %d 的学生不存在！ n",num);
    }
    return (head);
};

<3>链表的插入

  头插法

  思路：将新的结点插入已知的链表的第一个结点之前

  例如：

template 
node *Inser_head(node*list , T value)
{
    node *pnode;
    pnode = new node;
    pnode ->value = value;
    pnode ->next = list->next;
    if (list ->next != nullptr)
        list->next->prev = pnode;
    pnode->next = list;
    list->next = pnode;
    return pnode;
}

尾插法

思路：

保存一个末尾指针，插入时先将末尾指针所指向的结点的后继设置为新的结点，然后更新末尾指针为新的结点

例如：

template
node *insert_tail(node*list,T value,node*tail)
{
    node *pnode;
    pnode = new node;
    pnode ->next= nullptr;
    pnode->value = value;
    tail->next = pnode;
    return pnode;
}