单向链表

1.基本概念

链表是用来处理大数据项目用于解决无法连续开辟大块连续内存空间的问题。

单向链表有：

• 带头结点单链表
• 不带头结点单链表
• 带头结点循环单链表
• 不带头结点循环单链表

2. 单向链表的创建

• 单链表的结点模板定义：

typedef int datatype;       // 定义数据类型别名

typedef struct node
{
    datatype data;      	// 数据域
    struct node *next;		// 指针域
}singly_link_list;

从上面的定义得知结点是由存放数据元素的数据域存放后继结点地址的指针域组成。

假设 p 是指向线性表第 i 个元素的指针，则该结点 ai 的数据域是 p->data ，p->data 的值是一个数据元素。

结点 ai 的指针域是 p->next 来表示，p->next 的值是一个指针，它指向的是第 i+1 个元素，即指向 ai+1 的指针。

p->data = ai;
p->next->data = ai+1;

3. 带头单向链表

带头单链表是一个有头结点的单链表

3.1 带头单链表的初始化

// 定义一个不带数据的结点来表示头结点
singly_link_list *list_init(void)
{
	singly_link_list *head = malloc(sizeof(singly_link_list));
	if(head != NULL)
        return head;
	return NULL;
}

// 调用：
singly_link_list *mylist = list_init();
if( mylist == NULL )
{
    printf("链表初始化失败\n");
	exit(0);	//结束程序
}

3.2 新建结点

// 新建结点
singly_link_list *create_node(datatype data)
{
    singly_link_list *new = malloc(sizeof(singly_link_list));
    if(new != NULL)
	{
        new->data = data;
        new->next = NULL;
    }
    return new;
}

// 调用：
for(i=1; i<=n; i++)// 循环创建结点
{
	singly_link_list *new  = create_node(i);
	if(new == NULL)
    {
		printf("%d节点创建失败\n", i);
		continue;	//跳过下面的操作，继续创建新的节点
	}
}

3.3 头插法和尾插法

// 头插法
void inter_head(struct node *head, struct node *new)
{
	new->next = head->next;		// 把新节点指向头节点的下一个
	head->next = new;	    	// 把头节点指向新节点
}

// 尾插法
void inter_tail(singly_link_list *head, singly_link_list *new)
{
	while (head->next != NULL)
		head = head->next;    	// 一个一个往后找，直到找到最后一个结点
	head->next = new; 			// 将最后一个结点的后继指针next设置为new（新结点地址）
}

3.4 插入结点

插入结点到指定位置

// 插入结点到链表指定位置
void inter_node(singly_link_list *node1, singly_link_list *node2)
{
	if(node1 == NULL || node2 == NULL)
		return ;
	node2->next = node1->next; 	// 在结点node1的后面插入node2结点
	node1->next = node2;
    
    // insert_head(node1, node2);	// 相当于头插法,node1相当于头节点，node2相当于新节点
}

3.5 遍历链表

// 遍历链表
void display_list(singly_link_list *head)
{
	//遍历链表的每一个元素，直到最后一个
	while(head->next != NULL)
	{
		printf("%d->", head->next->data);
		head = head->next;
		if(head->next == NULL)
			printf("^");	// 用 ^ 表示空
    }
	printf("\n");
}

3.6 查找结点

//判断链表是否为空
bool is_empty(struct node *head)
{
	return head->next == NULL;
}
// 查找结点		
singly_link_list *find_node(singly_link_list *head, datatype data)
{
	if(is_empty(head))
		return NULL;

	while(head->next != NULL)
	{
		head = head->next;
		if(head->data == data)     // 如果datatype是结构体、字符串类型,不可以直接这样比较
		{
			printf("找到该结点\n");
			return head;
		}
	}
}

3.7 删除结点

删除只是将结点从该链表中删除，但是这个结点还会存留在空间中，依旧可以对它进行其他操作。

// 删除结点
singly_link_list *remove_node(singly_link_list *head, datatype data)
{
	singly_link_list *d_node = NULL;
	if(is_empty(head))
		return NULL;
	//遍历所有元素，查找是否有匹配data的值
	while(head->next != NULL)
	{
		d_node = head->next;
		
		if(head->next->data == data)	//如果datatype是结构体类型？是字符串类型？是否可以这样直接比较？
		{
			head->next = d_node->next;
			d_node->next = NULL;
			return d_node;	//返回删除的节点
		}
		head = head->next;
	}
	return NULL;	//没该元素，删除失败
}

3.8 销毁结点

// 销毁某一条链表的结点
bool destroy_node(singly_link_list *head, datatype data)
{
	struct node *d_node = remove_node(head, data);	//从链表中删除这个节点
	if(d_node != NULL)
	{
		free(d_node);	//释放这个节点的空间
		return true;
	}
	return false;
}

3.9 销毁链表

//销毁链表
void destroy_list(singly_link_list **head)
{
	singly_link_list *tmp = (*head)->next;
	//如果头的下一个节点不为空，就释放掉
	//如果头的下一个为空，说明只剩下头节点
	while( (*head)->next != NULL )
	{
		(*head)->next = tmp->next;
		free( tmp );
		tmp = (*head)->next;
	}
	free(*head);	//把头节点也释放掉
	
	*head = NULL;	//让这个链表头指针置空
}

3.10 移动结点

// 结点的移动
bool move_node(singly_link_list *head, datatype srcdata, datatype destdata)
{
	singly_link_list *f_node_dest = NULL;
	singly_link_list *f_node_src = NULL;
	//链表是否为空？
	if(is_empty(head))
		return false;
	
	//destdata节点是否存在？
	if( (f_node_dest = find_node(head, destdata)) == NULL){
		return false;
	}

	//srcdata节点是否存在？
	if( (f_node_src = find_node(head, srcdata)) == NULL){
		return false;
	}

	//移动 = 删除+头插
	f_node_src = remove_node(head, srcdata);
	inter_head(f_node_dest, f_node_src);
	
	return true;
}

3.11 更新结点

// 更新结点
void update_node(singly_link_list *head, datatype old_data, datatype new_data)
{
	singly_link_list *find = find_node(head, old_data);
	if (find == NULL)
		printf("没有找到结点，修改失败\n");
	else
	{
		find->data = new_data;
		printf("数据更新成功\n");
	}
}

3.12 main测试代码

int main(int argc, char *argv[])
{
	singly_link_list *mlist = list_init();
	if(mlist == NULL)
	{
		printf("链表初始化失败\n");
		exit(0);   // 结束程序
	}

	int i, n;
	printf("输入多少个自然数：");
	scanf("%d", &n);

	for(i=1; i<=n; i++)// 循环创建结点
	{
		singly_link_list *new  = create_node(i);
		if(new == NULL)
		{
			printf("%d节点创建失败\n", i);
			continue;	//跳过下面的操作，继续创建新的节点
		}
		// inter_head(mlist, new);
		inter_tail(mlist, new);
	}

	display_list(mlist);	
	move_node(mlist, 16, 8);
	update_node(mlist, 3, 77);
	display_list(mlist);

	return 0;
}

4. 不带头单向链表

没有头结点，头指针指向的就是第一个元素。

singly_link_list *mlist = NULL;