线性表——单链表的设计思路与实现

WangSZ徽章-先富之人-津桥芝士平台等级-认证-LV10-津桥芝士平台6个月前更新
471

单链表的基本定义：

单链表的结构像一个链条一般，一个结点的next指针指向后一个结点的地址，以此类推，在使用时通过头结点的next指针向后访问，一般的，头结点作为整个链表开始的标志，不存放任何数据，这种会造成空间的浪费，所以根据实际情况，可以确定是否使用不存储数据的头结点。

typedef struct Node{
	ElemType data;
	struct Node *next;
}Node, *LinkList;

单链表的初始化：

对于单链表的初始化，设计思路如下：

  • 头结点可以使用一个指针，对其分配地址。如果分配内存成功，将其next指针指向NULL，返回头结点的地址，分配内存失败就返回NULL。在分配内存后，一定要将next指针指向NULL，防止野指针。

代码的实现：

Node *InitList(LinkList L)			//创建一个头结点 
{
	L = (Node *)malloc(sizeof(Node));
	if(L == NULL)
		return NULL;
	L->data = 0;
	L->next = NULL; 
	return L;
}

单链表数据的插入（头插法）：

将一个结点插入在表头之后，称之为头插法，设计思路如下：

  • 将新结点的next指针指向头结点的next指针指向的地址，
  • 再将头结点的指针指向新结点的地址，完成插入。

实现代码如下：

Node *InsertListHead(LinkList L, ElemType data)			//头插法 
{
	Node *p = (Node *)malloc(sizeof(Node));
	if(p == NULL)
		return NULL;
	p->data = data;
	p->next = L->next;
	L->next = p;
	L->data++;
	return p;
}

单链表数据的插入（尾插法）：

将一个结点插入表尾，称之为尾插法，设计思路如下：

  • 首先通过循环找到表尾，接着将新结点的指针指向表尾的地址（NULL)
  • 再将表尾的next指针指向新结点的地址，再将新地址返回。

实现代码如下：

Node *InsertListTail(LinkList L, ElemType data)			//尾插法 
{
	Node *p = (Node *)malloc(sizeof(Node)), *r = L;
	if(p == NULL)
		return NULL;
		
	p->data = data;
	while(r->next != NULL)
		r = r->next;
	p->next = r->next;
	r->next = p;
	r = p;
	L->data++; 
	return r;
}

在指定位置插入元素：

在指定位置插入元素的设计思路如下：

  • 先进行基本的位置判断，看插入的位置是否合法，不合法就返回false。
  • 为新的节点分配一个内存空间，并判断是否分配内存成功。
  • 接着找到待插入的位置（假设位置是从头结点开始依次向后数），接着将新节点的next指针指向作为缓冲的节点的next指针指向的地址。
  • 接着将作为缓冲节点的next指针指向新节点的地址。返回true。

实现代码如下（以头结点作为0，向后数依次递增）：

bool Insert(LinkList L, int pos, ElemType data)			//在指定位置插入一个元素 
{
	if(pos < 1 || pos > Size(L))   	// 先进行位置检查 
		return false;
	int i;
	Node *p = L, *s = (Node *)malloc(sizeof(Node));
	if(s == NULL)					// 判断是否分配内存成功 
	    return false; 
	for(i = 1; i < pos; i++)     // 找到插入的位置 
	    p = p->next;
	s->data = data;
	s->next = p->next;
	p->next = s;
	L->data++;
	return true; 
}

删除某个位置的结点：

删除某个位置的节点的实现如下：

  • 先进行位置的判断和链表是否为空的判断，位置不对或链表为空，返回NULL。
  • 遍历到待删除位置的前一个结点（结点1），再通过另外一个指针指向待删除的位置（结点2）。
  • 将指向结点1的next指针指向结点2的next指针指向的地址，完成对于结点的连接。
  • 返回删除的位置的指针。

代码实现如下：

Node *DeletePosition(LinkList L, int pos)			//删除单链表中指定位置的结点 
{
	if(pos < 1 || pos > Size(L) || L->next == NULL)
		return NULL;
	Node *p = L, *q = NULL, *buf = NULL;
	int i;
	ElemType e;
	
	for(i = 1; i < pos; i++)
	    p = p->next;
	q = p->next; 
	p->next = q->next;
	return q;
}

删除链表中的某个值：

删除链表中的某个值大致如下：

  • 先设置两个缓冲结点，一个作为非判断条件的结点（结点1），一个作为用于条件判断的指针（结点2）。
  • 遍历整个单链表，其将在目标值与数据域相同时，释放掉结点的空间。当作为结点2的next指针指向NULL时循环结束，保持结点1的next指针指向结点2的地址。
  • 循环时，当数据域满足删除的条件，将结点1的next指针指向结点2的next指针指向的地址，接着释放掉节点2的内存，完成删除。
void DeleteValue(LinkList L, ElemType value)
{
	Node *p = L, *q = L;
	while(q->next != NULL)
	{
		p = q->next;
		if(p->data == value)
		{
			q->next = p->next;
			free(p);
			continue;
		}
		q = p;
	}
}

销毁整个链表：

销毁整个单链表的步骤大致如下：

  • 一个缓冲结点用于作为指向头结点（暂将其视为结点1），另外设置一个缓冲结点（结点2）。
  • 先将结点2指向待销毁的结点的后一个结点，销毁掉待销毁的结点，接着将指结点2指向的结点赋值结点1
  • 重复上述一步，直到结点1指向NULL。

实现代码如下：

void Destory(LinkList L)			// 销毁单链表 
{
	Node *p = L, *q = NULL;
	while(p != NULL)
	{
		q = p->next;
                p = ->next;
		free(q);
	}
}

