CPP学习之——动态链表的中插法(15.12)

发表于 分类于 ， ， 阅读时长 ≈ 4 分钟

一 概述

  • 中间插法首先假定各个结点是从小到大的顺序排列的，然后我们在中间插入一个新结点，这样会出现两种情况。

二 情况分析

  • 第一种情况是要插入的结点小于等于第一个结点，那么理所当然它要放在第一个结点的前面。比如说我们有2、3、4这样3个数，它们是顺序排列的，我们要将1插到这3个数中，那么我们首先比较第一个数字2。1比2小，那么1就要放到2的前面
  • 第二种情况是插入的结点要比第一个结点大，那么我们就要继续比较下一个结点，直到出现两个情况
    • 一个情况是插入的结点仍然大于下一个结点，但是这个下一个结点已经是尾结点。比如说我们有1、2、3这样3个数，要插入的数字为4。
    • 另一种情况是所要插入的结点小于等于下一个结点，那么我们就要保存下一个结点和前一个结点的地址，然后将新结点插入到它们的中间。比如说我们有1、2、4这样3个数，要插入的数字为3。我们按照由小到大的顺序进行比较，当比较到4时，发现3比4小，那么我们就要将3放到4的前面，具体操作是先保存4和2的位置，然后将3放到4和2的中间

三 过程

  • 我们首先在这个insert函数里建立一个新的结点，然后为这个新结点它的编号和价格赋值
  • 然后我们来判断一下该结点的编号是不是第一种情况，也就是所要插入的结点小于或者等于第一个结点，假如该情况，那么将新结点设置为头结点。因为list已经变成了头结点，所以我们将list它的地址赋给全局的head，然后将list它的next指针指向原先的头结点head
  • 假如不是第一种情况，那么就是第二种情况。我们首先定义一个指针用来保存前一个结点的地址，然后开始一个循环，循环的条件是所要插入的结点编号大于第一个结点的编号，同时还有下一个结点，假如该条件满足，那么将该结点保存到temp中，然后再取下一个结点做同样的判断
  • 假如这个循环不被满足，那么会有两种情况。
    • 第一个情况是所要插入的结点编号大于下一个结点，但是该结点没有下一个结点了，也就是说所要插入的结点编号大于尾结点，因此我们要将插入的新结点作为尾结点，具体操作是用原来的尾结点的next指针指向新的结点list
    • 其他情况则是所要插入的结点编号小于等于下一个结点。那么我们要将新结点插入到下一个结点与前一个结点的中间。前面我们用temp保存了前一个结点的地址，用head保存了下一个下一个结点的地址，因此我们可以用temp的next指针指向新节点list
  • 注意：insert，这里在将新结点list设置为头结点以后，要退出insert函数。否则程序继续往下运行，会将一个结点重复插入

四 示例演示及结果输出

4.1 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
class book 
{
	public:
		int num;
		float price;
		book *next;
};
book *head = NULL;
bool check(string str) 
{
	for (int i = 0; i < (int)str.length(); i++)
	{
		if ((str[i] > '9' || str[i] < '0') && (str[i] != '.'))
			return false;
	}
	return true;
}
book* create() 
{
	book *p1, *p2;
	p1 = new book;
	head = p1;
	p2 = p1;
	cout << "请输入图书的编号，以0结束" << endl;
	string str;
	cin >> str;
	while (!check(str)) {
		cout << "输入的不是数字，请重新输入，按0返回" << endl;
		cin >> str;
	}
	p1->num = atoi(str.c_str());
	//cin>>p1->num;
	if (p1->num != 0) {
		cout << "请输入图书的价格" << endl;
		cin >> str;
		while (!check(str)) {
			cout << "输入的不是数字，请重新输入，按0返回" << endl;
			cin >> str;
		}
		p1->price = atof(str.c_str());
		//cin>>p1->price;
	} else {
		delete p1;
		p2 = NULL;
		p2->next = NULL;
		head = NULL;
		return head;
	}
	while (p1->num != 0) 
	{
		p2 = p1;
		p1=new book;
		cout << "请输入图书的编号，以0结束" << endl;
		cin >> str;
		while (!check(str)) {
			cout << "输入的不是数字，请重新输入，按0返回" << endl;
			cin >> str;
		}
		p1->num = atoi(str.c_str());
		//cin >> p1->num;
		if (p1->num != 0) {
			cout << "请输入图书的价格" << endl;
			cin >> str;
			while (!check(str)) {
				cout << "输入的不是数字，请重新输入，按0返回" << endl;
				cin >> str;
			}
			p1->price = atof(str.c_str());
			//cin >> p1->price;
		}
		p2->next = p1;
	}
	delete p1;
	p2->next = NULL;
	return head;
}
void showbook(book *head)
{
	cout<<endl;
	cout<<"图书信息如下："<<endl;
	while(head)
	{
		cout<<"图书编号："<<head->num<<"\t"<<"图书价格："<<head->price<<endl;
		head=head->next;
	}
}
void Delete(book *head,int num)
{
	book *l;
	if(head->num==num){
		l=head;
		head=head->next;
		::head=head;
		delete l;
		cout<<"操作成功"<<endl;
		return ;
	}
	while(head)
	{
		if(head->next==NULL)
		{
			cout<<"找不到要删除的编号。"<<endl;
			return ;
		}
		if(head->next->num==num)
		{
			l=head->next;
			head->next=l->next;
			delete l;
			cout<<"操作成功"<<endl;
			return ;
		}
		head=head->next;
	}
	cout<<"找不到要删除的编号。"<<endl;

}
void insert(book *head,int num,float price)
{
	book *list=new book;
	list->num=num;
	list->price=price;
	if(num<=head->num)
	{
		list->next=head;
		::head=list;
		return;
	}
	book *temp=NULL;
	while((num>head->num)&&(head->next!=NULL))
	{
		temp=head;
		head=head->next;
	}
	if(num>head->num)
	{
		head->next=list;

	}else
	{
		temp->next=list;
		list->next=head;
	}


}
int main() 
{
	head=create();
	showbook(head);
	cout<<"请输入你要删除的图书编号：";
	int BookNum;
	cin>>BookNum;
	Delete(head,BookNum);
	showbook(head);
	cout<<"请输入您要插入的图书编号：";
	cin>>BookNum;
	cout<<"请输入您要插入的图书价格：";
	float BookPrice;
	cin>>BookPrice;
	insert(head,BookNum,BookPrice);
	showbook(head);
	return 0;
}

4.2 输出结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
请输入图书的编号，以0结束
1
请输入图书的价格
11
请输入图书的编号，以0结束
2
请输入图书的价格
22
请输入图书的编号，以0结束
3
请输入图书的价格
33
请输入图书的编号，以0结束
0

图书信息如下：
图书编号：1	图书价格：11
图书编号：2	图书价格：22
图书编号：3	图书价格：33
请输入你要删除的图书编号：2
操作成功

图书信息如下：
图书编号：1	图书价格：11
图书编号：3	图书价格：33
请输入您要插入的图书编号：2
请输入您要插入的图书价格：22

图书信息如下：
图书编号：1	图书价格：11
图书编号：2	图书价格：22
图书编号：3	图书价格：33