单链表的定义
线性表的链式存储又称单链表，通过一组任意的存储单元来存储线性表中的数据元素。
L = (,
,
,...,
)
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
判断单链表是否为空
1、head为null时，单链表为空；
2、head->next为null时，单链表为空；
使用头结点的优点：
1、链表的第一个位置和其他位置的操作统一
2、空表和非空表的操作统一
单链表的基本操作
/**
* 头插法插入方式
*/
LinkList List_HeadInsert(LinkList &L){
LNode *s;int x;
L=(LinkList)malloc(sizeof(LNode));
L->next=null;
scanf("%d",&x);
while(x!=9999){
s=(LNode*)mallooc(sizeof(LNode));
s->date=x;
s->next=L->next;
L->next=s;
scanf("%d",&s);
}
return L;
}
/**
* 尾插法插入方式
*/
LinkList List_TailInsert(LinkList &L){
int x;
L=(LinkList)malloc(sizeof(LNode));
LNode *s;*r=L;
scanf("%d",&x);
while(x!=9999){
s=(LNode*)mallooc(sizeof(LNode));
s->date=x;
r->next=L->s;
r=s;
scanf("%d",&s);
}
return L;
}
/**
* 按照序号查找
*/
LNode *GetElem(LinkList L,Int i){
int j = 1;
LNode *p = L->next;
if(i==0){
return L;
}
if(i<1){
return NULL;
}
while(p&&j<i){
p=p->next;
j++;
}
return p;
}
/**
* 按值查找
*/
LNode *LocateElem(LinkList L,ElemType e){
LNode *p = L->next;
while(p!==null&&p->data!=e){
p=p->next;
}
return p;
}
顺序存储和链式存储区的差异性
顺序存储：
1、无论静态分配还是非静态分配都需要预先分配合适的内存空间
2、静态分配时预分配空间太大会造成浪费，太小会造成溢出
3、动态分配时虽不会溢出但是扩充需要大量移动元素，操作效率低
链式存储：
在需要时分配结点空间即可，高效方便，但指针要使用额外空间
怎么选择线性表的存储结构
三个常用的操作
本章总览
