链表的学习

在数据结构中有一种结构叫做线性表，线性表是储存一个线性数据的表格，本文就简要的介绍一下线性表的构成。

---

 

一、线性表的定义

定义：由同种类型数据元素构成的有序数列的线性结构

长度、表头、表尾

List

线性表的形式有两种：一种是数组构成的表，另一种是链表。

所谓数组形成的表就是一个数组，如下定义所示

typedef struct{	ElementType Data[];	int last;}List

　　

从上面可以看出一个线性表类型要包括一组数据和数据的最末尾。

这样有一个弊端，就是在对线性表插入时需要对其后面的所有元素挪动位置。

故我们采取另一种方式，也就是链表的结构

结构如下：

typedef struct Node{	ElementType Data;	struct Node *Next;}List;

　　

二、链表基本功能实现

（1）求表的长度

void Length(List *Ptrl){	List *p = Ptrl;	int j =0;//记录数量	while(p)//结束符号为NULL	{		p = p->Next;		j++;	}	return j;}

　　

（2）查找

按序号查找

List *FindKth(int K,List *Ptrl){	List *p = Ptrl;	int i = 1;	while(p != NULL && i 
     
      Next;		i++;	}	if(i == K)		return p;	else 		return NULL;	}
     

　　

按值查找

List *Find(Element Data,List *Ptrl){	List *p = Ptrl;	while(p != NULL && p->Data != Data)	{		p = p->Next;	}//找不到就是NULL	return p;}

　　

（3）插入元素

在链表中某个位置插入某个元素

所以入口参数为元素内容、位置、链表。

出口参数为新的链表。

List *Insert(ElementType X,int i,List* Ptrl){	List *p,*s;//新链表和旧链表	//首先判断参数是否有效	p = FindKth(i-1,Ptrl);//获取i-1号节点	if(p == NULL)	{		printf("参数错误");		return NULL;	}	else	{		//如果在表头插入元素		if(i == 1){//重新申请一片空间			s = (List*)malloc(sizeof(List));			s->Data = X;			s->Next = Ptrl;			return Ptrl;		}		else{			s = (List*)malloc(sizeof(List));			s->Data = X;//交接工作  新节点插入			s->Next = p->Next;			p->Next = s;			return Ptrl;		}	}}

　　

（4）删除元素

List* Delete(int i, List *PtrL)

1、先找到链表的第 i-1 个结点，用p 指向；

2、再用指针s 指向要被删除的结点：P的下一个节点

3、然后修改指针，删除s 所指结点;

4、最后释放s 所指结点的空间。

List* Delete(int i, List *PtrL){	List *p,*s;//新旧链表	//判断数据有效性	p = FindKth(i-1,Ptrl);//获取i-1号节点	if(p == NULL)	{		printf("参数错误");	}	else{		if(i == 1){//在头部插入元素			p = p->next;			free(s);			return Ptrl;		}		else{			s = p->Next;			p->Next = s->Next;			free(s);			return Ptrl;		}	}}

　　

注意：在进行指针操作时要记住判断是否为空；