作者：Q_jack | 来源：互联网 | 2023-06-06 14:23
太简单了，直接贴题目然后上代码。
题目：
实验2
2.1 实验目的
熟练掌握线性表的链式存储结构。
熟练掌握单链表的有关算法设计。
根据具体问题的需要，设计出合理的表示数据的链式存储结构，并设计相关算法。
2.2 实验要求
本次实验中的链表结构指带头结点的单链表；
单链表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现；
比如存储、算法实现放入文件：linkedList.h
实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；
程序有适当的注释。
2.3 实验任务
编写算法实现下列问题的求解。
<1>尾插法创建单链表，打印创建结果。
<2>头插法创建单链表，打印创建结果。
<3>销毁单链表。
<4>求链表长度。
<5>求单链表中第i个元素（函数），若不存在，报错。
实验测试数据基本要求：
第一组数据：单链表长度n≥10，i分别为5，n，0，n+1，n+2
第二组数据：单链表长度n=0，i分别为0，2
<6>在第i个结点前插入值为x的结点。
实验测试数据基本要求：
第一组数据：单链表长度n≥10，x=100, i分别为5,n,n+1,0,1,n+2
第二组数据：单链表长度n=0，x=100，i=5
<7>链表中查找元素值为x的结点，成功返回结点指针，失败报错。
实验测试数据基本要求：
单链表元素为（1，3，6，10，15，16，17，18，19，20）
x=1，17，20，88
<8>删除单链表中第i个元素结点。
实验测试数据基本要求：
第一组数据：单链表长度n≥10，i分别为5,n,1,n+1,0
第二组数据：单链表长度n=0， i=5
<9>在一个递增有序的单链表L中插入一个值为x的元素，并保持其递增有序特性。
实验测试数据基本要求：
单链表元素为（10,20,30,40,50,60,70,80,90,100）,
x分别为25，85，110和8
<10>将单链表Ｌ中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的单链表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果。
实验测试数据基本要求：
第一组数据：单链表元素为（1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）
第二组数据：单链表元素为（10,20,30,40,50,60,70,80,90,100）
代码：
1 // stdafx.h : include file for standard system include files, 2 // or project specific include files that are used frequently, but 3 // are changed infrequently 4 // 5
6 #if !defined(AFX_STDAFX_H__195DB73A_A23D_4A80_A4F5_2F4FC5141CBC__INCLUDED_)
7 #define AFX_STDAFX_H__195DB73A_A23D_4A80_A4F5_2F4FC5141CBC__INCLUDED_
8
9 #if _MSC_VER > 1000
10 #pragma once
11 #endif // _MSC_VER > 1000
12
13 #include
14
15 using namespace std; 16
17 typedef int elementType; 18 typedef struct node 19 { 20 elementType data; 21 node* next; 22 }LList, *PList; 23
24 // TODO: reference additional headers your program requires here 25
26 //{{AFX_INSERT_LOCATION}} 27 // Microsoft Visual C++ will insert additional declarations immediately before the previous line.
28
29 #endif // !defined(AFX_STDAFX_H__195DB73A_A23D_4A80_A4F5_2F4FC5141CBC__INCLUDED_)
1 // linkedList1.h: interface for the linkedList class. 2 // 3 //////////////////////////////////////////////////////////////////////
4
5 #if !defined(AFX_LINKEDLIST1_H__4C3F34C9_D36C_43D6_97CF_A8E55FD6BD7D__INCLUDED_)
6 #define AFX_LINKEDLIST1_H__4C3F34C9_D36C_43D6_97CF_A8E55FD6BD7D__INCLUDED_
7
8 #if _MSC_VER > 1000
9 #pragma once
10 #endif // _MSC_VER > 1000
11
12 #include "StdAfx.h"
13
14 using namespace std; 15
16 class linkedList 17 { 18 public: 19 linkedList();//构造函数
20 virtual ~linkedList();//析构函数，销毁单链表
21 bool createLinkedListRail( int length );//尾插法构建单链表
22 bool createLinkedListFront( int length );//头插法构建单链表
23 void addLinkedListNodeLast( int value );//警告：必须初始化才能使用！ 24 //我尝试判断调用对象的链表是否初始化来作为是否调用该函数的依据，结果失败：无论如何判断，总是不能在零节点时插入
25 bool initiateLinkedList();//初始化单链表
26 bool isEmpty();//判断单链表是否为空
27 bool getElementByPosition( int pos, int& value );//求单链表中第pos个元素（函数），若不存在，报错
28 bool insertListByPosition( int pos, int value );//在第pos个结点前插入值为value的结点
29 bool getElementByValue( int& pos, int value );//链表中查找元素值为x的结点，成功返回结点指针，失败报错。
30 bool removeListNodeByPosition( int pos, int& value );//删除单链表中第pos个元素结点
31 bool insertListSort( int value );//在一个递增有序的单链表L中插入一个值为value的元素，并保持其递增有序特性
32 bool oddEvenSort( linkedList& LA,linkedList& LB );//将调用单链表中的元素按奇偶性分配給被调用的单链表LA与LB
33 void printLinkedList();//打印单链表
34 int linkedListLength();//返回单链表长度
35 private: 36 LList *head; 37 int len; 38 }; 39
40 #endif // !defined(AFX_LINKEDLIST1_H__4C3F34C9_D36C_43D6_97CF_A8E55FD6BD7D__INCLUDED_)
1 // linkedList1.cpp: implementation of the linkedList class. 2 // 3 //////////////////////////////////////////////////////////////////////
4
5 #include "stdafx.h"
6 #include "linkedList1.h"
7
8
9 //////////////////////////////////////////////////////////////////////
10 // Construction/Destruction
11 //////////////////////////////////////////////////////////////////////
12
13 linkedList::linkedList() 14 { 15 head = NULL; 16 len = 0; 17 } 18
19 linkedList::~linkedList() 20 { 21 LList* tmp = head; 22 //for( int i = 0; i
23 while( tmp->next ) 24 { 25 LList *q = tmp; 26 tmp = tmp->next; 27 delete q; 28 } 29 } 30
31 bool linkedList::initiateLinkedList() 32 { 33 std::ios::sync_with_stdio(false); 34 head = new LList; 35 if( !head ) 36 { 37 cout <<"初始化失败！" << endl; 38 return false; 39 } 40 head->next = NULL; 41 return true; 42 } 43
44 bool linkedList::createLinkedListRail( int length ) 45 { 46 std::ios::sync_with_stdio(false); 47 initiateLinkedList(); 48 LList* rail = head; 49 for( int i = 1; i <= length; i ++ ) 50 { 51 LList* tmp = new LList; 52 int num; 53 cin >> num; 54 //num = i + 1;
55 tmp->data = num; 56 tmp->next = rail->next; 57 rail->next = tmp; 58 rail = tmp; 59 len ++; 60 } 61 return true; 62 } 63
64 bool linkedList::createLinkedListFront( int length ) 65 { 66 std::ios::sync_with_stdio(false); 67 initiateLinkedList(); 68 for( int i = 0; i ) 69 { 70 int num; 71 cin >> num; 72 //num = i + 1;
73 LList* tmp = new LList; 74 tmp->data = num; 75 tmp->next = head->next; 76 head->next = tmp; 77 len ++; 78 } 79 return true; 80 } 81
82 void linkedList::addLinkedListNodeLast( int value ) 83 { 84 //ios::sync_with_stdio(false);
85
86 LList* tmp = head; 87 LList* last = NULL; 88 while(tmp) 89 { 90 last = tmp; 91 tmp = tmp->next; 92 } 93 LList* PNew = new LList; 94 PNew->data = value; 95 PNew->next = NULL; 96 last->next = PNew; 97 len ++; 98 } 99
100 bool linkedList::isEmpty() 101 { 102 return head->next == NULL; 103 } 104
105 void linkedList::printLinkedList() 106 { 107 std::ios::sync_with_stdio(false); 108 if( isEmpty() ) 109 { 110 cout <<"空链表，无法打印！" << endl; 111 return; 112 } 113 LList* tmp = head->next; 114 int column = 0; 115 while(tmp) 116 { 117 cout <3) <data <<" "; 118 column ++; 119 if( column % 10 == 0 ) 120 cout << endl; 121 tmp = tmp->next; 122 } 123 cout << endl; 124 } 125
126 int linkedList::linkedListLength() 127 { 128 if( isEmpty() ) 129 { 130 cout <<"空链表！" << endl; 131 return -1; 132 } 133 int l = 0; 134 LList* tmp = head->next; 135 while(tmp) 136 { 137 tmp = tmp->next; 138 l ++; 139 } 140 return l; 141 //return len;
142 } 143
144 bool linkedList::getElementByPosition( int pos, int& value ) 145 { 146 ios::sync_with_stdio(false); 147 if( isEmpty() ) 148 { 149 cout <<"链表为空！获取元素失败！" << endl; 150 return false; 151 } 152 if( pos > len ) 153 { 154 cout <<"位置大于表长！获取元素失败！" << endl; 155 return false; 156 } 157 if( pos <= 0 ) 158 { 159 cout <<"位置必须大于0！获取元素失败！" << endl; 160 return false; 161 } 162 int index = 0; 163 LList* tmp = head; 164 while(tmp) 165 { 166 if( index == pos ) 167 { 168 //cout <data;
169 value = tmp->data; 170 return true; 171 } 172 tmp = tmp->next; 173 index ++; 174 } 175 return true; 176 } 177
178 bool linkedList::insertListByPosition( int pos, int value ) 179 { 180 ios::sync_with_stdio(false); 181 if( isEmpty() ) 182 { 183 cout <<"链表为空！插入元素失败！" << endl; 184 return false; 185 } 186 else if( pos > len ) 187 { 188 cout <<"位置大于表长且差值大于1！删除元素失败！" << endl; 189 return false; 190 } 191 else if( pos == len ) 192 { 193 cout <<"将会直接把新节点接在链表尾部！" << endl; 194 addLinkedListNodeLast( value ); 195 return true; 196 } 197 else if( pos <= 0 ) 198 { 199 cout <<"位置必须大于0！插入元素失败！" << endl; 200 return false; 201 } 202 int index = 0; 203 LList* tmp = head; 204 while( index != pos - 1 && tmp ) 205 { 206 index ++; 207 tmp = tmp->next; 208 } 209 if( tmp == NULL ) 210 { 211 cout <<"位置大于表长且不在表长的后一位！插入元素失败！" << endl; 212 return false; 213 } 214 LList* PNew = new LList; 215 PNew->data = value; 216 PNew->next = tmp->next; 217 tmp->next = PNew; 218 len ++; 219 return true; 220 } 221
222 bool linkedList::getElementByValue( int& pos, int value ) 223 { 224 ios::sync_with_stdio(false); 225 if( isEmpty() ) 226 { 227 cout <<"链表为空！获取元素失败！" << endl; 228 return false; 229 } 230 int index = 1; 231 LList* tmp = head->next; 232 while(tmp) 233 { 234 if( tmp->data == value ) 235 { 236 pos = index; 237 return true; 238 } 239 tmp = tmp->next; 240 index ++; 241 } 242 return false; 243 } 244
245 bool linkedList::removeListNodeByPosition( int pos, int& value ) 246 { 247 ios::sync_with_stdio(false); 248 if( isEmpty() ) 249 { 250 cout <<"链表为空！删除元素失败！" << endl; 251 return false; 252 } 253 if( pos > len ) 254 { 255 cout <<"位置大于表长！删除元素失败！" << endl; 256 return false; 257 } 258 if( pos <= 0 ) 259 { 260 cout <<"位置必须大于0！删除元素失败！" << endl; 261 return false; 262 } 263 LList* tmp = head; 264 int index = 0; 265 while( index != pos - 1 && tmp ) 266 { 267 tmp = tmp->next; 268 index ++; 269 } 270 LList* PDel = tmp->next; 271 value = PDel->data; 272 tmp->next = tmp->next->next; 273 delete PDel; 274 len --; 275 return true; 276 } 277
278 bool linkedList::insertListSort( int value ) 279 { 280 ios::sync_with_stdio(false); 281 if( isEmpty() ) 282 { 283 cout <<"链表为空！插入元素失败！" << endl; 284 return false; 285 } 286 LList* tmp = head; 287 while( tmp->next && tmp->next->data //下一个节点的data比value小就继续循环 288 //写成下面这样导致比最后一个节点的data大的value无法插入！因为循环结束时tmp->next为NULL，无法插入。 289 //while( tmp && tmp->next->data
290 { 291 //if( tmp->data
292 tmp = tmp->next; 293 } 294 LList* PNew = new LList; 295 PNew->data = value; 296 PNew->next = tmp->next; 297 tmp->next = PNew; 298 return true; 299 } 300
301 bool linkedList::oddEvenSort( linkedList& LA,linkedList& LB ) 302 { 303 ios::sync_with_stdio(false); 304 if( isEmpty() ) 305 { 306 cout <<"原链表为空！分配元素失败！" << endl; 307 return false; 308 } 309 //if( !LA.head->next && !LB.head->next )
310 if( !LA.head && !LB.head ) 311 { 312 LA.initiateLinkedList(); 313 LB.initiateLinkedList(); 314 } 315 LList* tmp = head->next; 316 while(tmp) 317 { 318 if( tmp->data >= 0 && ( tmp->data & 1 ) ) 319 LA.addLinkedListNodeLast( tmp->data ); 320 //else if( tmp->data >= 0 && !( tmp->data & 1 ) )
321 else
322 LB.addLinkedListNodeLast( tmp->data ); 323 tmp = tmp->next; 324 } 325 return true; 326 }
1 // LinkedList.cpp : Defines the entry point for the console application. 2 // 3
4 #include "stdafx.h"
5 #include "linkedList1.h"
6
7 int main(int argc, char* argv[]) 8 { 9 ios::sync_with_stdio(false); 10 freopen( "1.in", "r", stdin ); 11
12 linkedList L1;//, L2;
13 int n; 14 cin >> n; 15 L1.createLinkedListFront(n); 16 cout <<"原表表长为：" << endl; 17 cout < endl; 18 cout <<"原表元素为：" << endl; 19 L1.printLinkedList(); 20 /*
21 L1.~linkedList(); 22 cout <<"现表表长为：" < 23 cout < 24 cout <<"现表元素为：" < 25 L1.printLinkedList(); 26 //L2.createLinkedListFront(5); 27 //cout < 28 //L2.printLinkedList(); 29 22 30 30 70 92 91 15 47 84 10 43 34 9 62 60 26 79 96 38 4 92 24 25 5 31
32 linkedList L3; 33 int n; 34 cin >> n; 35 L3.createLinkedListRail(n); 36 cout <<"原表表长为：" < 37 cout < 38 cout <<"原表元素为：" < 39 L3.printLinkedList();//5，n，0，n+1，n+2 40
41 int value = -100; 42 int num; 43 cin >> num; 44 for( int i = 0; i 45 { 46 int pos; 47 cin >> pos; 48 if( L3.getElementByPosition( pos, value ) ) 49 { 50 cout <<"第 " < 51
52 } 53 else 54 cout <<"不存在位置为 " < 55 } 56
57 linkedList L4; 58 int n; 59 cin >> n; 60 L4.createLinkedListRail(n); 61 cout <<"原表表长为：" < 62 cout < 63 cout <<"原表元素为：" < 64 L4.printLinkedList();//x=100, i分别为5,n,n+1,0,1,n+2 65 int value = 100; 66 int num; 67 cin >> num; 68 for( int i = 0; i 69 { 70 int pos; 71 cin >> pos; 72 if( L4.insertListByPosition( pos, value ) ) 73 { 74 cout <<"value = " < 75 cout <<"现表表长为：" < 76 cout < 77 cout <<"现表元素为：" < 78 L4.printLinkedList(); 79 } 80 } 81
82 linkedList L5; 83 int n; 84 cin >> n; 85 L5.createLinkedListRail(n); 86 cout <<"原表表长为：" < 87 cout < 88 cout <<"原表元素为：" < 89 L5.printLinkedList(); 90 int index = -1; 91 //1，17，20，88 92 for( int i = 0; i <4; i ++ ) 93 { 94 int value; 95 cin >> value; 96 if( L5.getElementByValue( index, value ) ) 97 { 98 cout <<"pos = " <104 } 105 } 106
107 linkedList L6; 108 int n; 109 cin >> n; 110 L6.createLinkedListRail(n); 111 L6.printLinkedList(); 112 cout <113 int value = -1; 114 //5,n,1,n+1,0 115 if( L6.removeListNodeByPosition( 5, value ) ) 116 { 117 cout <<"pos = " <<5 <<", value = " <118 } 119 L6.printLinkedList(); 120 if( L6.removeListNodeByPosition( n , value ) ) 121 { 122 cout <<"pos = " <123 } 124 else 125 { 126 cout <<"不存在位置等于 " <127 } 128 L6.printLinkedList(); 129 if( L6.removeListNodeByPosition( 1, value ) ) 130 { 131 cout <<"pos = " <<1 <<", value = " <132 } 133 L6.printLinkedList(); 134 if( L6.removeListNodeByPosition( n + 1, value ) ) 135 { 136 cout <<"pos = " <137 } 138 else 139 { 140 cout <<"不存在位置等于 " <141 } 142 L6.printLinkedList(); 143 if( L6.removeListNodeByPosition( 0, value ) ) 144 { 145 cout <<"pos = " <<0 <<", value = " <146 } 147 else 148 { 149 cout <<"不存在位置等于 " <<0 <<" 的元素！" <150 } 151 L6.printLinkedList(); 152
153
154 linkedList L7; 155 int n; 156 cin >> n; 157 L7.createLinkedListRail(n); 158 cout <<"原表表长为：" <159 cout <160 cout <<"原表元素为：" <161 L7.printLinkedList(); 162
163 //int value = -1; 164 //5,n,1,n+1,0 165 for( int i = 0; i <1; i ++ ) 166 { 167 int value; 168 cin >> value; 169 if( L7.removeListNodeByPosition( 5, value ) ) 170 { 171 cout <<"pos = " <<5 <<", value = " <172 cout <<"现表表长为：" <173 cout <174 cout <<"现表元素为：" <175 L7.printLinkedList(); 176 } 177 if( L7.removeListNodeByPosition( n , value ) ) 178 { 179 cout <<"pos = " <180 } 181 else 182 { 183 cout <<"不存在位置等于 " <184 } 185 } 186
187 linkedList L8; 188 int n; 189 cin >> n; 190 L8.createLinkedListRail(n); 191 cout <<"原表表长为：" <192 cout <193
194 cout <<"原表元素为：" <195 L8.printLinkedList(); 196 int value; 197 for( int i = 0; i <4; i ++ ) 198 { 199 cin >> value; 200 if( L8.insertListSort(value) ) 201 { 202 cout <<"插入元素 " <203 cout <204 cout <<"插入元素 " <205 L8.printLinkedList(); 206 } 207 else 208 cout <<"Error!" <209 } 210
211 int n; 212 linkedList L9, LA, LB; 213 cin >> n; 214 L9.createLinkedListRail(n); 215 //LA.initiateLinkedList(), LB.initiateLinkedList(); 216 cout <<"原链表表长为：" <217 cout <218 cout <<"原链表元素为：" <219 L9.printLinkedList(); 220 L9.oddEvenSort( LA, LB ); 221 cout <<"奇数链表表长为：" <222 cout <223 cout <<"奇数链表元素为：" <224 LA.printLinkedList(); 225 cout <<"偶数链表表长为：" <226 cout <227 cout <<"偶数链表元素为：" <228 LB.printLinkedList(); 229 */
230 return 0; 231 }
图1 测试（1）
图2 测试（2）
图3 测试（3）
图4 测试（4）
图5 测试（5）
图6 测试（5）
图7 测试（6）
图8 测试（6）
图9 测试（7）
图10 测试（8）
图11 测试（8）
图12 测试（9）
图13 测试（10）
图14 测试（10）
京公网安备 11010802041100号