C语言单链表实现初始化、创建、增、删、查等基本操作（详细）
【摘要】 目录一、单链表的定义及初始化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;
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）