算法逻辑

链表由节点及连线组成,一个节点分配一个数据,将新旧节点连接成为一个链表。节点中有数据和下个节点的地址(指针)。

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

操作数据

头插法(有头节点)

  • 新建节点,将数据放入后将头节点的next指针指向的地址给新节点的next指针(将准备断开的线备份接一条给新节点牵着)。

  • 将头节点的next指针指向新节点(断开线重新连)

void HeadInList(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));      //创建头节点
    L->next=NULL;       //设置最后的一个元素的next为NULL
    int x;
    scanf("%d",&x);
    LinkList n;     //声明用作创建新节点的结构体变量
    while(x!=9999){
        n=(LinkList)malloc(sizeof(LNode));      //创建新节点
        n->data=x;
        n->next=L->next;        //新节点的next连接到插入位置的后继上
        L->next=n;      //L的next连接到新节点上
        scanf("%d",&x);
    }
}

运行结果:

尾插法

  • 声明一个新指针用作标记当前位置

  • 新节点获取数据

  • 当前位置的节点next指针指向新节点

  • 位标指针移动到新节点(位标指针指向最后一个节点)

  • 新节点的next指向NULL(最后一个节点)

void EndInList(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));      //创建头节点
    int x;
    scanf("%d",&x);
    LinkList n,p=L;     //n为新节点,p为当前节点位置
    while(x!=9999){
        n=(LinkList)malloc(sizeof(LNode));
        n->data=x;
        p->next=n;      //新节点插与入位置的前驱连接
        p=n;
        scanf("%d",&x);
    }
    n->next=NULL;
}

运行结果:

位置查找

声明一个节点类型的结构体指针储存查找返回的节点,通过遍历进行位置的查找。

LinkList GetItem(LinkList L,int Spos){
    int i=0;
    while(L&&i<Spos){
        L=L->next;
        i++;
    }
    return L;
}

按值查找

通过遍历进行对比,将相同数值返回

LinkList GetNum(LinkList L,int value){
    while (L){
        if(L->data==value){
            return L;
        }
        L=L->next;
    }
}

第i个位置插入

使用循环遍历且进行计数,到目标位置后进行插入操作

bool ListInsert(LinkList L,int pos,int value){
    LinkList p=GetItem(L,pos-1);
    LinkList q;
    q=(LinkList)malloc(sizeof(LNode));
    q->data=value;
    q->next=p->next;
    p->next=q;
    return true;
}

删除

通过将删除位置的前驱和后继连接,后将要删除的节点free

bool ListDelete(LinkList &L,int pos){
    LinkList p = GetItem(L,pos-1);      //获取待删除节点位置的前驱地址
    if(!p){
        return false;
    }
    LinkList q = p->next;       //获取待删除节点的地址
    if(!q){                     //检查q是否存在
        return false;
    }
    p->next=q->next;        //将待删除节点的前驱和后继相连(孤立节点)
    free(q);        //删除节点
}