查询某个值是否存在：

查询某个值是否存在的步骤大致如下：

  • 将一个缓冲结点指向头结点。
  • 循环中将缓冲结点指向其next指针指向的地址，当数据域是要查询的值，则返回true（或者是其它标识）,当遍历到最后一个结点时，还未能查找到，则结束循环，返回false;

实现代码如下：

bool Find(LinkList L, ElemType e)			//按值查找 
{
    Node *p = L;
    while(p->next != NULL)
    {
    	p = p->next;
    	if(p->data == e)
    		return true
    }
    return false
}

统计链表中的结点数量：

获取结点的数量步骤大致如下：

  • 设置一个缓冲结点指向头结点，再设置一个变量用于计数。
  • 接着遍历整个单链表，将缓冲结点的指针指向的缓冲结点的next指针指向的地址，当next指针指向NULL结束。
  • 返回计数的变量。

实现代码如下：

int Size(LinkList L)			//检查单链表中的元素个数 
{
	Node *p = L;
	int count = 0;
	while(p->next != NULL)
	{
		p = p->next;
		++count;
	}
	return count;
}

查询链表是否为空：

  • 如果头结点的next指针指向NULL，则说明为空，返回true，否则返回false。

实现代码如下：

bool Empty(LinkList L)			//检查单链表是否为空表 
{
	if(L->next == NULL)
	    return true;
	return false;
}

修改某个结点的数据域：

修改结点的数据域，步骤大致如下：

  • 先判断位置是否合法，或者是链表是否为空，空则返回false。
  • 将指针指向待修改的位置的地址，这一步通过简单循环即可实现。
  • 修改其数据域。

实现代码如下：

bool Change(LinkList L, int pos, ElemType e)
{
	if(pos < 1 || pos > Size(L) || Empty(L))
            return false;
	Node *p = L;
	int i;
	for(i = 1; i <= pos; i++)
	    p = p->next;
	p->data = e;
	return true;
}

总实现代码

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>

typedef int ElemType;

typedef struct Node{
	ElemType data;
	struct Node *next;
}Node, *LinkList;

bool Empty(LinkList L)			//检查单链表是否为空表 
{
	if(L->next == NULL)
	    return true;
	return false;
}

int Size(LinkList L)			//检查单链表中的元素个数 
{
	Node *p = L;
	int count = 0;
	while(p->next != NULL)
	{
		p = p->next;
		++count;
	}
	return count;
}

Node *InitList(LinkList L)			//创建一个头结点 
{
	L = (Node *)malloc(sizeof(Node));
	if(L == NULL)
		return NULL;
	L->data = 0;
	L->next = NULL; 
	return L;
}

Node *InsertListHead(LinkList L, ElemType data)			//头插法 
{
	Node *p = (Node *)malloc(sizeof(Node));
	if(p == NULL)
		return NULL;
	p->data = data;
	p->next = L->next;
	L->next = p;
	L->data++;
	return p;
}

Node *InsertListTail(LinkList L, ElemType data)			//尾插法 
{
	Node *p = (Node *)malloc(sizeof(Node)), *r = L;
	if(p == NULL)
		return NULL;
		
	p->data = data;
	while(r->next != NULL)
		r = r->next;
	p->next = r->next;
	r->next = p;
	r = p;
	L->data++; 
	return r;
}

bool Insert(LinkList L, int pos, ElemType data)			//在指定位置插入一个元素 
{
	if(pos < 1 || pos > L->data)   	// 先进行位置检查 
		return false;
	int i;
	Node *p = L, *s = (Node *)malloc(sizeof(Node));
	if(s == NULL)					// 判断是否分配内存成功 
		return false; 
	for(i = 1; i < pos; i++)     // 找到插入的位置 
	    p = p->next;
	s->data = data;
	s->next = p->next;
	p->next = s;
	L->data++;
	return true; 
}

void Destory(LinkList L)			// 销毁单链表 
{
	Node *p = L, *q = NULL;
	while(p != NULL)
	{
		q = p;
                p = p->next;
		free(q);
	}
}

Node *DeletePosition(LinkList L, int pos)			//删除单链表中指定位置的结点 
{
	if(pos < 1 || pos > L->data || L->next == NULL)
		return NULL;
	Node *p = L, *q = NULL;
	int i;
	ElemType e;
	
	for(i = 1; i < pos; i++)
	    p = p->next;
	q = p->next; 
	p->next = q->next;
	return q;
}

void DeleteValue(LinkList L, ElemType value)
{
	Node *p = L, *q = L;
	while(q->next != NULL)
	{
		p = q->next;
		if(p->data == value)
		{
			q->next = p->next;
			free(p);
			continue;
		}
		q = p;
	}
}

bool Change(LinkList L, int pos, ElemType e)
{
	if(pos < 1 || pos > Size(L) || Empty(L))
		return false;
	Node *p = L;
	int i;
	for(i = 1; i <= pos; i++)
	    p = p->next;
	p->data = e;
	return true;
} 

bool Find(LinkList L, ElemType e)			//按值查找 
{
    Node *p = L;
    while(p->next != NULL)
    {
    	p = p->next;
    	if(p->data == e)
    		return true;
	}
	return false;
}

int main()
{
	
	return 0;
}
1
1人已评分
分享
请登录后发表评论

    回复1
    只看作者
    最新最热
发布文章发布帖子
在手机上浏览此页面
工作时间
全周无休：9:00-23:00
欢迎大家骚扰
zibll子比主题
本站同款主题模板
zibll子比主题是一款漂亮优雅的网站主题模板，功能强大，配置简单。
查看详情