[数据结构与算法]链表的常见操作

C语言实现链表操作

• 定义头文件Common.h

  #include<stdio.h>
  #include<stdlib.h>
  #include<string.h>
  #define TRUE 1
  #define FALSE 0
  #define OK 1
  #define ERROR 0
  #define OVERFLOW -2
  #define MAXSIZE 100
  typedef int Status;
  typedef int ElemType;//自定义数据类型
  

• LinkList.cpp文件

#include "Common.h"

LNode* MakeNode_L(ElemType e) { // 构造数据域为e的单链表结点
    LNode* p;
    p = (LNode*)malloc(sizeof(struct LNode)); // 分配结点空间
    if (NULL == p) return NULL;
    p->data = e;  p->next = NULL;
    return p;
}

Status InitList_L(LinkList& L) { // 初始化一个只含头结点的空单链表L
    L = (LNode*)malloc(sizeof(struct LNode));// 生成新结点
    if (NULL == L)  return OVERFLOW;
    L->next = NULL;
    return OK;
}

Status InsertAfter_L(LNode* p, LNode* q) {  // 在p结点之后插入q结点
    if (NULL == p || NULL == q) return ERROR;  // 参数不合理
    q->next = p->next;    // 修改q结点的指针域  
    p->next = q;   // 修改p结点的指针域
    return OK;
}

Status CreatList_L(LinkList& L, int n, ElemType* A) { // 建立一个长度为n的单链表，数组A[]提供n个元素值，尾插入法
    LNode* p, * q;
    int i;
    if (OVERFLOW == InitList_L(L)) return OVERFLOW;
    p = L;
    for (i = 0; i < n; i++) { // 依次在表尾插入n个结点
        q = MakeNode_L(A[i]);
        InsertAfter_L(p, q);
        p = q;  // 令p指向新插入结点
    }
    return OK;
}

Status CreatList_LH(LinkList& L, int n, ElemType* A) {//头插入
    LNode* p, * q;
    int i;
    if (OVERFLOW == InitList_L(L)) return OVERFLOW;
    p = L;
    for (i = n-1; i >= 0; i--) { // 依次在表尾插入n个结点
        q = MakeNode_L(A[i]);
        InsertAfter_L(p, q);
    }
    return OK;
}

Status CreatList_LN(LinkList& L, int n, ElemType* A) {//创建不带头链表
    int i = 0;
    LNode *p = NULL, *q = NULL;

    L = NULL;
    for (i = n - 1; i >= 0; i--) {
        q = MakeNode_L(A[i]);
        q->next = L;
        L = q;
    }
    return OK;
}

Status DeleteElem_LH(LinkList& L, int i, ElemType& e) {//带头结点删除
    LNode *p = L, *q = NULL;
    int j = 1;
    while ( p->next && j < i)
    {
        p = p->next;
        ++j;
    }
    if (p->next == NULL || j > i) return ERROR;
    q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return OK;
}

Status DeleteElem_LN(LinkList& L, int i, ElemType& e) { //无头结点删除
    LNode* p = NULL, * q = NULL;
    p = L;
    int n = 1;

    if (i <= 0) {
        return ERROR;
    }

    if (i != 1) {

        while (p != NULL && p->next != NULL) {
            if (n == i - 1) {
                q = p;
                e = p->next->data;
                break;
            }
            n++;
            p = p->next;
        }
        //前驱节点q 
        p = q->next; //要删除的节点p

        q->next = p->next;
        free(p);
    }
    else if (i == 1) {
        q = L;
        L = L->next;
        e = q->data;
        free(q);
    }

    return OK;
}