数据结构(二)链表操作

数据结构…本系列旨在对基础算法进行记录和学习,为了之后的面试一个弥补~~

本系列不是科普文,是为了找工作快速拾遗系列.

快速浏览,不会把学过的东西忘记~~

1.单向链表

示例图 添加节点 删除节点

代码实现:

#include <iostream>

using namespace std;

//#define DATA int
typedef int DATA;//int的别名，为了便于管理
//定义一个结构体当做数据
/* typedef struct DATA
{
    int nNumb;
    char sName[20];
    float fMath;
}; */
//定义链表一个链节点
typedef struct SNode
{
    DATA data;//数据，可以是结构体和类等，4字节
    SNode *pNext;//指针，指向下一个节点，4字节
}SNode; 
SNode* g_pHead = NULL;//第一个链表是空链表
//从尾插入一个数据
void AddTail(DATA data)
{
    SNode* p = g_pHead;//防止改变头结点的指针
    //建立新的节点
    SNode* p1 = new SNode;
    p1->data = data;
    p1->pNext = NULL;
    if(!p)//如果一开始就是空链表
    {
        g_pHead = p1;
        return;
    }
    while(p->pNext)//找到最尾部的节点
    {
        p = p->pNext;
    }
    p->pNext = p1;
}
//从头插入一个数据
void AddHead(DATA data)
{
    SNode* p = new SNode;//申请一个堆空间，8字节
    p->data  = data;
    p->pNext = g_pHead;
    g_pHead  = p;//把新插入的节点当做头
}
//修改链表节点数据
void Modify(DATA data, DATA newData)
{
    SNode* p = g_pHead;
    SNode* p1 = new SNode;
    if (!p)
    {
        p1->data = newData;
        p1->pNext = NULL;
        g_pHead = p1;
        return;
    }
    while(p)
    {
        if (p->data==data)
        {
            p->data = newData;
        }
        p = p->pNext; 
    }
}
//查找某个数据
bool Find(DATA data)
{
    SNode* p = g_pHead;
    while(p)
    {
        if(p->data == data) return true;
        p = p->pNext;    
    }
    return false;
}
//删除某个节点
bool Delete(DATA data)
{
    SNode* p = g_pHead;//当前节点
    SNode* p1 = NULL;//下一个节点
    if(!p) return false;//空链表直接返回
    if(p->data == data )//删除第一个节点
    {
        g_pHead = p->pNext;
        delete p;
        return true;
    }        
    while(p)//删除中间和结尾节点
    {
        if(p->data == data)
        {
            p1->pNext = p->pNext;
            delete p;
            return true;
        }
        p1 = p;
        p = p->pNext;
    }
    return false;
}
//打印全部节点数据
void print()
{
    SNode* p = g_pHead;
    while(p)
    {
        cout<<p->data<<endl;
        p = p->pNext;
    }
}
//交换数据的排序
void sortByNum(bool reverse = true)
{
    SNode* p = g_pHead;
    SNode* m = NULL;
    while(p)
    {
        m = p->pNext;
        while(m)
        {
            if(p->data > m->data && reverse)
            {
                DATA midData;
                midData = p->data;
                p->data = m->data;
                m->data = midData;
            }
            else if(p->data < m->data && !reverse)
            {
                DATA midData;
                midData = p->data;
                p->data = m->data;
                m->data = midData;
            }
            m = m->pNext;
        }
        p=p->pNext;
    }
}
int main(int argc, char*argv[])
{
/*     AddHead(1);
    AddHead(2);
    AddHead(3); */
    AddTail(11);
    AddTail(2);
    AddTail(13);
    AddTail(10);
    AddTail(14);
    AddTail(1);
    //Modify(13,16);
    //Delete(13);
    print();
    sortByNum(false);
    print();
    return 0;
}

2.双向链表

示意图 添加节点 删除节点

代码实例:

#ifndef DOUBLE_CHAINS_H
#define DOUBLE_CHAINS_H
#include <iostream>
using namespace std;

//
template<typename T>
struct Node
{
public:
    Node() = default;
    Node(T value,Node<T>* preptr,Node<T>* nextptr):
        _value(value),pre_ptr(preptr),next_ptr(nextptr)
    {}
public:
    T _value;
    Node<T>* pre_ptr;
    Node<T>* next_ptr;
};

//
template<typename T>
class DoubleLink
{
public:
    DoubleLink();
public:
    typedef Node<T>* pointer;//
private:
    pointer phead;
    int count;
public:

    pointer insert(int index,T value);
    pointer insert_front(T value);
    pointer insert_last(T value);
    pointer getNode(int index);

    T get(int index);
    T get_front();
    T get_last();
    Node<T>* getHead();

    bool isEmpty();
    int size();

    Node<T>* del(int index);
    Node<T>* delete_front();
    Node<T>* delete_last();

