【C语言】超详细讲解顺序表的各种操作

简介: 数据结构在内存中的表示通常有两种形式,一种是顺序存储,另一种是链式存储。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素,我们把这种存储形式存储的线性表称为顺序表。

1.顺序表的定义


数据结构在内存中的表示通常有两种形式,一种是顺序存储,另一种是链式存储。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素,我们把这种存储形式存储的线性表称为顺序表。


2.顺序表的特点


1.顺序表的逻辑结构和物理结构是一致的。

2.顺序表中任意一个数据元素都可以随机存取,所以顺序表是一种随机存取的存储结构。


3.顺序表的定义


#define MAXLEN 100 //定义MAXLEN

typedef int DataType;

typedef struct

{

DataType data[MAXLEN];

int Length;

}SeqList;

定义MAXLEN为100,表示顺序表最大的存储空间   利用宏方便对顺序表的大小进行修改

利用typedef将DataType定义成int类型的数据,如果顺序表存放的数据要修改成其他类型的,可以直接 利用typedef将DataType修改成我们想要的数据类型就可以了,这也方便对顺序表进行修改

顺序表SeqList是一个结构体类型,它有两个成员组成,data表示存储顺序表的数组,其长度MAXLEN表示顺序表中元素数目的最大值,Length表示顺序表的实际长度

注意:C语言的数组下标从0开始


4.顺序表的常用操作的实现


4.1 顺序表的初始化

顺序表的初始化就是要建立一个空表L,将L作为指针参数,将表L的实际长度设置为0  代码如下:

void InitList(SeqList* L)

{

L->Length = 0;

}

4.2 顺序表的建立

对于初始化好的顺序表,我们要从键盘输入n个数,将这些数存在顺序表中,修改表场后建立顺序表L,代码如下:

void CreateList(SeqList* L,int n)

{

int i = 0;

for (i = 0; i < n; i++)

{

 scanf("%d", &L->data[i]);

}

L->Length = i;

}

4.3 查找操作

顺序表的查找分为按值和按序号查找,下面开始介绍这两种方法的实现,大家可以根据需求进行使用。

1. 按位置查找

按位置查找就是查找第i个位置的元素的值,在i无效时返回出错,有效时返回成功,并用指针x所指的变量传回第i个元素的值 代码如下:

int GetElem(SeqList* L, int i, DataType* x)

{

if (i<1 || i>L->Length)

{

 return 0;

}

else

{

 *x = L->data[i - 1];

 return 1;

}

}

注意:在查找的时候要先判断i是不是合法的(是否为负数是否超过数组的最大下标值等),以及要考虑到i不是合法的数据时,要怎么处理。


2.按值查找操作

按值查找是指在顺序表中,查找与给指定值x相等的数据元素所在位置的下标。

算法的设计思想:首先令i等于0,然后从表的第一个位置开始逐个与给定值x进行判断,当i小于表长且与该位置的元素值与x的值不相等时i自加,直到循环结束为止。若i的值大于表长就是查找失败,就返回0;若查找成功就返回其位置,就是i+1(数组下标从0开始所以要加1)

代码如下:

int Locate(SeqList* L, DataType x)

{

int i = 0;

while (i < L->Length && L->data[i] != x)

{

 i++;

}

if (i > L->Length)

{

 return 0;

}

else

{

 return i + 1;

}

}

4.4 插入操作


线性表的插入是指在表的第i个位置上(因为C语言的下标是从0开始的,所以插入位置下标为i-1)插入一个值为x的元素,插入后使原表长增加1,称为表长度为n+1的表。

顺序表的插入节点的步骤如下:

1.将数组下标从第i个位置一直到最后一个位置的结点全部往后移,让出第i个位置

2.将新节点x插入第i个位置

3.修改表长

顺序表插入元素的过程如图所示:

7.png

要注意一下几点问题:

1.首先要检查顺序表是否已满,在表满的情况下不能插入,否则会产生溢出错误

2.检查插入位置的有效性,插入的有效范围是1<=i<=n+1(n是原来的表长)

3.注意数据移动的方向,必须从原线性表的最后一个结点开始往后移动

代码如下:

int InsElem(SeqList* L, int i, DataType x)

{

int j = 0;

if (L->Length >= MAXLEN)

{

 printf("顺序表已满!");

 return -1;

}

if (i<1 || i>L->Length+1)

{

 printf("插入位置出错");

 return 0;

}

if (i == L->Length + 1) //插入位置为表尾时

{

 L->data[i - 1] = x;

 L->Length++;

 return 1;

}

for (j = L->Length - 1; j >= i - 1; j--)//插入位置为表中时

{

 L->data[j + 1] = L->data[j];

}

L->data[i = 1] = x;

L->Length++;

return 1;

}

顺序表的插入操作大约需要移动一半的数据元素,时间复杂度为O(n).


4.5 删除操作


线性表的删除操作是指将第i个元素(C语言数组下标从0开始,删除位置下标为i-1)从顺序表中去掉,删除后顺序表长度-1

