[线性表](2.1)链式基本操作

基本操作声明:

typedef struct LNode
{
    //结点类型
    ElemType data;
    struct LNode *next
}*Link,*Position;

typedef struct
{
    //链表类型
    Link head, tail;//分别指向线性链表中的头结点和最后一个结点
    int len;//指示线性链表中的数据元素的个数
}LinkList;


Status MakeNode(Link& p, ElemType e);
//分配由p指向的值为e的结点,并返回OK,若分配失败,则返回ERROR

void FreeNode(Link& p);
//释放p所指向的结点

Status InitList(LinkList& L);
//构建一个新链表L

Status DestroyList(LinkList& L)
//销毁线性表L,L不再存在

Status ClearList(LinkList& L);
//将线性表L重置为空表,并释放原链表的结点空间

Status InsFirst(Link h, Link s);
//已知h指向线性链表的头结点,将s所指结点插入在第一个结点之前

Status DelFirst(Link h, Link& q);
//已知h指向线性链表的头结点,删除链表中第一个结点并以q返回

Status Append(LinkList& L, Link s);
//将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点
//之后,并改变链表L的尾指针指向新的尾结点

Status Remove(LinkList& L, Link& q);
//删除线性链表L中的尾结点并以q返回,改变链表L的尾指针指向新的尾结点

Status InsBefore(LinkList& L, Link& p, Link s);
//已知p指向线性链表L中的第一个结点,将s所指结点插入在p所指结点之前
//并修改指针p指向新插入的结点

Status InsAfter(LinkList& L, Link& p, Link s);
//已知p指向线性链表L中的第一个结点,将s所指结点插入到o所指结点之后
//并修改指针p指向新插入的结点

Status SerCurElem(Link& p, ElemType e);
//已知p指向线性链表中的一个结点,用e更新p所指结点内的值

ElemType GetCurElem(Link p);
//已知p指向线性链表中的一个结点,返回p所指结点中的数据元素

Status ListEmpty(LinkList L);
//若线性链表L为空表,则返回TRUE,否则返回FALSE

int ListLength(LinkList L);
//返回线性表L中元素个数

Position GetHead(LinkList L);
//返回线性链表中头结点的个数

Position GetLast(LinkList L);
//返回线性链表L中最后一个结点的位置

Position PriorPos(LinkList L, Link p);
//已知p指向线性链表在L中的一个结点,返回p所指结点的直接前驱的位置
//若无前驱,则返回NULL

Position NextPos(LinkList L, Link p);
//已知p指向线性链表在L中的一个结点,返回p所指结点的直接后继的位置
//若无后继,则返回NULL

Status LocatePos(LinkList L, int i, Link& p);
//用p指示线性链表L中第i个结点的位置,并返回OK,i值不合法时返回ERROR

