怎么什么软件可以吧做网站,模板性公司网站图片,长沙做网站公司哪家好,做淘宝导航网站顺序表的优缺点
缺点#xff1a; 中间/头部的插入删除#xff0c;时间复杂度效率较低#xff0c;为O(N) 空间不够的时候需要扩容。 如果是异地扩容#xff0c;增容需要申请新空间#xff0c;拷贝数据#xff0c;释放旧空间#xff0c;会有不小的消耗。 扩容可能会存在…顺序表的优缺点
缺点 中间/头部的插入删除时间复杂度效率较低为O(N) 空间不够的时候需要扩容。 如果是异地扩容增容需要申请新空间拷贝数据释放旧空间会有不小的消耗。 扩容可能会存在空间浪费。 增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。
优点
尾差尾删足够快。下标的随机访问和修改足够快。
链表的初步认知
针对顺序表的缺点链表就被设计出来了。 链表的特点即按需申请释放。 当我们需要一块空间时我们就申请一块空间。当我们需要添加数据时就继续增加一个一个小块。 主要是就是一个一个小块之间的连接。为了方便连接和管理每一个结点中都存有一个指针用于指向下一个结点。正式一个一个“链接”起来所以叫做链表。
下面图中主要标识了顺序表和链表的逻辑结构的不同。 对于顺序表我们只需要知道指向这块内存空间的指针即可。 但是对于链表我们仅仅知道指向第一块内存空间的指针是不够的因为一块与一块之间没有连接。所以对于每一块都必须存有指向下一块空间的指针。 定义单链表的结构
链表的逻辑图 链表的物理图
//Single List Table
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;//SLTNode* next 是不可以的
}SLTNode;下面我们再来写一个打印单链表的的函数。
void PrintSList(SLTNode* phead)
{SLTNode* p phead;while (p ! NULL){printf(%d , p-data);pp-next;}printf(NULL\n);
}然后接下来我们再来在主函数中自己建一个单链表其实也就是开辟几个结点的空间然后使得结点之间可以“链接”起来即可。
int main()
{SLTNode* n1 (SLTNode*)malloc(sizeof(SLTNode));n1-data 1;SLTNode* n2 (SLTNode*)malloc(sizeof(SLTNode));n2-data 2;SLTNode* n3 (SLTNode*)malloc(sizeof(SLTNode));n3-data 3;n1-next n2;n2-next n3;n3-next NULL;PrintSList(n1);
}由上图我们可以知道代码的逻辑。
动态分配内存创建3个 SLTNode 类型的节点并将其地址赋值给指针 n1、n2、n3。然后将3个结点的next字段都赋值。然后将链表链接起来。 n1-next n2;将节点 n1 的 next 指针指向节点 n2表示 n1 的下一个节点是 n2。n2-next n3;将节点 n2 的 next 指针指向节点 n3表示 n2 的下一个节点是 n3。n3-next NULL;将节点 n3 的 next 指针设置为 NULL表示链表到此结束。 最后打印链表。 我们进行逐语句调试在监视窗口中观察n1,n2,n3的变化。 我们可以看出来n1、n2 和 n3 的物理地址并不连续。 根据结构体的定义我们可以计算出结构体的大小。 如果内存连续地址应该是 而根据我们的监视信息并非连续这正是因为在代码中使用了 malloc 动态分配内存。 malloc 从堆中分配内存而堆内存的分配通常是非连续的具体取决于系统内存分配器的实现和当前堆内存的使用情况。因此动态分配的内存块通常在物理地址上是分散的。 这一篇小博客我们认识链表下面我们将接着实现链表。 加油
