【数据结构】-单链表(带头结点）

浅浅的花香味﹌ 2023-02-27 10:31 149阅读 0赞

### 单链表-带头结点 ###

*  1.头文件及类型定义
 *  2.单链表结点类型定义
 *  3.函数声明
 *  4.基本操作
 *   *  4.1 初始化单链表
     *  4.2 判空
     *  4.3 插入操作
     *   *  4.3.1 按位插入
         *  4.3.2 指定结点插入
         *   *  4.3.2.1 指定结点后插
             *  4.3.2.2 指定结点前插
             *   *  4.3.2.2.1 前插法1(时间复杂度为O(n))
                 *  4.3.2.2.2 前插法2(时间复杂度为O(1))
     *  4.4 删除操作
     *   *  4.4.1 按位删除
         *  4.4.2 指定结点删除
         *   *  4.4.2.1 删除法1(时间复杂度为O(n))
             *  4.4.2.2 删除法2(时间复杂度为O(1))
     *  4.5 查找操作
     *   *  4.5.1 按位查找
         *  4.5.2 按值查找
     *  4.6 求表长
     *  4.7 创建单链表
     *   *  4.7.1 头插法
         *  4.7.2 尾插法
         *   *  4.7.2.1 依次查找(时间复杂度为O(n^2))
             *  4.7.2.2 尾指针(时间复杂度为O(n))
     *  4.8 遍历
     *  4.9 main函数
 *  5.小结

# 1.头文件及类型定义 #

#include<stdio.h>
    #include<stdlib.h>
    #define ElemType int

# 2.单链表结点类型定义 #

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

# 3.函数声明 #

/*函数声明*/
    LinkList InitList(LinkList& L);								//1.初始化单链表
    bool Empty(LinkList L);										//2.判空
    bool InsertList(LinkList& L, int i, ElemType e);			//3-1.插入函数-按位插入
    bool InsertNextNode(LNode* p, ElemType e);					//3-2.插入函数-指定结点后插
    bool InsertPriorNode1(LinkList& L, LNode* p, ElemType e);	//3-3-1.插入函数-指定结点前插-法1：老实人O(n)
    bool InsertPriorNode2(LNode* p, ElemType e);				//3-3-2.插入函数-指定结点前插-法2：偷天换日O(1)
    bool ListDelete(LinkList& L, int i, ElemType& e);			//4-1.按位删除
    bool DeleteNode1(LinkList& L, LNode* p);					//4-2-1.指定结点删除-法1：老实人O(n)
    bool DeleteNode2(LNode* p);									//4-2-2.指定结点删除-法2：偷天换日O(1)
    LNode* GetElem(LinkList L, int i);							//5-1.查找函数-按位查找
    LNode* LocateElem(LinkList L, ElemType e);					//5-2.查找函数-按值查找
    int Length(LinkList L);										//6.求表的长度
    LinkList List_TailInsert1(LinkList& L);						//7-1-1.创建单链表-尾插法1：老实人O(n^2)
    LinkList List_TailInsert2(LinkList& L);						//7-1-2.创建单链表-尾插法2：尾指针O(n)
    LinkList List_HeadInsert(LinkList& L);						//7-2.创建单链表-头插法：O(n)
    void PrintList(LinkList L);									//8.遍历单链表

# 4.基本操作 #

## 4.1 初始化单链表 ##

//1.初始化单链表(带头结点)
    LinkList InitList(LinkList& L) {
        
    	L = (LNode*)malloc(sizeof(LNode));			//分配一个头结点
    	if (L == NULL)
    		return NULL;		//内存不足，分配失败
    	L->next = NULL;		//头结点之后暂时没有结点
    	return L;
    }

## 4.2 判空 ##

//2.判空
    bool Empty(LinkList L) {
        
    	if (L->next == NULL)
    		return true;
    	else
    		return false;
    	//或者 return (L->next == Null);
    }

## 4.3 插入操作 ##

### 4.3.1 按位插入 ###

//3-1.插入函数-按位序插入：表中第i个位置上插入指定元素e 
    bool InsertList(LinkList& L, int i, ElemType 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++;
    		}
    	*/
    	LNode* p = GetElem(L, i - 1);
    
    	/*此段代码====后插操作
    		if (p == NULL)
    			return false;		//i值不合法
    		LNode* s = (LNode*)malloc(sizeof(LNode));		//为要插入的结点申请空间
    		if (s == NULL)		//内存分配失败
    			return false;
    		s->data = e;			//放入数据
    		s->next = p->next;		//要插入结点指向i-1的后继结点
    		p->next = s;		//i-1的结点指向插入的结点
    		return true;
    	*/
    	return InsertNextNode(p, e);
    }

