链表直接插入排序

链表直接插入排序,第1张

链表直接插入排序

文章目录
    • 带头结点
    • 不带头结点

带头结点

基本思想:
将带头结点head的链表拆分为:head带一个结点的链表和q带剩余结点的链表,将q中的每个结点逐次插入到head链表中,构成一个带头结点且结点值递增的链表

关键代码:

linkList sort(linkList &head){
	linkList p, q, r, l;
	p = head->next;//将原链表拆分为两个链表,一个head带一个结点,一个q带剩余结点 
	q = p->next;
	p->next = NULL;
	while(q!=NULL){
		p = head;
		r = q->next;
		while(p->next!=NULL){//找到要插入的位置 
			if(p->next->numbernumber){
				p=p->next;
			}else{
				break;
			}
		}
		q->next = p->next;//插入结点 
		p->next = q;
		q = r;//恢复位置 
		l = head;
		int i=0;
		printf("插入第%d个结点后,第一个链表为",++i);
		while(l!=NULL){
			printf(" %d", l->number);
			l = l->next;
		}
		printf("n");
	}
	
	return head; 
}

不带头结点

基本思想:
将不带头结点head的链表拆分为:head指向的一个结点的链表和q带剩余结点的链表,将q中的每个结点逐次插入到head链表中,构成一个不带头结点结点值递增的链表

关键代码:

	linkList Sort(linkList &head){
	linkList p, q, r, l;
	q = head->next;
	head->next = NULL;
	while(q!=NULL){
		p = head;
		r = q->next;
		if(q->numbernumber){//q插入head第一个结点之前 
			q->next = p;
		}else{//q大于等于head第一个结点,从head第二个结点开始比较 
			while(p->next!=NULL){//q插入head中间或最后 
				if(p->next->numbernumber){
					p=p->next;
				}else{
					break;
				}
			}
			q->next = p->next;
			p->next = q;
		}
		q = r;
		l = head;
		int i=0;
		printf("插入第%d个结点后,第一个链表为",++i);
		while(l!=NULL){
			printf(" %d", l->number);
			l = l->next;
		}
		printf("n");
	}
	return head;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5692520.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存