上篇谈了谈尾插法和头插法,这篇谈谈中间插入元素和删除。
1、中间插入元素
既然谈到了要从中间插入那就得确定插入的位置是否合法了,我总不能链表总长为5,但是插入的位置是60,这就不对了。所以得先确定这个链表的长度为多少。这个比较简单,就是在寻找尾部的过程中计数,直到走到最后一个节点。
代码如下:
int Get_Length(LinkList header) { LinkList p = header->next; int i = 0; while(p != NULL) { p = p->next; i++; } return i; }
头结点记为0,首元结点开始计数为1,再往后就是2,3,4等等。
在确定了链表长度以后,就得开始想办法往里插入元素了,方法如图。
从这儿就已经可以看出和头结点有异曲同工之妙了。
思路又来了:
①新建一个结点。(老规矩)
②找到一个结点,然后准备将新结点放在这个结点后面。
③开始插入新结点:改变找到的结点的next的指针,将其指向新结点,然后将新结点的next指向找到的结点的原next。(有些拗口,结合图片应该是好理解些)
下面开始写代码,咱们现在①和③都明白,主要是这个找该怎么整,简单想一想就是想找的位置和遍历的当前位置是否相等,这也算是增删改查的查了。
代码如下:(对越界行为做特殊处理)
LinkList Search_Site(LinkList header, int site_) { int i = 1; LinkList p = header->next; if(site_ == 0) { return header; } if(site_ > Get_Length(header)) { printf("more than now.\n"); return NULL; } if(site_ >= 1 && site_ <= Get_Length(header)) { while(site_ != i) { p = p->next; i++; } } return p; }
文章来源地址https://www.toymoban.com/news/detail-548567.html
先对上述函数进行验证main函数如下:
int main() { printf("This is Struct_Data:\n\n"); LinkList head = Init_linklist(); AddLetter_Tail(head,'H'); AddLetter_Tail(head,'i'); AddLetter_Tail(head,','); AddLetter_Tail(head,'L'); AddLetter_Tail(head,'i'); AddLetter_Tail(head,'n'); AddLetter_Tail(head,'u'); AddLetter_Tail(head,'x'); AddLetter_Tail(head,'.'); PrintList(head); printf("len: %d\n",Get_Length(head)); printf("Search2:%c \n",Search_Site(head,2)->letter); printf("search9:%c \n",Search_Site(head,9)->letter); printf("search1:%c \n",Search_Site(head,1)->letter); printf("search3:%c \n",Search_Site(head,3)->letter); printf("\n"); printf("len: %d\n",Get_Length(head)); return 0; }
效果如下:
发现没有毛病٩(๑❛ᴗ❛๑)۶
在链表中间加入新元素:
void Add_Inster(LinkList header, int site_, char letter_) { LinkList p = Search_Site(header,site_); LinkList q = (LinkList)malloc(sizeof(LNode)); q->letter = letter_; q->next = p->next; p->next = q; }
main函数如下:(在4,4,9的位置插入元素)
int main() { printf("This is Struct_Data:\n\n"); LinkList head = Init_linklist(); AddLetter_Tail(head,'H'); AddLetter_Tail(head,'i'); AddLetter_Tail(head,','); AddLetter_Tail(head,'L'); AddLetter_Tail(head,'i'); AddLetter_Tail(head,'n'); AddLetter_Tail(head,'u'); AddLetter_Tail(head,'x'); AddLetter_Tail(head,'.'); PrintList(head); printf("len: %d\n",Get_Length(head)); printf("Add_Inster 4,4,9\n "); Add_Inster(head,4,'-'); Add_Inster(head,4,'?'); Add_Inster(head,9,'<'); PrintList(head); printf("len: %d\n",Get_Length(head)); return 0; }
效果如下:
2、下面就是删除操作了,这个有一丢丢麻烦,因为要抹掉链表中的一个结点,那就涉及指针重新指向和释放内存(因为新建结点是申请出来的,不要它的话自然就得free掉了)了。
先看图,主观上就是找到这个结点扔掉,然后再续上。仔细一想会出现问题,比如我想删掉C,也就是第三个,找到之后应该利用第二个指向第四个,但是我们不知道第二个的地址,所以要想删除第三个得寻找到第二个然后再改变指针指向。
代码如下:
void Delete(LinkList header,int site_) { if(site_ < 1 || site_ > Get_Length(header)) { printf("delete error.\n"); return; } else { LinkList p = Search_Site(header,site_ - 1); LinkList q = p->next; p->next = q->next; free(q); } }
main函数代码如下:(删除第6,3,2,1位)
int main() { printf("This is Struct_Data:\n\n"); LinkList head = Init_linklist(); AddLetter_Tail(head,'H'); AddLetter_Tail(head,'i'); AddLetter_Tail(head,','); AddLetter_Tail(head,'L'); AddLetter_Tail(head,'i'); AddLetter_Tail(head,'n'); AddLetter_Tail(head,'u'); AddLetter_Tail(head,'x'); AddLetter_Tail(head,'.'); PrintList(head); printf("len: %d\n",Get_Length(head)); printf("Delete 6,2,3,1\n"); Delete(head,6); Delete(head,2); Delete(head,3); Delete(head,1); PrintList(head); printf("len: %d\n",Get_Length(head)); return 0; }
效果图如下:
这篇顺便把查也谈了一下,下一篇谈谈最后一个改,比较简单,就是查到然后改掉就可以了。
总结:①中间插入元素的方法和头插法有些类似,可以做类比对比,但是要注意是否越界问题。
②这些顺序都不是死的,只是程序上要多些步骤保存一下地址而已,好比删除,也可以先释放内存,前提是先保存好地址,避免找不到next。
以上只是本人的理解和所见,如有不同见解和看法,欢迎在评论区批评指正。文章来源:https://www.toymoban.com/news/detail-548567.html
到了这里,关于C语言:数据结构之单链表(三)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!