线性表->链式存储->循环链表

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

文字描述

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。

示意图

算法分析

插入、删除、查找等同单链表。

代码实现

//
// Created by lady on 19-1-27.
// #include <stdio.h>
#include <stdlib.h> //线性表的单向循环链表存储结构
typedef struct ElemType{
char data[];
}ElemType;
typedef struct CNode{
ElemType e;
struct CNode *next;
}CNode;
typedef struct {
CNode *head;//指向第一个指针
CNode *tail;//指向最后一个指针
int length;//表示链表数据元素个数
}CLinkNode, *CLinkList; //构造一个空的线性表
static int InitList_CL(CLinkList *L)
{
(*L) = (CLinkList)malloc(sizeof(CLinkNode));
(*L)->length = ;
(*L)->head = NULL;
(*L)->tail = NULL;
} //销毁线性表
static int Destory_CL(CLinkList *L)
{
if(L == NULL || (*L) == NULL){
return -;
}
CNode *p = (*L)->head;
CNode *q;
while(p){
q = p;
p = p->next;
free(q);
if(p == (*L)->head)
break;
}
free(*L);
(*L) = NULL;
} //返回1表示空， 0表示非空
static int ListEmpty_CL(CLinkList L)
{
return L->length ? : ;
} //返回线性表L中的数据元素个数
static int ListLength_CL(CLinkList L)
{
return L->length;
} //在线性表末尾插入数据元素e
static int ListInsert_CL(CLinkList *L,ElemType e)
{
CNode *new = (CNode *)malloc(sizeof(CNode));
if(new == NULL){
return -;
}
CNode *p;
new ->e = e;
new->next = NULL;
if(ListEmpty_CL(*L)){
(*L)->length += ;
new->next = new;
(*L)->head = new;
(*L)->tail = new;
}else{
(*L)->length +=;
new->next = (*L)->head;
(*L)->tail->next = new;
(*L)->tail = new;
}
return ;
} //删除L中的第loc个数据元素，并将被删元素的值存放在e中
static int ListDelete_CL(CLinkList *L, int loc, ElemType *e)
{
CNode *p = (*L)->head;
CNode *q = NULL;
int i = ;
int f = ;
while(p){
if(i == loc){
f = ;
break;
}
i += ;
q = p;
p = p->next;
if(p == (*L)->head){
f = -;
break;
}
}
if(f<)
return -;
(*L)->length -= ;
(*e) = p->e;
if((*L)->length == ){
free(p);
(*L)->head = NULL;
(*L)->tail = NULL;
}
if(q == NULL){
q = p->next;
free(p);
(*L)->tail->next = q;
}else{
q->next = p->next;
free(p);
}
return ;
} //依次对L的每个数据元素调用函数fun
static int ListTraverse_CL(CLinkList L, int (*fun)(ElemType,int), char note[])
{
printf("遍历循环链表%s:", note);
CNode *p = L->head;
int i = ;
while(p){
if(fun(p->e, ++i)){
return -;
}
p = p->next;
if(p == L->head)
break;
}
printf("\n");
return ;
} static int print(ElemType e, int loc)
{
printf("%3d=%-10s", loc, e.data);
return ;
} //创建一个长度为n的链表
static int CreateList_CL(CLinkList *L, int n, char note[])
{
printf("创建一个长度为%d的循环链表%s!\n", n, note);
InitList_CL(L);
ElemType e;
int i = ;
for(i=; i<n; i++){
printf("输入第%d个元素:", i+);
scanf("%s[^\\n]", e.data);
ListInsert_CL(L, e);
}
} int main(int argc, char *argv[])
{
CLinkList L;
ElemType e;
int location = ; CreateList_CL(&L, , "L:");
ListTraverse_CL(L, print, "L"); printf("输入删除元素的位置:");
scanf("%d", &location);
ListDelete_CL(&L, location, &e);
printf("位于%d的元素%s已经从循环链表中被删除！\n", location, e.data);
ListTraverse_CL(L, print, "L"); Destory_CL(&L);
return ;
}

循环链表

代码运行

/home/lady/CLionProjects/untitled/cmake-build-debug/untitled
创建一个长度为5的循环链表L:!
输入第1个元素:WU
输入第2个元素:ZHENG
输入第3个元素:WANG
输入第4个元素:SUN
输入第5个元素:LI
遍历循环链表L: 1=WU 2=ZHENG 3=WANG 4=SUN 5=LI
输入删除元素的位置:2
位于2的元素ZHENG已经从循环链表中被删除！
遍历循环链表L: 1=WU 2=WANG 3=SUN 4=LI Process finished with exit code 0

线性表->链式存储->循环链表的更多相关文章

