单向链表·初识【c语言】

╰+攻爆jí腚メ 2024-04-06 10:32 197阅读 0赞

#### 文章目录 ####

*  顺序表和链表的优缺点
 *  入门·增删改查【大佬请路过】
 *   *  增
     *   *  头插·思路·代码
         *  尾插·思路·代码
         *  定位插入·前插入
         *  定位插入·后插入
     *  删
     *   *  头删
         *  尾删
         *  指定删除·节点
     *  查
     *  改
     *  销毁·链表

## 顺序表和链表的优缺点 ##

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th>优点</th> 
   <th>缺点</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>顺序表</td> 
   <td>支持随机访问</td> 
   <td>1. 空间损耗 2. 头部或者中间位置的插入和删除，麻烦，挪动数据有消耗</td> 
  </tr> 
  <tr> 
   <td>链表</td> 
   <td>1. 合理使用空间 头插头删节省空间</td> 
   <td>不支持随机访问</td> 
  </tr> 
 </tbody> 
</table>

## 入门·增删改查【大佬请路过】 ##

*  本部分相信，很多人都经历过，虽然单纯的增删改查没什么实际的意义。但是这是我们我们的基础，将简单的逻辑思路搞清楚之后，我们才可以更快更好的深入学习。
 *  定义的节点

typedef int SLNDataType;
    typedef struct SingleListNode {
        
    	SLNDataType data;
    	struct SingleListNode* next;
    } SLN;

### 增 ###

#### 头插·思路·代码 ####

![在这里插入图片描述][1ec1793c2f6846a4b4d4e7865d118116.png]

void SLNPushFront(SLN** pphead, SLNDataType x) {
        
    	SLN* newNode = CreateSLN(x);
    	//无论链表是否为空，都正确
    	newNode->next = *pphead;
    	*pphead = newNode;
    }

#### 尾插·思路·代码 ####

*  关于为什么使用二级指针，因为函数传递的是一级指针，如果使用同级指针，会造成指针值传递。形参指针不修改实参指针的值。

void SLNPushBack(SLN** pphead, SLNDataType x) {
        
    	SLN* newNode=CreateSLN(x);
    	if (*pphead == NULL) {
        
    		*pphead = newNode;
    	}
    	else {
        
    		//找到尾节点
    		SLN* tail = *pphead;
    		while (tail->next != NULL) {
        
    			tail = tail->next;
    		}
    		tail->next = newNode;
    	}
    	
    }

![在这里插入图片描述][62bd7cc47c3e43f98bbc400aa101c1ba.png]

#### 定位插入·前插入 ####

![在这里插入图片描述][26d0db402ff144f08073a72340e6daf9.png]

void SLNInsertBefore(SLN** pphead, SLN* pos, SLNDataType x) {
        
    	SLN* newNode = CreateSLN(x);
    	//头节点的情况
    	if (*pphead == pos) {
        
    		newNode->next = *pphead;
    		*pphead = newNode;
    	}
    	//非头节点的情况：找到pos的前一个位置
    	else {
        
    		SLN* posPrev = *pphead;
    		while (posPrev->next != pos) {
        
    			posPrev = posPrev->next;
    		}
    		posPrev->next = newNode;
    		newNode->next = pos;
    	}
    }

#### 定位插入·后插入 ####

![在这里插入图片描述][436fc1c1f9a4474791c70a4dfc29e220.png]

void SLNInsertAfter(SLN* pos, SLNDataType x) {
        
    	SLN* newNode = CreateSLN(x);
    	newNode->next = pos->next;
    	pos->next = newNode;
    }

### 删 ###

#### 头删 ####

![在这里插入图片描述][2b4efe6fad684d34962497fde4f3f214.png]

void SLNPopFront(SLN** pphead) {
        
    	if (*pphead == NULL) {
        
    		cout << "空链表" << endl;
    		return;
    	}
    	else {
        
    		SLN* newTail=(*pphead)->next;
    		free(*pphead);
    		*pphead = newTail;
    	}
    }

#### 尾删 ####

![在这里插入图片描述][3ce2196c38ea4000b1ebf411a50213ac.png]

