C# · 12月 19, 2021

数据结构与算法:单向链表实现与封装

概述

单向链表分为单向有头链表和单线无头链表,本文针对单向有头链表使用C语言来实现并进行封装。

实现

list_head.h文件

#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文件

/********************************************************

Copyright (C),2016-2017,

FileName: list

Author: woniu201

Description:单向有头链表使用

********************************************************/

#include

#include “list_head.h”

/************************************

@ Brief: 创建链表头

@ Author: woniu201

@ Return:

************************************/

list* list_create()

{

list* pNode = (list *)malloc(sizeof(list));

memset(pNode,sizeof(list));

if (pNode == NULL)

{

return MALLOC_FAIL;

}

pNode->pNext = NULL;

return pNode;

}

/************************************

@ Brief: 按位置插入节点

@ Author: woniu201

@ Return:

************************************/

int list_insert_at(list* pHead,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,sizeof(list));

newNode->data = *pData;

pNode->pNext = newNode;

}

return SUCC;

}

/************************************

@ Brief: 按顺序插入节点

@ 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,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: 按位置删除节点

@ 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(“不存在该节点n”);

return INDEXFAIL;

}

else

{

if (pCur->pNext == NULL)

{

pNode->pNext = NULL;

}

else

{

pNode->pNext = pCur->pNext;

}

free(pCur);

pCur = NULL;

}

return SUCC;

}

/************************************

@ Brief: 按值删除节点

@ 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(“不存在该节点n”);

return INDEXFAIL;

}

else

{

if (pCur->pNext == NULL)

{

pNode->pNext = NULL;

}

else

{

pNode->pNext = pCur->pNext;

}

free(pCur);

pCur = NULL;

}

return SUCC;

}

/************************************

@ Brief: 判断链表是否为空

@ Author: woniu201

@ Return:

************************************/

int list_isempty(list* pHead)

{

if (pHead->pNext == NULL)

{

return LIST_EMPTY;

}

else

{

return LIST_NOEMPTY;

}

}

/************************************

@ Brief: 遍历打印链表

@ Author: woniu201

@ Return:

************************************/

void list_display(list* pHead)

{

if (list_isempty(pHead) == LIST_EMPTY)

{

printf(“链表为空n”);

return FAIL;

}

list* pNode = pHead->pNext;

while (pNode)

{

printf(“%dn”,pNode->data);

pNode = pNode->pNext;

}

}

/************************************

@ Brief: 释放链表内存

@ 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 测试

#include

#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,&data1);

// ret = list_insert_at(pHead,1,&data2);

// if (ret == INDEXFAIL)

// {

// printf(“添加索引位置错误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;

}

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对的支持。如果你想了解更多相关内容请查看下面相关链接