【背景】
考研复习到后期，因为专业课的需要开始对数据结构学科的复习，把之前的实验重新用C语言实现了一遍，其中线性表部分是复习的第一部分，编码过程中也发现之前的潜在问题，以前的编码利用C/C++混编，个人在纯C编程上一定程度上碰了壁，如指针与引用与取地址符号等问题在C语言上的区分，更加明确了C与C++之间的界限。而今天的主角是线性表。
线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。
【源码运行环境】
操作系统：MAC OS X 10.13.4
编译环境：CLion (C++ 14) cmake
【源码实现】
List.h 源码部分
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 | //// Created by WellLee on 2018/10/27.//#ifndef LIST_LIST_H#define LIST_LIST_H#include <stdio.h>#include <stdlib.h>/* * 说明：define 定义一些常用的符号特性 * 作用：增加代码可读性 * Author: WellLee * Last Modified: 2018年10月26日23:27:51 */#define OVERFLOW -1#define TRUE 1#define FALSE 0#define SqListMAXSIZE 20typedef int Status;typedef int Elem;/* * 结构：顺序线性表 * 作用：定义了顺序线性表的一些结构特性，封装了常用的线性表操作 * Author: WellLee * Last modified: 2018年10月26日23:26:36 */typedef struct SequenceList{ Elem elements[SqListMAXSIZE]; int Cur_length; int Max_Length;}SqList;Status InitList(SqList *L);Status ListEmpty(SqList *L);Status ClearList(SqList *L);Status GetElem(SqList *L, int i, Elem *e);Status LocateElem(SqList *L, Elem e, int *l);Status SequenceListInsert(SqList *L, int i, Elem e);Status SequenceListDelete(SqList *L, int i, Elem *e);Status ListLength(SqList *L,int *length);void showElements(SqList *L);/* * 结构：链式线性表 * 作用：定义了链式线性表的一些结构特性，封装了常用的线性表操作 * Author: WellLee * Last modified: 2018年10月28日00:15:42 */typedef struct Node{ Elem e; struct Node *next;}Node;typedef struct Node *Link;Status InitLinkList(Link *L);Status LinkListEmpty(Link L);void ShowLinkList(Link L);Status DestroyList(Link *L);Status LinkListLength(Link L,int *length);Status GetElemFromLinkList(Link L, int i,Elem *e);Status LocateElemFromLinkList(Link L,Elem e, int *i);Status LinkListInsert(Link *L, int i, Elem e);Status LinkListDelete(Link *L, int i, Elem *e);Status LinkListReverse(Link *L);#endif //LIST_LIST_H |
SequenceList.c 源码部分：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 | //// Created by WellLee on 2018/10/26.///* * 文件名：SequenceList.c * 作用：补充对顺序线性表的操作 * Author: WellLee * Last Modified: 2018年10月26日23:30:59 */#include "List.h"#include "memory.h"/* * 方法名：InitList * 作用：对顺序线性表进行初始化操作 * Author: WellLee * Last Modified:2018年10月27日23:27:19 */Status InitList(SqList *L){ int total; L->Cur_length = 0; L->Max_Length = SqListMAXSIZE; printf("请输入您要插入的元素个数（不超过20个）\n"); scanf("%d", &total); if(total < 0 || total > 20) { printf("数组溢出\n"); return OVERFLOW; } if(total == 0) { printf("There is nothing to do \n"); return FALSE; } for(int i = 0; i < total; i++) { printf("请输入第%d个元素: ",i+1); scanf("%d",&L->elements[i]); } L->Cur_length = total; return TRUE;}/* * 方法名：showElements * 作用：显示顺序线性表的元素 * Author: WellLee * Last Modified:2018年10月27日23:28:13 */void showElements(SqList *L){ if(ListEmpty(L)) { printf("这是一张空表\n"); return; } printf("线性表元素如下：总元素为%d\n", L->Cur_length); for(int i = 0; i < L->Cur_length; i++) { printf("%d ",L->elements[i]); } printf("\n");}/* * 方法名：ListEmpty * 作用：判断线性表是否为空 * Author: WellLee * Last Modified:2018年10月27日23:28:13 */Status ListEmpty(SqList *L){ if(L->Cur_length == 0) { return TRUE; } return FALSE;}/* * 方法名：ClearList * 作用：清空顺序线性表 * Author: WellLee * Last Modified:2018年10月27日23:28:13 */Status ClearList(SqList *L){ memset(L->elements,0, sizeof(L->elements)); L->Max_Length = 0; L->Cur_length = 0; return TRUE;}/* * 方法名：GetElem * 作用：获取顺序线性表指定位置的元素 * Author: WellLee * Last Modified:2018年10月27日23:28:13 */Status GetElem(SqList *L, int i, Elem *e){ if(i >= L->Cur_length || i < 0) { return OVERFLOW; } Elem a = L->elements[i]; *e = a; printf("e = %d\n", *e); return TRUE;}/* * 方法名：LocateElem * 作用：定位元素在线性表的第一次出现位置 * Author: WellLee * Last Modified:2018年10月27日23:28:13 */Status LocateElem(SqList *L, Elem e, int *l){ if(ListEmpty(L)) { return OVERFLOW; } for(int i = 0; i < L->Cur_length; i++) { if(e == L->elements[i]) { *l = i + 1; return TRUE; } } return FALSE;}/* * 方法名：SequenceListInsert * 作用：顺序线性表插入操作 * Author: WellLee * Last Modified:2018年10月27日23:28:13 */Status SequenceListInsert(SqList *L, int i, Elem e){ if(i < 0 || L->Cur_length > (SqListMAXSIZE - 1)) { return OVERFLOW; } if(i > L->Cur_length - 1) { printf("当前线性表长度为：%d ,无法满足您的插入需求\n"); return FALSE; } for(int j = L->Cur_length - 1;j >= i; j--) { L->elements[j + 1] = L->elements[j]; } L->elements[i] = e; L->Cur_length += 1; return TRUE;}/* * 方法名：SequenceListDelete * 作用：删除顺序线性表中的元素 * Author: WellLee * Last Modified:2018年10月27日23:28:13 */Status SequenceListDelete(SqList *L, int i, Elem *e){ if(ListEmpty(L) || i > L-> Cur_length - 1) { return OVERFLOW; } *e = L->elements[i]; for (int j = i; j < L->Cur_length - 1; j++) { L->elements[j] = L->elements[j+1]; } L->elements[L->Cur_length - 1] = 0; L->Cur_length -= 1; return TRUE;}/* * 方法名：ListLength * 作用：获取线性表的长度 * Author: WellLee * Last Modified:2018年10月27日23:28:13 */Status ListLength(SqList *L,int *length){ *length = L->Cur_length; return TRUE;} |
LinkList.c 源码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 | //// Created by WellLee on 2018/10/28.//#include "List.h"#include "time.h"/* * 方法名：InitLinkList * 作用：初始化链式线性表 * Author: WellLee * Last Modified:2018年10月28日12:21:18 */Status InitLinkList(Link *L){ Link p,r; int length; srand(time(0)); printf("请输入链表长度： "); scanf("%d",&length); *L = (Link)malloc(sizeof(Node)); r = *L; for (int i = 0; i < length; i++) { p = (Node *)malloc(sizeof(Node)); p->e = rand() % 100 + 1; r->next = p; r = p; } r->next = NULL; printf("链表创建完成\n");}/* * 方法名：ShowLinkList * 作用：显示链式线性表中的元素 * Author: WellLee * Last Modified:2018年10月28日12:21:18 */void ShowLinkList(Link L){ Link temp = L->next; if(!temp) { printf("这是一张空表\n"); return; } printf("链式线性表元素如下：\n"); while(temp != NULL) { printf("%d ",temp->e); temp = temp->next; } printf("\n");}/* * 方法名：LinkListEmpty * 作用：判断链式线性表是否为空 * Author: WellLee * Last Modified:2018年10月28日12:21:18 */Status LinkListEmpty(Link L){ if(L->next == NULL) { return TRUE; } return FALSE;}/* * 方法名：DestroyList * 作用：销毁链式线性表 * Author: WellLee * Last Modified:2018年10月28日12:21:18 */Status DestroyList(Link *L){ Link temp = *L; Link freePoint; freePoint = temp; temp = temp->next; freePoint->next = NULL; while(temp != NULL) { freePoint = temp; temp = temp->next; printf("释放元素为%d 的节点内存\n",freePoint->e); free(freePoint); } return TRUE;}/* * 方法名：LinkListLength * 作用：获取链式线性表长度 * Author: WellLee * Last Modified:2018年10月28日12:21:18 */Status LinkListLength(Link L,int *length){ Link temp = L->next; *length = 0; while(temp != NULL) { *length += 1; temp = temp->next; }}/* * 方法名：GetElemFromLinkList * 作用：从链式线性表中获取指定位置的元素 * Author: WellLee * Last Modified:2018年10月28日12:21:18 */Status GetElemFromLinkList(Link L, int i, Elem *e){ int cur_length; LinkListLength(L, &cur_length); if(!L || i > cur_length || i <= 0){ printf("越界！\n"); return OVERFLOW; } Link temp = L->next; for(int j = 0; j < i - 1; j++) { temp = temp->next; } *e = temp->e; return TRUE;}/* * 方法名：LocateElemFromLinkList * 作用：定位元素在链式线性表中的位置 * Author: WellLee * Last Modified:2018年10月28日12:21:18 */Status LocateElemFromLinkList(Link L,Elem e,int *i){ int cur_length= 0; LinkListLength(L, &cur_length); if(!L) { printf("越界\n"); return OVERFLOW; } Link temp = L->next; int flag = FALSE; int c; for(c = 0; c < *i; c++){ if(temp->e != e){ temp = temp->next; continue; } flag = TRUE; break; } if(flag) { *i = c + 1; } else{ *i = -1; } return TRUE;}/* * 方法名：LinkListInsert * 作用：向链式线性表中指定位置插入元素 * Author: WellLee * Last Modified:2018年10月28日12:21:18 */Status LinkListInsert(Link *L, int i, Elem e){ Link temp = *L; Link p = *L; temp = temp->next; int length = 0; LinkListLength(*L, &length); if(i < 0 || i > length + 1) { printf("越界\n"); return OVERFLOW; } for(int c = 0; c < i - 1; c++) { p = temp; temp = temp->next; } Link node = (Link)malloc(sizeof(Node)); node->e = e; node->next = temp; p->next = node; return TRUE;}/* * 方法名：LinkListDelete * 作用：删除链式线性表中指定位置的元素 * Author: WellLee * Last Modified:2018年10月28日12:21:18 */Status LinkListDelete(Link *L, int i, Elem *e){ Link temp = *L; Link p = *L; temp = temp->next; int length; LinkListLength(p,&length); if(i < 0 || i > length) { printf("越界\n"); return OVERFLOW; } for(int c = 0; c < i-1; c++) { p = temp; temp = temp->next; } Link freepoint; freepoint = temp; p->next = temp->next; *e = freepoint->e; free(freepoint); return TRUE;} |
【分析/总结】
顺序线性表具有如下优点：
-
无需为表示表中元素之间的逻辑关系增加额外的存储空间；
-
考研快速地存储表中任一位置的元素；
顺序线性表具有以下缺点：
-
插入和删除操作需要移动大量元素；
-
当线性表长度变化较大时，难以确定存储空间的容量；
-
造成存储空间的碎片；
链式线性表具有以下优点：
-
插入和删除操作只需要改变指针指向，时间效率高；
-
不需要提前分配空间，随用随分配，灵活性高；
-
在内存空间分配上灵活性高；
链式线性表具有以下缺点：
-
查找效率慢；
-
需要为地址开辟额外的存储空间；
总结：
从功能需求上看若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。反之宜采用链式存储结构。
而从空间分配上看，当线性表元素变化较大或者根本不知道有多大的时候，宜采用单链表存储结构。反之宜采用顺序存储结构。
【参考文献】
《大话数据结构》.程杰.清华大学出版社