1.线性表

1.1线性表之顺序表

运行环境:VS2019(其他版本也可以,基本的代码都通用)

语言环境:c/c++

(需要将源文件后缀为.cpp,一些头文件需要)
声明:大部分代码均参考自=>【数据结构教程李春葆（第5版）】

1.1.1头文件的创建

在运行和编写代码前,为了条理更加清楚,首先创建三个头文件

(1) MyHead.h

#pragma once

//导入所需头文件:
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>

using namespace std;

(2) SqList.h

#pragma once
#include "MyHead.h"

(3) Example.h

#pragma once
#include "SqList.h"

先说说这三个头文件的作用的，首先第一个MyHead.h，是总的头文件，里面包含了基本运行的头文件。第二个是SqList.h，用于即将放入本章节的顺序表创建一系列函数的声明。第三个是Example.h，是用于存放本章节的例题，非习题。之后也可以把习题放入里面。他们的包含关系是(3)>(2)>(1)，所以到时候main函数直接包含Example.h即可。

总结:除了MyHead.h头文件之外，其他两个头文件，基本只放函数声明。

1.1.2基本的文件

下面是顺序表的基本结构和方法:

(1) SqList.h头文件

#pragma once
#include "MyHead.h"

#define MaxSize 50		//线性表最大长度
typedef int ElemType;	//定义抽象数据类型

typedef struct
{
	ElemType data[MaxSize]; //存放线性表元素
	int length;				//存放长度
} SqList;					//类型

//由数组a[0,...,n - 1]创建顺序表L
void CreateList(SqList*& L, ElemType a[], int n);

//初始化线性表
void InitList(SqList*& L);

//销毁线性表
void DestoryList(SqList*& L);

//判断线性表是否为空表
bool ListEmpty(SqList* L);

//求线性表的长度
int ListLength(SqList* L);

//输出线性表
void DispList(SqList* L);

//求线性表中的某个数据元素值
bool GetElem(SqList* L, int i, ElemType& e);

//查找元素的位置,若不存在返回-1
int LocateElem(SqList* L, ElemType e);

//插入数据元素
bool ListInsert(SqList*& L, int i, ElemType e);

//删除数据元素
bool ListDelete(SqList*& L, int i, ElemType& e);

(2)SqList.cpp

#include "SqList.h"

void CreateList(SqList*& L, ElemType a[], int n)
{
	int i = 0, k = 0;
	L = (SqList*)malloc(sizeof SqList);
	while (i < n)
		L->data[k++] = a[i++];
	L->length = k;
}

void InitList(SqList*& L)
{
	L = (SqList*)malloc(sizeof SqList);
	L->length = 0;
}

void DestoryList(SqList*& L)
{
	free(L);
}

bool ListEmpty(SqList* L)
{
	return L->length == 0;
}

int ListLength(SqList* L)
{
	return L->length;
}

void DispList(SqList* L)
{
	for (int i = 0; i < L->length; i++)
		printf("%d ", L->data[i]);
	puts("");
}

bool GetElem(SqList* L, int i, ElemType& e)
{
	if (i < 1 || i > L->length)
		return false;
	e = L->data[i - 1];
	return true;
}

int LocateElem(SqList* L, ElemType e)
{
	int i = 0;
	while (i < L->length && L->data[i] != e)
		i++;
	if (i >= L->length)
		return 0;
	else return i + 1;
}

bool ListInsert(SqList*& L, int i, ElemType e)
{
	if (i < 1 || i > L->length + 1)
		return false;
	i--;								//将i转为数组下标意义
	for (int j = L->length; j > i; j--) //从尾开始,挪动元素,直到下标为i的位置
		L->data[j] = L->data[j - 1];
	L->data[i] = e;						//插入元素
	L->length++;						//插入后长度+1
	return false;
}

bool ListDelete(SqList*& L, int i, ElemType& e)
{
	if (i < 1 || i > L->length)
		return false;
	--i;								//将i转换数组下标意义
	for (int j = i; j < L->length; j++)
		L->data[j] = L->data[j + 1];	//下标i被删除,挪动元素
	e = L->data[i];						//返回删除的元素(引用)
	L->length--;
	return true;
}

