[网络协议]3.2、离散存储【链表】

你要从自己开始，先检讨自己。

3.2、 离散存储【链表】

? 定义：

? ?????????n个节点离散分配

? ?????????彼此通过指针相连

? ?????????每个节点只有一个前驱节点，每个节点只有一个后继节点

? ?????????首节点没有前驱节点，尾节点没有后继节点

? 专业术语：

? ?????????首节点：

? ??????????????????第一个有效节点

? ?????????尾节点：

? ??????????????????最后一个有效节点

? ?????????头结点：

? ??????????????????头结点的数据类型和首节点类型一样

? ??????????????????第一个有效节点之前的那个节点

? ??????????????????头节点并不存放有效数据

? ??????????????????加头结点的目的主要是为了方便对链表的操作

? ?????????头指针：

? ??????????????????指向头结点的指针变量

? ?????????尾指针：

? ??????????????????指向尾节点的指针变量

?????????问题：
? ??????????????????如果希望通过一个函数来对链表进行处理，我们至少需要接收链表的哪些参数？

? ???????????????????????????只需要一个参数：头指针

? ???????????????????????????因为我们通过头指针可以推算出链表的其他所有参数

?????????数据结构：

# include <stdio.h>

typedef struct Node
{
	int data; // 数据域 
	struct Node * pNext; // 指针域 
}NODE, *PNODE； // NODE 等价于 struct Node, PNODE 等价于 struct Node * 

?????????分类：

? ??????????????????单链表

? ??????????????????双链表

? ??????????????????循环链表

? ??????????????????非循环链表

?
? ?????????算法：

? ??????????????????狭义的算法是与数据的存储方式密切相关

? ??????????????????广义的算法是与数据的存储方式无关

? ?????????泛型：

? ??????????????????利用某种技术达到的效果就是：不同的存储方式，执行的操作是一样的

?

? ?????????链表的优缺点：

? ??????????????????优点：

? ??????????????????插入和删除速度快（只需改变指针指向即可）；

? ??????????????????没有空间限制，只与内存空间大小有关；

? ??????????????????内存利用率变高;

? ?????????缺点：

? ??????????????????占用额外的空间存储指针，比较浪费空间，不连续存储，malloc函数开辟空间碎片比较多;

? ??????????????????查找速度比较慢，因为在查找时，需要循环链表。

示例代码：

# include <stdio.h>
# include <stdlib.h>
// # include <malloc.h>
typedef struct Node
{
	int data; // 数据域 
	struct Node * pNext; // 指针域 
}NODE, *PNODE; // NODE 等价于 struct Node, PNODE 等价于 struct Node * 

// 函数申明
PNODE create_list(void); //创建链表 
void traverse_list(PNODE pHead); // 遍历链表 
bool is_empty(PNODE pHead); // 判断链表是否为空 
int length_list(PNODE pHead); // 求链表的长度 
// 在pHead所指向链表的第pos个节点的前面插入一个新的节点，该节点的值val，
// 并且pos的值从1开始 
bool insert_list(PNODE pHead, int pos, int val); 
bool delete_list(PNODE pHead, int pos, int *pVal);
void sort_list(PNODE pHead); // 对链表进行排序 
 
int main(void)
{
	PNODE pHead = NULL; 
	
	pHead = create_list();
	
	int len = length_list(pHead); 
	printf("链表的长度为：%d\n",len);
	traverse_list(pHead);
	
	sort_list(pHead);
	
	printf("排序后：\n");
	traverse_list(pHead);
	
	
	insert_list(pHead, 6, 66); // 在链表第6个元素之前插入元素 66 
	traverse_list(pHead);
	
	int val; // 保存被删除的元素 
	if (delete_list(pHead, 6, &val)) {
		printf("元素 %d删除成功！\n",val); 
	}else {
		printf("被删除的元素不存在！\n");
	}
	traverse_list(pHead);
	return 0; 
} 

PNODE create_list(void)
{
	// 创建头节点
	PNODE pHead = (PNODE)malloc(sizeof(NODE));
	PNODE pTail = pHead; //尾指针 
	pTail->pNext = NULL; 
	
	int len; // 链表长度 
	int i;
	int val; // 存放输入的节点的数据域 
	
	printf("请输入需要创建的链表的长度：len=");
	scanf("%d",&len);
	
	for(i = 0; i < len; i++)
	{
		printf("请输入第%d个值:",i+1);
		scanf("%d",&val);
		
		// 创建节点
		PNODE pNew = (PNODE)malloc(sizeof(NODE));
		
		pNew->data = val; // 将数据挂在新节点的数据域 
		
		// 将新节点插入到尾节点后面 
		pTail->pNext = pNew;
		pNew->pNext = NULL;
		pTail = pNew;

	}
	return pHead;
}


void traverse_list(PNODE pHead)
{
	// 刚开始 p 指向第一个有效节点 
	PNODE p = pHead->pNext;
	
	while(p != NULL)
	{
		printf("%d \t",p->data);
		p = p->pNext;
	}
	printf("\n"); 
	
	return;
}

bool is_empty(PNODE pHead)
{
	if(NULL == pHead->pNext)
	{
		return true;
	}
	return false;
	
}
int length_list(PNODE pHead)
{
	int length = 0;
	PNODE p = pHead->pNext;
	
	while(p != NULL)
	{
		length ++;
		p = p->pNext;
	}
	return length;
}


void sort_list(PNODE pHead)
{
	int i ,j;
	int len = length_list(pHead);
	
	int temp;
	PNODE p,q; 
	
	for(i = 0,p = pHead->pNext; i<len-1; i++, p = p->pNext)
	{
		for(j = i+1, q = p->pNext; j < len; j++,q = q->pNext)
		{
			if (p->data > q->data)
			{
				//交换 
				temp = p->data;
				p->data = q->data;
				q->data = temp;
			}
		}
		
	}
	
	// 去掉i，j写法 
//	for(p = pHead->pNext; p->pNext != NULL; p = p->pNext)
//	{
//		for( q = p->pNext; q != NULL;q = q->pNext)
//		{
//			if (p->data > q->data)
//			{
//				//交换 
//				temp = p->data;
//				p->data = q->data;
//				q->data = temp;
//			}
//		}	
//	}
	return;
}


// 在pHead所指向链表的第pos个节点的前面插入一个新的节点，该节点的值val，
// 并且pos的值从1开始 
bool insert_list(PNODE pHead, int pos, int val)
{
	int i = 0;
	PNODE p = pHead;
	
	while (NULL != p && i < pos-1)
	{
		p = p->pNext;
		i++;
	}
	if (i > pos-1 || NULL == p)
	{
		return false;
	}
	
	PNODE pNew = (PNODE)malloc(sizeof(NODE));
	pNew->data = val;
	
	pNew->pNext = p->pNext;
	p->pNext = pNew;
	
	return true;	
}


bool delete_list(PNODE pHead, int pos, int *pVal)
{
	int i = 0;
	PNODE p = pHead;
	
	while (NULL != p && i < pos-1)
	{
		p = p->pNext;
		i++;
	}
	// 跳出循环，p指向的是第 pos-1个节点，即待删除节点的前一个节点 
	
	if(i > pos-1 || NULL == p->pNext)
		return false;
	
	
	PNODE q = p->pNext; // 保存要删除的节点
	
	*pVal = q->data;
	p->pNext = 	p->pNext->pNext;
	free(q);
	q = NULL;
	return true;
}