C语言单向链表的表示与实现实例详解
2023-06-13 09:15:37 时间
1.概述:
C语言中的单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。
链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值。
如下图所示:
一个单向链表包含两个值:当前节点的值和一个指向下一个节点的链接
一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
链表最基本的结构是在每个节点保存数据和到下一个节点的地址,在最后一个节点保存一个特殊的结束标记,另外在一个固定的位置保存指向第一个节点的指针,有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点,一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来,然后直接访问。当然如果只是访问数据就没必要了,不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个节点。
相对于双向链表,这种普通的,每个节点只有一个指针的链表也叫单向链表,或者单链表,通常用在每次都只会按顺序遍历这个链表的时候(例如图的邻接表,通常都是按固定顺序访问的)。
2.程序实现:
/*c2-2.h线性表的单链表存储结构*/ structLNode { ElemTypedata; structLNode*next; }; typedefstructLNode*LinkList;/*另一种定义LinkList的方法*/
/*bo2-2.c单链表线性表(存储结构由c2-2.h定义)的基本操作(12个)*/ StatusInitList(LinkList*L) {/*操作结果:构造一个空的线性表L*/ *L=(LinkList)malloc(sizeof(structLNode));/*产生头结点,并使L指向此头结点*/ if(!*L)/*存储分配失败*/ exit(OVERFLOW); (*L)->next=NULL;/*指针域为空*/ returnOK; } StatusDestroyList(LinkList*L) {/*初始条件:线性表L已存在。操作结果:销毁线性表L*/ LinkListq; while(*L) { q=(*L)->next; free(*L); *L=q; } returnOK; } StatusClearList(LinkListL)/*不改变L*/ {/*初始条件:线性表L已存在。操作结果:将L重置为空表*/ LinkListp,q; p=L->next;/*p指向第一个结点*/ while(p)/*没到表尾*/ { q=p->next; free(p); p=q; } L->next=NULL;/*头结点指针域为空*/ returnOK; } StatusListEmpty(LinkListL) {/*初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE*/ if(L->next)/*非空*/ returnFALSE; else returnTRUE; } intListLength(LinkListL) {/*初始条件:线性表L已存在。操作结果:返回L中数据元素个数*/ inti=0; LinkListp=L->next;/*p指向第一个结点*/ while(p)/*没到表尾*/ { i++; p=p->next; } returni; } StatusGetElem(LinkListL,inti,ElemType*e)/*算法2.8*/ {/*L为带头结点的单链表的头指针。当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR*/ intj=1;/*j为计数器*/ LinkListp=L->next;/*p指向第一个结点*/ while(p&&j<i)/*顺指针向后查找,直到p指向第i个元素或p为空*/ { p=p->next; j++; } if(!p||j>i)/*第i个元素不存在*/ returnERROR; *e=p->data;/*取第i个元素*/ returnOK; } intLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType)) {/*初始条件:线性表L已存在,compare()是数据元素判定函数(满足为1,否则为0)*/ /*操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。*/ /*若这样的数据元素不存在,则返回值为0*/ inti=0; LinkListp=L->next; while(p) { i++; if(compare(p->data,e))/*找到这样的数据元素*/ returni; p=p->next; } return0; } StatusPriorElem(LinkListL,ElemTypecur_e,ElemType*pre_e) {/*初始条件:线性表L已存在*/ /*操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,*/ /*返回OK;否则操作失败,pre_e无定义,返回INFEASIBLE*/ LinkListq,p=L->next;/*p指向第一个结点*/ while(p->next)/*p所指结点有后继*/ { q=p->next;/*q为p的后继*/ if(q->data==cur_e) { *pre_e=p->data; returnOK; } p=q;/*p向后移*/ } returnINFEASIBLE; } StatusNextElem(LinkListL,ElemTypecur_e,ElemType*next_e) {/*初始条件:线性表L已存在*/ /*操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继,*/ /*返回OK;否则操作失败,next_e无定义,返回INFEASIBLE*/ LinkListp=L->next;/*p指向第一个结点*/ while(p->next)/*p所指结点有后继*/ { if(p->data==cur_e) { *next_e=p->next->data; returnOK; } p=p->next; } returnINFEASIBLE; } StatusListInsert(LinkListL,inti,ElemTypee)/*算法2.9。不改变L*/ {/*在带头结点的单链线性表L中第i个位置之前插入元素e*/ intj=0; LinkListp=L,s; while(p&&j<i-1)/*寻找第i-1个结点*/ { p=p->next; j++; } if(!p||j>i-1)/*i小于1或者大于表长*/ returnERROR; s=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/ s->data=e;/*插入L中*/ s->next=p->next; p->next=s; returnOK; } StatusListDelete(LinkListL,inti,ElemType*e)/*算法2.10。不改变L*/ {/*在带头结点的单链线性表L中,删除第i个元素,并由e返回其值*/ intj=0; LinkListp=L,q; while(p->next&&j<i-1)/*寻找第i个结点,并令p指向其前趋*/ { p=p->next; j++; } if(!p->next||j>i-1)/*删除位置不合理*/ returnERROR; q=p->next;/*删除并释放结点*/ p->next=q->next; *e=q->data; free(q); returnOK; } StatusListTraverse(LinkListL,void(*vi)(ElemType)) /*vi的形参类型为ElemType,与bo2-1.c中相应函数的形参类型ElemType&不同*/ {/*初始条件:线性表L已存在*/ /*操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败*/ LinkListp=L->next; while(p) { vi(p->data); p=p->next; } printf("\n"); returnOK; }
/*algo2-5.c主程序*/ #include"c1.h" typedefintElemType; #include"c2-2.h" #include"bo2-2.c" voidCreateList(LinkList*L,intn)/*算法2.11*/ {/*逆位序(插在表头)输入n个元素的值,建立带表头结构的单链线性表L*/ inti; LinkListp; *L=(LinkList)malloc(sizeof(structLNode)); (*L)->next=NULL;/*先建立一个带头结点的单链表*/ printf("请输入%d个数据\n",n); for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/ scanf("%d",&p->data);/*输入元素值*/ p->next=(*L)->next;/*插入到表头*/ (*L)->next=p; } } voidCreateList2(LinkList*L,intn) {/*正位序(插在表尾)输入n个元素的值,建立带表头结构的单链线性表*/ inti; LinkListp,q; *L=(LinkList)malloc(sizeof(structLNode));/*生成头结点*/ (*L)->next=NULL; q=*L; printf("请输入%d个数据\n",n); for(i=1;i<=n;i++) { p=(LinkList)malloc(sizeof(structLNode)); scanf("%d",&p->data); q->next=p; q=q->next; } p->next=NULL; } voidMergeList(LinkListLa,LinkList*Lb,LinkList*Lc)/*算法2.12*/ {/*已知单链线性表La和Lb的元素按值非递减排列。*/ /*归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列*/ LinkListpa=La->next,pb=(*Lb)->next,pc; *Lc=pc=La;/*用La的头结点作为Lc的头结点*/ while(pa&&pb) if(pa->data<=pb->data) { pc->next=pa; pc=pa; pa=pa->next; } else { pc->next=pb; pc=pb; pb=pb->next; } pc->next=pa?pa:pb;/*插入剩余段*/ free(*Lb);/*释放Lb的头结点*/ Lb=NULL; } voidvisit(ElemTypec)/*ListTraverse()调用的函数(类型要一致)*/ { printf("%d",c); } voidmain() { intn=5; LinkListLa,Lb,Lc; printf("按非递减顺序,"); CreateList2(&La,n);/*正位序输入n个元素的值*/ printf("La=");/*输出链表La的内容*/ ListTraverse(La,visit); printf("按非递增顺序,"); CreateList(&Lb,n);/*逆位序输入n个元素的值*/ printf("Lb=");/*输出链表Lb的内容*/ ListTraverse(Lb,visit); MergeList(La,&Lb,&Lc);/*按非递减顺序归并La和Lb,得到新表Lc*/ printf("Lc=");/*输出链表Lc的内容*/ ListTraverse(Lc,visit); }
相关文章
- linux tree命令,Linux tree命令实例详解
- C语言实例|使用C程序优雅地杀掉其它程序进程
- linux防火墙状态查看的方法实例
- Linux下快速新建数据库实例操作指南(linux新建数据库实例)
- Oracle两表连接查询实例(oracle两个表连接)
- Oracle 监听实例的设置与配置方法详解(oracle监听实例)
- C语言连接Oracle数据库拖管库实例解析(c连接oracle拖管库)
- C语言编程与Oracle数据库交互实例(c oracle编程示例)
- Sqlserver2000数据库备份实例代码
- C语言编写银行打印程序实例参考
- Android控件Gallery3D效果实例代码
- C#拓展方法的简单实例
- C语言解压华为固件的实例代码
- javascriptjq弹出层实例
- C语言中的回调函数实例
- 在Golang中使用C语言代码实例
- php中Array2xml类实现数组转化成XML实例
- C语言安全之数组长度与指针实例解析
- C语言线性表的顺序表示与实现实例详解
- 使用Nodejs开发微信公众号后台服务实例
- C语言中qsort函数用法实例小结
- C语言的递归思想实例分析
- C语言连续子向量的最大和及时间度量实例
- C语言实现图的遍历之深度优先搜索实例