C语言数据结构之单向链表(SingleList)
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;
}
/* --[#|#]-- */
- 下一步,研究双向链表!!!