### 4.3.2 指定结点插入 ###

#### 4.3.2.1 指定结点后插 ####

//3-2.插入函数-指定结点后插：在指定结点之后插入元素e
    bool InsertNextNode(LNode* p, ElemType e) {
        
    	if (p == NULL)
    		return false;
    	LNode* s = (LNode*)malloc(sizeof(LNode));
    	if (s == NULL)		//内存分配失败
    		return false;
    	s->data = e;
    	s->next = p->next;
    	p->next = s;
    	return true;
    }

#### 4.3.2.2 指定结点前插 ####

##### 4.3.2.2.1 前插法1(时间复杂度为O(n)) #####

//3-3-1.插入函数-指定结点前插：在指定结点之前插入元素e---法1：老实人O(n)
    bool InsertPriorNode1(LinkList& L, LNode* p, ElemType e) {
        
    	if (p == NULL)
    		return false;		//给定结点合法
    	LNode* q;
    	q = L;
    	while (q != NULL && q->next != p)
    		q = q->next;
    	/*此段代码====指定后插
    		if (q == NULL)
    			return false;	//给定结点不在单链表中
    		LNode* s = (LNode*)malloc(sizeof(LNode));
    			if (s == NULL)
    				return false;		//内存分配失败
    			s->data = e;
    			s->next = q->next;	
    			q->next = s;
    			return true;
    	*/
    	return InsertNextNode(q, e);
    }

##### 4.3.2.2.2 前插法2(时间复杂度为O(1)) #####

//3-3-2.插入函数-指定结点前插：在指定结点之前插入元素e---法2：偷天换日O(1)
    bool InsertPriorNode2(LNode* p, ElemType e) {
        
    	if (p == NULL)
    		return false;
    	LNode* s = (LNode*)malloc(sizeof(LNode));
    	if (s == NULL)		//内存分配失败
    		return false;
    	s->next = p->next;
    	p->next = s;
    	s->data = p->data;
    	p->data = e;
    	return true;
    }

## 4.4 删除操作 ##

### 4.4.1 按位删除 ###

//4-1.按位序删除
    bool ListDelete(LinkList& L, int i, ElemType& 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++;
    		}
    	*/
    	LNode* p = GetElem(L, i - 1);
    	if (p == NULL)
    		return false;		//i值不合法
    	if (p->next == NULL)		//第i-1个结点之后已无其他结点
    		return false;
    	LNode* q = p->next;		//p指向被删除结点q
    	e = q->data;			//用e返回被删除元素的值
    	p->next = q->next;		//q指向被删除结点的后继结点
    	free(q);				//释放被删除结点的空间
    	return true;
    }

### 4.4.2 指定结点删除 ###

#### 4.4.2.1 删除法1(时间复杂度为O(n)) ####

//4-2-1.指定结点的删除：删除指定的元素p---法1：老实人O(n)
    bool DeleteNode1(LinkList& L, LNode* p) {
        
    	if (p == NULL)
    		return false;
    	LNode* q;		//设q为p的前驱结点
    	q = L;
    	while (q != NULL && q->next != p)	//遍历找到p的前驱结点q
    		q = q->next;		
    	if (q == NULL)
    		return false;
    	q->next = p->next;
    	free(p);
    	return true;
    }

#### 4.4.2.2 删除法2(时间复杂度为O(1)) ####

//4-2-2.指定结点的删除：删除指定的元素p---法2：偷天换日O(1)
    bool DeleteNode2(LNode* p) {
        
    	if (p == NULL)
    		return false;
    	LNode* q = p->next;		//令q指向p的后继结点
    	p->data = q->data;		//q的数据域赋值给p的数据域
    	p->next = q->next;		//p的后继结点指向q的后继结点
    	free(q);				//释放q的空间
    	return true;
    }//若p为最后一个结点，则只能用法1

