当前位置： 首页 > article >正文

C语言数据结构之单向链表（SingleList）

article 2024/10/24 22:08:46

C语言数据结构之单向链表（SingleList）

  • 自定义结构体数据类型SListNode表示单向链表的节点，成员包括一个无类型的data用来存贮数据和一个SListNode本身类型的指针next，指向下一个节点。
  • 围绕SListNode写一系列函数以slist_开头实现单向链表的各种功能，做一个简单的封装。

创建链表slist_node_new与释放链表slist_free

  • 创建链表节点函数slist_node_new，带一个无类型的参数，做为节点的数据！
  • 释放单向链表函数slist_free，参数单向链表节点，从此节点开始的节点都将被释放！

代码如下：

/* filename : slist.c */
#include <stdio.h>
#include <stdlib.h>

/**/
typedef struct _SListNode SListNode;
struct _SListNode {
  void *data;
  SListNode *next;
};

/**/
SListNode *
slist_node_new (void *data)
{
  SListNode *node = (SListNode*) malloc (sizeof(SListNode));
  node->data = data;
  node->next = NULL;
  return node;
}

/**/
void
slist_free (SListNode *root)
{
  SListNode *tmp;
  while (root != NULL)
    {
      tmp = root->next;
      free (root);
      root = tmp;
    }
}

/**/
int
main (int argc, char *argv[])
{
  char *name = "Tomson";
  SListNode *root = slist_node_new (name);
  slist_free(root);
  return 0;
}
/* --[#|#]-- */

编译运行，达到预期，检测一下内存情况，结果如下：

songvm@ubuntu:~/works/xdn/loo$ gcc slist.c -o slist
songvm@ubuntu:~/works/xdn/loo$ ./slist
songvm@ubuntu:~/works/xdn/loo$ valgrind --leak-check=yes ./slist
==2046== Memcheck, a memory error detector
==2046== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2046== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2046== Command: ./slist
==2046== 
==2046== 
==2046== HEAP SUMMARY:
==2046==     in use at exit: 0 bytes in 0 blocks
==2046==   total heap usage: 1 allocs, 1 frees, 16 bytes allocated
==2046== 
==2046== All heap blocks were freed -- no leaks are possible
==2046== 
==2046== For counts of detected and suppressed errors, rerun with: -v
==2046== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

链表尾部追加append，链表头部追加prepend，链表逐项操作foreach

  • 链表尾部追加函数 slist_append，参数为无类型指针
  • 链表头部追加函数 slist_prepend，参数为无类型指针
  • 链表逐项操作函数 slist_foreach，参数为函数指针MgFunc，需要自定义一个函数来操作逐个节点的数据
  • 测试函数，向链表追加了四个字符串AAAA,BBBB,CCCC,DDDD，逐项操作显示链内容，然后向链表头部追加字符串EEEE，再逐项操作显示结果为EEEE,AAAA,BBBB,CCCC,DDDD

代码如下：

/* filename : slist.c */
#include <stdio.h>
#include <stdlib.h>

/* define function pointer with a void* argument */
typedef void (*MgFunc) (void *data);

/* define single list node datatype */
typedef struct _SListNode SListNode;
struct _SListNode {
  void *data;
  SListNode *next;
};

/* create a new single list node */
SListNode *
slist_node_new (void *data)
{
  SListNode *node = (SListNode*) malloc (sizeof(SListNode));
  node->data = data;
  node->next = NULL;
  return node;
}

/* free single list node from root to end */
void
slist_free (SListNode *root)
{
  SListNode *tmp;
  while (root != NULL)
    {
      tmp = root->next;
      free (root);
      root = tmp;
    }
}

/* append a new node at single list tail of head with data */
SListNode *
slist_append (SListNode *head, void *data)
{
  SListNode *tmp = head, *node = slist_node_new (data);
  while (tmp->next != NULL)
    tmp = tmp->next;
  tmp->next = node;
  return head;
}