顺序表删除结点的步骤如下:

1.将要删除的元素赋值给指针x所指的变量

2.将第i+1到最后一个结点依次顺序向前移动

3.顺序表长度-1,删除成功,并返回

删除操作过程图如下:

8.png

代码如下:

int DelElem(SeqList* L, int i, DataType* x)

{

int j = 0;

if (L->Length == 0)

{

 printf("顺序表为空");

 return 0;

}

if (i<1 || i>L->Length)

{

 printf("不存在第i个元素");

 return 0;

}

*x = L->data[i - 1];

for (j = 1; j < L->Length; j++)

{

 L->data[j - 1] = L->data[j];

}

L->Length--;

return 1;

}

删除操作的平均每次大概需要移动一半的元素,时间复杂度为O(n).


4.6 输出表中的元素

输出顺序表的元素,就是遍历一次一维数组,然后把它打印出来  代码如下:

void DispList(SeqList* L)

{

int i = 0;

for (i = 0; i < L->Length; i++)

{

 printf("%d ", L->data[i]);

}

}


5.顺序表的操作的完整程序代码


上面是顺序表的基本操作函数,为了运行相关代码,还要设计好主函数,运用之前学过的循环和开关语句,实现反复实行各种操作的功能。为了方便可以写一个菜单显示各项功能选项。

#define _CRT_SECURE_NO_WARNINGS 1

#include<stdio.h>

#define MAXLEN 100 //定义MAXLEN

typedef int DataType;

typedef struct

{

DataType data[MAXLEN];

int Length;

}SeqList;

void InitList(SeqList* L)

{

L->Length = 0;

}

void CreateList(SeqList* L,int n)

{

int i = 0;

for (i = 0; i < n; i++)

{

 scanf("%d", &L->data[i]);

}

L->Length = i;

}

int GetElem(SeqList* L, int i, DataType* x)

{

if (i<1 || i>L->Length)

{

 return 0;

}

else

{

 *x = L->data[i - 1];

 return 1;

}

}

int Locate(SeqList* L, DataType x)

{

int i = 0;

while (i < L->Length && L->data[i] != x)

{

 i++;

}

if (i > L->Length)

{

 return 0;

}

else

{

 return i + 1;

}

}

int InsElem(SeqList* L, int i, DataType x)

{

int j = 0;

if (L->Length >= MAXLEN)

{

 printf("顺序表已满!");

 return -1;

}

if (i<1 || i>L->Length+1)

{

 printf("插入位置出错");

 return 0;

}

if (i == L->Length + 1) //插入位置为表尾时

{

 L->data[i - 1] = x;

 L->Length++;

 return 1;

}

for (j = L->Length - 1; j >= i - 1; j--)//插入位置为表中时

{

 L->data[j + 1] = L->data[j];

}

L->data[i = 1] = x;

L->Length++;

return 1;

}

int DelElem(SeqList* L, int i, DataType* x)

{

int j = 0;

if (L->Length == 0)

{

 printf("顺序表为空");

 return 0;

}

if (i<1 || i>L->Length)

{

 printf("不存在第i个元素");

 return 0;

}

*x = L->data[i - 1];

for (j = 1; j < L->Length; j++)

{

 L->data[j - 1] = L->data[j];

}

L->Length--;

return 1;

}

void DispList(SeqList* L)

{

int i = 0;

for (i = 0; i < L->Length; i++)

{

 printf("%d ", L->data[i]);

}

}

void  Menu()

{

printf("                  顺序表的各种操作\n");

printf("==================================================\n");

printf("|              1——建立顺序表                   |\n");

printf("|              2——插入元素                     |\n");

printf("|              3——删除元素                     |\n");

printf("|              4——按位置查找元素               |\n");

printf("|              5——按元素值查找其在表中位置     |\n");

printf("|              6——求顺序表的长度               |\n");

printf("|              0——返回                         |\n");

printf("==================================================\n");

printf("请输入菜单号(0-6):");

}

int main()

