前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >线性表的链式存储-单链表

线性表的链式存储-单链表

作者头像
Cloud-Cloudys
发布于 2020-07-06 11:31:41
4370
发布于 2020-07-06 11:31:41
举报
文章被收录于专栏：ShanSan的云原生之路

单链表操作

  • 单链表的创建（尾插法、头插法）
  • 单链表的查找操作
  • 单链表的删除操作
  • 单链表的逆置操作(使用头插法)
  • 单链表表长的计算
  • 打印单链表

单链表的创建

头插法

代码语言：javascript
复制
forward_list* creat_3()    //头插法
{
    forward_list *head,*s;
	int num;
	head = NULL;//链表初始状态为空
	while(scanf("%d",&num) && num)
	{
		s = (forward_list*)malloc(sizeof(forward_list));
		s->data = num;

		s->next = head;

		head = s;//将新结点插入到表头
	}
	return head;
}

尾插法（不含头结点）

代码语言：javascript
复制
//尾插法建表
forward_list* creat_1()
{
    forward_list *head=NULL;//头指针，初始状态为空
	forward_list *rear=NULL;//尾指针，初始状态为空
	int num;
	forward_list *s;
	while(scanf("%d",&num) == 1 && num)//输入0结束
	{
		s = (forward_list*)malloc(sizeof(forward_list));

		s->data = num;
		if(head == NULL)//将新节点加入空表
	        head = s;
	    else            //原表非空，将新节点链接到表尾之后
	        rear->next = s;
		rear = s;//尾指针指向新的表尾
    }
    if(rear!= NULL)//对于非空表，将尾结点的下一个结点置空
	    rear->next = NULL;

	return head;
}

尾插法（含头结点）

代码语言：javascript
复制
//尾插法建表,包含头结点
forward_list* creat_2()
{
	forward_list *s;
	forward_list *head, *rear;
	int num;

	head = (forward_list*)malloc(sizeof(forward_list));
	rear = head;

	while(scanf("%d",&num)==1 && num)
	{
		s = (forward_list*)malloc(sizeof(forward_list));

		s->data = num;
	    rear->next = s;
		rear = s;//表指针指向新的表尾
	}
	rear->next = NULL;

	return head;
}

单链表的查找操作

按值查找

代码语言：javascript
复制
void search_1(forward_list *s, int x)
{
	forward_list *p;
	p = s;
	while(p != NULL)
	{
		if(p->data == x)
		{
		    printf("\nthe value : %d is exist !\n",x);
		    return ;
		}
		p = p->next;
	}
	printf("\nthe value : %d is not fonud !\n",x);
}

按值查找（包含头结点）

代码语言：javascript
复制
void search_2(forward_list *s, int x)//带头节点
{
	forward_list *p;
	p = s->next;//emmmm
	while(p != NULL)
	{
		if(p->data == x)
		{
		    printf("\nthe value : %d is exist !\n",x);
		    return ;
		}
		p = p->next;
	}
	printf("\nthe value : %d is not fonud !\n",x);
}

单链表的删除操作

按给定结点的位置删除（带头结点）

代码语言：javascript
复制
void delete_1(forward_list *head,int i)        //删除第i个节点(单链表包含头节点)
{
	int j=0;
	forward_list *p,*q;
	p=head;
	j=0;
	while((p->next!=NULL)&&(j<i-1))
	{
		p=p->next;
		j++;
	}
	if(p->next!=NULL)
	{
		q=p->next;
		p->next=p->next->next;
		free(q);
	}
	else
		printf("illegal delete position,delete failed!");
}

按照指定值删除结点(不带头结点)

代码语言：javascript
复制
void forward_list_delete_1(forward_list *s,int x)//删除链表（不带头节点）中指定值的元素
{
    forward_list *p;
    forward_list *temp;//用来存放被删除元素的前一个结点
	p = s;
	if(x == p->data)
	    free(p);

	temp = p;
	p = p->next;
    while(p != NULL)
	{
	    if(p->data == x)
		{
            temp->next = p->next;
            free(p);
            return ;
		}
		temp = p;
		p = p->next;
	}
	printf("\n你要删除的元素 %d 不在表中\n",x);
	return ;
}

单链表的逆置

头插法逆置(带头结点)

代码语言：javascript
复制
void reverse_2(forward_list *head)//头插法逆置,带头节点
{
    forward_list *p,*q;
    p=head->next;
    head->next=NULL;
    while(p)
    {
        q=p;
        p=p->next;
        q->next=head->next;
        head->next=q;
    }
}

