数据结构

数据结构笔记——线性表的链式表示（单链表）

基本概念

  • 其实不妨说这就是链表。其存储单元无须连续。

  • 链表的组成单位为节点（Node）

  • 首个节点称为头节点，最后一个节点称为尾节点。

  • 我们一般直接使用Linklist L 来定义链表。使用LNode *p来定义一个节点指针

typedef struct LNode 
{
    ElemType data; //数据
    struct LNode *next; //指向下一个节点
}LNode,*LinkList;

单链表基本操作的实现

说在前面

  • 由于本人问题，仍然无法快速分清代码中“*p”等等，让人眼花缭乱。出于应试目的，所有的节点的创建统统使用LinkList p这样的样式来创建，避免了指针的来回转换。

  • 以下的代码，均可以通过画图的方式来快速理解。但不便于用文字展示，所以请读者自行画图，敬请见谅！

单链表的初始化

Status initList(LinkList L){
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    return OK;
}

单链表的销毁

Status DestroyList(LinkList L){
    LinkList p;
    while((L)!=NULL){
        p=L;
        (L)=(L)->next;
        free(p);
    }
    return OK;
}

单链表的清空

Status ClearList(LinkList L){
    LinkList p,q;
    p=L->next;
    while(p==NULL){
        q=p->next;
        free(p);
        p=q;
    }
    L->next=NULL;
    return OK;
}

单链表的表长

int ListLenth(LinkList L){
    LinkList p=L;
    int count=0;
    while(p!=NULL){
        p=p->next;
        count++;
    }
    return count;
}

取单链表的第i个元素

Status GetElem(LinkList L,int i,ElemType *e){
    LinkList p=L->next;
    int j=1;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    if(p==NULL||j>i){
        return ERROR;
    }
    e=p->data;
    return OK;
}

单链表按值查找

查找时要从头开始所以复杂度 O(n)

//返回数据的位置
LinkList LocalElem(LinkList L,ElemType e){
    LinkList p=L->next;
    while(p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
}


//返回数据的位置序号
int LocalElem2(LinkList L,ElemType e){
    LinkList p=L->next;
    int j=1;
    while(p->data!=e&&p!=NULL){
        p=p->next;
        j++;
    }
    if(p==NULL){
        return 0;
    }else {
        return j;
    }
}

在第i个节点插入e

需要从头查找，复杂度O(n)

Status ListInsert(LinkList L,int i,ElemType e){
    LinkList p=L;
    int j=0;
    while (p!=NULL&&j<i-1)//寻找第i-1个节点，使得要插入节点与其链接
    {
        p=p->next;
        j++;
    }
    if(p==NULL||j>i-1){ //i不合法
        return ERROR;
    }
    LinkList s=(LinkList)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
    
}

删除第i个节点

需要从头查找 复杂度O（n）

Status ListDelete(LinkList L,int i,ElemType *e){
    LinkList p=L;
    int j=0;
    while(p->next!=NULL&&j<i-1){ //到达要删除节点的前一个
        p=p->next;
        j++;
    }
    if(p->next==NULL||j>i-1){
        return ERROR;
    }
    LinkList q=p->next;
    p->next=p->next->next;
    e=q->data;
    free(q);
    return OK;
}

头插法创建单链表

复杂度为O(n)

void CreateList_H(LinkList L,int n){
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    for(int i=0;i<n;i++){
        LinkList p=(LinkList)malloc(sizeof(LNode));
        scanf(&p->data);
        p->next=L->next; //把头节点后面的一串接到p的next上
        L->next=p; //连接到头节点

    }

}

尾插法创建单链表

复杂度为O(n)

void CreateList_R(LinkList L,int n){
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    LinkList r=L;
    for(int i=0;i<n;i++){
        LinkList p=(LinkList)malloc(sizeof(LNode));
        p->next=NULL;
        scanf(&p->data);
        r->next=p; //插入到表尾
        r=p; //更新最新的表尾
    }
}

Comment