博客

包含线性表的创建、初始化、增删、输出等操作…

#include<stdio.h> 
#include<stdlib.h>
#define maxSize 100
typedef struct
{
	int data[maxSize];
	int length;
}SqList;
void CreateList(SqList* &L, int a[], int n)//通过数组建立顺序表
{
	int i = 0, k = 0;
	L = (SqList*)malloc(sizeof(SqList));//分配存放顺序表的空间
	while (i < n)//扫描数组，将数组中前n个元素逐个存放至顺序表
	{
		L->data[i] = a[i];
		k++, i++;
	}
	L->length = k;
}
void InitList(SqList* &L)//初始化线性表 initiate 英[ɪˈnɪʃieɪt] 开始， 创始，开辟
{
	L = (SqList *)malloc(sizeof(SqList));
	L->length = 0;
}
void DestroyList(SqList* &L)//销毁线性表 destroy [dɪˈstrɔɪ]杀死; 破坏，摧毁;
{
	free(L);
}
bool ListEmpty(SqList* L)//判断是否为空表 empty[ˈempti]空的，空虚的，空洞的;
{
	return(L->length == 0);
}
int ListLength(SqList* L)//返回线性表长度
{
	return(L->length);
}
void DispList(SqList* L)//输出线性表
{
	if (L->length == 0)
		printf("线性表为空");
	for (int i = 0; i < L->length; i++)
	{
		printf("%d  ", L->data[i]);
		
	}printf("\n");
}
bool Getint(SqList *L, int i, int &e)//求线性表中第X个元素的值
{
	if (i<1 || i>L->length)
		return false;
	e = L->data[i - 1];
	return true;
}
int Locateint(SqList* L, int e)//按元素值查找，并返回逻辑序号 locate[ləʊˈkeɪt]查找…的地点; 确定…的位置

{
	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, int e)//插入数据元素
{
	if (i<1 || i>L->length + 1)
		return false;
	for (int j=L->length;j > i - 1; j--)
	{
		L->data[j ] = L->data[j-1];
	}
	L->data[i - 1] = e;
	L->length ++;
	return true;
}
bool ListDelete(SqList* &L, int i, int &e)//删除第i个数据元素
{
	if (i<1 || i>L->length)
		return false;
	e = L->data[i-1];
	for (int j = i - 1; j < L->length-1; j++)
	{
		L->data[j] = L->data[j + 1];
	}
	L->length--;
	return true;
}
void delnode1(SqList* &L, int x)//删除顺序表中值为x的元素
{
	int k = 0;
	for (int i = 0; i < L->length; i++)
	{
		if (L->data[i] = x)
			;
		else
		{
			L->data[k] = L->data[i];
			k++;
		}
		L->length = k;
	}
}
void delnode2(SqList* &L, int x)
{
	int k = 0, i=0;
	while (i < L->length)
	{
		if (L->data[i] == x)
			k++;
		else
			L->data[i - k] = L->data[i];
		i++;
	}
	L->length -= k;
}
void partition1(SqList* &L)//以data[0]为基准，大于的放后面；小于的放前面partition[pɑ:ˈtɪʃn]分割; 隔墙; 划分
{
	int i = 0, j = L->length - 1;
	int pivot = L->data[0];//pivot[ˈpɪvət]枢轴; 中心点
	while (i < j)
	{
		while (i<j && L->data[j] > pivot)
			j--;
		while (i<j && L->data[i] <= pivot)
			i++;
		if (i < j)
		{
			int v = L->data[i];
			L->data[i] = L->data[j];
			L->data[j] = v;
		}
		
	}
	int v = L->data[i];
	L->data[i] = L->data[0];
	L->data[0] = v;
}
void partition2(SqList* &L)//还需强化理解
{int i = 0, j = L->length - 1;
	int 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;
}

int main()
{
	int a[] = { 6,2,5,7,8,3,5,8,9,4 };
	SqList* L;
	InitList(L);
	CreateList(L,a,10);
	DispList(L);
	printf("线性表长度为%d\n", ListLength(L));
	ListInsert(L, 3, 4);
	DispList(L);
	int e=0;
	ListDelete(L, 3, e);
	printf("删除的数据为%d\n",e);
	DispList(L);
	partition2(L);
	DispList(L);
	system("pause");
	return 0;
}