void SLNPopBack(SLN** pphead) {
        
    	/*
    	删除总共分三种情况：
    	1：链表本身是空的
    	2：链表只有一个节点
    	3：链表有一个以上的节点
    	*/
    	//1-粗暴的方式
    	//assert(*pphead!=NULL);
    	//2-温柔的方式
    	if (*pphead == NULL) {
        
    		cout << "空链表" << endl;
    		return;
    	}
    	
    	else if((*pphead)->next == NULL) {
        
    		free(*pphead);
    		*pphead = NULL;
    		
    	}
    	else {
        
    		//找到尾节点和尾节点的前一个节点
    		//将尾节点释放，将尾节点的前一个节点的next置为null
    		//方法一：
    		/*
    		SLN* tail = *pphead;
    		SLN* prev = NULL;
    		while (tail->next != NULL) {
    			prev = tail;
    			tail = tail->next;
    		}
    		free(tail);
    		tail = NULL;
    		prev->next = NULL;
    		*/
    		//方法二：
    		SLN* tail = *pphead;
    		while (tail->next->next) {
        
    			tail = tail->next;
    		}
    		free(tail->next);
    		tail->next = NULL;
    	}
    }

#### 指定删除·节点 ####

![在这里插入图片描述][95b3e40815454eb18b03d4d8dabab142.png]

void SLNEase(SLN** pphead, SLN* pos) {
        
    	//要删除的元素是头节点
    	if(*pphead == pos) {
        
    		*pphead = pos->next;
    		free(pos);
    		//方法二：SLNPopFront(pphead);
    	}
    	else {
        
    		SLN* posPrev = *pphead;
    		while (posPrev->next != pos) {
        
    			posPrev= posPrev->next;
    		}
    		posPrev->next = pos->next;
    		free(pos);
    		pos = NULL;//可有可没有，形参没改变实参，防止某些时候错误，顺手写上
    	}
    }

### 查 ###

SLN* SLNFindByValue(SLN* phead, SLNDataType x) {
        
    	SLN* cur = phead;
    	while (cur != NULL) {
        
    		if (cur->data == x) {
        
    			return cur;
    		}
    		else {
        
    			cur = cur->next;
    		}
    	}
    	return NULL;
    }

### 改 ###

SLN* plist = NULL;
        SLNPushBack(&plist, 1);
        SLNPushBack(&plist, 2);
        SLNPushBack(&plist, 3);
        SLNPushBack(&plist, 2);
        SLNPushBack(&plist, 4);
        SLNPushBack(&plist, 2);
        SLNPushBack(&plist, 5);
        SLNPrint(plist);
        //查找作用
        SLN*pos=SLNFindByValue(plist, 2);
        int i = 1;
        while (pos) {
        
            cout << "第" << i++ << "个pos节点：" << &pos << "->" << pos->data << endl;
            pos = SLNFindByValue(pos->next, 2);
        }
        //修改作用
        pos = SLNFindByValue(plist, 2);
        while(pos) {
        
            pos->data = 20;
            pos = SLNFindByValue(pos->next, 2);
        }
        SLNPrint(plist);

### 销毁·链表 ###

![在这里插入图片描述][91572c12c3cf4b16bd27bc08a47c484d.gif_pic_center]

void SLNDestroy(SLN** pphead) {
        
    	SLN* q = NULL;
    	SLN*p = *pphead;//让p指向头节点
    	while (p != NULL) {
        
    		q = p->next;//让q指向当前节点的后一个节点
    		delete p;//删除当前节点
    		p = q;
    	}
    	//free(*pphead);
    	*pphead = NULL;
    }

[1ec1793c2f6846a4b4d4e7865d118116.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/4063c40a09fc46c2bd953549eb393fe4.png
[62bd7cc47c3e43f98bbc400aa101c1ba.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/89585d58a5c14f5ba3d4ecb3c71cd972.png
[26d0db402ff144f08073a72340e6daf9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/c20693706ebd4dfcb9aaceaf54f7f0a4.png
[436fc1c1f9a4474791c70a4dfc29e220.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/fdf947c409ff4b618c288d60b981024e.png
[2b4efe6fad684d34962497fde4f3f214.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/0b981f2755f14c918723388ea2bd4d50.png
[3ce2196c38ea4000b1ebf411a50213ac.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/ef5182348f8947a79f45dce9b3329030.png
[95b3e40815454eb18b03d4d8dabab142.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/4f1c9a784df145c2acfa506afcd37704.png
[91572c12c3cf4b16bd27bc08a47c484d.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/06/b5e4aeee510041099ceda7d8aaad06c4.gif