欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-20 14:24:34
...
首先我们谈谈数据结构的重要性:如果说 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;
}