一、 实验目的
1、掌握线性表的逻辑结构
2、熟练掌握线性表的链式存储结构定义及基本操作
3、加深对链式存储数据结构的理解，逐步培养解决实际问题的编程能力
二、 实验要求
1、演示程序运行结果
2、分析调试过程中出现的现象
3、总结单链表基本操作的特点
4、分析算法的时间复杂度
三、实验内容
编写程序，实现单链表的创建、插入和删除等基本操作算法。
(1) 创建带头结点的单链表。
(3) 查找值为给定值的元素，如果找到返回其位序，否则返回0
(4) 在单链表的特定位置插入任意元素并输出单链表中的各元素值。
(5) 在单链表的特定位置删除任意元素并输出单链表中的各元素值。
1. #include<iostream> 2. #include<string> 3. #include<iomanip> 4. #include<fstream> 5. using namespace std; 6. 7. #define OK 1 8. #define ERROR 0 9. #define OVERFLOW -2 10. typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。 11. typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型 12. 13. struct Book { 14. string id;//ISBN 15. string name;//书名 16. double price;//定价 17. }; 18. typedef struct LNode { 19. Book data; //结点的数据域 20. struct LNode *next; //结点的指针域 21. } LNode, *LinkList; //LinkList为指向结构体LNode的指针类型 22. 23. string head_1, head_2, head_3; 24. int length; 25. 26. Status InitList_L(LinkList &L) { // 单链表的初始化 27. //构造一个空的单链表L 28. L = new LNode; //生成新结点作为头结点，用头指针L指向头结点 29. L->next = NULL; //头结点的指针域置空 30. return OK; 31. } 32. 33. Status GetElem_L(LinkList L, int i, Book &e) { // 单链表的取值 34. //在带头结点的单链表L中查找第i个元素 35. //用e返回L中第i个数据元素的值 36. int j; 37. LinkList p; 38. p = L->next; 39. j = 1; //初始化，p指向第一个结点，j为计数器 40. while (j < i && p) { //顺链域向后扫描，直到p指向第i个元素或p为空 41. p = p->next; //p指向下一个结点 42. ++j; //计数器j相应加1 43. } 44. if (!p || j > i) 45. return ERROR; //i值不合法i＞n或i<=0 46. e = p->data; //取第i个结点的数据域 47. return OK; 48. } //GetElem_L 49. 50. LNode *LocateElem_L(LinkList L, int e){LinkList p; p=L->next;while(p && p->data.price!=e) p=p->next;return p;// 按值查找 51. //在带头结点的单链表L中查找值为e的元素 52. 53. } //LocateElem_L 54. 55. Status ListInsert_L(LinkList &L, int i, Book &e) { // 单链表的插入 56. //在带头结点的单链表L中第i个位置插入值为e的新结点 57. int j; 58. LinkList p, s; 59. p = L; 60. j = 0; 61. while (p && j < i - 1) { 62. p = p->next; 63. ++j; 64. }//查找第i?1个结点，p指向该结点 65. if (!p || j > i - 1) 66. return ERROR; //i＞n+1或者i＜1 67. s=new LNode; //生成新结点*s 68. s->data=e; //将结点*s的数据域置为e 69. s->next=p->next; //将结点*s的指针域指向结点ai 70. p->next=s; //将结点*p的指针域指向结点*s 71. ++length; 72. return OK; 73. } //ListInsert_L 74. 75. Status ListDelete_L(LinkList &L, int i) { // 单链表的删除 76. //在带头结点的单链表L中，删除第i个位置 77. LinkList p, q; 78. int j; 79. p = L; 80. j = 0; 81. while ((p->next) && (j < i - 1)) //查找第i?1个结点，p指向该结点 82. { 83. {p=p->next;++j;} 84. } 85. if (!(p->next) || (j > i - 1)) 86. return ERROR; //当i>n或i<1时，删除位置不合理 87. q = p->next; //临时保存被删结点的地址以备释放 88. p->next = q->next; //改变删除结点前驱结点的指针域 89. delete q; //释放删除结点的空间 90. --length; 91. return OK; 92. } //ListDelete_L 93. 94. void CreateList_H(LinkList &L, int n) { // 前插法创建单链表 95. //逆位序输入n个元素的值，建立到头结点的单链表L 96. LinkList p; 97. L = new LNode; 98. L->next = NULL; //先建立一个带头结点的空链表 99. length = 0; 100. fstream file; 101. file.open("book.txt"); 102. if (!file) { 103. cout << "未找到相关文件，无法打开！" << endl; 104. exit(ERROR); 105. } 106. file >> head_1 >> head_2 >> head_3; 107. while (!file.eof()) { 108. p = new LNode; //生成新结点*p 109. file >> p->data.id >> p->data.name >> p->data.price; //输入元素值赋给新结点*p的数据域 110. p->next = L->next; 111. L->next = p; //将新结点*p插入到头结点之后 112. length++;//同时对链表长度进行统计 113. } 114. file.close(); 115. } //CreateList_F 116. 117. void CreateList_R(LinkList &L, int n) { // 后插法创建单链表 118. //正位序输入n个元素的值，建立带表头结点的单链表L 119. LinkList p, r; 120. L = new LNode; 121. L->next = NULL; //先建立一个带头结点的空链表 122. r = L; //尾指针r指向头结点 123. length = 0; 124. fstream file; //打开文件进行读写操作 125. file.open("book.txt"); 126. if (!file) { 127. cout << "未找到相关文件，无法打开！" << endl; 128. exit(ERROR); 129. } 130. file >> head_1 >> head_2 >> head_3; 131. while (!file.eof()) { //将文件中的信息运用后插法插入到链表中 132. p = new LNode;//生成新结点 133. file >> p->data.id >> p->data.name >> p->data.price;//输入元素值赋给新结点*p的数据域 134. p->next = NULL; 135. r->next = p;//将新结点*p插入尾结点*r之后 136. r = p;//r指向新的尾结点*p 137. length++; //同时对链表长度进行统计 138. } 139. file.close(); 140. } //CreateList_L 141. 142. int main() { 143. int a, n, choose; 144. double price; 145. Book e; 146. LinkList L, p; 147. cout << "1. 建立\n"; 148. cout << "2. 输入\n"; 149. cout << "3. 取值\n"; 150. cout << "4. 查找\n"; 151. cout << "5. 插入\n"; 152. cout << "6. 删除\n"; 153. cout << "7. 输出\n"; 154. cout << "0. 退出\n\n"; 155. 156. choose = -1; 157. while (choose != 0) { 158. cout << "请选择:"; 159. cin >> choose; 160. switch (choose) { 161. case 1: //建立一个单链表 162. if (InitList_L(L)) 163. cout << "成功建立链表!\n\n"; 164. break; 165. case 2: //使用后插法创建单链表 166. CreateList_R(L, length); 167. cout << "输入 book.txt 信息完毕\n\n"; 168. break; 169. case 3: //单链表的按序号取值 170. cout << "请输入一个位置用来取值:"; 171. cin >> a; 172. if (GetElem_L(L, a, e)) { 173. cout << "查找成功\n"; 174. cout << "第" << a << "本图书的信息是：\n"; 175. cout << left << setw(15) << e.id << "\t" << left << setw(50) 176. << e.name << "\t" << left << setw(5) << e.price << endl 177. << endl; 178. } else 179. cout << "查找失败\n\n"; 180. break; 181. case 4: //单链表的按值查找 182. cout << "请输入所要查找价格:"; 183. cin >> price; 184. if (LocateElem_L(L, price) != NULL) { 185. cout << "查找成功\n"; 186. cout << "该价格对应的书名为：" << LocateElem_L(L, price)->data.name 187. << endl << endl; 188. } else 189. cout << "查找失败! 定价" << price << " 没有找到\n\n"; 190. break; 191. case 5: //单链表的插入 192. cout << "请输入插入的位置和书的信息，包括：编号 书名 价格（用空格隔开）:"; 193. cin >> a; 194. cin >> e.id >> e.name >> e.price; 195. if (ListInsert_L(L, a, e)) 196. cout << "插入成功.\n\n"; 197. else 198. cout << "插入失败!\n\n"; 199. break; 200. case 6: //单链表的删除 201. cout << "请输入所要删除的书籍的位置:"; 202. cin >> a; 203. if (ListDelete_L(L, a)) 204. cout << "删除成功!\n\n"; 205. else 206. cout << "删除失败!\n\n"; 207. break; 208. case 7: //单链表的输出 209. cout << "当前图书系统信息（链表）读出:\n"; 210. p = L->next; 211. while (p) { 212. cout << left << setw(15) << p->data.id << "\t" << left << setw( 213. 50) << p->data.name << "\t" << left << setw(5) 214. << p->data.price << endl; 215. p = p->next; 216. } 217. cout << endl; 218. break; 219. } 220. } 221. return 0; 222. }
