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


相关文章
|
1月前
|
C语言
链栈的初始化以及用C语言表示进栈、出栈和判断栈空
链栈的初始化以及用C语言表示进栈、出栈和判断栈空
21 3
|
1月前
|
存储 编译器 C语言
【数据结构】C语言实现单链表万字详解(附完整运行代码)
【数据结构】C语言实现单链表万字详解(附完整运行代码)
55 0
|
18天前
|
存储 编译器 C语言
C语言学习记录——结构体(声明、初始化、自引用、内存对齐、结构体设计、修改默认对齐数、结构体传参)一
C语言学习记录——结构体(声明、初始化、自引用、内存对齐、结构体设计、修改默认对齐数、结构体传参)一
22 2
|
18天前
|
编译器 Linux C语言
C语言学习记录——结构体(声明、初始化、自引用、内存对齐、结构体设计、修改默认对齐数、结构体传参)二
C语言学习记录——结构体(声明、初始化、自引用、内存对齐、结构体设计、修改默认对齐数、结构体传参)二
19 1
|
1月前
|
编译器 C语言 C++
从C语言到C++⑦(第二章_类和对象_下篇)初始化列表+explicit+static成员+友元+内部类+匿名对象(上)
从C语言到C++⑦(第二章_类和对象_下篇)初始化列表+explicit+static成员+友元+内部类+匿名对象
16 1
|
26天前
|
存储 算法 编译器
C语言中的二维数组:定义与初始化技术详解
C语言中的二维数组:定义与初始化技术详解
40 0
|
26天前
|
存储 编译器 C语言
C语言指针变量的定义与初始化技术详解
C语言指针变量的定义与初始化技术详解
26 0
|
26天前
|
存储 C语言 索引
C语言一维数组的定义与初始化技术详解
C语言一维数组的定义与初始化技术详解
29 0
|
1月前
|
Java 编译器 C语言
从C语言到C++⑦(第二章_类和对象_下篇)初始化列表+explicit+static成员+友元+内部类+匿名对象(下)
从C语言到C++⑦(第二章_类和对象_下篇)初始化列表+explicit+static成员+友元+内部类+匿名对象
16 0
|
1月前
|
C语言 C++
从C语言到C++⑦(第二章_类和对象_下篇)初始化列表+explicit+static成员+友元+内部类+匿名对象(中)
从C语言到C++⑦(第二章_类和对象_下篇)初始化列表+explicit+static成员+友元+内部类+匿名对象
29 0