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

梦里梦外; 2023-02-27 10:35 38阅读 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.插入函数-按位序插入：表中第i个位置上插入指定元素e 
    bool InsertNextNode(LNode* p, ElemType e);					//3-2.插入函数-指定结点后插：在指定结点之后插入元素e
    bool InsertPriorNode1(LinkList& L, LNode* p, ElemType e);	//3-3-1.插入函数-指定结点前插：在指定结点之前插入元素e---法1：老实人O(n)
    bool InsertPriorNode2(LNode* p, ElemType e);				//3-3-2.插入函数-指定结点前插：在指定结点之前插入元素e---法2：偷天换日O(1)
    bool ListDelete(LinkList& L, int i, ElemType& e);			//4-1.按位序删除
    bool DeleteNode1(LinkList& L, LNode* p);					//4-2-1.指定结点的删除：删除指定的元素p---法1：老实人O(n)
    bool DeleteNode2(LNode* p);									//4-2-2.指定结点的删除：删除指定的元素p---法2：偷天换日O(1)
    LNode* GetElem(LinkList L, int i);							//5-1.查找函数-按位查找：返回第i个元素
    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 = NULL;			//初始化为空，暂时没有任何结点
    	return L;
    }

## 4.2 判空 ##

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

## 4.3 插入操作 ##

### 4.3.1 按位插入 ###

//3-1.插入函数-按位序插入：表中第i个位置上插入指定元素e 
    bool InsertList(LinkList& L, int i, ElemType e) {
        
    	if (i == 1) {
        
    		LNode* s = (LNode*)malloc(sizeof(LNode));
    		if (s == NULL)		//内存分配失败
    			return false;
    		s->data = e;
    		s->next = L;
    		L = s;
    		return true;
    	}
    	/*此段代码=====按位查找操作
    		LNode* p;		//指针p指向当前扫描到的结点
    		int j = 1;		//当前p指向的是第几个结点
    		p = L;			//L指向头指针
    		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;		//给定结点不合法
    	if (p == L) {
        			//若指定插入第一个结点之前
    		LNode* s = (LNode*)malloc(sizeof(LNode));
    		if (s == NULL)
    			return false;		//内存分配失败
    		s->data = e;
    		s->next = L;
    		L = s;
    		return true;
    	}
    	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;
    }

##### 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) {
        		//如果是第一个结点
    		LNode* p;
    		p = L;
    		e = p->data;
    		L = p->next;
    		free(p);
    		return true;
    	}
    	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;
    	if (L == p) {
        
    		L = p->next;
    		free(p);
    		return true;
    	}
    	LNode* q;
    	q = L;
    	while (q != NULL && q->next != p)
    		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 = 1;
    	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;		//第一个结点赋给p
    	while (p != NULL && p->data != e)
    		p = p->next;
    	return p;		//找到后返回该结点的指针，否则返回NULL
    }

## 4.6 求表长 ##

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

## 4.7 创建单链表 ##

### 4.7.1 头插法 ###

//7-2.创建单链表：头插法
    LinkList List_HeadInsert(LinkList& L) {
        
    	L = InitList(L);		//初始化单链表
    	ElemType x;
    	LNode* s;
    	int i = 1;
    	printf("开始创建单链表！\n请输入第%d个元素：", i);
    	scanf("%d", &x);
    	while (x != 0) {
        
    		s = (LNode*)malloc(sizeof(LNode));
    		s->data = x;
    		s->next = L;
    		L = s;
    		printf("成功插入第%d个元素：%d\n", i,x);
    		printf("请输入%d个元素：", ++i);
    		scanf("%d", &x);
    	}
    	return L;
    }

### 4.7.2 尾插法 ###

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

//7-1-1.创建单链表-尾插法1：老实人O(n^2)
    LinkList List_TailInsert1(LinkList& L) {
        
    	InitList(L);
    	int length = 0;			//length 1.用来记录当前长度
    	ElemType x;
    	scanf("%d", &x);
    	while (x != 0) {
        
    		InsertList(L, length + 1, x);	//2.用来标识元素位序
    		length++;
    		scanf("%d", &x);
    	}
    	return L;
    }

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

//7-1-2.创建单链表-尾插法2：尾指针O(n)
    LinkList List_TailInsert2(LinkList& L) {
        
    	ElemType x;
    	L = InitList(L);
    	int i = 1;				//标记第一个结点以便于给头指针赋值
    	LNode* s, * r = L;			//r为表尾指针
    	scanf("%d", &x);		输入第一个结点的值
    	while (x != 0) {
        			//输入0表示结束
    		s = (LNode*)malloc(sizeof(LNode));
    		if (i == 1) {
        		//如果是第一个结点
    			s->data = x;	
    			L = s;			//将此结点的指针赋值给头指针
    			r = s;			
    			i = 0;			//将i置0表示，在用第一个结点给头指针赋值之后，头指针不参与接下来的操作
    			scanf("%d", &x);
    			continue;		//跳出本次循环，进入下一次赋值
    		}
    		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;
    	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.小结 #

*  在对无头结点的单链表进行操作时，很多操作要单独考虑操作对象是第一个结点的情况，因此需要专门设置一段逻辑来处理。为了避免这种情况，引入带头结点的单链表(所有结点的处理逻辑均相同)。