线性表的顺序存储结构(数组插入，删除)——c语言描述

1. 线性表的顺序存储结构

1.2 线性表的存储结构的表示**

​ 顺序存储结构类似数组存储结构。

代码：

**分析：**Len表示线性表的长度

#define SUCCESS            1
#define ERROR          0
#define MAXSIZE            10

typedef int ElemType;
typedef int LIST_STATUS;

typedef struct SQ_LIST_ {
​     ElemType Data[MAXSIZE];
​     int Len;
}SQ_LIST;

SQ_LIST L;

1.2 线性表的操作****OperatorList()**

​ 对应线性表的抽象数据类型，有以下的操作：创建线性表并赋值，打印线性表的内容，清空线性表，返回线性表对应序号的值，在线性表查相应的值，增加线性表的元素，删除线性表的元素。

LIST_STATUS OperatorList() {
	LIST_STATUS Status;
	int GetIndex = 2;
	int GetE;
	int LoElm = 3;
	int InsertIndex = 2;
	int InsertElm = 15;
	int DeleteIndex = 2;	

	CreatList(&L);
	PrintList(L);
	
	/*
	ClearList(&L);
	PrintList(L);
	*/

	/*
	GetElem(&L, GetIndex, &GetE);
	printf("The GetIndex = %d, GetE = %d\n", GetIndex, GetE);
	*/

	/*
	Status = LocateElem(L, LoElm);
	printf("Status = %d\n", Status);
	*/

	/*
	Status = InsertElem03(&L, InsertIndex, InsertElm);
	if (ERROR == Status) {
		printf("InsertElem faild!\n");		
	}
	*/

	Status = DeleteElem01(&L, DeleteIndex);
	if (ERROR == Status) {
		printf("DeleteElem01 faild!\n");
	}
	PrintList(L);
	return Status;
}

1.3 打印线性表****PrintList**

​ 打印线性表的各个元素和长度。

代码：

LIST_STATUS PrintList(const SQ_LIST L) {
​     int i = 0;

​     printf("Print List:\n");

​     for (i = 0; i < L.Len; ++i) {
​          printf("L.Data[%d] = %d\n", i, L.Data[i]);
​     }

​     printf("L.Len= %d\n", i, L.Len);
​     return SUCCESS;
}

1.4 创建线性表**

​ 创建一个线性表，里面存储三个值。

代码：

LIST_STATUS CreatList(SQ_LIST *const L) {
​     L->Data[0] = 1;
​     L->Data[1] = 2;
​     L->Data[2] = 3;
​     L->Len = 3;             
​     return SUCCESS;
}

结果：

Creat list:

Print List:

L.Data[0] = 1

L.Data[1] = 2

L.Data[2] = 3

L.Len= 3

1.5 清零线性表****ClearList**

​ 将线性表里面的成员清零。

代码：

LIST_STATUS ClearList(SQ_LIST * const L) {
​     printf("Clear list:\n");
​     memset(L, 0, sizeof(SQ_LIST));

​     return SUCCESS;
}

结果：

Creat list:

Print List:

L.Data[0] = 1

L.Data[1] = 2

L.Data[2] = 3

L.Len= 3

Clear list:

Print List:

L->Len= 0

1.6 获取线性表指定位置的值****GetElem**

​ 返回第二个元素的值。

**分析：**先判断线性表的长度是否为0和输入的位置是否合法，再将位置对应的值返回。

代码：

LIST_STATUS GetElem(const SQ_LIST *const L, const int GetIndex, int * const GetE) {
​     if ( 0==L->Len || GetIndex<1 || GetIndex>L->Len ) {
​          return ERROR; 
​     }

​     *GetE = L->Data[GetIndex -1];
​     return SUCCESS;
}

结果：

Creat list:

Print List:

L.Data[0] = 1

L.Data[1] = 2

L.Data[2] = 3

L.Len= 3

The GetIndex = 2, GetE = 2

1.7 查找元素****LocateElem**

**问题：**查找给定元素，查找到返回成功，否则失败

代码：

LIST_STATUS LocateElem(const SQ_LIST L, const int LoElm) {
​     int Index = 0;
​     printf("\nLocateElem:\n");
    
​     if (0 == L.Len) {
​          return ERROR; 
​     }
    
​     for (Index = 0; Index < L.Len; ++Index) {
​          if (LoElm == L.Data[Index]) {
​              return SUCCESS;
​          }    
​     }

​     if (Index == L.Len) {
​          return SUCCESS;
​     }
}

结果：

Creat list:

Print List:

L.Data[0] = 1

L.Data[1] = 2

L.Data[2] = 3

L.Len= 3

LocateElem:

Status = 1

1.8 插入元素**

**问题：**在线性表的第InsetIndex个位置中插入一个元素Ele。如a[0], a[1], a[2], a[3], 要在a[0]后面插入一个元素Elm。比如a[0], a[1], a[2], a[3], 要在a[0]后面插入一个元素Elm。

分析：

①判断是否长度和输入的参数是否合法：首先线性表是否已满（长度的是否为最大值）；判断插入的位置是否合法（不能比1小，不能比线性表长度+1的位置还大）；

② 先后移数组元素：当插入表头位置或者表中间位置时，先将线性表的元素后移一位，再将元素插入指定位置，增加线性表的长度；当插入线尾时，不用移动线性表，直接往后面添加，并增加线性表的长度。用循环方法，把

即：a[2] = a[1], a[3] =a[2], a[4] = a[3]。

③插入元素并增加线性表的长度。即a[1] = Elm, Len++

线性表元素往后移动的两种算法：

从前往后遍历 ——从下标1遍历到下标3