计算单链表的表长

* 带头结点 *

代码语言：javascript
复制
void list_length_2(forward_list *s)
{
	int count;
	forward_list *p=s->next;
	while(p)
	{
		count++;
		p = p->next;
	}
	printf("\nlist length: %d\n",count);
}

* 不带头结点 *

代码语言：javascript
复制
void list_length_1(forward_list *s)
{
	int count;
	forward_list *p=s;
	while(p)
	{
		count++;
		p = p->next;
	}
	printf("\nlist length: %d\n",count);
}

打印单链表

* 带头结点 *

代码语言：javascript
复制
void print_forward_list_2(forward_list *s)//打印含头节点的单链表
{
	forward_list *p;
	p = s->next;//因为含有头节点，head->data的数据域的数据未知
	while(p != NULL)
	{
		printf("%-3d",p->data);
		p = p->next;
	}
	return ;
}

* 不带头结点 *

代码语言：javascript
复制
void print_forward_list_1(forward_list *s)//打印单链表
{
	forward_list *p;
	p = s;
	while(p != NULL)
	{
		printf("%4d",p->data);
		p = p->next;
	}
	return ;
}

试试

源程序

代码语言：javascript
复制
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>

//定义单链表结点类型
typedef struct node{
	int data;                         //结点数据域
	struct node *next;                //结点指针域

}forward_list;

//尾插法建表
forward_list* creat_1()
{
    forward_list *head=NULL;//头指针，初始状态为空
	forward_list *rear=NULL;//尾指针，初始状态为空
	int num;
	forward_list *s;
	while(scanf("%d",&num) == 1 && num)//输入0结束
	{
		s = (forward_list*)malloc(sizeof(forward_list));

		s->data = num;
		if(head == NULL)//将新节点加入空表
	        head = s;
	    else            //原表非空，将新节点链接到表尾之后
	        rear->next = s;
		rear = s;//尾指针指向新的表尾
    }
    if(rear!= NULL)//对于非空表，将尾结点的下一个结点置空
	    rear->next = NULL;

	return head;
}

//尾插法建表,包含头结点
forward_list* creat_2()
{
	forward_list *s;
	forward_list *head, *rear;
	int num;

	head = (forward_list*)malloc(sizeof(forward_list));
	rear = head;

	while(scanf("%d",&num)==1 && num)
	{
		s = (forward_list*)malloc(sizeof(forward_list));

		s->data = num;
	    rear->next = s;
		rear = s;//表指针指向新的表尾
	}
	rear->next = NULL;

	return head;
}

forward_list* creat_3()    //头插法
{
    forward_list *head,*s;
	int num;
	head = NULL;//链表初始状态为空
	while(scanf("%d",&num) && num)
	{
		s = (forward_list*)malloc(sizeof(forward_list));
		s->data = num;

		s->next = head;

		head = s;//将新结点插入到表头
	}
	return head;
}

void search_1(forward_list *s, int x)
{
	forward_list *p;
	p = s;
	while(p != NULL)
	{
		if(p->data == x)
		{
		    printf("\nthe value : %d is exist !\n",x);
		    return ;
		}
		p = p->next;
	}
	printf("\nthe value : %d is not fonud !\n",x);
}

void search_2(forward_list *s, int x)//带头节点
{
	forward_list *p;
	p = s->next;//emmmm
	while(p != NULL)
	{
		if(p->data == x)
		{
		    printf("\nthe value : %d is exist !\n",x);
		    return ;
		}
		p = p->next;
	}
	printf("\nthe value : %d is not fonud !\n",x);
}

void reverse_1(forward_list *head)//头插法逆置单链表
{
	forward_list *p;
	forward_list *temp;

	p = head;//存好之前的单链表
	//printf("\n%d\n",p->data);
	head->next = NULL;
	while(p)
	{
	    temp = p;
	    //printf("1");
	    p = p->next;
	    temp->next = head->next;
		head = temp;
		printf("\n%d\n",head->data);
	}
}

void reverse_2(forward_list *head)//头插法逆置,带头节点
{
    forward_list *p,*q;
    p=head->next;
    head->next=NULL;
    while(p)
    {
        q=p;
        p=p->next;
        q->next=head->next;
        head->next=q;
    }
}


