《数据结构》第2章 表（C语言描述）

2024-08-30 13:32
文章标签 语言 数据结构 描述

本文主要是介绍《数据结构》第2章 表（C语言描述），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

2.1线性表

数据结构指的是数据元素及数据元素之间的相互关系，包含下面三方面的内容：

表1

这里写图片描述

其中，线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。

特征：

  • 集合中必存在唯一的一个“第一元素”；
  • 集合中必存在唯一的一个 “最后元素” ；
  • 除最后一个元素之外，均有 唯一的后继(后件)；
  • 除第一个元素之外，均有 唯一的前驱(前件)；

线性表作为一种基本的数据结构类型，在计算机存储器的映像（或表示）一般有两种形式：

  • 顺序映像—即我们常用的数组；
  • 链式映像—即我们常用的链表。

1）顺序存储结构的特点

  • 逻辑上相邻的元素 A ( i ) A ( i + 1 ) A(i) A(i+1) A(i)A(i+1)，其存储位置也是相邻的；
  • 对数据元素 A ( i ) A(i) A(i)的存取为随机存取或地址存取。
  • 存储密度高。存储密度D=（数据结构中的元素所占存储空间）/(整个数据结构所占空间)

2）顺序存储结构的不足
对表的插入和删除等运算的时间复杂度较差。
3）顺序存储结构的表示
在C语言中，一维数组的元素也是存放于一片连续的存储空间中，故可借助于C语言中一维数组类型来描述线性表的存储结构，即

#define N 100  
typedef int data_t;//这样定义的目的是为了代码便于维护，如果下次表中数据类型为char，修改比较方便；  
typedef struct  
{  data_t data[N];//表的存储空间  int last;//当前表尾指针，对我们对数据的定位起到很大的作用  
}sqlist_t,*sqlink_t;//顺序表类型

指针 L 指向一个顺序表,我们的数据{a0,a1,a2… last};

sqlink_t L;  
L = (sqlink_t *)malloc(sizeof(sqlink_t));

这里我们定义的 int last ，可以表示{ } 、{ a0 }、{a0,a1}、{a0,a1…a99};ai可以表示为 L->data[i] (0<=i<=L->last)，一般情况下，0 < L->last < N，如果是空表{ }，此时L->last = -1;
下面我们通过一个实例来看线性表基本算法的相关算法如何使用：
seqlist.h

#ifndef _SEQ_LIST_H_  
#define _SEQ_LIST_H_  
typedef int data_t;
#define MAX 100  
typedef struct {  
data_t  data[MAX];  
/***************************** 
*pointer to the position  
* in the array 'data' where  
* stores the last element of 
* the list 
*****************************/  
int last;  
} seqlist_t;  
seqlist_t *CreateEmptySqlist();  
void DestroySqlist(seqlist_t *list);  
void ClearSqlist(seqlist_t *list);  
int EmptySqlist(seqlist_t *list);  
int FullSqlist(seqlist_t *list);  
int LengthSqlist(seqlist_t *list);  
int GetSqlist(seqlist_t *list, int at, data_t *x);  
int SetSqlist(seqlist_t *list, int at, data_t x);  
int InsertSqlist(seqlist_t *list, int at, data_t x);  
int DeleteSqlist(seqlist_t *list, int at);  
#endif /* _SEQ_LIST_H_ */

seqlist.c

