玩转C线性表和单向链表之Linux双向链表优化

　　前言：

　　这次介绍基本数据结构的线性表和链表，并用C语言进行编写；建议最开始学数据结构时，用C语言；像栈和队列都可以用这两种数据结构来实现。

　　一、线性表基本介绍　　

　　1 概念：

线性表也就是关系户中最简单的一种关系，一对一。

如：学生学号的集合就是一个线性表。

2 特征：

① 有且只有一个“首元素“。

② 有且只有一个“末元素”。

③ 除“末元素”外，其余元素均有唯一的后继元素。

④ 除“首元素”外，其余元素均有唯一的前驱元素。

3 存储划分：

① 如果把线性表用“顺序存储”，那么就是“顺序表”。

② 如果把线性表用“链式存储”，那么就是“链表”。

4 常用操作：

　　添加，删除，插入，查找，遍历，统计。

　　二、线性表实现　　

　　主要实现线性表的创建、销毁和插入等操作，将接口封装在.h文件中，如下：

#ifndef  __MY_SEQLIST_H__ 
#define __MY_SEQLIST_H__

typedef void SeqList;
typedef void SeqListNode;

SeqList* SeqList_Create(int capacity);    //创建线性表

void SeqList_Destroy(SeqList* list);    //销毁
    
void SeqList_Clear(SeqList* list);        //清空

int SeqList_Length(SeqList* list);        //求线性表的长度

int SeqList_Capacity(SeqList* list);    //求线性表的容量

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);    //向线性表中插入元素

SeqListNode* SeqList_Get(SeqList* list, int pos);    //获取指定位置元素

SeqListNode* SeqList_Delete(SeqList* list, int pos);    //删除指定位置元素


#endif  //__MY_SEQLIST_H__

　　注意：定义头文件时，要包含“#ifndef”，防止头文件重复包含！

　　1、线性表创建

　　　主要就是对节点分配内存，代码如下：

//在结构体中套1级指针
//
typedef struct _tag_SeqList
{
    int length;
    int capacity;
    unsigned int *node;   //int* node[]
}TSeqList;

