点击蓝色“五分钟学算法”关注我哟
加个“星标”，一起学算法
1 数组1.1 数组含义
数组：相同元素构成有序的元素集合。数组中存储的元素类型是一致的，数组也是学习编程时最先接触的数据集合。
1.2 存储方式
数组在内存中采用连续的存储方式，也就是说数据在内存中存放是连续的。例如：
当程序执行如下代码：
<pre style="font-size: inherit; color: inherit; line-height: inherit;">`int array[10] //在栈上分配一个有10个int元素的数组
printf("array的地址:%pn", &array);
for(int i = 0; i data = data;//为新节点赋值
tmp->next = node;//将当前节点添加至当前链表末尾
tmp = node;//将当前指向的节点指针指向新节点
printf("请输入一个整数数据n");
scanf("%d", &data);
}
node->next = NULL;
*p = pHead;
return ret;
}
`</pre>
4.2 单链表遍历
单链表的遍历十分简单，只需从链表头开始，沿着指针指向顺序依次输出元素即可。
遍历过程：
遍历程序：
<pre style="font-size: inherit; color: inherit; line-height: inherit;">`void traverse_List(Node* pHead) {
Node* pCur;//创建用于遍历链表的指针
if(pHead == NULL || pHead->next == NULL) {
printf("LinkList is NULLn");//表为空
}
pCur = pHead;//将pCurrent指向头节点
while(pCur->next) { //当前节点不为最后的节点
printf("%d ", pCur->next->data);//输出数据值
pCur = pCur->next;//将当前节点指针后移，指向下一个节点
}
}
`</pre>
4.3 单链表查找
单链表的数据查找需要遍历整个链表，在遍历过程中，将节点数据与查找数据比较。
查找程序：
<pre style="font-size: inherit; color: inherit; line-height: inherit;">`//查找数据为value的节点
Node find_List(Node pHead, int value){
Node *pTmp; //遍历链表指针
if(pHead == NULL || pHead->next == NULL) {
printf("Node is NULLn");
return NULL;
}
pTmp = pHead;
while(pTmp->next) {//遍历链表
printf("%d ", pTmp->next->data);
if(pTmp->next->data == value){//判断值是否相等
pTmp = pTmp->next;//查找到目标节点
return pTmp; //返回目标节点
}
pTmp = pTmp->next;//继续向下查找
}
return NULL;//查找失败
}
`</pre>
4.4 单链表插入
插入过程：
插入过程插入代码：
<pre style="font-size: inherit; color: inherit; line-height: inherit;">`//p节点后插入值为i的节点
void insert_Node(Node *p, int i){
Node* node = new Node;
node->value = i;
node->next = p->next;
p->next = node;
}
`</pre>
4.5 单链表删除
删除过程：
删除过程
删除代码：
4.6 单链表逆序
单链表逆序是笔试题中出现频率较高的考点。逆序即将当前链表顺序进行反转。
逆序：
逆序过程：
逆序代码：
<pre style="font-size: inherit; color: inherit; line-height: inherit;">`//单链表逆序
void reverseLinkList(Node* pHead) {
Node* pPre = NULL;//指向当前节点的上一个节点
Node* pCur = NULL;//指向当前节点的指针
Node* pTmp = NULL;
if(pHead == NULL || pHead->next == NULL || pHead->next->next == NULL) {
return;
}
pPre = pHead->next;
pCur = pHead->next->next;
while(pCur) {//遍历整个链表
//交换顺序，实现逆序
pTmp = pCur->next;
pCur->next = pPre;
pPre = pCur;
pCur = pTmp;
}
pHead->next->next = NULL;
pHead->next = pPre;
}
`</pre>
5 总结
单链表优缺点：
优点：
1：插入、删除操作不需移动其他元素, 只需改变指针。
2：链表各个节点在内存中空间不要求连续，空间利用率高。
缺点：
1：访问数组元素效率低
原 创 热 文推 荐
☞
你点的每个“在看”，我都认真当成了喜欢