#include <stdio.h>  
#include <stdlib.h>  
#include "seqlist.h"  /**************************************************create a list and init it as empty  *Input : void *Output: void *Return: new list, NULL when failed  *************************************************/  
seqlist_t *CreateEmptySqlist()  
{seqlist_t *list;  list = (seqlist_t *)malloc(sizeof(seqlist_t));  if(list != NULL)  {list->last = -1;//list->last初始化，空表中，list-last = -1;  }  return list;  
}  /**************************************************destroy a list  *Input : the list to be destroied.  *Output: void *Return: void *************************************************/  
void DestroySqlist(seqlist_t *list)  
{if (list == NULL)  	     return ;  free(list);  	  return;  
}  /**************************************************clear the list and reset it as empty *Input : the list to be cleared.  *Output: void *Return: void *************************************************/  
void ClearSqlist(seqlist_t *list)  
{if (list == NULL)         return ;   list->last = -1;//清空线性表  		  
}  /************************************************  *judge if the list is empty *Input:   the list to be tested.  *Output:  void *Return: *  1:  list is empty *  0:  not  *  -1: error, e.g. the list is invalid ************************************************/  
int EmptySqlist(seqlist_t *list)  
{  if (list == NULL)  	  return -1;     if(list->last == -1)//空表的标志  	return 1;   else  return 0;  
}  /************************************************  *judge if the list is full  *Input : the list to be tested.  *Output: void *Return: *  1 : list is full *  0 : not  *  -1: error ************************************************/  
int FullSqlist(seqlist_t *list)  
{if (list == NULL)   return -1; if (MAX - 1 == list->last)  return 1;   else  return 0;  
}  /************************************************  *get length of the list  *Input : the list to be tested.  *Output: void *Return:  *  0: length of the list; *  -1 : means error  ************************************************/  
int LengthSqlist(seqlist_t *list)  
{if (list == NULL)  return -1;  else  	return (list->last + 1);  
}  /************************************************ *get data of element at specified position *Input :  *  list :  the list to be operated. *  at :    the position where to get the element at,  *  position index starts from zero. *Output: x : the data value returned *Return: *  0 : success; *  -1: error, e.g. list is invalid; 'at' extends  *  the range of the list     ************************************************/  
int GetSqlist(seqlist_t *list, int at, data_t *x) //data_t *x为出参  
{if(list == NULL || at < 0 || at > list->last)  return -1;   *x = list->data[at];  	 return 0;  
}  /***************************************************set/update data of element at specified position *Input :  *  list :the list to be operated. *	at :the position at where to set the element,position index starts from zero *  x : the new data value *Output: void *Return: *	0 : success; *  -1: error, e.g. list is invalid; 'at' extends the range of the list    *************************************************/  
int SetSqlist(seqlist_t *list, int at, data_t x)//data_t x为入参  
{if(list == NULL || at < 0 || (at > list->last))  		 return -1;     list->data[at] = x;   return 0;  
}  /************************************************ *Insert element at the specified position. If the "at" exceed the  *upper limit of the list, append the data at the end of the list.  *e.g. insert a new data into a { }. *Input :  *  list :  the list to be operated. *  at :    the position at which to insert the new element,position index starts from zero. *  x : the data to be inserted  *Output: void *Return: *  0 : success;  *  <0: error  ************************************************/  
int InsertSqlist(seqlist_t *list, int at, data_t x)  
{int j;   if(list == NULL || at < 0 || FullSqlist(list))if(at > list->last)//此情况比较特殊，如表中长度是50，却要插在60前面，我们这里将其插在50后面，即at = list->last + 1  {at = list->last + 1;//若是空表{}，list->last为-1，此时将其放在第0位；      }  else  	    {	    for(j = list->last; j >= at; j--)  				{list->data[j+1] = list->data[j];  		}  				 }  list->data[at] = x;  list->last++;//list->last要+1  return 0;  
}  /************************************************* *delete the element by the position *Input :  *	list :  the list to be operated. *	at :    the position at which to delete the element,  *position index starts from zero *Output : void *Return : *  0 : success; *  !0 :    error   *************************************************/  
int DeleteSqlist(seqlist_t *list, int at)  
{int i; if(list == NULL || at < 0 || (at > list->last)) 	return -1;  for(i = at + 1; i <= list->last;i++)  list->data[i-1] = list->data[i];  	list->last--;  			return 0;  
}

main.c

#include <stdio.h>  
#include <stdlib.h>  
#include "seqlist.h"  void iterate_list(seqlist_t *list)  
{int i;  printf("list.last = %d", list->last);  for (i = -1; i < list->last;) {printf("%d,", list->data[++i]);  }  if (LengthSqlist(list) > 0)  printf("\b}\n");  else  printf("}\n");  			  
}  int main(int argc, const char *argv[])  
{int i;  int length;  		data_t a[10] = {2,4,6,8,10,12,14,16,18,20};  data_t x;  				    seqlist_t *list;  list = CreateEmptySqlist();  if (list == NULL)  return -1;  for(i = 0; i < 10;i++)  {if((InsertSqlist(list,i,a[i])) < 0)  	break;  }  iterate_list(list);  length = LengthSqlist(list);  printf("The length of the list is %d\n",length);  						  GetSqlist(list,4,&x);  printf("The NO.4 data of the list is %d\n",x);  SetSqlist(list,4,5);  GetSqlist(list,4,&x);  printf("After updataing! The NO.4 data of the list is %d\n",x);  printf("Delete data[4]!\n");  DeleteSqlist(list,4);  GetSqlist(list,4,&x);  printf("Now data[4] = %d\n",x);  printf("Now the legth of the list is %d\n",LengthSqlist(list));  ClearSqlist(list);  if(EmptySqlist(list))  printf("The list is empty!\n");  printf("Now the legth of the list is %d\n",LengthSqlist(list));  DestroySqlist(list);  printf("The list is destroyed!\n");  return 0;  
}

makefile

.PHONY : clean
OBJ = test
OBJS = seqlist.o main.o  
CFLAGS = -c -g -Wall  
CC = gcc  
$(OBJ):$(OBJS)  @$(CC) -o test -g $(OBJS)  
main.o:main.c seqlist.h @$(CC) $(CFLAGS) main.c  
seqlist.o:seqlist.c seqlist.h @$(CC) $(CFLAGS) seqlist.c  
clean:  rm -rf *.o

执行结果如下：
这里写图片描述

2.2链表

2.2.1单向链表

线性表存储结构分为顺序存储、链式存储。
链表就是典型的链式存储，将线性表L = （a0,a1,a2,…an-1）中个元素分布在存储器的不同存储块，成为结点（Node），通过地址或指针建立他们之间的练习，所得到的存储结构为链表结构。

2.2.1.1节点类型描述：
typedef struct node_t
{data_t data; //节点的数据域struct node_t *next;//节点的后继指针域
}linknode_t,*linklist_t;

也可这样表示：

struct node_t
{data_t data; struct node_t *next;
}
typedef struct node_t linknode_t;
typedef struct node_t *linklist_t;

若说明

linknode_t  A;
linklist_t p  = &A;

则结构变量A为所描述的节点，而指针变量P为指向此类型节点的指针（p的值为节点的地址）；
这样看来 linknode_t linklist_t 的作用是一样的，那为什么我们要定义两个数据类型（同一种）呢？主要为了代码的可读性，我们要求标识符要望文识义，便于理解；
1、linknode_t *pnode 指向一个节点；
2、linklist_t list 指向一个整体

2.2.1.2头结点 head

我们在前篇提到的顺序存储线性表，如何表达一个空表{ }，是通过list->last = -1来表现的，所谓的空表就是数据域为NULL，而我们的链表有数据域和指针域，我们如何表现空链表呢？这时，就引入了头结点的概念，头结点和其他节点数据类型一样，只是数据域为NULL，head->next = NULL，下面我们看一个创建空链表的函数，如何利用头结点来创建一个空链表：

linklist_t CreateEmptyLinklist()
{linklist_t list;list = (linklist_t)malloc(sizeof(linknode_t));if (NULL != list) {list->next = NULL;}return list;
}

只要头结点，链表就还在！

2.2.1.3链表基本运算的相关算法

链表的运算除了上面的创建空链表，还有数据的插入，删除，查找等函数，链表的运算有各种实现方法，如何写出一个高效的，封装性较好的函数是我们要考虑的，比如数据插入函数，我们就要尽可能考虑所有能出现的结果，比如：1）如果需插入数据的链表是个空表；2）所插入的位置超过了链表的长度；如果我们的函数能包含所有能出现的情况，不仅能大大提高我们的开发效率，也会减少代码的错误率。下面，我们来看看下面的这个链表的插入函数的实现：

int InsertLinklist(linklist_t list, int at, data_t x)
{linknode_t *node_prev, *node_at, *node_new;int pos_at;int found = 0;if (NULL == list) return -1;/* at must >= 0  */if (at < 0) return -1;/*第一步、分配空间*/node_new = malloc(sizeof(linknode_t));if (NULL == node_new) {return -1;}node_new->data = x; /* assigned value */node_new->next = NULL; /*节点如果插入超过链表长度的位置，会接到尾节点后面，这样，node_new成了尾节点，node_new->next = NULL *//*第二步、定位*/node_prev = list;//跟随指针，帮助我们更好的定位node_at = list->next; //遍历指针pos_at = 0;while (NULL != node_at) {if (pos_at == at){found = 1; //找到正确的位置，跳出循环break;			}/* move to the next pos_at */node_prev = node_at; //跟随指针先跳到遍历指针的位置node_at = node_at->next;//遍历指针跳到下一个节点的位置pos_at++;}/*第三步、插入*/	if (found) {/* found = 1,找到正确的位置，插入  */node_new->next = node_at;//插入的节点next指向node_atnode_prev->next = node_new;//插入节点的前一个节点} else {/*若是没找到正确的位置，即所插入位置超越了链表的长度，则接到尾节点的后面，同样，这样适用于{ }即空链表，这样我们可以建立一个空链表，利用这个函数，实现链表的初始化*/node_prev->next = node_new;}

这个插入函数可利用性就非常高。
下面讲一个完整链表代码贴出：
listlink.h

#ifndef _LNK_LIST_H_
#define _LNK_LIST_H_typedef int data_t;
typedef struct node_t {data_t data;struct node_t *next;
} linknode_t, *linklist_t;linklist_t CreateEmptyLinklist();
void DestroyLinklist(linklist_t list);
void ClearLinklist(linklist_t list);
int EmptyLinklist(linklist_t list);
int LengthLinklist(linklist_t list);
int GetLinklist(linklist_t list, int at, data_t *x);int SetLinklist(linklist_t list, int at, data_t x);
int InsertLinklist(linklist_t list, int at, data_t x);
int DeleteLinklist(linklist_t list, int at);
linklist_t ReverseLinklist(linklist_t list);
#endif /* _LNK_LIST_H_ */

linklist.c

#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"linklist_t CreateEmptyLinklist()
{linklist_t list;list = (linklist_t)malloc(sizeof(linknode_t));if (NULL != list) {list->next = NULL;}return list;
}void DestroyLinklist(linklist_t list)
{if (NULL != list) {ClearLinklist(list);free(list);}
}void ClearLinklist(linklist_t list)
{linknode_t *node; /* pointer to the node to be removed */if (NULL == list) return;while (NULL != list->next) {node = list->next;list->next = node->next;free(node);}return;
}int LengthLinklist(linklist_t list)
{int len = 0;linknode_t *node; //iterate pointerif (NULL == list) return -1;node = list->next; // node points to the first data nodewhile (NULL != node) {len++;node = node->next;}return len;
}int EmptyLinklist(linklist_t list)
{if (NULL != list) {if (NULL == list->next) {return 1;} else {return 0;}} else {return -1;}
}int GetLinklist(linklist_t list, int at, data_t *x)
{linknode_t *node;	/* used for iteration */int pos;		/* used for iteration and compare with */if (NULL == list) return -1;/* at must >= 0 */if (at < 0) return -1;/* start from the first element */node = list->next;pos = 0;while (NULL != node) {if (at == pos) {if (NULL != x) {*x = node->data;}return 0;			}/* move to the next */node = node->next;pos++;}return -1;
}int SetLinklist(linklist_t list, int at, data_t x)
{linknode_t *node; /* used for iteration */int pos;int found = 0;if (!list) return -1;/* at must >= 0 */if (at < 0) return -1;/* start from the first element */node = list->next;pos = 0;while (NULL != node) {if (at == pos) { found = 1; /* found the position */node->data = x;break;			}/* move to the next */node = node->next;pos++;}if (1 == found) {return 0;} else {return -1;}
}int InsertLinklist(linklist_t list, int at, data_t x)
{/* * node_at and pos_at are used to locate the position of node_at.* node_prev follows the node_at and always points to previous node *	of node_at.* node_new is used to point to the new node to be inserted.*/linknode_t 	*node_prev, *node_at, *node_new;int		pos_at;int 		found = 0;if (NULL == list) return -1;/* at must >= 0 */if (at < 0) return -1;node_new = malloc(sizeof(linknode_t));if (NULL == node_new) {return -1;}node_new->data = x; /* assigned value */node_new->next = NULL;node_prev = list;node_at = list->next;pos_at = 0;while (NULL != node_at) {if (pos_at == at) {/* * found the node 'at'*/ found = 1;break;			}/* move to the next pos_at */node_prev = node_at;node_at = node_at->next;pos_at++;}if (found) {/* insert */node_new->next = node_at;node_prev->next = node_new;} else {/* * If not found, means the provided "at"* exceeds the upper limit of the list, just * append the new node to the end of the list.*/node_prev->next = node_new;}return 0;
}int DeleteLinklist(linklist_t list, int at)
{/* * node_at and pos_at are used to locate the position of node_at.* node_prev follows the node_at and always points to previous node *	of node_at.*/linknode_t 	*node_prev, *node_at;int		pos_at;int 		found = 0;if (!list) return -1;/* at must >= 0 */if (at < 0) return -1;node_prev = list;node_at = list->next;pos_at = 0; while (NULL != node_at) {if (pos_at == at) {/* * found the node 'at'*/ found = 1;break;			}/* move to the next pos_at */node_prev = node_at;node_at = node_at->next;pos_at++;}if (found) {/* remove */node_prev->next = node_at->next;free(node_at);return  0;} else {return -1;}
}linklist_t ReverseLinklist(linklist_t list)
{linknode_t *node;	/* iterator */linknode_t *node_prev;	/* previous node of iterator */linknode_t *node_next;	/* next node of iterator, * used to backup next of iterator */if (NULL == list) return NULL;node_prev = NULL;node = list->next;while (NULL != node) {/** step1: backup node->next* due to the next of iterator will be* modified in step2*/node_next = node->next;/* * when iterator reaches the last node * of original list, make the list head* point to the last node, so the original* last one becomes the first one.*/if (NULL == node_next) {list->next = node;}/* * step2: reverse the linkage between nodes* make the node pointer to the previous node,* not the next node*/		node->next = node_prev;		/* * step3: move forward */node_prev = node;node = node_next;}return list;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"int main()
{int i;data_t x;linklist_t p;p =	CreateEmptyLinklist();data_t a[10] = {1,3,5,7,9,11,13,15,17,19};for(i = 0;i < 10;i++){InsertLinklist(p,i,a[i]);}ReverseLinklist(p);printf("The length of the list is:%d\n",LengthLinklist(p));GetLinklist(p,4,&x);printf("The NO.4 of this list is:%d\n",x);SetLinklist(p,4,100);GetLinklist(p,4,&x);printf("After updating!The No.4 0f this list is:%d\n",x);DeleteLinklist(p,4);printf("After updating!The length of the list is:%d\n",LengthLinklist(p));GetLinklist(p,4,&x);printf("After updating!The No.4 0f this list is:%d\n",x);ReverseLinklist(p);ClearLinklist(p);if(EmptyLinklist(p))printf("This list is empty!\n");DestroyLinklist(p);printf("This list is destroyed!\n");return 0;
}

Makefile

.PHONY : clean
OBJ = test
OBJS = linklist.o main.o  
CFLAGS = -c -g -Wall  
CC = gcc  
$(OBJ):$(OBJS)  @$(CC) -o test -g $(OBJS)  
main.o:main.c linklist.h @$(CC) $(CFLAGS) main.c  
linklist.o:linklist.c linklist.h @$(CC) $(CFLAGS) linklist.c  
clean:  @rm -rf *.o

执行结果如下：
这里写图片描述

2.2.2循环链表

前面我们学习了单向链表，现在介绍单向循环链表，单向循环链表是单链表的一种改进，若将单链表的首尾节点相连，便构成单向循环链表结构，如下图：
这里写图片描述

图2

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

循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大。当然，如果只会在最后插入数据（或者只会在之前），处理也是很容易的。

2.2.2.1 Joseph问题（约瑟夫环）

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人找到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

约瑟夫环用数学问题来描述就是：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。如何用循环链表来求解Josephu问题？

下面我们用单向循环链表来模拟这个问题：

#include <stdio.h>  
#include <stdlib.h>  typedef int data_t;  typedef struct node_t  
{  data_t data;  struct node_t *next;      
}linknode_t,*linklist;  linklist CreateList(int n)  
{  int i;  linklist p,head,tail;  head = NULL;  for(i = 1;i <= n;i++)  {  p = (linklist)malloc(sizeof(linklist));  if(p == NULL)  {  printf("malloc fails!\n");  }  p->data = i;  if(head == NULL)  {  head = p;  tail = head;  }  else  {  tail->next = p;  }                 tail = p;  }  tail->next = head;  return head;   
}  
void Joseph(int n,int k,int m)  
{  int i;  linklist p,r;  p = CreateList(n);  for(i = 1;i < k;i++) //从第K个人开始数  {  p = p->next;  }  while(p->next != p)  {  for(i = 1;i <= m-2;i++)  //数到第m个人，去自杀  p = p->next;  r = p->next;  p->next = r->next;  printf("%d->",r->data);  free(r);  p = p->next;//从下一个人继续数  }  printf("%d\n",p->data);  
}  
int main()  
{  Joseph(41,1,3);  return 0;  
}

输出结果如下：
3->6->9->12->15->18->21->24->27->30->33->36->39->1->5->10->14->19->23->28->32->37->41->7->13->20->26->34->40->8->17->29->38->11->25->2->22->4->35->16->31
我们可以看到，最后两个是16和31，这样，约瑟夫和他的朋友就躲过了一劫！

2.2.2.2判断一个链表是不是循环链表（如何判定这个链表当中是否包含有环路）

解决方法：

判断是否是循环链表时，也设置两个指针，慢指针和快指针，让快指针比慢指针每次移动快两次。如果快指针追赶上慢指针，则为循环链表，否则不是循环链表，如果快指针或者慢指针指向NULL，则不是循环链表。
代码如下：

#include <stdio.h>  
#include <stdlib.h>  typedef int data_t;  typedef struct node_t  
{  data_t data;  struct node_t *next;      
}linknode_t,*linklist;  
linklist CreateList(int n)  
{  int i;  linklist p,head,tail;  head = NULL;  for(i = 1;i <= n;i++)  {  p = (linklist)malloc(sizeof(linklist));  if(p == NULL)  {  printf("malloc fails!\n");  }  p->data = i;  if(head == NULL)  {  head = p;  tail = head;  }  else  {  tail->next = p;  }                 tail = p;  }  tail->next = head;  return head;   
}  
int JudgeIsloop(linklist list)  
{  int flag = 0;  linknode_t *slow,*fast;  if(list == NULL)  return 0;  slow = list;  fast = list->next;  while(slow)  {  if(fast == NULL || fast->next == NULL)//走到头了  return 0;  else if(fast == slow || fast->next == slow)//二者相遇，因为fast走的快，如果fast->next指向slow，也是循环的  {     flag = 1;  return 1;  }  else  {  slow = slow->next;//慢指针走一步  fast = fast->next->next;//快指针走两步  }  }  return 0;  
}  
int main()  
{  int i;  int flag = 0;  linklist list;  list = CreateList(10);  JudgeIsloop(list);  if(flag = 0)  printf("The list is not a looplist!\n");  else  {  printf("The list is a looplist!\n");//循环链表则打印出来  for(i = 0;i < 10;i++)  {  printf("%d->",list->data);  list = list->next;  }  printf("%d\n",list->data);  }  return 0;  
}

结果如下：
The list is a looplist!
1->2->3->4->5->6->7->8->9->10->1

这篇关于《数据结构》第2章 表（C语言描述）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1120960。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

科研绘图系列：R语言扩展物种堆积图（Extended Stacked Barplot）

介绍 R语言的扩展物种堆积图是一种数据可视化工具，它不仅展示了物种的堆积结果，还整合了不同样本分组之间的差异性分析结果。这种图形表示方法能够直观地比较不同物种在各个分组中的显著性差异，为研究者提供了一种有效的数据解读方式。 加载R包 knitr::opts_chunk$set(warning = F, message = F)library(tidyverse)library(phyl
阅读更多...
透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

透彻！驯服大型语言模型（LLMs）的五种方法，及具体方法选择思路

引言 随着时间的发展，大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用，随着人们期望的不断增加，目标也发生了巨大的变化。在短短的几个月的时间里，人们对大模型的认识已经从对其zero-shot能力感到惊讶，转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构（例如Transformer）对海量的、多种多样的数据分布进行建模得到，它包含了大量的先验
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
C语言 | Leetcode C语言题解之第393题UTF-8编码验证

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目： 题解： static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return
阅读更多...
MiniGPT-3D, 首个高效的3D点云大语言模型，仅需一张RTX3090显卡，训练一天时间，已开源

MiniGPT-3D, 首个高效的3D点云大语言模型，仅需一张RTX3090显卡，训练一天时间，已开源

项目主页：https://tangyuan96.github.io/minigpt_3d_project_page/ 代码：https://github.com/TangYuan96/MiniGPT-3D 论文：https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA，被ACM MM2024接收，只拥有47.8M的可训练参数，在一张RTX
阅读更多...
如何确定 Go 语言中 HTTP 连接池的最佳参数？

如何确定 Go 语言中 HTTP 连接池的最佳参数？

确定 Go 语言中 HTTP 连接池的最佳参数可以通过以下几种方式： 一、分析应用场景和需求 并发请求量： 确定应用程序在特定时间段内可能同时发起的 HTTP 请求数量。如果并发请求量很高，需要设置较大的连接池参数以满足需求。例如，对于一个高并发的 Web 服务，可能同时有数百个请求在处理，此时需要较大的连接池大小。可以通过压力测试工具模拟高并发场景，观察系统在不同并发请求下的性能表现，从而
阅读更多...
C语言：柔性数组

C语言：柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t；t = malloc(sizeof(Test) + 11);strcpy(t->arr,
阅读更多...
C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》

C语言指针入门 《C语言非常道》 作为一个程序员，我接触 C 语言有十年了。有的朋友让我推荐 C 语言的参考书，我不敢乱推荐，尤其是国内作者写的书，往往七拼八凑，漏洞百出。 但是，李忠老师的《C语言非常道》值得一读。对了，李老师有个官网，网址是： 李忠老师官网 最棒的是，有配套的教学视频，可以试看。 试看点这里 接下来言归正传，讲解指针。以下内容很多都参考了李忠老师的《C语言非
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2