【数据结构——线性表之顺序表】

淡淡的烟草味﹌ 2022-12-10 11:24 222阅读 0赞

# 【数据结构——线性表之顺序表】 #

### 目录： ###

*  【数据结构——线性表之顺序表】
 *   *  一、顺序表的表示
     *   *  1、静态顺序存储结构
         *  2、动态顺序存储结构
     *  二、顺序表基本操作的实现
     *   *  1、初始化
         *  2、查找
         *  3、插入
         *  4、删除
         *  5、顺序表的操作

## 一、顺序表的表示 ##

### 1、静态顺序存储结构 ###

/*线性表静态顺序存储结构*/
    #define MAXSIZE 100 //定义线性表的最大长度
    typedef int ElemType; //定义抽象类型ElemType为int类型
    typedef struct
    {
        
    	ElemType elem[MAXSIZE]; //声明一个ElemType类型的数组elem
    	int length; //顺序表的当前长度
    }SqList; //此结构为SqList类型

### 2、动态顺序存储结构 ###

/*线性表动态顺序存储结构*/
    #define MAXSIZE 100 //定义线性表的最大长度
    typedef int ElemType; //定义抽象类型ElemType为int类型
    typedef struct
    {
        
    	ElemType* elem;//存储空间的基地址
    	int length;//当前长度
    }SqList;

## 二、顺序表基本操作的实现 ##

**补充：操作算法中用到的预定义常量和类型**

//函数结果状态代码
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    //Status是函数返回值类型，其值是函数结果状态代码
    typedef int Status;

**线性表的定义：**

#define MAXSIZE 100 //定义线性表的最大长度
    typedef int ElemType; //定义抽象类型ElemType为int类型
    typedef struct
    {
        
    	ElemType* elem;//存储空间的基地址
    	int length;//当前长度
    }SqList;

### 1、初始化 ###

> 算法思想  
> (1)为顺序表动态分配一个预定义大小的数组空间，使elem指向这段空间的基地址  
> (2)使该顺序表的当前长度为0

/*顺序表的初始化*/
    typedef int Status;
    Status InitList(SqList& L)//修改线性表，按引用传递
    {
        
    	L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间
    	if (!L.elem)  //开辟存储空间失败
    		exit(OVERFLOW); 
    	L.length = 0; //线性表的长度为0
    	return OK;
    }

### 2、查找 ###

> 算法思想：  
> (1)从第一个元素起，依次和e相比较  
> (2)若第i个元素的值等于e,则查找成功，返回该元素的位序 i + 1  
> (3)若查遍整个顺序表都没有找到，则查找失败，返回0

/*顺序表的查找*/
    int LocateElem(SqList L, ElemType e)
    {
        
    	for (i = 0;i < L.length;i++) //i 为下标序号
    		if (L.elem[i] == e)
    			return i + 1; //查找成功，返回i+1
    	return 0; //查找失败，返回0
    }

### 3、插入 ###

> 算法思想：  
> (1)检查插入的位置i是否合法(合法范围 1 <= i <= n + 1), 若不合法返回ERROR  
> (2)检查数组空间是否存满，若存满返回ERROR  
> (3)从第n个元素到第i个元素依次往后移动一位  
> (4)将要插入的元素存到第i个位置  
> (5)表长 + 1  
> (6)插入成功，返回OK

/*顺序表的插入*/
    typedef int ElemType;
    typedef int Status;
    Status ListInsert(SqList& L, int i, ElemType e)
    {
        
    	if (i < 1 || i > L.length + 1) return ERROR;//插入位置不合法
    	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;//新插入的元素e存到i-1
    	++L.length;//表长+1
    	return OK;
    }

### 4、删除 ###

> 算法思想  
> (1)判断删除元素位置是否合法  
> (2)将删除元素存入到e中  
> (3)将第i - 1到第i个元素依次往前移动一位  
> (4)表长 - 1，删除成功返回OK

/*顺序表的删除*/
    typedef int Status;
    typedef int ElemType;
    Status ListDelete(SqList& L, int i, ElemType& e)
    {
        
    	if (i < 1 || i > L.length + 1) return ERROR;//判断位置是否合法
    	e = L.elem[i - 1];//删除元素存入e
    	for (j = i, j <= L.length -1, j++)
    		L.elem[j - 1] = L.length[j];
    	--L.length;
    	return OK;
    }

### 5、顺序表的操作 ###

