[数据结构与算法]单链表的基本功能（增 ，删，改，查，求长度，排序）

链表是一种常见的数据结构。它与常见的数组是不同的，使用数组时先要指定数组包含元素的个数，即为数组的长度，但是如果向这个数组中加入的元素超过了数组的大小时，便不能将内容全部保存。
??链表这种存储方式，其元素个数是不受限定的，当进行添加元素的时候存储的个数就会随之改变。

首先进行链表的初始化

struct Node
{
	int data;
	struct Node *next;
};

若进行学生成绩的链表操作，可以使用结构体嵌套功能

struct student
{
	char name[20];
	int num;
	int Chi;    //语文
	int math;
	int English;
};

//链表初始化 
struct Node
{
	struct student data;     //数据域 
	struct Node *next;     //指针域 
};

接下来创建链表（创建头节点）

struct Node *createlist()
{
	struct Node *headNode = (struct Node*)malloc(sizeof(struct Node));   //变量使用前的的初始化 
	headNode->next = NULL;
	return headNode;
};

创建完头结点后，接下来进行插入操作

第一种方法：头插法?

 
void  insertNodeByHead(struct Node*headNode,struct student data)/*头插法*/
{
	//创建插入的节点 
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); 
	newNode->data = data;
	newNode->next = headNode->next;
	headNode->next = newNode;
}

第二种：尾插法? ?和头插法的区别就是首先需要遍历整个链表到最后一个，剩下做法和头插法一样

//尾插法 
void insertNodeByEnd(struct Node *headNode,struct student data)
{
	struct Node *temp =headNode;    //地址一样 
	while(temp->next )
	{
		temp = temp->next ;
	}
	if(temp)
	{
		
		struct Node *s = (struct Node*)malloc(sizeof(struct Node));
		//s->next = NULL;	
		temp->next = s;
		temp = s;
		strcpy(s->data.name,data.name);
		s->data.num  = data.num ;
		s->data.math  = data.math ;
		temp->next = NULL;
	}
}	

第三种方法：随机位置插入，相较于之前的两种做法，第三种做法更为灵活，可以自由选择插入的位置

?
//任意位置插入
void inserteveryNode(struct Node*headNode,int p/*第几个位置插入*/,struct student data)
{
	int i;
	struct Node *w = headNode;
	struct Node *s = (struct Node*)malloc(sizeof(struct Node));
	for(i=0;i<p;i++)
	{
	     w = w->next ;
		 if(w == NULL)
	   {
		printf("error");
		return;
	   }
	}
		strcpy(s->data.name,data.name);
		s->data.num = data.num;
		s->data.Chi = data.Chi;      //Chi为语文
		s->data.math = data.math;
		s->data.English = data.English;
		
	    s->next = w->next;
		w->next = s;
	
}

?

然后进行删除操作
?

//删除操作 
void deleteNodeByAppion(struct Node*headNode ,int num)
{
    struct Node*posNode = headNode->next;
    struct Node*posNodefront = headNode;
    if(posNode==NULL)
	   printf("无法删除链表为空\n");
	else
	{
		while(posNode->data.num != num)
		{
			posNodefront = posNode ;
			posNode = posNodefront->next;
		    if(posNode==NULL)
		    {
			     printf("没有找到相关信息，无法删除\n");
			     return;
		    }
		}
		posNodefront->next = posNode->next;
		free(posNode); 
	 }
}

然后进行修改操作

该段代码可以进行多样的功能，自由的选择想要修改的数据

//修改操作 
struct Node *gai(struct Node*headNode,int count,char w)
{
	//struct student data;
	int Chi,English,math,num;
	char name[20]; 
	struct Node *p = headNode; 
	int j;
	for(j=0;j<count;j++)
	{
		p = p->next ;           
	}
	if(w == 'A')
	{
		printf("请输入修改后的学生姓名: ");
		scanf("%s",name);
		strcpy(p->data.name,name);
	}
	if(w == 'B')
	{
		printf("请输入修改后的学生学号: ");
		scanf("%d",&num);
		p->data.num = num;
	}
	if(w == 'C')
	{
		printf("请输入修改后的学生语文成绩: ");
		scanf("%d",&Chi);
		p->data.Chi = Chi;
	}
	if(w == 'D')
	{
		printf("请输入修改后的学生数学成绩: ");
		scanf("%d",&math);
		p->data.math = math;
	}
	if(w == 'E')
	{
		printf("请输入修改后的学生英语成绩: ");
		scanf("%d",&English); 
		p->data.English = English;
	}
	return p;
}
 

