一、循环链表 循环链表是与单链表一样,是一种链式的存储结构,所不同的是,循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点,从而构成一个环形的链。 循环链表的运算与单链表的运算基本一致。所不同的有以下几点: 1、在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。 2、在判断是否到表尾时,是判断该结点链域的值是否是表头结点,当链域值等于表头指针时,说明已到表尾。而非象单链表那样判断链域值是否为NULL。 二、双向链表 双向链表其实是单链表的改进。 当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有 一个存储直接后继结点地址的链域,那么能不能定义一个既有存储直接后继结点地址的链域,又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这就是双向链表。 在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域;一个存储直接前驱结点地址,一般称之为左链域。在c语言中双向链表结点类型可以定义为: typedef struct node { int data; /*数据域*/ struct node *llink, *rlink; /*链域,*llink是左链域指针,*rlink是右链域指针*/ } JD; 当然,也可以把一个双向链表构建成一个双向循环链表。 双向链表与单向链表一样,也有三种基本运算:查找、插入和删除。 双向链表的基本运算: 1、查找 假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时,我们同样从表头结点往后依次比较各结点数据域的值,若正是该特定值,则返回指向结点的指针,否则继续往后查,直到表尾。 下例就是应用双向循环链表查找算法的一个程序。 #include <stdio.h> #include <malloc.h> #define N 10 typedef struct node { char name[20]; struct node *llink,*rlink; }stud; stud * creat(int n) { stud *p, *h, *s; int i; if((h=(stud *)malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } h->name[0]=’\0’; h->llink=NULL; h->rlink=NULL; p=h; for(i=0;i<n;i++) { if((s= (stud *) malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } p->rlink=s; printf("请输入第%d个人的姓名",i+1); scanf("%s",s->name); s->llink=p; s->rlink=NULL; p=s; } h->llink=s; p->rlink=h; return(h); } stud * search(stud *h, char *x) { stud *p; char *y; p=h->rlink; while(p!=h) { y=p->name; if(strcmp(y,x)==0) return(p); else p=p->rlink; } printf("没有查找到该数据!"); } void print(stud *h) { int n; stud *p; p=h->rlink; printf("数据信息为:\n"); while(p!=h) { printf("%s ",&*(p->name)); p=p->rlink; } printf("\n"); } main() { int number; char studname[20]; stud *head, *searchpoint; number=N; clrscr(); head=creat(number); print(head); printf("请输入你要查找的人的姓名:"); scanf("%s", studname); searchpoint=search(head, studname); printf("你所要查找的人的姓名是:%s", *&searchpoint->name); } 2、插入 对于双向循环链表,我们现在可以随意地在某已知结点p前或者p后插入一个新的结点。 假若s,p,q是连续三个结点的指针,若我们要在p前插入一个新结点r,则只需把s的右链域指针指向r,r的左链域指针指向s,r的右链域指针指向p,p的左链域指针指向r即可。 在p,q之间插入原理也一样。 下面就是一个应用双向循环链表插入算法的例子: #include <stdio.h> #include <malloc.h> #include <string.h> #define N 10 typedef struct node { char name[20]; struct node *llink,*rlink; }stud; stud * creat(int n) { stud *p, *h, *s; int i; if((h=(stud *)malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } h->name[0]=’\0’; h->llink=NULL; h->rlink=NULL; p=h; for(i=0;i<n;i++) { if((s= (stud *) malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } p->rlink=s; printf("请输入第%d个人的姓名",i+1); scanf("%s",s->name); s->llink=p; s->rlink=NULL; p=s; } h->llink=s; p->rlink=h; return(h); } stud * search(stud *h, char *x) { stud *p; char *y; p=h->rlink; while(p!=h) { y=p->name; if(strcmp(y,x)==0) return(p); else p=p->rlink; } printf("没有查找到该数据!"); } void print(stud *h) { int n; stud *p; p=h->rlink; printf("数据信息为:\n"); while(p!=h) { printf("%s ",&*(p->name)); p=p->rlink; } printf("\n"); } void insert(stud *p) { char stuname[20]; stud *s; if((s= (stud *) malloc(sizeof(stud)))==NULL) { printf("不能分配内存空间!"); exit(0); } printf("请输入你要插入的人的姓名:"); scanf("%s",stuname); strcpy(s->name,stuname); s->rlink=p->rlink; p->rlink=s; s->llink=p; (s->rlink)->llink=s; } main() { int number; char studname[20]; stud *head, *searchpoint; number=N; clrscr(); head=creat(number); print(head); printf("请输入你要查找的人的姓名:"); scanf("%s", studname); searchpoint=search(head, studname); printf("你所要查找的人的姓名是:%s\n", *&searchpoint->name); insert(searchpoint); print(head); }[url=http://www.bccn.net/Article/kfyy/cyy/jszl/200603/3845.html][/url] 3、删除 删除某个结点,其实就是插入某个结点的逆操作。还是对于双向循环链表,要在连续的三个结点s,p,q中删除p结点,只需把s的右链域指针指向q,q的左链域指针指向s,并收回p结点就完成了。 下面就是一个应用双向循环链表删除算法的例子: #include #include #include #define N 10 typedef struct node { char name[20]; struct node *llink, *rlink; } stud;
循环链表及双向链表
发布日期:2021-09-08 22:55:23
浏览次数:20
分类:技术文章
本文共 3835 字,大约阅读时间需要 12 分钟。
转载于:https://www.cnblogs.com/zzili/archive/2012/12/06/6663381.html
转载地址:https://blog.csdn.net/weixin_34341229/article/details/93423648 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月15日 01时21分46秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
你的 Redis 为什么变慢了?
2019-04-26
我去!微信竟然可以查出行轨迹了,预计又一波情侣要分手?
2019-04-26
阿里云网盘,开放申请啦!非会员下载 10MB/s!有图有真相!
2019-04-26
百度搜出十年前的照片?法院判赔1元~
2019-04-26
云原生收购潮:思科计划收购Portshift;Kasten加入Veeam
2019-04-26
每日一皮:客户期望 vs 最终产品
2019-04-26
面试:说说你对 HashMap 的认识?
2019-04-26
靠,上班打游戏!不,我只是在Minecraft里管理Kubernetes...
2019-04-26
2.5 亿!华为成立新公司!
2019-04-26
B站疯传,一整套Java学习资料,白拿不谢,叫我雷锋!
2019-04-26
超牛逼的 Feed 流系统设计!
2019-04-26
感受 lambda 之美!
2019-04-26
每日一皮:用户“这个项目很容易嘛”~
2019-04-26
面试:GET和POST两种基本请求方法有什么区别
2019-04-26
超卖 100 瓶茅台的事故分析
2019-04-26
为什么阿里如此钟爱Flink?
2019-04-26
一个 Java 对象到底有多大?
2019-04-26
每日一皮:听说学琵琶的都很文弱...
2019-04-26
Spring Security 实战干货:OAuth2授权回调的核心认证流程
2019-04-26
首支完全由 AI 创作的歌曲《未来之歌》发布!对于未来,你方了吗?
2019-04-26