创新互联是一家专注于网站制作、成都网站建设与策划设计,瓯海网站建设哪家好?创新互联做网站,专注于网站建设10年,网设计领域的专业建站公司;建站业务涵盖:瓯海等地区。瓯海做网站价格咨询:13518219792
线性表（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 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< } 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; } } } 以上代码都是笔者进行了测试，数据结构部分主要是关注对于顺序表的基本操作，主程序这里只是作为测试程序，没有在进一步优化，并且，顺序表的插入删除，这里是不考虑相同元素的，尤其在按值删除时，只会删除掉优先遇到的值，并不会全部删除相同的值。 顺序表的优缺点： 优点：可以快速获取到表中任意数据元素， 缺点：插入和删除操作需要移动大量元素，当线性表的长度变化较大时，很难确定存储空间的大小，造成存储空间“碎片”当顺序表比较长时，插入、删除时比较浪费时间。
本文标题：数据结构之线性表（C语言版）
本文地址：http://bjjierui.cn/article/jgdjds.html