下面为简化版代码(该段代码对学号（num）进行修改)

大家也可以自由的更换形参从而调整更改的数据

//修改操作 
struct Node *gai(struct Node*headNode,int count,int num)
{
	//struct student data;
	int Chi,English,math,num;
	char name[20]; 
	struct Node *p = headNode; 
	int j;
	for(j=0;j<count;j++)
	{
		p = p->next ;           
	}
	 p->data.num = num;
	return p;
}
 

最后进行查找操作

struct Node *cha2(struct Node*headNode,int i)
{
	struct Node *k = headNode;
	int j;
	for(j=0;j<i;j++)
	{
		k = k->next;
	}
	return k;
}

输入一个想要查找的序号（i）借助循环语句从而进行查找，最后返回整个结点所保存的数据

求链表的长度

//求长度 
int len(struct Node *headNode)
{
	int len = 0;
	struct Node *p = headNode->next;
	while(p)
	{  
		p=p->next;
		len++;
	}
	return len;
}

最后进行链表的排序

其实仔细观察链表的排序和正常的数组排序是一模一样的，可以采用类比的思想进行操作

下面介绍排序方法：

1.冒泡排序

//链表冒泡排序 
void maopao(struct Node *headNode)
{ 
    char name1[20];
	int math_; 
	struct Node *p ;
	struct Node *q ;
	struct Node *t ;
	for(p = headNode;p->next != NULL;p = p->next)
	{
		for(q = headNode;q->next != NULL;q = q->next )
		{
			if(q->data.num < q->next->data.num)
			 {
			 	  int temp = q->data.num;
			 	  q->data.num = q->next->data.num;
			 	  q->next->data.num = temp;
			 	
			 	  strcpy(name1,q->data.name);
	 	 	   	  strcpy(q->data.name,q->next->data.name);
	 	 	   	  strcpy(q->next->data.name,name1);
	 	 	   	  
	 	 	   	  math_ = q->data.math;
	 	 	   	  q->data.math = q->next->data.math;
	 	 	   	  q->next->data.math = math_;
			 }
		}
	}
}

2.选择排序

void maopao(struct Node *headNode)
{
	struct Node *p, *s;
	char name1[20];
	int math_;
	for(s = headNode->next;s!=NULL;s = s->next)
	 {	     
	 	 for(p = s->next;p!=NULL;p = p->next)
	 	 {
	 	 	if(p->data.num > s->data.num)
	 	 	     {
	 	 	   	  int temp = p->data.num;
	 	 	   	  p->data.num = s->data.num;
	 	 	   	  s->data.num = temp;
	 	 	   	  
	 	 	   	  strcpy(name1,p->data.name);
	 	 	   	  strcpy(p->data.name,s->data.name);
	 	 	   	  strcpy(s->data.name,name1);
	 	 	   	  
	 	 	   	  math_ = p->data.math ;
	 	 	   	  p->data.math = s->data.math;
	 	 	   	  s->data.math = math_;
	 	 	   	  
				 }
		  }
	 }
}

最后进行链表的遍历

//遍历链表 
void printfList(struct Node*headNode){
	struct Node*pMove = headNode->next;
	printf("name\tnum\tChi\tmath\tEnglish\n");
	while(pMove)
	{
		printf("%s\t%d\t%d\t%d\t%d\n",pMove->data.name,pMove->data.num,pMove->data.Chi,pMove->data.math,pMove->data.English);
		pMove = pMove->next;
	}
	printf("\n");
}

完整的代码如下：

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h> 
#include<string.h>
int count = 1;

struct student
{
	char name[20];
	int num;
	int Chi;
	int math;
	int English;
};

//链表初始化 
struct Node
{
	struct student data;     //数据域 
	struct Node *next;     //指针域 
};

//创建头链表 
struct Node *createlist()
{
	struct Node *headNode = (struct Node*)malloc(sizeof(struct Node));   //变量使用前的的初始化 
	headNode->next = NULL;
	return headNode;
};

//创建头结点 
/*struct Node*createNode(struct student data){
	struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
	newNode->data = data;
	newNode->next = NULL;
	return newNode; 
};*/

//遍历链表 
void printfList(struct Node*headNode){
	struct Node*pMove = headNode->next;
	printf("name\tnum\tChi\tmath\tEnglish\n");
	while(pMove)
	{
		printf("%s\t%d\t%d\t%d\t%d\n",pMove->data.name,pMove->data.num,pMove->data.Chi,pMove->data.math,pMove->data.English);
		pMove = pMove->next;
	}
	printf("\n");
}

