线性表·顺序表

  大家好，我是Koko~ 

  数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。 数据结构往往同高效的检索算法和索引技术有关。

   本专栏将针对数据结构相关知识进行梳理及总结。建议搭配C语言版（严蔚敏版）数据结构教材使用更佳。

   线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。在稍复杂的线性表中，一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录，含有大量记录的线性表又称文件。

   同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在着序偶关系。

---

1、线性结构的基本特征：

   线性逻辑结构的非形式化描述          一个数据元素的有序（次序）集

（1）集合中必存在唯一的一个“第一元素”

（2）集合中必存在唯一的一个 “最后元素”

（3）除最后元素在外，均有 唯一的后继

（4）除第一元素之外，均有 唯一的前驱

2、线性表类型的存储结构----顺序映射

   线性表具有两种结构——顺序结构和链式结构。本节主要讲解顺序结构所对应的顺序表。

顺序映象

           以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系<x,y>

通常情况顺序映象方法是

           令y的存储位置和x的存储位置相邻。

一、顺序表的定义

    顺序表，用一组地址连续的存储单元依次存储线性表的数据元素，它的逻辑地址相邻，物理地址也相邻（参照一维数组）。

  顺序表的优点：简单、支持随机访问、查找方便、尾插和尾删效率高。

  顺序表的缺点：数据的插入和删除慢（需要挪动后面的数据）。

  顺序表的结构如下图所示，它有两个区域，一个是数据区域类似于数组，存放用户存储的数据，另一个是一个整形变量区，存放已经使用了的区域个数。

定义顺序表类型

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20

//数据元素的类型
typedef int ElemType;   

//定义顺序表类型
typedef struct
{
	ElemType a[MAXSIZE];
	int length;    //顺序表的实际长度
}SqList, *SqList;                 

二、顺序表的基本操作函数

  对顺序表，有初始化、打印、插入、删除、查找的基本操作。

1、初始化顺序表函数

Status Init_List(SqList &L)
{
	memset(L.data, 0, sizeof(L));//初始化数据为0
	L.length = 0;                //初始化长度为0
	return 0;
}

2、创建顺序表函数

//建立线性表
void Creat_List(SqList *L)
{
	int i;
	printf("请输入线性表的长度: ");
	scanf("%d",&L->length);
	for(i=0;i<L->length;i++)
	{
		printf("数据 %d =",i);
	        scanf("%d",&(L->a[i]));
        }
}

3、输出函数

//输出线性表
void Out_List(SqList L)
{
	int i;
	for(i=0;i<=L.length-1;i++)
		printf("%10d",L.a[i]);
}

4、插入函数（插入一个元素）

//在线性表的第i个位置插入元素e
void Insert_Sq(SqList *L,int i,ElemType e)
{
	int j;
	if(L->length==MAXSIZE)
		printf("线性表已满!\n");
	else 
        {
		if(i<1||i>L->length+1)
	            printf("输入位置错!\n");
		else 
        {
		for(j=L->length-1;j>=i-1;j--)
	            L->a[j+1]=L->a[j];
                L->a[i-1]=e;   
		L->length++;
		}
	}
}

5、删除函数（删除一个元素）

//删除第i个元素，返回其值
ElemType Delete_Sq(SqList *L,int i)
{
	ElemType x;
	int j;
	if(L->length==0)
		printf("空表!\n");
	else if(i<1||i>L->length)
	{
		printf("输入位置错！\n");
		x=-1;
	}
	else
	{
		x=L->a[i-1];
		for(j=i;j<=L->length-1;j++)
                    L->a[j-1]=L->a[j];
                L->length--;
	}
	return(x);
}

6、查找函数（查找一个值为e的元素，返回它的位置）

//查找值为e的元素，返回它的位置
int Locate_Elem(SqList L,ElemType e)
{
	int i=0;
	while(L.a[i]!=e) 
              i++;
	if(i<=L.length-1)
		return(i+1);
}

三、顺序表的功能操作函数

1、倒置函数（将原顺序表直接倒置）

