循环链表插入和删除

86 阅读 0 评论 57 点赞

我是靠谱客的博主美满蓝天，这篇文章主要介绍循环链表插入和删除，现在分享给大家，希望可以做个参考。

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表成为单循环链表，简称循环链表。

单链表判断空链表为head->next 而循环链表判断空链表为head->next 是否等于head

时间复杂度

由于终端结点用尾指针rear指示，则查找终端结点是O(1)，而开始结点是rear->next->next，当然也是O(1)

初始化循环链表

复制代码

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
34
35
36
37
38
39
40
41
42
43
44
45
void ds_init(node **pNode)
{
    int item;
    node *temp;
    node *target;
    
    printf("输入结点的值，输入0完成初始化n");
    
    while(1)
    {
        scanf("&d", &item);
        fflush(stdin);
        
        if(item == 0)
            return;
        
        if((*pNode) == NULL)
        {
            /* 循环链表只有一个结点 */
            *pNode = (node*)malloc(sizeof(struct CLinkList));
            
            if(!(*pNode))
            	exit(0);
            
            (*pNode)->data = item;
            (*pNode)->next = *pNode;
        }
        else
        {
            /* 找到next指向第一个结点的结点 */
            for(target = (*pNode); target->next != (*pNode); target = target->next)
                ;
            /* 生成一个新的结点 */
            temp = (node *)malloc(sizeof(struct CLinkList));
            
            if(!temp)
                exit(0);
            
            temp->data = item;
            temp->next = *pNode;
            target->next = temp;
        }
    }
}

插入结点

复制代码

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void ds_insert(node **pNode, int i)
{
    node *temp;
    node *target;
    node *p;
    int item;
    int j = 1;
    
    printf("输入要插入结点的值：");
    scanf("%d", &item);
    
    if(i == 1)
    {
        // 新插入的结点作为第一结点
        temp = (node *)malloc(sizeof(struct CLinkList));
        
        if(temp)
            exit(0);
        
        temp->data = item;
        
        /* 寻找最后一个结点 */
        for(target = (*pNode); target->next != (*pNode); target = target->next)
            ;
        
        temp->next = (*pNode);
        target->next = temp;
        *pNode = temp;
    }
    else
    {
        target = *pNode;
        for(; j < (i-1); ++j)
        {
            target = target->next;
        }
        
        temp = (node *)malloc(sizeof(struct CLinkList));
        
        if(!temp)
            exit(0);
        
        temp->data = item;
      	
        p = target->next;
        target->next = temp;
        *pNode = p;
    }
}

删除结点

复制代码

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
void ds_delete(node **pNode, int i)
{
    node *target;
    node *temp;
    int j = 1;
    
     if(i == 1)
    {
        // 删除的是第一个结点  
        /* 寻找最后一个结点 */
        for(target = (*pNode); target->next != (*pNode); target = target->next)
            ;
        
        temp = (*pNode);
        *pNode = (*pNode)->next;
         target->next = *pNode;
         free(temp);
    }
    else
    {
        target = *pNode;
        
        for(; j< i-1; ++j)
        {
            target = target->next;
        }
        
        temp = target->next;
        target->next = temp->next;
        free(temp);
    }
}

返回结点所在位置

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int ds_search(node *pNode, int elem)
{
	node *target;
    int i = 1;
    
    for(target = pNode; target->data != elem && target->next != pNode; ++i)
    {
        target = target->next;
    }
    
    if(target->next == pNode) // 表中不存在该元素
        return 0;
    else
        return i;
}