logo

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

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;

}

​

X
Copyright © 2088 u19男篮世界杯_世界杯在哪看 - xmzohe.com All Rights Reserved.
友情链接