数据结构—链表（c语言）

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

我们可以将链表与数组进行类比来学习，链表与数组具有相同的逻辑结构。
它们之间也有区别，我们学过数组都知道，数组各元素的存储空间是连续的、固定的，数组元素个数在我们定义完成后是不可改变的。而链表中的元素个数是可变化的，元素的存储空间是动态分配的，逻辑上相邻的节点物理存储空间上不一定相邻，而数组则是逻辑上相邻则物理存储空间上也相邻。

链表是采用动态存储分配的一种重要的数据结构。链表的基本操作有增删改查等。在进行链表的基本操作之前我们要学习两个处理动态链表所需要的函数。
（1）分配内存空间函数 malloc
函数调用的一般形式为：（类型说明符 * ）malloc （size）

malloc函数要求系统在内存中分配一块存储空间，这个存储空间是长度为size字节的连续区域，函数的返回值为该区域的首地址。“类型说明符”，表示将该区域用于何种数据类型。
（2）释放内存空间函数 free
函数调用的一般形式为：free（p）
释放p所指向的一块内存空间，p是一个任意类型的指针变量，它指向被释放区域的首地址，被释放的区域应该是由malloc所分配的区域。
一个好的存储空间动态分配程序应该包括申请内存空间、使用内存空间、释放内存空间三个步骤。
下面就是链表的增删查找基本操作。

#include
#include
struct node
{
	int num,score;
	struct node * next;
};
void find(struct node * head)
	struct node *p;
	int x;
	printf("输入要查找的学号:n");
	scanf("%d",&x);
	p=head;
	while(p!=NULL && p->num!=x)
		p=p->next;
	if(p)
		printf("num=%dtscore=%d",p->num,p->score);
	else
		printf("%d没有找到！n");
}
void main()
{
	struct node * creat (struct node * head,int n);
	void print(struct node * head);
	struct node *dele(struct node * head);
	struct node * head=NULL;
	struct node *insert(struct node * head);
	head=creat(head,5);
    find(head);
    dele(head);
	insert(head);
	print(head);
}
struct node * creat(struct node * head,int n)
{
	struct node * p, * q;
	int i;
	for (i=1;i<=n;i++)
	{
		q=(struct node * )malloc(sizeof(struct node));
		printf("输入第%d个num,score:n",i);
		scanf("%d,%d",&q->num,&q->score);
		q->next=NULL;
		if(head==NULL)
		   head=q;
		else
			p->next=q;
		p=q;
	}
	return head;
}
void print(struct node * head)
{
	struct node * p=head;
	printf("numtscoren");
	while(p!=NULL)
	{
		printf("%dt%dn",p->num,p->score);
		p=p->next;
	}
}
struct node *dele(struct node *head)
{
	int x;
	struct node *p,*q;
	p=head;
	printf("输入你要删除的学号:n");
	scanf("%d",&x);
	while(p!=NULL && p->num!=x)
	{
		q=p;
		p=p->next;
	}
	if(p==NULL)
	   printf("没有找到该学号n");
	else if(p==head)
		head=p->next;
	else
		q->next=p->next;
	free(p);
	return(head);
}
struct node * insert(struct node * head)
{
	struct node *q,*p,*p1;
	q=(struct node * )malloc(sizeof(struct node));
	printf("输入加入的学号、成绩:n");
	scanf("%d,%d",&q->num,&q->score);
	if(head==NULL)
	{
		q->next=NULL;
		head=q;
		return(head);
	}
	if(head->num > q->num)
	{
		q->next=head;
		head=q;
		return head;
	}
	p=head;
	p1=head->next;
	while(p1!=NULL && p1->num < q->num)
	{
		p=p1;
		p1=p1->next;
	}
	q->next=p1;
	p->next=q;
	return(head);
}