学习心得:C语言实现链表的操作超详细

简介: 学习心得:C语言实现链表的操作超详细

1240

今天将给大家讲述链表的学习心得。学习数据结构,毋庸置疑链表必须学好,后面的栈、队列、树、图都是以链表为基础的;链表的种类很多,有单链表、双链表、循环链表、非循环链表;在此,我们以非循环单链表为例,来讲链表的创建、求长度、排序、插入和排序。

1.什么是链表

链表我的理解要包含以下特征:

(1).由n个节点离散分配;

(2).每个节点通过指针连接

(3)每一个节点由一个前驱节点和一个后驱节点

(4).首节点没有前驱节点,尾节点没有后驱节点;

满足上面的4条,我们就称为链表;链表既然由很多个节点,那节点又由什么组成?节点由两个部分组成,一是数据域,用来存放有效数据;二是指针域,用来指向下一个节点;下面用C语言来构建链表数据结构,首先应该构造出节点,然后再把所有的节点连起来,就构成了链表;

(1)节点的构造

typedef struct Node

{

int data;//数据域,用来存放数据域;

struct Node *pNext;//定义一个结构体指针,指向下一次个与当前节点数据类型相同的节点

}NODE,*PNODE; //NODE等价于 struct Node; PNODE等价于struct Node *; 此处用大写是为了与变量区分,可以让人容易变出是个数据类型

typedef 只是给数据类型取个别名,即 typedef 数据类型 别名;我们知道struct Node 是我们定义的数据类型;

(2)链表的创建

在创建链表之前,我们需要需要了解一下专业术语:

首节点:存放第一个有效数据的节点;

尾节点:存放最后一个有效数据的节点;

头节点:头节点的数据类型与首节点的数据类型相同,并且头节点是首节点前面的那个节点,并不存放有效数据;头节点的存在只是为了方便链表的操作。

头指针:指向头节点的指针;

尾指针:指向尾节点的指针;

首先,我们应该创建一个头节点,并用头指针指向它,用C语言描述:用malloc向计算机申请一块内存,并定义一个指向与头节点数据类型相同的指针(一定要判断申请内存是否成功);

然后,要知道要创建链表的长度,用一个循环来每次创建一个节点,并把每个节点连在一起;

1240

假如我们要在头节点phead后面插入节点p:

(1)把头节点的指针域指向P节点,即pHead->pNext=p;

(2)把p节点的指针域指向NULL,即p->pNext=NULL;

这样就可以了吗? 想想我们就可以发现,当我们要插入多个节点时,头节点始终指向最后添加的一个数据,以前的节点通过头指针此时已经找不到了;我们定义一个尾指针pTail,始终用来指向链表的结尾,每次只在pTail后面添加节点。

伪算法:

(1)定义一个尾指针pTail,并初始化,使它指向头节点,即pTail=pHead;

(2)在pTail后面添加节点,修改指针:

pTail->pNext=p;

p->pNext=NULL;

pTail=p; //使pTail指向链表最后一个元素

PNODE Create_List(void)

