单向链表

• child::单向链表常用操作

适用范围:

优缺点:

优点:

1. 可以快速删除、插入、追加节点

缺点:

1. 查找困难
2. 比顺序表占用多一点内存

单向链表结构梗概:

1. 若干个结点（NODE）, 具有数据域和地址域
   1. 特殊的结点: 一个头结点
      1. 其数据域一般用来存储链表的元数据
      2. 地址域指向第一个中间结点 (没有则指向空)
   2. 特殊的结点: 一个尾节点（TAIL）(一般很少用到)
      1. 数据域为空
      2. 地址域为空
   3. 普通的结点: 中间结点
      1. 数据域存放该结点所代表的数据
      2. 地址域指向下一个中间结点(没有则指向空)
2. 一个指向链表头结点的头指针（head）

单向链表在c语言中的实现:

定义单向链表的节点类型

typedef struct Node{
元素类型 data;    //数据域
struct Node * next; //地址域
} Node, * LinkList;  //Node为该结构体类型的名字 , LinkList为该结构体指针类型的名字

C语言中链表的惯用标识符：

1. Node用来定义节点
2. LinkList用来定义节点指针
3. L表示头指针

作用：

1. 创建LInkList结构体指针类型的作用：
   1. 方便把地址做强制类型转换为该节点的类型
   2. 方便定义指向该节点的指针

对链表操作的实现：

初始化链表(建立空链表)

InitList(LinkList *L){ //传入头指针的地址
*L = (LinkList)calloc(1,sizeof(Node));  //把传入的地址作为头指针, 创建头结点, 并让头指针指向头节点
(*L) -> next = NULL; //把头结点指向空
}

作用:

1. 传入Node类型的地址, 返回一个空链表

头插法建表

梗概:

1. 把新的节点都插到头结点之后

性质:

1. 逻辑顺序与输入顺序相反
2. 头结点处于最后一个

c实现:

int CreateFromHead(LinkList L){
	Node *s;//插入的节点地址
	ElemType c;
	while ((c=getchar())!='$'){//'$'为结束符
		s = (Node*)calloc(1,sizeof(Node));
		if (s == NULL) return ERROR;
		s->data = c; //给数据域赋值
		s->next = L->next;//先把新节点连上
		L->next = s;//把前驱断开，连上新节点
	}
	return OK;
}

尾插法

梗概:

1. 把新节点插入到尾节点处
2. 把最后一个节点的地址域设为空

按序号查找

/*找第i个节点,返回其地址或空*/
Node *Get(LinkList L, int i){
	Node *p;//p为节点探针
	int j;//j为计数器
	if (i<1) return NULL;//处理不合理的节点
	p=L->next; j=0; //先测探第一个
	while (p!=NULL){ //分析探测存不存在
		j++; //探测后计数
		if(i==j)break;//计数后够了就停
		p = p->next; //探测下一个
	}
	return p;//保证返回找不到NULL
}

按值查找

/*查找节点值为key的第一个节点,返回其地址或空*/
Node *Locate(LinkList L, ElemType key){
	Node *p;//探针
	p=L->next;//先探测第一个
	while(p!=NULL){//分析探测结果存不存在
		if(p->data==key) break;//找到就停下
		p=p->next;//继续探测下一个
	}
	return p; //保证找不到返回空
}

求链表长度

/*求长度,返回长度*/
int ListLength(LinkList L){
	Node *p;//探针
	int j=0;//计数
	p=L->next;//探测第一个
	while (p!=NULL){//分析探测结果存不存在
		j++;//结果并入计数
		p=p->next;//探测下一个
	}
	return j;
}

单链表插入操作

梗概:

1. 插在头结点后的任意位置

考虑情况:

1. 空链表
2. 中间位置
3. 最后一个节点的后面

c语言实现:

/*在单链表L中第i个节点之前插入值为e的新节点*/
int InsList(LinkList L, int i, ElemType e){
	Node *pre, *s;//pre为直接前驱, *s为插入节点
	if (i<1) return ERROR;//处理前驱越界
	pre=((i==1)?L:Get(L,i-1));//找前驱
	if (pre==NULL){//处理前驱不存在
		printf("插入位置不合理!");
		return ERROR;
	}
	s =(Node*)calloc(1,sizeof(Node));
	s->data=e;
	s->next =pre->next;//先接上后继
	pre->next=s;//后断开，接上前驱
	return OK;
}

删除操作:

梗概:

1. 删除除头结点的任意节点

考虑:

1. 第一个节点
2. 中间位置
3. 最后一个节点
   1. 最后一个节点指向空
   2. 删除最后一个节点之后, 前驱指向直接后继, 也为空, 和中间位置的情况一样
4. 删除的节点不存在

c实现:

/*在链表L中删除第i个元素,并将删除的元素保存到*e中*/
int DelList(LinkList L,int i,ElemType *e){
	Node *pre,*r; //pre直接前驱,*r为目标
	if(i<1) return ERROR; //处理前驱越界
	pre=((i==1))?L:Get(L,i-1)); //找前驱
	if (pre==NULL||pre->next==NULL){ //处理前驱不存在和目标不存在
		printf("删除的节点位置不合理!");
		return ERROR;
	}
	r = pre->next; //通过前驱找到目标
	pre->next=r->next;//前驱跳过目标接上后继
	*e=r->data; free(r);
	return OK;
}

实际运用

常见需求

child::单链表就地逆置