数据结构——顺序表基本操作的实现（初始化、取值、查找、插入）

一、线性表与顺序表的概述

线性表的数据元素的逻辑特征是线性的，是一种典型的线性结构。这样的结构可以借鉴数组，如数组a[10]中，a[1]前一定是a[0]，a[1]后一定是a[2]，首结点（a[0]）前面无元素，尾结点（a[9]）后面无节点。

顺序表表示数据元素不仅在逻辑上线性，并且存储位置也是线性的。逻辑线性如上述例子所示，而数据元素的存储位置线性可解释为：当数组a[10]的数据类型为int（int型占4个字节），此时假设a[0]的初始地址为0x0000 0000，则可以直接推出a[1]的地址为0x0000 0004……a[4]的地址为0x0000 0010。

二、顺序表基本操作的实现

1、头文件

#include <stdlib.h>
#include <stdio.h>
#include <iostream>

using namespace std;		//显示cout未定义，需要加上这句

2、宏定义

#define MaxSize		100
#define OK			1
#define ERROR		0
#define TRUE		1
#define FALSE		0
#define INFEASIBLE	-1
#define OverFlow	-2
typedef int ElemType;
typedef int status;

3、结构体定义

typedef struct
{
	//ElemType elem[MaxSize];		//数组表示（静态分配）
	ElemType *elem;			        //指针表示（动态分配）
	int length;
}SqList;

4、相关操作函数

（1）初始化顺序表

/* 初始化顺序表 */
status InitList(SqList &L)
{
	L.elem = (ElemType*)malloc(sizeof(ElemType) * MaxSize);		//为顺序表分配存储空间
	if (!L.elem) exit(OVERFLOW);								//存储分配失败退出
	L.length = 0;												//空表长度为0
	return OK;
}

（2）取值

/* 取值：将顺序表中第i个元素的值赋给e */
status GetElem(SqList &L, int i, ElemType &e)
{
	if (i < 1 || i>100) return ERROR;
	e = L.elem[i - 1];
	return OK;
}

（3）查找顺序表中元素

/* 查找e位于顺序表L中的位置 */
status LocateElem(SqList L, ElemType e)
{
	int i = 0;
	for (int i = 0; i < L.length; i++)
	{
 		if (L.elem[i] == e)
		{
			return i + 1;
		}
	}
	return ERROR;
}

（4）删除元素

/* 删除元素，若要将删除的元素保存起来，则添加形参ElemType e */
status ListDelete(SqList &L, int i)
{
	if (i<1 || i>L.length) return ERROR;
	for (int j = i; j <= L.length - 1; j++)
	{
		L.elem[j - 1] = L.elem[j];
	}
	L.elem[L.length - 1] = 0;				//将最后一个元素清零
	L.length--;								//表长-1
	return OK;
}

（5）打印顺序表中所有元素

/* 打印顺序表中所有元素 */
status ShowListElem(SqList L)
{
	for (int i = 0; i < L.length; i++)
	{
		cout << L.elem[i] << " ";
	}
	cout << " " << endl;
	return OK;
}

（6）插入元素

/* 插入元素 */
status ListInsert(SqList &L, int i, ElemType e)
{
	if (i<1 || i>L.length+1) return ERROR;		
	if (L.length == MaxSize) return ERROR;
	for (int j = L.length-1; j >= i - 1; j--)
	{
		L.elem[j + 1] = L.elem[j];
	}
	L.elem[i - 1] = e;
	L.length++;
	return OK;
}

（7）其他函数

/* 
	销毁已存在的顺序表
	若分配存储时用new，则对应用delete；若采用malloc，则用free。
*/
status ListDestroy(SqList &L)
{
	free(L.elem);
	return OK;
}
/* 清空顺序表 */
status ListClear(SqList &L)
{
	L.length = 0;
	return OK;
}
/* 顺序表是否为空 */
status IsEmpty(SqList &L)
{
	if (!L.length) return TRUE;
	else return FALSE;
}
/* 顺序表的长度 */
status ListLength(SqList &L)
{
	return L.length;
}

（8）main

int main(void)
{
	int a[5] = { 1,2,4,5,6 };
	SqList L;
	InitList(L);
	cout << "顺序表的初始长度为：" << L.length << endl;
	L.elem = a;
	L.length = 5;
	ShowListElem(L);
	cout << "存入数据后，顺序表的长度为：" << L.length << endl;
	int b = 0;				//GetElem中将顺序表中的第i个元素赋给b
	int Location = 0;		//表示c位于顺序表的位置
	int c = 5;				//LocateElem在顺序表中定位c
	GetElem(L, 3, b);
	cout << "未操作时，取出值为：" << b << endl;
	ListInsert(L, 3, 3); 
	GetElem(L, 3, b);
	cout << "插入3之后，取出值为：" << b << endl;
	ShowListElem(L);
	cout << "插入3之后，顺序表长度为：" << L.length << endl;
	Location = LocateElem(L, c);
	cout << "6位于顺序表的位置：" << Location << endl;
	ListDelete(L, 3);
	GetElem(L, 3, b);
	cout << "删除3之后，取出值为：" << b << endl;
	cout << "删除3之后，顺序表长度为：" << L.length << endl;
	Location = LocateElem(L, c);
	cout << "6位于顺序表的位置：" << Location << endl;
	ListClear(L);
	cout << "清空链表后，顺序表长度为：" << L.length << endl;

	return 0;
}