数据结构——顺序表详解

定义顺序表是一种线性表的存储结构，它用一组地址连续的存储单位依次存储线性表中的数据元素。从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表具有动态分配空间、支持随机访问和顺序访问,逻辑顺序与物理顺序一致。每个元素可以都有唯一的位置，可以通过索引直接访问元素。元素可以是任意类型，包括基本数据类型、结构体等。

文章共4,390字 · 阅读需要大约15分钟

一键AI生成摘要，助你高效阅读

问答

清风明月01

2403人浏览 · 2023-10-05 21:58:22

清风明月01 · 2023-10-05 21:58:22 发布

一、顺序表的定义及其特点

定义：顺序表是一种线性表的存储结构，它用一组地址连续的存储单位依次存储线性表中的数据元素。从而使得逻辑上相邻的两个元素在物理位置上也相邻。

特点：

顺序表具有动态分配空间、支持随机访问和顺序访问,逻辑顺序与物理顺序一致。
每个元素可以都有唯一的位置，可以通过索引直接访问元素。
元素可以是任意类型，包括基本数据类型、结构体等。

二、顺序表的运算

顺序表的运算主要包括初始化、插入、删除和查找等操作。其中初始化是指将顺序表中所有元素都赋值为0或者空字符；插入操作需要将新元素插到指定位置，同时更新新顺序表的长度；删除操作需要将元素从顺序表中移除，并更新顺序表长度；查找操作需要在顺序表中查找一个元素，并返回其位置或未找到的表中。

三、顺序表的实现

1、顺序表的创建

顺序表可分为静态和动态顺序表两种。以下所用为静态顺序表需要确定最大长度，易导致空间资源不足或浪费。具体实现如下：

typedef struct     /*定义顺序表的数据结构*/
{
	DataType data[MAXSIZE];	/*存储空间，数组*/
	int length;			/*顺序表的当前长度*/
}SeqList;    /*顺序表的结构体类型*/

2、顺序表初始化

只需要将存储空间的大小设置为初始值0即可。具体实现如下：

/*顺序表初始化*/
int init(SeqList *L)
{
	L->length = 0;    // 初始时，顺序表长度为0
	return 0;
}

3、顺序表的插入

在顺序表插入元素，需要先找到插入的位置，然后将后一个元素依次往后移动一位，最后将新元素放到指定位置。如果插入位置超过了当前长度，则无法执行插入操作。具体实现如下：

/*插入元素*/
int insert(SeqList *L, int i, DataType x)
{
	int j;

	/*判断是否满*/
	if(full(L))
	{                // 如果顺序表已满，则无法插入
		printf("Error[10001],顺序表已满！\n");
		return 10001;
	}
	/*判断位置i合法性*/
	if(i<1 || i>length(L)+1)     // 如果插入位置不合法，则无法插入
	{
		printf("Error[10002],位置i不合法！\n");
		return 10002;
	}

	/*移动元素,向后移动*/
	for(j=L->length;j>=i;j--) // 将插入位置后的元素依次后移一位
	{
		L->data[j] = L->data[j-1];
	}
	L->data[j] = x;     // 在指定位置插入元素
	L->length++; // 顺序表长度加1
	return 0; /*ok!*/
}

4、顺序表的删除

在顺序表中删除一个元素首先要找到删除元素的位置，然后将该位置后面的元素依次向前移动一位，覆盖掉要删除的元素，并更新顺序表的长度。具体实现如下：

/*删除元素*/
int delete(SeqList *L, int i, DataType *x)
{
	int k;
	if(i<1||i>=L->length+1){	//如果删除位置不合法，则无法删除 
		printf("Error[1003],删除位置i不合法\n");
		return 10003; 
	} 
	
	//将删除位置后的元素依次前移一位
	for(k=i-1;k<L->length-1;k++){
		L->data[k]=L->data[k+1];
		 
	} 
	//顺序表长度减一
	L->length--;
	return 0; 
}

5、顺序表的查找

在顺序表中查找一个元素，需要从头开始遍历顺序表，直到找到指定目标或者遍历完整个顺序表。具体实现如下：

// 查找顺序表中是否存在指定元素，如果存在则返回其位置，否则返回-1
int find(SeqList *L, int x) {
    for (int i = 0; i < L->length; i++) {
        if (L->data[i] == x) {    //如果当前遍历到的元素的值等于要查找的值x
            return i;    //返回当前元素下标
        }
    }
    return 0;
}

