2021-4-8 【链表】【】

何为链表

我们知道，一般用数组存放一组数据时，必须事先定义固定的长度（即元素的个数）。这在某些问题的解决中，并不是特别的适用。例如：记录不同的班级的学生数据时，由于各班人数不同，会出现开辟过大的数组导致内存浪费，开辟过小的数组导致数组元素不够用的情况。而链表可以根据需要动态开辟内存单元，是一种常见的重要数据结构。

链表如同铁链一样，一环扣一环，中间是不能断开的。打个通俗的比喻：幼儿园的老师带领小朋友出来散步，老师牵着第一个小朋友的手，第一个小朋友牵着第二个小朋友的手…这就是一个“链”，最后一个小朋友的手是空的。

老师即“头指针” 变量，以Head表示，它存放一个地址，链表中每一个元素称为“结点”，每个结点都应该包括两个部分：一为实际元素值，一为下一结点的地址。

最后一个元素不指向其他元素，它被称为“表尾”，以“NULL”表示，“NULL”在C++语言里指向“空指针”。

很显然，这种链表的数据结构，必须要用指针变量才能实现。

简单静态链表

下面的代码是一个简单的静态链表，它由3个学生的数据（学号，成绩）的结点组成。请考虑：（1）head的作用（2）p的作用

//简单静态链表
#include<iostream>
using namespace std;

struct student
{
   
	long num;
	float score;
	struct student *next;
};

int main()
{
   
	struct student a,b,c,*head,*p;
	a.num=34341; a.score=81.5;
	b.num=34341; b.score=81.5;
	c.num=34341; c.score=81.5;
	head=&a;
	a.next=&b;
	b.next=&c;
	c.next=NULL;
	p=head;
	do
	{
   
		cout<<p->num<<" "<<p->score<<endl;
		p=p->next;
	}while(p!=NULL);
	getchar();
}

处理动态链表的函数

1.malloc
函数原型为

void *malloc(unsigned int size);

作用是在内存的动态存储区中分配一个长度为size的连续空间。此函数返回的是一个指向分配域起始地址的指针，如果此函数未能成功地执行（如内存空间不足），则返回空指针（NULL）。

2.calloc
函数原型为

void *calloc(unsigned n,unsigned size);

作用是在内存的动态存储区中分配n个长度为size的连续空间。函数返回一个指向分配域起始地址的指针；如果分配不成功，则返回NULL。

3.free()
函数原型为

void free(void *p);

作用是释放由p指向的内存区，使这部分内存区能被其他变量使用。

动态链表的准备工作

一个完善的动态链表程序应该具有以下基本功能：建立链表，插入结点，删除结点，打印链表，释放链表等。扩展的动态链表程序还可能有获得链表长度，获得当前结点，查找结点位置，连续两个链表，比较两个链表等功能。下面将逐个实现其功能代码。

为了程序的易读性和可扩展性，有时需要在程序开头先进行预定义处理，请务必领会下面的代码用意，否则将影响对以后代码的理解

#include<stdlib.h>
#include<stdio.h>
typedef int ElemType;       //以 ElemType 代表 int 型数据
typedef struct List *link;  //以 link 代表链表指针
typedef struct List Lnode;  //以 Lnode 代表链表结点

struct List
{
   
	ElemType data;           //此处仅以一个整型变量为例
	struct List *next;
};

主函数的建立：下面的主函数只是一个简单调用各功能的示范例子，读者可自行修改和添加代码以完成更复杂的任务。请根据主函数的代码考虑各功能子函数的原型应如何建立。

int main()
{
   
	int l;
	link head1;
	link head2;
	head1=create(head1);                              //建立链表1
	head2=create(head2);                              //建立链表2 
	connect(head1,head2);                             //连接两个链表
	head1=insert(head1,888,5);                        //在位置5处插入元素888
	head1=del(head1,3);                               //删除一个结点
	display(head1);                                   //打印链表
	printf("\n lenth is %d\n",lenth(head1));          //打印链表长度
	printf("\n get is %d\n",get(head1,3));            //获得当前结点值
	printf("\n locate 12 is %d",lenth(head1,12));     //查找元素12所在的位置
	head=setnull(head);                               //释放链表
}

链表的建立

由主函数调用create（）函数的方式可知，该函数应该返回一个结点的指针，输入的参数也应该是一个结点指针，参考代码如下：

link create(link Head)
{
   
	ElemType newData;
	link NewPoint;
	//先创建一个结点
	Head=(link)malloc(sizeof(Lnoed));
	printf("please input number :\n");
	scanf("%d",&newData);
	Head->data=newData;   //结点赋值
	Head->next=NULL;     //结点指向空地址
	
	while(1)             //继续添加结点
	{
   
		NewPoint=(link)malloc(sizeof(Lnode));//开辟一个结点空间
		if(NewPoint==NULL){
   //如果开辟空间失败，则返回
			break;//此判断语句在某些类型的竞赛中用处不大，可忽略
		}
		printf("please input number : input '-1' means exit\n");
		scanf("%d",&newData);
		if(newData==-1){
         //输入-1则添加结点结束并返回head
			return Head;
		}
		NewPoint->data=newData;
		NewPoint->next=Head;
		Head=NewPoint;
	}
	return Head;
}

链表的显示

该子函数无返回值，输入参数为链表的头指针，请考虑：指针p的作用是什么？如果不用指针p，直接用Head这个指针会出现什么后果？

void display(link Head)
{
   
	link p;
	p=Head;
	if(p==NULL)
		printf("\nList is empty\n");
	else
		do
		{
   
			printf("%d",p->data);
			p=p->next;
		}while(p!=NULL);
}

结点的插入

link insert(link Head,ElemType x,int i)
{
   
	link NewPoint,p=Head;
	int j=1;
	NewPoint=(link)malloc(sizeof(Lnode));
	NewPoint->data=x;
	if(i==1)
	{
   
		NewPoint->next=Head;
		Head=NewPoint;
	}
	else
	{
   
		while(j<i-1&&p->next!=NULL)
		{
   
			p=p->NULL;
			j++;
		}
		if(j==i-1)
		{
   
			NewPoint->next=p->next;
			p->next=NewPoint;
		}
		else
			printf("insert is Failure,i is not right!!");
	}
	return Head;
}