//倒置函数 将原顺序表直接倒置
void Reverse(SqList &L)
{
	if (L.length)
		for (int i = 0; i<L.length - 1 - i; i++)
		{
			int t = L.data[i];
			L.data[i] = L.data[L.length - 1 - i];
			L.data[L.length - 1 - i] = t;
		}
}

2、奇偶分开并排序

//奇偶分开并排序
void SplitSort(SqList &L)
{
	int Even = 0;
	int Odd = L.length - 1;
	int i = 0;
	int j = L.length - 1;
	bool flag = false;
	if (L.length)
		for (; i < j; i++, j--)
		{
			while (L.data[i] % 2 != 0)i++;
			while (L.data[j] % 2 == 0)j--;
			if (L.data[i] % 2 == 0 && L.data[j] % 2 != 0&&i<j)
			{
				int temp = L.data[i];
				L.data[i] = L.data[j];
				L.data[j] = temp;
				flag = true;
			}
			if(!flag) //没有交换
			{
				Even = L.length - 1;//全奇数
				Odd = 0; //全偶数
			}
		}
	if (flag)
	{
		for(int i=0;i<L.length;i++)
			if (L.data[i] % 2 == 0) 
			{
				Odd = i;
				Even = i - 1;
				break;
			}
	}
	sort(L.data, L.data + Even + 1);
	sort(L.data + Odd, L.data + L.length);
}

四、顺序表操作总览

/*
Project: sequence_list(数据结构-顺序表)
*/

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define MaxSize 100
#define ElemType int
#define Status int
using namespace std;

//顺序表数据结构
typedef struct
{
	ElemType a[MAXSIZE];
	int length;    //顺序表的实际长度
}SqList, *SqList;  

//***************************基本操作函数*******************************//

//初始化顺序表函数，构造一个空的顺序表 
Status Init_List(SqList &L)
{
	memset(L.data, 0, sizeof(L));//初始化数据为0
	L.length = 0;                //初始化长度为0
	return 0;
}

//创建顺序表函数 初始化前n个数据
void Creat_List(SqList *L)
{
	int i;
	printf("请输入线性表的长度: ");
	scanf("%d",&L->length);
	for(i=0;i<L->length;i++)
	{
		printf("数据 %d =",i);
	        scanf("%d",&(L->a[i]));
        }
}

//插入函数 位置i插入数据 i及之后元素后移  1=<i<=length+1 
void Insert_Sq(SqList *L,int i,ElemType e)
{
	int j;
	if(L->length==MAXSIZE)
		printf("线性表已满!\n");
	else 
        {
		if(i<1||i>L->length+1)
	            printf("输入位置错!\n");
		else 
        {
		for(j=L->length-1;j>=i-1;j--)
	            L->a[j+1]=L->a[j];
                L->a[i-1]=e;   
		L->length++;
		}
	}
}

//删除函数 删除位置i的元素 i之后的元素依次前移
ElemType Delete_Sq(SqList *L,int i)
{
	ElemType x;
	int j;
	if(L->length==0)
		printf("空表!\n");
	else if(i<1||i>L->length)
	{
		printf("输入位置错！\n");
		x=-1;
	}
	else
	{
		x=L->a[i-1];
		for(j=i;j<=L->length-1;j++)
                    L->a[j-1]=L->a[j];
                L->length--;
	}
	return(x);
}

//查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
int Locate_Elem(SqList L,ElemType e)
{
	int i=0;
	while(L.a[i]!=e) 
              i++;
	if(i<=L.length-1)
		return(i+1);
}

//倒置函数 将原顺序表直接倒置
void Reverse(SqList &L)
{
	if (L.length)
		for (int i = 0; i<L.length - 1 - i; i++)
		{
			int t = L.data[i];
			L.data[i] = L.data[L.length - 1 - i];
			L.data[L.length - 1 - i] = t;
		}
}

