数据结构基础:双链表结构、实现

简介: 数据结构基础:双链表结构、实现

继续和颦颦学C语言呀.......>


双链表的结构

这里的head 为头节点,是‘哨兵位’,实际不存储任何有效的数据

它的存在是为了遍历环链表避免死循环

双链表的实现

typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next; //指针保存下⼀个节点的地址
struct ListNode* prev; //指针保存前⼀个节点的地址
LTDataType data;
}LTNode;

头插

DLinkList HeadInsert(DLinkList &L)
{
    InitList(L); 
    int x;
    cin>>x;
    while(x!=9999)
    {
        LTNode *s = (LTNode *)malloc(sizeof(LTNode));
        s->data = x;
        if(L->next == NULL)
        {
            s->next = NULL;
            s->pre = L;
            L->next = s;
        }
        else
        {
            s->next = L->next;
            L->next->pre = s;
            s->pe = L;
            L->next = s;
        }
        cin>>x;
    }
    return L;
}

尾插

DLinkList TailInsert(DLinkList &L)
{
    InitList(L);
    LTNode *s,*r=L;
    int x;
    cin>>x;
    while(x!=9999)
    {
        s = (LTNode *)malloc(sizeof(LTNode));
        s->data = x;
        s->next = NULL;
        s->pre = r;
        r->next = s;
        r = s;
        cin>>x;
    }
    return L;
}

遍历双链表

void PrintList(DLinkList L)
{
    DNode *p = L->next;
    while(p){
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

查找

void Delete(DLinkList &L, int i)
{
    if(i<1 || i>Length(L))
    {
        cout<<"delete failed: index is wrong."<<endl;
        return;
    }
    LDNode *p = GetElem(L,i-1);
    LDNode *q = p->next;
    p->next = q->next; 
    q->next->pre = p; 
    free(q);
}
 


代码需要大家自己多打打才会印象深刻哦加油


相关文章
|
10天前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
13 0
|
1天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
2天前
|
存储
数据结构——带头双向循环链表
数据结构——带头双向循环链表
|
5天前
|
存储
初阶数据结构 带头双链表
初阶数据结构 带头双链表
7 0
|
5天前
数据结构初阶 链表的补充
数据结构初阶 链表的补充
7 0
|
5天前
|
存储
数据结构初阶 链表详解
数据结构初阶 链表详解
7 0
|
10天前
|
存储
数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)
数据结构学习记录——如何建立图(邻接矩阵、邻接表-图节点的结构、创建并初始化、插入变、完整图的建立)
12 0
|
10天前
|
存储
数据结构学习记录——堆的插入(堆的结构类型定义、最大堆的创建、堆的插入:堆的插入的三种情况、哨兵元素)
数据结构学习记录——堆的插入(堆的结构类型定义、最大堆的创建、堆的插入:堆的插入的三种情况、哨兵元素)
10 2
|
10天前
|
存储 算法
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
9 0
数据结构和算法学习记录——二叉树的存储结构&二叉树的递归遍历(顺序存储结构、链表存储结构、先序中序后序递归遍历)
|
10天前
|
算法
数据结构和算法学习记录——特殊线性表之栈(上)-栈的概念、栈的结构、链式栈数组栈、栈的结构体定义、栈的基本接口函数、栈顶初始化函数
数据结构和算法学习记录——特殊线性表之栈(上)-栈的概念、栈的结构、链式栈数组栈、栈的结构体定义、栈的基本接口函数、栈顶初始化函数
4 0