List of List with header pointer
First, origin
It was very early to write a list of a header pointer, which inserted from the tail into an element, deleted an element in any location, and found a bug when using this LIST, corrected, and added several interface functions. Passed, I hope to use the beginners of C.
Second, the basic description
2.1, data structure
l ListNode
Typedef struct listnode
{
Int Data; // you can add any type data here
Int ID;
Struct ListNode * Next;
} * ListNode, _ListNode;
Where Data, ID is used for test programs, can be replaced with any data type.
l list
Typedef struct list
{
Struct ListNode * HEAD;
Struct ListNode * tail;
INT count; // 0 --empty
INT Current_ID;
} * list, _list;
HEAD, TAIL points to the actual elements, when the List is empty, pointing null, current_id for test programs, can go.
2.2, function description
l void List_init (list)
Initialize List
l void List_insert (List, ListNode)
List's tail insertion element
l int List_delete (List, ListNode)
Delete the specified element from the list, delete successful return 1. Delete failed to return 0
l void list_poll (List myroot)
Traverse the entire pool, test
l ListNode New_ListNode (const Int ID, INT DATA)
Build new elements and assign memory for them
l void delete_listnode (listnode mylistNode)
Delete the specified element and release its memory
l ListNode Find_Node_BY_DATA (List Myroot, Const Int Data)
Find matching elements based on DATA on LIST
l ListNode Find_Node_BY_ID (List Myroot, Const Int)
Find matching elements based on IDs on list
Third, code
3.1, List.h:
/ * list.h
** Copyright 2004 Coon Xu.
** Author: coon Xu
**
Date: 02
Feb 2005
* /
#ifndef list_h
#define list_h
#include
#include
Typedef struct listnode
{
Int Data; // you can add any type data here
Int ID;
Struct ListNode * Next;
} * ListNode, _ListNode;
Typedef struct list
{
Struct ListNode * HEAD;
Struct ListNode * tail;
INT count; // 0 --empty
INT Current_ID;
} * list, _list;
Void List_init (list);
Void List_insert (List, ListNode);
INT list_delete (List, ListNode); Void List_Poll (List Myroot);
ListNode New_ListNode (const Int ID, INT DATA);
Void delete_listnode (listnode mylistnode);
ListNode Find_Node_BY_DATA (List Myroot, Const Int Data);
ListNode Find_Node_BY_ID (List Myroot, Const Int);
#ENDIF
3.2, List.c:
/ * list.c
** Copyright 2004 Coon Xu.
** Author: coon Xu
**
Date: 02
Feb 2005
* /
#include "list.h"
Void List_init (List Myroot)
{
MYROOT-> count = 0;
MYROOT-> Head = NULL;
MYROOT-> TAIL = NULL;
MYROOT-> CURRENT_ID = 1;
}
Void List_Poll (List Myroot)
{
Printf ("--------------------------------------------- -------- / n ");
ListNode p_listnode = myroot-> head;
While (p_listnode! = NULL)
{
Printf ("ID:% D / T DATA:% D / N", P_ListNode-> ID, P_ListNode-> Data);
P_ListNode = p_listnode-> next;
}
}
// INSERT Node At the Tail
Void List_insert (List Myroot, ListNode MyListNode)
{
MYROOT-> COUNT ;
MyListNode-> Next = NULL;
IF (myroot-> head == null)
{
MYROOT-> Head = myListNode;
MYROOT-> TAIL = MYLISTNODE;
}
Else
{
MYROOT-> TAIL-> Next = myListNode;
MYROOT-> TAIL = MYLISTNODE;
}
Printf ("[INSERT]: / TList.cout: / T% D / N", myroot-> count);
}
Int list_delete (List Myroot, ListNode MyListNode)
{
Struct ListNode * p_listnode = myroot-> head;
Struct ListNode * pre_listnode;
// myroot is Empty
IF (p_listnode == null)
{
Return 0;
}
// delete head node
IF (p_listnode == myListNode)
{
MYROOT-> COUNT -;
// MYROOT HAS ONLY One Node
IF (myroot-> tail == myListNode)
{
MYROOT-> Head = NULL;
MYROOT-> TAIL = NULL;
}
Else
{
MYROOT-> Head = p_listnode-> next;}
Printf ("[delete]: / tlist.cout: / t% d / n", myroot-> count);
Return 1;
}
While (p_listnode! = NULL)
{
IF (p_listnode == myListNode)
{
Break;
}
pre_listnode = p_listnode;
P_ListNode = p_listnode-> next;
}
IF (p_listnode == null)
{
Printf ("can not find the node ... / n");
Return 0;
}
Else
{
pre_listnode-> next = p_listnode-> next;
IF (myroot-> tail == p_listnode)
{
MYROOT-> TAIL = pre_listnode;
}
MYROOT-> COUNT -;
Printf ("[delete]: / tlist.cout: / t% d / n", myroot-> count);
Return 1;
}
}
ListNode New_ListNode (const Int ID, INT DATA)
{
ListNode p_listnode = malloc (sizeof (_listNode));
p_ListNode-> ID = ID;
P_ListNode-> Data = DATA;
Return P_ListNode;
}
Void Delete_ListNode (ListNode MyListNode)
{
MyListNode-> Next = NULL;
Free (myListNode);
MYListNode = NULL;
}
ListNode Find_Node_BY_DATA (List Myroot, Const Int Data)
{
ListNode p_listnode = myroot-> head;
While (p_listnode! = NULL)
{
IF (p_listnode-> data == data)
{
Printf ("Find The Node for Data:% D / N", DATA);
Break;
}
P_ListNode = p_listnode-> next;
}
Return P_ListNode;
}
ListNode Find_Node_BY_ID (List Myroot, Const Int)
{
ListNode p_listnode = myroot-> head;
While (p_listnode! = NULL)
{
IF (p_listnode-> id == id)
{
Printf ("Find The Node for ID:% D / N", ID);
Break;
}
P_ListNode = p_listnode-> next;
}
Return P_ListNode;
}
3.3, with a test of the main program
Main.c:
#include
#include
#include "list.h"
Int main (int Argc, char * argv [])
{
List mylist = malloc (sizeof (_list));
List_init (mylist);
INT IX = 0;
For (ix = 0; ix <10; ix )
{
ListNode my_listnode = new_listnode ((myList-> current_id) , ix);
List_insert (mylist, my_listnode);
}
List_poll (mylist);
// delete head node and test
ListNode my_listnode = find_node_by_id (mylist, 1);
List_delete (MyList, My_ListNode);
delete_listnode; m_listnode;
List_poll (mylist);
// INSERT a Node and Test
MY_LISTNODE = New_ListNode ((MyList-> Current_ID) , 100);
List_insert (mylist, my_listnode);
List_poll (mylist);
// delete tail node and test
MY_LISTNODE = FIND_NODE_BY_ID (MYLIST, 10);
List_delete (MyList, My_ListNode);
delete_listnode; m_listnode;
List_poll (mylist);
// INSERT a Node and Test
MY_LISTNODE = New_ListNode ((MyList-> Current_ID) , 200);
List_insert (mylist, my_listnode);
List_poll (mylist);
// delete a normal node and test
MY_LISTNODE = FIND_NODE_BY_DATA (MYLIST, 6);
List_delete (MyList, My_ListNode);
Delete_listnode;
List_poll (mylist);
// INSERT a Node and Test
My_ListNode = new_listnode ((myList-> current_id) , 300);
List_insert (mylist, my_listnode);
List_poll (mylist);
// delete Head Node Again and Test
MY_LISTNODE = FIND_NODE_BY_ID (MyList, 2);
List_delete (MyList, My_ListNode);
delete_listnode; m_listnode;
List_poll (mylist);
// INSERT a Node and Test
MY_LISTNODE = New_ListNode ((MyList-> Current_ID) , 400);
List_insert (mylist, my_listnode);
List_poll (mylist);
System ("pause");
Return 0;
}
