汽车最好网站建设,基于互联网怎样做网站推广,wordpress中文问题,页面设计公司招聘文章目录 1.链表的概念以及结构2.链表的分类2.1 单向或者双向2.2 带头或者不带头2.3 循环或者不循环2.4 无头单向非循环链表和带头双向循环链表 3.单链表的实现3.1 准备工作3.2 节点的创建3.3 单链表的释放3.4 打印链表3.5 单链表的尾插3.6 单链表的尾删3.7 单链表头删3.8 单链… 文章目录 1.链表的概念以及结构2.链表的分类2.1 单向或者双向2.2 带头或者不带头2.3 循环或者不循环2.4 无头单向非循环链表和带头双向循环链表 3.单链表的实现3.1 准备工作3.2 节点的创建3.3 单链表的释放3.4 打印链表3.5 单链表的尾插3.6 单链表的尾删3.7 单链表头删3.8 单链表的头插3.9 单链表的查找3.10 在pos位置后插入3.11 删除pos位置后的数据 4.代码整合5.顺序表与链表的区别 1.链表的概念以及结构
概念链表是一种物理储存结构上的非连续、非顺序的储存结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链式结构在逻辑上是连续的但是在物理上不一定连续现实中的节点一般都是从堆上申请出来的从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续
2.链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表。
2.1 单向或者双向 2.2 带头或者不带头 2.3 循环或者不循环 2.4 无头单向非循环链表和带头双向循环链表
虽然有这么多的链表结构但是我们实际中最常用的还是两种结构。 无头单向非循环链表
带头双向循环链表
无头单向非循环链表结构简单一般不会单独用来存储数据实际中更多的是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外在笔试中出现较多带头双向循环链表结构最复杂一般用来单独存储数据。实际中使用的链表结构都是带头双向循环链表。另外这个结构虽然复杂但是使用代码实现时反而简单。
3.单链表的实现
3.1 准备工作
定义结构体. 链表的节点只要两个值需要存储一个是数据内容一个是下一个节点的地址。 注意为了更多的使用场景我们可以定义一个宏去去替换数据类型。为了方便我就直接写int的。
typedef struct SListNode
{int data;struct SListNode* next;
}SL;3.2 节点的创建
正常利用malloc创建就好注意要检查内存是否开辟失败。
//动态申请一个节点
SL* BuySListNode(int x)
{SL* tmp (SL*)malloc(sizeof(SL));if (tmp NULL){perror(malloc);exit(-1);}tmp-data x;tmp-next NULL;return tmp;
}3.3 单链表的释放
注意使用二级指针因为我们传递的是一级指针的地址
SL* head NULL;
DestoryList(head);释放时为了释放当前节点我们要在cur指向下一个节点时先保存一下该节点的地址。
//释放
void DestoryList(SL** head)
{SL* cur (*head);while (cur){SL* prev cur;cur cur-next;free(prev);prev NULL;}
}3.4 打印链表
遍历打印就可以了,assert的目的是为了防止有人把空指针传进来。
//打印链表
void PrintList(SL** head)
{assert(head);//assert(*head);SL* cur *head;while (cur){printf(%d , cur-data);cur cur-next;}printf(\n);
}
3.5 单链表的尾插
尾插有两种情况 1.*head为空 直接让*head指向一个新的节点 2.*head不为空 找到当前链表的最后一个节点然后将新创建的节点连接到后面
//单链表尾插
void PushBackList(SL** head,int x)
{assert(head);//防止有人把空指针传进来。if (*head NULL){*head BuySListNode(x);return;}SL* cur *head;SL* tmp BuySListNode(x);while (cur-next){cur cur-next;}cur-next tmp;
}3.6 单链表的尾删
删除存在三种情况 1.只有一个节点了 直接free释放*head要置为NULL 2.不止一个节点 先找到第二个节点然后释放第一个节点将*head指向新的第一个节点。 3.没有节点 直接报错
//单链表尾删
void PopbackList(SL** head)
{assert(head);//防止有人把空指针传进来。assert(*head);SL* cur *head;if (cur-next NULL)//当剩下1个元素时直接释放{free(cur);*head NULL;return;}SL* prev cur;while (cur-next){prev cur;cur cur-next;}free(cur);cur NULL;prev-next NULL;
}3.7 单链表头删
删除存在三种情况 1.只有一个节点了 直接free释放*head要置为NULL 2.不止一个节点 找到最后一个节点和其前一个节点找倒数第二个节点的目的是为了将next置为NULL 3.没有节点 直接报错
//单链表头删
void PopFrontList(SL** head)
{assert(head);//防止有人把空指针传进来。assert(*head);SL* cur *head;if (cur-next NULL)//当剩下1个元素时直接释放{free(cur);*head NULL;return;}SL* next cur-next;free(cur);cur NULL;*head next;
}3.8 单链表的头插
头插有两种情况 1.*head为空 直接让*head指向一个新的节点 2.*head不为空 创建一个新的节点找到当前链表的第一个节点然后将新创建的节点的next指针指向第一个节点。然后让*head指向新的节点
//单链表头插
void PushFrontList(SL** head, int x)
{assert(head);if (*head NULL){*head BuySListNode(x);return;}SL* newnode BuySListNode(x);newnode-next *head;*head newnode;
}3.9 单链表的查找
找到返回节点找不到返回NULL
//单链表的查找
SL* FindSlistNode(SL** head, int x)
{assert(head);assert(*head);SL* cur *head;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}3.10 在pos位置后插入
既然要在pos节点后插入数据那就要保证链表不为NULLpos不为NULL 插入的逻辑就是尾插的逻辑但是这里我们不在需要找节点位置了已经给出pos节点了。
//在pos位置后插入
void InsertList(SL** head, SL* pos, int x)
{assert(head);assert(*head);assert(pos);SL* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}3.11 删除pos位置后的数据
注意两种情况就行了。
//删除pos位置后的节点
void EraseList(SL** head, SL* pos)
{assert(pos);assert(head);assert(*head);if (pos-next NULL)return;else{SL* next pos-next-next;SL* tmp pos-next;pos-next next;free(tmp);tmp NULL;}
}4.代码整合
//list.h
#include stdio.h
#include time.h
#include stdlib.h
#include assert.htypedef struct SListNode
{int data;struct SListNode* next;
}SL;//动态申请一个节点
SL* BuySListNode(int x);//销毁链表
void DestoryList(SL** head);//打印链表
void PrintList(SL** head);//单链表尾插
void PushBackList(SL** head, int x);//单链表尾删
void PopbackList(SL** head);//单链表头删
void PopFrontList(SL** head);//单链表头插
void PushFrontList(SL** head, int x);//单链表的查找
SL* FindSlistNode(SL** head, int x);//在pos位置后插入
void InsertList(SL** head, SL* pos, int x);//删除pos位置后的节点
void EraseList(SL** head, SL* pos);//list.c
#include list.hSL* BuySListNode(int x)
{SL* tmp (SL*)malloc(sizeof(SL));if (tmp NULL){perror(malloc);exit(-1);}tmp-data x;tmp-next NULL;return tmp;
}void DestoryList(SL** head)
{SL* cur (*head);while (cur){SL* prev cur;cur cur-next;free(prev);}}//打印链表
void PrintList(SL** head)
{//assert(*head);SL* cur *head;while (cur){printf(%d , cur-data);cur cur-next;}printf(\n);
}//单链表尾插
void PushBackList(SL** head,int x)
{if (*head NULL){*head BuySListNode(x);return;}SL* cur *head;SL* tmp BuySListNode(x);while (cur-next){cur cur-next;}cur-next tmp;
}//单链表尾删
void PopbackList(SL** head)
{assert(*head);SL* cur *head;if (cur-next NULL)//当剩下1个元素时直接释放{free(cur);cur NULL;*head NULL;return;}SL* prev cur;while (cur-next){prev cur;cur cur-next;}free(cur);cur NULL;prev-next NULL;
}//单链表头删
void PopFrontList(SL** head)
{assert(head);//防止有人把空指针传进来。assert(*head);SL* cur *head;if (cur-next NULL)//当剩下1个元素时直接释放{free(cur);cur NULL;*head NULL;return;}SL* next cur-next;free(cur);cur NULL;*head next;
}//单链表头插
void PushFrontList(SL** head, int x)
{assert(head);if (*head NULL){*head BuySListNode(x);return;}SL* newnode BuySListNode(x);newnode-next *head;*head newnode;
}//单链表的查找
SL* FindSlistNode(SL** head, int x)
{assert(*head);SL* cur *head;while (cur){if (cur-data x){return cur;}cur cur-next;}return NULL;
}//在pos位置后插入
void InsertList(SL** head, SL* pos, int x)
{assert(pos);SL* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}//删除pos位置后的节点
void EraseList(SL** head, SL* pos)
{assert(pos);assert(head);assert(*head);if (pos-next NULL)return;else{SL* next pos-next-next;SL* tmp pos-next;pos-next next;free(tmp);tmp NULL;}
}//test.c
#include list.h//void test1()
//{
// SL* head BuySListNode(1);
// PushBackList(head, 2);
// PushBackList(head, 3);
// PushBackList(head, 4);
// PopFrontList(head);
// PrintList(head);
// PopFrontList(head);
// PrintList(head);
// PopFrontList(head);
// PrintList(head);
// PopFrontList(head);
// PrintList(head);
// DestoryList(head);
//}
//
//void test2()
//{
// SL* head BuySListNode(1);
// PushFrontList(head, 4);
// PushFrontList(head, 2);
//
// SL* tmp FindSlistNode(head, 1);
// printf(tmp:%d\n, tmp-data);
//
// tmp FindSlistNode(head, 100);
// if(tmp!NULL)
// printf(tmp:%d\n, tmp-data);
// DestoryList(head);
//
//}
//
//void test3()
//{
// SL* head NULL;
// PushFrontList(head, 4);
// PushFrontList(head, 2);
// PushBackList(head, 1);
// PushBackList(head, 1);
// PushBackList(head, 1);
// SL* tmp FindSlistNode(head, 2);
// InsertList(head, tmp, 100);
// EraseList(head, tmp);
// PrintList(head);
// DestoryList(head);
//
//}int main()
{test3();return 0;
}5.顺序表与链表的区别
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定 连续随机访问支持O(1)不支持O(N)任意位置插入或者删除 元素可能需要搬移元素效率低 O(N)只需修改指针指向插入动态顺序表空间不够时需要 扩容没有容量的概念应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率高低
