首页 > 代码库 > 重刷数据结构，小题大做，——难道非要头结点吗？

重刷数据结构，小题大做，——难道非要头结点吗？

2024-07-17 23:24:53   217人阅读

数据结构教材上讲线性表的链式表示时，通常都会引入一个头结点。

带头结点的链表示意图如下：
1.空链表

2.有三个结点的单链表

按照书上的说法，引入头结点有一下两个优点：
  1. 由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
  2. 无论链表是否为空，其头指针是指向头结点的非空指针，因此空表和非空表的处理也就一致了。
上面的两点的意思是：1.不管是在第一个位置还是其它位置插入一个新的结点，都是在一个结点之后插入（在第一个位置插入新结点，是在头结点后插入）；如果没有头结点，在第一个位置插入结点是直接给头指针赋值，而在其它位置插入结点是将结点插入到一个结点之后，这两种处理是不同的。删除结点也类似；
2.空表和非空表中都有结点，所以对空表的处理也就一致了。

你可能会疑惑：难道非得要头指针吗？难道没有头结点，插入、删除、空表的处理就不一致了吗？（貌似有一些同学和我有同样的疑问）


不一致问题的来源

教材给出的插入和删除操作的算法如下：
插入结点

s->next = p->next;
p->next = s;

删除结点

p->next = q->next;
free(q);

        从上面可以看出，插入和删除结点的核心操作在于改变结点的next指针域指向。而上面都是通过指向结点的指针来改变结点的next域的，比如p->next = q->next。在没有头结点的情况下，如果要插入和删除第一个结点，需要修改头指针。而头指针不属于任何结点，不能通过修改某个结点的next指针域来修改头指针，所以得特殊处理，这就带来了操作的不一致性。头指针、结点的next指针域，它们虽然都是同一种类型的指针，但得分开处理。
        所以问题的来源在于：通过指向结点的指针来访问结点的next指针域，这种方法不适合头指针。



书上的解决方法
书上的解决方法就是引入头结点。这样即使是插入或删除第一个结点，而已不需要修改头指针，而只需要通过头指针修改头结点的next指针域。这样操作都一致了。


新的解决方法
前面说了，问题的来源是“通过指向结点的指针来访问结点的next指针域，这种方法不适合头指针” 。这种访问方法把头指针和结点的next指针当做两个不同的东西。那我们为什么不把头指针和结点的next指针域看做同一种东西呢?它们本就是同样的数据类型啊！这样不是可以一致处理了。把它们都看作指向结点的指针，就可以通过指向指针的指针来修改和访问了。新的算法如下：

插入

s->next = *p;    //p指向指针的指针
*p = s;

删除

*p = q->next;    //p指向指针的指针
free(q);

小弟通过上面的思路写代码证实了，这种方法可以达到同样的效果。不需要添加头结点，而且操作一致。


代码
下面是两份代码，一份是教材上有头结点的版本，一份是本文提出的无头结点的版本。代码都通过测试！
/*
*有头结点版本
*作者：善良超哥哥
*时间：2014-8-16
*/
//LinkList.h
#ifndef _LIMKLIST_H_
#define _LINKLIST_H_

typedef struct LNode{
	char	data;
	struct LNode *next;
}LNode;

typedef struct{
	LNode	*head;	//指向第一个结点的指针
	int		len;	//链表长度
}LinkList;

//创建链表，尾插法
void CreateList(LinkList *L);
//在第i个位置插入元素e
int ListInsert(LinkList *L,int i,char e);
//删除第i个位置的元素，并用*e返回
int ListDelete(LinkList *L,int i,char *e);
//遍历打印链表中的所有元素
void ListPrint(LinkList *L);

#endif
//LinkList.c
/*
有头结点的链表实现
*/

#include "LinkList.h"
#include <stdio.h>
#include <stdlib.h>

//创建链表，尾插法
void CreateList(LinkList *L)
{
	L->head = malloc(sizeof(LNode));//创建头结点
	L->head->next = NULL;
	L->len = 0;
	
	//开始输入字符，创建链表，以#结束
	char c;
	LNode *p = L->head;
	while((c = getchar()) != '#')
	{
		LNode *s = malloc(sizeof(LNode));
		s->data = http://www.mamicode.com/c;>

无头结点版本：
/*
*无头结点版本
*作者：善良超哥哥
*时间：2014-8-16
*/
//LinkList.h
#ifndef _LIMKLIST_H_
#define _LINKLIST_H_

typedef struct LNode{
	char	data;
	struct LNode *next;
}LNode;

typedef struct{
	LNode	*head;	//指向第一个结点的指针
	int		len;	//链表长度
}LinkList;

//创建链表，尾插法
void CreateList(LinkList *L);
//在第i个位置插入元素e
int ListInsert(LinkList *L,int i,char e);
//删除第i个位置的元素，并用*e返回
int ListDelete(LinkList *L,int i,char *e);
//遍历打印链表中的所有元素
void ListPrint(LinkList *L);

#endif


//LinkList.c

#include "LinkList.h"
#include <stdio.h>
#include <stdlib.h>

//创建链表，尾插法
void CreateList(LinkList *L)
{
L->head = NULL;
L->len = 0;
//开始输入字符，创建链表，以#结束
char c;
LNode **p = &(L->head);
while((c = getchar()) != ‘#‘)
{
LNode *s = malloc(sizeof(LNode));
s->data = http://www.mamicode.com/c;
(*p) = s;
p = &(s->next);
++(L->len);
}
(*p) = NULL;
}

//在第i个位置插入元素e
int ListInsert(LinkList *L,int i,char e)
{
if(i < 1 || i > L->len || L == NULL)
{
return 0;//失败
}
LNode **p = &(L->head);
for(int j = 1; j < i; j++)
{
p = &((*p)->next);
}
LNode *s = malloc(sizeof(LNode));
s->data = http://www.mamicode.com/e;
s->next = *p;
*p = s;
++(L->len);
return 1;
}

//删除第i个位置的元素，并用*返回
int ListDelete(LinkList *L,int i,char *e)
{
if(L == NULL || i < 1 || i >= L->len)
{
return 0;//失败了
}
LNode **p = &(L->head);
for(int j = 1; j < i; j++)
{
p = &((*p)->next);
}
//删除p指针指向的结点
LNode *q = *p;
*p = q->next;
*e = q->data;
free(q);
--(L->len);
return 1;
}

//遍历打印链表中的所有元素
void ListPrint(LinkList *L)
{
LNode *p = L->head;
while(p!=NULL)
{
printf("%c",p->data);
p = p->next;
}
printf("\n");
}


算法对比


联系
我们