    void print_head();
};
template<typename T>
DoubleLink<T>::DoubleLink()
{
    phead = new Node<T>(0,nullptr,nullptr);
    phead->next_ptr = phead;
    phead->pre_ptr  = phead;
    count = 0;
}
/*
获取指定下标的元素
*/
template <typename T>
Node<T>* DoubleLink<T>::getNode(int index)
{
    if(index>=count||index<0)
        return nullptr;
    if(index<=count/2)//如果在前半部分
    {
        pointer temp = phead;
        while(index)
        {
            temp = temp->next_ptr;
            index--;
        }
        return temp;
    }
    //在后半部分
    index = count-index-1;
    pointer temp = phead;
    while(index)
    {
        temp = temp->pre_ptr;
        index--;
    }
    return temp;
}
/*
*将节点位置插到index位置之前
*/
template<typename T>
Node<T>* DoubleLink<T>::insert(int index,T value)
{
    if (index==0)
    {
        return insert_front(value);
    }
    pointer temp = getNode(index);
    if (temp==nullptr)
        return nullptr;
    pointer newNode = new Node<T>(value,temp->pre_ptr,temp);
    temp->pre_ptr->next_ptr = newNode;
    temp->pre_ptr = newNode;
    return newNode;
}
/*
*将新节点插到第一个位置
*/
template<typename T>
Node<T>* DoubleLink<T>::insert_front(T value)
{
    pointer newNode = new Node<T>(value,phead,phead->next_ptr);
    phead->next_ptr->pre_ptr = newNode;
    phead->next_ptr = newNode;
    count++;
    return newNode;
}
/*
*将新节点插到链表尾部
*/
template <typename T>
Node<T>* DoubleLink<T>::insert_last(T value)
{
    Node<T> * newNode = new Node<int>(value, phead->pre_ptr, phead);
    phead->pre_ptr->next_ptr = newNode;
    phead->pre_ptr = newNode;
    count++;
    return newNode;
}
/*
 *
*/
template <typename T>
bool DoubleLink<T>::isEmpty()
{
    return count == 0;
}
/*
*获取第一个节点的值
*/
template<typename T>
T DoubleLink<T>::get_front()
{
    return phead->next_ptr->_value;
}
/*
*获取最后一个节点的值
*/
template <typename T>
T DoubleLink<T>::get_last()
{
    return phead->pre_ptr->_value;
}
/*
*获取指定位置节点的值
*/
template <typename T>
T DoubleLink<T>::get(int index)
{
    Node<T>  pnode = getNode(index);
    return pnode->_value;
}
/*
*删除链表第一个节点
*返回删除后链表第一个节点
*/
template<typename T>
Node<T>* DoubleLink<T>::delete_front()
{
    if(count==0)
        return nullptr;
    pointer temp = phead->next_ptr;
    temp->next_ptr->pre_ptr = temp->pre_ptr;
    delete phead->next_ptr;
    temp->pre_ptr->next_ptr = temp->next_ptr;
    count--;
    return temp;
}
/*
*删除链表的末尾节点
*返回删除后链表尾部元素
*/
template<typename T>
Node<T>* DoubleLink<T>::delete_last()
{
    if (count == 0)
    {
        return nullptr;
    }
    Node<T>*pnode = phead->pre_ptr;
    pnode->pre_ptr->next_ptr = phead;
    phead->pre_ptr = pnode->pre_ptr;
    delete pnode;
    count--;
    return phead->pre_ptr;
}
/*
*删除指定位置的元素
*
*/
template <typename T>
Node<T>* DoubleLink<T>::del(int index)
{
    if (index == 0)
        return delete_front();
    if (index == count - 1)
        return delete_last();
    if (index >= count)
        return nullptr;
    Node<T>* pnode = getNode(index);
    pnode->pre_ptr->next_ptr = pnode->next_ptr;
    pnode->next_ptr->pre_ptr = pnode->pre_ptr;

    Node<T>* ptemp = pnode->pre_ptr;
    delete pnode;
    count--;
    return ptemp;
}
/*
*print data from head
*/
template<typename T>
void DoubleLink<T>::print_head()
{
    pointer temp = phead->next_ptr;
    int k = count;
    while(k!=0)
    {
        cout<<temp->_value<<endl;
        temp = temp->next_ptr;
        k--;
    }
}
#endif // DOUBLE_CHAINS_H

测试:

#include <iostream>
using namespace std;

#include "double_chains.h"

int main()
{
    DoubleLink<int> dlink;
    //插入测试

    dlink.insert_front(10);
    dlink.insert_front(20);
    dlink.insert_front(30);
    dlink.delete_front();
    dlink.print_head();
    getchar();
    return 0;
}

注意C++的template只能在一个头文件,千万不要模块化编程一个在.h文件一个在.cpp文件!!!

参考资料:

文章主要参考,且图片均来自大神博文

我之前写的C++链表

吕鑫老师视频,很早之前看得