/* prev append a new node as head of single list head with data */
SListNode *
slist_preppend (SListNode *head, void *data)
{
  SListNode *node = slist_node_new (data);
  node->next = head;
  return node;
}

/* foreach single list node run mgfunc from head to end */
void
slist_foreach (SListNode *head, MgFunc mgfunc)
{
  SListNode *tmp = head;
  while (tmp != NULL)
    {
      mgfunc (tmp->data);
      tmp = tmp->next;
    }
}

/* ------------------------------ */

/* define function for MgFunc */
void
out_string (void *data)
{
  printf ("[%s], ", (char*)data);
}

/* test slist append and preppend */
void
test_slist_append (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head = slist_node_new (txt[0]);
  head = slist_append (head, txt[1]);
  head = slist_append (head, txt[2]);
  head = slist_append (head, txt[3]);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_preppend (head, txt[4]);
  slist_foreach (head, out_string); printf ("\n");
  slist_free(head);
}

/**/
int
main (int argc, char *argv[])
{
  test_slist_append ();
  return 0;
}
/* --[#|#]-- */

编译运行，达到预期，检测内存分配释放情况，结果如下：

songvm@ubuntu:~/works/xdn/loo$ gcc slist.c -o slist
songvm@ubuntu:~/works/xdn/loo$ ./slist
[AAAA], [BBBB], [CCCC], [DDDD], 
[EEEE], [AAAA], [BBBB], [CCCC], [DDDD],
songvm@ubuntu:~/works/xdn/loo$ valgrind --leak-check=yes ./slist
==2198== Memcheck, a memory error detector
==2198== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2198== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2198== Command: ./slist
==2198== 
[AAAA], [BBBB], [CCCC], [DDDD], 
[EEEE], [AAAA], [BBBB], [CCCC], [DDDD], 
==2198== 
==2198== HEAP SUMMARY:
==2198==     in use at exit: 0 bytes in 0 blocks
==2198==   total heap usage: 6 allocs, 6 frees, 1,104 bytes allocated
==2198== 
==2198== All heap blocks were freed -- no leaks are possible
==2198== 
==2198== For counts of detected and suppressed errors, rerun with: -v
==2198== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

链表连接concat，链表插入insert

  • 链表连接函数slist_concat，参数为两个链表的头部节点，返回值为两个链表连接后的头部结点
  • 链表插入函数slist_insert，参数为链表的位置索引和数据，带数据创建节点然后插入到指定的索引位置

代码如下：

/* concat single list sla and slb, return sla as head */
SListNode *
slist_concat (SListNode *sla, SListNode *slb)
{
  SListNode *tmp = sla;
  while (tmp->next != NULL)
    tmp = tmp->next;
  tmp->next = slb;
  return sla;
}

/* insert a node into single list of head with data */
SListNode *
slist_insert (SListNode *head, int pos, void *data)
{
  int idx = 0;
  SListNode *tmp = head;
  while (tmp != NULL)
    {
      if (idx == pos)
	{
	  SListNode *next, *node;
	  node = slist_node_new (data);
	  next = tmp->next;
	  tmp->next = node;
	  node->next = next;
	  break;
	}
      tmp = tmp->next;
      idx = idx + 1;
    }
  return head;
}
  • 测试函数test_slist_concat，创建两个链表lsa内容为：AAAA,BBBB,CCCC和lsb内容为：DDDD,EEEE，连接后链表内容为：AAAA,BBBB,CCCC,DDDD,EEEE
  • 测试函数test_slist_insert，创建链表，依次向位置索引1和4插入字符串XXXX

代码如下：

/**/
void
test_slist_concat (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head, *sla, *slb;
  sla = slist_node_new (txt[0]);
  sla = slist_append (sla, txt[1]);
  sla = slist_append (sla, txt[2]);
  slb = slist_node_new (txt[3]);
  slb = slist_append (slb, txt[4]);
  slist_foreach (sla, out_string); printf ("\n");
  slist_foreach (slb, out_string); printf ("\n");
  head = slist_concat (sla, slb);
  slist_foreach (head, out_string); printf ("\n");
  slist_free (head);
}

