JZTXT

数据结构

发布时间 2023-09-19 20:43:15作者: LiHaoyu

线性表

顺序表

链表

单链表

  1. 初始化
typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode, *LinkList;

bool InitLinkList(LinkList &L) //初始化
{
    L = new LNode;
    if (L == NULL) //内存不足，分配失败
        return false;
    L->next = NULL;
    return true;
}
  1. 头插法
LinkList CreateList_Head(LinkList &L, int n) //头插法
{
    L = new LNode;
    L->next = NULL;

    for (int i = 0; i < n; i ++ )
    {
        LNode *p = new LNode;
        cin >> p->data;
        p->next = L->next;
        L->next = p;
    }

    return L;
}
  1. 尾插法
LinkList CreateList_Tail(LinkList &L, int n) //尾插法
{
    L = new LNode;
    L->next = NULL;
    LNode *tail = L;
    for (int i = 0; i < n; i ++ )
    {
        LNode *p = new LNode;
        cin >> p->data;
        tail->next = p;
        p->next = NULL;
        tail = p;
    }

    tail->next = NULL;

    return L;
}
  1. 按位查找
LNode* GetElem(LinkList L, int i) //按位查找
{
    if (i < 0)
        return NULL;
    LNode *p = L;
    int j = 0;
    while (p && j < i)
    {
        p = p->next;
        j ++ ;
    }

    return p;
}
  1. 按值查找
LNode* LocateElem(LinkList &L, int e) //按值查找
{
    LNode *p = L->next; //首元节点
    while (p && p->data != e)
    {
        p = p->next;
    }

    return p; //查找成功返回值为e的节点地址p，查找失败p为NULL
}
  1. 按位插入
bool ListInsert(LinkList L, int i, int e) //按位插入
{
    if (i < 1)
        return false;
    LNode *p;
    if (!(p = GetElem(L, i - 1)))
        return false;
    
    LNode *s = new LNode;
    s->data = e;
    
    s->next = p->next;
    p->next = s;

    return true;
}
  1. 按位删除
bool ListDelete(LinkList L, int i) //按位删除
{
    if (i < 1)
        return false;
    LNode *p;
    if (!(p = GetElem(L, i - 1)))
        return false;
    if (p -> next == NULL) //第i个节点为空
        return false;

    LNode *q = p->next;
    p->next = q->next;
    delete q;
    return true;
}
  1. 遍历
void Print(LinkList L)
{
    LNode *p = L->next;
    while (p != NULL)
    {
        if (p->next != NULL)
            cout << p->data << " ";
        else
            cout << p->data;
        p = p->next;
    }
}

双链表

  1. 初始化
typedef struct DuLNode
{
    int data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode, *DuLinkList;

bool InitDuLinkList(DuLinkList &L) //初始化
{
    L = new DuLNode; //分配一个头节点
    if (L == NULL) //分配失败
        return false;
    L->prior = NULL; //头节点的前指针永远指向NULL
    L->next = NULL; //因为是空表，头节点之后暂时还没有节点

    return true;
}
  1. 头插法
DuLinkList CreateList_Head(DuLinkList &L, int n) //头插法
{
    L = new DuLNode;
    L->next = NULL;
    L->prior = NULL;

    for (int i = 0; i < n; i ++ )
    {
        DuLNode *p = new DuLNode;
        cin >> p->data;
        if (L->next == NULL) //插入第一个节点与插入其他节点的方法不一样
        {
            L->next = p;
            p->prior = L;
            p->next = NULL;
        }
        else
        {
            p->next = L->next;
            L->next->prior = p;
            L->next = p;
            p->prior = L;
        }
    }
    return L;
}
  1. 尾插法
DuLinkList CreateList_Tail(DuLinkList &L, int n) //尾插法
{
    L = new DuLNode;
    L->next = NULL;
    L->prior = NULL;
    DuLNode *tail = L;
    for (int i = 0; i < n; i ++ )
    {
        DuLNode *p = new DuLNode;
        cin >> p->data;
        p->prior = tail;
        tail->next = p;
        tail = p;
    }

    tail->next = NULL;

    return L;
}
  1. 按位查找
DuLNode* GetElem(DuLinkList L, int i) //按位查找
{
    if (i < 0) return NULL;
    DuLNode *p = L;
    int j = 0;
    while (p && j < i)
    {
        p = p->next;
        j ++ ;
    }

    return p;
}
  1. 按值查找
DuLNode* LocateElem(DuLinkList L, int e) //按值查找
{
    DuLNode *p = L->next;
    while (p && p->data != e)
    {
        p = p->next;
    }
    return p;
}
  1. 按位插入
bool ListInsert(DuLinkList &L, int i, int e) //按位插入
{
    if (i < 1)
        return false;
    DuLNode *p;
    if (!(p = GetElem(L, i))) //第i个元素不存在
        return false;
    DuLNode *s = new DuLNode;
    s->data = e;
    s->prior = p->prior;
    p->prior->next = s;
    s->next = p;
    p->prior = s;

    return true;
    
}
  1. 按位删除
bool ListDelete(DuLinkList &L, int i) //按位删除
{
    if (i < 1)
        return false;
    DuLNode *p;
    if (!(p = GetElem(L, i))) //第i个元素不存在
        return false;

    p->prior->next = p->next;
    if (p->next != NULL)
        p->next->prior = p->prior;
    
    delete p;

    return true;
}
  1. 遍历
void Print(DuLinkList L)
{
    DuLNode *p = L->next;
    while (p != NULL)
    {
        if (p->next != NULL)
            cout << p->data << " ";
        else
            cout << p->data;
        p = p->next;
    }
}

循环链表