C语言单链表实现初始化、创建、增、删、查等基本操作（详细）

2022-10-10 1124

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 目录一、单链表的定义及初始化1、定义 2、初始化 1)不带头结点的单链表 2)带头节的单链表二、单链表插入和删除1)插入1、按位序插入（带头结点）2、按位插入（不带头结点） 3、指定结点的后插操作 4、指定结点的前插操作2）删除 1、按位序删除（带头结点）2、指定结点删除3、指定最后结点的删除三、查找 1）按位查找2）按值查找四、建立 1）头插法2）尾插法六、补充求单链表长度

一、单链表的定义及初始化

首先介绍一个关键字typedef ——数据类型重命名

typedef < 数据类型> <别名>

typedef struct LNode LNode

1、定义

typedef sturct LNode{                      //定义单链表结点类型      
    ElemType date ;                //每个结点存放一个数据元素
    struct LNode *next;            //指针指向下一个结点
}LNode, *LinkList;
typedef  LNode{                      //定义单链表结点类型      
    ElemType date ;                //每个结点存放一个数据元素
    struct LNode *next;            //指针指向下一个结点
};
typedef struct LNode LNode;
typedef struct LNOde *LinkList;
//上面俩个是等价的
struct LNode *p = (struct LNode*) malloc(sizeof(struct LNode));  /*增加一个新结点：在内存中申请一个结点所需空间，并用指针p指向这个结点 */

要表示一个单链表时，只需要声明一个头指针L，指向单链表的第一个节点

LNode *L ; //声明一个指向单链表第一个结点的指针（强调这是一个结点用LNode*）

或： LinkList L； //声明一个指向单链表的第一个结点的指针（强调这是一个单链表LinkList）

2、初始化

1)不带头结点的单链表

bool InitList(LinkList &L)      //初始化空链表
{
     L = NULL;                 //空表没有任何结点
     return true;           
}
void test()
{
     LinkList L ;         //声明一个指向单链表的指针
     //初始化一个空表
     InitList (L);
}

判断是否为空

bool Empty(LinkList L){
    if(L == NULL)
       return true;
    else 
       return false;
}
//或：
bool Empty(LinkList L){
     return (L == NULL);
}

2)带头节的单链表

//初始化一个单链表（带头结点）
bool InitList (LinkList &L){
     L = (LNode * ) malloc (sizeof(LNode));        //分配一个头结点
     if (L == NULL)                                //内存不足分配失败
        return false; 
     L->next  = NULL;
     return true;
}

判断是否为空

bool Empty(LinkList L){
     if(L->next == NULL)
         return true;
     else 
         return false;
}

二、单链表插入和删除

1)插入

1、按位序插入（带头结点）

//在第i个位置插入元素e
bool ListInsert(LinkList &L, int  i,,ElemType e){
     if( i < 1)
        return false;
     LNode *p;                              //指针p指向当前扫描借点钱
     int j = 0;                             //当前p指向是第几个结点
     p = L;                                 L指向头结点，头结点是第0个结点
     while( p! = NULL && j < i - 1)         //循环找到第i-1个结点
     {   
         p = p->next;
         j ++;
     }
     if(p == NULL)                          //i值不合法
        return false;
     LNode *s = (LNode*)malloc(sizeof(LNode));
     s->date = e;
     s->next = p->next;                    
     p->next = s;                           //将结点s连到p之后 
     return true;
}

2、按位插入（不带头结点）

bool ListInsert(LinkList &L, int  i,,ElemType e){
     if( i < 1)
        return false;
     if(i == 1){
     LNode *s = (LNode *s)malloc(sizeof(LNode));
     s->date = e;
     s->next = L;
     L = s;
     return true;
     } 
     LNode *p;                              //指针p指向当前扫描借点钱
     int j = 0;                             //当前p指向是第几个结点
     p = L;                                 L指向头结点，头结点是第0个结点
     while( p! = NULL && j < i - 1)         //循环找到第i-1个结点
     {   
         p = p->next;
         j ++;
     }
     if(p == NULL)                          //i值不合法
        return false;
     LNode *s = (LNode*)malloc(sizeof(LNode));
     s->date = e;
     s->next = p->next;                    
     p->next = s;                           //将结点s连到p之后 
     return true;
}

3、指定结点的后插操作

bool InsertNextNode (LNode *p ,Elemtype e){
     if( p == NULL)
     return false；
     LNode *s = (LNode *) malloc(sizeof(LNode));
     if (s == NULL)             //内存分配失败
        return false;
     s->date = e;              //用结点s保存数据元素e
     s->next = p->next;
     p->next = s;              //将结点s连接到p之后
     return true;
}

4、指定结点的前插操作

bool InsertPriorNode (LNode *p,ElemType e){
     if(p == NULL)
        return false;
     LNode *s = (LNode *)malloc(sizeof(LNode));
     if(s == NULL) 
        return false;
     s->next = p->next;
     p->next = s;                   //新节点s连到p之后
     s->date = p->date;             //将p之中元素复制到s中
     p->date = e;                   //p中元素覆盖W为e
}
//时间复杂度为O(1)

2）删除

1、按位序删除（带头结点）

