· 附录对于头结点单向链表的优化方法

————————————本文旨在交流学习计算机知识，欢迎交流讨——————————— 上一章，我们浅显的讨论了链表的结构，本文在上一章的链表的基础上做出了些许优化，可配合食用。回到正题，我们已经了解链表的结构，它是一种非连续空间存储的线性表，主要依靠地址域访问下一个元素并通过遍历操作进行增删改查。如图，这是我们上一章所介绍的链表结构：我们的惯用操作：

1
//单向链表的插入，删除（先找到节点p）：
2

3
//插入：
4
newnode->next=p->next;
5
p->next=newnode;
6
//删除：
7
node_new temp;
8
temp=p->next;
9
p->next=p->next->next;
10
free(temp);

看着这幅图，我们不禁想到一个问题：我们真的需要这个头节点吗，是否有些看起来不整齐且结构不一致？于是，我们考虑到：也许我们可以用指针标记header的位置，然后再在每一次的函数接口里面新建一个头结点，用完即删，这样或许看起来更加的整齐和高效。如图所示：这时，我们引入dummy节点，并将其放入栈，dummy节点充当第一个节点。

1
void insert(link*header,element val)
2
{
3
node_t dummy;
4
dummy->next=header;//header为我们的指针（因为简化了头结点，我们只传入指针）
5
node_t *p=&dummy;//p为遍历指针，从dummy开始遍历；
6
while(p->next)
7
{
8
p=p->next;
9
}
10
header=dummy->next;//还原操作；
11
}

下面，我们重写一下代码：定义链表结构：

1
typedef int Element_t;
2
struct node{
3
Element_t val;
4
struct node *next;
5
}node_t;
6
//节点的结构体；
7

8
typedef struct {
9
node_t *header;
10
int count;
11
} List_t;
12
//链表结构体（包括头结点和数量）；

初始化链表：

1
void initList(List_t *table)
2
{
3
table->count=0;
4
table->header=NULL;
5
)

从最基础的展现函数开始：

1
void shouList(const List_t *table){
2
node_t p=table->header;
3
printf("List :");
4
while(p)
5
{
6
printf("%d\t",p->val);
7
p=p->next;
8
}
9
printf("\n");
10
}

这里如果不知道const为什么要放在形参里的可以看看我的第一篇文章，里面有详细解答。然后就是增删改查的经典案例了：从增开始：

1
int insertListHeader(List_t* table,Element_t val)
2
{
3
node_t dummy;
4
dummy.next=table->header;
5

6
node_t *p=&dummy;//临时头结点dummy及临时过渡中间容器p；
7
node_t *new_node=malloc(sizeof(node_t));
8

9
if(new_node==NULL)
10
{
11
printf("ERROR\n");
12
)
13
//朴素的增加操作；
14
new_node->val=val;
15
new_node->next=p->next;
16
p->next=new_node;
17
++table->count;
18

19
table->header=dummy->next;
20
return 0;
21
}

然后这是按位插入操作：

1
int insertListPos(List_t* table,int pos,Element_t val)
2
{
3
if(postable->count)
4
{
5
printf("the pos is not a truly place\n");
6
}
7
node_t dummy;
8
dummy.next=table->header;
9
node_t* p=&dummy;
10
int index=-1;//计数器；
11
while(indexnext;
12
++index;
13
}//遍历查找
14
node_t *new_node=malloc(sizeof(node_t));
15
new_node->next=p->next;
16
p->next=new_node;
17
++table->count;
18
table->header=dummy.next;
19
return 0;
20
}

删除操作：

1
int deleteList(List_t* table,Element val)
2
{
3
node_t dummy;
4
dummy.next=table->header;
5

6
node_t* p=&dummy;
7
while(p->next&&p->val!=val)
8
{
9
p=p->next;
10
}
11
if(p->next==NULL)
12
{
13
printf("404 NOT FOUND\n");
14
return 0;
15
}
16
node_t temp=malloc(sizeof(node_t));
17
temp=p->next;
18
p->next=p_next_next;
19
free(temp);
20
--table->count;
21
table->header=dummy->next;
22
return 0;
23
}

最后的最后就是销毁链表了： ###关于销毁链表，其原理就是按位遍历并按位删除。###

1
void destroyList(List_t *table) {
2
node_t dummy;
3
dummy.next = table->header;
4

5
node_t *p = &dummy;
6
node_t *tmp;
7
while (p->next) {
8
tmp = p->next;
9
p->next = tmp->next;
10
free(tmp);
11
--table->count;
12
}
13
printf("LinkList have %d node!\n", table->count);
14
// table->header = NULL;
15
}

以上就是附录内容，欢迎指正！

音乐

文章分享

评论区

音乐

音乐

文章目录