void forward_list_delete_1(forward_list *s,int x)//删除链表（不带头节点）中指定值的元素
{
    forward_list *p;
    forward_list *temp;//用来存放被删除元素的前一个结点
	p = s;
	if(x == p->data)
	    free(p);

	temp = p;
	p = p->next;
    while(p != NULL)
	{
	    if(p->data == x)
		{
            temp->next = p->next;
            free(p);
            return ;
		}
		temp = p;
		p = p->next;
	}
	printf("\n你要删除的元素 %d 不在表中\n",x);
	return ;
}

void delete_1(forward_list *head,int i)        //删除第i个节点(单链表包含头节点)
{
	int j=0;
	forward_list *p,*q;
	p=head;
	j=0;
	while((p->next!=NULL)&&(j<i-1))
	{
		p=p->next;
		j++;
	}
	if(p->next!=NULL)
	{
		q=p->next;
		p->next=p->next->next;
		free(q);
	}
	else
		printf("illegal delete position,delete failed!");
}




/*//不对
void list_delete(forward_list *s, int i)//删除单链表(不带头节点)的第i个结点
{
    int count=1;
	forward_list *p,*q;
	p=s;

	//将p移动到被删除结点的前一个结点

	while((p!=NULL)&&(count<i-1))
	{

		p=p->next;
		count++;
	}

	if(i == count)
	{
		q = p;
		p = p->next;
		free(q);
		return ;
	}
   	if(p->next!=NULL)
	{
		q=p->next;
		p->next=p->next->next;
		free(q);
	}
	else
		printf("illegal delete position,delete failed!");

}
*/
void list_length_1(forward_list *s)
{
	int count;
	forward_list *p=s;
	while(p)
	{
		count++;
		p = p->next;
	}
	printf("\nlist length: %d\n",count);
}

void list_length_2(forward_list *s)
{
	int count;
	forward_list *p=s->next;
	while(p)
	{
		count++;
		p = p->next;
	}
	printf("\nlist length: %d\n",count);
}

void print_forward_list_1(forward_list *s)//打印单链表
{
	forward_list *p;
	p = s;
	while(p != NULL)
	{
		printf("%4d",p->data);
		p = p->next;
	}
	return ;
}

void print_forward_list_2(forward_list *s)//打印含头节点的单链表
{
	forward_list *p;
	p = s->next;//因为含有头节点，head->data的数据域的数据未知
	while(p != NULL)
	{
		printf("%-3d",p->data);
		p = p->next;
	}
	return ;
}

int main()
{
	/*不带头结点的单链表*/
	printf("使用不带头结点的单链表:\n");
	forward_list *p;
	printf("尾插法建表:\n");
	p = creat_1();//尾插法建表
	print_forward_list_1(p);
	list_length_1(p);

	//查找是否存在值为6的结点
	search_1(p,6);
	printf("\n删了个5后，表变为\n");
	forward_list_delete_1(p,5);
	print_forward_list_1(p);

	//头插法建表
	forward_list *s;
	printf("\n头插法建表:\n");
	s = creat_3();
	print_forward_list_1(s);
	list_length_1(s);

	/*带头结点的单链表*/
	printf("\n\n使用带头结点的单链表:\n");
	forward_list *t;
	t = creat_2();
	print_forward_list_2(t);

	search_2(t,6);
	list_length_2(t);
	printf("\n逆置:\n");
	reverse_2(t);
	print_forward_list_2(t);
	list_length_2(t);

	return 0;
}

运行结果

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018年12月15日，如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 单链表操作
    • 单链表的创建
      • 头插法
      • 尾插法（不含头结点）
      • 尾插法（含头结点）
    • 单链表的查找操作
      • 按值查找
      • 按值查找（包含头结点）
    • 单链表的删除操作
      • 按给定结点的位置删除（带头结点）
      • 按照指定值删除结点(不带头结点)
    • 单链表的逆置
      • 头插法逆置(带头结点)
    • 计算单链表的表长
      • 打印单链表
      • 试试
        • 源程序
          • 运行结果
          领券

          腾讯云开发者

          扫码关注腾讯云开发者

          扫码关注腾讯云开发者

          领取腾讯云代金券

          热门产品

          热门推荐

          更多推荐

          Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

          深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

          腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

          Copyright © 2013 - 2024 Tencent Cloud.

          All Rights Reserved. 腾讯云 版权所有

          登录 后参与评论