博客

第二章 线性表（链表）

本章思维导图





1.单链表


（1）单链表的定义

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。

单链表节点类型描述

typedef struct LNode {      //定义单链表结点类型
	int data;               //每个节点存放一个数据元素
	struct LNode* next;     //指针指向下一个节点
}LNode, *LinkList;

（2）头插法

//头插法
LinkList List_HeadInsert(LinkList& L) {   //逆向建立单链表
	LNode* s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));  //创建头结点
	L->next = NULL;                       //初始为空链表
	scanf("%d", &x);                      //输入节点的值
	while (x != 666) {                    //输入666表示结束
		s = (LNode*)malloc(sizeof(LNode));//创建新节点
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
	return L;
}

（3）尾插法

//尾插法
LinkList List_TailInsert(LinkList& L) {    //正向建立单链表
	int x;
	L = (LinkList)malloc(sizeof(LNode));
	LNode* s, * r = L;                     //r为尾指针
	scanf("%d", &x);                       //输入节点的值
	while (x != 666) {                     //输入666表示结束
		s = (LNode*)malloc(sizeof(LNode)); //创建新节点
		s->data = x;
		r->next = s;
		r = s;                             //r指向新的表尾结点
		scanf("%d", &x);
	}
	r->next = NULL;                        //尾结点指针置空
	return L;
}

（4）按位序插入（带头结点）

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList& L, int i, int e) {
	if (i < 1)
		return false;
	LNode* p;                     //指针p指向当前扫描的结点
	int j = 0;                    //当前p指向的是第几个结点
	p = L;                        //L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i - 1) {  //循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if (p == NULL)                   //i值不合法
		return false;
	LNode *s = (LinkList)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;                 //将结点s连到p之后
	return true;                 //插入成功
}

（5）按位序插入（不带头结点）

//在第i个位置插入元素e（不带头结点）
bool ListInsert(LinkList& L, int i, int e) {
	if (i < 1)
		return false;
	if (i == 1) {     //插入第1个结点的操作与其它结点操作不同
		LNode* s = (LinkList)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;        //头指针指向新节点
		return true;
	}
	LNode* p;                     //指针p指向当前扫描的结点
	int j = 0;                    //当前p指向的是第几个结点
	p = L;                        //L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i - 1) {  //循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if (p == NULL)                   //i值不合法
		return false;
	LNode* s = (LinkList)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;                 //将结点s连到p之后
	return true;                 //插入成功
}

单链表带头结点的优点如下：

• 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一样，无需进行特殊处理。
• 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就得到统一。

（6）后插操作（在p节点之后插入元素e）

//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode* p, int e) {
	if (p == NULL)
		return false;
	LNode* s = (LinkList)malloc(sizeof(LNode));
	if (s == NULL)                //内存分配失败
		return false;
	s->data = e;
	s->next = p->next;
	p->next = s;                 //将结点s连到p之后
	return true;                 //插入成功
}

（7）前插操作（在p节点之前插入元素e）

//前插操作（在p节点之前插入元素e）
bool InsertPriorNode(LNode* p, int e) {
	if (p == NULL)
		return false;
	LNode* s = (LinkList)malloc(sizeof(LNode));
	if (s == NULL)                //内存分配失败
		return false;
	s->next = p->next;
	p->next = s;                 //新节点s连到p之后
	s->data = p->data;           //将p中元素复制到s中
	p->data = e;                 //p中元素覆盖为e
	return true;                 //插入成功
}

（8）按位序删除（带头结点）

//按位序删除（带头结点）
bool ListDelete(LinkList& L, int& e) {
	if (i < 1)
		return false;
	LNode* p;                     //指针p指向当前扫描的结点
	int j = 0;                    //当前p指向的是第几个结点
	p = L;                        //L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i - 1) {  //循环找到第i-1个结点
		p = p->next;
		j++;
	}
	if (p == NULL)                  //i值不合法
		return false;
	if (p->next == NULL)            //第i-1个结点之后已无其他结点
		return false;
	LNode* q = p->next;             //令q指向被删除结点
	e = q->data;                    //用e返回元素的值
	p->next = q->next;              //将*p结点从链中断开
	free(q);                        //释放结点的存储空间
	return true;                    //删除成功
}

（9）删除指定结点p

//删除指定结点p
bool DeleteNode(LNode* p) {
	if (p == NULL)
		return false;
	LNode* q = p->next;             //令q指向*p的后继结点
	p->data = p->next->data;        //和后继结点交换数据域
	p->next = q->next;              //将*q结点从链中断开
	free(q);                        //释放后继结点的存储空间
	return true;
}

(10) 按位查找，返回第i个元素(带头结点)

//按位查找，返回第i个元素(带头结点)
LNode* GetElem(LinkList L, int i) {
	if (i < 0)
		return NULL;
	LNode* p;                     //指针p指向当前扫描的结点
	int j = 0;                    //当前p指向的是第几个结点
	p = L;                        //L指向头结点，头结点是第0个结点（不存数据）
	while (p != NULL && j < i) {  //循环找到第i个结点
		p = p->next;
		j++;
	}
	return p;
}

(11) 按值查找，找到数据==e的结点

//按值查找，找到数据==e的结点
LNode* LocateElem(LinkList L, int e) {
	LNode* p = L->next;    //从第1个结点开始查找数据域为e的结点
	while (p != NULL && p->data != e)
		p = p->next;
	return p;    //找到后返回该结点指针，否则返回NULL
}

（12）求表长

//求表的长度
int Length(LinkList L) {
	int len = 0;
	LNode* p = L;
	while (p->next != NULL) {
		p = p->next;
		len++;
	}
	return len;
}

（13）顺序表与单链表的比较

2.双链表


（1）双链表节点类型描述

//双链表节点类型描述
typedef struct DNode {
	int data;
	struct DNode* prior, * next;
}DNode,*DLinkList;里插入代码片

（2）初始化双链表(带头结点)

//初始化双链表(带头结点)
bool InitDLinkList(DLinkList& L) {
	L = (DNode*)malloc(sizeof(DNode));  //分配一个头节点
	if (L == NULL)                      //内存不足，分配失败
		return false;                   
	L->prior = NULL;                   //头结点的prior永远指向NULL  
	L->next = NULL;                    //头结点之后暂时没有结点
	return true;
}

（3）在p节点之后插入s结点

//在p节点之后插入s结点
bool InsertNextDNode(DNode* p, DNode* s) {
	s->next = p->next;        //将结点*s插入到结点*p之后
	p->next->prior = s;
	s->prior = p;
	p->next = s;
}
//在p节点之后插入s结点（改进）
bool InsertNextDNode(DNode* p, DNode* s) {
	if (p == NULL || s == NULL)       //非法参数
		return false;
	s->next = p->next;        //将结点*s插入到结点*p之后
	if(p->next!=NULL)
		p->next->prior = s;
	s->prior = p;
	p->next = s;
	return true;
}

（4）删除p结点的后继结点

//删除p结点的后继结点
bool DeleteNextDNode(DNode* p) {
	if (p == NULL)
		return false;
	DNode* q = p->next;     //找到p的后继结点q
	if (q == NULL)          //p没有后继结点
		return false;
	p->next = q->next;
	if (q->next != NULL)      //q结点不是最后一个结点
		q->next->prior = p;
	free(q);                  //释放结点空间
	return true;
}