当前位置：首页 > article >正文

【数据结构】线性表

article 2024/11/20 19:03:37

静态分配顺序表

// 静态分配顺序表
// 1. 顺序存储类型
#define MaxSize 50
typedef struct
{
    // Elemtype data[MaxSize];
    int data[MaxSize];
    int length;
} SqList;

// 2. 初始化
void InitList(SqList &L)
{
    L.length = 0;
}

// 3. 插入元素
// bool ListINert(SqList &L, int i, Elemtype e)
bool ListInsert(SqList &L, int i, int e)
{
    if (i < 1 || i > L.length + 1)
        return false;
    if (L.length >= MaxSize)
        return false;
    for (int j = L.length; j >= i; j--)
    {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

// 4. 删除
// bool ListDelete(SqList &L, int i ,Elemtype &e)
bool ListDelete(SqList &L, int i, int &e)
{
    if (i < 1 || i > L.length)
        return false;
    e = L.data[i - 1];
    for (int j = i; j <= L.length; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

// 5. 按位查找
int GetElem(SqList L, int i)
{
    return L.data[i - 1];
}

// 5. 按值查找
// int LocateElem(SqList &L, Elemtype &e)
int LocateElem(SqList &L, int &e)
{
    for (int i = 0; i < L.length; i++)
    {
        if (L.data[i] == e)
            return i + 1;
    }
    return 0;
}

动态分配顺序表

// 动态分配顺序表
// 1. 顺序存储类型

#define InitSize 50
typedef struct
{
    // Elemtype *data;
    int *data;
    int MaxSize, length;
} SqList;

// 2. 初始化
void InitList(SqList &L)
{
    // L.data = (Elemtype *)malloc(sizeof(Elemtype) * InitSize);
    L.data = (int *)malloc(sizeof(int) * InitSize);
    L.length = 0;
    L.MaxSize = InitSize;
}

// 3. 插入元素
// bool ListINert(SqList &L, int i, Elemtype e)
bool ListInsert(SqList &L, int i, int e)
{
    if (i < 1 || i > L.length + 1)
        return false;
    if (L.length >= MaxSize)
        return false;
    for (int j = L.length; j >= i; j--)
    {
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;
    L.length++;
    return true;
}

// 4. 删除
// bool ListDelete(SqList &L, int i ,Elemtype &e)
bool ListDelete(SqList &L, int i, int &e)
{
    if (i < 1 || i > L.length)
        return false;
    e = L.data[i - 1];
    for (int j = i; j <= L.length; j++)
    {
        L.data[j - 1] = L.data[j];
    }
    L.length--;
    return true;
}

// 5. 按位查找
int GetElem(SqList L, int i)
{
    return L.data[i - 1];
}

// 5. 按值查找
// int LocateElem(SqList &L, Elemtype &e)
int LocateElem(SqList &L, int &e)
{
    for (int i = 0; i < L.length; i++)
    {
        if (L.data[i] == e)
            return i + 1;
    }
    return 0;
}

带头结点的单链表

typedef struct LNode
{
    // ElemType data;
    int data;
    struct LNode *next;
} LNode, *LinkList;

// 1.单链表的初始化
// （有头结点）
bool InitList(LinkList &L)
{
    L = (LNode *)malloc(sizeof(LNode));
    if (L == NULL)
        return false;
    L->next = NULL;
    return true;
}
// 没有头结点
bool InitList(LinkList &L)
{
    L = NULL;
    return true;
}

// 2.尾插法建立单链表
LinkList List_TailInsert(LinkList &L)
{
    int x;
    // 创建头结点
    L = (LinkList)malloc(sizeof(LNode));
    // r为尾结点，s为每次创建的新结点
    LNode *s, *r = L;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    // 尾结点置为空
    r->next = NULL;
    return L;
}

// 3.头插法创建单链表
LinkList List_HeadInsert(LinkList &L)
{
    int x;
    LNode *s;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d", &x);
    while (x != 9999)
    {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

// 4.插入节点
// p = GetElem(L, i - 1);
// s->next = p->next;
// p->next = s;

// 5.在第i个位置后插入节点操作（带头结点）
// bool ListInsert(LinkList &L, int i, ElemType e)
bool ListInsert(LinkList &L, int i, int e)
{
    if (i < 1)
        return false;
    // p指向当前扫描到的节点
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 6.在第i个位置后插入节点操作（不带头结点)
bool ListInsert(LinkList &L, int i, int e)
{
    if (i < 1)
        return false;
    if (i == 1)
    {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        // 头指针指向新节点
        L = s;
        return true;
    }
    LNode *p;
    p = L;
    // 注意j的取值
    int j = 1;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

// 7.在第i个位置之前插入节点操作
bool InsertPriorNode(LNode *p, int e)
{
    if (p == NULL)
        return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL)
        return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

// 8.在第i个位置删除节点操作（带头结点）
bool ListDelete(LinkList &L, int i, int e)
{
    if (i < 1)
        return false;
    LNode *p;
    int j = 0;
    p = L;
    while (p != NULL && j < i - 1)
    {
        p = p->next;
        j++;
    }
    if (p == NULL)
        return false;
    if (p->next == NULL)
        return false;
    LNode *q = p->next;
    e = q->data;
    p->next = p->next->next;
    free(q);
    return true;
}

// 9.删除指定节点
bool DeleteNode(LNode *p)
{
    if (p == NULL)
        return false;
    LNode *q = p->next;
    p->next = q->next;
    free(q);
    return true;
}

// 10.按序号查找节点值
LNode *GetElem(LinkList L, int i)
{
    int j = 1;
    LNode *p = L->next;
    // 返回头结点
    if (i == 0)
        return L;
    if (i < 1)
        return NULL;
    while (p != NULL && j < i)
    {
        p = p->next;
        j++;
    }
    return p;
}
// 另外一个版本
// LNode *GetElem(LinkList L, int i)
// {
//     if (i < 1)
//         return NULL;
//     int j = 0;
//     LNode *p = L;
//     while (p != NULL && j < i)
//     {
//         p = p->next;
//         j++;
//     }
//     return p;
// }

// 11.按值查找表节点
LNode *LocateElem(LinkList L, int e)
{
    LNode *p = L;
    if (p == NULL)
        return false;
    while (p != NULL && p->date != e)
    {
        p = p->next;
    }
    return p;
}

// 12.求表长（不含头结点）
int Length(LinkList L)
{
    int len = 0;
    LNode *p = L;
    while (p->next != NULL)
    {
        p = p->next;
        len++;
    }
    return len;
}