devbox
菜鸟追梦旅行
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构——顺序表详解

作者：菜鸟追梦旅行 | 2024-04-17 11:07:43

赞

踩

顺序表

目录

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

二、顺序表的运算

三、顺序表的实现 

1、顺序表的创建

2、顺序表初始化

3、顺序表的插入

4、顺序表的删除

5、顺序表的查找

6、顺序表的输出

四、完整Demo

五、小结

六、参考文献 

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

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

特点：

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

二、顺序表的运算

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

三、顺序表的实现 

1、顺序表的创建

  • 顺序表可分为静态和动态顺序表两种。以下所用为静态顺序表需要确定最大长度，易导致空间资源不足或浪费。具体实现如下：
  1. typedef struct     /*定义顺序表的数据结构*/
  2. {
  3. 	DataType data[MAXSIZE];	/*存储空间，数组*/
  4. 	int length;			/*顺序表的当前长度*/
  5. }SeqList;    /*顺序表的结构体类型*/

2、顺序表初始化

  • 只需要将存储空间的大小设置为初始值0即可。具体实现如下：
  1. /*顺序表初始化*/
  2. int init(SeqList *L)
  3. {
  4. 	L->length = 0;    // 初始时，顺序表长度为0
  5. 	return 0;
  6. }

3、顺序表的插入

  • 在顺序表插入元素，需要先找到插入的位置，然后将后一个元素依次往后移动一位，最后将新元素放到指定位置。如果插入位置超过了当前长度，则无法执行插入操作。具体实现如下：
  1. /*插入元素*/
  2. int insert(SeqList *L, int i, DataType x)
  3. {
  4. 	int j;
  5.  
  6. 	/*判断是否满*/
  7. 	if(full(L))
  8. 	{                // 如果顺序表已满，则无法插入
  9. 		printf("Error[10001],顺序表已满！\n");
  10. 		return 10001;
  11. 	}
  12. 	/*判断位置i合法性*/
  13. 	if(i<1 || i>length(L)+1)     // 如果插入位置不合法，则无法插入
  14. 	{
  15. 		printf("Error[10002],位置i不合法！\n");
  16. 		return 10002;
  17. 	}
  18.  
  19. 	/*移动元素,向后移动*/
  20. 	for(j=L->length;j>=i;j--) // 将插入位置后的元素依次后移一位
  21. 	{
  22. 		L->data[j] = L->data[j-1];
  23. 	}
  24. 	L->data[j] = x;     // 在指定位置插入元素
  25. 	L->length++; // 顺序表长度加1
  26. 	return 0; /*ok!*/
  27. }

4、 顺序表的删除

  • 在顺序表中删除一个元素首先要找到删除元素的位置，然后将该位置后面的元素依次向前移动一位，覆盖掉要删除的元素，并更新顺序表的长度。具体实现如下：
  1. /*删除元素*/
  2. int delete(SeqList *L, int i, DataType *x)
  3. {
  4. 	int k;
  5. 	if(i<1||i>=L->length+1){	//如果删除位置不合法，则无法删除 
  6. 		printf("Error[1003],删除位置i不合法\n");
  7. 		return 10003; 
  8. 	} 
  9. 	
  10. 	//将删除位置后的元素依次前移一位
  11. 	for(k=i-1;k<L->length-1;k++){
  12. 		L->data[k]=L->data[k+1];
  13. 		 
  14. 	} 
  15. 	//顺序表长度减一
  16. 	L->length--;
  17. 	return 0; 
  18. }

5、 顺序表的查找

  • 在顺序表中查找一个元素，需要从头开始遍历顺序表，直到找到指定目标或者遍历完整个顺序表。具体实现如下：
  1. // 查找顺序表中是否存在指定元素，如果存在则返回其位置，否则返回-1
  2. int find(SeqList *L, int x) {
  3.     for (int i = 0; i < L->length; i++) {
  4.         if (L->data[i] == x) {    //如果当前遍历到的元素的值等于要查找的值x
  5.             return i;    //返回当前元素下标
  6.         }
  7.     }
  8.     return 0;
  9. }

 6、顺序表的输出

  • 顺序表的输出通过一个for循环从头到尾遍历各元素并输出表中各元素的值，其中条件<L.length（顺序表的总长度）。具体实现如下：
  1. void print(SeqList *L)
  2. {
  3. 	int i;
  4.  
  5. 	if(L->length==0)
  6. 	{
  7. 		printf("顺序表为空！");
  8. 		return 0;
  9. 	}
  10. 	printf("顺序表为:");
  11. 	for(i=0;i<L->length;i++)
  12. 	{
  13. 		printf(" %d ", L->data[i]);
  14. 	}
  15. 	printf("\n");
  16. }

