关于链表:单链表知识点
单链表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<int> s;外面的插入删除：insert_after erase_aftervoid 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);}