devbox
很楠不爱3
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

北邮22信通：（6）实验1 题目三 ：通讯录管理_数据结构实验利用线性表实现通讯录管理

作者：很楠不爱3 | 2024-05-12 14:44:44

赞

踩

数据结构实验利用线性表实现通讯录管理

北邮22信通一枚~   

跟随课程进度每周更新数据结构与算法的代码和文章 

持续关注作者  解锁更多邮苑信通专属代码~

获取更多文章  请访问专栏：

北邮22信通_青山如墨雨如画的博客-CSDN博客

目录

1. 实验要求：

2   程序分析：

2.1存储结构：

​编辑2.2关键算法分析：

        2.2.1.关键算法：

        2.2.2.代码详细分析：

3.完整代码

4.程序运行结果

1. 实验要求：

利用线性表实现一个通讯里管理系统，通讯录的数据格式如下：

Struct  datatype

{

       int ID;

char name[10];

char ch;

char phone[13];

char addr[31];

}

***编者注：为了实现更多功能，编者已将数据域扩展成了类***

要求：

实现通讯录的建立，增加，删除，修改，查询等功能；

能够实现简单的菜单交互，可以根据用户输入的命令选择不同的操作；

能够保存每次更新的数据；

编写main（）函数测试线性表的正确性；

2   程序分析：

2.1存储结构：

单链表：

2.2关键算法分析：

        2.2.1.关键算法：

                通讯录的增加数据、删除数据、修改数据、查询数据、打印数据、获得长度功能。

        2.2.2.代码详细分析：

                2.2.2.1单链表增加数据：

                        2.2.2.1.1头插法增加数据

                                时间复杂度：O(n)

                                获取插入位置的前一个结点的地址1；

                                新建一个节点，数据域赋值；

                                指针域指向地址1的下一个地址；

                                修改地址1的next指针，使之指向新增结点；

  1. template<class temp>
  2. inline void linklist<temp>::insert(int i, temp x)
  3. {
  4. 	node<temp>* p = this->front;
  5. 	if (i != 1)
  6. 		p = get(i - 1);
  7. 	if (p != NULL)
  8. 	{
  9. 		node<temp>* s = new node<temp>;
  10. 		s->data = x;
  11. 		s->next = p->next;
  12. 		p->next = s;
  13. 	}
  14. 	else
  15. 	{
  16. 		cout << "插入位置错误！" << endl;
  17. 		exit(0);
  18. 	}
  19. }

                        2.2.2.1.2自动将数据增添至链表末尾的方式增添数据

                                时间复杂度：O(n)

                                定义一个指针，遍历链表使指针指向最后一个结点；

                                新建一个结点，数据域赋值，指针域置空；

                                将指针指向的结点的next指针指向新建结点

  1. template<class temp>
  2. inline void linklist<temp>::addtorear(temp x)
  3. {
  4. 	node<temp>* p = this->front->next;
  5. 	while (p != NULL)
  6. 		p = p->next;
  7. 	node<temp>* s = new node<temp>;
  8. 	s->data = x;
  9. 	s->next = NULL;
  10. 	p->next = s;
  11. }

                2.2.2.2单链表删除数据

                        2.2.2.2.1按位置删除结点

                                时间复杂度：O(n)

                                获取删除位置的前一个结点的地址1（指针1）；

                                定义指向要删除的结点的指针2；

                                将指针1所指向的结点的next指针指向指针2所指向的结点的next指针；

                                删除指针2所指向的结点地址；

  1. template<class temp>
  2. inline void linklist<temp>::del(int i)
  3. {
  4. 	node<temp>* p = this->front;
  5. 	if (i != 1)p = get(i - 1);
  6. 	node<temp>* q = p->next;
  7. 	p->next = q->next;
  8. 	temp x = q->data;
  9. 	delete q;
  10. 	cout << "删除的数据为:" << endl;
  11. 	x.print();
  12. }

                        2.2.2.2.2按值删除结点

                                时间复杂度：O(n)

                                定义指向有效起始位置（首结点）的指针；

                                遍历链表，寻找数据域相同的结点的前一个结点；

                                按照2.2.1方法删除链表结点；

  1. template<class temp>
  2. inline void linklist<temp>::del(temp x)
  3. {
  4. 	int flag = 0;
  5. 	node<temp>* p = this->front;
  6. 	while (p->next != NULL)
  7. 	{
  8. 		if (p->next->data == x)
  9. 		{
  10. 			node<temp>* q = p->next;
  11. 			p->next = q->next;
  12. 			delete q;
  13. 			cout << "删除数据完毕！" << endl;
  14. 			flag = 1;
  15. 			break;
  16. 		}
  17. 		p = p->next;
  18. 	}
  19. 	if (flag == 0)
  20. 	{
  21. 		cout << "未查询到数据！" << endl;
  22. 	}
  23. }

                2.2.2.3修改数据

                        时间复杂度：O(n)

                        获取修改数据的结点地址；

                        修改结点的数据域；

  1. template <class temp>
  2. inline void linklist<temp>::change(int i, temp x)
  3. {
  4. 	node<temp>* p = get(i);
  5. 	p->data = x;
  6. }

                2.2.2.4查询数据

                        2.2.2.4.1返回值类型为指针的get函数

                                时间复杂度：O(n)

                                定义指向首结点的指针；

                                遍历链表，直到符合 要求时停止；

                                返回指针；

  1. template<class temp>
  2. node<temp>* linklist<temp>::get(int i)
  3. {
  4. 	node<temp>* p = this->front->next;
  5. 	int j = 1;
  6. 	while (p != NULL && j != i)
  7. 	{
  8. 		p = p->next;
  9. 		j++;
  10. 	}
  11. 	return p;
  12. }

                        2.2.2.4.2返回值为该结点在单链表中的顺序的（int类型）的函数locate：

                                时间复杂度：O(n)

                                定义指向首结点的指针；

                                遍历链表，直到符合要求时停止；

                                返回计数变量的值；如果没有找到返回-1；

  1. template<class temp>
  2. inline int linklist<temp>::locate(temp x)
  3. {
  4. 	node<temp>* p = this->front->next;
  5. 	int j = 1;
  6. 	while (p != NULL)
  7. 	{
  8. 		if (p->data == x)return j;
  9. 		p = p->next;
  10. 		j++;
  11. 	}
  12. 	return -1;//如果没有找到，返回无效值
  13. }

