线性表（List）是最常见的也是最简单的一种数据结构。所谓线性表就是零个或者多个数据元素的有限序列。注意定义中的几个关键字：有限、序列。有限就是告诉我们元素个数是有限的；而序列就是说元素之间是有顺序的。
线性表的抽象数据类型：
ADT线性表（List）
Data
线性表的数据元素集合对象为{a1、a2、……an}，每个数据元素的类型均为DataType。其中除了第一个元素外，每一个元素有且只有一个直接前驱元素，出来最后一个元素外，每一个元素有且只有一个后继元素。元素之间的关系是一一对应的关系。
Operation
InitList（&L）：初始化操作，建立一个空的线性表L。
DestoryList（&L）：线性表已存在，销毁线性表L。
ClearList(&L):线性表已存在，将L重置为空表。
ListEmpty（L）:线性表已存在,若L为空表，则返回TRUE，否则返回FALSE.
ListLength（L）：线性表已存在,返回线性表的数据元素的个数。
GetElem（L,I,&x）：线性表已存在，并且1< i <ListLength,用x返回L中第i个元素的值。
ListInsert（&L,i，e）线性表已存在，并且1< i <ListLength,在i之前位置插入新的数据元素，L的长度加1。
ListDelist（&L，i，&e）线性表已存在，并且1< i <ListLength,删除线性表L的第i个元素，并且用e返回其值，L的长度减1。
InsertList_Back(*L, x):线性表已存在 ,从线性表的尾部开始插入元素，L的长度加1。
InsertList_Front(*L, ElemType x)：线性表已存在 ,从线性表的头部开始插入元素，L的长度加1。
DelitelList_Back(*L)：线性表已存在 ,从线性表的尾部开始删除元素，L的长度减1。
DelitelList_Front(*L)：线性表已存在 ,从线性表的头部开始删除元素，L的长度减1。
Delite_Val(*L, key)：线性表已存在，如果线性表中存在key值，则删除线性表中的key值，L的长度减1,并且返回TRUE,如果线性表中不存在key值，则返回FALSE.
void Clear(*L):线性表已存在,清空现象表中的所有元素。
void Sort(*L);线性表已存在，对线性表中存在的元素排序。排序成功返回TRUE，排序失败返回FALSE。
Reverse (*L)：线性表已存在，并且顺序表中存在元素，逆置。逆置成功返回TRUE，失败返回FALSE。
void Show_list(*L)：线性表已存在，打印输出，线性表中 所有元素。
endADT
线性表的存储结构，前边我们已经提过，对于数据的存储结构只有两种，一种为顺序存储结构，另一种为链式存储结构。线性表作为一种数据结构也有两种存储结构，今天我们先只谈顺序存储结构，也就是顺序表，链式存储结构，我将在后边总结。
头文件宏定义等声明：
#include<stdio.h>
#include<Windows.h>
#include<malloc.h>
#include<iostream>
using namespace std;
#include"SeqList.h"
#define ElemType int
#define DEFAULT_SIZE 8
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;
typedef int DataType;
初始化操作：
typedef struct List
{
DataType *bace;
int capacity;
int length;
}SeqList;
//初始化顺序表，初始化成功返回OK，失败返回ERROR
Status Init_list(SeqList *list)
{
list->capacity = DEFAULT_SIZE ;
list->bace = (DataType *)malloc(sizeof(DataType) * list->capacity );
list->length = 0;
if(NULL == list->bace)
{
return ERROR;
}
else
return OK;
}
插入元素操作：
//顺序表头插元素，插入成功返回TRUE,插入失败返回FALSE,
Status Insert_front(SeqList *list,ElemType x)
{
if(list->length >= list->capacity)
{
cout<<"存储空间已满，不能插入"<<x <<endl;
return FALSE;
}
for(int i = list->length; i > 0; i--)
{
list->bace[i] = list->bace[i - 1];
}
list->bace[0] = x;
list->length++;
return TRUE;
}
//顺序表尾插，插入成功返回TRUE,插入失败返回ERROR
Status Insert_back(SeqList *list, ElemType x)
{
if(list->length >= list->capacity)
{
cout<<"存储空间，不能插入"<<x <<endl;
return FALSE;
}
list->bace[list->length] = x;
list->length++;
return TRUE;
}
//顺序表按照值插入，插入成功返回TRUE，插入失败返回ERROR
Status Insert_Value(SeqList *list, ElemType x)
{
int i;
if(list->length >= list->capacity)
{
cout<<"存储空间，不能插入"<< x <<endl;
return FALSE;
}
for(i = list->length; i > 0; i--)
{
if(list->bace[i-1] > x)
list->bace[i] = list->bace[i - 1];
else
break;
}
list->bace[i] = x;
list->length++;
return TRUE;
}
//按照位置插入，插入成功返回TRUE，插入失败返回ERROR
Status Insert_pos(SeqList *list,int pos,ElemType x)
{
if(pos < 0 || pos >= list->length)
{
cout<<"插入位置错误"<<x <<"未能插入"<<endl;
return FALSE;
}
for(int i = list->length; i > pos; i--)
{
list->bace[i] = list->bace[i - 1];
}
list->bace[pos] = x;
list->length++;
return TRUE;
}
删除元素操作：
//头删,删除成功返回TRUE，删除失败返回ERROR
Status Delise_Front(SeqList *list,ElemType *x)
{
if(0 == list->length)
{
cout<<"空间已无元素不能删除了"<<endl;
return FALSE;
}
*x = list->bace[0];
for(int i = 0; i < list->length ; i++)
{
list->bace[i] = list->bace[i + 1];
}
list->length--;
return TRUE;
}
//尾删,删除成功返回TRUE，删除失败返回ERROR
Status Delite_back(SeqList *list, ElemType *x)
{
if(0 == list->length)
{
cout<<"空间已无元素不能删除了"<<endl;
return FALSE;
}
*x = list->bace[list->length - 1];
list->length--;
return TRUE;
}
//按位置删除，删除成功返回TRUE，删除失败返回ERROR
Status Delite_pos(SeqList *list,int pos,ElemType *x)
{
if(pos < 0 || pos >= list->length )
{
cout<<"删除位置出错"<<endl;
return FALSE;
}
*x = list->bace[pos];
for(int i = pos; i < list->length; i++)
{
list->bace[i] = list->bace[i + 1];
}
list->length--;
return TRUE;
}
//按值删除，删除成功返回TRUE，删除失败返回ERROR
Status Delite_value(SeqList *list, ElemType x)
{
if(0 == list->length)
{
cout<<"空间已无元素不能删除了"<<endl;
return FALSE;
}
for(int i = 0; i < list->length; i++)
{
if( x == list->bace[i])
{
list->bace[i] = list->bace[i + 1];
list->length--;
}
}
return TRUE;
}
取元素操作：
//打印输出顺序表
Status Show_list(SeqList *list)
{
for(int i = 0; i < list->length; i++)
{
cout<<list->bace[i]<<" ";
}
cout<<endl;
return TRUE;
}
排序、逆置等其他操作：
//清空顺序表
Status Clear(SeqList *list)
{
list->length = 0;
return TRUE;
}
//排序排序操作，这里采用冒泡排序，读者也可以采用其他排序方法。
Status Sort_List(SeqList *list)
{
for(int i = 0; i < list->length - 1; i++)
{
for(int j = 0; j < list->length - i - 1; j ++)
{
if(list->bace[j] > list->bace[j + 1])
{
ElemType temp = list->bace[j];
list->bace[j] = list->bace[j + 1];
list->bace[j + 1] = temp;
}
}
}
return TRUE;
}
//释放内存空间
Status Destory(SeqList *list)
{
list->length = 0;
list->capacity = 0;
free(list->bace);
list->bace = NULL;
return TRUE;
}
主函数测试程序：
typedef enum
{
EXIT,
INIT_LIST,
INSERT_FRONT,
INSERT_BACK,
INSERT_VALUE,
INSERT_POS,
DELITE_FRONT,
DELITE_BACK,
DELITE_POS,
DELITE_VALUE,
CLEAR_LIST,
SORT_LIST,
RESERVE_LIST,
SHOW_LIST,
DESTORY_LIST,
}ENUM;
void show()
{
cout<<"***************************************"<<endl;
cout<<"* [1] InitList [2] Insert_Front *"<<endl;
cout<<"* [3] Insert_Back [4] Insert_Value *"<<endl;
cout<<"* [5] Insrt_pos [6] Delite_Front *"<<endl;
cout<<"* [7] Delite_Back [8] Delite_pos *"<<endl;
cout<<"* [9] Delite_value [10] Clear_List *"<<endl;
cout<<"* [11] Sort_List [12] Reserve_List *"<<endl;
cout<<"* [13] Show_List [14] Destory_List *"<<endl;
cout<<"* [0] Exit_System *"<<endl;
cout<<"***************************************"<<endl;
}
void insert_fr(SeqList *list)
{
ElemType x;
printf("请输入要插入的元素\n");
scanf("%d",&x);
int result1 = Insert_front(list, x);
if(TRUE == result1)
printf("insert frount ok\n");
else
printf("insert frount error\n");
}
void insert_ba(SeqList *list)
{
ElemType x;
printf("请输入要插入的元素\n");
scanf("%d",&x);
int result1 = Insert_back(list,x);
if(TRUE == result1)
printf("insert back ok\n");
else
printf(" insert back error\n");
}
void insert_value(SeqList *list)
{
ElemType x;
printf("请输入要插入的元素\n");
scanf("%d",&x);
int result1 = Insert_Value(list,x);
if(TRUE == result1)
printf("insert value ok\n");
else
printf("insert value error\n");
}
void insert_pos(SeqList *list)
{
int pos,x;
printf("请输入要插入的位置和值\n");
scanf("%d%d",&pos,&x);
int result1 = Insert_pos(list,pos, x);
if(TRUE == result1)
printf("insert pos x ok\n");
else
printf("insert pos x error\n");
}
void delite_fr(SeqList *list)
{
int x;
int result1 = Delise_Front(list, &x);
if(TRUE == result1)
{
printf("delite ok\n");
}
else
printf("delite fr error\n");
}
void delite_br(SeqList *list)
{
int x;
int result1 = Delite_back(list, &x);
if(TRUE == result1)
{
printf("delite ok\n");
}
else
printf("delite br error\n");
}
void delite_pos(SeqList *list)
{
int pos, x;
printf("请输入要删除的位置：\n");
scanf("%d",&pos);
int result1 = Delite_pos(list,pos,&x);
if(TRUE == result1)
{
printf("%d delite pos ok\n",x);
}
else
printf("delite pos error\n");
}
void delite_value(SeqList *list)
{
int x;
printf("请输入要删除的值\n");
scanf("%d",&x);
int result1 = Delite_value(list, x);
if(TRUE == result1)
{
printf("%d delite pvalue ok\n",x);
}
else
printf("delite value error\n");
}
void clear_list(SeqList *list)
{
int result1 = Clear(list);
if(TRUE == result1)
{
printf("clear ok\n");
}
else
printf("clear error\n");
}
void sort_list(SeqList *list)
{
int result1 = Sort_List(list);
if(TRUE == result1)
{
printf(" sort ok\n");
}
else
printf("sort error\n");
}
void show_list(SeqList *list)
{
int result1 = Show_list(list);
if(TRUE == result1)
{
printf(" show ok\n");
}
else
printf("show error\n");
}
void destory(SeqList *list)
{
int result1 = Destory(list);
if(TRUE == result1)
{
printf(" destor ok\n");
}
else
printf("detor error\n");
}
void Reserve(SeqList *list)
{
int result1 = Reserve_List (list);
if(TRUE == result1)
{
printf(" res ok\n");
}
else
printf("res error\n");
}
void main()
{
int Select_Value,Cyc_Value = 1;
SeqList list;
int result1 = Init_list(&list);
while(Cyc_Value)
{
show();
printf("请选择\n");
scanf("%d",&Select_Value);
switch(Select_Value)
{
case INIT_LIST:
Init_list(&list);
break;
case INSERT_FRONT:
insert_fr(&list);
break;
case INSERT_BACK:
insert_ba(&list);
break;
case INSERT_VALUE:
insert_value(&list);
break;
case INSERT_POS:
insert_pos(&list);
break;
case DELITE_FRONT:
delite_fr(&list);
break;
case DELITE_BACK:
delite_br(&list);
break;
case DELITE_POS:
delite_pos(&list);
break;
case DELITE_VALUE:
delite_value(&list);
break;
case CLEAR_LIST:
clear_list(&list);
break;
case SORT_LIST:
sort_list(&list);
break;
case RESERVE_LIST:
Reserve(&list);
break;
case SHOW_LIST:
show_list(&list);
break;
case DESTORY_LIST:
destory(&list);
break;
case EXIT:
Cyc_Value = 0;
break;
default :
printf("输入选项错误,请重新选择\n");
break;
}
}
}
以上代码都是笔者进行了测试，数据结构部分主要是关注对于顺序表的基本操作，主程序这里只是作为测试程序，没有在进一步优化，并且，顺序表的插入删除，这里是不考虑相同元素的，尤其在按值删除时，只会删除掉优先遇到的值，并不会全部删除相同的值。
顺序表的优缺点：
优点：可以快速获取到表中任意数据元素，
缺点：插入和删除操作需要移动大量元素，当线性表的长度变化较大时，很难确定存储空间的大小，造成存储空间“碎片”当顺序表比较长时，插入、删除时比较浪费时间。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