//按位序删除（带头结点）
bool ListDelete(LinkList &L,int i,ElemType &e){
  if(i<1) 
    return false;
  LNode *p;                    //指针p指向当前扫描到的节点
  int j = 0;                   // 当前p指向的是第几个节点
  p = L; //L指向头节点，头节点是第0个节点（不存数据）
  while(p!=NULL && j<i-1){     //循环到第i-1个节点 
    p = p->next;
    j++;
  } 
  if(p==NULL) return false; //i值不合法 
  if(p->next == NULL) return false;          //第i-1个节点之后没有其他节点 
  LNode *q = p->next;                       //q指向被删除的节点 
  e = q->data;
  p->next = q->next;
  free(q);
  return true;
}

2、指定结点删除

//指定节点的删除
bool DeleteNode(LNode *p){
  if(p==NULL) return false;
  LNode *q = p->next; //q指向*p的后继节点 
  p->data = p->next->data; //p的后继节点数据赋值给p 
  p->next = q->next; //q节点从链中断开 
  free(q); //释放 
  return true;
}

3、指定最后结点的删除

//指定节点的删除
bool DeleteNode(LNode *p){
  if(p==NULL) return false;
  LNode *q = p->next;              //q指向*p的后继节点 
  p->data = p->next->data;        //p的后继节点数据赋值给p 
  p->next = q->next;             //q节点从链中断开 
  free(q);                      //释放 
  return true;
}

三、查找

1）按位查找

//按位查找，返回第i各元素带头节点
LNode * GetElem(LinkList L,int i){
  if(i<0){
    return NULL;
  }
  LNode *p;                  // 指针p指向当前扫描到的结点
  int j = 0;
  p = L;                    //L指向头结点 , L是第0个结点（不存放数据）
  while(p!=NULL && j < i){   //循环到第i个结点 
    p = p->next;
    j++;
  }
  return p; 
}

2）按值查找

//按值查找，返回e元素
//带头节点
LNode * GetElem(LinkList L,ElemType e){
  LNode *p = L->next;          //从第一个结点开始查找数据域为e的结点
  while(p!=NULL && p->data != e){
    p = p -> next;
  } 
  return p; 
}

四、建立

1）头插法

//头插法 
LinkList List_HeadInsert(LinkList &L){
  int x;  //假设ElemType为整型 
  L = (LinkList)malloc(sizeof(LNode)); //建立头结点 
  LNode  *s;  //r为表尾指针
  L->next = NULL; //初始尾空链表 （必须初始化） 
  scanf("%d",&x);
  while(x!=9999) {
    s = (LNode*)malloc(sizeof(LNode));
    s->next = L->next;
    s->data = x;
    L->next = s;  //头结点指向新的结点 
    scanf("%d",&x); 
  } 
  return L; 
}

2）尾插法

typedef struct LNode{
  int data;
  struct LNode *next; 
}LNode,*LinkList;
//初始化一个单链表（带头节点）
bool InitList(LinkList &L){
  L = (LNode*)malloc(sizeof(LNode));
  if(L == NULL){
    return false; //内存不足分配失败 
  }
  L->next = NULL; //头结点之后暂时没有结点 
  return true; 
} 
//尾插法建立单链表： 初始化单链表长度
/*
  while 循环{
    每次取一个数据元素e
    ListInsert(L,length+1,e) ;
    length++;
  } 
  时间复杂度：O（n2） 
*/ 
LinkList List_TailInsert(LinkList &L){
  int x;  //假设ElemType为整型 
  L = (LinkList)malloc(sizeof(LNode)); //建立头结点 
  LNode  *s,*r=L;  //r为表尾指针
  scanf("%d",&x);
  while(x!=9999) {
    s = (LNode*)malloc(sizeof(LNode));
    s->data = x;
    r->next = s;
    r = s; //r始终指向表尾 
    scanf("%d",&x); 
  }
  r->next = NULL;  //尾结点置空 
  return L; 
} 
int main(){
  LinkList L; //声明一个指向单链表的指针
  InitList(L);//初始化一个空表 
  List_TailInsert(L);
  return 0;
}

六、补充求单链表长度

//求单链表的长度
int Length (LinkList L){
  int len = 0; //统计表长
  LNode *p = L;
  while(p->next != NULL){
    p = p->next;
    len++;
  } 
  return len;
}

C语言单链表实现初始化、创建、增、删、查等基本操作（详细）

目录

一、单链表的定义及初始化

1、定义

2、初始化

二、单链表插入和删除

1)插入

1、按位序插入（带头结点）

2、按位插入（不带头结点）

3、指定结点的后插操作

4、指定结点的前插操作

2）删除

1、按位序删除（带头结点）

2、指定结点删除

3、指定最后结点的删除

三、查找

1）按位查找

2）按值查找

四、建立

1）头插法

2）尾插法

六、补充求单链表长度

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

C语言单链表实现初始化、创建、增、删、查等基本操作（详细）

目录

一、单链表的定义及初始化

1、定义

2、初始化

二、单链表插入和删除

1)插入

1、按位序插入（带头结点）

2、按位插入（不带头结点）

3、指定结点的后插操作

4、指定结点的前插操作

2）删除

1、按位序删除（带头结点）

2、指定结点删除

3、指定最后结点的删除

三、查找

1）按位查找

2）按值查找

四、建立

1）头插法

2）尾插法

六、补充求单链表长度

热门文章

最新文章

相关课程

相关电子书