单链表的学习

线性表的顺序存储结构的优缺点

优点;随机存取，存储空间利用率高

缺点：插入，删除效率低；必须按事先估计的最大元素个数分配连续的存储空间，难以临时扩大

链表的定义

采用链式存储结构的线性表称为链表

链表

单链表、循环链表、双向链表

结点

每个数据元素——数据域

直接后继的存储地址——指针域

单链表的定义

每个结点只包含一个指针域的链表

单链表结构

最后一个结点的指针域为null

First是头指针，指向链表中的第一个结点

链表中的第一个结点称为头结点

单链表类型定义

typedef struct node
{
	ElemType element;
	Struct node *link;
}node;
tepedef struct singleList
{
	struct node first;
	int n;
}singleList

单链表的插入

功能：

在给定元素ai之后插入值为X的元素

插入算法步骤为：

1、生成数据域为x的新结点，指针q指向新结点

2、从头结点开始，找到元素ai所在结点，指针p指向该结点

3、将新结点插入在ai所在结点之后

4、表长加1

Status Insert(SingleList *L,int i,ElemType x)
{
	Node *p,*q;
	int j;
	if(i<-1||i>L-n-1)
	return ERROR;
	p=L->first;
	for(j=0;j<i;j++)p=p->link;//从头结点开始查找ai 
	q=malloc(sizeof(Node));//生成新结点q 
	q->element=x;
	if(i>-1)
	{
		q->link=p->link;
		p->link=q;
	}//新结点插在单链表中间位置的情况 
	else
	{
		q->link=L->first;
		L->first=q;
	}//新结点插在a0之前，成为新的头结点 
	L->n++;//表长增加1 
	return OK;
}

单链表的删除运算

Status Delete(SingleList *L,int i)
{
	int j;
	Node *p,*q;
	if(!L->n)
	return ERROR;
	if(i<0||i>L->n-1)
	return ERROR;
	q=L->first;
	p=L->first;
	for(j=0;j<i-1;j++)q=q->link;//q指向ai-1 
	if(i==0)
	L->first=L->first->link//删除的是头结点
	else
	{
	p=q->link;//p指向ai 
	q->link=p->link;//从单链表中删除p所指向的结点 
	}
	free(p);//释放P所指结点的存储空间 
	L->n--;
	return OK;
}