单链表

发表于 | 分类于
本文字数： 1.9k | 阅读时长 ≈ 2 分钟

1.单链表的定义

1
2
3
4
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

2.采用头插法建立单链表

从表尾到表头逆向建立单链表L,每次均在头节点之后插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LinkList CreateList1(LinkList &L)
{
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    scanf("%d",&x);
    while(x!=9999)
    {
        s==(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L-next=s;
        scanf("%d",&x);
    }
}

3.采用尾插法建立单链表

从表头到表尾正向建立单链表，每次均在表尾插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LinkList CreateList2(LinkList &L)
{
    int x;
    L=(LinkList)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;
}

4.按序号查找节点值

本算法取出单链表L(带头节点)中第i个位置的节点指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
LNode *GetElem(LinkList L,int i)
{
    int j=1;
    LNode *p=L->next;
    if(i==0)
    {
        return L;
    }
    if(i<1)
    {
        return NULL;
    }
    while(p&&j<i)
    {
        p=p->next;
        j++;
    }
    return p;
}

5.按值查找表节点

查找单链表(带头节点)中数据域为e的节点指针，否则返回NULL

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

6.插入节点

Ⅰ.尾插

1
2
3
p=GetElem(L,i-1);
s->next=p-next;
p-next=s;

Ⅱ.头插

可以找到要插入位置的前驱节点再使用尾插，另一种方法是按尾插插入新的节点，然后再互换前驱和该节点的数据域

1
2
3
4
5
s->next=p->next;
p-next=s;
temp=s->data;
s->data=p->data;
p->data=temp;

7.删除节点

Ⅰ.删除p指针的后继

1
2
3
4
p=GetElem(L,i-1);
q=p->next;
p->next=p->next->next;//p->next=q->next;
free(q);

Ⅱ.删除p指针本身

1
2
3
4
q=p->next;
p->data=p->next->data//p->data=q->data;
p->next=q->next;
free(q);