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

概述

单向链表分为单向有头链表和单线无头链表,本文针对单向有头链表使用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 <stdio.h>
#include "list_head.h"
/************************************
@ Brief: 创建链表头
@ 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: 按位置插入节点
@ 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: 按顺序插入节点
@ 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: 按位置删除节点
@ 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("%d\n", 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 <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("添加索引位置错误\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;
}

总结

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

(0)

相关推荐

  • C++ STL入门教程(2) list双向链表使用方法(附程序代码)

    一.简介 "Unlike other standard sequence containers, list and forward_list objects are specifically designed to be efficient inserting and removing elements in any position, even in the middle of the sequence." Lists将元素按顺序储存在链表中.与向量(vector)相比, 它允许快速

  • C++ 实现双向链表的实例

    双向链表C++ 的实现 本文是通过C++ 的知识实现数据结构中的双向链表,这里不多说 了,代码注释很清楚, 实现代码: //double LinkList implement with C++ template #include<iostream> using namespace std; /*template<typename Type> class DBListADT { public: virtual void Append(const Type &)=0; virt

  • C++数据结构与算法之反转链表的方法详解

    本文实例讲述了C++数据结构与算法之反转链表的方法.分享给大家供大家参考,具体如下: 算法概述:要求实现将一条单向链表反转并考虑时间复杂度. 算法分析: 数组法(略): 将列表元素逐个保存进数组,之后再逆向重建列表 点评:实现逻辑最简单,需要额外的内存开销. 移动指针: 通过三个指针逐个从链表头开始逐一反转链表元素的指针 点评:不需要额外的内存开销,会改变原始链表. 递归: 以递归的方式首先找到链表尾部,再逐一反转指针 点评:不需要额外的内存开销,不会改变原始链表. 算法实现: 构建链表结构 /

  • C++ 实现静态链表的简单实例

    C++ 实现静态链表的简单实例 用数组描述的链表,即称为静态链表. 在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标cur. 这种存储结构,仍需要预先分配一个较大的空间,但在作为线性表的插入和删除操作时不需移动元素,仅需修改指针,故仍具有链式存储结构的主要优点. 下图表示了静态链表的一中存储结构: 图中用彩色途上的是两个头结点,不存放数据,分别用来记录第一个备用节点和第一个数据节点的下标. 下面给出静态链表的C++实现代码: 首先给出头文件:StaticList.

  • 利用C++简单实现顺序表和单链表的示例代码

    本文主要给大家介绍了关于C++实现顺序表和单链表的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍: 一.顺序表示例代码: #include <assert.h> #include <iostream> using namespace std; typedef int Datatype; class SeqList { public: SeqList() :_array(NULL) ,_size(0) ,_capacity(0) { } SeqList(const

  • 使用C++实现顺序链表

    这是创建的LIst.h头文件 #ifndef LIST_H #define LIST_H class List { public: List(int size); ~List(); void DestroyList(); void ClearList(); bool ListEmpty(); int ListLength(); bool GetElem(int i, int *e); int LocateElem(int *e); bool ListInsert(int i, int *e);

  • C++删除链表中间节点的方法

    本文实例讲述了C++删除链表中间节点的方法.分享给大家供大家参考,具体如下: 题目: 给定链表头结点head,实现删除链表的中间节点函数. 解题思路及代码: 快慢指针,快指针走两步,慢指针一步. 当快指针走到终点时,慢指针正好是链表中间节点,删除此节点即可. 链表结构定义: typedef struct Node { int data; struct Node* next; }node, *pLinkedList; 算法C++代码: Node* removeMidNode(pLinkedList

  • C++数据结构之链表的创建

    C++数据结构之链表的创建 前言 1.链表在C/C++里使用非常频繁, 因为它非常使用, 可作为天然的可变数组. push到末尾时对前面的链表项不影响. 反观C数组和std::vector, 一个是静态大小, 一个是增加多了会对之前的元素进行复制改写(线程非常不安全). 2.通常创建链表都是有next这样的成员变量指向下一个项, 通过定义一个head,last来进行链表创建. 参考函数 TestLinkCreateStupid(). 说明 1.其实很早就知道另一种创建方式, 但是一直没总结. 没

  • C/C++ 双链表之逆序的实例详解

    C/C++ 双链表之逆序的实例详解 一.结点结构 双向链表的数据结构定义如下: typedef struct node { ElemType data; struct node *prior struct node *next; }list; 其中,ElemType可以是任意数据类型如int.float或者char等,在算法中,规定其默认为int类型. 二.带头结点 本文描述的是双向链表逆序,链表逆序需要维护3个指针,分别指向前一个节点.当前节点和下一个节点,具体代码如下: list *reve

  • C++中链表操作实例分析

    链表概述 链表是一种常见的重要的数据结构.它是动态地进行存储分配的一种结构.它可以根据需要开辟内存单元.链表有一个"头指针"变量,以head表示,它存放一个地址.该地址指向一个元素.链表中每一个元素称为"结点",每个结点都应包括两个部分:一为用户需要用的实际数据,二为下一个结点的地址.因此,head指向第一个元素:第一个元素又指向第二个元素:--,直到最后一个元素,该元素不再指向其它元素,它称为"表尾",它的地址部分放一个"NULL&q

随机推荐