/**/
void
test_slist_insert (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  char *str = "XXXX";
  SListNode *head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_insert (head, 1, str);
  head = slist_insert (head, 4, str);
  slist_foreach (head, out_string); printf ("\n");
  slist_free (head);
}

编译运行，测试连接两个链表，结果如预期：

songvm@ubuntu:~/works/xdn/loo$ gcc slist.c -o slist
songvm@ubuntu:~/works/xdn/loo$ ./slist
[AAAA], [BBBB], [CCCC], 
[DDDD], [EEEE], 
[AAAA], [BBBB], [CCCC], [DDDD], [EEEE], 
songvm@ubuntu:~/works/xdn/loo$

编译运行，测试向链表中插入数据，结果如预期：

songvm@ubuntu:~/works/xdn/loo$ gcc slist.c -o slist
songvm@ubuntu:~/works/xdn/loo$ ./slist
[AAAA], [BBBB], [CCCC], [DDDD], [EEEE], 
[AAAA], [BBBB], [XXXX], [CCCC], [DDDD], [XXXX], [EEEE], 
songvm@ubuntu:~/works/xdn/loo$

链表删除节点remove，链表删除头部节点remove_head，链表删除尾部节点remove_tail

  • 删除节点函数slist_remove，参数为指定节点的索引值
  • 删除头部节点函数slist_remove_head
  • 删除尾部节点函数slist_remove_tail

代码如下：

/* remove a node in single list at nth */
SListNode *
slist_remove (SListNode *head, int nth)
{
  SListNode *tmp = head, *pn = head;
  int idx = 0;
  while (tmp->next != NULL)
    {
      if (idx == nth)
	{
	  SListNode *node = tmp->next;
	  free (tmp);
	  if (idx == 0) return node;
	  else pn->next = node;
	  break;
	}
      pn = tmp;
      tmp = tmp->next;
      idx = idx + 1;
    }
  return head;
}

/* remove the single list head node */
SListNode *
slist_remove_head (SListNode *sln)
{
  SListNode *tmp = sln->next;
  if (sln == NULL) return sln;
  free (sln);
  sln = tmp;
  return sln;
}

/* remove the single list tail node */
SListNode *
slist_remove_tail (SListNode *sln)
{
  SListNode *tmp = sln, *pn;
  while (tmp->next != NULL)
    {
      pn = tmp;
      tmp = tmp->next;
    }
  pn->next = NULL;
  free (tmp);
  return sln;
}
  • 测试函数test_slist_remove，创建链表，删除索引值为1和2的节点
  • 测试函数test_slist_remove_head_tail，创建链表，分别删除链表的头节点和尾节点

代码如下：

/**/
void
test_slist_remove (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_remove (head, 1);
  head = slist_remove (head, 2);
  slist_foreach (head, out_string); printf ("\n");
  slist_free (head);
}

/**/
void
test_slist_remove_head_tail (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_remove_head (head);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_remove_tail (head);
  slist_foreach (head, out_string); printf ("\n");
  slist_free (head);
}

编译运行，测试删除链表节点，顺利通过，结果如下：

songvm@ubuntu:~/works/xdn/loo$ gcc slist.c -o slist
songvm@ubuntu:~/works/xdn/loo$ ./slist
[AAAA], [BBBB], [CCCC], [DDDD], [EEEE], 
[AAAA], [CCCC], [EEEE], 
songvm@ubuntu:~/works/xdn/loo$

编译运行，测试删除链表头和链表尾，同时检查内存使用情况，达到目标，结果如下：