写好基本的结构和方法后，下面是例题的代码：

(3)Example.h

#pragma once
#include "SqList.h"

//例2.3
void delnode1(SqList*& L, ElemType x);
void delnode2(SqList*& L, ElemType x);

//例2.4
void partition1(SqList*& L);
void partition2(SqList*& L);

//例2.5
void myMove(SqList*& L);
void move2(SqList*& L);

(4)Example.cpp

#include "Example.h"

void delnode1(SqList*& L, ElemType x)
{
	int k = 0;
	for (int i = 0; i < L->length; i++)
		if (L->data[i] != x)
			L->data[k++] = L->data[i]; //若当前元素不为x,则依次从头插入
	L->length = k;					   //在原表的情况下操作,更改长度
}

//两个指针k和i维护L表,k跟随i,指向的是为x的元素,等待i扫描后面的不为x的元素来填充
void delnode2(SqList*& L, ElemType x)
{
	int k = 0, i = 0;					
	while (i++ < L->length)
		if (L->data[i] == x)
			k++;
		else
			L->data[i - k] = L->data[i];
	L->length -= k;
}

void partition1(SqList*& L)
{
	int i = 0, j = L->length - 1;
	ElemType pivot = L->data[0];
	while (i < j)
	{
		while (i < j && L->data[j] > pivot)	//右往左找到一个小于等于基准的元素
			j--;
		while (i < j && L->data[i] <= pivot)//右往左找到一个比基准大的元素
			i++;
		if (i < j)
			swap(L->data[i], L->data[j]);
	}		
	swap(L->data[0], L->data[i]);
}

void partition2(SqList*& L)
{
	int i = 0, j = L->length - 1;
	ElemType pivot = L->data[0];
	while (i < j)
	{
		while (j > i && L->data[j] > pivot)
			j--;
		L->data[i] = L->data[j];
		while (i < j && L->data[i] <= pivot)
			i++;
		L->data[j] = L->data[i];
	}
	L->data[i] = pivot;
}

void myMove(SqList*& L)
{
	int i = 0, j = L->length - 1;
	while (i < j)
	{
		while (j > i && (L->data[j] & 1) == 0)
			j--;
		while (i < j && L->data[i] & 1)
			i++;
		if (i < j) 
			swap(L->data[i], L->data[j]);
	}
}

void move2(SqList*& L)
{
	int i = -1;
	for (int j = 0; j < L->length; j++)
	{
		if (L->data[j] & 1)
		{
			i++;
			if (i != j)
				swap(L->data[i], L->data[j]);
		}
	}
}

1.1.3 代码的测试

下面是main方法，如果有冲突，可自行注释一下:

(5)main.cpp

#include "Example.h"

int main()
{
	int arr[] = { 3,8,2,7,1,5,3,4,6,0 };	//创建数组
	int len = sizeof arr / sizeof arr[0];	//数组长度
	SqList *list;							
	CreateList(list, arr, len);				//创建线性表
	DispList(list);							//遍历输出

	

	//测试获取元素
	ElemType e;
	if (GetElem(list, 3, e))
		printf("获取成功!获取的元素的值为:%d\n",e);
	else
		printf("获取失败!\n");
	//测试获取顺序表长度
	printf("顺序表的长度:%d\n", ListLength(list));
	
	//测试获取元素下标
	int index = LocateElem(list, e);
	if (!index)
		printf("%d的下标为:%d\n", e, index);
	else
		printf("未查到该元素!\n");

	//测试插入和删除
	ListInsert(list, 5, 999);
	printf("插入后的顺序表:");
	DispList(list);

	ListDelete(list, 3, e);
	printf("删除后的顺序表:");
	DispList(list);

	//测试是否为空
	if (ListEmpty(list))
		printf("list表为空\n");
	else
		printf("list表不为空\n");

	//测试例2.4
	//partition2(list);
	//DispList(list);


	//测试例2.5
	move2(list);
	DispList(list);

	DestoryList(list);						//销毁线性表
	return 0;
}