动态链表数据结构(头插法和尾插法)

动态链表

---

链表的概念:

a)如果结构体成员变量中有指向同类节点的指针变量，那么就能够将一个个的结构具体的变串连起来，这样的一系列节点形象上像一条链子，我们称之为链表。
b)每个节点都是有2部分组成：数据区+地址区（指向自身结构体的指针变量）
c)其中指向自身类型节点的指针，我们称之为地址域。
b)最后一个节点没有下一个节点，地址域赋值为NULL。

---

链表特征：

1、（单）链表：必须有链表头pHeader;
2、通过链表头，可以顺次向下访问所有节点。
3、如果是空链表链表头为0，pHeader=NULL;
3、链表尾节点：类似于null结尾的字符串，最后一个节点的指针pNext==0;
4、可以在任意位置插入和删除节点。

---

一、 链表插入方法

向头插入节点（头插法）

1、新插入的节点的后继是什么？
2、g_pHead指向的是什么？

向尾插入节点（尾插法）

尾插法：
1、原尾节点的后继是什么？
2、新插入节点的后继是什么？

二、代码书写

#include <stdio.h>
#include<stdlib.h>
#include <string.h>
typedef double DATA;
struct SNode
{
	DATA data;
	struct SNode* pNext;
};  //动态链表 就是在堆上
struct  SNode* g_pHead = NULL;

void ADDHead(DATA d) //头插 从小到大 最早插入的在尾部
{
	struct SNode* p = (struct SNode*)malloc(sizeof(SNode));       //申请一个新的节点
	if (!p)
		return;  //判断p是否为空
	p->data = d;
	p->pNext = g_pHead;  //它里面存放的就是它要的数据 要来第一个节点位置
	g_pHead = p;	//新的头 ，打印从心头开始
}
void ADDTail(DATA d) //尾插
{
	struct SNode* p = (struct SNode*)malloc(sizeof(SNode));       //申请一个新的节点
	if (!p)
		return;  //判断p是否为空
	p->data = d;
	p->pNext = NULL;
	if (g_pHead == NULL)  //第一次
	{
		g_pHead = p;
		return;
	}//第二次以后类似于 strcat找尾巴的过程
	struct SNode* pTail = g_pHead;
	while (pTail->pNext != NULL)
		pTail = pTail->pNext; //不可以用p++ 因为的地址空间不是连续的 链式偏移
	pTail->pNext = p;

}
void Print()
{
	int sum = 0;
	struct SNode* p = g_pHead;
	while (p) //p!=NULL
	{
		printf(" %-6.2f ", p->data);
		p = p->pNext; //递增区
		sum++; //统计
	}
	printf("总共有%d条数据\n", sum);
}
int Remove(DATA d)
{
	//循环
	struct SNode* p = g_pHead;
	while (p)
	{
		if(p->data == d)
		{
			p->pNext = p->pNext->pNext;
			free(p->pNext); //不能直接free 要先上下2个节点连接起来再free
			return 1;
		}
		p = p->pNext;
	}
	return 0; //False 删除失败没有这个数据
}
int main()
{
	double d = 5;
	Print();
	while (--d>0)
	{
		ADDTail(d * 13 / 11);
	}
	Print();
	Remove(2.0 * 13 / 11);
	Remove(3.0 * 13 / 11);

	Print();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

更新版本

#include <stdio.h>
#include <stdlib.h>
typedef double DATA;

struct SNode
{
   DATA data;
   struct SNode* pNext;
};
struct SNode* g_pHead = NULL;
void AddHead(DATA d)
{//头插
   struct SNode* p = (struct SNode*)malloc(sizeof(SNode));
   if (!p)
   	return;
   p->data = d;
   p->pNext = g_pHead;//要来第一个节点位置
   g_pHead = p;//新的头，打印从新头开始
}
void AddTail(DATA d)
{//尾插
   struct SNode* p = (struct SNode*)malloc(sizeof(SNode));
   if (!p)
   	return;
   p->data = d;
   p->pNext = NULL;
   if (g_pHead == NULL)
   {	//第一次
   	g_pHead = p;
   	return;
   }
   //第二次以后 类似strcat找尾巴的过程
   struct SNode* pTail = g_pHead;
   while (pTail->pNext)//!= NULL
   	pTail = pTail->pNext;//不可以用p++; 链式偏移 
   pTail->pNext = p;
   
}

void Print()
{
   int sum = 0;
   struct SNode* p = g_pHead;
   while (p)//p != NULL
   {
   	printf("%-6.2f", p->data);

   	p = p->pNext;//能不能理解:不能用p++
   	sum++;
   }
   printf("总共有 %d 条数据\n", sum);
}
//int Remove(DATA d)
//{//循环遍历
//	struct SNode* p = g_pHead, * q = NULL;
//	while (p)//p != NULL
//	{
//		p = p->pNext;
//		free(p);//不能直接free，要先上下2个节点连起来再free
//		return 1;//true
//		
//		q = p;//前一个
//		p = p->pNext;//下一个
//	}
//	return 0;//false 删除失败，没有这个数据
//}
int Remove(DATA d)
{//循环遍历
   struct SNode* p = g_pHead,*q = NULL;
   while(p)//p != NULL
   {
   	if (p->data == d)
   	{
   		if(p == g_pHead)
   			g_pHead = p->pNext;//删除头
   		else
   			q->pNext = p->pNext;//中间和尾部都对
   		free(p);//不能直接free，要先上下2个节点连起来再free
   		return 1;//true
   	}
   	q = p;//前一个
   	p = p->pNext;//下一个
   }
   return 0;//false 删除失败，没有这个数据
}
//int Remove(DATA d)
//{//循环遍历
//	struct SNode* p = g_pHead, * q = NULL;
//	while (p)//p != NULL
//	{
//		if (p->data == d)
//		{
//			if (q)
//				q->pNext = p->pNext;//中间和尾部都对
//			else
//				g_pHead = p->pNext;//删除头
//			free(p);//不能直接free，要先上下2个节点连起来再free
//			return 1;//true
//		}
//		q = p;//前一个
//		p = p->pNext;//下一个
//	}
//	return 0;//false 删除失败，没有这个数据
//}
int main()
{
   double d = 6;
   Print();
   while (--d > 0)
   {
   	AddHead(d * 13 / 11);
   }
   Print();
   Remove(5.0 * 13 / 11);
   Print();
   return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118