3.完整代码

  1. #include<iostream>
  2. #include<iomanip>
  3. using namespace std;
  4.  
  5. class phonebook
  6. {
  7. private:
  8. 	int ID;
  9. 	string name;
  10. 	string gender;
  11. 	string phone;
  12. 	string address;
  13. public:
  14. 	phonebook();
  15. 	phonebook(int, string, string, string, string);
  16. 	void getinfo(int, string, string, string, string);
  17. 	void print();
  18. 	void operator =(phonebook&);
  19. 	bool operator ==(phonebook&);
  20. };
  21.  
  22. phonebook::phonebook()
  23. {
  24. 	this->ID = 0;
  25. 	this->name = "invalid_name";
  26. 	this->gender = "invalid_gender";
  27. 	this->phone = "unknown_phone_number";
  28. 	this->address = "unknown_address";
  29. }
  30.  
  31. phonebook::phonebook(int ID, string name,
  32. 	string gender, string phone, string address)
  33. {
  34. 	this->ID = ID;
  35. 	this->name = name;
  36. 	this->gender = gender;
  37. 	this->phone = phone;
  38. 	this->address = address;
  39. }
  40.  
  41. inline void phonebook::getinfo(int ID, string name,
  42. 	string gender, string phone, string address)
  43. {
  44. 	this->ID = ID;
  45. 	this->name = name;
  46. 	this->gender = gender;
  47. 	this->phone = phone;
  48. 	this->address = address;
  49. }
  50.  
  51. inline void phonebook::print()
  52. {
  53. 	cout << setiosflags(ios::left);
  54. 	cout << "ID:" << setw(10) << this->ID;
  55. 	cout << "name:" << setw(10) << this->name;
  56. 	cout << "gender:" << setw(10) << this->gender;
  57. 	cout << "phone:" << setw(15) << this->phone;
  58. 	cout << "address:" << setw(10) << this->address;
  59. 	cout << endl;
  60. }
  61.  
  62. inline void phonebook::operator=(phonebook& a)
  63. {
  64. 	this->ID = a.ID;
  65. 	this->name = a.name;
  66. 	this->gender = a.gender;
  67. 	this->phone = a.phone;
  68. 	this->address = a.address;
  69. }
  70.  
  71. inline bool phonebook::operator==(phonebook& a)
  72. {
  73. 	int cnt = 0;
  74. 	if (this->ID == a.ID)cnt++;
  75. 	if (this->name == a.name)cnt++;
  76. 	if (this->gender == a.gender)cnt++;
  77. 	if (this->phone == a.phone)cnt++;
  78. 	if (this->address == a.address)cnt++;
  79. 	return (cnt == 5) ? true : false;
  80. }
  81.  
  82. template<class temp>
  83. struct node
  84. {
  85. 	temp data;
  86. 	node<temp>* next;
  87. };
  88.  
  89. template<class temp>
  90. class linklist
  91. {
  92. private:
  93. 	node<temp>* front;
  94. public:
  95. 	linklist()
  96. 	{
  97. 		this->front = new node<temp>;
  98. 		this->front->next = nullptr;
  99. 	}
  100. 	linklist(temp a[], int n);
  101. 	~linklist();
  102. 	node<temp>* get(int i);
  103. 	void printlist();
  104. 	void printlength();
  105. 	int getlength();
  106. 	int locate(temp x);
  107. 	void insert(int i, temp x);
  108. 	void addtorear(temp x);
  109. 	void change(int i, temp x);
  110. 	void del(int i);
  111. 	void del(temp x);
  112. };
  113.  
  114. template<class temp>
  115. linklist<temp>::linklist(temp a[], int n)
  116. {
  117. 	this->front = new node<temp>;
  118. 	this->front->next = NULL;
  119. 	for (int i = n - 1; i >= 0; i--)
  120. 	{
  121. 		node<temp>* s = new node<temp>;
  122. 		s->data = a[i];
  123. 		s->next = this->front->next;
  124. 		this->front->next = s;
  125. 	}
  126. }
  127.  
  128. template<class temp>
  129. linklist<temp>::~linklist()
  130. {
  131. 	node<temp>* p = this->front;
  132. 	while (p != NULL)
  133. 	{
  134. 		this->front = p;
  135. 		p = p->next;
  136. 		delete this->front;
  137. 	}
  138. }
  139.  
  140. template<class temp>
  141. node<temp>* linklist<temp>::get(int i)
  142. {
  143. 	node<temp>* p = this->front->next;
  144. 	int j = 1;
  145. 	while (p != NULL && j != i)
  146. 	{
  147. 		p = p->next;
  148. 		j++;
  149. 	}
  150. 	return p;
  151. }
  152.  
  153. template <class temp>
  154. inline void linklist<temp>::printlist()
  155. {
  156. 	node<temp>* p = this->front->next;
  157. 	if (p == NULL)
  158. 	{
  159. 		cout << "p==NULL!" << endl;
  160. 		exit(0);
  161. 	}
  162. 	while (p != NULL)
  163. 	{
  164. 		p->data.print();
  165. 		p = p->next;
  166. 	}
  167. 	cout << endl;
  168. }
  169.  
  170. template <class temp>
  171. inline void linklist<temp>::printlength()
  172. {
  173. 	node<temp>* p = this->front->next;
  174. 	int cnt = 0;
  175. 	while (p != NULL)
  176. 	{
  177. 		p = p->next;
  178. 		cnt++;
  179. 	}
  180. 	cout << endl << "有效学生信息为" << cnt << "个" << endl << endl;
  181. }
  182.  
  183. template <class temp>
  184. inline int linklist<temp>::getlength()
  185. {
  186. 	node<temp>* p = this->front->next;
  187. 	int cnt = 0;
  188. 	while (p != NULL)
  189. 	{
  190. 		p = p->next;
  191. 		cnt++;
  192. 	}
  193. 	return cnt;
  194. }
  195.  
  196. template<class temp>
  197. inline int linklist<temp>::locate(temp x)
  198. {
  199. 	node<temp>* p = this->front->next;
  200. 	int j = 1;
  201. 	while (p != NULL)
  202. 	{
  203. 		if (p->data == x)return j;
  204. 		p = p->next;
  205. 		j++;
  206. 	}
  207. 	return -1;//如果没有找到，返回无效值
  208. }
  209.  
  210. template<class temp>
  211. inline void linklist<temp>::insert(int i, temp x)
  212. {
  213. 	node<temp>* p = this->front;
  214. 	if (i != 1)
  215. 		p = get(i - 1);
  216. 	if (p != NULL)
  217. 	{
  218. 		node<temp>* s = new node<temp>;
  219. 		s->data = x;
  220. 		s->next = p->next;
  221. 		p->next = s;
  222. 	}
  223. 	else
  224. 	{
  225. 		cout << "插入位置错误！" << endl;
  226. 		exit(0);
  227. 	}
  228. }
  229.  
  230. template<class temp>
  231. inline void linklist<temp>::addtorear(temp x)
  232. {
  233. 	node<temp>* p = this->front->next;
  234. 	while (p != NULL)
  235. 		p = p->next;
  236. 	node<temp>* s = new node<temp>;
  237. 	s->data = x;
  238. 	s->next = NULL;
  239. 	p->next = s;
  240. }
  241.  
  242. template <class temp>
  243. inline void linklist<temp>::change(int i, temp x)
  244. {
  245. 	node<temp>* p = get(i);
  246. 	p->data = x;
  247. }
  248.  
  249. template<class temp>
  250. inline void linklist<temp>::del(int i)
  251. {
  252. 	node<temp>* p = this->front;
  253. 	if (i != 1)p = get(i - 1);
  254. 	node<temp>* q = p->next;
  255. 	p->next = q->next;
  256. 	temp x = q->data;
  257. 	delete q;
  258. 	cout << "删除的数据为:" << endl;
  259. 	x.print();
  260. }
  261.  
  262. template<class temp>
  263. inline void linklist<temp>::del(temp x)
  264. {
  265. 	int flag = 0;
  266. 	node<temp>* p = this->front;
  267. 	while (p->next != NULL)
  268. 	{
  269. 		if (p->next->data == x)
  270. 		{
  271. 			node<temp>* q = p->next;
  272. 			p->next = q->next;
  273. 			delete q;
  274. 			cout << "删除数据完毕！" << endl;
  275. 			flag = 1;
  276. 			break;
  277. 		}
  278. 		p = p->next;
  279. 	}
  280. 	if (flag == 0)
  281. 	{
  282. 		cout << "未查询到数据！" << endl;
  283. 	}
  284. }
  285.  
  286. int main()
  287. {
  288. 	system("color 0A");
  289. 	phonebook pbook[5] =
  290. 	{
  291. 		{1,"zhang","male","11111111111","a"},
  292. 		{2,"wang","female","22222222222","b"},
  293. 		{3,"li","male","33333333333","c"},
  294. 		{4,"zhao","female","44444444444","d"},
  295. 		{5,"liu","male","55555555555","e"}
  296. 	};
  297. 	linklist<phonebook>list(pbook, 5);
  298. 	while (1)
  299. 	{
  300. 	label0:
  301. 		cout << setw(41) << "欢迎来到通讯录管理系统！" << endl;
  302. 		cout << setw(40) << "*****增加数据请按1*****" << endl;
  303. 		cout << setw(40) << "*****删除数据请按2*****" << endl;
  304. 		cout << setw(40) << "*****修改数据请按3*****" << endl;
  305. 		cout << setw(40) << "*****查询数据请按4*****" << endl;
  306. 		cout << setw(40) << "*****显示数据请按5*****" << endl;
  307. 		cout << setw(40) << "*****退出查询请按6*****" << endl;
  308. 		cout << endl << "请输入序号:";
  309. 		int n0;
  310. 		cin >> n0;
  311. 		int flag = 1;
  312. 		switch (n0)
  313. 		{
  314. 		case 1:
  315. 		{
  316. 			cout << setw(40) << "欢迎来到数据增加界面！" << endl;
  317. 			cout << "请输入您想增加到通讯录中的先生/女士信息:" << endl;
  318. 			cout << "注意，请依次输入ID，姓名，性别，" <<
  319. 				"电话号码和家庭住址，所有信息占一行" << endl;
  320. 			int ID; string name, gender, phone, address;
  321. 			cin >> ID >> name >> gender >> phone >> address;
  322. 			phonebook record0(ID, name, gender, phone, address);
  323. 			cout << "请输入您想将数据插入的位置序号:" << endl;
  324. 			int n1;
  325. 			cin >> n1;
  326. 			int length = list.getlength();
  327. 			if (n1 <= length)
  328. 				list.insert(n1, record0);
  329. 			else
  330. 				list.addtorear(record0);
  331. 			cout << "插入后的通讯录显示为:" << endl;
  332. 			list.printlist();
  333. 			break;
  334. 		}
  335. 		case 2:
  336. 		{
  337. 			cout << setw(40) << "欢迎来到数据删除界面！" << endl;
  338. 		label1:
  339. 			cout << "按顺序删除请按0，按值删除请按1" << endl;
  340. 			int n2;
  341. 			cin >> n2;
  342. 			switch (n2)
  343. 			{
  344. 			case 0:
  345. 			{
  346. 				int order;
  347. 				cout << "请输入删除的数据在通讯录中的顺序:";
  348. 				cin >> order;
  349. 				list.del(order);
  350. 				cout << "删除后的通讯录显示为:" << endl;
  351. 				list.printlist();
  352. 				break;
  353. 			}
  354. 			case 1:
  355. 			{
  356. 				cout << "请输入您想删除的先生/女士信息:" << endl;
  357. 				cout << "注意，请依次输入ID，姓名，性别，" <<
  358. 					"电话号码和家庭住址，所有信息占一行" << endl;
  359. 				int ID; string name, gender, phone, address;
  360. 				cin >> ID >> name >> gender >> phone >> address;
  361. 				phonebook record1(ID, name, gender, phone, address);
  362. 				list.del(record1);
  363. 				cout << "删除后的通讯录显示为:" << endl;
  364. 				list.printlist();
  365. 				break;
  366. 			}
  367. 			default:
  368. 			{
  369. 				cout << "输入错误！" << endl;
  370. 				goto label1;
  371. 				break;
  372. 			}
  373. 			}
  374.  
  375. 			break;
  376. 		}
  377. 		case 3:
  378. 		{
  379. 			cout << setw(40) << "欢迎来到数据修改界面！" << endl;
  380. 			cout << "请输入您想修改的先生/女士在通讯录中的顺序:";
  381. 			int n3;
  382. 			cin >> n3;
  383. 			cout << "请输入您想修改先生/女士信息:" << endl;
  384. 			cout << "注意，请依次输入ID，姓名，性别，" <<
  385. 				"电话号码和家庭住址，所有信息占一行" << endl;
  386. 			int ID; string name, gender, phone, address;
  387. 			cin >> ID >> name >> gender >> phone >> address;
  388. 			phonebook record2(ID, name, gender, phone, address);
  389. 			list.change(n3, record2);
  390. 			cout << "修改后的通讯录为:" << endl;
  391. 			list.printlist();
  392. 			break;
  393. 		}
  394. 		case 4:
  395. 		{
  396. 		label2:
  397. 			cout << setw(40) << "欢迎来到数据查询界面！" << endl;
  398. 			cout << "请输入您想查询的先生/女士信息:" << endl;
  399. 			cout << "注意，请依次输入ID，姓名，性别，" <<
  400. 				"电话号码和家庭住址，所有信息占一行" << endl;
  401. 			int ID; string name, gender, phone, address;
  402. 			cin >> ID >> name >> gender >> phone >> address;
  403. 			phonebook record3(ID, name, gender, phone, address);
  404. 			int pos = list.locate(record3);
  405. 			if (pos == -1)
  406. 			{
  407. 				cout << "该人员不在通讯录内，请问您是否继续查询？" << endl;
  408. 				cout << "如果选择继续查询请按1，不继续查询请按0" << endl;
  409. 				int n4;
  410. 				cin >> n4;
  411. 				switch (n4)
  412. 				{
  413. 				case 1:
  414. 				{
  415. 					goto label2;
  416. 					break;
  417. 				}
  418. 				case 0:
  419. 					break;
  420. 				default:
  421. 					break;
  422. 				}
  423. 			}
  424. 			else
  425. 			{
  426. 				cout << endl << "您查找的人员在通讯录中，"
  427. 					"在通讯录中的顺序为第" << pos << "个" << endl << endl;
  428. 			}
  429. 			break;
  430. 		}
  431. 		case 5:
  432. 		{
  433. 			cout << setw(40) << "欢迎来到数据显示界面！" << endl;
  434. 			list.printlength();
  435. 			cout << "您当前通讯录列表打印如下:" << endl;
  436. 			list.printlist();
  437. 			break;
  438. 		}
  439. 		case 6:
  440. 		{
  441. 			return 0;
  442. 		}
  443. 		default:
  444. 		{
  445. 			flag = 0;
  446. 			break;
  447. 		}
  448. 		}
  449. 		if (flag == 0)
  450. 		{
  451. 			cout << "上次输入无效，请重新输入！" << endl;
  452. 			goto label0;
  453. 		}
  454. 	}
  455. 	return 0;
  456. }
  457. /*
  459. 初始数据：
  460. 1 zhang male 11111111111 a
  461. 2 wang female 22222222222 b
  462. 3 li male 33333333333 c
  463. 4 zhao female 44444444444 d
  464. 5 liu male 55555555555 e
  466. 增加数据样例：
  468. 6 meng female 66666666666 f
  470. */

4.程序运行结果

代码效果图：

程序运行结果：

开始界面：用户输入功能选择的键值；

对每个界面均有输入错误处理机制，使用了label  goto语句；

部分功能为了更好满足用户需求，实现了switch语句的嵌套；

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/559397
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号