当前位置: 首页 > news >正文

专业做网站电话品牌设计公司

专业做网站电话,品牌设计公司,浙江品牌网站建设,武汉网站制作怎么做文章目录 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节点后插入数据,那就要保证链表不为NULL,pos不为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.h>typedef 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.h"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;
}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)
只需修改指针指向
插入动态顺序表,空间不够时需要
扩容
没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率
http://www.ritt.cn/news/20472.html

相关文章:

  • 门户类网站是什么意思手机推广app
  • 用php做美食网站肇庆seo按天计费
  • 做个电商网站和app互联网推广怎么找渠道
  • 如何做魔道祖师网站360优化大师官方免费下载
  • wordpress透明主题下载seo关键词优化软件官网
  • 做尽调需要用到的网站上海搜索引擎优化seo
  • 国际设计师网站有哪些百度客服人工电话多少
  • 中小企业网站制作多少钱爱站网长尾关键词挖掘工具福利片
  • 阜阳网站设计嵌入式培训班一般多少钱
  • 云南省交通投资建设集团有限公司网站网站域名注册
  • wordpress thecorporationthemeseo sem是什么职位
  • 金属加工网站怎么做seo流量排名工具
  • 公司运营策划方案广州百度seo优化排名
  • 长沙做推广的公司有多少白帽seo是什么
  • 软件开发公司网站模板百度推广工作好干吗
  • 门户网站建设情况汇报最新新闻热点事件
  • 构建一个网站需要什么网上推广app怎么做
  • 中国高清vpswindows在线观看杭州seo的优化
  • 网站必须实名认证吗发稿平台
  • 如何删除在凡科上做的网站seo推广哪家好
  • 三亚河北建设招聘信息网站外贸网站优化
  • 网站营销是什么济宁seo公司
  • 网站空间流量查询焦作关键词优化排名
  • 大兴网站定制开发网络营销工程师培训
  • dede 网站地图 模块如何自己开发软件app
  • 做网站和做软件一样吗网络优化的三个方法
  • 新网站一天做多少外链宁波网络推广方式
  • 做网站大连2023广东最新疫情
  • 自己做的网站网页滑动不网络广告文案
  • .我爱你 网站上海网络营销有限公司