//头插法 
void  insertNodeByHead(struct Node*headNode,struct student data)/*头插法*/
{
	//创建插入的节点 
	struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
	/*newNode->data.English = data.English;
	newNode->data.math = data.math;
	newNode->data.Chi = data.Chi;
	newNode->data.num = data.num;
	strcpy(newNode->data.name,data.name);*/
	newNode->data = data;
	newNode->next = headNode->next;
	headNode->next = newNode;
}

//尾插法 
/*void insertNodeByEnd(struct Node *headNode,struct student data)
{
	struct Node *temp =headNode;//地址一样 
	while(temp->next )
	{
		temp = temp->next ;
	}
	if(temp)
	{
		
		struct Node *s = (struct Node*)malloc(sizeof(struct Node));
		//s->next = NULL;	
		temp->next = s;
		temp = s;
		strcpy(s->data.name,data.name);
		s->data.num  = data.num ;
		s->data.math  = data.math ;
		temp->next = NULL;
	}
}*/	

//任意位置插入
/*void inserteveryNode(struct Node*headNode,int p/*第几个位置插入*//*,struct student data)*/
/*{
	int i;
	struct Node *w = headNode;
	struct Node *s = (struct Node*)malloc(sizeof(struct Node));
	for(i=0;i<p;i++)
	{
	     w = w->next ;
		 if(w == NULL)
	   {
		printf("error");
		return;
	   }
	}
		strcpy(s->data.name,data.name);
		s->data.num = data.num;
		s->data.Chi = data.Chi;
		s->data.math = data.math;
		s->data.English = data.English;
		
	    s->next = w->next;
		w->next = s;
	
}*/

//删除操作 
void deleteNodeByAppion(struct Node*headNode ,int num){
    struct Node*posNode = headNode->next;
    struct Node*posNodefront = headNode;
    if(posNode==NULL)
	   printf("无法删除链表为空\n");
	else
	{
		while(posNode->data.num != num)
		{
			posNodefront = posNode ;
			posNode = posNodefront->next;
		    if(posNode==NULL)
		    {
			     printf("没有找到相关信息，无法删除\n");
			     return;
		    }
		}
		posNodefront->next = posNode->next;
		free(posNode); 
	 }
}

//查找操作 
/*void cha(struct Node *headNode,int num)
{
//	printf("dasdasdasdas");
       //注意小野 （野指针）
	struct Node*p = headNode->next;
	int count = 0;
	while(p)
	{
		count++;
		if(p->data.num == num)
		{
			printf("%d %s %d %d",count,p->data.name ,p->data.num ,p->data.math );
			return;
		}
		 p = p->next;
	} 
    printf("未找到");
    return;
}*/
//查的第二种方法 
struct Node *cha2(struct Node*headNode,int i)
{
	struct Node *k = headNode;
	int j;
	for(j=0;j<i;j++)
	{
		k = k->next;
	}
	return k;
}
//修改操作 
struct Node *gai(struct Node*headNode,int count,char w)
{
	//struct student data;
	int Chi,English,math,num;
	char name[20]; 
	struct Node *p = headNode; 
	int j;
	for(j=0;j<count;j++)
	{
		p = p->next ;           
	}
	if(w == 'A')
	{
		printf("请输入修改后的学生姓名: ");
		scanf("%s",name);
		strcpy(p->data.name,name);
	}
	if(w == 'B')
	{
		printf("请输入修改后的学生学号: ");
		scanf("%d",&num);
		p->data.num = num;
	}
	if(w == 'C')
	{
		printf("请输入修改后的学生语文成绩: ");
		scanf("%d",&Chi);
		p->data.Chi = Chi;
	}
	if(w == 'D')
	{
		printf("请输入修改后的学生数学成绩: ");
		scanf("%d",&math);
		p->data.math = math;
	}
	if(w == 'E')
	{
		printf("请输入修改后的学生英语成绩: ");
		scanf("%d",&English); 
		p->data.English = English;
	}
	return p;
}

//求长度 
int len(struct Node *headNode)
{
	int len = 0;
	struct Node *p = headNode->next;
	while(p)
	{  
		p=p->next;
		len++;
	}
	return len;
}

