数据结构|线性表的基本操作数据结构|c语言

借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。

#defineOK1 #defineERROR-1 #defineMAX_SIZE100 typedefintStatus ; typedefintElemType ; typedefstructsqlist {ElemTypeElem_array[MAX_SIZE] ; int length ; } SqList ;

【数据结构|线性表的基本操作】1 顺序线性表初始化

Status Init_SqList( SqList *L ) {L->elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ; if ( !L -> elem_array ) returnERROR ; else {L->length= 0 ; return OK ; } }

2 顺序线性表的插入
在线性表 L= (a1，…a i-1，ai， ai+1，…，an) 中的第i(1≦i≦n)个位置上插入一个新结点e，使其成为线性表：
L=(a1，…a i-1，e，ai，ai+1，…，an)
实现步骤
(1) 将线性表L中的第i个至第n个结点后移一个位置。
(2) 将结点e插入到结点ai-1之后。
(3) 线性表长度加1。
算法描述

Status Insert_SqList(Sqlist *L，int i ，ElemType e) {int j ; if( i<0||i>L->length-1)returnERROR ; if(L->length>=MAX_SIZE) {printf(“线性表溢出!\n”); returnERROR ; } for( j=L->length–1; j>=i-1; --j ) L->Elem_array[j+1]=L->Elem_array[j]; /*i-1位置以后的所有结点后移*/ L->Elem_array[i-1]=e; /*在i-1位置插入结点*/ L->length++ ; returnOK ; }

3 顺序线性表的删除
在线性表 L=(a1，…a i-1，ai， ai+1，…，an) 中删除结点ai(1≦i≦n)，使其成为线性表：
L= (a1，…ai-1，ai+1，…，an)
实现步骤
(1) 将线性表L中的第i+1个至第n个结点依此向前移动一个位置。
(2) 线性表长度减1。
算法描述

ElemTypeDelete_SqList(Sqlist *L，int i) {intk ; ElemTypex ; if(L->length==0) {printf(“线性表L为空!\n”); return ERROR; } else if ( i<1||i>L->length ) {printf(“要删除的数据元素不存在!\n”) ; return ERROR ; } else{x=L->Elem_array[i-1] ; /*保存结点的值*/ for ( k=i ; klength ; k++) L->Elem_array[k-1]=L->Elem_array[k]; /*i位置以后的所有结点前移*/ L->length--; return (x); } }

4 顺序线性表的查找定位删除
在线性表 L= (a1，a2，…，an) 中删除值为x的第一个结点。
实现步骤
(1) 在线性表L查找值为x的第一个数据元素。
(2) 将从找到的位置至最后一个结点依次向前移动一个位置。
(3) 线性表长度减1。
算法描述

StatusLocate_Delete_SqList(Sqlist *L，ElemType x) /*删除线性表L中值为x的第一个结点*/ {inti=0 , k ; while(ilength)/*查找值为x的第一个结点*/ {if(L->Elem_array[i]!=x )i++ ; else {for ( k=i+1; k< L->length; k++) L->Elem_array[k-1]=L->Elem_array[k]; L->length--; break ; } } if(i>L->length) {printf(“要删除的数据元素不存在!\n”) ; return ERROR ; } returnOK; }

完整程序会在下一篇博客中给出。