基本数据结构实现–单链表【含测试代码】
- 2021 年 6 月 28 日
- 筆記
- 基本数据结构实现(包括测试代码)
基本数据结构实现–单链表
链表是线性表的另一种实现方式。与顺序表不同，链表中逻辑上相邻的数据元素在物理上未必相邻，而是通过一个指针指明下一个元素的
物理地址。单链表中节点类型的描述如下：
1 struct LNode { 2 ElemType data; //节点数据域 3 LNode* next; //指向下一个节点的指针 4 }; 5 typedef LNode* LinkList;
单链表的优点：与顺序表相比，单链表的优点在于插入和删除操作：虽然单链表的插入和删除操作与顺序表一样时间复杂度都是O(n),但是对于单链表来说，
插入和删除时的基本操作主要是“比较”（对于按位插入删除，比较是否到了第i位；对于按值操作，比较值是否相等），而顺序表插入和删除时
的基本操作主要是“移动”。从硬件的角度讲，做一次比较运算的时间是远小于赋值运算的。因此，链表的插入和删除操作要高效得多。
单链表的缺点：由于单链表中逻辑上相邻的元素在物理上未必相邻，故不能根据第一个元素的地址立即计算出第i个元素的地址。于是单链表不支持随机访问。
（所谓随机访问是指：根据起始地址加上元素序号就可以立即找到任意一个元素。）要在单链表中访问第i个元素，必须一个一个访问链表中每一个元素直到
第i个。
以下代码实现一个带头节点的单链表，并尝试实现一种重要操作：将链表反序
1 /* 带头节点的单链表 2 3 实现操作： 4 *1 判空 5 *2 求表长 6 *3 按位序查找 7 *4 按值查找 8 *5 前插操作 9 *6 后插操作 10 *7 按位插入 11 *8 删除指定节点 12 *9 按位删除 13 *10 单链表的建立-头插和尾插 14 */ 15 #include <iostream> 16 #include <cstdio> 17 using namespace std; 18 19 typedef int ElemType; 20 typedef struct LNode { 21 ElemType data; //节点数据域 22 LNode* next; //指向下一个节点的指针 23 } * LinkList; 24 25 bool Empty(LinkList& L) 26 { 27 if( L->next == NULL ) 28 return true; 29 return false; 30 } 31 32 //求表的长度 33 int Length(LinkList L) 34 { 35 int len = 0; 36 LNode* p = L; 37 //始终让p指向第j个节点，当p没有下一个节点时，j就是表的长度 38 while( p->next != NULL ) { 39 len++; 40 p = p->next; 41 } 42 return len; 43 } 44 45 //按位序查找，返回指向第i个节点的指针 46 //查找失败时返回的是NULL 47 LNode* GetElem(LinkList L,int i) 48 { 49 if( i < 0 ) 50 return NULL; 51 int j = 0; 52 LNode* p = L; 53 while( j < i && p != NULL ) { 54 j++; 55 p = p->next; 56 } 57 return p; //i=0时返回的是头节点,i值大于表长是返回的是空指针 58 } 59 60 //按值查找，找到数据域为e的节点,返回其指针 61 LNode* LocateElem(LinkList L,ElemType e) 62 { 63 LNode* p = L->next; //注意不是LNode* p = L :因为指向头节点，数据域是未知的 64 while( p != NULL && p->data != e ) { 65 p = p->next; 66 } 67 return p; //若e不存在，返回空指针 68 } 69 70 //前插操作：在p节点之前插入元素e 71 bool InsertPriorNode(LNode* p,ElemType e) 72 { 73 if( p == NULL ) 74 return false; 75 76 //偷天换日 77 LNode* s = new LNode; 78 s->next = p->next; 79 p->next = s; 80 s->data = p->data; 81 p->data = e; 82 return true; 83 } 84 85 //后插操作：在p节点之后插入元素e 86 bool InsertNextNode(LNode* p,ElemType e) 87 { 88 if( p == NULL ) 89 return false; 90 LNode* s = new LNode; 91 s->data = e; 92 s->next = p->next; 93 p->next = s; 94 return true; 95 } 96 97 //按位插入：在单链表L的第i个位置插入元素e 98 bool ListInsert(LinkList& L,int i,ElemType e) 99 { 100 if( i < 1 ) 101 return false; //位序最小是1 102 103 //先拿到指向第i-1个节点的指针，然后在他后面插入元素e 104 LNode* p = GetElem(L,i-1); 105 return InsertNextNode(p,e); 106 } 107 108 //删除指定节点p 109 bool DeleteNode(LNode* p) 110 { 111 if( p == NULL ) 112 return false; 113 //偷天换日 114 LNode* s = p->next; 115 //有bug：当p是最后一个节点时，无法删除(无法从p->next获取data) 116 //非要删除最后一个节点的话，可以传L头节点指针进来 117 p->data = s->data; 118 p->next = s->next; 119 delete s; 120 121 return true; 122 } 123 124 //按位删除：删除单链表L的位序为i的元素，并用e返回 125 bool ListDelete(LinkList& L, int i,int& e) 126 { 127 if( i < 1 ) 128 return false; 129 LNode* p = GetElem(L,i-1); 130 131 if( p == NULL ) //没有第i-1个节点，更没有第i个节点 132 return false; 133 if( p->next == NULL ) //找到了第i-1个节点，但是没有第i个节点 134 return false; 135 LNode* t = p->next; 136 e = t->data; 137 p->next = t->next; 138 delete t; 139 return true; 140 } 141 142 //头插法建立单链表(假设所给数据从键盘输入) 143 LinkList List_HeadInsert(LinkList& L) 144 { 145 //假设元素为int型 146 int x; 147 L = new LNode; 148 L->next = NULL; 149 while( cin >> x ) { 150 InsertNextNode(L,x); 151 } 152 return L; 153 } 154 155 //尾插法建立单链表(假设所给数据从键盘输入) 156 LinkList List_TailInsert(LinkList& L) 157 { 158 //假设元素为int型 159 int x; 160 L = new LNode; 161 L->next = NULL; 162 LNode* r = L; 163 while( cin >> x ) { 164 LNode* s = new LNode; 165 s->data = x; 166 r->next = s; 167 r = s; //创建过程中不必将尾节点的next置空，因为后面还会有节点 168 } 169 r->next = NULL; //链表创建结束，最后一个节点的下一个节点置空 170 return L; 171 } 172 173 //按顺序输出单链表中所有元素 174 void Print(LinkList L) 175 { 176 if( L == NULL ) 177 return ; 178 LNode* iterater = L->next; 179 while( iterater != NULL ) { 180 cout << iterater->data << endl; 181 iterater = iterater->next; 182 } 183 } 184 185 void test1() 186 { 187 //*测试使用a[i]=2*i的100个元素建立链表 188 int a[100]; 189 for( int i=0; i<100; i++ ) { 190 a[i] = 2*i; 191 } 192 LinkList L = new LNode; 193 L->next = NULL; 194 //使用尾插法将以上数组插入链表L 195 LNode* r = L; 196 for( int i=0; i<100; i++ ) { 197 198 LNode* s = new LNode; 199 s->data = a[i]; 200 r->next = s; 201 r = s; 202 } 203 r->next = NULL; 204 205 //*测试在值为20的元素后插入元素985211 206 LNode* t = LocateElem(L,20); //按值查找 207 InsertNextNode(t,985211); 208 209 //*测试删除位序为15的元素(值应该是26) 210 LNode* tt = GetElem(L,15); //按位序查找 211 if( tt != NULL ) { 212 DeleteNode(tt); 213 } 214 215 //*测试按位序删除位序为100的元素 216 int ttt = 0; 217 if( ListDelete(L,100,ttt) ) 218 cout << "按位序删除成功，删除的元素是：" << ttt << endl; 219 Print(L); 220 cout << "-------------------------------" << endl; 221 222 223 //下面尝试将L反序 *****重要***** 224 //抓住链表中的第一个数据元素,一个一个往后进行头插,表头结点指针还是L 225 LNode* it = L->next; 226 L->next = NULL; //*****第一个数据已经抓住了;不加这句会导致表尾自己指向自己(而非指向NULL) 227 228 //从链表的第一个节点开始，一个一个地在将表中所有节点重新插在表头 229 while( it != NULL ) { 230 LNode* nxt = it->next; 231 it->next = L->next; 232 L->next = it; //头插法重构链表，即可将链表反序 233 it = nxt; 234 } 235 Print(L); 236 237 //*测试查找不存在的元素返回空指针 238 if( LocateElem(L,999) == NULL ) { 239 cout << endl << "999不存在" << endl; 240 } 241 242 } 243 244 //测试头插法 245 void test2() 246 { 247 LinkList L; 248 List_HeadInsert(L); 249 Print(L); 250 } 251 252 int main() 253 { 254 // test1(); 255 // test2(); 256 return 0; 257 }
