数据结构笔记3-线性表-单链表

参考网课数据结构-青岛大学-王卓-第三周

参考书籍《数据结构C语言版第二版》 中国工信出版集团 人民邮电出版社出版 严蔚敏 编著

---

线性表的链式存储

单链表，双链表，循环链表

头指针，头结点，首元节点

Note

在链表中设计头结点有什么好处？ 1.在处理首元节点的变化会比较方便——与其他位置一致。 2.便于非空表和空表的统一处理——头指针都是指向头结点的非空指针。

Warning

头结点在统计表长的时候不计入，不属于数据域。

链表的储存结构特点

1. 顺序存取法（对比随机存取法）：只能从前往后找，越往后访问越慢。
2. 数据域+指针域

单链表的类型定义和变量定义

类型定义

typedef struct Lnode{
	ElemType data;
	struct Lnode *next;
}Lnode,*LinkList;

Note

嵌套定义：自己的定义包含了自己。自己：struct Lnode typedef: 重新起名字

变量定义

LinkList L; //定义链表L，指向头节点的指针通常用于代表整个链表
LNode *p；   //定义节点指针p
 
//LNode *L;   通常不用
//LinkList p;   通常不用
 

单链表通常如下定义（具体例子 ）

为了统一链表操作，通常如下定义：

typedef Struct{
	char num[8];  //数据域
	char name[8]; //数据域
	int score;    //数据域
}ElemType;
 
typedef struct Lnode{
	ElemType data; //数据域
	struct Lnode *next; //指针域
}Lnode,*LinkList;

Hint

这样定义的想法是先定义一个ElemType，再结合ElemType加上指针域定义链表，而不是吧二者直接全部写到链表里面。

单链表基本操作的实现

单链表的初始化（C++的写法）

Status InitList_L(LinkList &L){
	L=new LNode;//或L=(LinkList)malloc(sizeof(LNode));是c的写法
	L->next=NULL;
}

Note

NULL是需要事先定义过的一些常用常量。

补充算法1-判断链表是否为空

int ListEempty(LinkList L){
if(L->next) return 0;
else return 1;
}

补充算法2-单链表的销毁

Status DestoryList_L(LinkList &L){
	Lnode *p;
	while(L){
		p=L;
		L=L->next //把节点指针进行后移
		delete p;
	}
	return OK;
}

Note

->表示结构体指针。即当有一个指向某个结构体的指针p后，想要把结构体中的a赋值给变量x，则可以写： x=p->a

Note

L=L->next  //把节点指针进行后移
p=L->next //让指针p指向首元节点
p=L            //让指针p指向头节点

上面三个有注释的操作非常重要

补充算法3-清空链表

Status ClearList(Linklist &L){
	Lnode *p,*q;
	p=L->next;
	while(p){
		q=p->next;
		delete p;
		p=q;
	}
	L->next=NULL;
	return OK;
}

Note

需要用到两个指针，在其中一个指针删除对应的内容之前，要让这个指针指向的节点的next部分存出来，不然执行删除之后就找不到下一个节点了。

补充算法4-求单链表表长

int ListLength_L(LinkList &L){
	LinkList p;
	p=L->next;
	i=0;
	while(p){
		i++;
		p=p->next;
	}
	return i;
}

取值-取单链表中第 i 个元素

Status GetElem_L(LinkList L, int i, ElemType &e){
	p=L->next;
	j=1;
	while(p&&j<i){
		p=p->next;
		++j;
	}
	if(!p||j>i)      //第i个元素不存在时
		return ERROR;
	e=p->data;
	return OK;
}

按值查找-返回地址

Lnode *LocateElem_L(LinkList L,Elemtype e){
	p=L->next;
	while(p&&p->data!=e)
		p=p->next;
	return p;
}

按值查找-返回位置序号

int LocateElem_L(LinkList L, Elemtype e){
	p=L->next;
	j=1;
	while(p&&p->data!=e)
		p=p->next;
	if(p) return j;
	else return 0;  //表示查找失败
}

插入-在指定标号节点前

Status ListInsert_L(LinkList &L, int i, ElemType e){
	p=L;
	j=0;
	while(p&&j<i-1){p=p->next;++j;}//find the i-1th node 第二要点
	if(!p||j>i-1) return ERROR;//whether the i-1th node do not exist 第三要点
	s=new LNode;
	s->next=p->next; //insert the new node.注意赋值顺序不能换，先接上后边的表，再接上前面。第一要点
	p->next=s;
	return OK;
}

Warning

注意insert时候赋值顺序不能换，先接上后边的表，再接上前面。如果调换顺序需要多定义一个变量作为中间变量。

Warning

注意三大要点，详见上面注释。

删除-删除指定节点

Status ListDelete_L(LinkList &L, int i, ElemType &e){
	p=L;
	j=0;
	while(p->next&&j<i-1){p=p->next;++j;} //寻找第i个节点，第二要点
	if(!(p->next)||j>i-1) return ERROR; //判断删除位置是否合理，第四要点
	q=p->next;
	p->next=q->next; //改变删除节点的前驱节点的指针域为下个节点，第一要点
	e=q->data;
	delete q; //释放删除节点的储存空间，第三要点
	return OK;
}

Warning

注意四大要点，已经在注释中标出。

单链表查找，插入，删除的时间效率分析

操作	时间复杂度
查找	$O(n)$
插入和删除	$O(1)$

单链表的建立-头插法

void CreateList_H(LinkList &L,int n){
	L=new LNode;
	L->next=NULL;    //建立一个带头结点单链表
	for(i=n;i>0;--i){
		p=new LNode;   //生成新节点 或 p=(LNode*)malloc(sizeof(LNode));
		cin>>p->data;   //输入元素值 或 scanf(&p->data); 
		p->next=L->next;   //插入到表头
		L->next=p;
	}
}

Hint

此处重要！（关于插入到表头的代码的解释）

p->next=L->next;   
L->next=p;

含义解释：先把上一个节点的指针域赋值给新节点的指针域；

再将上一个节点的指针域写入为新节点的地址。

单链表的建立-尾插法

void CreateList_R(LinkList &L, int n){
	L=new LNode;
	L->next=NULL;
	r=L;
	for(i=0;i<n;++i){
		p=new LNode;
		cin>>p->data; //生成新节点，输入元素值
		p->next=NULL; //令新节点的指针域为空，重点
		r->next=p; //令新节点的地址存在旧表末尾节点的指针域中，重点
		r=p; //将r指向新表的末尾节点，重点
	}
}

时间复杂度$O(n)$，关于重点详见注释，注意操作顺序。

---