Data structures and algorithms: Implementation and encapsulation of unidirectional linked lists
- 2020-06-12 10:13:09
- OfStack
An overview of the
One-way linked list can be divided into one-way headed list and single-line headless list. In this paper, C language is used to implement and encapsulate one-way headed list.
implementation
list_head h file
#ifndef _LIST_H_
#define _LIST_H_
typedef int datatype;
#define SUCC
#define MALLOC_FAIL 1
#define NOHEADNODE 2
#define INDEXFAIL 3
#define LIST_EMPTY 4
#define LIST_NOEMPTY 5
#define FAIL 10
typedef struct List_Node
{
datatype data;
struct List_Node* pNext;
}list;
list*list_create();
int list_insert_at(list* pHead, int i, datatype* pData);
int list_order_insert(list* pHead, datatype* pData);
int list_delete_at(list* pHead, int index);
int list_delete(list* pHead, datatype* pData);
int list_isempty(list* pHead);
void list_display(list* pHead);
void list_destory(list* pHead);
#endif // !_LIST_H_
list_head c file
/********************************************************
Copyright (C), 2016-2017,
FileName: list
Author: woniu201
Description: Unidirectional header linked list use
********************************************************/
#include <stdio.h>
#include "list_head.h"
/************************************
@ Brief: Create the watch header
@ Author: woniu201
@ Return:
************************************/
list* list_create()
{
list* pNode = (list *)malloc(sizeof(list));
memset(pNode, 0, sizeof(list));
if (pNode == NULL)
{
return MALLOC_FAIL;
}
pNode->pNext = NULL;
return pNode;
}
/************************************
@ Brief: Insert nodes by position
@ Author: woniu201
@ Return:
************************************/
int list_insert_at(list* pHead, int i, datatype* pData)
{
int j = 0;
if (pHead == NULL)
{
return NOHEADNODE;
}
list* pNode = pHead;
if (i<0)
{
return INDEXFAIL;
}
while (j< i && pNode !=NULL)
{
pNode = pNode->pNext;
j++;
}
if (pNode == NULL)
{
return INDEXFAIL;
}
else
{
list* newNode = (list*)malloc(sizeof(list));
if (newNode ==NULL)
{
return MALLOC_FAIL;
}
memset(newNode, 0, sizeof(list));
newNode->data = *pData;
pNode->pNext = newNode;
}
return SUCC;
}
/************************************
@ Brief: The nodes are inserted in order
@ Author: woniu201
@ Return:
************************************/
int list_order_insert(list* pHead, datatype* pData)
{
if (pHead == NULL)
{
return NOHEADNODE;
}
list* pNewNode = (list*)malloc(sizeof(list));
if (pNewNode == NULL)
{
return MALLOC_FAIL;
}
memset(pNewNode, 0, sizeof(list));
pNewNode->data = *pData;
list* pNode = pHead;
if (pNode->pNext == NULL)
{
pNode->pNext = pNewNode;
return SUCC;
}
while (pNode->pNext != NULL && pNode->pNext->data < *pData)
{
pNode = pNode->pNext;
}
if (pNode->pNext)
{
pNewNode->pNext = pNode->pNext;
pNode->pNext = pNewNode;
}
else
{
pNode->pNext = pNewNode;
}
return SUCC;
}
/************************************
@ Brief: Delete nodes by location
@ Author: woniu201
@ Return:
************************************/
int list_delete_at(list* pHead, int index)
{
int j = 0;
if (pHead == NULL)
{
return NOHEADNODE;
}
if (index < 0)
{
return INDEXFAIL;
}
list* pCur = pHead;
list* pNode = pHead;
while (pCur->pNext)
{
pNode = pCur;
pCur = pCur->pNext;
if (index == j)
{
break;
}
j++;
}
if (j< index)
{
printf(" This node does not exist \n");
return INDEXFAIL;
}
else
{
if (pCur->pNext == NULL)
{
pNode->pNext = NULL;
}
else
{
pNode->pNext = pCur->pNext;
}
free(pCur);
pCur = NULL;
}
return SUCC;
}
/************************************
@ Brief: Delete nodes by value
@ Author: woniu201
@ Return:
************************************/
int list_delete(list* pHead, datatype* pData)
{
if (pHead == NULL)
{
return NOHEADNODE;
}
list* pCur = pHead;
list* pNode = pHead;
int bFind = 0;
while (pCur->pNext)
{
pNode = pCur;
pCur = pCur->pNext;
if (pCur->data == *pData)
{
bFind = 1;
break;
}
}
if (!bFind)
{
printf(" This node does not exist \n");
return INDEXFAIL;
}
else
{
if (pCur->pNext == NULL)
{
pNode->pNext = NULL;
}
else
{
pNode->pNext = pCur->pNext;
}
free(pCur);
pCur = NULL;
}
return SUCC;
}
/************************************
@ Brief: Determine if the list is empty
@ Author: woniu201
@ Return:
************************************/
int list_isempty(list* pHead)
{
if (pHead->pNext == NULL)
{
return LIST_EMPTY;
}
else
{
return LIST_NOEMPTY;
}
}
/************************************
@ Brief: Walk through the printed list
@ Author: woniu201
@ Return:
************************************/
void list_display(list* pHead)
{
if (list_isempty(pHead) == LIST_EMPTY)
{
printf(" The list is empty \n");
return FAIL;
}
list* pNode = pHead->pNext;
while (pNode)
{
printf("%d\n", pNode->data);
pNode = pNode->pNext;
}
}
/************************************
@ Brief: Free list memory
@ Author: woniu201
@ Return:
************************************/
void list_destory(list* pHead)
{
list* pCur = pHead;
list* pNext = pHead->pNext;
while (pNext)
{
pNext = pNext->pNext;
free(pCur);
pCur = NULL;
pCur = pNext;
}
}
main c test
#include <stdio.h>
#include "list_head.h"
int main()
{
list* pHead = list_create();
int data1 = 1;
int data2 = 3;
int data3 = 2;
// int ret = list_insert_at(pHead,0, &data1);
// ret = list_insert_at(pHead, 1, &data2);
// if (ret == INDEXFAIL)
// {
// printf(" Error adding index position \n");
// }
list_order_insert(pHead, &data2);
list_order_insert(pHead, &data1);
list_order_insert(pHead, &data3);
list_delete_at(pHead, 3);
int deleteData = 1;
list_delete(pHead, &deleteData);
list_display(pHead);
list_destory(pHead);
return 1;
}
conclusion