6、顺序表的输出

顺序表的输出通过一个for循环从头到尾遍历各元素并输出表中各元素的值，其中条件<L.length（顺序表的总长度）。具体实现如下：

void print(SeqList *L)
{
	int i;

	if(L->length==0)
	{
		printf("顺序表为空！");
		return 0;
	}
	printf("顺序表为:");
	for(i=0;i<L->length;i++)
	{
		printf(" %d ", L->data[i]);
	}
	printf("\n");
}

四、完整Demo

main.c（主函数）

#include <stdio.h>
#include "SeqList.h"
#include "welcome.h"
#include<string.h>
int main(int argc, char* argv[])
{
	SeqList L;
	int cmd;
	int i;
	int m,n;

	DataType x;
	
	for(i=0;i<strlen(welcome);i++)
	{
		printf("%c",welcome[i]);
		for(m=0;m<1000;m++)
			for(n=0;n<1000;n++)
			{
				;
			}
	}
	printf("\n\n\n");
	printf("---------------------顺序表演示程序-------------------\n");
	do
	{
		printf("1. 初始化顺序表\n");
		printf("2. 插入元素\n");
		printf("3. 删除元素\n");
		printf("4. 判断顺序表是否为空\n");
		printf("5. 判断顺序表是否满\n");
		printf("6. 输出顺序表\n");
		printf("7. 查找元素\n");
		printf("8. 帮助\n"); 
		printf("0. 退出\n");
		printf("请输入您要进行的操作（1~8,0退出）：");
		scanf("%d", &cmd);
		switch(cmd)
		{
		case 1:
			if(!init(&L))
			{
				printf("顺序表已初始化！\n");
			}
			break;
		case 2:
			printf("请输入插入位置i，插入元素x（i，x）：");
			scanf("%d,%d",&i,&x);
			if(!insert(&L,i,x))
			{
				printf("元素【%d】已插入位置【%d】\n",x, i);
			}
			break;
		case 3:
			printf("请输入删除位置i(i)：");
			scanf("%d",&i);
			if(!delete(&L,i,&x)){ 
				printf("位置【%d】上的元素已经删除\n",i, x);
			}
			break;
		case 4:
			if(empty(&L))
			{
				printf("顺序表为空\n");
			}
			else
			{
				printf("顺序表不为空！\n");
			}
			break;
			 
		case 5:
			if(full(&L))
			{
				printf("顺序表已满！\n");
			}
			else
			{
				printf("顺序表未满！\n");
			}
			break;
		case 6:
			print(&L);
			break;
		case 7:
			printf("请输入你要查找的元素x：");
			scanf("%d",&x);
			find(&L,x,i);
			break;
		case 8:
			printf(" 本程序为顺序表的演示程序，有HQ设计开发，程序实现了对顺序表插入删除查找等功能！\n");
			break;
			
		}
	}while(cmd != 0);

	return 0;
}