## 4.5 查找操作 ##

### 4.5.1 按位查找 ###

//5-1.查找函数-按位查找：返回第i个结点
    LNode* GetElem(LinkList L, int i) {
        
    	if (i < 0)
    		return NULL;	//小于单链表长度
    	LNode* p = L;
    	int j = 0;
    	while (p != NULL && j < i) {
        
    		p = p->next;
    		j++;
    	}
    	return p;		//也可能返回NULL，当输入i大于单链表长度时
    }

### 4.5.2 按值查找 ###

//5-2.查找函数-按值查找：找到第一个数据域为e的结点
    LNode* LocateElem(LinkList L, ElemType e) {
        
    	LNode* p = L->next;		//第一个结点赋给p
    	while (p != NULL && p->data != e)
    		p = p->next;
    	return p;		//找到后返回该结点的指针，否则返回NULL
    }

## 4.6 求表长 ##

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

## 4.7 创建单链表 ##

### 4.7.1 头插法 ###

//7-1.创建单链表：头插法
    LinkList List_HeadInsert(LinkList& L) {
        
    	L = InitList(L);		//初始化单链表
    	ElemType x;
    	int i = 1;		//用作记录插入第几个元素
    	printf("开始创建单链表！\n请输入%d个元素：", i);
    	scanf("%d", &x);
    	while (x != 0) {
        
    		if (InsertNextNode(L, x)) 		//头插法本质是头结点的后插操作
    			printf("成功插入第%d个元素：%d\n", i, x);
    		else
    			printf("插入第%d个元素失败！\n", i);
    		printf("请输入%d个元素：", ++i);
    		scanf("%d", &x);
    	}
    	printf("单链表创建完成！\n");
    	return L;
    }

### 4.7.2 尾插法 ###

#### 4.7.2.1 依次查找(时间复杂度为O(n^2)) ####

//7-2-1.创建单链表-尾插法1：老实人O(n^2)
    LinkList List_TailInsert1(LinkList& L) {
        
    	InitList(L);
    	int length = 0;
    	ElemType x;
    	scanf("%d", &x);
    	while (x != 0) {
        
    		InsertList(L, length + 1, x);
    		length++;
    		scanf("%d", &x);
    	}
    	return L;
    }

#### 4.7.2.2 尾指针(时间复杂度为O(n)) ####

//7-2-2.创建单链表-尾插法2：尾指针O(n)
    LinkList List_TailInsert2(LinkList& L) {
        
    	ElemType x;
    	L = InitList(L);	//建立头结点
    	LNode* s, * r = L;			//r为表尾指针
    	scanf("%d", &x);			//输入结点的值
    	while (x != 0) {
        			//输入0表示结束
    		s = (LNode*)malloc(sizeof(LNode));
    		s->data = x;
    		r->next = s;
    		r = s;				//指向新的表尾结点
    		scanf("%d", &x);
    	}
    	r->next = NULL;			//创建单链表结束，表尾结点指针置空
    	return L;
    }

## 4.8 遍历 ##

//8.遍历单链表
    void PrintList(LinkList L) {
        
    	LNode* p;
    	p = L->next;
    	printf("遍历单链表：\n");
    	while (p != NULL) {
        
    		printf("%d\t", p->data);
    		p = p->next;
    	}
    	printf("\n");
    }

## 4.9 main函数 ##

