单链表的学习

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

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

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

链表的定义

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

链表

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

结点

每个数据元素——数据域

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

单链表的定义

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

单链表结构

最后一个结点的指针域为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;
}