1000_(2)单链表

单链表的实现

虽然链表与顺序表逻辑结构都为线性表。但不同于顺序表的是，链表不需要连续的存储空间，换句话说就是不受空间限制，用多少申请多少，这也是它的重要优点之一，减少空间的浪费

• 链表，包括后边的链栈..究其核心在于指针的掌握；请记住，实现具体操作前必须熟练使用指针，否则很难真正理解链式结构
• 单链表结构体定义

typedef struct LNode{ 
    ElementType data;
    struct LNode *next; // next 指针-》指向下一个结点 
}LNode, *LinkList; // struct LNode & struct LNode *

与顺序表不同，单链表重点在构建，增删改查等操作比较简单，所以重点掌握单链表的两种建表方法头插法、尾插法 ，PS:这两种方法是几乎所有题目的最内层的核心
tips:小技巧，可以边阅读代码，边在纸上模拟指针的操作，加深理解

• 头插法--》一句话总结：先挂尾部，在连头需深刻理解深层含义

/*
    头插法 倒序生成单链表 O(n)
*/
LinkList List_HeadInsert(LinkList &L){
    // 头节点 -- 构建空表 
    L = new LNode;
    L->next = NULL;
    LNode *s;
    ElementType x;
    cin >> x;
    while(x != 9999){// 输入9999结束 
        // 头插法 倒序生成单链表
        s = new LNode;
        s->data = x;
        s->next = L->next; // 先连尾 
        L->next = s; // 后断头 
        cin >> x;
    }
    return L;
    
}

• 尾插法--》一句话总结：连表尾，更新尾指针

/*
    尾插法 -- 顺序生成单链表
    尾指针保存尾结点 O(n) 
*/
LinkList List_TailInsert(LinkList &L){
    LNode *s, *r;
    L = new LNode;
    r = L; // 初始化为头节点
    ElementType x;
    cin >> x;
    while(x != 9999){
        s = new LNode;
        s->data = x;
        r->next = s;
        r = s; // 更新尾指针为当前插入结点 
        cin >> x;
    }
    r->next = NULL; // 尾后为空 
        
}

思考 上述两种方法实现的单链表 结点顺序有什么不同，如果尾插法最后的尾后不置空会如何？

• 增删改查定义

void PrintList(LinkList L); //顺序打印
LNode *GetElem(LinkList L, int i); // 下标查值
LNode *LocateElem(LinkList L, ElementType e); // 元素查值
bool List_NodeInsert(LinkList &L, int i, LNode *node); // 指定下标插入结点
bool List_NodeInsertBehind(LinkList &L, int i, LNode *node);
bool List_NodeDelete(LinkList &L, int i); // 删除结点

• 操作实现--》参考注释思考链表与顺序表的优缺点

/*
    指定序号 查找结点 返回值结点指针
    O(n) 
*/
LNode *GetElem(LinkList L, int i){
    if(i < 0)   return NULL;
    if(i == 0) return L;
    LNode *p = L->next; // 第一个数据结点指针
    int tags = 1; // 计数
    while(p && tags < i){
        p = p->next;
        tags++;
    }
    
    return p;
    
}

/*
    按值查找 返回结点指针
    O(n) 
*/
LNode *LocateElem(LinkList L, ElementType e){
    LNode *p = L->next; // 第一个数据结点
    while(p && p->data != e)
        p = p->next;
    return p;
    
}

/*
    指定位置后 插入结点操作  找到前驱结点 插入 
    O(n) 
*/
bool List_NodeInsert(LinkList &L, int i, LNode *node){
    LNode *p = GetElem(L, i-1);
    if(!p) return false; // 插入结点不合法
    node->next = p->next; // 先后在 续前 
    p->next = node;
    return true;
}

/*
    指定位置前插入结点 (后插变前插)
    思路：找到前驱结点 后插 交换前驱和当前插入结点的值
    O(n) 
*/ 
bool List_NodeInsertBehind(LinkList &L, int i, LNode *node){
    LNode *p = GetElem(L, i-1);
    if(!p)  return false;
    
    node->next = p->next;
    p->next = node;
    // 交换值 
    ElementType e;
    e = node->data;
    node->data = p->data;
    p->data = e;
    return true;
}

/*
    删除指定位置结点 找到前驱 移除 
*/
bool List_NodeDelete(LinkList &L, int i){
    LNode *node = GetElem(L, i-1);
    if(!node) return false;
    
    LNode *q = node->next;
    node->next = q->next;
    delete q;
    q = NULL; // c++ 特性 内存释放 指针不释放
    return true; 
    
}


/*
    遍历打印单链表 -- 含头节点 
*/
void PrintList(LinkList L){ 
    while(L->next){
        if(L->next->next)
            cout << L->next->data << "->";
        else
            cout << L->next->data << endl;
        L = L->next;
    }
}

• 如果尾指针的next域没有置空，当前链表就是一个无效的链表，没有终点的链表。