线性表-&gt&semi;链式存储-&gt&semi;双向链表
文字描述之前的链表(单链表.循环链表)的链式存储结构中只有一个指示直接后继的指针域.由此,从某个结点出发只能顺指针往后寻查其他结点.若要寻查结点的直接前驱,则需从表头指针出发.即单链表中,NextE ...
线性表-&gt&semi;链式存储-&gt&semi;线形链表(单链表)
文字描述: 为了表示前后两个数据元素的逻辑关系,对于每个数据元素,除了存储其本身的信息之外(数据域),还需存储一个指示其直接后继的信息(即直接后继的存储位置,指针域). 示意图: 算法分析: 在单链表 ...
C语言实现线性表(链式存储方式)
#include <stdio.h> #include <stdlib.h> //提供malloc()原型 typedef struct LNode *List; typede ...
C语言线性表链式表结构实现
一个单链式实现的线性表 mList (GCC编译). /** * @brief 线性表的链式实现 (单链表) * @author wid * @date 2013-10-21 * * @note 若代 ...
javascript实现数据结构：线性表--线性链表（链式存储结构）
上一节中, 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单,直观的公式来表示.然后,另一方面来看,这个特点也造成这种存储 ...
c数据结构 -- 线性表之复杂的链式存储结构
复杂的链式存储结构循环链表定义:是一种头尾相接的链表(即表中最后一个结点的指针域指向头结点,整个链表形成一个环) 优点:从表中任一节点出发均可找到表中其他结点注意:涉及遍历操作时,终止条件是判断 ...
c数据结构 -- 线性表之顺序存储结构于链式存储结构（单链表）
线性表定义:线性表是具有相同特性的数据元素的一个有限序列类型: 1:顺序存储结构定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构算法: #include <stdio. ...
[置顶] ※数据结构※&srarr;&star;线性表结构（queue）&star;============优先队列链式存储结构（queue priority list）（十二）
优先队列(priority queue) 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除.在优先队列中,元素被赋予优先级.当访问元素时,具有最高优先级的元素最先删除.优先队列具有 ...
C++编程练习(2)----&OpenCurlyDoubleQuote;实现简单的线性表的链式存储结构&OpenCurlyDoubleQuote;
单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素. 对于查找操作,单链表的时间复杂度为O(n). 对于插入和删除操作,单链表在确定位置后,插入和删除时间仅为O(1). 单链表不需要分配存储 ...

随机推荐

后台js弹提示
StringBuffer sb=new StringBuffer(); try{ sb.append("<script> location.href=\"member_ ...
MFC六大核心机制之一：MFC程序的初始化
很多做软件开发的人都有一种对事情刨根问底的精神,例如我们一直在用的MFC,很方便,不用学太多原理性的知识就可以做出各种窗口程序,但喜欢钻研的朋友肯定想知道,到底微软帮我们做了些什么,让我们在它的框架下 ...
2014多校第四场1006 || HDU 4902 Nice boat （线段树区间更新）
题目链接题意 : 给你n个初值,然后进行两种操作,第一种操作是将(L,R)这一区间上所有的数变成x,第二种操作是将(L,R)这一区间上所有大于x的数a[i]变成gcd(x,a[i]).输出最后n个数 ...
安装ubuntu时的注意事项----个人小总结
今天重装了一次ubuntu,以前是别人帮我装的,而这次是我自己照着网上教程装的. 这个教程还是挺不错的,我就是照着这个装成功的 http://jingyan.baidu.com/article/60c ...
Spring MVC 遇到的一点点问题（转）
今天下午下班之前看了看凯歌给的Spring Training的教程的lab篇,我之前有跟着做没有遇到什么问题,但是到了跟Spring MVC integrating的时候,遇到一点点有趣的事情. 这个 ...
FZU 1896 神奇的魔法数 dp
网上都说是数位dp 但是虽然在队伍里负责动态规划但是数位dp还不会…… 百度了一下发现和最大子序列思路差不多…… 最大子序列的dp[i][j]是表示两个序列前i项和前j项的最大子序列…… dp[i ...
SpringBoot快速开发REST服务最佳实践
一.为什么选择SpringBoot Spring Boot是由Pivotal团队提供的全新框架,被很多业内资深人士认为是可能改变游戏规则的新项目.早期我们搭建一个SSH或者Spring Web应用,需 ...
oracle中创建数据库用户，并授权
--查看表空间文件路径select * from dba_data_files where tablespace_name=$TABLESPACE CREATE TABLESPACE usr_aa D ...
11&period;Python-第三方库requests详解(三）
Response对象使用requests方法后,会返回一个response对象,其存储了服务器响应的内容,如上实例中已经提到的 r.text.r.status_code……获取文本方式的响应体实例: ...
MFC中调用web api
使用COM组件来调用,需要catch com error. IXMLHTTPRequestPtr pIXMLHTTPRequest = NULL; BSTR bstrString = NULL; HR ...