songvm@ubuntu:~/works/xdn/loo$ gcc slist.c -o slist
songvm@ubuntu:~/works/xdn/loo$ ./slist
[AAAA], [BBBB], [CCCC], [DDDD], [EEEE], 
[BBBB], [CCCC], [DDDD], [EEEE], 
[BBBB], [CCCC], [DDDD], 
songvm@ubuntu:~/works/xdn/loo$ valgrind --leak-check=yes ./slist
==2786== Memcheck, a memory error detector
==2786== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2786== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2786== Command: ./slist
==2786== 
[AAAA], [BBBB], [CCCC], [DDDD], [EEEE], 
[BBBB], [CCCC], [DDDD], [EEEE], 
[BBBB], [CCCC], [DDDD], 
==2786== 
==2786== HEAP SUMMARY:
==2786==     in use at exit: 0 bytes in 0 blocks
==2786==   total heap usage: 6 allocs, 6 frees, 1,104 bytes allocated
==2786== 
==2786== All heap blocks were freed -- no leaks are possible
==2786== 
==2786== For counts of detected and suppressed errors, rerun with: -v
==2786== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
songvm@ubuntu:~/works/xdn/loo$

链表倒转reverse

  • 链表倒转函数slist_reverse，将链表的各节点倒转过来！！！

代码如下：

/* reverse the single list, head change to tail */
SListNode *
slist_reverse (SListNode *sln)
{
  SListNode *tmp = sln, *tail = NULL;
  while (tmp != NULL)
    {
      SListNode *node = tmp;
      tmp = tmp->next;
      node->next = tail;
      tail = node;
    }
  return tail;
}
  • 测试函数，创建链表内容为ABCDE，倒转后内容为EDCBA

代码如下：

/**/
void
test_slist_reverse (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *tail, *head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  tail = slist_reverse (head);
  slist_foreach (tail, out_string); printf ("\n");
  slist_free (tail);
}

编译运行，顺利通过，测试内存情况，结果如下：

songvm@ubuntu:~/works/xdn/loo$ gcc slist.c -o slist
songvm@ubuntu:~/works/xdn/loo$ ./slist
[AAAA], [BBBB], [CCCC], [DDDD], [EEEE], 
[EEEE], [DDDD], [CCCC], [BBBB], [AAAA], 
songvm@ubuntu:~/works/xdn/loo$ valgrind --leak-check=yes ./slist
==2831== Memcheck, a memory error detector
==2831== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==2831== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==2831== Command: ./slist
==2831== 
[AAAA], [BBBB], [CCCC], [DDDD], [EEEE], 
[EEEE], [DDDD], [CCCC], [BBBB], [AAAA], 
==2831== 
==2831== HEAP SUMMARY:
==2831==     in use at exit: 0 bytes in 0 blocks
==2831==   total heap usage: 6 allocs, 6 frees, 1,104 bytes allocated
==2831== 
==2831== All heap blocks were freed -- no leaks are possible
==2831== 
==2831== For counts of detected and suppressed errors, rerun with: -v
==2831== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
songvm@ubuntu:~/works/xdn/loo$

求链表长度length，取链表节点get_nth，取链表节点的数据get_nth_data

  • 求链表长度slist_length
  • 取链表节点slist_get_nth，参数nth为索引值
  • 取链表节点的数据slist_get_nth_data，参数nth为索引值

代码如下：

/* get single list length */
int
slist_length (SListNode *sln)
{
  int len = 0;
  SListNode *tmp = sln;
  while (tmp != NULL)
    {
      tmp = tmp->next;
      len = len + 1;
    }
  return len;
}

/* get nth node from single list begin 0, if has not return NULL */
SListNode *
slist_nth (SListNode *sln, int nth)
{
  int idx = 0;
  SListNode *tmp = sln;
  while (tmp != NULL)
    {
      if (idx == nth) return tmp;
      tmp = tmp->next;
      idx = idx + 1;
    }
  return NULL;
}

/* get data of nth node from single list */
void *
slist_nth_data (SListNode *sln, int nth)
{
  int idx = 0;
  SListNode *tmp = sln;
  while (tmp != NULL)
    {
      if (idx == nth) return tmp->data;
      tmp = tmp->next;
      idx = idx + 1;
    }
  return NULL;
}
  • 测试函数，创建链表，长度为5，第2节点为CCCC，第3节点为DDDD

代码如下：

