大话数据结构学习②线性表的单链表存储结构

#define OK 1
#define ERROR 0
typedef int Status;

typedef struct
{
    ElemType data;
    struct Node *next;
} Node;

typedef struct Node *LinkList; // 定义单链表

// 获取单链表的长度
Status GetElem(LinkList L, int i, ElemType *e)
{
    in j;              // 用于记录当前位置
    LinkList p;        // 用于指向当前位置
    p = L->next;       // p指向第一个结点
    j = 1;             // j初始化为1
    while (p && j < i) // 当p不为空且j小于i时
    {
        p = p->next; // p后移一个结点
        j++;         // j加1
    }
    if (!p || j > i)  // 当p为空或者j大于i时
        return ERROR; // 返回错误
    *e = p->data;     // 将p的值赋给e
    return OK;        // 返回OK
}

// 在单链表中插入元素
Status ListInsert(LinkList *L, int i, ELemType e)
{
    int j;             // 用于记录当前位置
    LinkList p, s;     // p指向当前结点,s指向新结点
    p = *L;            // p指向第一个结点
    j = 1;             // j初始化为1
    while (p && j < i) // 当p不为空且j小于i时
    {
        p = p->next; // p后移一个结点
        j++;         // j加1
    }
    if (!p || j > i)                    // 当p为空或者j大于i时
        return ERROR;                   // 返回错误
    s = (LinkList)malloc(sizeof(Node)); // 分配空间
    s->data = e;                        // 将e赋给新结点
    s->next = p->next;                  // 将新结点插入到p的后面
    p->next = s;                        // 将p的后继指向新结点
    return OK;                          // 返回OK
}

// 删除单链表中的第i个元素
Status ListDelete(LinkList *L, int i, ElemType *e)
{
    int j;                   // 用于记录当前位置
    LinkList p, q;           // p指向当前结点,s指向待删除结点
    p = *L;                  // p指向第一个结点
    j = 1;                   // j初始化为1
    while (p->next && j < i) //遍历寻找第i个元素
    {
        p = p->next; // p后移一个结点
        j++;         // j加1
    }
    if (!(p->next) || j > i) // 当p为空或者j大于i时
        return ERROR;        // 返回错误
    q = p->next;             // q指向待删除结点
    p->next = q->next;       // 将q的后继指向p的后继
    *e = q->data;            // 将q的值赋给e
    free(q);                 // 释放q,free函数的作用是释放内存
    return OK;               // 返回OK
}

/*
    插入和删除算法都是由2部分组成,第一部分就是查找第i个元素,第二部分就是插入或删除元素。
    对于插入或删除数据越频繁的操作,单链表比起顺序存储来说,单链表的优势是很明显的。

*/

单链表与结构与顺序结构的优缺点:

  ①存储分配的方式不同,顺序存储结构用一段连续存储单元一次存储线性表的数据元素,单链表则采用链式存储结构,用一组任意的存储单元存放线性表的元素。

  ②时间性能:查找:顺序存储结构:O(1),单链表O(n),

                      插入和删除:顺序存储结构需要平均移动表长一半的元素,时间复杂度为O(n);单链表在找出位置的指针后,插入和删除时间复杂度仅为O(1)

  ③空间性能:顺序存储结构需要预分配存储空间,分大了就浪费,分小了,就容易发生溢出;单链表不需要分配空间,只要有就分配,元素个数也不收限制。

上一篇:Android项目实战:浅谈ListView悬浮头部展现效果


下一篇:用智慧让商场的购物体验大放异彩