线性表的链式存储
链式结构存储密度小,存储空间利用率低
只能顺序存储(其中指针域用来表明节点间的关系)
插入和删除操作方便
- 初始化线性表 initlist(l)
- 销毁线性表 destorylist(l)
- 判断线性表是否为空 listempty(l)
- 求线性表的长度 listlength(l)
- 输出线性表 displist(l)
- 求线性表中某个数据元素值 getelem(l, i, e)
- 按元素值查找 locateelem(l, e)
- 插入数据元素 listinsert(l, i, e)
- 删除数据元素 listdelete(l, i, e)
代码如下:
![线性表的链式存储](https://www.ctvol.com/wp-content/themes/justnews/themer/assets/images/lazy.png)
1 #include <stdio.h> 2 #include <stdlib.h> 3 typedef int elemtype; 4 5 typedef struct lnode { 6 elemtype data; 7 struct lnode *next; 8 } linklist; 9 10 /*建立单链表*/ 11 /*头插法*/ 12 void createlistf(linklist* &l, elemtype a[], int n) { 13 l = (linklist *)malloc(sizeof(linklist)); 14 l -> next = null; 15 16 int i; 17 linklist *s; 18 for(i = 0; i < n; i++) { 19 s = (linklist *)malloc(sizeof(linklist)); 20 s -> data = a[i]; 21 s -> next = l -> next; 22 l -> next = s; 23 } 24 } 25 26 /*尾插法*/ 27 void createlistr(linklist* &l, elemtype a[], int n) { 28 l = (linklist *)malloc(sizeof(linklist)); 29 l -> next = null; 30 31 linklist *p;//指针 p 来进行操作 32 p = l; 33 34 linklist *s; 35 int i; 36 for(i = 0; i < n; i++) { 37 s = (linklist *)malloc(sizeof(linklist)); 38 s -> data = a[i]; 39 p -> next = s; 40 p = s; 41 } 42 p -> next = null; 43 } 44 45 /*基本运算*/ 46 /*初始化线性表 initlist(l)*/ 47 void initlist(linklist* &l) { 48 l = (linklist *)malloc(sizeof(linklist)); 49 l -> next = null; 50 } 51 52 /*销毁线性表 destorylist(l)*/ 53 void destorylist(linklist* &l) { 54 linklist *pre = l; 55 linklist *p = l -> next; 56 57 while(p != null) { 58 free(pre); 59 pre = p; 60 p = p -> next; 61 } 62 63 free(pre); 64 } 65 66 /*判断线性表是否为空 listempty(l)*/ 67 bool listempty(linklist* l) { 68 return l -> next == null; 69 } 70 71 /*求线性表的长度 listlength(l)*/ 72 int listlength(linklist* l) { 73 linklist *p = l; 74 int i = 0; 75 76 while(p -> next != null) { 77 p = p -> next; 78 i++; 79 } 80 81 return i; 82 } 83 84 /*输出线性表 displist(l)*/ 85 void displist(linklist* l) { 86 linklist *p = l -> next; 87 88 while(p != null) { 89 printf("%d ", p -> data); 90 p = p -> next; 91 } 92 93 printf("n"); 94 } 95 96 /*求线性表中某个数据元素值 getelem(l, i, e)*/ 97 bool getelem(linklist* l, int i, elemtype &e) { 98 linklist *p = l; 99 100 int k = 0; 101 while(k < i && p != null) { 102 k++; 103 p = p ->next; 104 } 105 106 if (p == null) { 107 return false; 108 } else { 109 e = p -> data; 110 return true; 111 } 112 } 113 114 /*按元素值查找 locateelem(l, e)*/ 115 int locateelem_wq(linklist* l, elemtype e) { 116 linklist *p = l; 117 118 int k = 0; 119 while(p != null) { 120 if (e == p -> data) { 121 return k; 122 } 123 p = p -> next; 124 k++; 125 } 126 127 return 0; 128 } 129 130 int locateelem(linklist* l, elemtype e) { 131 linklist *p = l -> next; 132 133 int k = 1; 134 while(p != null && e != p -> data) { 135 p = p -> next; 136 k++; 137 } 138 139 if (p == null) { 140 return 0; 141 } else { 142 return k; 143 } 144 } 145 146 /*插入数据元素 listinsert(l, i, e)*/ 147 bool listinsert(linklist* &l, int i, elemtype e) { 148 linklist *p = l; 149 150 int k = 0; 151 while(k < i - 1 && p != null) {//找到前驱节点 152 p = p -> next; 153 k++; 154 } 155 156 if (p == null) { 157 return false; 158 } else { 159 linklist *s; 160 s = (linklist *)malloc(sizeof(linklist)); 161 s -> data = e; 162 s -> next = p -> next; 163 p -> next = s; 164 return true; 165 } 166 } 167 168 /*删除数据元素 listdelete(l, i, e)*/ 169 bool listdelete_wq(linklist* &l, int i, elemtype &e) { 170 linklist *pre = l;//保存第 i 个指针的前驱 171 linklist *p = l -> next;//保存第 i 个指针的位置 172 173 int k = 1; 174 while(k < i && p != null) { 175 pre = pre -> next; 176 p = p -> next; 177 k++; 178 } 179 180 if (p == null) { 181 return false; 182 } else { 183 e = p ->data; 184 pre -> next = p -> next; 185 free(p); 186 return true; 187 } 188 } 189 190 bool listdelete(linklist* &l, int i, elemtype &e) { 191 linklist *pre = l;//保存第 i 个指针的前驱 192 193 int k = 0; 194 while(k < i - 1 && pre != null) { 195 pre = pre -> next; 196 k++; 197 } 198 199 if (pre == null) { 200 return false; 201 } else { 202 linklist *p; 203 p = pre -> next; 204 if (p == null) { 205 return false; 206 } 207 e = p -> data; 208 pre -> next = p -> next; 209 free(p); 210 return true; 211 } 212 } 213 214 int main(int argc, char const *argv[]) { 215 int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; 216 linklist *l; 217 initlist(l); 218 //createlistr(l, a, 9); 219 createlistf(l, a, 9); 220 displist(l); 221 printf("length = %dn", listlength(l)); 222 elemtype e; 223 getelem(l, 4, e); 224 printf("fourth number = %dn", e); 225 printf("%d is located at %dn", e, locateelem_wq(l, 6)); 226 listinsert(l, 2, 10); 227 displist(l); 228 listdelete_wq(l, 2, e); 229 displist(l); 230 return 0; 231 }
加号求调戏
这儿是运行结果哦:
9 8 7 6 5 4 3 2 1 length = 9 fourth number = 6 6 is located at 4 9 10 8 7 6 5 4 3 2 1 9 8 7 6 5 4 3 2 1
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/608377.html