/* */
void
test_slist_length (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *node, *head;
  head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  printf ("Single list length is %d\n", slist_length(head));
  node = slist_nth (head, 2);
  printf ("Single list 2nd node data is [%s]\n", (char*)(node->data));
  printf ("Single list 3th node data is [%s]\n", (char*)slist_nth_data(head, 3));
  slist_free (head);
}

编译运行，顺利通过，达到预期，运行结果如下：

songvm@ubuntu:~/works/xdn/loo$ gcc slist.c -o slist
songvm@ubuntu:~/works/xdn/loo$ ./slist
[AAAA], [BBBB], [CCCC], [DDDD], [EEEE], 
Single list length is 5
Single list 2nd node data is [CCCC]
Single list 3th node data is [DDDD]
songvm@ubuntu:~/works/xdn/loo$

判断链表是否为循环链表

  • 循环锭表的特征为next节点指针指向头节点，这样在逐项操作时会造成死循环！！！
  • 判断链表是否为循环链表函数slist_is_round，是返回1，否则返回0！！！

代码如下：

/* if single list is round return 1, else return 0 */
int
slist_is_round (SListNode *sln)
{
  SListNode *tmp = sln, *node = tmp;
  while (tmp != NULL)
    {
      tmp = tmp->next;
      if (tmp == node) return 1;
    }
  return 0;
}
  • 测试函数，创建链表，尾指针指向头节点，成为循环链表，查看函数slist_is_round返回值

代码如下：

/**/
void
test_slist_is_round (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head, *tail;
  head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);

  tail = slist_nth (head, 4);
  tail->next = head; //link round

  if (slist_is_round (head))
    printf ("Single list is round!\n");
  else
    printf ("Single list not round!\n");

  tail->next = NULL; //cut round

  if (slist_is_round (head))
    printf ("Single list is round!\n");
  else
    printf ("Single list not round!\n");

  slist_free (head);
}

编译运行，顺利通过，达到预期！！！运行结果如下：

songvm@ubuntu:~/works/xdn/loo$ gcc slist.c -o slist
songvm@ubuntu:~/works/xdn/loo$ ./slist
Single list is round!
Single list not round!
songvm@ubuntu:~/works/xdn/loo$

完整代码如下：

/* filename : slist.c */
#include <stdio.h>
#include <stdlib.h>

/* define function pointer with a void* argument */
typedef void (*MgFunc) (void *data);

/* define single list node datatype */
typedef struct _SListNode SListNode;
struct _SListNode {
  void *data;
  SListNode *next;
};

/* create a new single list node */
SListNode *
slist_node_new (void *data)
{
  SListNode *node = (SListNode*) malloc (sizeof(SListNode));
  node->data = data;
  node->next = NULL;
  return node;
}

/* free single list node from root to end */
void
slist_free (SListNode *root)
{
  SListNode *tmp;
  while (root != NULL)
    {
      tmp = root->next;
      free (root);
      root = tmp;
    }
}

/* append a new node at single list tail of head with data */
SListNode *
slist_append (SListNode *head, void *data)
{
  SListNode *tmp = head, *node = slist_node_new (data);
  while (tmp->next != NULL)
    tmp = tmp->next;
  tmp->next = node;
  return head;
}

/* prev append a new node as head of single list head with data */
SListNode *
slist_preppend (SListNode *head, void *data)
{
  SListNode *node = slist_node_new (data);
  node->next = head;
  return node;
}

/* foreach single list node run mgfunc from head to end */
void
slist_foreach (SListNode *head, MgFunc mgfunc)
{
  SListNode *tmp = head;
  while (tmp != NULL)
    {
      mgfunc (tmp->data);
      tmp = tmp->next;
    }
}

/* concat single list sla and slb, return sla as head */
SListNode *
slist_concat (SListNode *sla, SListNode *slb)
{
  SListNode *tmp = sla;
  while (tmp->next != NULL)
    tmp = tmp->next;
  tmp->next = slb;
  return sla;
}

