数据结构笔记-单链表

发表于 | 分类于 ，

哎呀！图片走丢了！

上大学以及博客复活后的第一篇博文，写点简单的吧，也算纪念一下。

单链表的节点声明

单链表中的节点使用结构体来定义，每个节点包含数据域和指针域。数据域保存节点信息，指针域保存下一节点的地址。

1
2
3
4
5
typedef struct Node
{
    int data;
    struct Node *next;
}node,*node_p;

单链表的建立

单链表的建立有头插法和尾插法两种，除了建成后数据顺序不同之外没啥区别。创建单个节点时，使用malloc函数申请新空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
//头插法
node_p build_head(int n)
{
    node_p l,p;
    l=(node_p)malloc(sizeof(node));
    l->next=NULL;
    for(int i=0;i<n;++i)
    {
        p=(node_p)malloc(sizeof(node));
        scanf("%d",&p->data);
        p->next=l->next;
        l->next=p;
    }
    return l;
}

//尾插法
node_p build_final(int n)
{
    node_p l,p,q;	//q指向当前链表的最后一个节点
    l=(node_p)malloc(sizeof(node));
    l->next=NULL;
    q=l;
    for(int i=0;i<n;++i)
    {
        p=(node_p)malloc(sizeof(node));
        scanf("%d",&p->data);
        p->next=NULL;
        q->next=p;
        q=p;
    }
    return l;
}

单链表的插入

没啥特殊的······直接看代码吧

1
2
3
4
5
6
7
8
void insert(node_p l,int n,node_p p)	//在第n个节点后插入p节点
{
    node_p q=l;
    for(int i=1;i<=n;++i)
        q=q->next;
    p->next=q->next;
    q->next=p;
}

单链表的删除

先找到被删节点的前一个节点，将其指针域指向被删节点的下一个节点，再释放被删节点。

1
2
3
4
5
6
7
8
void del(node_p l,int n)	//删除第n个节点
{
    node_p p=l;
    for(int i=1;i<n;++i)	//循环n-1次，找到第n个节点的前一个节点
        p=p->next;
   	p->next=p->next->next;
    free(p->next);
}

单链表的就地逆置

所谓就地逆置，就是再不改变物理储存位置的前提下将链表逆置。

基本思路为：分别用$p,q$两个指针指向第$i,i+1$个节点，然后让$q$指向$p$。这时需要让$p,q$依次后移一个节点，而因为$q$指向了$p$，所以$q$与后续节点的联系就断了，那么就需要用另一个指针保存$q$的后续节点的位置，即$o=q->next$。然后就可以借助$o$完成$p,q$的依次后移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
node_p turn(node_p l)
{
    if(!l->next->next)
        return l;
    node_p p=l->next,q=l->next->next,o=l;
    while(o)
    {
        o=q->next;	//o指向q的下一个，方便之后后移
        q->next=p;
        p=q;
        q=o;
    }	//运行到最后一次时，q先指向尾节点，o指向空。p，q逆置完成后，p指向尾节点，q指向空
    	//所以最后停在尾节点的指针为p
    l->next->next=NULL;    //让之前的一号节点指向空（此时头指针l仍指向之前的一号节点）
    l->next=p;    //头指针指向现在的一号节点
    return l;
}
0%