网站建设制作费用预算表,小程序数据网,网站建设服务器介绍图片,给公司做网站要多少钱链表是线性表的一种#xff0c;它在逻辑结构上是连续的#xff0c;在物理结构上是非连续的。
也就是说链表在物理空间上是独立的#xff0c;可能是东一块西一块的。如下顺序表和链表在内存空间上的对比#xff1a; 而链表的每一块空间是如何产生联系实现在逻辑结构上是连续…链表是线性表的一种它在逻辑结构上是连续的在物理结构上是非连续的。
也就是说链表在物理空间上是独立的可能是东一块西一块的。如下顺序表和链表在内存空间上的对比 而链表的每一块空间是如何产生联系实现在逻辑结构上是连续的呢
链表的每一块内存称为一个结点(或节点)结点我们用结构体类型的变量来申请空间其中的一个(或多个)成员用来存放有效数据另一个成员来存放下一个结点的地址那样的话我们就可以通过地址访问到下一个结点。
如下 本章只是对链表创建过程的细节和陷阱进行分析解决并不会对链表的各种增删查改进行一一讲解但这些操作会在文章末尾给出原码。
关于一个简单的链表以下是头文件的声明 #pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
typedef int SLDatatype;
typedef struct SLNode
{SLDatatype val;struct SLNode* next;
}SLNode;
void SLN_HeadAdd(SLNode** pphead, SLDatatype x);//插入结点(头插)
void SLN_EndAdd(SLNode** pphead, SLDatatype x);//插入结点(尾插)
SLNode* SLN_Find(SLNode** pphead, SLDatatype x);//查找元素所在的结点
void SLN_fLocAdd(SLNode** pphead, SLNode* Loc, SLDatatype x);//指定位置后插入
void SLN_pLocAdd(SLNode* Loc, SLDatatype x);//指定位置后插入void SLN_Print(SLNode* phead);//打印链表void SLN_HeadDele(SLNode** pphead);//删除结点(头删)
void SLN_EndDele(SLNode** pphead);//删除结点(尾删)
void SLN_LocDele(SLNode** pphead, SLNode* Loc);//指定位置删除void SLN_Free(SLNode** pphead);//销毁链表释放内存细节1成员类型的重命名 在这个声明结点的过程把int类型重命名为SLDatatype后面要改储存的数据类型的话不必再去写的函数中一个一个的修改只需要在重命名这里一次性修改就可以。 然后这里还把 struct SLNode 重命名为SLNode可以方便后面简写。 现在我们来看插入
因为每次插入必然需要申请结点空间很繁琐所以我们来封装一个函数专门用来申请结点空间
如下
SLNode* SLNAdd(SLDatatype x)//x为需要储存的元素
{SLNode* pk (SLNode*)malloc(sizeof(SLNode));assert(pk);pk-val x;pk-next NULL;return pk;
} 头插 陷阱1是否使用二级指针 你真正理解什么情况需要传二级指针参数什么情况不用为什么用吗 对于头插初学者可能会写出下面这样的代码 void SLN_HeadAdd(SLNode* phead, SLDatatype x)
{SLNode* padd SLNAdd(x);if (psNULL)phead padd;else{padd-next phead;phead padd;}
} 可以看出这里对参数phead做了更改如这个表达式 phead padd; 但显然这里phead是临时变量当函数结束后就销毁了而实参并没有任何变化。 注意malloc申请的空间并没有销毁 如何解决 有两个方法 就是把更改后的头结点返回去再用原头结点去接收如下 SLNode* SLN_HeadAdd(SLNode* phead, SLDatatype x)
{SLNode* padd SLNAdd(x);if (pheadNULL)phead padd;else{padd-next phead;phead padd;}return phead;
} 此外还可以通过直接改变原头结点解决即通过对指针的解引用来实现在函数内改变而头结点是一个指向结构体的地址(即一个一级指针)改变它就需要一个二级指针参数来接收头结点的地址然后对这个参数解引用从而达到改变头结点(也就是结构体的地址)的目的。 如下 void SLN_HeadAdd(SLNode** pphead, SLDatatype x)
{SLNode* padd SLNAdd(x);if (*ppheadNULL)*pphead padd;else{padd-next *pphead;*pphead padd;}
} 细节2指针作为形参目的 下面函数实现的是链表的尾删
void SLN_EndDele(SLNode* phead)
{SLNode* ph phead;if (!ph)return;SLNode* pk ph;while (ph-next){pk ph;ph ph-next;}pk-next NULL;free(ph);
} 我们来思考这个函数为什么不用二级指针也不用返回头结点就能完成又为什么不用指针完成不了。注意该过程只对结点的成员进行了改变和结点的销毁而要在一个函数内改变结构体成员是需要得到该成员的地址的而一个一级指针就刚好满足了这个要求的-就相当于得到该成员的地址并且对他它解引用。而这里这个函数用一级指针作为参数的作用真正用于的是以下两部 pk-next NULL; free(ph); 一个是需要改变成员所以需要一级指针另一个是需要释放内存所以需要一级指针没有这两部这个函数的参数完全可以不是指针变量。 例如一个链表的打印函数可以这么写 void SLN_Print(SLNode head)
{while (head.next){printf(%d-, head.val);head *(head.next);}printf(NULL\n);
} 要注意的是这个表达式head *(head.next);因为head.next是struct SLNode* 类型head是struct SLNode类型所以这个需要对head.next解引用。 总结1当一个函数需要改变结点的地址时需要传二级指针(或传一级指针但要返回头结点)。2当一个函数只需要改变结点成员或销毁结点的时候只需要传一级指针。3当一个函数对结点以及成员不做任何改变的时候只需要传一个结构体变量。
注意这里结点指的是结构体的地址。 陷阱2运算符优先级问题 下面是一个关于头插的函数 void SLN_HeadDele(SLNode** pphead)
{assert(pphead);if (*pphead NULL)return;SLNode* ph (*pphead)-next;free(*pphead);*pphead ph;
} 我们要注意的是这个语句 SLNode* ph (*pphead)-next; 在初学者很容易写为 SLNode* ph *pphead-next;但要注意-成员访问运算符的优先级是比解引用操作符的优先级要高的这里要不要忘记用()明确运算的优先。 陷阱3结点前驱丢失问题 在初学者经常犯的一个错误就在对链表进行增删查该等操作过程中常常会把操作的结点后面的结点给弄丢一旦丢失再也无法找到。 例如一个链表的指定结点之后插入结点的函数这样写 void SLN_pLocAdd(SLNode* Loc, SLDatatype x)
{SLNode* padd SLNAdd(x);Loc-next padd;
} 或这么写 void SLN_pLocAdd(SLNode* Loc, SLDatatype x)
{SLNode* padd SLNAdd(x);Loc-next padd;padd-nextLoc-next;
} 两种写法都是错误的第一种写法直接将Loc原本所指向的结点丢失 第二种写法相当于padd-nextpadd;不仅丢失了Loc用来指向的结的还造成打印和尾插等操作的死循环。 正确的写法是 void SLN_pLocAdd(SLNode* Loc, SLDatatype x)
{SLNode* padd SLNAdd(x);padd-next Loc-next;Loc-next padd;
} 陷阱4不可逆向遍历缺陷 要知道链表不可逆向遍历的得到一个结点是无法访问到上一个结点的只能往下访问。所以如果害怕某个结点在遍历过程中丢失的话就需要新的变量来把它储存。 例如一个链表的尾删函数 void SLN_EndDele(SLNode* phead)
{SLNode* ph phead;if (!ph)return;SLNode* pk ph;while (ph-next){pk ph;ph ph-next;}pk-next NULL;free(ph);ph NULL;
} 其中表达式 pk ph; 用变量pk对ph的值进行储存之后再改变ph。 #includeSLNode.h
SLNode* SLNAdd(SLDatatype x)//
{SLNode* pk (SLNode*)malloc(sizeof(SLNode));assert(pk);pk-val x;pk-next NULL;return pk;
}
void SLN_HeadAdd(SLNode** pphead, SLDatatype x)
{assert(pphead);SLNode* ps *pphead;SLNode* padd SLNAdd(x);if (!ps)//相当于if(pkNULL)*pphead padd;else{padd-next ps;*pphead padd;}
}
//SLNode* SLN_HeadAdd(SLNode* phead, SLDatatype x)
//{
// SLNode* ph SLNAdd(x);
// if (phead NULL)
// {
// return ph;
// }
// else
// {
// ph-next phead;
// return ph;
// }
//
//}
void SLN_EndAdd(SLNode** pphead, SLDatatype x)
{assert(pphead);SLNode* ps *pphead;SLNode* padd SLNAdd(x);if (!ps)*pphead padd;else{while (ps-next){psps-next;}ps-next padd;}
}
void SLN_Print(SLNode* phead)
{while (phead){printf(%d-, phead-val);phead phead-next;}printf(NULL\n);
}
//void SLN_Print(SLNode head)
//{
// while (head.next)
// {
// printf(%d-, head.val);
// head *(head.next);
// }
// printf(NULL\n);
//}
SLNode* SLN_Find(SLNode** pphead, SLDatatype x)
{assert(pphead);SLNode* ph *pphead;while (ph){if (ph-val x)return ph;ph ph-next;}return NULL;
}
void SLN_fLocAdd(SLNode** pphead, SLNode* Loc, SLDatatype x)
{assert(pphead);SLNode* ph *pphead;SLNode* pd ph, * padd SLNAdd(x);if (Locph){SLN_HeadAdd(pphead, x);return;}while (ph-next){if (ph Loc){padd-next Loc;pd-next padd;return;}pd ph;ph ph-next;}
}
void SLN_pLocAdd(SLNode* Loc, SLDatatype x)
{SLNode* padd SLNAdd(x);padd-next Loc-next;Loc-next padd;
}
void SLN_HeadDele(SLNode** pphead)
{assert(pphead);if (*pphead NULL)return;SLNode* ph (*pphead)-next;//陷阱free(*pphead);*pphead ph;
}
void SLN_EndDele(SLNode** pphead)
{assert(pphead);SLNode* ph *pphead;if (!ph)return;SLNode* pk ph;while (ph-next){pk ph;ph ph-next;}pk-next NULL;free(ph);ph NULL;
}
//void SLN_EndDele(SLNode* phead)
//{
// SLNode* ph phead;
// if (!ph)
// return;
// SLNode* pk ph;
// while (ph-next)
// {
// pk ph;
// ph ph-next;
// }
// pk-next NULL;
// free(ph);
// ph NULL;
//}
void SLN_LocDele(SLNode** pphead, SLNode* Loc)
{assert(pphead);if (*pphead NULL)return;SLNode* ph*pphead,*pkph;if (Loc ph){SLN_HeadDele(pphead);return;}while (ph){if (ph Loc){pk-next ph-next;free(ph);ph NULL;return;}pk ph;ph ph-next;}
}
void SLN_Free(SLNode** pphead)
{assert(pphead);while (*pphead){SLNode* ph (*pphead)-next;free(*pphead);*pphead ph;}}
