初学链表Ⅰ

初学链表Ⅰ


太菜了,现在才学链表。

链表 是一种物理存储单元上非连续、非顺序的存储结构。链表由一系列结点组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。查找一个节点的复杂度为O(n)

单向链表

单链表结构示意

用C语言表示大概是这样的:

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

带头节点/不带头结点的链表

单链表分为带头节点的跟不带头结点的。
两者有些区别,带头节点的大概有这么些特点:

  • 链表为空时,带头节点的单链表头指针指向头结点,不带头结点的头指针为NULL。
  • 向链表表头插入或删除节点时带头结点的似乎更方便,不,应该是绝对更方便。
  • 无论单链表是否为空,头指针永远指向的是头结点,可以减少一些Bug的出现。

这篇文章使用的带头结点的方式。

建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct node* createlist(int len)
{
struct node *head,*p,*t;
int i,temp;
head = NULL;
head = (struct node *)malloc(sizeof(struct node)); //申请头结点
if (!head) exit(-1); //申请失败
head->next = NULL; //初始化
for(i=0; i<len; i++)
{
scanf("%d",&temp);
t = (struct node *)malloc(sizeof(struct node)); //申请临时节点
t->data = temp;
t->next = NULL;
if(head->next==NULL) //如果头结点的指针域为空
head->next = t;
else p->next = t; //如果已经添加过节点
p = t;
}
return head; //返回头节点
}

插入节点

假设传入的链表升序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct node* insert_node(int num, struct node *head)
{
struct node *t,*q;
t = head; //从表头开始遍历
while(t!=NULL)
{
if(t->next==NULL||t->next->data>=num)
//注意:条件的顺序不能改变!!
//如果下一个节点大于待插入数或者下一个节点是表尾 则插入
{
q->data = num;
q->next = t->next;
t->next = q;
break;
}
t = t->next; //移到下一个节点
}
return head; //返回头结点
}

删除节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
struct node* delete_node(int k, struct node *head)
{
int i;
struct node *t,*p;
t = head;
for(i=0; i<k; i++) //遍历节点
t = t->next;
if(t->next == NULL) //已经到表尾了或数据输入有误
printf("Error!\n");
else
{
p = t->next;
t->next = p->next;
free(p);
}
return head; //返回头结点
}

逆向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct node* reverse_list(struct node *head)
{
struct node *p,*q,*t;
//如果链表长度为1
if(head->next->next == NULL) //带了头结点所以是->next->next
return head;
p = head->next;
q = p->next;
t = NULL;
while(q != NULL)
{
t = q->next;
q->next = p;
p = q;
q = t;
}
head->next->next = NULL;
head->next = p;
return head;
}

输出节点

输出很简单,简单遍历即可。

1
2
3
4
5
6
7
8
9
10
11
12
void print_list(struct node *head)
{
struct node *p;
p = head->next;
while(p!=NULL)
{
printf("%d ",p->data);
p = p->next;
}
printf("\n");
return;
}

统计节点数

1
2
3
4
5
6
7
8
9
10
11
int analyse_list(struct node *head)
{
struct node *t = head;
int num=0;
while(t->next != NULL)
{
num++;
t = t->next;
}
return num;
}

删除链表

1
2
3
4
5
6
7
8
9
10
11
12
void destroy_list(struct node *head)
{
struct node *p,*t;
p = head->next;
while(p != NULL)
{
t = p;
p = p->next;
free(t);
}
free(head);
}

相关文章