SeqList.c(函数实现）

/*
	SeqList.c 顺序表实现
*/
#include "SeqList.h"


/*顺序表初始化*/
int init(SeqList *L)
{
	L->length = 0;
	return 0;
}


/*顺序表的长度*/
int length(SeqList *L)
{
	return L->length;
}

/*顺序表是否满*/
int full(SeqList *L)
{
	return (L->length == MAXSIZE)?1:0;
}

/*是否空*/
int empty(SeqList *L)
{
	return (L->length == 0)?1:0;
}

/*插入元素*/
int insert(SeqList *L, int i, DataType x)
{
	int j;

	/*判断是否满*/
	if(full(L))
	{
		printf("Error[10001],顺序表已满！\n");
		return 10001;
	}
	/*判断位置i合法性*/
	if(i<1 || i>length(L)+1)
	{
		printf("Error[10002],位置i不合法！\n");
		return 10002;
	}

	/*移动元素,向后移动*/
	for(j=L->length;j>=i;j--)
	{
		L->data[j] = L->data[j-1];
	}
	L->data[j] = x;
	L->length++;
	return 0; /*ok!*/
}

/*删除元素*/
int delete(SeqList *L, int i, DataType *x)
{
	int k;
	if(i<1||i>=L->length+1){	//如果删除位置不合法，则无法删除 
		printf("Error[1003],删除位置i不合法\n");
		return 10003; 
	} 
	
	//将删除位置后的元素依次前移一位
	for(k=i-1;k<L->length-1;k++){
		L->data[k]=L->data[k+1];
		 
	} 
	//顺序表长度减一
	L->length--;
	return 0; 
}

/*输出顺序表*/
void print(SeqList *L)
{
	int i;

	if(empty(L))
	{
		printf("顺序表为空！\n");
		return 0 ;
	}
	printf("顺序表为:");
	for(i=0;i<L->length;i++)
	{
		printf(" %d ", L->data[i]);
	}
	printf("\n");
}
/*查找元素*/
int find(SeqList *L,int x)
{
	int i;
	for (i=0;i<L->length;i++){
		if (L->data[i]==x){
			printf("元素【%d】在表中第【%d】个位置\n",x,i+1);
		}
	}
}

SeqList.h(函数声明/顺序表结构体）

/*

	SeqList.h 顺序表定义
*/

#define MAXSIZE 1000

typedef int DataType;

/*顺序表*/
typedef struct
{
	DataType data[MAXSIZE];
	int length;
}SeqList;

/*顺序表初始化*/
int init(SeqList *L);

/*顺序表的长度*/
int length(SeqList *L);

/*顺序表是否满*/
int full(SeqList *L);

/*是否空*/
int empty(SeqList *L);

/*插入元素*/
int insert(SeqList *L, int i, DataType x);

/*删除元素*/
int delete(SeqList *L, int i, DataType x);

/*输出顺序表*/
void print(SeqList *L);
/*查找元素*/
int find(SeqList *L, int i, DataType x);

welcome.h(函数声明）

char welcome[]=(
    "                ********\n"
    "               ************\n"
    "               ####....#.\n"
    "             #..###.....##....\n"
    "             ###.......######              ###            ###\n"
    "                ...........               #...#          #...#\n"
    "               ##*#######                 #.#.#          #.#.#\n"
    "            ####*******######             #.#.#          #.#.#\n"
    "           ...#***.****.*###....          #...#          #...#\n"
    "           ....**********##.....           ###            ###\n"
    "           ....****    *****....\n"
    "             ####        ####\n"
    "           ######        ######\n"
    "##############################################################\n"
    "#...#......#.##...#......#.##...#......#.##------------------#\n"
    "###########################################------------------#\n"
    "#..#....#....##..#....#....##..#....#....#####################\n"
    "##########################################    #----------#\n"
    "#.....#......##.....#......##.....#......#    #----------#\n"
    "##########################################    #----------#\n"
    "#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#\n"
    "##########################################    ############\n"
    );

运行结果：

********
************
####....#.
#..###.....##....
###.......###### ### ###
........... #...# #...#
##*####### #.#.# #.#.#
####*******###### #.#.# #.#.#
...#***.****.*###.... #...# #...#
....**********##..... ### ###
....**** *****....
#### ####
###### ######
##############################################################
#...#......#.##...#......#.##...#......#.##------------------#
###########################################------------------#
#..#....#....##..#....#....##..#....#....#####################
########################################## #----------#
#.....#......##.....#......##.....#......# #----------#
########################################## #----------#
#.#..#....#..##.#..#....#..##.#..#....#..# #----------#
########################################## ############

---------------------顺序表演示程序-------------------
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：1
顺序表已初始化！
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：2
请输入插入位置i，插入元素x（i，x）：1,2
元素【2】已插入位置【1】
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：2
请输入插入位置i，插入元素x（i，x）：2,3
元素【3】已插入位置【2】
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：6
顺序表为: 2 3
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：3
请输入删除位置i(i)：1
位置【1】上的元素已经删除
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：6
顺序表为: 3
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：4
顺序表不为空！
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：5
顺序表未满！
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：6
顺序表为: 3
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：7
请输入你要查找的元素x：3
元素【3】在表中第【1】个位置
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：8
本程序为顺序表的演示程序，有HQ设计开发，程序实现了对顺序表插入删除查找等功能！
1. 初始化顺序表
2. 插入元素
3. 删除元素
4. 判断顺序表是否为空
5. 判断顺序表是否满
6. 输出顺序表
7. 查找元素
8. 帮助
0. 退出
请输入您要进行的操作（1~8,0退出）：0
Press any key to continue