#include<stdio.h>
    #include<stdlib.h>
    
    #define MAXSIZE 100
    #define OK 1
    #define TRUE 1
    #define FALSE 0
    #define OVERFLOW -2
    #define ERROE 0
    
    typedef int ElemType;
    typedef int Status;
    
    /*定义顺序表*/
    typedef struct
    {
        
    	ElemType* elem;//数组空间基指针
    	int length;
    }SqList;
    
    Status InitList_Sq(SqList& L);/*初始化顺序表*/
    void InputList_Sq(SqList& L);/*顺序表的输入*/
    void Output_Sq(SqList& L);/*顺序表的输出*/
    int LocateElem_Sq(SqList L, ElemType e);/*顺序表的查找*/
    Status InsertList_Sq(SqList& L, int i, ElemType e);/*顺序表的插入*/
    Status DeleteList_Sq(SqList& L, int i, ElemType e);/*顺序表的删除*/
    
    /*main函数*/
    int main(void)
    {
        
    	SqList L;//顺序表L
    	int i, value;
    	InitList_Sq(L);//初始化顺序表
    	InputList_Sq(L);//顺序表的输入
    	Output_Sq(L);//顺序表的输出
    
    	printf("\n请输入要查找的元素：");
    	int e;
    	scanf_s("%d", &e);//输入要查找的元素
    	int locate = LocateElem_Sq(L, e);
    	printf("要查找元素所在的位置为：第 %d 位",locate);
    
    	printf("\n请输入要插入的位置i:");
    	scanf_s("%d", &i);
    	printf("请输入要插入的元素：");
    	scanf_s("%d", &e);
    	value =  InsertList_Sq(L, i, e);//插入元素
    	if (value)
    		Output_Sq(L);//输出
    	else
    		printf("插入失败！");
    
    	printf("\n请输入要删除元素的位置i:");
    	scanf_s("%d", &i);
    	value = DeleteList_Sq(L, i, e);//删除元素
    	if (value)
    		Output_Sq(L);//输出
    	else
    		printf("删除失败！");
    	return 0;
    }
    
    /*初始化顺序表*/
    Status InitList_Sq(SqList& L)
    {
        
    	L.elem = new ElemType[MAXSIZE];//开辟空间
    	if (!L.elem) exit(OVERFLOW);//分配空间失败
    	L.length = 0;//定义表长为0
    	printf("顺序表初始化成功！\n");//初始化提示
    	return OK;
    }
    
    /*顺序表的输入*/
    void InputList_Sq(SqList& L)
    {
        
    	int n;
    	printf("请输入顺序表的长度：");
    	scanf_s("%d", &n);
    	L.length = n;
    	if (n > MAXSIZE)//检查输入的长度是否合法
    		printf("数组长度不合法！");
    	else
    	{
        
    		printf("请输入%d个元素：\n", n);
    		for (int i = 0;i < L.length;i++)
    		{
        
    			printf("第%d个元素为：", i);
    			scanf_s("%d", &L.elem[i]);
    		}
    	}
    }
    
    /*顺序表的输出*/
    void Output_Sq(SqList& L)
    {
        
    	printf("当前顺序表的元素依次是：");
    	for (int i = 0;i < L.length;i++)
    		printf("%d ", L.elem[i]);
    }
    
    /*顺序表的查找*/
    int LocateElem_Sq(SqList L, ElemType e)
    {
        
    	for (int i = 0;i < L.length;i++)
    		if (L.elem[i] == e) return i + 1;//查找成功返回i+1
    	return 0;
    }
    
    /*顺序表的插入*/
    Status InsertList_Sq(SqList& L, int i, ElemType e)
    {
        
    	if (i < 1 || i > L.length + 1) return ERROE;//i值不合法
    	if (L.length == MAXSIZE) return ERROE;//存储空间已满
    	for (int j = L.length - 1;j >= i - 1;j--)
    		L.elem[j + 1] = L.elem[j];//插入位置后面的元素依次往后移动
    	L.elem[i - 1] = e;//新插入的元素存在i - 1 中
    	++L.length;//表长+1
    	return OK;
    }
    
    /*顺序表的删除*/
    Status DeleteList_Sq(SqList& L, int i, ElemType e)
    {
        
    	if (i < 1 || i > L.length) return ERROE;// i值不合法
    	e = L.elem[i - 1];//将删除的元素存入到e中
    	for (int j = i;j <= L.length - 1;j++)
    		L.elem[j - 1] = L.elem[j];//将i位置后面的元素往前移动一位
    	--L.length;//表长-1
    	return OK;
    }

**运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ2NTE4NDYx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/04ae009527fa4dbfa203b7d5b849f5ca.png