[C language data structure] static single linked list

StaticLinkLinst.h

# ifndef STATIC_LINKLIST_H#define STATIC_LINKLIST_Htypedef void StaticLinkListNode; / / static single linked list node typedef void StaticLinkList; / / static single linked list / * * create static single linked list * @ maximum capacity of param capacity static single linked list * @ return returns pointer to static single linked list * / StaticLinkList* StaticLinkList_Create (int capacity) / * * destroy static single linked list * @ param list static single linked list pointer * / void StaticLinkList_Destroy (StaticLinkList * list); / * * clear static single linked list * @ param list static single linked list pointer * / void StaticLinkList_Clear (StaticLinkList * list) / * * insert element into static single linked list pos position * @ param list static single linked list pointer * @ param node element pointer * @ param pos inserted index * / int StaticLinkList_Insert (StaticLinkList * list,StaticLinkListNode * node,int pos) / * * get the element at the index position in the static single linked list * @ param list static single linked list pointer * @ param pos static single linked list index value * @ param return element pointer * / StaticLinkListNode* StaticLinkList_Get (StaticLinkList * list,int pos) / * * delete the value at the index position in the static single-linked list * @ param list static single-linked list pointer * @ param pos static single-linked list index * @ param return non-zero indicates that the deletion was successful * / int StaticLinkList_Remove (StaticLinkList * list,int pos) / * * get the number of currently stored elements in static single linked list * @ pointer to param list static single linked list * @ return static single linked list number of stored elements * / int StaticLinkList_Length (StaticLinkList * list) / * * get the maximum number of storage elements of static single linked list * @ param list pointer of static single linked list * @ return maximum number of storage elements of static single linked list * / int StaticLinkList_Capacity (StaticLinkList * list); # endif / / STATICLINKLIST_H

StaticLinkList.c

# include "StaticLinkList.h" # include "malloc.h" # define NO_NODE-1typedef struct _ StaticLinkListNode {unsigned int data; / / data field pointer int next; / / array subscript of the next node} TStaticLinkListNode;typedef struct _ StaticLinkList {int length; int capacity; TStaticLinkListNode node []; / / flexible array} TStaticLinkList for storing static linked lists / * * create static single linked list * @ maximum capacity of param capacity static single linked list * @ return returns the pointer to the static single linked list * / StaticLinkList* StaticLinkList_Create (int capacity) {/ / because the 0 position of the flexible array is used as the header node, the actual capacity is capapcity + 1 size_t size = sizeof (TStaticLinkList) + sizeof (TStaticLinkListNode) * (capacity + 1); TStaticLinkList * list = (TStaticLinkList *) malloc (size) If (list! = 0) {int I; list- > capacity = capacity; list- > length = 0; list- > node [0]. Next = 0; for (I = 1 for I Node [I]. Next = NO_NODE;}} return list } / * * destroy static single linked list * @ param list static single linked list pointer * / void StaticLinkList_Destroy (StaticLinkList * list) {free (list);} / * * clear static single linked list * @ param list static single linked list pointer * / void StaticLinkList_Clear (StaticLinkList * list) {if (list! = 0) {TStaticLinkList * s_list = (TStaticLinkList *) list; listings-> length = 0 }} / * * insert element * @ param list static single linked list pointer * @ param node element pointer * @ param pos inserted index * @ param return non-zero indicates successful insertion * / int StaticLinkList_Insert (StaticLinkList * list,StaticLinkListNode * node,int pos) {TStaticLinkList * s_list = (TStaticLinkList *) list / / determine that the linked list and node pointer are not null, the location is legal, and the increased capacity will not exceed the maximum capacity int ret = ((s_list! = 0) & & (node! = 0) & & (pos > = 0) & &\ (pos length) & & (slots list-> length + 1 capacity + 1)); if (ret) {int index =-1 / / the array subscript of the element to be placed int current = 0; / / the array subscript of the current node int I = 0; / / traverses to find the empty item for in the array (I = 1; I capacity NO_NODE +) {if (slots list-> Node [I]. Next = = NO_NODE) {index = I; break;}} / / move to the front for (I = 0; I) where you need to insert the position

< pos ; i++) { current = s_list->

Node [current] .next;} node; listings-> Node [index] .next = index; listings-> node [current] .Next; swatches listings-> Node [index] .data = (unsigned int) slotted listings-> node [current] .next = index; slots listings-> length++;} return ret } / * * get the element * @ param list static single linked list pointer * @ param pos static single linked list index value * @ param return element pointer * / StaticLinkListNode* StaticLinkList_Get (StaticLinkList * list,int pos) {TStaticLinkListNode * s_node = 0; TStaticLinkList * s_list = (TStaticLinkList *) list; if ((list! = 0) & (pos > = 0) & (pos)

< s_list->

Length) {int current = 0; int index =-1; int I; / / move to the location where you need to query for (I = 0; I

< pos ; i++) { current = s_list->

Index [current] .next;} / get the array subscript of the element s_node = current list-> Node [current] .next; / / cast the type in data to StaticLinkListNode *, because the node pointer s_node = (StaticLinkListNode *) slotlist-> node [index] .data;} node is saved when you insert it. } / * * Delete the value at the index position in the static single linked list * @ param list static single linked list pointer * @ param pos static single linked list index * @ param return non-zero indicates deletion succeeded * / int StaticLinkList_Remove (StaticLinkList * list,int pos) {TStaticLinkList * s_list = (TStaticLinkList *) list; int ret = (s_list! = 0) & & (pos > = 0) & (pos)

< s_list->

Length); if (ret) {int index =-1; int current = 0; int I = 0; for (I = 0; I

< pos;i++) { current = s_list->

Index [current] .next;} / / the array subscript of the deleted element: Node [current] .next; / / assign the subsequent subscript of the deleted element to the subsequent subscript of the deleted element except the precursor of the deleted element, slist.node [current] .next = slist.node.next / / set the subscript of the deleted element as NO_NODE slots list-> Node [index] .next = NO_NODE; slots list-> length--;} return ret } / * * get the number of currently stored elements in static single linked list * @ pointer to param list static single linked list * @ number of stored elements in static single linked list * / int StaticLinkList_Length (StaticLinkList * list) {int ret =-1; if (list! = 0) {TStaticLinkList * s_list = (TStaticLinkList *) list; ret = slots list-> length;} return ret } / * * get the maximum number of storage elements in static single linked list * @ pointer to param list static single linked list * @ return maximum number of storage elements in static single linked list * / int StaticLinkList_Capacity (StaticLinkList * list) {int ret =-1; if (list! = 0) {TStaticLinkList * s_list = (TStaticLinkList *) list; ret = storage list-> capacity;} return ret;}

Test code

# include # include "StaticLinkList.h" int main (void) {int iPowerj. int a [5]; StaticLinkList * list = StaticLinkList_Create (5); for (I = 0 [I] = 5) {a [I] = I;} for (I = 0 [I] < 5]) {StaticLinkList_Insert (list,& (a [I]), 0);} StaticLinkList_Remove (list,0); for (I = 0) I < StaticLinkList_Length (list); iTunes +) {j = StaticLinkList_Get (list,i); printf ("% d\ n", * j);} return 0;}