用C语言实现单链表的各种操作(一)
更新时间:2020年4月25日 17:46 点击:1729
最近,从新复习了一下数据结构中比较重要的几个部分,现在把自己的成果记录下来,主要就是仿照严蔚敏的《数据结构》(C 语言版),中的例子和后面的习题进行改编的。首先,是单链表的各种实现,其中,包含了一些常考的知识点。例如,单链表的逆置,单链表的合并,找到单链表的中间节点等的算法实现。
下面这个是单链表的结构体的定义:
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;
下面的基本的单链表的操作:其中,有一些宏,没有给出他们的一些定义,者可以通过,严蔚敏的《数据结构》(C 语言版),查看得到。
/* 功能:构建一个空的带头节点的单链表*/
Status InitList (struct LNode **L)
{
(*L) = (struct LNode *)malloc(sizeof(struct LNode)); //产生头节点
if(!*L)
exit(OVERFLOW);
(*L)->next = NULL;
return OK;
}
/*销毁线性表*/
Status DestroyList(struct LNode *L)
{
struct LNode *q;
while(L)
{
q = L->next;
free(L);
L = q;
}
return OK;
}
/*将L重置为空表*/
Status ClearList(struct LNode *L)
{
LinkList *p,*q;
p = L->next;
while(p)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return OK;
}
/*判断链表是否为空表*/
Status ListEmpty(LinkList *L)
{
if(L->next)
{
return FALSE;
}
else
{
return TRUE;
}
}
/*返回单链表中元素的个数*/
int ListLength(struct LNode *L)
{
int i=0;
LinkList *p = L->next;
while(p)
{
i++;
p = p->next;
}
return i;
}
/* L为带头节点的单链表的头指针,当第i个元素存在时,其值赋给e,并返回OK */
Status GetElem(struct LNode *L,int i,ElemType *e)
{
int j=1;
LinkList *p = L->next;
while(p && j<i)
{
p = p->next;
j++;
}
if(!p || j>i)
return ERROR;
*e = p->data;
return OK;
}
/*返回L中第一个与e满足关系compare()的数据元素的位序,
若给存在返回值为0,compare()是数据元素的判定函数*/
int LocateElem(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType))
{
int i =0;
LinkList *p = L->next;
while(p)
{
i++;
if(compare(p->data,e))
return i;
p=p->next;
}
return 0;
}
/*所cur_e是L中的数据元素,且给就第一个,则用pre_e返回它的前驱*/
Status PriorElem(struct LNode *L,ElemType cur_e,ElemType *pre_e)
{
LinkList *q,*p=L->next;
while(p->next)
{
q = p->next;//q指向p的后继
if(q->data == cur_e)
{
*pre_e = p->data;
return OK;
}
p = q;
}
return INFEASIBLE;
}
/* 若cur_e是L中的数据元素,且不是最后一个,则用next_e返回它的后继*/
Status NextElem(struct LNode *L,ElemType cur_e,ElemType *next_e)
{
LinkList *p;
p = L->next;
while(p->next)
{
if(p->data == cur_e)
{
* next_e = p->next->data;
return OK;
}
p = p->next;
}
return INFEASIBLE;
}
/* 在带头节点的单链表L中的第i个位置之前插入元素e*/
Status ListInsert(struct LNode *L,int i,ElemType e)
{
int j =0;
struct LNode *p=L,*s=NULL;
while(p && j<i-1)
{
p=p->next;
j++;
}
if(!p || j>i-1)
return ERROR;
s = (struct LNode *)malloc(sizeof(struct LNode));
if(!s)
printf("malloc error~\n");
// p->next = s;
s->data = e;
// p->next = s;
s->next = p->next;
p->next = s;
//s->next = NULL;
// p = s;
return OK;
}
/*在带头节点的单链表中删除第i个元素,并有e返回其值*/
Status ListDelete(LinkList *L,int i,ElemType *e)
{
LinkList *p=L,*q;
int j=0;
while(p->next && j< i-1)
{
p = p->next;
j++;
}
if(!p->next || j>i-1)
return ERROR;
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
/* 依次对L的每个元素调用vi(),打印输出语句*/
Status ListTraverse(struct LNode *L,void (*vi)(ElemType))
{
LinkList *p = L->next;
while(p)
{
vi(p->data);
p = p->next;
}
printf("\n");
return OK;
}
下面这个是单链表的结构体的定义:
复制代码 代码如下:
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;
下面的基本的单链表的操作:其中,有一些宏,没有给出他们的一些定义,者可以通过,严蔚敏的《数据结构》(C 语言版),查看得到。
复制代码 代码如下:
/* 功能:构建一个空的带头节点的单链表*/
Status InitList (struct LNode **L)
{
(*L) = (struct LNode *)malloc(sizeof(struct LNode)); //产生头节点
if(!*L)
exit(OVERFLOW);
(*L)->next = NULL;
return OK;
}
/*销毁线性表*/
Status DestroyList(struct LNode *L)
{
struct LNode *q;
while(L)
{
q = L->next;
free(L);
L = q;
}
return OK;
}
/*将L重置为空表*/
Status ClearList(struct LNode *L)
{
LinkList *p,*q;
p = L->next;
while(p)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return OK;
}
/*判断链表是否为空表*/
Status ListEmpty(LinkList *L)
{
if(L->next)
{
return FALSE;
}
else
{
return TRUE;
}
}
/*返回单链表中元素的个数*/
int ListLength(struct LNode *L)
{
int i=0;
LinkList *p = L->next;
while(p)
{
i++;
p = p->next;
}
return i;
}
/* L为带头节点的单链表的头指针,当第i个元素存在时,其值赋给e,并返回OK */
Status GetElem(struct LNode *L,int i,ElemType *e)
{
int j=1;
LinkList *p = L->next;
while(p && j<i)
{
p = p->next;
j++;
}
if(!p || j>i)
return ERROR;
*e = p->data;
return OK;
}
/*返回L中第一个与e满足关系compare()的数据元素的位序,
若给存在返回值为0,compare()是数据元素的判定函数*/
int LocateElem(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType))
{
int i =0;
LinkList *p = L->next;
while(p)
{
i++;
if(compare(p->data,e))
return i;
p=p->next;
}
return 0;
}
复制代码 代码如下:
/*所cur_e是L中的数据元素,且给就第一个,则用pre_e返回它的前驱*/
Status PriorElem(struct LNode *L,ElemType cur_e,ElemType *pre_e)
{
LinkList *q,*p=L->next;
while(p->next)
{
q = p->next;//q指向p的后继
if(q->data == cur_e)
{
*pre_e = p->data;
return OK;
}
p = q;
}
return INFEASIBLE;
}
/* 若cur_e是L中的数据元素,且不是最后一个,则用next_e返回它的后继*/
Status NextElem(struct LNode *L,ElemType cur_e,ElemType *next_e)
{
LinkList *p;
p = L->next;
while(p->next)
{
if(p->data == cur_e)
{
* next_e = p->next->data;
return OK;
}
p = p->next;
}
return INFEASIBLE;
}
/* 在带头节点的单链表L中的第i个位置之前插入元素e*/
Status ListInsert(struct LNode *L,int i,ElemType e)
{
int j =0;
struct LNode *p=L,*s=NULL;
while(p && j<i-1)
{
p=p->next;
j++;
}
if(!p || j>i-1)
return ERROR;
s = (struct LNode *)malloc(sizeof(struct LNode));
if(!s)
printf("malloc error~\n");
// p->next = s;
s->data = e;
// p->next = s;
s->next = p->next;
p->next = s;
//s->next = NULL;
// p = s;
return OK;
}
/*在带头节点的单链表中删除第i个元素,并有e返回其值*/
Status ListDelete(LinkList *L,int i,ElemType *e)
{
LinkList *p=L,*q;
int j=0;
while(p->next && j< i-1)
{
p = p->next;
j++;
}
if(!p->next || j>i-1)
return ERROR;
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
/* 依次对L的每个元素调用vi(),打印输出语句*/
Status ListTraverse(struct LNode *L,void (*vi)(ElemType))
{
LinkList *p = L->next;
while(p)
{
vi(p->data);
p = p->next;
}
printf("\n");
return OK;
}
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04