链表_牛客博客

链表是什么：

链表是一种由上一个元素的引用指向下一个元素的存储结构，链表通过指针来连接元素与元素。

链表与数组的区别：

（1）链表是链式的存储结构；

（2）数组是顺序的存储结构；

（3）链表通过指针来连接元素与元素，数组则是把所有元素按次序依次存储。

基本实现：

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int data;
	struct node *next;
};
int main()
{
	struct node *head,*p,*q,*t;
	int n,a,i;
	scanf("%d",&n);
	head=NULL;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		p=(struct node *)malloc(sizeof(struct node));
		p->data=a;
		p->next=NULL;
		if(head==NULL)
			head=p;
		else
			q->next=p;
		q=p;
	}
	t=head;
	while(t!=NULL)
	{
		printf("%d ",t->data);
		t=t->next; 
	}
	return 0;
}

输入：

1 2 3 4 5 6 7 9 10

输出：

1 2 3 4 5 6 7 9 10

向链表中插入一个数字：

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int data;
	struct node *next;
};
int main()
{
	struct node *head,*p,*q,*t;
	int n,a,i;
	scanf("%d",&n);
	head=NULL;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a);
		p=(struct node *)malloc(sizeof(struct node));
		p->data=a;
		p->next=NULL;
		if(head==NULL)
			head=p;
		else
			q->next=p;
		q=p;
	}
	scanf("%d",&a);
	
	t=head;
	while(t!=NULL)
	{
		if(t->next==NULL||t->next->data>a)
		{
			p=(struct node *)malloc(sizeof(struct node));
			p->data=a;
			p->next=t->next;
			t->next=p;
			break;
		 } 
		t=t->next;
	}
	t=head;
	while(t!=NULL)
	{
		printf("%d ",t->data);
		t=t->next; 
	}
	return 0;
}

输入：

1 2 3 4 5 6 7 9 10

输出：

1 2 3 4 5 6 7 8 9 10