/* insert a node into single list of head with data */
SListNode *
slist_insert (SListNode *head, int pos, void *data)
{
  int idx = 0;
  SListNode *tmp = head;
  while (tmp != NULL)
    {
      if (idx == pos)
	{
	  SListNode *next, *node;
	  node = slist_node_new (data);
	  next = tmp->next;
	  tmp->next = node;
	  node->next = next;
	  break;
	}
      tmp = tmp->next;
      idx = idx + 1;
    }
  return head;
}

/* remove a node in single list at nth */
SListNode *
slist_remove (SListNode *head, int nth)
{
  SListNode *tmp = head, *pn = head;
  int idx = 0;
  while (tmp->next != NULL)
    {
      if (idx == nth)
	{
	  SListNode *node = tmp->next;
	  free (tmp);
	  if (idx == 0) return node;
	  else pn->next = node;
	  break;
	}
      pn = tmp;
      tmp = tmp->next;
      idx = idx + 1;
    }
  return head;
}

/* remove the single list head node */
SListNode *
slist_remove_head (SListNode *sln)
{
  SListNode *tmp = sln->next;
  if (sln == NULL) return sln;
  free (sln);
  sln = tmp;
  return sln;
}

/* remove the single list tail node */
SListNode *
slist_remove_tail (SListNode *sln)
{
  SListNode *tmp = sln, *pn;
  while (tmp->next != NULL)
    {
      pn = tmp;
      tmp = tmp->next;
    }
  pn->next = NULL;
  free (tmp);
  return sln;
}

/* reverse the single list, head change to tail */
SListNode *
slist_reverse (SListNode *sln)
{
  SListNode *tmp = sln, *tail = NULL;
  while (tmp != NULL)
    {
      SListNode *node = tmp;
      tmp = tmp->next;
      node->next = tail;
      tail = node;
    }
  return tail;
}

/* get single list length */
int
slist_length (SListNode *sln)
{
  int len = 0;
  SListNode *tmp = sln;
  while (tmp != NULL)
    {
      tmp = tmp->next;
      len = len + 1;
    }
  return len;
}

/* get nth node from single list begin 0, if has not return NULL */
SListNode *
slist_nth (SListNode *sln, int nth)
{
  int idx = 0;
  SListNode *tmp = sln;
  while (tmp != NULL)
    {
      if (idx == nth) return tmp;
      tmp = tmp->next;
      idx = idx + 1;
    }
  return NULL;
}

/* get data of nth node from single list */
void *
slist_nth_data (SListNode *sln, int nth)
{
  int idx = 0;
  SListNode *tmp = sln;
  while (tmp != NULL)
    {
      if (idx == nth) return tmp->data;
      tmp = tmp->next;
      idx = idx + 1;
    }
  return NULL;
}

/* if single list is round return 1, else return 0 */
int
slist_is_round (SListNode *sln)
{
  SListNode *tmp = sln, *node = tmp;
  while (tmp != NULL)
    {
      tmp = tmp->next;
      if (tmp == node) return 1;
    }
  return 0;
}

/* ------------------------------ */

/* define function for MgFunc */
void
out_string (void *data)
{
  printf ("[%s], ", (char*)data);
}

/* test slist append and preppend */
void
test_slist_append (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head = slist_node_new (txt[0]);
  head = slist_append (head, txt[1]);
  head = slist_append (head, txt[2]);
  head = slist_append (head, txt[3]);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_preppend (head, txt[4]);
  slist_foreach (head, out_string); printf ("\n");
  slist_free(head);
}

/**/
void
test_slist_concat (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head, *sla, *slb;
  sla = slist_node_new (txt[0]);
  sla = slist_append (sla, txt[1]);
  sla = slist_append (sla, txt[2]);
  slb = slist_node_new (txt[3]);
  slb = slist_append (slb, txt[4]);
  slist_foreach (sla, out_string); printf ("\n");
  slist_foreach (slb, out_string); printf ("\n");
  head = slist_concat (sla, slb);
  slist_foreach (head, out_string); printf ("\n");
  slist_free (head);
}

