线性表的链式存储
2018-12-04 07:13:30来源:博客园 阅读 ()
线性表的链式存储
链式结构存储密度小,存储空间利用率低
只能顺序存储(其中指针域用来表明节点间的关系)
插入和删除操作方便
- 初始化线性表 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)
代码如下:
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 = %d\n", ListLength(L)); 222 ElemType e; 223 GetElem(L, 4, e); 224 printf("fourth number = %d\n", e); 225 printf("%d is located at %d\n", 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
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:c语言智能指针 附完整示例代码
下一篇:判断是不是素数
- C++ 共用体 2020-06-05
- STM32F103驱动M24256 256k存储芯片进行读写 2020-05-28
- C++ 自动变量 2020-05-10
- C++ 存储持续性 2020-05-10
- 图的连通分量(利用邻接表存储信息) 2020-04-02
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash