单链表

声明

1
2
3
4
typedef struct LNode {
    ElemType data; //结点的数据域
    struct LNode *next; //结点的指针域
} LNode, * LinkList; //LinkList为指向结构体LNode的指针类型

初始化

1
2
3
4
5
6
Status InitList_L(LinkList &L)
{
    L = new LNode;
    L->next = NULL;
    return OK;
}

取值

1
2
3
4
5
6
7
8
9
10
11
12
Status GetElem_L(LinkList L, int i, ElemType &e)
{
    LinkList p = L->next;int j=1;
    while(p&&j<i)
    {
        p = p->next;
        ++j;
    }
    if(!p || j>i)    return ERROR;
    e = p->data;
    return OK;
}

查找

1
2
3
4
5
6
7
LNode * LocateElem_L(LinkList L, int e)
{
    LinkList p = L->next;
    while(p&&p->data!=e)
        p = p->next;
    return p;
}

求表长度

1
2
3
4
5
6
7
8
9
10
11
int  ListLength_L(LinkList L)
{
    LinkList p = L->next;
    int l=0;
    while(p)
    {
        p = p->next;
        l++;
    }
    return l;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status ListInsert_L(LinkList &L, int i, ElemType e)
{
    LinkList p = L, p1;
    p1 = new LNode;
    p1->data = e;
    int j=0;
    while(p && j<i-1)
    {
        p = p->next;
        j++;
    }
    if(!p || j>i) return ERROR;
    p1->next = p->next;
    p->next = p1;
}

删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status ListDelete_L(LinkList &L, int i)
{
    LinkList p = L, r;
    int j = 0;
    while(p->next && j<i-1)
    {
        p = p->next;
        j++;
    }
    if(!(p->next) || j>i-1) return ERROR;
    r = p->next;
    p->next = r->next;
    delete r;
    return OK;
}

创建操作实现-尾插法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void CreateList_R(LinkList &L, int n)
{
    L = new LNode;
    L->next = NULL;
    LinkList r = L;
    for(int j=0; j<n; j++)
    {
        LinkList p = new LNode;
        cin>>p->data;
        p->next = NULL;
        r->next = p;
        r = p;
    }
}

单链表创建操作实现-头插法

1
2
3
4
5
6
7
8
9
10
11
12
13
void CreateList_H(LinkList &L, int n)
{
    L = new LNode;
    L->next = NULL;
    LinkList r = L, p;
    for(int i=0; i<n; i++)
    {
        p = new LNode;
        cin >> p->data;
        p->next = r->next;
        r->next = p;
    }
}