电脑基础 · 2023年3月26日

9-数据结构-单链表头插法尾插法

问题:

单链表头插法与尾插法

思路:

  1. 头插法,类似于前面的在末位置前,插入元素。最后创建完为逆序;
  2. 尾插法,则是定一个尾指针r,每次接入新的结点s,随后r=s(即r往后移位)

详解:

头插法:

  1. 先初始化链表l——l=(linklist)malloc(sizeof(lnode));  l->next=NULL;
  2. 定义一个暂存结点用来一直插入元素,接进链中。——lnode*s。
  3. 随后定义插入数据x
  4. 进入循环,当输入x=9999时,循环结束
  5. 初始化s
  6. 随后进行后插操作,s->data=x;s->next=l->next;l->next=s;
  7. 之后再输入x
  8. 这样创建的链表就是逆序的链表了,可以1用来做逆序题目;

尾插法:

  1. 先初始化链表l——l=(linklist)malloc(sizeof(lnode));  l->next=NULL;
  2. 定义一个暂存结点用来一直插入元素,接进链中。——lnode*s。
  3. 定义一个尾指针r,用来表示链表的尾部
  4. 让尾指针r=l,就算真正接进l链表中了。
  5. 随后一样的操作输入x,进入循环
  6. 循环中,初始化s
  7. 给s数据域赋值——s->data=x;
  8. 让尾指针r指向s,连接起来——r->next=s;
  9. 随后移动r尾指针的位置到s结点中——r=s;达到位移目的。

代码如下:

头插法:

linklist tcreatlist(linklist &l,int &len)
{
	l=(linklist)malloc(sizeof(lnode));
	l->next=NULL;
	lnode *s;
	int x;
	printf("请输入所需添加的数据,输入9999结束输入\n");
	scanf("%d",&x);
	while(x!=9999)
	{
		len++;
		s=(lnode*)malloc(sizeof(lnode));
		s->data=x;
		s->next=l->next;
		l->next=s;
		scanf("%d",&x);
	}
	return l;
}

尾插法:

linklist wcreatlist(linklist &l,int &len)//尾插法
{
	l=(linklist)malloc(sizeof(lnode));
	l->next=NULL;
	lnode *s;
	lnode *r=l;
	int x;
	printf("请输入所需添加的数据\n");
	scanf("%d",&x);
	while(x!=9999)
	{	len++;//计算链表长度
		s=(lnode*)malloc(sizeof(lnode));
		s->data=x;
		r->next=s;
		r=s;
		scanf("%d",&x);
	}
	r->next=NULL;
	return l;
}