线性表的链式储存(链表)

线性表的链式储存(链表)

typedef struct LNode *List;
struct LNode
{
    ElementType Data;
    List Next;
};
struct LNode L;
List PTRL;

求表长

int Length(List PtrL)
{
    List p=PtrL;    /* p指向的是第一个结点*/
    int j=0;
    while(p)
    {
        p=p->Next;
        j++;        /* 当前p指向的是第j个结点*/
    }
    return j;
}

//时间性能为O(n)

查找(按序号查找:FindKth)

List FindKth(int K,List PtrL)
{
    List p=Ptrl;
    int i=1;
    while (p!=NULL&&i<K)
    {
        p=p->Next;
        i++;
    }
    if(i==K)return p;    /* 找到第K个,返回指针*/
    else return NULL;    /*否则返回空*/
}

查找(按值查找:Find)

List Find(ElementType X,List PtrL)
{
    List p=PtrL;
    while(p!=NULL&&p->Date!=X)
        p=p->Next;
    return p;
}

插入(在第i-1(1<=i<=n+1)个结点后插入一个值为X的新结点)

List Insert(ElementType X,int i,List PrtL)
{
    List p,s;
    if(i==1)            /* 新结点插入在表头*/
    {
        s=(List)malloc(sizeof(struct LNode));    /* 申请、填装结点*/
        s->Date=X;
        s->Next=PtrL;
        return s;                                /* 返回新表头指针*/
    }
    p=FindKth(i-1,PtrL)                            /* 查找第i-1个结点*/
    if(p==NULL)                                    /* 第i-1个不存在,不能插入*/
    {
        printf("参数i错");
        return NULL;
    }
    else
    {
        s=(List)malloc(sizeof(struct LNode));    /* 申请、填装结点*/
        s->Date=X;
        s->Next=p->Next;                        /* 新结点插入在第i-1个结点的后面*/
        p->Next=s;
        return PtrL;
    }
}

删除(删除链表的第i(1<=i<=n)个位置上的结点)

List Delete(int i,List PtrL)
{
    List p,s;
    if(i==1)        /* 若要删除的是表的第一个结点*/
    {
        s=PtrL;        /* s指向第一个结点*/
        if(PtrL!=NULL)PtrL=PtrL->Next;    /* 从链表中删除*/
        else return NULL;
        free(s);    /* 释放被删除结点*/
        return PtrL;
    }
    p=FindKth(i-1,PtrL);    /* 查找第i-1个结点 */
    if(p==NULL)
    {
        printf("第%d个结点不存在",i-1);
        return NULL;
    }
    else if(p->Next==NULL)
    {
        printf("第%d个结点不存在",i);
        return NULL;
    }
    else
    {
        s=p->Next;            /* s指向第i个结点*/
        p->Next-s->Next;    /* 从链表中删除*/
        free(s);            /* 释放被删除结点*/
        return PtrL;
    }
}

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 zzzqqqyyy2002@163.com

×

喜欢就点赞,疼爱就打赏