单链表删除元素最大的节点 |
您所在的位置：网站首页 › 单链表删除数据元素中的元素会消失吗对吗 › 单链表删除元素最大的节点 |
单链表删除元素最大的节点
|
构思: 单链表是单向的, 要删除最大的节点 ,就需要通过遍历和比较, 从头指针对链表进行便利, 然后每遍历一个节点, 就与最大的结点 进行比较, 如果比最大的节点大, 那就把她当成最大节点, 直到 遍历到最后一个结点 , 我们就找到最大的节点了, 然后开始进行删除操作 , 那怎么删除节点呢? 把最大节点的前一个节点的尾指针指向, 最大节点的后一个节点 因为最大节点的尾指针存放着其下一个节点, 所以 , 我们只需要知道最大节点的前一个节点 和最大节点就可以了 现在开始定义 , LinkList *p ; //新节点 LinkList *pre; //新节点的前一个节点 LinkList *maxp; //最大节点 LinkList *maxpre; //最大节点的前一个节点
初始的时候 , 最大的结点就是第一个节点 , 最大节点前一节点就是头节点 p=L->next; pre = L; map = p; maxpre = pre; 接着往下走:
开始遍历节点: 从左到右 , 前一节点往后指向 新节点 , 新节点往后遍历 pre = p; p = p->next; 然后, 我们就取到了第二个节点了, (因为默认第一个节点是最大的) 如果 新节点比最大节点大 , 那么就需要把 最大节点和最大节点的前一节点的指针指向新节点 if(maxp ->data < p->data) { maxp = p; maxpre = pre; }
然后什么时候结束呢? 当新节点 p 是空的时候结束, while(p!=NULL) 现在已经找到了最大的节点, 下面就把最大节点前后的节点链接起来, 然后释放最大节点的空间就可以了 maxpre ->next = maxp ->next; free(maxp); 代码如下: void delmaxnode(LinkList *&L) { LinkList *p = L->next,*pre = L,*maxp=p,*maxpre=pre; while(p!=NULL){ if(maxp->datadata){ maxp = p; maxpre = pre; } pre = p; p=p->next; } maxpre->next=maxp->next; free(maxp); } 测试源代码: #include #include typedef int ElemType; typedef struct LNode //定义单链表结点类型 { ElemType data; struct LNode *next; //指向后继结点 } LinkList; void CreateListF(LinkList *&L,ElemType a[],int n);//头插法建立单链表 void CreateListR(LinkList *&L,ElemType a[],int n);//尾插法建立单链表 void DestroyList(LinkList *&L); //销毁单链表 void DispList(LinkList *L); //输出单链表 void delmaxnode(LinkList *&L); //删除内容最大的节点 int main() { LinkList *L1, *L2; ElemType a[8]= {1,2,3,4,5,6,7,8}; CreateListF(L1, a, 8); printf("头插法建表结果："); DispList(L1); CreateListR(L2, a, 8); printf("尾插法建表结果："); DispList(L2); delmaxnode(L1); printf("L1删除最大节点的结果:"); DispList(L1); delmaxnode(L2); printf("L2删除最大节点的结果:"); DispList(L2); DestroyList(L1); DestroyList(L2); return 0; } void CreateListF(LinkList *&L,ElemType a[],int n)//头插法建立单链表 { LinkList *s; int i; L=(LinkList *)malloc(sizeof(LinkList)); //创建头结点 L->next=NULL; for (i=0; idata=a[i]; s->next=L->next; //将*s插在原开始结点之前,头结点之后 L->next=s; } } void CreateListR(LinkList *&L,ElemType a[],int n)//尾插法建立单链表 { LinkList *s,*r; int i; L=(LinkList *)malloc(sizeof(LinkList)); //创建头结点 L->next=NULL; r=L; //r始终指向终端结点,开始时指向头结点 for (i=0; idata=a[i]; r->next=s; //将*s插入*r之后 r=s; } r->next=NULL; //终端结点next域置为NULL } void DestroyList(LinkList *&L) //销毁单链表 { LinkList *p=L,*q=p->next; while (q!=NULL) { free(p); p=q; q=p->next; } free(p); //此时q为NULL,p指向尾结点,释放它 } void DispList(LinkList *L) //输出单链表 { LinkList *p=L->next; while (p!=NULL) { printf("%d ",p->data); p=p->next; } printf("\n"); } void delmaxnode(LinkList *&L) { LinkList *p = L->next,*pre = L,*maxp=p,*maxpre=pre; while(p!=NULL){ if(maxp->datadata){ maxp = p; maxpre = pre; } pre = p; p=p->next; } maxpre->next=maxp->next; free(maxp); } 测试结果:
|
【本文地址】
今日新闻 |
推荐新闻 |