巴中建网站的公司,邹平县建设局网站,站长素材网站官网,交换链接或称互惠链接一、顺序表优缺点 优点#xff1a;我们知道顺序表结构简单#xff0c;便于随机访问表中任一元素#xff1b; 缺点#xff1a;顺序存储结构不利于插入和删除#xff0c;不利于扩充#xff0c;也容易造成空间浪费。 二、链表的定义 ①#xff1a;概念#xff1a; 用一组任…一、顺序表优缺点 优点我们知道顺序表结构简单便于随机访问表中任一元素 缺点顺序存储结构不利于插入和删除不利于扩充也容易造成空间浪费。 二、链表的定义 ①概念 用一组任一的存储单元存储线性表的数据元素可以是连续也可以是不可连续的数据元素之间的逻辑关系借助指示元素存储位置的指针来表示这种存储方式叫做线性表的 链式存储结构 简称 链表 。 ②结点 为了表示数据元素间的逻辑关系除了存储数据本身信息之外还需要存放其直接后继的存储位置地址这两部分数据域和指针域组成一个 结点 用于表示一个元素。 数据域存储数据元素的信息 指针域存放直接后继的元素的地址。 表示图如下 同时还需要注意以下几点 注意我们规定链表的尾结点最后一个结点的指针域为NULL这样可以方便进行操作。 ③单链表的定义 若链表的每个结点只包含一个指针域则称此链表为 线性链表或 单链表。 ④头结点 有时为了操作方便在单链表的第一个结点之前添加一个结点称为 头结点或伪结点。 不带哨兵的头结点就直接使用 带哨兵的头结点就按以下规则 头结点的数据域可以不存放任何信息也可以存放其他特殊信息 头结点的指针域存放第一个结点的存储地址即指向第一个结点 本次小编用的是不带哨兵的头结点。 有头结点的单链表叫做“带头结点的单链表”。 三 、单链表的C语言结构定义 typedef int SLDataType;//方便以后跟改数据类型typedef struct SLisrNode
{SLDataType data;//数据域struct SListNode* next;//指针域
}Lnode, * LinkList;//用typedef重定义后Londe为结点类型,LinkList为指向结点的指针类型 四、单链表基本操作 作几点说明 ①为了方便让大家感受一下单链表所以先实现遍历单链表让大家体会其结构的韵味 ②我们一般都默认用带有头结点的单链表 ③大家一般都会写与控制台有互动的代码但小编这里只是带大家入门上手只是简单实现所以大家可以根据小编的思路自行设计。 ④本次实现小编也是采用多文件操作没听说过的小伙伴可以大致了解一下就几句话意思很简单。 ⑤跟往常不一样的是小编会把详细说明放在注释里面大家请认真解读有疑问或没看懂的欢迎大家评论区讨论。 四.1、遍历单链表 源代码 //遍历单链表
void SLTPrint(SLTNode* phead)
{//一般头指针phead我们都不会动方便我们多次操作//所以我们可以创建一个临时指针来进行操作SLTNode* tmp phead;//因为单链表尾结点的指针域为NULL所以循环条件可以为tmp//当tmp为NULL时说明链表遍历完成并且退出循环while (tmp){//打印数据域打印-只是方便展示链表结构)printf(%d-, tmp-data);//因为指针域指向下一个结点所以可以通过赋值方法找到下一个结点tmp tmp-next;}//方便展示链表结构所以末尾打印一个NULLprintf(-NULL\n);
} 四.2、用malloc函数创建新结点 因为指针phead刚开始创建时并没有指向任何结点需要在程序执行过程中通过按结点的类型向系统申请建立一个新结点通过调用标准函数malloc动态开辟空间生成 即创建一个新结点具体格式如下 phead(SLTNnode*)malloc(sizeof(SLTNode)); 当phead结点不需要时我们应该用free函数释放空间收回结点 因为有多种操作所以我们将这个操作写成一个函数方便后续调用 源代码 //创建新结点
//因为要返回动态申请的结点所以有返回类型
SLTNode* BuySLiseNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//判断是否开辟成功if (newnode NULL){perror(malloc);exit(-1);}//填充数据newnode-data x;newnode-next NULL;//返回return newnode;
} 四.3、尾插法 尾插法顾名思义就是在链表尾部进行插入数据 大致步骤分为两步 ①找到链表尾结点根据尾结点的next域为NULL来作为循环条件进行寻找 ②将新结点链接到尾结点的next域即可 源代码即解释如下 //尾插法
//函数第一个形参是二级指针是存储链表的地址用的传址调用
//函数第二个形参是要插入的数据
void SLTPushBack(SLTNode** pphead1, SLTDataType x)
{//得到一个新结点SLTNode* newnode BuySLiseNode(x);//若链表为空链表则直接将新结点赋值给链表因为我们是传址调用可以改变外面链表的内容if (*pphead1 NULL){*pphead1 newnode;}else{//同理将链表拷贝到一个临时结点中便于操作SLTNode* tmp *pphead1;//①找到尾结点//因为尾结点的next域为NULL所以可以作为循环判断条件while (tmp-next NULL){tmp tmp-next;}//②链接tmp-next newnode;//这里可能有的小伙伴不理解觉得这里不也是直接赋值吗怎么改变外部链表的?//所以大家就要注意一句话如下//1.改变结构体用结构体指针//2.改变结构体指针要用结构体指针的指针二级指针// //上面的pphead就是一个结构体二级指针用于改变结构体指针//但这里的next是结构体成员所以我们只需要改变结构体所以就用结构体指针//而tmp本来就是我们结构头指针拷贝过来的所以改变了tmp的next就相当于改变了外部链表的尾结点的next}//因为tmp、newnode这些都是局部变量函数结束后会自动销毁//第二次又会从初始位置开始操作所以我们不用调整这些变量的值//但链表结点内容不会被销毁因为我们是用malloc函数在堆区上面申请的空间只有free后才会销毁
} 测试结果 void TestList2()
{SLTNode* phead NULL;//头结点,用于链接新结点//尾插100、200、300SLTPushBack(phead, 100);SLTPushBack(phead, 200);SLTPushBack(phead, 300);//打印SLTPrint(phead);}int main()
{//测试
// TestSLTist1();TestList2();return 0;
} 运行结果 四.4、头插法 当我们理解清楚尾插法里面的各种细节后头插以及后面的操作都会觉得很简单 头插大致分为 ①将新结点的next域指向首结点 ②再让头指针指向新结点 源代码及解释如下
//头插法
//形参和尾插法是相同的道理
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{//因为我们每一步都要使用不带哨兵的头结点所以每次都要改变结构体指针// 所以形参用二级指针是必须的并且不用区分链表是否为空//先得到一个新结点SLTNode* tmp BuySLiseNode(x);//①新结点的next域指向首结点tmp-next *pphead;//②头结点指向新结点*pphead tmp;
} 四.5、尾删法 尾删法也涉及到许多细节大家也需要仔细思考 因为我们使用的是不带哨兵的头指针就会涉及改变结构体和改变结构体指针的问题 只要记住 改变next和data域就是改变结构体只需要使用结构体指针 改变头指针就是改变结构体指针这时需要结构体二级指针 尾删法分为三中种情况 ①链表为空 ②链表里面只有一个结点 ③链表里面有两个或两个以上的结点; 具体细节看注释 源代码如下
//头删法
//形参是结构体二级指针因为分为几种情况有一种情况会改变结构体指针
void SLTPopBack(SLTNode** pphead)
{//情况一链表为空则提示删除失败if (*pphead NULL){printf(此链表为空无法删除!\n);return;}//情况二只有一个结点此时需要使用头指针所以要用到二级指针//直接用free释放掉头指针即可因为我们用的是不带哨兵的头指针头指针指向的就是首元素//又因为只有一个元素所以直接释放头指针在将头指针置空即可//if((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//情况三有两个及其以上的结点步骤如下//①定位到尾结点//②释放尾结点//将尾结点的前一个结点的next域置空(所以一定要保存前一结点的地址)//同理先将链表内容拷贝到临时指针中进行操作,因为我们操作的是结构体所以用结构体指针即可实现SLTNode* tmp *pphead;//如果tmp-next-next为NULL说明tmp-next就是尾结点tmp就是尾结点的前一个结点所以就可以进行释放了while (tmp-next-next){tmp tmp-next;}free(tmp-next);tmp-next NULL;}
} 四.6、头删法 头删法比较简单但因为是在头部操作所以每一步都是在改变结构体指针即头指针所以每一步都要用结构体二级指针所以形参是结构体二级指针 头删法只有两种情况 ①链表为空与尾删一样 ②链表不为空这里没有区分一个结点和多个结点是因为我们每一步都要用到结构体二级指针所以两者操作是一样的 具体细节即源代码如下 //头删法
//参数同尾删一样会改变结构体指针所以用结构体二级指针
void SLTPopFront(SLTNode** pphead)
{//情况一链表为空同尾删一样if (*pphead NULL){printf(此链表为空无法删除!\n);return;}//情况二链表不为空//①先将第二个结点的地址即(*pphead-next))保存到临时指针//②再释放头指针即释放首元素)//③再将存放第二个结点地址的临时指针赋给头指针*ppheadSLTNode* nextnode (*pphead)-next;free(*pphead);*pphead nextnode;
}