**双指针方法。a[0], a[1], a[2], a[3]。**一个指针pre向前一个的元素，一个指针cur指向目前的元素。实现循环体的时候，需要引入中间变量Temp将后一个元素先存起来。

分析：

① 初始化： Pre = a[1], Cur = a[2]

② 循环体：Temp = a[2]，Cur = Pre

③ 移动指针：Pre = Temp，Cur = a[3]

使用循环：for(i = 0; i < n; ++i), Cur可以用a[i]代替，初始化中Cur可以与循环合在一起，Pre可以用a[i-1].

修改后的版本：

//初始化
Pre = a[InsetIndex - 1];
for (i = InsetIndex; i < Len; ++i) {
​     //循环体
​     Temp = a[i];
​     a[i] = Pre;
    
​     //移动指针
​     Pre = Temp;
}

代码：

LIST_STATUS InsertElem02(SQ_LIST * const L, const int InsertIndex, const int InsertElm) {   
​     int Pre;
​     int Temp;
​     int i;

​     printf("\nInsertElem start:\n");

​     if (MAXSIZE == L->Len || InsertIndex < 1 || InsertIndex > L->Len + 1) {
​          printf("Invaild Len or InserInsex!\n");
​          return ERROR;
​     }
    
​     //Initialize
​     Pre = L->Data[InsertIndex - 1];
​     for (i = InsertIndex; i <= L->Len; ++i) {        
​          //Loop
​          Temp = L->Data[i];      
​          L->Data[i] = Pre;
    
​          //Move Pre
​          Pre = Temp;        
​     }
 
​     L->Data[InsertIndex - 1] = InsertElm;
​     L->Len++;     
​     printf("InsertElem end:\n");

​     return SUCCESS;
}

结果：

Creat list:

Print List:

L.Data[0] = 1

L.Data[1] = 2

L.Data[2] = 3

L.Len= 3

InsertElem start:

InsertElem end:

Print List:

L.Data[0] = 1

L.Data[1] = 15

L.Data[2] = 2

L.Data[3] = 3

L.Len= 4

从后往前遍历 ——从下标4遍历到下标1

**分析：**a[0], a[1], a[2], a[3]。不用使用中间变量存储中间的值，a[4] = a[3], a[3] = a[2], a2[2] = a[1].

代码：

LIST_STATUS InsertElem03(SQ_LIST * const L, const int InsertIndex, const int InsertElm) {
​     int i = 0;

​     printf("\nInsertElem start:\n");
​     if (MAXSIZE == L->Len || InsertIndex < 1 || InsertIndex > L->Len + 1) {
​          printf("\nInvaild Len or InserInsex!\n");
​          return ERROR;
​     }

​     for (i = L->Len; i >= InsertIndex - 1; --i) {
​          L->Data[i] = L->Data[i-1];
​     }

​     L->Data[InsertIndex - 1] = InsertElm;
​     L->Len++;
    
​     printf("InsertElem end:\n");
​     return SUCCESS;
}

结果：

Creat list:

Print List:

L.Data[0] = 1

L.Data[1] = 2

L.Data[2] = 3

L.Len= 3

InsertElem start:

InsertElem end:

Print List:

L.Data[0] = 1

L.Data[1] = 15

L.Data[2] = 2

L.Data[3] = 3

L.Len= 4

1.9 删除元素**

**问题：**在线性表的第InsetIndex个位置中删除一个元素a[InsetIndex]。如a[0], a[1], a[2], a[3], 要删除a[1]，比如a[0], a[1], a[2], a[3]。要删除是头或者中间的时候，移动数组。要删除是表尾时，不用移动数组。

**分析：**a[2], a[3]往前移动。长度减一

两种算法：

算法1：从前往后遍历

代码：

LIST_STATUS DeleteElem01(SQ_LIST * const L, const int DeleteIndex) {
​     int i = 0;

​     if (0 == L->Len || DeleteIndex < 1 || DeleteIndex > L->Len) {
​          printf("\nInvaild Len or DeleteIndex!\n");
​          return ERROR;
​     }

​     for (i = DeleteIndex - 1; i < L->Len - 1; ++i) {
​          L->Data[i] = L->Data[i + 1];    
​     }
    
​     L->Len--;
}

结果：

Creat list:

Print List:

L.Data[0] = 1

L.Data[1] = 2

L.Data[2] = 3

L.Len= 3

Invaild Len or DeleteIndex!

DeleteElem01 faild!

Print List:

L.Data[0] = 1

L.Data[1] = 2

L.Data[2] = 3

L.Len= 3

算法2：从后往前遍历

**分析：**双指针法，Cur指向当前的元素，Pre指向之前的元素，Temp将中间变量保存起来

代码：

LIST_STATUS DeleteElem02(SQ_LIST * const L, const int DeleteIndex) {

​     int i = 0;

​     int Pre;

​     int Temp;

 

​     printf("\nDeleteElem start:\n");

 

​     if (0 == L->Len || DeleteIndex < 1 || DeleteIndex > L->Len) {

​          printf("\nInvaild Len or DeleteIndex!\n");
​          return ERROR;
​     }

​     Pre = L->Data[L->Len - 1];
​     for (i = L->Len - 2; i >= DeleteIndex - 1; --i) {
​          Temp = L->Data[i];
​          L->Data[i] = Pre;
​          Pre = Temp;
​     }

​     L->Len--;
​     printf("\nDeleteElem end\n");
​     return SUCCESS;
}

结果：

Creat list:

Print List:

L.Data[0] = 1

L.Data[1] = 2

L.Data[2] = 3

L.Len= 3

DeleteElem start:

DeleteElem end

Print List:

L.Data[0] = 1

L.Data[1] = 3

L.Len= 2