{

SeqList L;

DataType x;

int n, i, loc;

char  ch1, ch2, a;

ch1 = 'y';

while (ch1 == 'y' || ch1 == 'Y')

{

 Menu();

 scanf("%c", &ch2);

 getchar();

 switch (ch2)

 {

 case  '1':

  InitList(&L);

  printf("请输入建立线性表的个数:");

  scanf("%d", &n);

  CreateList(&L, n);

  printf("建立的线性表为:");

  DispList(&L);

  break;

 case  '2':

  printf("请输入要插入的位置:");

  scanf("%d", &i);

  printf("请输入要插入的元素值:");

  scanf("%d", &x);

  if (InsElem(&L, i, x))

  {

   printf("已成功在第%d的位置上插入%d,插入后的线性表为:\n", i, x);

   DispList(&L);

  }

  else

   printf("输入插入的参数错误!");

  break;

 case  '3':

  printf("请输入要删除元素的位置:");

  scanf("%d", &i);

  if (DelElem(&L, i, &x))

  {

   printf("已成功在第%d的位置上删除%d,删除后的线性表为:\n", i, x);

   DispList(&L);

  }

  else

   printf("\n输入删除的参数错误!");

  break;

 case  '4':

  printf("请输入要查看表中元素位置(从1开始):");

  scanf("%d", &i);

  if (GetElem(&L, i, &x))

   printf("当前线性表第%d个元素的值为:%d", i, x);

  else

   printf("输入的位置错误!");

  break;

 case  '5':

  printf("请输入要查找的元素值为:");

  scanf("%d", &x);

  loc = Locate(&L, x);

  if (loc)

   printf("查找元素值为%d的位置为:%d", x, loc);

  else

   printf("该表中无此元素!");

  break;

 case  '6':

  printf("当前线性表的长度为:%d", L.Length);

  break;

 case  '0':

  ch1 = 'n';

  break;

 default:

  printf("输入有误,请输入0-4进行选择!");

 }

 if (ch2 != '0')

 {

  printf("\n按回车键继续,按任意键返回主菜单!\n");

  a = getchar();

  if (a != '\xA')

  {

   getchar(); ch1 = 'n';

  }

 }

}

}

代码执行效果如图所示:

9.png

图片大小有限就不功能就不一一列举出来了。感兴趣的可以自己去试着写一下


总结:


顺序存储结构的优点是节省存储空间,顺序表结构简单便于随机访问表中任意的数据元素;缺点是插入和删除操作需要移动大量的数据元素,特别是当顺序表的而数据元素含有复杂信息是,移动工作量大、程序执行效率低。另外,顺序表的存储空间是连续且预先分配,若顺序表的长度变化较大时,难以预估顺序表的长度,可能会造成空间的浪费,也可能会导致数据溢出。(水平有限,若有错误,还请指正,谢谢!!)

相关文章
|
6月前
|
存储 算法 程序员
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
【数据结构】C语言实现顺序表万字详解(附完整运行代码)
161 0
|
6月前
|
C语言
C语言顺序表
C语言顺序表
55 0
|
19天前
|
存储 C语言
【数据结构】顺序表(c语言实现)(附源码)
本文介绍了线性表和顺序表的基本概念及其实现。线性表是一种有限序列,常见的线性表有顺序表、链表、栈、队列等。顺序表是一种基于连续内存地址存储数据的数据结构,其底层逻辑是数组。文章详细讲解了静态顺序表和动态顺序表的区别,并重点介绍了动态顺序表的实现,包括初始化、销毁、打印、增删查改等操作。最后,文章总结了顺序表的时间复杂度和局限性,并预告了后续关于链表的内容。
50 3
|
1月前
|
存储 C语言
探索C语言数据结构:利用顺序表完成通讯录的实现
本文介绍了如何使用C语言中的顺序表数据结构实现一个简单的通讯录,包括初始化、添加、删除、查找和保存联系人信息的操作,以及自定义结构体用于存储联系人详细信息。
19 2
|
1月前
|
C语言
链式顺序表实现(C语言描述)
本文介绍了如何在C语言中实现链式顺序表,包括数据结构的定义、节点的创建、数据的插入和删除以及链表的打印和销毁。
38 2
|
1月前
|
C语言
顺序表数组法构建(C语言描述)
如何使用C语言通过数组方法构建有序顺序表,包括顺序表的创建、插入、删除和打印等。
18 2
|
2月前
|
存储 C语言 C++
数据结构基础详解(C语言) 顺序表:顺序表静态分配和动态分配增删改查基本操作的基本介绍及c语言代码实现
本文介绍了顺序表的定义及其在C/C++中的实现方法。顺序表通过连续存储空间实现线性表,使逻辑上相邻的元素在物理位置上也相邻。文章详细描述了静态分配与动态分配两种方式下的顺序表定义、初始化、插入、删除、查找等基本操作,并提供了具体代码示例。静态分配方式下顺序表的长度固定,而动态分配则可根据需求调整大小。此外,还总结了顺序表的优点,如随机访问效率高、存储密度大,以及缺点,如扩展不便和插入删除操作成本高等特点。
196 5
|
2月前
|
存储 算法 C语言
C语言手撕数据结构代码_顺序表_静态存储_动态存储
本文介绍了基于静态和动态存储的顺序表操作实现,涵盖创建、删除、插入、合并、求交集与差集、逆置及循环移动等常见操作。通过详细的C语言代码示例,展示了如何高效地处理顺序表数据结构的各种问题。
|
5月前
|
存储 C语言
数据结构——顺序表(C语言版)
数据结构——顺序表(C语言版)
64 5
|
6月前
|
存储 C语言
C语言实验-动态顺序表实现简易通讯录(二)
在这个C语言实验中,你将实现一个简单的通讯录,它使用动态顺序表来存储联系人信息。
51 2