{

int len; //存放链表的长度

int i; //循环变量

int val;//用来临时存放用户输入的结点的值

PNODE List;

PNODE pHead=(PNODE)malloc(sizeof(NODE));//分配一个头节点

if(NULL==pHead)

{

printf("Memory allocation failure");

exit(-1);

}

else

{ PNODE pTail=pHead;

pHead->pNext=NULL;

printf("please input the length of list: "); //需要一个指针始终指向链表的结尾

scanf("%d",&len);

for(i=0;i

{

PNODE p=(PNODE)malloc(sizeof(NODE));

if(NULL==p)

{

printf("Memory allocation failure");

exit(-1);

}

else

{

printf("please input the value of list: ");

scanf("%d",&val);

p->data=val;

pTail->pNext=p;

p->pNext=NULL;

pTail=p;

}

}

}

return pHead;

}


1240

小编给大家推荐一个学习氛围超好的地方,C/C++交流企鹅裙:870963251!适合在校大学生,小白,想转行,想通过这个找工作的加入。裙里有大量学习资料,有大神解答交流问题,每晚都有免费的直播课程


2.向链表中插入元素

1240

假如要在节点2的前面插入节点p,我们首先要找到节点2的前驱节点1,假设现在q指针指向节点1,则

(1)p->pNext=q->pNext;

(2)q->pNext=p;

程序代码如下:

//链表的第pos有效元素前面插入元素val,首先我们应该找到第pos个元素前面一个元素的位置;

//当链表有3个元素时,pos=4,将不会进行插入操作

bool Insert_List(PNODE pHead,int pos,int val)

{

int i=0;

PNODE p=pHead;

while((NULL!=p)&&(i

{

p=p->pNext;

i++;

}

if(p==NULL||i>pos-1) //把链表为空的情况考虑进去了;i>pos-1 可以防止用户输入错误;

return false;

//程序执行到这之后,i=pos-1;p指针指向链表第pos个有效节点的前驱,即指向第pos-1节点;

PNODE q=(PNODE)malloc(sizeof(NODE));

q->data=val;

q->pNext=p->pNext;

p->pNext=q;

}


1240

3.删除链表中的元素

1240

假如要删除节点2,只需要把节点1指针域指针指向节点3,但不要忘记释放节点2所占的内存,否则将会造成内存泄漏;首先必须找到节点2的前驱节点1,假设p指向节点1。

(1)q=p->pNext; //首先用q保存要删除节点的地址;

(2)p->pNext=q->pNext; //q->pNext=p->pNext->pNext; 修改指针使节点1指向节点3;

(3)free(q); //释放节点2所占的内存;

bool Delete_List(PNODE pHead,int pos,int *val)

{

int i=0;

PNODE p=pHead;

while((NULL!=p)&&(i

{

p=p->pNext;

i++;

}

if(p==NULL||i>pos-1) //把链表为空的情况考虑进去了;i>pos-1 可以防止用户输入错误;

return false;

//程序执行到这之后,i=pos-1;

PNODE q=p->pNext; //q指向待删除的节点;

*val=q->data;

p->pNext=q->pNext; //修改链表指针指向;

free(q); //释放q所指向节点的内存;

q=NULL;//千万不可以忘记,否则会出现野指针;

}


1240

4.链表元素的排序

快速排序和冒泡排序的思想对于链表这个数据结构同样适用,下面是一个用选择排序来实现链表的排序;

//链表有效元素的个数

int Length_List(PNODE pHead)

{ int len=0; //定义变量要记得初始化;

PNODE p=pHead->pNext;

while(NULL!=p)

{

len++;

p=p->pNext;

}

return len;

}

//对链表中的元素进行排序

void Sort_List(PNODE pHead)

{

int i,j;

int temp;

int len=Length_List(pHead);

PNODE p,q;//指向链表第一个有效元素

for(i=0,p=pHead->pNext;ipNext);i++,p=p->

{

for(j=i+1,q=p->pNext;jpNext);j++,q=q->

{

//交换数据

if(p->data>q->data)

{

temp=p->data;

p->data=q->data;

q->data=temp;

}

}

}

}

和数组排序很像,只是这里需要两个指针p、q不停地移动,来获取链表中的数据元素;

相关文章
|
19天前
|
C语言
对链表使用插入排序的C语言实现示例
对链表使用插入排序的C语言实现示例
|
1月前
|
存储 编译器 C语言
初识C语言——详细入门(系统性学习day4)
初识C语言——详细入门(系统性学习day4)
|
1月前
|
Linux C语言
Linux系统下C语言的队列操作
Linux系统下C语言的队列操作
23 0
|
1月前
|
编译器 程序员 开发工具
c语言从入门到实战——在系统学习C语言之前所需要了解的知识
C语言是一种通用的、过程式的计算机编程语言,支持结构化编程、词汇变量作用域和递归等功能,其设计提供了低级别的存取权限,并且要求程序员管理所有的内存细节。C语言的基本构成包括数据类型(如整型、浮点型、字符型等)、运算符(如算术运算符、关系运算符、逻辑运算符等)、控制结构(如顺序结构、选择结构、循环结构等)以及函数等。此外,C语言还提供了指针的概念,这是其他许多编程语言所不具备的。指针是一个变量,其值为另一个变量的地址,通过指针可以间接访问和操作内存中的数据。C语言也支持数组、结构体、联合体等复合数据类型,以及文件操作、动态内存分配等高级功能。
51 0
|
1月前
|
存储 C语言
通俗易懂的学习C语言中输入一组数并找出其最大值
通俗易懂的学习C语言中输入一组数并找出其最大值
|
1月前
|
C语言
C语言循环链表讲解
C语言循环链表讲解
19 0
|
3天前
|
存储 C语言
C语言中字符串的引用与数组元素操作
C语言中字符串的引用与数组元素操作
12 0
|
1月前
|
存储 C语言 索引
在C语言中静态链表
在C语言中静态链表
17 1
|
1月前
|
存储 算法 C语言
在C语言中的动态链表
在C语言中的动态链表
9 0
|
1月前
|
前端开发 C语言
c语言中的链表
c语言中的链表
9 1