/**/
void
test_slist_insert (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  char *str = "XXXX";
  SListNode *head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_insert (head, 1, str);
  head = slist_insert (head, 4, str);
  slist_foreach (head, out_string); printf ("\n");
  slist_free (head);
}

/**/
void
test_slist_remove (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_remove (head, 1);
  head = slist_remove (head, 2);
  slist_foreach (head, out_string); printf ("\n");
  slist_free (head);
}

/**/
void
test_slist_remove_head_tail (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_remove_head (head);
  slist_foreach (head, out_string); printf ("\n");
  head = slist_remove_tail (head);
  slist_foreach (head, out_string); printf ("\n");
  slist_free (head);
}

/**/
void
test_slist_reverse (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *tail, *head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  tail = slist_reverse (head);
  slist_foreach (tail, out_string); printf ("\n");
  slist_free (tail);
}

/* */
void
test_slist_length (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *node, *head;
  head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);
  slist_foreach (head, out_string); printf ("\n");
  printf ("Single list length is %d\n", slist_length(head));
  node = slist_nth (head, 2);
  printf ("Single list 2nd node data is [%s]\n", (char*)(node->data));
  printf ("Single list 3th node data is [%s]\n", (char*)slist_nth_data(head, 3));
  slist_free (head);
}

/**/
void
test_slist_is_round (void)
{
  char *txt[5] = {"AAAA", "BBBB", "CCCC", "DDDD", "EEEE"};
  SListNode *head, *tail;
  head = slist_node_new (txt[0]);
  for (int i = 1; i < 5; i++)
    head = slist_append (head, txt[i]);

  tail = slist_nth (head, 4);
  tail->next = head; //link round

  if (slist_is_round (head))
    printf ("Single list is round!\n");
  else
    printf ("Single list not round!\n");

  tail->next = NULL; //cut round

  if (slist_is_round (head))
    printf ("Single list is round!\n");
  else
    printf ("Single list not round!\n");

  slist_free (head);
}

/**/
int
main (int argc, char *argv[])
{
  //test_slist_append ();
  //test_slist_concat ();
  //test_slist_insert ();
  //test_slist_remove ();
  //test_slist_remove_head_tail ();
  //test_slist_reverse ();
  //test_slist_length ();
  test_slist_is_round ();
  return 0;
}
/* --[#|#]-- */
  • 下一步，研究双向链表！！！

http://www.kler.cn/news/363554.html

相关文章：

  • 052_python基于Python高校岗位招聘和分析平台
  • 2024年软件设计师中级（软考中级）详细笔记【11】知识产权基础知识（分值2~3分）
  • 视频网站系统的设计与实现(论文+源码)_kaic
  • 监控-08-skywalking监控告警
  • SQL高级查询03
  • Mac 使用 zsh 终端提示 zsh: killed 的问题
  • 【C++ 算法进阶】算法提升六
  • 《Pyhon入门:yield关键字常用用法》
  • solana phantom NFT图片显示不出来？
  • 【含开题报告+文档+PPT+源码】基于SpringBoot和Vue的编程学习系统
  • 鸿蒙中富文本编辑与展示
  • 资料下载 | ENOVIA企业集成框架解决方案
  • Spring Boot集成Shiro认证
  • Android 两种方式实现类似水波扩散效果
  • 手机pdf阅读器，用手机也能够阅读、编辑pdf文件
  • 右键以vscode打开目录的时候出现找不到应用程序
  • 亿佰特CAN转422、232、485模块解决高于115200波特率时设备失联问题
  • 一文掌握 jetbrains IDE 新 UI，还不会新 UI 的同学快看过来
  • OpenMediaVault安装插件以及重置web控制台密码
  • 软考攻略/超详细/系统集成项目管理工程师/基础知识分享18
  • Uefi Application小游戏开发之推箱子
  • idea启动报错：com.intellij.diagnostic.PluginException
  • 【数据结构】专栏开篇 | 1024程序员节
  • 信息库：Air780E量产binpkg文件的获取途径探究！
  • EureKa是什么?
  • 内存溢出与内存泄漏详解！