C语言单循环链表的表示与实现实例详解

1.概述:

对于一个循环链表来说,其首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表,可以选择开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法,循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存, 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

指向整个列表的指针可以被称作访问指针。


用单向链表构建的循环链表

循环链表中第一个节点之前就是最后一个节点,反之亦然循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理,区别不大(详见下面实例代码)。当然,如果只会在最后插入数据(或者只会在之前),处理也是很容易的。
另外有一种模拟的循环链表,就是在访问到最后一个节点之后的时候,手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能,在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。

2.程序实现:

/* c2-2.h 线性表的单链表存储结构 */
 struct LNode
 {
  ElemType data;
  struct LNode *next;
 };
 typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */
/* bo2-4.c 设立尾指针的单循环链表(存储结构由c2-2.h定义)的12个基本操作 */
 Status InitList_CL(LinkList *L)
 { /* 操作结果:构造一个空的线性表L */
  *L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
  if(!*L) /* 存储分配失败 */
   exit(OVERFLOW);
  (*L)->next=*L; /* 指针域指向头结点 */
  return OK;
 }
 Status DestroyList_CL(LinkList *L)
 { /* 操作结果:销毁线性表L */
  LinkList q,p=(*L)->next; /* p指向头结点 */
  while(p!=*L) /* 没到表尾 */
  {
   q=p->next;
   free(p);
   p=q;
  }
  free(*L);
  *L=NULL;
  return OK;
 }
 Status ClearList_CL(LinkList *L) /* 改变L */
 { /* 初始条件:线性表L已存在。操作结果:将L重置为空表 */
  LinkList p,q;
  *L=(*L)->next; /* L指向头结点 */
  p=(*L)->next; /* p指向第一个结点 */
  while(p!=*L) /* 没到表尾 */
  {
   q=p->next;
   free(p);
   p=q;
  }
  (*L)->next=*L; /* 头结点指针域指向自身 */
  return OK;
 }
 Status ListEmpty_CL(LinkList L)
 { /* 初始条件:线性表L已存在。操作结果:若L为空表,则返回TRUE,否则返回FALSE */
  if(L->next==L) /* 空 */
   return TRUE;
  else
   return FALSE;
 }
 int ListLength_CL(LinkList L)
 { /* 初始条件:L已存在。操作结果:返回L中数据元素个数 */
  int i=0;
  LinkList p=L->next; /* p指向头结点 */
  while(p!=L) /* 没到表尾 */
  {
   i++;
   p=p->next;
  }
  return i;
 }
 Status GetElem_CL(LinkList L,int i,ElemType *e)
 { /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
  int j=1; /* 初始化,j为计数器 */
  LinkList p=L->next->next; /* p指向第一个结点 */
  if(i<=0||i>ListLength_CL(L)) /* 第i个元素不存在 */
   return ERROR;
  while(j<i)
  { /* 顺指针向后查找,直到p指向第i个元素 */
   p=p->next;
   j++;
  }
  *e=p->data; /* 取第i个元素 */
  return OK;
 }
 int LocateElem_CL(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
 { /* 初始条件:线性表L已存在,compare()是数据元素判定函数 */
  /* 操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。 */
  /*      若这样的数据元素不存在,则返回值为0 */
  int i=0;
  LinkList p=L->next->next; /* p指向第一个结点 */
  while(p!=L->next)
  {
   i++;
   if(compare(p->data,e)) /* 满足关系 */
    return i;
   p=p->next;
  }
  return 0;
 }
 Status PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e)
 { /* 初始条件:线性表L已存在 */
  /* 操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱, */
  /*      否则操作失败,pre_e无定义 */
  LinkList q,p=L->next->next; /* p指向第一个结点 */
  q=p->next;
  while(q!=L->next) /* p没到表尾 */
  {
   if(q->data==cur_e)
   {
    *pre_e=p->data;
    return TRUE;
   }
   p=q;
   q=q->next;
  }
  return FALSE;
 }
 Status NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e)
 { /* 初始条件:线性表L已存在 */
  /* 操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继, */
  /*      否则操作失败,next_e无定义 */
  LinkList p=L->next->next; /* p指向第一个结点 */
  while(p!=L) /* p没到表尾 */
  {
   if(p->data==cur_e)
   {
    *next_e=p->next->data;
    return TRUE;
   }
   p=p->next;
  }
  return FALSE;
 }
 Status ListInsert_CL(LinkList *L,int i,ElemType e) /* 改变L */
 { /* 在L的第i个位置之前插入元素e */
  LinkList p=(*L)->next,s; /* p指向头结点 */
  int j=0;
  if(i<=0||i>ListLength_CL(*L)+1) /* 无法在第i个元素之前插入 */
   return ERROR;
  while(j<i-1) /* 寻找第i-1个结点 */
  {
   p=p->next;
   j++;
  }
  s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
  s->data=e; /* 插入L中 */
  s->next=p->next;
  p->next=s;
  if(p==*L) /* 改变尾结点 */
   *L=s;
  return OK;
 }
 Status ListDelete_CL(LinkList *L,int i,ElemType *e) /* 改变L */
 { /* 删除L的第i个元素,并由e返回其值 */
  LinkList p=(*L)->next,q; /* p指向头结点 */
  int j=0;
  if(i<=0||i>ListLength_CL(*L)) /* 第i个元素不存在 */
   return ERROR;
  while(j<i-1) /* 寻找第i-1个结点 */
  {
   p=p->next;
   j++;
  }
  q=p->next; /* q指向待删除结点 */
  p->next=q->next;
  *e=q->data;
  if(*L==q) /* 删除的是表尾元素 */
   *L=p;
  free(q); /* 释放待删除结点 */
  return OK;
 }
 Status ListTraverse_CL(LinkList L,void(*vi)(ElemType))
 { /* 初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
  LinkList p=L->next->next;
  while(p!=L->next)
  {
   vi(p->data);
   p=p->next;
  }
  printf("\n");
  return OK;
 }
/* main2-4.c 单循环链表,检验bo2-4.c的主程序 */
 #include"c1.h"
 typedef int ElemType;
 #include"c2-2.h"
 #include"bo2-4.c"
 Status compare(ElemType c1,ElemType c2)
 {
  if(c1==c2)
   return TRUE;
  else
   return FALSE;
 }
 void visit(ElemType c)
 {
  printf("%d ",c);
 }
 void main()
 {
  LinkList L;
  ElemType e;
  int j;
  Status i;
  i=InitList_CL(&L); /* 初始化单循环链表L */
  printf("初始化单循环链表L i=%d (1:初始化成功)\n",i);
  i=ListEmpty_CL(L);
  printf("L是否空 i=%d(1:空 0:否)\n",i);
  ListInsert_CL(&L,1,3); /* 在L中依次插入3,5 */
  ListInsert_CL(&L,2,5);
  i=GetElem_CL(L,1,&e);
  j=ListLength_CL(L);
  printf("L中数据元素个数=%d,第1个元素的值为%d。\n",j,e);
  printf("L中的数据元素依次为:");
  ListTraverse_CL(L,visit);
  PriorElem_CL(L,5,&e); /* 求元素5的前驱 */
  printf("5前面的元素的值为%d。\n",e);
  NextElem_CL(L,3,&e); /* 求元素3的后继 */
  printf("3后面的元素的值为%d。\n",e);
  printf("L是否空 %d(1:空 0:否)\n",ListEmpty_CL(L));
  j=LocateElem_CL(L,5,compare);
  if(j)
   printf("L的第%d个元素为5。\n",j);
  else
   printf("不存在值为5的元素\n");
  i=ListDelete_CL(&L,2,&e);
  printf("删除L的第2个元素:\n");
  if(i)
  {
   printf("删除的元素值为%d,现在L中的数据元素依次为:",e);
   ListTraverse_CL(L,visit);
  }
  else
   printf("删除不成功!\n");
  printf("清空L:%d(1: 成功)\n",ClearList_CL(&L));
  printf("清空L后,L是否空:%d(1:空 0:否)\n",ListEmpty_CL(L));
  printf("销毁L:%d(1: 成功)\n",DestroyList_CL(&L));
 }
(0)

相关推荐

  • C语言数据结构之双向循环链表的实例

    数据结构之双向循环链表 实例代码: #include <stdlib.h> #include <stdio.h> #include <malloc.h> typedef struct Node{ struct Node *pNext; int data; struct Node *prior; } NODE,*PNODE; PNODE CreatList(); void TreNode(PNODE pHead); bool isEmpty(PNODE pHead); i

  • C语言中双向链表和双向循环链表详解

    双向链表和双向循环链表 和单向链表相比,多了一个前驱结点.如果他为空,那么next和prior都指向自己.而对于双循环链表,只需要最后一个元素的next指向head->next,head->next的prior指向最后一个节点即可. 插入操作 新节点s插入链表,s->next给p结点,s->prior给p->prior,然后,p->prior->next指向s,p->prior再指向s.顺序需要注意 s->next = p; s->prior =

  • C语言单循环链表的表示与实现实例详解

    1.概述: 对于一个循环链表来说,其首节点和末节点被连接在一起.这种方式在单向和双向链表中皆可实现.要转换一个循环链表,可以选择开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点.再来看另一种方法,循环链表可以被视为"无头无尾".这种列表很利于节约数据存储缓存, 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下. 指向整个列表的指针可以被称作访问指针. 用单向链表构建的循环链表 循环链表中第一个节点之前就是最后一个节点,反之亦然.循环链表的无边界使得在这

  • C语言单向链表的表示与实现实例详解

    1.概述: C语言中的单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始. 链表中最简单的一种是单向链表,它包含两个域,一个信息域和一个指针域.这个链接指向列表中的下一个节点,而最后一个节点则指向一个空值. 如下图所示: 一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接 一个单向链表的节点被分成两个部分.第一个部分保存或者显示关于节点的信息,第二个部分存储下一个节点的地址.单向链表只可向一个方向遍历. 链表最基本的结构是在每个节点

  • Java语言面向对象编程思想之类与对象实例详解

    在初学者学Java的时候,面向对象很难让人搞懂,那么今天小编就来为大家把这个思想来为大家用极为简单的方法理解吧. 首先我们来简单的阐述面向对象的思想. 面向对象: 官方的语言很抽象,我们把官方的解释和定义抛开.想想,自己有什么,对!!我们自己有手脚眼口鼻等一系列的器官.来把自己所具有的器官就可以看作我们的属性,自己是不是可以喜怒哀乐和嬉笑怒骂,这些是不是我们的行为,那么自己的具有的属性加自己有的行为就称为一个对象. 注意!!我们自己,一个个体是一个对象,因为,你是你,我是我,我们虽然有相同的,但

  • C语言实现进制转换函数的实例详解

    C语言实现进制转换函数的实例详解 前言: 写一个二进制,八进制,十六进制转换为十进制的函数 要求: 函数有两个参数,参数(1)是要转换为十进制的进制数,参数(2)是标示参数(1)是什么进制(2,8,16标示二进制,八进制,十六进制). 要有报错信息,比如参数是1012,但参数(2)是2,显然是进制数表示有错误. 系统表 pg_proc 存储关于函数的信息 内部函数在编译之前需要先定义在 pg_proc.h 中,src/include/catalog/pg_proc.h CATALOG(pg_pr

  • C/C++ 双链表之逆序的实例详解

    C/C++ 双链表之逆序的实例详解 一.结点结构 双向链表的数据结构定义如下: typedef struct node { ElemType data; struct node *prior struct node *next; }list; 其中,ElemType可以是任意数据类型如int.float或者char等,在算法中,规定其默认为int类型. 二.带头结点 本文描述的是双向链表逆序,链表逆序需要维护3个指针,分别指向前一个节点.当前节点和下一个节点,具体代码如下: list *reve

  • C语言中 值传递和指针传递实例详解

    C语言中 值传递和指针传递实例详解 在C语言中,函数的参数和返回值的传递方式有两种:值传递和指针传递. 值传递和指针传递初学者总会有一种朦胧的感觉,所以建议把指针传递的概念摸透,才能熟练应用. 值传递示例:x其实是n的一份临时拷贝,所以并不会改变n的值. #include <stdio.h> #include <windows.h> void Fun(int x) { x = 1; } int main() { int n = 2; Fun(n); printf("%d\

  • C语言单链队列的表示与实现实例详解

    1.概述: C语言的队列(queue),是指先进先出(FIFO, First-In-First-Out)的线性表.在具体应用中通常用链表或者数组来实现.队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作. 而单链队列使用链表作为基本数据结果,因此不存在伪溢出的问题,队列长度也没有限制.但插入和读取的时间代价会比较高 2.实例代码: /* 单链队列--队列的链式存储结构 */ typedef struct QNode { QElemType data; struct

  • C语言循环队列的表示与实现实例详解

    1.概述: C语言的队列(queue),是先进先出(FIFO, First-In-First-Out)的线性表数据结构.在具体应用中通常用链表或者数组来实现.队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作. 循环队列可以更简单的防止伪溢出的发生,但是队列大小是固定的. 2.实例代码: /* 队列的顺序存储结构(循环队列) */ #define MAX_QSIZE 5 /* 最大队列长度+1 */ typedef struct { QElemType *base

  • C语言中炫酷的文件操作实例详解

    目录 什么是文件 程序文件 数据文件 (本文重点) 文件名 文件的打开和关闭 文件指针 文件函数 相对路径与绝对路径 输入输出流 二进制读写 fwirte fread 总结 什么是文件 磁盘上的文件是文件 但是在程序设计中,我们一般谈的文件有两种:程序文件和数据文件(从文件功能的角度来分类). 程序文件 包括源程序文件(例如.c文件)目标文件(windows环境后缀为.obj)可执行程序(windos环境后缀为exe). 数据文件 (本文重点) 文件的内容不一定是程序,而是程序运行时读写的数据,

  • C语言main函数的三种形式实例详解

    在C语言中,main()函数有三种形式. 1.无参数 #include <stdio.h> int main(void) { printf("Hello World!\n"); return 0; } 2.有两个参数 习惯上第一个参数是整型argc,保存了外部调用命令的参数个数,第二个参数是指针数组或二级指针argv,以字符串形式保存了与argc对应的参数,如下例子: #include <stdio.h> int main(int argc, char* arg

随机推荐