int main() {
        
    	LinkList L;
    	int i;
    
    	/*以下操作只要涉及对单链表的改动，均遍历单链表*/
    
    	/*1、头插法建立单链表*/
    	L = List_HeadInsert(L);  
    	//L = List_TailInsert1(L);	 //尾插法1：O(n^2)
    	//L = List_TailInsert2(L);	 //尾插法2：O(n)
    	printf("当前表长为：%d\n", Length(L));
    	PrintList(L);
    
    	///*2、按位插入*/
    	ElemType e1;
    	printf("请输入您所要插入的位序i和元素值e：");
    	scanf("%d%d", &i, &e1);
    	if (InsertList(L, i, e1))
    		printf("您已成功插入元素值：%d\n", e1);
    	else
    		printf("位序i不合法，插入元素值%d失败！\n", e1);
    	PrintList(L);
    
    	/*3、按位删除*/
    	ElemType e2 = -1;
    	printf("请输入您所要删除的位序i：");
    	scanf("%d", &i);
    	if (ListDelete(L, i, e2))
    		printf("您已成功删除元素值：%d\n", e2);
    	else
    		printf("位序%d不合法，元素删除失败！\n", i);
    	PrintList(L);
    
    	/*4、按位查找*/
    	printf("请输入您要查找的位序i：");
    	scanf("%d", &i);
    	LNode* p1 = GetElem(L, i);
    	printf("位序为%d的值为：%d\n", i, p1->data);
    
    	/*5、指定结点后插,以按位查找的p1结点为例*/
    	ElemType e3;
    	printf("请输入您要后插的值：");
    	scanf("%d", &e3);
    	if (InsertNextNode(p1, e3))
    		printf("p结点后插成功，元素值为：%d\n", e3);
    	else
    		printf("p结点后插失败！\n");
    	PrintList(L);
    
    	/*6、指定结点前插*/
    	ElemType e4;
    	printf("请输入您要前插的值：：");
    	scanf("%d", &e4);
    	if (InsertPriorNode1(L, p1, e4))		//此处用前插法1：老实人O(n^2)
    		//InsertPriorNode2(p1, e4);			//前插法2：偷天换日O(n) 
    		printf("p结点前插成功，元素值为：%d\n", e4);
    	else
    		printf("p结点前插失败\n");
    	PrintList(L);
    
    	/*7、按值查找*/
    	ElemType e5;
    	printf("请输入您要查找的元素值e：");
    	scanf("%d", &e5);
    	LNode* p2 = LocateElem(L, e5);
    
    	/*8、指定结点删除，以按值查找的p2结点为例*/
    	if (DeleteNode1(L, p2))				//此处用删除的法1：老实人O(n^2)
    		//DeleteNode2(p2)   法2：偷天换日O(n)
    		printf("值为%d的元素删除成功！\n", e5);
    	else
    		printf("值为%d的元素删除失败！\n", e5);
    	PrintList(L);
    	return 0;
    }

# 5.小结 #

1.  **带头结点和无头结点的单链表在操作上的不同**  
    如果涉及到要对前驱结点进行操作，那么，无头结点的单链表需要一段逻辑来处理操作是第一个结点的情况，主要是头指针的变化，而带头结点的单链表头指针永远指向的是头结点，故和其他结点的处理逻辑是一样的。由于带头结点的链表处理方式简单，故后续双链表，循环单链表，循环双链表均只用带头结点的链表实现。
2.  **代码的封装**  
    单链表的很多操作是公用的，例如按位插入和按位删除首先是要按位查找其前驱节点，然后对指针进行修改；按位插入的第二个处理逻辑以及指定结点前插法1实际上实对指定结点的后插操作，此时，代码的封装显得尤为重要。
3.  **单链表的局限性**  
    1.由于单链表中每个结点只包含指向其后继结点的指针，故在寻找其前驱结点时是很麻烦的，虽然寻找前驱结点可能用其他操作来避免（仅仅是避免），但有时会出现bug。例如：在删除指定结点时，常规方法是找到指定结点的前驱结点，然后进行指针的相关修改，释放指定结点的内存。另一种方法是将其后继结点的值转移，然后修改指针，释放其后继结点的内存，也可以达到删除指定结点的效果。但如果删除的是最后一个结点，其后继结点为NULL，将其后继结点的值转移显然是有问题的，于是此种情况只能用常规方法处理，因此，想要快捷找到指定结点的前驱结点单链表显然是不合适的，故引入双链表。  
    2.另外，因为很多时候对链表的操作都是在头部或者尾部(例如：头插法或者尾插法建立链表)，利用循环单链表效率更高。若为普通单链表(表尾指针指向NULL)且仅知道头结点，要从头结点找到尾结点，只能从头到尾依次扫描，时间复杂度为O(n)；若为循环单链表，令单链表的指针L指向表尾结点，那么从尾结点找到头结点，时间复杂度为O(1)，效率提升比较明显。当然，如果要在表尾进行插入和删除操作，需要改变指针L的指向。