数据结构(C语言) —— 线性表(顺序表)

发表于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

线性表

线性表是一种最简单的数据结构，其主要操作特点是可以在任意位置插入和删除一个数据元素。线性表有两种存储结构分别是顺序存储结构和链式存储结构，前者称为顺序表，后者称为链表，链表主要还分为单链表，循环单链表，双向循环链表三种。本篇我们先讲讲顺序表的实现。

线性表的抽象数据类型

这里涉及到了抽象数据类型的定义（什么是抽象数据类型），简单介绍一下：抽象数据类型是指一个逻辑概念上的类型和这个类型上的操作集合，而类型是一组值的集合。因此线性表的抽象数据类型主要包括两个方面：数据集合和在该数据集合上的操作集合。

1.数据集合

线性表的数据集合可以表示为a0, a1, a2,…,an-1,每个数据元素的数据类型都是抽象数据元素的数据类型DataType。

typedef int DataType;

2.操作集合

(1) 初始化ListInitiate(L): 初始化线性表L。
(2) 求当前数据元素个数ListLength(L): 函数返回线性表L的当前数据元素个数。
(3) 插入数据元素ListInsert(L, i, x): 在线性表L的第i个数据元素前插入数据元素x。
(4) 删除数据元素ListDelete(L, i, x): 删除线性表L的第i个数据元素。
(5) 取数据元素ListGet(L, i, x): 取线性表L的第i个数据元素，由输出参数x带回。

线性表的顺序表示和实现

接下来我们讲解线性表的第一种存储结构—>顺序存储结构（顺序表）

顺序表的存储结构

我们用结构体表示顺序表的结构，定义结构体SeqList如下：

typedef struct
{
    DataType list[MaxSize];
    int size;
} SeqList;
DataType为数组元素（数据元素）的数据类型，MaxSize表示数组的最大元素个数，size表示当前存储元素个数，且有size<=MaxSize,SeqList为结构体名。

顺序表操作的实现

(1) 初始化ListInitiate(L)

1
2
3
4
5
void ListInitiate(SeqList *L)		//初始化顺序表L
{
	L->size = 0;		//定义初始数据元素个数
}
【说明】由于函数中要改变参数L的size域的值，所以参数L要设计为输出型参数，即设计为SeqList的指针类型。否则，size域的修改值将不会带回。

(2) 求当前数据元素个数ListLength(L)

1
2
3
4
int ListLength(SeqList L)
{
	return L.size;		返回顺序表L的当前数据元素个数
}

(3) 插入数据元素ListInsert(L, i, x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int ListInsert(SeqList *L, int i, DataType x)
//在顺序表L的第i（0<=i<=size）个位置前插入数据元素值x
//插入成功返回1，失败返回0
{
	int j;
	if(L->size >= MaxSize)
	{
		printf("顺序表已满无法插入！\n");
		return 0;
	}
	else if(i<0 || i>L->size)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	else
	{
		//从后向前依次后移数据，为插入做准备
		for(j=L->size; j>i; j--) L->size[j] = L->size[j-1];

		L->list[i] = x;		//插入x
		L->size ++;		    //元素个数加1
		return 1;
	}
}

(4) 删除数据元素ListDelete(L, i, x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int ListDelete(SeqList *L, int i, DataType *x)
//删除顺序表L中位置i（0<=i<=size-1）上的数据元素并保存到x中
//删除成功返回1，失败返回0
{
	int j;
	if(L->size <=0)
	{
		printf("顺序表已空，无数据可删！\n");
		return 0;
	}
	else if(i<0 ||i>L->size-1)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	else
	{
		*x = L->list[i];		//保存删除的元素到x
		
		//从后向前依次前移
		for(j=i+1; j<=L->size; j++) L->size[j-1] = L->size[j];

		L->size--;		//数据元素个数减1
		return 1;
	}
}

(5) 取数据元素ListGet(L, i, x)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ListGet(SeqList L, int i, DataType *x)
//取顺序表L中第i个数据元素存于x中，成功返回1，失败返回0
{
	if(i<0 ||i>L.size-1)
	{
		printf("参数i不合法！\n");
		return 0;
	}
	else
	{
		*x = L.list[i];
		return 1;
	}
}

顺序表应用举例

编程实现如下任务：

建立一个线性表，首先依次输入数据元素1，2，3，...，10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。
假设该线性表的数据元素个数在最坏情况下不会超过100个。要求使用顺序表。

程序设计如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#define MaxSize 100
typedef int DataType;
#include "SeqList.h"

void main(void)
{
	SeqList mylist;
	int i, x;
	
	ListInitiate(&mylist);
	for(i=0; i<10; i++)
		ListInsert(&mylist, i, i+1);	
	ListDelete(&mylist, 4, &x);
	//显示顺序表当前数据元素
	for(i=0; i<ListLength(mylist); i++)
	{
		ListGet(mylist, i, &x);
		printf("%d ", x);
	}
}

程序运行结果：

1 2 3 4 6 7 8 9 10