首页 > 代码库 > 顺序表--数组
顺序表--数组
顺序表结点的存储地址计算公式：
第i个数据元素的存储位置：Loc(ai)=Loc(ai)+(i-1)*l；1≤i≤n（l为每个元素需占l个存储单元）
第（i+1）个数据元素的存储位置Loc(ai+1)和第i个数据元素的存储位置Loc(ai)的关系：Loc(ai+1)=Loc(ai)+l;
数组：
#define OK 1#define ERROR -1#define MAX_SIZE 100typedef int Status ;typedef int ElemType ; typedef struct sqlist{ ElemType elem_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 ) return ERROR ; L->length= 0 ; return OK ; }
2. 顺序线性表的插入---实现步骤（Einsert=n/2，平均时间复杂度为O(n)）
/*
(1) 将线性表L中的第i个至第n个结点后移一个位置。
(2) 将结点e插入到结点ai-1之后。
(3) 线性表长度加1
*/
Status Insert_SqList(Sqlist *L，int i ，ElemType e) { int j ; if( i<1||i>L->length+1) return ERROR ; //i合法值1到length+1 if(L->length>=MAX_SIZE) { printf(“线性表溢出!\n”); return ERROR ; } 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++ ; return OK ; }
3 顺序线性表的删除（Einsert=（n-1）/2，平均时间复杂度为O(n)）
/*
(1) 将线性表L中的第i+1个至第n个结点依此向前移动一个位置。
(2) 线性表长度减1。
*/
ElemType Delete_SqList(Sqlist *L，int i){ int k ; ElemType x ; if(L->length==0) { printf(“线性表L为空!\n”); return ERROR; } if(i<1||i>L->length) { printf(“要删除的数据元素不存在!\n”) ; return ERROR ; } x=L->Elem_array[i-1] ; /*保存结点的值*/ for(k=i; k<L->length; k++) L->Elem_array[k-1]=L->Elem_array[k];/* i位置以后的所有结点前移 */ L->length--; return (x);}
4 顺序线性表的查找定位删除---实现步骤（Ecompare=(n+1)/2，Edelete=(n-1)/2，平均时间复杂度：Ecompare+Edelete=n ，即为O(n) ）
/*
(1) 在线性表L查找值为x的第一个数据元素。
(2) 将从找到的位置至最后一个结点依次向前移动一个位置。
(3) 线性表长度减1。
*/
Status Locate_Delete_SqList(Sqlist *L，ElemType x)/* 删除线性表L中值为x的第一个结点 */{ int i=0 , k ; while(i<L->length) /*查找值为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 ; } return OK; }
动态数组：
typedef struct{ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量（以sizeof（ElemType ）为单位）}SqList;
创建顺序表（数组）：
status Init(SqList &l){ l.elem=(ElemType *)malloc(初始长度*sizeof（ElemType ）)； if(!l.elem) exit(0); l.length=0; l.listsize=初始长度; return ok; }
插入：
status insertlist(SqList *L,int i,ElemType e) //第i的位置插入元素{ if(i<1||i>L.length+1) //下表为0的作为哨兵，不放数据。判断i是否合法 return error; if(L.length>=L.listsize) //存储空间已满，增加分配空间 { newbase=(ElemType *)realloc(L.elem,（L.listsize+增量）*sizeof（ElemType ）);//L.elem原指针的位置 if(!newbase) //存储分配失败 exit(0); L.elem=newbase; //新基址 L.listsize+=增量; //增加存储容量 } q=&(L.elem[i-1]); //p插入的位置 for(p=&(L.elem[length-1]);p>=q;--p) *(p+1)=*p; //指针移动 *q=e; //插入元素 ++L.length; //表长加一 return ok;}
删除：
status deletlist(SqList *L,int i,ElemType e){ if(i<1||i>L.length) //下判断i是否合法 return error; p=&(L.elem[i-1]); //删除元素的位置 e=*p; //删除元素的值 q=L.elem+L.elem+Llength-1; //表尾的位置 for(++p;p<=q;++p) *(p-1)=*p; //元素左移 --L.length; //表长减一 return ok;}
顺序表--数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。