c 语言 数据结构-链表


一、链表简介

链表也是一种线性表,链表与顺序表最大的不同是链表中的元素可以按照不连续的顺序进行存储,在链表结构中,每一个元素都存储着下一个元素的地址。
链表的特征:
1.1 链表中每一个节点都包含两部分:1 链表的数据域 2 链表的指针域,其中数据域指向链表元素中的数据,指针域则存储下一个链表元素的地址。
1.2 链表元素在逻辑上是一个连续的线性结构,在物理存储上可能不是一个连续的内存空间。
1.3 当我们知道了链表元素中第一个元素的地址,我们就可以通过遍历获取链表中的所有元素。
链表是通过结构体来实现的一种数据结构。


二、定义一个常见的链表结构

typedef struct node{
int a;
struct node *next;

}LN,*LAdd;

LN *a1;
LAdd a1;
//以上两种定义都是定义一个结构体指针。

//建立一个长度为n的链表
LAdd initNode(int n)
{
LAdd a1,b,List =NULL; //a1当前链表 b上一个链表 list链表首地址
int i=0;
for(;ia =n;
a1->next =NULL;
if(!List)
{
List =a1; //将首地址放入变量,准备返回
}else
{
a1->next =b; //将上一个链表的地址放入当前结构体中
}

b=a; //临时变量 记录上一个链表的地址

}

return List;

}


三、向链表中插入节点 删除节点

3.1 链表中插入节点
向链表a中的b元素后面插入节点,节点中元素值info
void insertNode(LAdd a,LAdd b,int info){
LAdd t;
t=(LAdd)malloc(sizeof(LN)); //生成一个新的链表元素
t->a = info;
if(b->next !=NULL) //判断元素b是否为最末尾的节点
{
t->next = b->next; //将元素b所指向的链表赋值给新创建的链表
}
b->next =t; //将元素b指向的链表修改为新创建的元素
}
3.2 链表删除节点
//删除链表a中的 元素b
void delNode(LAdd a,LAdd b){
LAdd t;
if(b ==a)
{
t =a->next; //如果删除的元素为链表的第一个元素,则直接修改指向就可以删除元素
a=t;
free(b);
}else{
//从第一个元素开始遍历和查找元素,直到找到元素b元素为止
t=a;
for(;;)
{
if(t->next == NULL) break;

if(t->next !=b)
{
t=t->next;
}else
{
t->next =b->next;
free(b);
break;
}
}
}
}


四、销毁一个链表

销毁一个链表的原理就是:遍历一个链表,然后依次free;
void delNodeAll(Ladd a){
LAdd t =a;
LAdd t2=a->next;
while(t){
free(t);
t= t2;
t2 =t2->next;
}
a=NULL;
}


五、链表示例


#include "stdio.h"
#include "stdlib.h"

typedef struct Node{
   int a1;
   struct Node *next;
}LN,*LAdd;


LAdd initNode()
 {
   LAdd  a= (LAdd)malloc(sizeof(LN));
   a->a1 = 100;
   a->next =NULL;
   return a;
}

void insert(LAdd a,LAdd p,int info)
{
  
   LAdd t =(LAdd)malloc(sizeof(LN));
   t->a1 =info;
   if(!a){
      a =t;   
   }else
   {
   t->next =p->next;
   p->next =t;
   }
}

void showNode(LAdd a){
   LAdd t = a;
   while(t)
   {
     printf("打印Node信息:%d\n",t->a1);
     t =t->next;
   }
}

void delAllNode(LAdd a)
{
   LAdd b1,b2;
   b1 =a;
   while(!b1){
      b2 =b1->next;
      free(b1);
      b1 =b2;
   }
}

int main()
{
   printf("链表测试:\n");
   //创建一个链表元素
   LAdd a,p;
    a=p=initNode();
   int i=0;
   for(;i<5;i++) 
   insert(a,p,i);
   showNode(a);    
   delAllNode(a);
}

相关阅读:
结构体的定义
c语言typedef 用法