//奇偶分开并排序
void SplitSort(SqList &L)
{
	int Even = 0;
	int Odd = L.length - 1;
	int i = 0;
	int j = L.length - 1;
	bool flag = false;
	if (L.length)
		for (; i < j; i++, j--)
		{
			while (L.data[i] % 2 != 0)i++;
			while (L.data[j] % 2 == 0)j--;
			if (L.data[i] % 2 == 0 && L.data[j] % 2 != 0&&i<j)
			{
				int temp = L.data[i];
				L.data[i] = L.data[j];
				L.data[j] = temp;
				flag = true;
			}
			if(!flag) //没有交换
			{
				Even = L.length - 1;//全奇数
				Odd = 0; //全偶数
			}
		}
	if (flag)
	{
		for(int i=0;i<L.length;i++)
			if (L.data[i] % 2 == 0) 
			{
				Odd = i;
				Even = i - 1;
				break;
			}
	}
	sort(L.data, L.data + Even + 1);
	sort(L.data + Odd, L.data + L.length);
}

//清空顺序表
void ClearList(SqList &L) {
	L.length = 0;
}

//********************************功能函数*****************************************//

//输出功能函数 按位置从小到大输出顺序表所有元素
void Out_List(SqList L)
{
	int i;
	for(i=0;i<=L.length-1;i++)
		printf("%10d",L.a[i]);
}

//创建顺序表函数
void Create(SqList &L)
{
	int n; bool flag;
	L.length = 0;
	printf("请输入要创建的顺序表长度(>1):");
	scanf("%d", &n);
	printf("请输入%d个数（空格隔开）:", n);
	flag = CreateList(L, n);
	if (flag) {
		printf("创建成功！\n");
		PrintList(L);
	}
	else printf("输入长度非法！\n");
 
}

//插入功能函数 调用Insert_Sq完成顺序表元素插入 调用Out_List函数显示插入成功后的结果
void Insert(SqList &L,int place, ElemType e)
{
	bool flag;
	printf("请输入要插入的位置(从1开始)及元素:\n");
	scanf("%d%d", &place, &e);
	flag = Insert_Sq(L, place, e);
 	if (flag)
	{
		printf("插入成功！！！\n");
		PrintList(L);
	}
}

//删除功能函数 调用Delete_Sq函数完成顺序表的删除 调用Out_List函数显示插入成功后的结果
void Delete(SqList &L,int place;)
{
        bool flag;
	printf("请输入要删除的位置(从1开始):\n");
	scanf("%d", &place);
	flag = Delete_Sq(L, place);
	if (flag)
	{
		printf("删除成功！！！\n");
		PrintList(L);
	}
}

//查找功能函数 调用LocateElem查找元素
void Locate_Elem(SqList L)
{
	ElemType e; int flag;
	printf("请输入要查找的值:\n");
	scanf("%d", &e);
	flag = Locate_Elem(L, e);
	if (flag)
	{
		printf("该元素位置为:%d\n", flag);
	}
	else
		printf("未找到该元素！\n");
}

//菜单
void menu()
{
	printf("********1.创建                        2.插入*********\n");
	printf("********3.删除                        4.查找*********\n");
  	printf("********5.倒置                        6.分奇偶排序***\n");
	printf("********7.输出                        8.清空*********\n");
	printf("********9.退出                              *********\n");
}
int main()
{
	SqList L; int choice;
	InitList(L);
	while (1)
	{
		menu();
		printf("请输入菜单序号：\n");
		scanf("%d", &choice);
 		if (9 == choice) break;
		 switch (choice)
		{
 		case 1:Create(L); break;
		case 2:Insert(L); break;
		case 3:Delete(L); break;
		case 4:Search(L); break;
		case 5:Reverse(L); break;
		case 6:SplitSort(L); break;
		case 7:PrintList(L); break;
		case 8:ClearList(L); break;
		default:printf("输入错误！！！\n");
		}
	}
	return 0;
}

—————————————————————————————————————————————————————————————————————————————————

以上部分代码和图片转自以下两篇文章，如有侵权，请告知删除!

「lady_killer9」  《数据结构-顺序表基本操作的实现（含全部代码）》
原文链接：https://blog.csdn.net/lady_killer9/article/details/82695770

「饭_团」           《顺序表（一）》
原文链接：https://blog.csdn.net/f__yuan/article/details/97000573