初学链表Ⅲ

初学链表Ⅲ


循环单链表

在单链表中,将终端节点的指针域NULL改成指向表头节点的或开始节点,就得到了单链形式的循环链表,并简单称为单循环链表

单循环链表结构示意

结构用c语言表示等同非循环单向链表:

1
2
3
4
5
struct CirLnode
{
int data;
struct CirLnode *next;
};

建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct CirLnode* create_list(int len)
{
int i,temp;
struct CirLnode *head,*p,*t;
head = (struct CirLnode*)malloc(sizeof(struct CirLnode));
head->next = NULL;
p = head;
for(i=0;i<len;i++)
{
scanf("%d",&temp);
t = (struct CirLnode*)malloc(sizeof(struct CirLnode));
t->data = temp;
t->next = NULL;
p->next = t;
p = t;
}
p->next = head; //将尾节点指回头结点
return head;
}

插入节点

假设传入的链表升序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct CirLnode* insert_node(int num,struct CirLnode *head)
{
struct CirLnode *p,*t;
int i;
p = head;
while(1)
{
if(p->next==head||p->next->data>num)
{
t = (struct CirLnode*)malloc(sizeof(struct CirLnode));
t->data = num;
t->next = p->next;
p->next = t;
break;
}
p = p->next;
if(p==head) break;
}
return head;
}

其他操作

其他的操作似乎与单链表差不多。

例如删除某个节点:

1
2
3
4
5
6
7
8
9
10
11
12
struct CirLnode* delete_node(int k,struct CirLnode *head)
{
int i;
struct CirLnode *p,*t;
p = head;
for(i=0;i<k;i++)
p = p->next;
t = p->next;
p->next = t->next;
free(t);
return head;
}

循环双链表

循环双链表示意

节点表示当然是一样的:

1
2
3
4
5
6
struct CirDuLnode
{
int data;
struct CirDuLnode *prior;
struct CirDuLnode *next;
};

建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct CirDuLnode* create_list(int len)
{
int i,temp;
struct CirDuLnode *head,*p,*t;
head = (struct CirDuLnode *)malloc(sizeof(struct CirDuLnode));
head->data = 0;
head->prior = head;
head->next = head;
p = head;
for(i=0; i<len; i++)
{
scanf("%d",&temp);
t = (struct CirDuLnode *)malloc(sizeof(struct CirDuLnode));
t->data = temp;
t->next = NULL;
t->prior = p;
p->next = t;
p = t;
}
head->prior = p;
p->next = head; //唯一跟双向链表的区别
return head;
}

正向遍历

1
2
3
4
5
6
7
8
9
10
11
void print_list(struct CirDuLnode *head)
{
struct CirDuLnode *t;
t = head->next;
while(t!=head) //判断条件跟双向链表不同
{
printf("%d ",t->data);
t = t->next;
}
printf("\n");
}

反向遍历

1
2
3
4
5
6
7
8
9
10
11
void re_print_list(struct CirDuLnode *head)
{
struct CirDuLnode *t;
t = head->prior;
while(t!=head) //判断条件跟双向链表不同
{
printf("%d ",t->data);
t = t->prior;
}
printf("\n");
}

其他操作

其他的操作其实都大同小异啦~

可以参考相关文章。


相关文章