单链表
1.顺序表
优点:物理空间连续,支持随机访问
缺点:空间不够就需要扩容,花费时间和空间;插入删除效率低下
2.单链表
优点:按需申请释放空间;插入删除常数时间
缺点:不支持随机访问
3.注意点
(1)在修改指针本身的内容时,也就是改变指针本身存储的地址,我们需要的是二级指针
void list_push_back(struct node** head, type x)
{
struct node* newnode = (struct node*)malloc(sizeof(struct node));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
//这里想改变头结点的地址,让它指向一块新的空间,也就是改变一个*类型的值->于是我们需要**作为形式参数!!
if (*head == NULL)
{
*head = newnode;
}
else
{
struct node* cur = *head;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
}
4.实现
//forward_list s;里面的插入删除:insert_after erase_after
void list_print(struct node* head)
{
struct node* cur = head;
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("n");
}
struct node* buy_newnode(type x)
{
struct node* newnode = (struct node*)malloc(sizeof(struct node));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
return newnode;
}
void list_push_back(struct node** phead, type x)
{
assert(phead);
struct node*newnode = buy_newnode(x);
//这里想改变头结点的地址,让它指向一块新的空间,也就是改变一个*类型的值->于是我们需要**作为形式参数!!
if (*phead == NULL)
{
*phead = newnode;
}
else
{
struct node* cur = *phead;
while (cur->next != NULL)
{
cur = cur->next;
}
cur->next = newnode;
}
}
//也需要传入二级指针:不管有没有元素,都需要改变head的值,因为head必须是指向第一个结点的!!!
void list_push_front(struct node** phead, type x)
{
assert(phead);
struct node* newnode = buy_newnode(x);
newnode->next = *phead;
*phead = newnode;
//验证上下都可以但上面的更加简洁
/*if (*phead == NULL)
{
*phead = newnode;
}
else
{
newnode->next = *phead;
*phead = newnode;
}*/
}
//一级指针不用检查:它可能就是一个空链表
//二级指针需要检查:head是存在的,head有这个变量,那就一定有个地址。phead里面存放的就是head的地址
void list_pop_front(struct node**phead)
{
assert(phead);
assert(*phead);//这里头删,head一定需要有值才可以删除
struct node* pre_head = *phead;
*phead = (*phead)->next;
free(pre_head);//释放它指向的空间
}
void list_pop_back(struct node**phead)
{
assert(phead);
assert(*phead);
struct node* t = *phead;
if (t->next == NULL)
{
free(*phead);
*phead = NULL;
}
else
{
while (t->next->next != NULL)
{
t = t->next;
}
t->next = NULL;
free(t->next);
}
}
struct node* list_find(struct node* head, type x)
{
assert(head);
struct node* t = head;
while (t != NULL)
{
if (t->data == x)
{
return t;
}
t = t->next;
}
return NULL;
}
void list_insert(struct node** phead, struct node* pos, type x)
{
assert(pos);
assert(phead);
if (pos == *phead)
{
list_push_front(phead, x);
}
else
{
struct node* t = *phead;
while (t->next != pos)
{
t = t->next;
}
struct node*newnode = buy_newnode(x);
newnode->next = pos;
t->next = newnode;
}
}
void list_erase(struct node**phead, struct node *pos)
{
assert(phead);
assert(pos);//如果链表为空,pos不可能有效
if (pos == *phead)
{
list_pop_front(phead);
}
else
{
struct node* t = *phead;
while (t->next != pos)
{
t = t->next;
}
t->next = pos->next;
free(pos);
//pos = NULL;//几乎无效?因为pos是个形参,在这里置空无用,交给外面处理
}
}
void list_insert_after(struct node* pos, type x)
{
assert(pos);
struct node * newnode = buy_newnode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void list_erase_after(struct node* pos)
{
assert(pos->next);
struct node* t = pos->next;
pos->next = pos->next->next;
free(t);
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
前言 .Net7里面对于基础类型的优化,是必不可少的。因为这些基础类型基本上都会经常用到,本篇除了基础类型的优化介绍之外,还有一个循环克隆的优化特性,也一并看下。 概括 1.基础类型优化 基础类型的优化有些不会涉及ASM,主要是记忆。 一:double.Par…