SeqList* SeqList_Create(int capacity)
{
    int ret = 0;
    TSeqList *tmp = NULL;

    tmp = (TSeqList *)malloc(sizeof(TSeqList));
    if (tmp == NULL)
    {
        ret = -1;
        printf("func SeqList_Create() err:%d 
", ret);
        return NULL;
    }
    memset(tmp, 0, sizeof(TSeqList));

    //根据capacity 的大小分配节点的空间
    tmp->node = (unsigned int *)malloc(sizeof(unsigned int *) * capacity);
    if (tmp->node  == NULL)
    {
        ret = -2;
        printf("func SeqList_Create() err: malloc err %d 
", ret);
        return NULL;
    }
    tmp->capacity = capacity;
    tmp->length = 0;
    return tmp;
}

void SeqList_Destroy(SeqList* list)
{
    TSeqList *tlist = NULL;
    if (list == NULL)
    {
        return ;
    }
    tlist = (TSeqList *)list;
    if (tlist->node != NULL)
    {
        free(tlist->node);
    }
    
    free(tlist);

    return ;
}

　　2、线性表插入

　　插入在业界有默认的规则吧，下面将要讲到的链表也是用这个规则。用图来讲解一下吧，如下：

　　讲解：例如，已经有线性表34、33、32、31，在1位置想插入35，想把从1开始的先后移，再插入，插入后的线性表如右图所示。

　　线性表插入代码如下：

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
    int i =0, ret = 0;
    TSeqList *tlist = NULL;

    if (list == NULL || node==NULL ||  pos<0)
    {
        ret = -1;
        printf("fun SeqList_Insert() err:%d 
", ret);
        return ret;
    }
    tlist = (TSeqList*)list;

    //判断是不是满了
    if (tlist->length >= tlist->capacity)
    {
        ret = -2;
        printf("fun SeqList_Insert() (tlist->length >= tlist->capacity) err:%d 
", ret);
        return ret;
    }

    //容错修正  6个长度 容量20;用户pos10位置插入..
    if (pos>=tlist->length)
    {
        pos = tlist->length; //
    }

    //1 元素后移
    for(i=tlist->length; i>pos; i--)
    {
        tlist->node[i] = tlist->node[i-1];
        //a[7] = a[6]
    }
    // i = 3
    // 2插入元素
    tlist->node[i] = (unsigned int )node;
    tlist->length ++;
    return 0;
}

　　3、获取指定位置元素

　　根据pos位置获取元素，代码如下：

SeqListNode* SeqList_Get(SeqList* list, int pos)
{
    int i =0;
    SeqListNode *ret = 0;
    TSeqList *tlist = NULL;

    if (list == NULL ||  pos<0)
    {
        printf("fun SeqList_Get() err:%d 
", ret);
        return NULL;
    }
    tlist = (TSeqList*)list;

    ret = (void *)tlist->node[pos];
    return ret;
}

　　4、删除指定位置元素

　　将指定位置的元素进行删除，代码如下：

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
    int i = 0;
    SeqListNode *ret = 0;
    TSeqList *tlist = NULL;

    if (list == NULL ||  pos<0) //检查
    {
        printf("fun SeqList_Delete() err:%d 
", ret);
        return NULL;
    }
    tlist = (TSeqList*)list;

    ret = (SeqListNode *)tlist->node[pos]; //缓存pos的位置
     
    for (i=pos+1; i<tlist->length; i++)  //pos位置后面的元素前移
    {
        tlist->node[i-1] = tlist->node[i];
    }
    tlist->length --;
    return ret;
}

　　5、总体代码

　　整个seqlist.c代码如下，方便使用与调试：

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "seqlist.h"


//在结构体中套1级指针
//
typedef struct _tag_SeqList
{
    int length;
    int capacity;
    unsigned int *node;   //int* node[]
}TSeqList;

SeqList* SeqList_Create(int capacity)
{
    int ret = 0;
    TSeqList *tmp = NULL;

    tmp = (TSeqList *)malloc(sizeof(TSeqList));
    if (tmp == NULL)
    {
        ret = -1;
        printf("func SeqList_Create() err:%d 
", ret);
        return NULL;
    }
    memset(tmp, 0, sizeof(TSeqList));

    //根据capacity 的大小分配节点的空间
    tmp->node = (unsigned int *)malloc(sizeof(unsigned int *) * capacity);
    if (tmp->node  == NULL)
    {
        ret = -2;
        printf("func SeqList_Create() err: malloc err %d 
", ret);
        return NULL;
    }
    tmp->capacity = capacity;
    tmp->length = 0;
    return tmp;
}

void SeqList_Destroy(SeqList* list)
{
    TSeqList *tlist = NULL;
    if (list == NULL)
    {
        return ;
    }
    tlist = (TSeqList *)list;
    if (tlist->node != NULL)
    {
        free(tlist->node);
    }
    
    free(tlist);

    return ;
}

//清空链表 //回到初始化状态
void SeqList_Clear(SeqList* list)
{
    TSeqList *tlist = NULL;
    if (list == NULL)
    {
        return ;
    }
    tlist = (TSeqList *)list;
    tlist->length = 0; 
    return ;
}

int SeqList_Length(SeqList* list)
{
    TSeqList *tlist = NULL;
    if (list == NULL)
    {
        return -1;
    }
    tlist = (TSeqList *)list;
    return tlist->length;
}

int SeqList_Capacity(SeqList* list)
{

    TSeqList *tlist = NULL;
    if (list == NULL)
    {
        return -1;
    }
    tlist = (TSeqList *)list;
    return tlist->capacity;
}

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
    int i =0, ret = 0;
    TSeqList *tlist = NULL;

    if (list == NULL || node==NULL ||  pos<0)
    {
        ret = -1;
        printf("fun SeqList_Insert() err:%d 
", ret);
        return ret;
    }
    tlist = (TSeqList*)list;

    //判断是不是满了
    if (tlist->length >= tlist->capacity)
    {
        ret = -2;
        printf("fun SeqList_Insert() (tlist->length >= tlist->capacity) err:%d 
", ret);
        return ret;
    }

    //容错修正  6个长度 容量20;用户pos10位置插入..
    if (pos>=tlist->length)
    {
        pos = tlist->length; //
    }

    //1 元素后移
    for(i=tlist->length; i>pos; i--)
    {
        tlist->node[i] = tlist->node[i-1];
        //a[7] = a[6]
    }
    // i = 3
    // 2插入元素
    tlist->node[i] = (unsigned int )node;
    tlist->length ++;
    return 0;
}

SeqListNode* SeqList_Get(SeqList* list, int pos)
{
    int i =0;
    SeqListNode *ret = 0;
    TSeqList *tlist = NULL;

    if (list == NULL ||  pos<0)
    {
        printf("fun SeqList_Get() err:%d 
", ret);
        return NULL;
    }
    tlist = (TSeqList*)list;

    ret = (void *)tlist->node[pos];
    return ret;
}

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
    int i = 0;
    SeqListNode *ret = 0;
    TSeqList *tlist = NULL;

    if (list == NULL ||  pos<0) //检查
    {
        printf("fun SeqList_Delete() err:%d 
", ret);
        return NULL;
    }
    tlist = (TSeqList*)list;

    ret = (SeqListNode *)tlist->node[pos]; //缓存pos的位置
     
    for (i=pos+1; i<tlist->length; i++)  //pos位置后面的元素前移
    {
        tlist->node[i-1] = tlist->node[i];
    }
    tlist->length --;
    return ret;
}

View Code

　　6、调试

　　写一个main函数，进行上面的接口调用与调试，代码如下：

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "seqlist.h"
typedef struct _Teacher
{
    int age;
    char name[64];
}Teacher;

void main()
{
    int        ret = 0, i = 0;
    SeqList* list = NULL;

    Teacher t1, t2, t3, t4,t5;
    t1.age = 31;
    t2.age = 32;
    t3.age = 33;
    t4.age = 34;
    t5.age = 35;

    list = SeqList_Create(10);
    if (list == NULL)
    {
        printf("func SeqList_Create() ret :%d 
", ret);
        return ;
    }

    ret = SeqList_Insert(list, (SeqListNode*) &t1, 0); //头插法
    ret = SeqList_Insert(list, (SeqListNode*) &t2, 0); //头插法
    ret = SeqList_Insert(list, (SeqListNode*) &t3, 0); //头插法
    ret = SeqList_Insert(list, (SeqListNode*) &t4, 0); //头插法
    ret = SeqList_Insert(list, (SeqListNode*) &t5, 1); //头插法

    //遍历
    for (i=0; i<SeqList_Length(list); i++)
    {
        Teacher*  tmp = (Teacher *) SeqList_Get(list, i);
        if (tmp == NULL)
        {
            return ;
        }
        printf("tmp->age:%d ", tmp->age);
    }

    //删除链表中的节点
    while( SeqList_Length(list) > 0 )
    {
        SeqList_Delete(list, 0);
    }

    system("pause");

    return ;
}

　三、链表

　　1、介绍

　　链表的大体有三种实现方式，用图进行讲解吧，如下图：

　　　说明：最上面就是最传统链表，每个节点存一个next指针，保存下一个节点的地址

　　　　　　中间是linux内核实现的链表，一般是双向链表，有一个缺点要记录偏移量

　　　　　　最后是改进之后的链表，不需要记录偏移量，这是前人的智慧，我将采用最后一种进行实现。

　　2、定义头文件

　　头文件主要包含结构体定义，和接口声明，主要实现链表初始化、插入、遍历等操作，头文件如下：　

#ifndef LINKLIST_H
#define LINKLIST_H

#include<stdlib.h>
#include<stdio.h>

//链表结点
typedef struct LINKNODE{
    void* data;  //指向任何类型的数据
    struct LINKNODE* next;
}LinkNode;

//链表结构体
typedef struct LINKLIST{
    LinkNode* head;
    int size;
}LinkList;

//定义函数指针
typedef void(*PRINTLINKNODE)(void*);

//初始化链表
LinkList* Init_LinkList();
//指定位置插入
void Insert_LinkList(LinkList* list,int pos,void* data);
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos);
//获得链表的长度
int Size_LinkList(LinkList* list);
//查找
int Find_LinkList(LinkList* list,void* data);
//返回第一个结点
void* Front_LinkList(LinkList* list);
//打印链表结点
void Print_LinkList(LinkList* list, PRINTLINKNODE print);
//释放链表内存
void FreeSpace_LinkList(LinkList* list);


#endif

　　3、插入节点

　　初始化链表跟线性表类似，就不在过多说明了，主要讲解插入和删除节点，对插入节点进行讲解，如下图：

　　说明：需要两个指针current、node，假如在3号位置进行插入，要先处理node->next，node指向3号位置，就把3号位置指针付给它，node->next=current->next;

2号位置指向node，把node指针赋值给它，current->next=node;

　　注意：图片左下角的红字，是理解链表插入、删除等的关键！

　　代码如下：

//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data){

    if (list == NULL){
        return;
    }
    if (data == NULL){
        return;
    }

    //友好的处理，pos越界 
    if (pos < 0 || pos > list->size) {
        pos = list->size;
    }

    //创建新的结点
    LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
    newnode->data = data;
    newnode->next = NULL;

    //找结点
    //辅助指针变量
    LinkNode* pCurrent = list->head;
    for (int i = 0; i < pos;i++){
        pCurrent = pCurrent->next;
    }

    //新结点入链表
    newnode->next = pCurrent->next;
    pCurrent->next = newnode;

    list->size++;
}

　　4、删除节点

　　说明：

　　删除3号位置，先保存被删除节点的位置，再将2直接指向4；

　　5、整体代码

　　整个的代码，方便大家使用和调试，代码如下：

#include"LinkList.h"

//初始化链表
LinkList* Init_LinkList(){

    LinkList* list = (LinkList*)malloc(sizeof(LinkList));
    list->size = 0;

    //头结点 是不保存数据信息
    list->head = (LinkNode*)malloc(sizeof(LinkNode));
    list->head->data = NULL;
    list->head->next = NULL;

    return list;
}
//指定位置插入
void Insert_LinkList(LinkList* list, int pos, void* data){

    if (list == NULL){
        return;
    }
    if (data == NULL){
        return;
    }

    //友好的处理，pos越界 
    if (pos < 0 || pos > list->size) {
        pos = list->size;
    }

    //创建新的结点
    LinkNode* newnode = (LinkNode*)malloc(sizeof(LinkNode));
    newnode->data = data;
    newnode->next = NULL;

    //找结点
    //辅助指针变量
    LinkNode* pCurrent = list->head;
    for (int i = 0; i < pos;i++){
        pCurrent = pCurrent->next;
    }

    //新结点入链表
    newnode->next = pCurrent->next;
    pCurrent->next = newnode;

    list->size++;

}
//删除指定位置的值
void RemoveByPos_LinkList(LinkList* list, int pos){
    if (list == NULL){
        return;
    }

    if (pos < 0 || pos >= list->size){
        return;
    }

    //查找删除结点的前一个结点
    LinkNode* pCurrent = list->head;
    for (int i = 0; i < pos;i ++){
        pCurrent = pCurrent->next;
    }

    //缓存删除的结点
    LinkNode* pDel = pCurrent->next;
    pCurrent->next = pDel->next;
    //释放删除结点的内存
    free(pDel);

    list->size--;
}
//获得链表的长度
int Size_LinkList(LinkList* list){
    return list->size;
}
//查找
int Find_LinkList(LinkList* list, void* data){
    if (list == NULL){
        return -1;
    }

    if (data == NULL){
        return -1;
    }

    //遍历查找
    LinkNode* pCurrent = list->head->next;
    int i = 0;
    while (pCurrent != NULL){
        if (pCurrent->data == data){
            break;
        }
        i++;
        pCurrent = pCurrent->next;
    }

    return i;
}
//返回第一个结点
void* Front_LinkList(LinkList* list){
    return list->head->next->data;
}
//打印链表结点
void Print_LinkList(LinkList* list, PRINTLINKNODE print){
    if (list == NULL){
        return;
    }
    //辅助指针变量
    LinkNode* pCurrent = list->head->next;
    while (pCurrent != NULL){
        print(pCurrent->data);
        pCurrent = pCurrent->next;
    }

}
//释放链表内存
void FreeSpace_LinkList(LinkList* list){

    if (list == NULL){
        return;
    }

    //辅助指针变量
    LinkNode* pCurrent = list->head;
    while (pCurrent != NULL){
        //缓存下一个结点
        LinkNode* pNext = pCurrent->next;
        free(pCurrent);
        pCurrent = pNext;
    }

    //释放链表内存
    list->size = 0;
    free(list);

}

View Code

　　6、调试代码

　　写一个main函数进行调试，如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkList.h"


//自定义数据类型
typedef struct PERSON{
    char name[64];
    int age;
    int score;
}Person;


//打印函数
void MyPrint(void* data){
    Person* p = (Person*)data;
    printf("Name:%s Age:%d Score:%d
",p->name,p->age,p->score);
}

int main(void){
    

    //创建链表
    LinkList* list = Init_LinkList();

    //创建数据
    Person p1 = { "aaa", 16, 100};
    Person p2 = { "bbb", 17, 99 };
    Person p3 = { "ccc", 18, 101 };
    Person p4 = { "ddd", 19, 97 };
    Person p5 = { "eee", 20, 59 };

    //数据插入链表
    Insert_LinkList(list, 0, &p1);
    Insert_LinkList(list, 0, &p2);
    Insert_LinkList(list, 0, &p3);
    Insert_LinkList(list, 0, &p4);
    Insert_LinkList(list, 2, &p5);

    //打印
    Print_LinkList(list, MyPrint);

    //删除3
    RemoveByPos_LinkList(list, 3);

    //打印
    printf("---------------
");
    Print_LinkList(list, MyPrint);

    //返回第一个结点
    printf("-----查找结果------------
");
     Person* ret = (Person*)Front_LinkList(list);
     printf("Name:%s Age:%d Score:%d
", ret->name, ret->age, ret->score);

    //销毁链表
    FreeSpace_LinkList(list);

    system("pause");
    return 0;
}

View Code

　　运行结果如下，供参考：

　　四、补充C++实现链表

　　1、头文件

　　头文件LinkedList.h,代码如下：

#include <iostream>

template<class T>
class Node {    //节点类
public:
    T e;    //数据域
    Node *next;    //指针域

    Node(T e, Node *next) : e(e), next(next) {    //构造函数的列表初始化
    }

    Node(T e) : e(e), next(nullptr) {
    }
    
    Node() : next(nullptr) {    //无参构造函数
    }
};

template<class T>
class LinkedList {
private:
    Node<T> *head;    //头结点
    int size;
public:
    class Range {
    };

    class Empty {
    };

    LinkedList() {    //构造函数
        head = new Node<T>();
    size = 0;
    }

    int getSize() {    //获取大小
        return size;
    }

    bool isEmpty() {    //判断是否为空
        return size == 0;
    }

    void add(int index, T e) {    //指定位置插入元素
        if (index < 0 || index > size) {
            throw Range();
        }
        Node<T> *prev = head;
        for (int i = 0; i < index; ++i) {
            prev = prev->next;
        }
        prev->next = new Node<T>(e, prev->next);
        size++;
    }

    void addFirst(T e) {    //插入元素 头插法
        add(0, e);
    }

    void addLast(T e) {        //插入元素 尾插法
        add(size, e);
    }

    T get(int index) {    //获取元素
        if (size == 0) {
            throw Empty();
        }
        if (index < 0 || index >= size) {
            throw Range();
        }
        Node<T> *cur = head->next;
        for (int i = 0; i < index; ++i) {
            cur = cur->next;
        }
        return cur->e;
    }

    T getFirst() {
        return get(0);
    }

    T getLast() {
        return get(size - 1);
    }

    void set(int index, T e) {
        if (size == 0) {
            throw Empty();
        }
        if (index < 0 || index >= size) {
            throw Range();
        }
        Node<T> *cur = head->next;
        for (int i = 0; i < index; ++i) {
            cur = cur->next;
        }
        cur->e = e;
    }

    void setFirst(T e) {
        set(0, e);
    }

    void setLast(T e) {
        set(size - 1, e);
    }

    T remove(int index) {    //删除指定位置元素
        if (index < 0 || index >= size) {
            throw Range();
        }
        if (size == 0) {
            throw Empty();
        }
        Node<T> *prev = head;
        for (int i = 0; i < index; ++i) {
            prev = prev->next;
        }
        Node<T> *retNode = prev->next;
        prev->next = retNode->next;
        retNode->next = nullptr;
        size--;
        return retNode->e;
    }

    T removeFirst() {
        return remove(0);
    }

    T removeLast() {
        return remove(size - 1);
    }

    void removeElement(T e) {
        Node<T> *prev = head;
        while (prev->next != nullptr) {
            if (prev->next->e == e) {
                break;
            }
            prev = prev->next;
        }

        if (prev->next != nullptr) {
            Node<T> *delNode = prev->next;
            prev->next = delNode->next;
            delNode->next = nullptr;
            size--;
        }
    }

    bool contains(T e) {    //是否包含
        Node<T> *cur = head;
        for (int i = 0; i < size; ++i) {
            cur = cur->next;
            if (cur->e == e) {
                return true;
            }
        }
        return false;
    }

    void print() {    //打印输出
        Node<T> *prev = head;
        std::cout << "LinkedList: size = " << size << std::endl;
        std::cout << "[";
        for (int i = 0; i < size; ++i) {
            prev = prev->next;
            std::cout << prev->e;
            if (i < size - 1) {
                std::cout << ", ";
            }
        }
        std::cout << "]" << std::endl;
    }
};

View Code

　　2、main函数

　　main.cpp如下：

#include <iostream>
#include "LinkedList.h"

int main() {
    LinkedList<int> *linkedList = new LinkedList<int>();
    for (int i = 0; i < 5; ++i) {
        linkedList->addFirst(i);    //头插法
    }
    linkedList->add(2, 30);    //指定位置插入元素
    linkedList->print();     //打印输出
    linkedList->remove(2);    //删除指定位置元素
    linkedList->print();
    linkedList->removeFirst();
    linkedList->print();
    linkedList->removeLast();
    linkedList->print();   
    return 0;
}

　　3、测试

　　运行结果如下：

　　总结

　　虽然线性表和单向链表是数据结构的基础，但完全掌握之后，再学习栈、队列等数据结构将会得心应手；

　　喜欢的希望帮忙点赞，不懂的欢迎随时留言！