[数据结构与算法]C语言链表

链表

链表定义

链表是一种常用的数据结构，链表类似于数组可以连续存储数据，但链表在物理地址上不是连续的，它是通过链表的指针域来存储不同节点的地址，将数据存储在数据域中（头节点是没有数据域的），而链表的最后一个节点的的指针域存放的指针存放的是NULL空地址。通链表可以方便的对我们的数据进行查找，遍历，删除，修改等等操作。

为什么要使用链表

为什么要使用链表？前面说了链表是类似与数组这种结构类型。链表解决了数组存在的许多问题，例如：数组的长度无法改变，数组元素替换删除复杂，无法存储多种类型的元素。

创建链表

使用头插法动态创建链表

#include <stdio.h>
#include <stdlib.h>

struct Student
{
   int data;//数据域
   struct Student *next;//指针用来访问下一个节点
};


struct Student *create(struct Student *head,int n){
	int i = 0;
	struct Student *p;//定义头节点，普通节点，尾部节点；

	for(i = 0;i < n;i++)
		{
		p = (struct Student *)malloc(sizeof(struct Student));
		scanf("%d", &(p->data));
		if(head == NULL)//判断是否为空
		   {
           head = p;
           }
        else
           {
           p->next = head;
           head = p;
           }
	    }
	    return head;
}
int main()
{
   struct Student *head;
   printf("please input the number of nodes\n");
   int n;
   scanf("%d",&n);
   head = create(head,n);
   return 0;
}

遍历链表

void printLink(struct Student *head)
{
   struct Student *point;//设置一个有效节点
   point = head;
   while(point != NULL)
   	{
   	   printf("%d ",point->data);
	   point = point->next;
   	}
   putchar('\n');

}

int main()
{
   struct Student *head = NULL;
   printf("please input the number of nodes\n");
   int n;
   scanf("%d",&n);
   head = create(head,n);
   printLink(head);
   return 0;
}

在指定元素后插入节点

struct Student *insert(struct Student *head,int data,struct Student *new)
{
   struct Student *p = head;

   while(p != NULL)
   	{
   	   if(p->data == data)
   	   	{
   	   	   new->next = p->next;//在元素后面插入元素
		   p->next = new;
		   return head;
   	   	}
	   p = p->next;
   	}
   return head;
}
int main()
{
   struct Student *head = NULL;
   printf("please input the number of nodes\n");
   int n;
   scanf("%d",&n);
   head = create(head,n);

   struct Student new = {100,NULL};
   head = insert(head,1,&new);//在元素‘1’的后面插入新元素	
   printLink(head);
   return 0;
}

删除指定节点

struct Student *deleteLink(struct Student *head,int data)
{
   struct Student *p = head;
   if(p->data == data)//删除第一个节点
   	{
   	   head = head->next;
   	}
   while(p->next != NULL)
   	{
   	   if(p->next->data == data)
   	   	{
   	   	   p->next =p->next->next;//使节点指向被删除的节点的下一个
		   return head;
   	   	}
	   p = p->next;
   	}
   return head;
}

int main()
{
   struct Student *head = NULL;
   printf("please input the number of nodes\n");
   int n;
   scanf("%d",&n);
   head = create(head,n);
   head = deleteLink(head,2);
   printLink(head);
   return 0;
}