建立一个带头结点的元素值递增有序的单链表(边插入边排序) c语言

清疚 2023-02-20 02:07 83阅读 0赞

## 建立一个带头结点的元素值递增有序的单链表(边插入边排序) c语言 ##

*先申请一个空间，放head指针(指在头结点)，之后定义q,p指针，始终指在头结点(q)和第一个数值  
(p）上,之后随着新数值的加入，通过q,p来调整新数值的位置，之后q,p再次回到原点。等待调整下一个  
数值*

//建立一个带头结点的元素值递增有序的单链表
    #include"stdio.h"
    #include"stdlib.h"
    typedef struct node
    { 
    	int data;
    	struct node *next;//struct node *类型，指向node本身;
    }link;
    
    link *paixu(link * head)
    { 
    	link *t,*p,*q;
    	int x;
    	t=(link *)malloc(sizeof(link));//申请一个放头结点的空间
    	head=t;
    	t->next=NULL;
    	printf("请输入一个数:\t");
    	scanf("%d",&x);
    	while(x!=0)
    	{ 
    		t=(link *)malloc(sizeof(link));
    		t->data=x;
    		q=head;//设置双指针;p在前,q在后;
    		p=head->next;
    		while(p!=NULL&&p->data<=x)
    			/*当p不为空(未到链表末尾),且p所指的数据域小于x，则p赋给q后，p后移。 也就是说，x应该插入到q后p前*/
    		{ 
    			q=p;
    			p=p->next;
    		}
    		q->next=t;//这两句是把t插入到p,q之间;
    		t->next=p;
    		printf("请输入一个数:\t");
    		scanf("%d",&x);
    	}
    	return head;
    }
    
    main()
    { 
    	link *head,*e;
    	head=NULL;
    	e=paixu(head);
    	printf("链表为:\n");
    	   e=e->next;//带头结点的打印
    	while(e!=NULL)
    	{ 
    		printf("%d\t",e->data);
    		e=e->next;
    	}
    	printf("\n");
    }

![运行][2020062120514146.png]

注：循环结束有两个条件：  
(1).p=NULL;  
说明p走到最后面，此时q指向最后节点，p是空的，x应该插入道q后。  
(2).p->data<=x;  
说明x应该插入到q后p前。

注：q->next=t;//这两句是把t插入到p,q之间;  
t->next=p;  
如果是插入第一个数值(也就是p=NULL)的情况，既 将NULL赋给t->next,  
此时新插入的结点就是最后的那个结点。

[2020062120514146.png]: https://img-blog.csdnimg.cn/2020062120514146.png