数据结构初级——静态顺序表

首先我们谈谈数据结构的重要性：如果说 Java 是自动档轿车，C 就是手动档吉普。数据结构呢？是变速箱的工作原理。
你完全可以不知道变速箱怎样工作，就把自动档的车子从 A 开到 B，而且未必就比懂得的人慢。

写程序这件事，和开车一样，经验可以起到很大作用，但如果你不知道底层是怎么工作的，就永远只能开车，既不会修车，也不能造车。程序员与程序员的不同水平在于数据结构与算法。虽然java有自己一种集合类，不需要我们自己去实现，但我们也要知道它的底层是怎么样实现的，无论你以后学习哪门语言，我们先从c语言的数据结构来说起，比如java只有你有一定的数据结构基础你才能看懂它的源码。

首先我们来看看顺序表

如果你的结构体和指针的基础不太好，赶紧看看，因为数据结构它玩的就是他们。

顺序表的结构

typedef struct list{
	datatype array[MAX__SIZE];
	int size;
}seqlist;

它是有一个一维数组和一个变量组成

array数组存储数据 MAX_SIZE是他的最大存储长度，size是他的有效元素个数。

datatype是它的数据类型，比如int ，char等 这是使我们代码更加灵活。

数据结构有它的增删改查：（这里我只给大家看看增删的过程，后面会给大家全面介绍）

1.增（大家发现没有这里我们存在效率问题，每次我们插入他的时间复杂度O（n),后面我们会对其进行改善）

//插入数据，e表示插入的位置
int insertbeginlist(seqlist *L, int e)
{
	assert(L);
	int i;
	int k;
	if (L->size > MAX__SIZE + 1)
	{
		printf("表已满!!!\n");
		return 0;
	}
	if (e<0 || e>L->size + 1)
	{
		printf("插入表的位置不合适！！！\n");
		return -1;
	}
	printf("请输如要插入的数字！！！\n");
	scanf("%d", &k);
	for (i = L->size; i >= e; i--)
	{
		L->array[i + 1] = L->array[i];
	}
	L->array[e] = k;
	L->size++;
	printlist(L);
	return 1;
}

2.删

void deletelist(seqlist *L)

{
	int k;
	int ret;
	int j = 0;
	printf("请输入删除的元素");
	scanf("%d", &k);
	int i = 0;
	for (i = 0; i < L->size; i++)
	{
		if (k == L->array[i])
		{
			ret = i;
			break;
		}
	}
	for (j = ret + 1; j < L->size; j++)
	{
		L->array[j - 1] = L->array[j];
	}
	L->size--;
	printf("\n");
}

在这里我们上代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#define MAX__SIZE 100
typedef int datatype;
typedef struct list{
	datatype array[MAX__SIZE];
	datatype size;
}seqlist;
//交换数据
void SWAP(datatype *x, datatype *y)
{
	assert(x);
	assert(y);
	int tmp = 0;
	tmp = *y;
	*y = *x;
	*x = tmp;
}

//初始化顺序表
void initlist(seqlist *L)
{
	assert(L);
	L->size = 0;
}

//插入数据
void putseqlist(seqlist *L, int n)
{
	assert(L);

	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &L->array[i]);

	}
	printf("\n");
	L->size = L->size + n;
}

//打印数据
void printlist(seqlist *L)
{
	assert(L);
	int i = 0;
	for (i = 0; i < L->size; i++)
	{
		printf("%d ", L->array[i]);
	}
}
//插入数据，e表示插入的位置
int insertbeginlist(seqlist *L, int e)
{
	assert(L);
	int i;
	int k;
	if (L->size > MAX__SIZE + 1)
	{
		printf("表已满!!!\n");
		return 0;
	}
	if (e<0 || e>L->size + 1)
	{
		printf("插入表的位置不合适！！！\n");
		return -1;
	}
	printf("请输如要插入的数字！！！\n");
	scanf("%d", &k);
	for (i = L->size; i >= e; i--)
	{
		L->array[i + 1] = L->array[i];
	}
	L->array[e] = k;
	L->size++;
	printlist(L);
	return 1;
}

//删除操作
void deletelist(seqlist *L)

{
	int k;
	int ret;
	int j = 0;
	printf("请输入删除的元素");
	scanf("%d", &k);
	int i = 0;
	for (i = 0; i < L->size; i++)
	{
		if (k == L->array[i])
		{
			ret = i;
			break;
		}
	}
	for (j = ret + 1; j < L->size; j++)
	{
		L->array[j - 1] = L->array[j];
	}
	L->size--;
	printf("\n");
}
//快排
void quicksort1(seqlist *L)
{
	int i = 0;
	int right = 0;
	int ret1=0;
	int ret2=0;
	int end = L->size - 1;
	
	while (right < end)
	{
		int max = L->array[right];
	    int min = L->array[right];
		for (i = right; i <=end; i++)
		{
			if (L->array[i]>max)
			{
				max = L->array[i];
				ret1 = i;
			}
		}
		if (L->array[end] < L->array[ret1])
		{
           SWAP(&L->array[end], &L->array[ret1]);
		   
		}
		end--;
		for (i = end; i >= right; i--)
		{
			if (L->array[i] < min)
			{
				min = L->array[i];	
				ret2 = i;
			}
		}
		if (L->array[right] > L->array[ret2])
		{
			SWAP(&L->array[right], &L->array[ret2]);
		
		}
		right++;
	}
}
int main()
{
	int n = 0;
	printf("请输入数组的长度：\n");
	scanf("%d", &n);
	seqlist L;
	initlist(&L);
	putseqlist(&L, n);
	//printlist(&L);
	//printf("请输入要插入的位置！！！！\n");
	//scanf("%d", &e);
	//insertbeginlist(&L, e);
	//printlist(&L);
	//deletelist(&L);
	//printlist(&L);
	quicksort1(&L);
	printlist(&L);
	system("pause");
	return 0;
}