数据结构之线性表(C语言版)-创新互联


  线性表(List)是最常见的也是最简单的一种数据结构。所谓线性表就是零个或者多个数据元素的有限序列。注意定义中的几个关键字:有限、序列。有限就是告诉我们元素个数是有限的;而序列就是说元素之间是有顺序的。

十年的崂山网站建设经验,针对设计、前端、开发、售后、文案、推广等六对一服务,响应快,48小时及时工作处理。营销型网站的优势是能够根据用户设备显示端的尺寸不同,自动调整崂山建站的显示方式,使网站能够适用不同显示终端,在浏览器中调整网站的宽度,无论在任何一种浏览器上浏览网站,都能展现优雅布局与设计,从而大程度地提升浏览体验。成都创新互联公司从事“崂山网站设计”,“崂山网站推广”以来,每个客户项目都认真落实执行。

线性表的抽象数据类型:

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

ListInsert(&L,i,e)线性表已存在,并且1< i

ListDelist(&L,i,&e)线性表已存在,并且1< i

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

#include

#include

#include

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<<"存储空间已满,不能插入"<

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<<"存储空间,不能插入"<

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  <

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<<"插入位置错误"<

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<<"空间已无元素不能删除了"<

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<<"空间已无元素不能删除了"<

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<<"删除位置出错"<

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<<"空间已无元素不能删除了"<

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<bace[i]<<"  ";

}

cout<

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<<"***************************************"<

cout<<"* [1] InitList    [2] Insert_Front  *"<

cout<<"* [3] Insert_Back  [4] Insert_Value  *"<

cout<<"* [5] Insrt_pos   [6] Delite_Front  *"<

cout<<"* [7] Delite_Back  [8] Delite_pos   *"<

cout<<"* [9] Delite_value  [10] Clear_List   *"<

cout<<"* [11] Sort_List   [12] Reserve_List *"<

cout<<"* [13] Show_List   [14] Destory_List *"<

cout<<"*          [0] Exit_System  *"<

cout<<"***************************************"<

}

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;

}

}

}


 以上代码都是笔者进行了测试,数据结构部分主要是关注对于顺序表的基本操作,主程序这里只是作为测试程序,没有在进一步优化,并且,顺序表的插入删除,这里是不考虑相同元素的,尤其在按值删除时,只会删除掉优先遇到的值,并不会全部删除相同的值


顺序表的优缺点:

优点:可以快速获取到表中任意数据元素,

缺点:插入和删除操作需要移动大量元素,当线性表的长度变化较大时,很难确定存储空间的大小,造成存储空间“碎片”当顺序表比较长时,插入、删除时比较浪费时间。

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


当前标题:数据结构之线性表(C语言版)-创新互联
标题来源:http://myzitong.com/article/dsjiig.html