【背景】
考研复习到后期，因为专业课的需要开始对数据结构学科的复习，把之前的实验重新用C语言实现了一遍，其中线性表部分是复习的第一部分，编码过程中也发现之前的潜在问题，以前的编码利用C/C++混编，个人在纯C编程上一定程度上碰了壁，如指针与引用与取地址符号等问题在C语言上的区分，更加明确了C与C++之间的界限。而今天的主角是线性表。
线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。
【源码运行环境】
操作系统：MAC OS X 10.13.4
编译环境：CLion (C++ 14) cmake
【源码实现】
List.h 源码部分
//
// 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 20
typedef 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 源码部分：
//
// 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 源码如下：
//
// 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;
}
【分析/总结】
顺序线性表具有如下优点：
-
无需为表示表中元素之间的逻辑关系增加额外的存储空间；
-
考研快速地存储表中任一位置的元素；
顺序线性表具有以下缺点：
-
插入和删除操作需要移动大量元素；
-
当线性表长度变化较大时，难以确定存储空间的容量；
-
造成存储空间的碎片；
链式线性表具有以下优点：
-
插入和删除操作只需要改变指针指向，时间效率高；
-
不需要提前分配空间，随用随分配，灵活性高；
-
在内存空间分配上灵活性高；
链式线性表具有以下缺点：
-
查找效率慢；
-
需要为地址开辟额外的存储空间；
总结：
从功能需求上看若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。反之宜采用链式存储结构。
而从空间分配上看，当线性表元素变化较大或者根本不知道有多大的时候，宜采用单链表存储结构。反之宜采用顺序存储结构。
【参考文献】
《大话数据结构》.程杰.清华大学出版社