//链表排序 1.0
/*void maopao(struct Node *headNode)
{
	struct Node *p, *s ;
	char name1[10];
	int math_;
	for(s = headNode->next;s!=NULL;s = s->next)
	 {	     
	 	 for(p = s->next;p!=NULL;p = p->next)
	 	 {
	 	 	if(p->data.num > s->data.num)
	 	 	     {
	 	 	   	  int temp = p->data.num;
	 	 	   	  p->data.num = s->data.num;
	 	 	   	  s->data.num = temp;
	 	 	   	  
	 	 	   	  strcpy(name1,p->data.name);
	 	 	   	  strcpy(p->data.name,s->data.name);
	 	 	   	  strcpy(s->data.name,name1);
	 	 	   	  
	 	 	   	  math_ = p->data.math ;
	 	 	   	  p->data.math = s->data.math;
	 	 	   	  s->data.math = math_;
	 	 	   	  
				 }
		  }
	 }
}*/

//链表冒泡排序 
void maopao(struct Node *headNode)
{ 
    char name1[20];
	int math_; 
	struct Node *p ;
	struct Node *q ;
	struct Node *t ;
	for(p = headNode;p->next != NULL;p = p->next)
	{
		for(q = headNode;q->next != NULL;q = q->next )
		{
			if(q->data.num < q->next->data.num)
			 {
			 	  int temp = q->data.num;
			 	  q->data.num = q->next->data.num;
			 	  q->next->data.num = temp;
			 	
			 	  strcpy(name1,q->data.name);
	 	 	   	  strcpy(q->data.name,q->next->data.name);
	 	 	   	  strcpy(q->next->data.name,name1);
	 	 	   	  
	 	 	   	  math_ = q->data.math;
	 	 	   	  q->data.math = q->next->data.math;
	 	 	   	  q->next->data.math = math_;
			 }
		}
	}
}

int main()
{
	struct Node* List = createlist();
	struct student info;
	while(1)
	{
		printf("请输入学生的姓名 学号 语文成绩 数学成绩 英语成绩: \n");
		scanf("%s",info.name);
		scanf("%d %d %d %d",&info.num ,&info.Chi ,&info.math,&info.English);
		insertNodeByHead(List,info);
		//insertNodeByEnd(List,info);
		printf("continue(Y/N)?\n");
		getchar(); 
		char choice ;
		//setbuf(stdin,NULL);    //清除缓存区    //缓冲区与文件流的问题 //
		scanf("%c",&choice);
		if(choice == 'N'|| choice == 'n')
		{
			//printf("退出输出"); 
			break;
		}
	}	
	    printfList(List);
	    printf("排序一下 \n");
		maopao(List);
		printfList(List);
	    /*printf("请输入学生的姓名 学号 数学成绩: \n");
		scanf("%s %d %d",info.name ,&info.num ,&info.math );
	    int l;              //第几组的序号
		printf("请选择在第几个位置插入数据");
		scanf("%d",&l);
	    inserteveryNode(List,l,info); 
	    printfList(List);*/
	printf("请输入想要删除的学生学号：\n");
	int num;
	scanf("%d",&num );
	deleteNodeByAppion(List,num ); 
	printfList(List);
	
	/*printf("请输入查找的数据： \n");
	 int math ;
    scanf("%d",&math );
	cha(List, math);               cha 
	printf("\n");*/
	
	int people;
	printf("您想要查找哪一位学生的成绩");
	scanf("%d",&people);
	struct Node *m = cha2(List,people);             /*  cha2 */
	printf("该学生的姓名 学号 语文成绩 数学成绩 英语成绩: \n");
	printf("%s\t%d\t%d\t%d\t%d\n",m->data.name ,m->data.num ,m->data.Chi,m->data.math,m->data.English);
	printf("\n");
	
	int lenss;
	printf("请选择更改哪一位学生的相关信息：\n");
	scanf("%d",&lenss);
	printf("请选择你要更改的信息 ：\n");
	printf("A.姓名 B.学号 C.语文成绩 D.数学成绩 E.英语成绩 \n");
	//setbuf(stdin,NULL);          //清楚缓存区不可以随便使用 
	getchar();    
	char t = getchar();
	struct Node* nums = gai(List,lenss,t);
	printf("\n");
	printf("该学生更改后的信息 ：\n");
	//setbuf(stdin,NULL);
	printf("%s %d %d %d %d\n",nums->data.name ,nums->data.num ,nums->data.Chi,nums->data.math,nums->data.English );	
	int lens = len(List);
	printf("该单链表的长度为：%d\n",lens);
    system("pause");
    return 0;
}