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

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

目录


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


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;
} 


相关文章
|
2月前
|
存储 C语言
C语言:一维数组的不初始化、部分初始化、完全初始化的不同点
C语言中一维数组的初始化有三种情况:不初始化时,数组元素的值是随机的;部分初始化时,未指定的元素会被自动赋值为0;完全初始化时,所有元素都被赋予了初始值。
|
2月前
|
存储 C语言
C语言单链表实现
一个用C语言编写的简单学生信息管理系统,该系统具备信息输入、成绩计算、排序、删除、查找、修改、保存和读取文件等功能。
25 0
C语言单链表实现
|
3月前
|
存储 C语言
【C语言基础考研向】10 字符数组初始化及传递和scanf 读取字符串
本文介绍了C语言中字符数组的初始化方法及其在函数间传递的注意事项。字符数组初始化有两种方式:逐个字符赋值或整体初始化字符串。实际工作中常用后者,如`char c[10]=&quot;hello&quot;`。示例代码展示了如何初始化及传递字符数组,并解释了为何未正确添加结束符`\0`会导致乱码。此外,还讨论了`scanf`函数读取字符串时忽略空格和回车的特点。
|
3月前
|
存储 算法 C语言
数据结构基础详解(C语言):单链表_定义_初始化_插入_删除_查找_建立操作_纯c语言代码注释讲解
本文详细介绍了单链表的理论知识,涵盖单链表的定义、优点与缺点,并通过示例代码讲解了单链表的初始化、插入、删除、查找等核心操作。文中还具体分析了按位序插入、指定节点前后插入、按位序删除及按值查找等算法实现,并提供了尾插法和头插法建立单链表的方法,帮助读者深入理解单链表的基本原理与应用技巧。
596 6
|
3月前
|
存储 算法 C语言
C语言手撕实战代码_循环单链表和循环双链表
本文档详细介绍了用C语言实现循环单链表和循环双链表的相关算法。包括循环单链表的建立、逆转、左移、拆分及合并等操作;以及双链表的建立、遍历、排序和循环双链表的重组。通过具体示例和代码片段,展示了每种算法的实现思路与步骤,帮助读者深入理解并掌握这些数据结构的基本操作方法。
|
3月前
|
算法 C语言 开发者
C语言手撕实战代码_单链表
本文档详细介绍了使用C语言实现单链表的各种基本操作和经典算法。内容涵盖单链表的构建、插入、查找、合并及特殊操作,如头插法和尾插法构建单链表、插入元素、查找倒数第m个节点、合并两个有序链表等。每部分均配有详细的代码示例和注释,帮助读者更好地理解和掌握单链表的编程技巧。此外,还提供了判断子链、查找公共后缀等进阶题目,适合初学者和有一定基础的开发者学习参考。
|
6月前
|
存储 编译器 C语言
C语言学习记录——结构体(声明、初始化、自引用、内存对齐、结构体设计、修改默认对齐数、结构体传参)一
C语言学习记录——结构体(声明、初始化、自引用、内存对齐、结构体设计、修改默认对齐数、结构体传参)一
62 2
|
6月前
|
编译器 Linux C语言
C语言学习记录——结构体(声明、初始化、自引用、内存对齐、结构体设计、修改默认对齐数、结构体传参)二
C语言学习记录——结构体(声明、初始化、自引用、内存对齐、结构体设计、修改默认对齐数、结构体传参)二
53 1
|
6月前
|
存储 人机交互 C语言
【C语言项目实战】使用单链表实现通讯录
【C语言项目实战】使用单链表实现通讯录
|
2月前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
36 3