插入有序的单链表(要求插入后元素有序排列)

问题引入：

某校实验室有一批计算机，按其价格从低到高的次序构成了一个单链表存放，链表中每个结点指出同样价格的若干台。现在又增加m台价格为h元的计算机，编程实现实验室计算机单链表中增加计算机的算法。

分析

这和插入排序的思想有点类似，我们直接在每次插入的时候都按照主关键字(即价格price)的顺序插，这样每次插入后都是有序的。

算法实现：

typedef struct node {
	double price;//价格
	int count;//数量
	struct node *next;
}*SLNode;

//插入函数
void Insert(SLNode head, double price, int count)
{
	SLNode p, q,r;
	p = head->next;
	q = head;
	while (p != NULL) {
		if (p->price == price) {//已存在就增加数量
			p->count += count;
			return;
		}
		else if (p->price > price) {//找到合适的插入位置
			r = (SLNode)malloc(sizeof(struct node));
			r->price = price;
			r->count = count;
			  r->next=q->next;
			q->next = r;
			return;
		}
		else if(p->price<price){
			q=p;//q始终指向p的前驱
			p = p->next;
		}
	}
	//走到这里说明，表中没有比要插入的price还要大的结点
	//直接接在链表表尾就行
	r = (SLNode)malloc(sizeof(struct node));
	r->count = count;
	r->price = price;
	r->next = NULL;
	q->next = r;
	return;
}

完整代码(VS2017)

LNode.h

#pragma once
typedef struct node {
	double price;//价格
	int count;//数量
	struct node *next;
}*SLNode;
//初始化
void Initiate(SLNode *head) {
	 *head = (SLNode)malloc(sizeof(struct node));//申请头结点
	(*head)->next = NULL;
}
//插入函数
void Insert(SLNode head, double price, int count)
{
	SLNode p, q,r;
	p = head->next;
	q = head;
	while (p != NULL) {
		if (p->price == price) {//已存在就增加数量
			p->count += count;
			return;
		}
		else if (p->price > price) {//找到合适的插入位置
			r = (SLNode)malloc(sizeof(struct node));
			r->price = price;
			r->count = count;
			  r->next=q->next;
			q->next = r;
			return;
		}
		else if(p->price<price){
			q=p;//q始终指向p的前驱
			p = p->next;
		}
	}
	//走到这里说明，表中没有比要插入的price还要大的结点
	//直接接在链表表尾就行
	r = (SLNode)malloc(sizeof(struct node));
	r->count = count;
	r->price = price;
	r->next = NULL;
	q->next = r;
	return;
}
//打印链表所有结点的数据元素
void print(SLNode head)
{
	SLNode p = head->next;
	printf("价格\t\t数量\n");
	while (p != NULL)
	{
		printf("%lf\t%d\n", p->price, p->count);
		p = p->next;
	}
}
//撤销单链表的申请空间
void Destroy(SLNode head)
{
	SLNode q;
	SLNode p = head->next;
	while (p) {
		q = p;
		p = p->next;
		free(q);
	}
	head = NULL;
}

test.cpp

#include<stdio.h>
#include<windows.h>
#include"LNode.h"
#include<malloc.h>
#include<stdlib.h>
int main() {
	SLNode head;
	Initiate(&head);
	for (int i = 0; i < 10; i++)
	{
		Insert(head,i+1,i+2);
	}
	print(head);
	Insert(head, 10, 10);
	print(head);
	system("pause");
	return 0;
}

运行结果:

第一次插入10个结点，第二次还是插入价格为10的结点，但由于链表已经有price=10的结点了，直接给那个结点的数量增加count就行(题目要求)。注意圈起来两处的数量

PS:

我竟然改bug改了好久，最后才发现自己竟然卡在了一个逻辑问题上，唉，最近这状态下滑，插入排序都能卡住，醉了，但是改好之后是真的舒服。