Basic operations of sequence table in C language

目录

顺序表的类型定义：

顺序表的基本操作：/*补充//函数结果状态代码

1:顺序表L得初始化（参数引用）

2:销毁顺序表L

3:清空顺序表L

4:求顺序表的长度

5:判断顺序表L是否为空

6:顺序表的取值（根据位置iGets the content of the data element at the corresponding position）

7:在顺序表L中查找与指定值e相同的数据元素的位置

8：在顺序表L中插入

9：顺序表中删除

小结：

---

顺序表的类型定义：

typedef struct{
   ElemType data[]; 

 //This way arrays are allocated statically;
 //ElemType数据类型,可直接把ElemType 改为int、float......
也可以定义typedef int ElemType;

   int length;
}SqList;   //顺序表类型

//If the data type is composite,Not just a data type.Defining an abstract data type.
eg：

typedef struct{
float p;
int    e;
}Polynomial;

typedef struct{
Polynomial *elem;
int length;
}SqList;

Dynamic allocation of complementary arrays
typedef struct{
ElemType *data;
int length;
}SqList;
//需要使用<stdlib.h>中的函数malloc与sizeof如下：
SqList L;
L.data = (ElemType *) malloc (sizeof(ElemType) * MaxSize); //Use this to dynamically allocate space.

顺序表的基本操作：
/*补充
//函数结果状态代码
 

#define TRUE   1
#define FALSE  0
#define OK       1
#define ERROR           0
#define INFEASIBLE    -1
#define OVERFLOW     -2
//Status   是函数的类型,其值是函数结果状态代码、
typedef int status;
typedef char ElemType;

1:顺序表L得初始化（参数引用）

Status IniList_Sq(SqList &L){
       L.elem =  new ElemType[MAXSIZE];  //new是C++函数与C的malloc函数作用一样：分配空间.
       if(!L.elem)  exit(OVERFLOW);   //exit为函数,所在头文件为:stdlib.h  功能：关闭所有文件,终止正在执行的进程. exit(x)(x不为0)都表示异常退出.
       L.length = 0;
       return OK;    
}

2:销毁顺序表L

void DestroyList(SqList &L){
if(L.elem) 
delete  L.elem; //释放存储空间
}

3:清空顺序表L

void ClearList(SqList &L){
L.length = 0;    //将线性表的长度置为0;
}

4:求顺序表的长度

int getlength(SqList L){
return (L.length);
}

5:判断顺序表L是否为空

int IsEmpty(SqList L){
if(L.length  == 0) return 1;
else return 0;
}

6:顺序表的取值（根据位置iGets the content of the data element at the corresponding position）

int GetElem(SqList L,int i,ElemType &e){
if(i<1 || i>length)
return ERROR; // 判断i值是否合理,若不合理,返回ERROR
e = L.elem[i-1]; //第i-1的单元存储着第i个数据
return  OK;
}

7:在顺序表L中查找与指定值e相同的数据元素的位置

int LocateElem(SqList L,ELemType e){
for(i = 0; i<L.length; i++)
    if(L.elem[i] == e) return i-1;
else return 0;
}

平均查找长度:ASL = （n+1）/2

8：在顺序表L中插入

status ListInsert_Sq(SqList &L, int i, ElemType e){
if(i<1 || i>L.length+1) return ERROR;        //i不合法
if(L.length == MAXSIZE) return ERROR;  //当前存储空间已满
for(j = L.length-1; j>=i-1; j++)
L.elem[j+1] = L.elem[j];
L.elem[i-1] = e;
L.length++;
return OK;
}

ASL = n/2   时间复杂度O（n）

9：顺序表中删除

status Listdelete_Sq(SqList &L,int i){
if(i<1) || i>L.length) return ERROR;
if(L.length == 0)  return ERROR;
for(j =i; j<=length-1; j++)
L.elem[j-1] = L.elem[j];
L.length--;
return OK;
}  

ASL = ( n-1)/2   时间复杂度O（n）

小结：

顺序表优缺点
优点：
1）存储密度大（结点本身所占存储量/结点结构所占存储量）
2）可以随机存取表中任一元素
缺点：
1）在插入、删除某一元素时,需要移动大量元素
2）浪费存储空间
3）属于静态存储形式,数据元素的个数不能自由扩充