单链表

WhYqZz2025-08-132025-11-05

单链表的概念

链式存储结构：用一组任意的存储单元存储线性表的数据元素（可以是连续的，也可以是不连续的）
结点（node）：存储映像

数据域：存储数据元素信息
指针域: 存储直接后继储存位置
存储的信息叫做指针或域

单链表的定义

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;//LNode强调是结点，LinkList强调是单链表

单链表的初始化

不带头结点的单链表

bool InitList(LinkList &L){
    L=NULL;
    return true;
}

带头结点的单链表

bool InitList(LinkList &L){
    L=(LNode*)malloc(sizeof(LNode));
    if(L=NULL){
        return false;
    }
    L->next=NULL;
    return true;
}

初始化

单链表的插入

按位序插入

不带头结点的单链表

bool ListInsert(LinkList &L,int i,int e){
    if(i<1)return false;
    LNode *p;
    p=L;
    if(i==1){
        LNode *s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;
        return true;
    }
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    LNode *s=(LNode *)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

带头结点的单链表

bool ListInsert(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;
    }
    LNode *s=(LNode*)malloc(sizeof(LNode));//为存放插入数据的数据域动态分配空间
    s->data=e;//将插入的数据e放入分配的空间中
    s->next=p->next;//指向后一个结点
    p->next=s;//将前一个结点指向所插入的结点
    return true;
}

指定结点的后插操作

bool InsertNextNode(LNode *p,int e){
    if(p==NULL)return false;
    LNode *s=(LNode*)malloc(sizeof(LNode));
    if(s==NULL)return false;
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

指定结点的前插操作

bool InsertpriorNode(LNode *p,int e){
    LNode *s=(LNode*)malloc(sizeof(LNode));
    if(s==NULL)return false;
    s->data=p->data;
    s->next=p->next;
    p->next=s;
    p->data=e;
    return true;
}

单链表的删除

按位序删除

带头结点的单链表

bool ListDelete(Linklist &L,int i,int &e){
    if(i<1)return false;
    int j=0;
    LNode *p;
    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=q->next;
    free(q);
    return true;

}

不带头结点的单链表

bool ListDelete(LinkList &L,int i,int &e){
    if(L==NULL)return false;
    if(i<1)return false;
    LNode *q=(LNode*)malloc(sizeof(LNode));
    if(i==1){
        q=L;
        e=q->data;
        L=L->next;
        free(q)；
        return true;
    }
    int j=1;
    LNode *p;
    p=L;
    while(p->next!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL)return false;
    if(p->next==NULL)return false;
    q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

删除指定结点

bool DeleteNode(LNode *p){
    if(p==NULL)return false;
    LNode *q=p->next;
    p->data=q->data;//当q指向NULL时不成立
    p->next=q->next；
    return true;
}

插入删除

单链表的查找

带头结点的单链表

按位查找

LNode *GetElem(LinkList L,int i){
    if(i<0)return NULL;
    int j=0;
    LNode *p;
    p=L;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

按值查找

LNode *LocateElem(LinkList L,int e){
    LNode *p=L->next;
    while(p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}

求单链表的长度

int Length(LinkList L){
    LNode *p=L;
    int len=0;
    while(p->next!=NULL){
        len++;
        p=p->next;
    }
    return len;
}

不带头结点的单链表

按位查找

LNode *GetElem(LinkList L,int i){
    if(i<1)return NULL;
    int j=1;
    LNode *p=L;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

按值查找

LNode *LocateElem(LinkList L,int e){
    LNode *p=L;
    while(p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}

求表的长度

int Length(LinkList L){
    LNode *p=L;
    int len=0;
    while(p!=NULL){
        p=p->next;
        len++;
    }
    return len;
}

单链表的建立

尾插法建立单链表

带头结点的单链表

LinkList List_TailInsert(LinkList &L){
    int x;
    L=(LNode*)malloc(sizeof(LNode));
    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;
}

不带头结点的单链表

LinkList List_TailInsrt(LinkList &L){
    int x;
    L=NULL;
    LNode *s,*r=NULL;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next=NULL;
        if(L==NULL){
            L=s;
        }
        else {
            r->next=s;
        }
        r=s;
    }
    return L;
}

头插建立单链表

带头结点的单链表

LinkList List_HeadInsert(LinkList &L){
    int x;
    L=(LNode*)malloc(sizeof(LNode));
    LNode *s;
    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;
}

不带头结点的单链表

LinkList List_HeadInert(LinkList &L){
    int x;
    L=NULL;
    LNode *s;
    scanf("%d",&x);
    while(x!=9999){
        s=(LNode*)malloc(sizeof(LNode));
        s->data=x;
        s->next=NULL;
        if(L==NULL){
            L=s;
        }
        else {
            s->next=L;
            L=s;
        }
        scanf("%d",&x);
    }
    return L;
}

单链表的逆置

带头结点的单链表

LinkList ReverseList(LinkList &L){
    if(L==NULL)return NULL;
    LNode *s,*p=L->next;
    L->next=NULL;
    while(p!=NULL){
        s=p;
        p=p->next;
        s->next=L->next;
        L->next=s;
    }
    return L;
}

不带头结点的单链表

LinkList ReverseList(LinkList &L)
{
    if(L==NULL)return NULL;
    LNode *newL=NULL;
    LNode *p=L;
    LNode *next;
    while(p!=NULL){
        next=p->next;
        if(newL==NULL){
            newL=p;
        }
        else {
            p->next=newL;
            newL=p;
        }
        p=next;
    }
    L=newL;
    return L;
}