四、完整Demo

  • main.c（主函数）
  1. #include <stdio.h>
  2. #include "SeqList.h"
  3. #include "welcome.h"
  4. #include<string.h>
  5. int main(int argc, char* argv[])
  6. {
  7. 	SeqList L;
  8. 	int cmd;
  9. 	int i;
  10. 	int m,n;
  11.  
  12. 	DataType x;
  13. 	
  14. 	for(i=0;i<strlen(welcome);i++)
  15. 	{
  16. 		printf("%c",welcome[i]);
  17. 		for(m=0;m<1000;m++)
  18. 			for(n=0;n<1000;n++)
  19. 			{
  20. 				;
  21. 			}
  22. 	}
  23. 	printf("\n\n\n");
  24. 	printf("---------------------顺序表演示程序-------------------\n");
  25. 	do
  26. 	{
  27. 		printf("1. 初始化顺序表\n");
  28. 		printf("2. 插入元素\n");
  29. 		printf("3. 删除元素\n");
  30. 		printf("4. 判断顺序表是否为空\n");
  31. 		printf("5. 判断顺序表是否满\n");
  32. 		printf("6. 输出顺序表\n");
  33. 		printf("7. 查找元素\n");
  34. 		printf("8. 帮助\n"); 
  35. 		printf("0. 退出\n");
  36. 		printf("请输入您要进行的操作（1~8,0退出）：");
  37. 		scanf("%d", &cmd);
  38. 		switch(cmd)
  39. 		{
  40. 		case 1:
  41. 			if(!init(&L))
  42. 			{
  43. 				printf("顺序表已初始化！\n");
  44. 			}
  45. 			break;
  46. 		case 2:
  47. 			printf("请输入插入位置i，插入元素x（i，x）：");
  48. 			scanf("%d,%d",&i,&x);
  49. 			if(!insert(&L,i,x))
  50. 			{
  51. 				printf("元素【%d】已插入位置【%d】\n",x, i);
  52. 			}
  53. 			break;
  54. 		case 3:
  55. 			printf("请输入删除位置i(i)：");
  56. 			scanf("%d",&i);
  57. 			if(!delete(&L,i,&x)){ 
  58. 				printf("位置【%d】上的元素已经删除\n",i, x);
  59. 			}
  60. 			break;
  61. 		case 4:
  62. 			if(empty(&L))
  63. 			{
  64. 				printf("顺序表为空\n");
  65. 			}
  66. 			else
  67. 			{
  68. 				printf("顺序表不为空！\n");
  69. 			}
  70. 			break;
  71. 			 
  72. 		case 5:
  73. 			if(full(&L))
  74. 			{
  75. 				printf("顺序表已满！\n");
  76. 			}
  77. 			else
  78. 			{
  79. 				printf("顺序表未满！\n");
  80. 			}
  81. 			break;
  82. 		case 6:
  83. 			print(&L);
  84. 			break;
  85. 		case 7:
  86. 			printf("请输入你要查找的元素x：");
  87. 			scanf("%d",&x);
  88. 			find(&L,x,i);
  89. 			break;
  90. 		case 8:
  91. 			printf(" 本程序为顺序表的演示程序，有HQ设计开发，程序实现了对顺序表插入删除查找等功能！\n");
  92. 			break;
  93. 			
  94. 		}
  95. 	}while(cmd != 0);
  96.  
  97. 	return 0;
  98. }
  • SeqList.c(函数实现）
  1. /*
  2. 	SeqList.c 顺序表实现
  3. */
  4. #include "SeqList.h"
  5.  
  6.  
  7. /*顺序表初始化*/
  8. int init(SeqList *L)
  9. {
  10. 	L->length = 0;
  11. 	return 0;
  12. }
  13.  
  14.  
  15. /*顺序表的长度*/
  16. int length(SeqList *L)
  17. {
  18. 	return L->length;
  19. }
  20.  
  21. /*顺序表是否满*/
  22. int full(SeqList *L)
  23. {
  24. 	return (L->length == MAXSIZE)?1:0;
  25. }
  26.  
  27. /*是否空*/
  28. int empty(SeqList *L)
  29. {
  30. 	return (L->length == 0)?1:0;
  31. }
  32.  
  33. /*插入元素*/
  34. int insert(SeqList *L, int i, DataType x)
  35. {
  36. 	int j;
  37.  
  38. 	/*判断是否满*/
  39. 	if(full(L))
  40. 	{
  41. 		printf("Error[10001],顺序表已满！\n");
  42. 		return 10001;
  43. 	}
  44. 	/*判断位置i合法性*/
  45. 	if(i<1 || i>length(L)+1)
  46. 	{
  47. 		printf("Error[10002],位置i不合法！\n");
  48. 		return 10002;
  49. 	}
  50.  
  51. 	/*移动元素,向后移动*/
  52. 	for(j=L->length;j>=i;j--)
  53. 	{
  54. 		L->data[j] = L->data[j-1];
  55. 	}
  56. 	L->data[j] = x;
  57. 	L->length++;
  58. 	return 0; /*ok!*/
  59. }
  60.  
  61. /*删除元素*/
  62. int delete(SeqList *L, int i, DataType *x)
  63. {
  64. 	int k;
  65. 	if(i<1||i>=L->length+1){	//如果删除位置不合法，则无法删除 
  66. 		printf("Error[1003],删除位置i不合法\n");
  67. 		return 10003; 
  68. 	} 
  69. 	
  70. 	//将删除位置后的元素依次前移一位
  71. 	for(k=i-1;k<L->length-1;k++){
  72. 		L->data[k]=L->data[k+1];
  73. 		 
  74. 	} 
  75. 	//顺序表长度减一
  76. 	L->length--;
  77. 	return 0; 
  78. }
  79.  
  80. /*输出顺序表*/
  81. void print(SeqList *L)
  82. {
  83. 	int i;
  84.  
  85. 	if(empty(L))
  86. 	{
  87. 		printf("顺序表为空！\n");
  88. 		return 0 ;
  89. 	}
  90. 	printf("顺序表为:");
  91. 	for(i=0;i<L->length;i++)
  92. 	{
  93. 		printf(" %d ", L->data[i]);
  94. 	}
  95. 	printf("\n");
  96. }
  97. /*查找元素*/
  98. int find(SeqList *L,int x)
  99. {
  100. 	int i;
  101. 	for (i=0;i<L->length;i++){
  102. 		if (L->data[i]==x){
  103. 			printf("元素【%d】在表中第【%d】个位置\n",x,i+1);
  104. 		}
  105. 	}
  106. }
  •  SeqList.h(函数声明/顺序表结构体）
  1. /*
  3. 	SeqList.h 顺序表定义
  4. */
  5.  
  6. #define MAXSIZE 1000
  7.  
  8. typedef int DataType;
  9.  
  10. /*顺序表*/
  11. typedef struct
  12. {
  13. 	DataType data[MAXSIZE];
  14. 	int length;
  15. }SeqList;
  16.  
  17. /*顺序表初始化*/
  18. int init(SeqList *L);
  19.  
  20. /*顺序表的长度*/
  21. int length(SeqList *L);
  22.  
  23. /*顺序表是否满*/
  24. int full(SeqList *L);
  25.  
  26. /*是否空*/
  27. int empty(SeqList *L);
  28.  
  29. /*插入元素*/
  30. int insert(SeqList *L, int i, DataType x);
  31.  
  32. /*删除元素*/
  33. int delete(SeqList *L, int i, DataType x);
  34.  
  35. /*输出顺序表*/
  36. void print(SeqList *L);
  37. /*查找元素*/
  38. int find(SeqList *L, int i, DataType x);
  • welcome.h(函数声明）
  1. char welcome[]=(
  2.     "                ********\n"
  3.     "               ************\n"
  4.     "               ####....#.\n"
  5.     "             #..###.....##....\n"
  6.     "             ###.......######              ###            ###\n"
  7.     "                ...........               #...#          #...#\n"
  8.     "               ##*#######                 #.#.#          #.#.#\n"
  9.     "            ####*******######             #.#.#          #.#.#\n"
  10.     "           ...#***.****.*###....          #...#          #...#\n"
  11.     "           ....**********##.....           ###            ###\n"
  12.     "           ....****    *****....\n"
  13.     "             ####        ####\n"
  14.     "           ######        ######\n"
  15.     "##############################################################\n"
  16.     "#...#......#.##...#......#.##...#......#.##------------------#\n"
  17.     "###########################################------------------#\n"
  18.     "#..#....#....##..#....#....##..#....#....#####################\n"
  19.     "##########################################    #----------#\n"
  20.     "#.....#......##.....#......##.....#......#    #----------#\n"
  21.     "##########################################    #----------#\n"
  22.     "#.#..#....#..##.#..#....#..##.#..#....#..#    #----------#\n"
  23.     "##########################################    ############\n"
  24.     );
  • 运行结果：

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

---------------------顺序表演示程序-------------------
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

五、小结

        本文详细介绍了顺序表的定义及其特点，以及初始化、插入、删除和查找等基本运算。通过一个简单的C程序实现，展示了顺序表的操作方法。最后，通过一个完整的Demo，验证了顺序表的正确性和可靠性。

六、参考文献 

《数据结构》(C语言版）李刚，刘万辉.北京：高等教育出版社 ，2017.   

《C语言程序设计》(第四版）谭浩强. 北京：清华大学出版社，2014.

  CSDN 数据结构-----顺序表基本操作

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/439892
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号