Position LocateElem(LinkList L, ElemType e, Status(*compare)(ElemType, ElemType);
//返回线性表链表L中第1个与e满足函数compare()判断关系的元素位置
//若不存在这样的元素,则返回NULL

Status ListTraverse(LinkList L, Status(*visit));
//依次对L的每个元素调用函数visit(),一旦visit()失败,则操作失败

以上算法利用C语言实现,仅供参考测试

#define OK 0;
#define ERROR -1
#define True 1
#define False -1


typedef int Status;
#include<stdio.h>
#include<stdlib.h>

typedef struct LNode
{
    //结点类型
    int data;
    struct LNode* next;
}*Link,*Position;

typedef struct
{
    //链表类型
    Link head, tail;//分别指向线性链表中的头结点和最后一个结点
    int len;//指示线性链表中的数据元素的个数
}LinkList;
Status b(int a);
Status a(int,int);

int main()
{
    /*主函数语块*/



}



Status MakeNode(Link p, int e)
//分配由p指向的值为e的结点,并返回OK,若分配失败,则返回ERROR
{
    p = (Link)malloc(sizeof(struct LNode));
    p->data = e;
}



void FreeNode(Link p)
//释放p所指向的结点
{
    free(p);
}
Status InitList(LinkList L)
//构建一个新链表L
{
    L.head = (Link)malloc(sizeof(struct LNode));
    L.head->next = NULL;
}

Status DestroyList(LinkList L)
{
    Link p = L.head, s = L.head;
    while (p->next != NULL)
    {
        s = p;
        p = p->next;
        free(s);
    }
    free(L.head);
}
//销毁线性表L,L不再存在

Status ClearList(LinkList L)
//将线性表L重置为空表,并释放原链表的结点空间
{
    Link p = L.head, s = L.head;
    while (p->next != NULL)
    {
        s = p;
        p = p->next;
        free(s);
    }
    L.head->next = NULL;
}

Status InsFirst(Link h, Link s)
//已知h指向线性链表的头结点,将s所指结点插入在第一个结点之前
{
    s->next = h->next;
    h->next = s;
}
Status DelFirst(Link h, Link q)
//已知h指向线性链表的头结点,删除链表中第一个结点并以q返回
{
    Link s;
    s = h->next;
    h->next = s->next;
      q = s;
    free(s);
}
Status Append(LinkList L, Link s)
//将指针s所指(彼此以指针相链)的一串结点链接在线性链表L的最后一个结点
//之后,并改变链表L的尾指针指向新的尾结点
{
    Link p = L.head;
    Link q = L.head;
    while (q->next != NULL)
    {
        q = q->next;
    }
    L.tail = q;
    /*指向尾结点*/
    q = s;
    while (q->next != NULL)
    {
        q = q->next;
    }
    L.tail->next = s;
    L.tail = q;
}
Status Remove(LinkList L, Link q)
//删除线性链表L中的尾结点并以q返回,改变链表L的尾指针指向新的尾结点
{
    Link h,s;
    h = L.head;
    s = L.head;

    while (s->next != NULL)
    {
        h = s;
        s = s->next;
    }

    h->next = NULL;
    q = s;
    free(s);
    L.tail = h;
}




Status InsBefore(LinkList L, Link p, Link s)
//已知p指向线性链表L中的第一个结点,将s所指结点插入在p所指结点之前
//并修改指针p指向新插入的结点
{
    p = L.head->next;
    s->next = p->next;
    L.head->next = s;
    p = s;
}



Status InsAfter(LinkList L, Link p, Link s)
//已知p指向线性链表L中的第一个结点,将s所指结点插入到p所指结点之后
//并修改指针p指向新插入的结点
{
    p = L.head->next;
    s->next = p->next->next;
    p->next = s;
    p = s;
}

Status SerCurElem(Link p, int e)
//已知p指向线性链表中的一个结点,用e更新p所指结点内的值
{
    p->data = e;
}

int GetCurElem(Link p)
//已知p指向线性链表中的一个结点,返回p所指结点中的数据元素
{
    return p->data;
}

Status ListEmpty(LinkList L)
//若线性链表L为空表,则返回TRUE,否则返回FALSE
{
    if (L.head->next == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }

}
int ListLength(LinkList L)
//返回线性表L中元素个数
{
    int count = 0;
    Link q;
    q = L.head;
    while (q->next != NULL)
    {
        count++;
        q = q->next;
    }
    return count;
}


Position GetHead(LinkList L)
//返回线性链表中头结点的位置
{
    return L.head;
}



Position GetLast(LinkList L)
//返回线性链表L中最后一个结点的位置
{
    Link s;
    s = L.head;
    while (s->next != NULL)
    {
        s = s->next;
    }
    L.tail = s;
    return s;
}

Position PriorPos(LinkList L, Link p)
//已知p指向线性链表在L中的一个结点,返回p所指结点的直接前驱的位置
//若无前驱,则返回NULL
{
    Link q;
    q = L.head;
    if (q == p)
    {
        return NULL;
    }
    while (q->next != NULL && q->next != p)
    {
        q = q->next;
    }
    return q;
}

Position NextPos(LinkList L, Link p)
//已知p指向线性链表在L中的一个结点,返回p所指结点的直接后继的位置
//若无后继,则返回NULL
{
    if (p->next == NULL)
    {
        return NULL;
    }
    else
    {
        return p->next;
    }

}

Status LocatePos(LinkList L, int i, Link p)
//用p指示线性链表L中第i个结点的位置,并返回OK,i值不合法时返回ERROR
{
    Link q;
    int count = 0;
    q = L.head;
    while (q->next != NULL)
    {
        count++;
        q = q->next;
        if (count == i)
        {
            return OK;
        }
    }
    return -1;
}


Position LocateElem(LinkList L, int e, Status (*compare)(int, int))
//返回线性表链表L中第1个与e满足函数compare()判断关系的元素位置
//若不存在这样的元素,则返回NULL
{
    Link q;
    q = L.head;
    int b;
    compare = a;
    while (q->next != NULL)
    {
        int a = q->data;
        if ((*compare)(a, e) == 0)
        {
            return q;
        }
    }
    return NULL;
}



Status ListTraverse(LinkList L, Status(*visit)(int))
//依次对L的每个元素调用函数visit(),一旦visit()失败,则操作失败
{
    Link q = L.head;
    visit = b;
    while (q != NULL)
    {
        if ((*visit)(q->data))
        {
            printf("成功\n");
        }
        else
        {
            printf("失败\n");
        }
        q = q->next;
    }
}



Status a(int a, int e)
{
    if (a == e)
    {
        return 0;
    }
    return -1;
}

Status b(int a)
{ 
    if(printf("%d ", a))
    {
        return 0;
    }
    else
    {
        return -1;
    }
}

本文链接:

https://nullcode.fun/11.html
1 + 4 =
快来做第一个评论的人吧~