网站建设标准 方案书,saas建站平台,广州seo地址,网课平台线性表顺序存储结构的优缺点
顺序表优点
无须为了表示中间的元素之间的逻辑关系而增加额外的存储空间#xff1b;因为以数组形式存储#xff0c;可以快速地存取表中任一位置的元素。
顺序表缺点
插入和删除操作需要移动大量元素#xff0c;时间复杂度为O(N)#xff1b;…线性表顺序存储结构的优缺点
顺序表优点
无须为了表示中间的元素之间的逻辑关系而增加额外的存储空间因为以数组形式存储可以快速地存取表中任一位置的元素。
顺序表缺点
插入和删除操作需要移动大量元素时间复杂度为O(N)当线性表长度变化较大时难以确定存储空间的容量造成存储空间的“碎片”。
顺序存储结构不足的解决办法
其实顺序表最大的缺点就是插入和删除时需要移动大量元素这显然就需要耗费极大时间因为相邻两元素的存储位置也具有邻居关系。它们编号是1,2,3,...,n它们在内存中的位置也是挨着的中间没有空隙当然就无法快速介入而删除后当中就会留出空隙自然需要弥补。
那这样的话我们反正都要让相邻的元素都留有足够余地那么干脆所有的元素都不考虑相邻位置了哪里有空位就到哪里而只是让每个元素知道他下一个元素的位置在哪里这样我们就可以在第一个元素时就知道第二个元素的位置内存地址而找到它在第二个元素时就知道第三个元素的位置内存地址而找到它。这样所有的元素我们就都可以通过遍历而找到了。
其实这个思路也就是链表存储思路而本篇文章着重讲述链表中的单链表。
线性表链式存储结构定义
在链式结构中除了要存储数据元素信息外还要存储它的后继元素的存储地址。
数据域存储数据元素信息的域称为数据域
指针域存储直接后继位置的域称为指针域。
在指针域中存储的信息称为指针或链。数据域与指针域信息组成数据元素的存储映像称为结点。
单链表n个结点链结成的链表此链表中的每个结点中只包含一个指针域。 单链表的代码实现以及分析
单链表的结构代码
单链表中的结点是由存放数据元素的数据域和存放后继结点地址的指针域组成的。所以假设这个数据为val存放后继结点地址的指针为next。
typedef int SLNDataType;
typedef struct SListNode
{struct SListNode* next;SLNDataType val;
}SLNode;单链表中的每一个节点都是一个结构体成员也就是多个结构体构成了一条链表。这与顺序表不同顺序表由于数组存储 所以就是一个结构体的数组中存储了多个节点。
单链表的遍历打印 void SLTPrint(SLNode* phead)
{assert(phead);SLNode* cur phead;while (cur ! NULL){printf(%d-, cur-val);cur cur-next;}printf(NULL\n);
}
单链表建立新的头结点
在创建新的头结点时需要用到malloc函数关于malloc的使用方法这里不做过多阐述大家有什么不懂的可以点击链接单击即可查看详细学习malloc的使用方法哦。 C库函数中 void *malloc(size_t size) 分配所需的内存空间并返回一个指向它的指针。 malloc是分配内存空间的函数。 SLNode* SLTCreateNode(SLNDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail\n);exit(-1);}newnode-next NULL;newnode-val x;return newnode;
}
单链表的尾插 那如果这是一个空表的话那么就直接让这个单链表为指针指向新创建的节点。 void SLTPushBack(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* Newnode SLTCreateNode(x);if (*pphead NULL){*pphead Newnode;}else{SLNode* tail pphead;while (tail-next ! NULL){tail tail-next;}tail-next Newnode;}
}
单链表的头插 void SLTPushFront(SLNode** pphead, SLNDataType x)
{assert(pphead);SLNode* Newnode SLTCreateNode(x);Newnode-next *pphead;*pphead Newnode;
}
单链表的尾删 void SLTPopBack(SLNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}free(tail-next);tail-next NULL;}
}
单链表的头删 void SLTPopFront(SLNode** pphead)
{assert(pphead);assert(*pphead);SLNode* cur (*pphead)-next;//注意在单链表头删的时候如果只有一个节点那也是可以的就让那个临时的为空free(*pphead);*pphead cur;
}
单链表的查找x数据 SLNode* SLTFind(SLNode* phead, SLNDataType x)
{SLNode* cur phead;while (cur){if (cur-val x){return cur;}else{cur cur-next;}}return NULL;
}
单链表在pos位置插入x的数 SLNode* SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(*pphead);assert(pphead);assert(pos);if (*ppheadpos){SLTPushFront(pphead,x);}else{SLNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLNode* Newnode SLTCreateNode(x);prev-next Newnode;Newnode-next pos;}
}
单链表删除pos位置上的值
void SLTErase(SLNode** pphead, SLNode* pos)
{assert(*pphead);assert(pphead);assert(pos);if (pos *pphead){SLTPopFront(pphead);}else{SLNode* prev *pphead;while (prev-next!pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}
单链表的销毁
void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur){SLNode* tmp cur-next;free(cur);cur tmp;}*pphead NULL;
}
