01 数据结构引入和顺序表

阅读引言：从本文开始给大家带来我在复习过程中写的数据结构的代码，分享给需要的同学

一、数据结构引入

1.数据结构解决什么问题

数据结构可以将杂乱无章的数据管理起来，提高数据的访问效率

计算机处理的对象（数据）已不再单纯是数值

其中系、办公室、……教师、学生可视为数据元素。元素之间呈现的是一种层次关系

设田径比赛项目有：A(跳高)、 B(跳远)、C(标枪)、D(铅球)、E(100m跑)、F(200m跑)。参赛选手的项目表，如下表所列：

2.数据结构的逻辑关系

二、顺序表的代码实现

/* squence_list.h */
#ifndef _SQUENCE_LIST_H
#define _SQUENCE_LIST_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define N 128
typedef int data_t;           /* 在编译的时候处理 */
typedef struct {
	data_t arr[N];             /* 顺序表的存储空间 */
	int last;                  /* 数组的最后一个元素的下标， last为-1代表数组中没有元素 */
}sq_list, *sq_link;

sq_link sqlist_create(void);                                    /* 创建顺序表 */
int sq_list_clear(sq_link p);                                   
int is_empty(sq_link p);
int get_length(sq_link p);
int sqlist_insert(sq_link p, data_t value, int pos);
void sqlist_show(sq_link p);
void sqlist_delete(sq_link p);
int sqlist_delete_pos(sq_link p, int pos);
int sqlist_locate(sq_link p, data_t value);
int two_sqlist_merge(sq_link p1, sq_link p2);
int delete_repeate_element(sq_link p);

#endif

/* squence_list.c */
#include "squence_list.h"


sq_link sqlist_create(void)
{
	sq_link p = (sq_link)malloc(sizeof(sq_list));
	if(p == NULL) {
		printf("%s malloc is failed!\n", __func__);
		return NULL;
	}

	memset(p, 0, sizeof(sq_list));
	p->last = -1;

	return p;
}

int sq_list_clear(sq_link p)
{
	if(p == NULL) {
		printf("param of %s is NULL!\n", __func__);
		return -1;
	}

	memset(p, 0, sizeof(sq_list));
	p->last = -1;

	return 0;
}

int is_empty(sq_link p) 
{
	if(p == NULL) {
		printf("param of %s is NULL!\n", __func__);
		return -1;
	}
	if(p->last == -1) {
		return 1;
	}
	return 0;
}

int get_length(sq_link p)
{
	if(p == NULL) {
		printf("param of %s is NULL!\n", __func__);
		return -1;
	}

	return (p->last + 1);
	
}

/* 顺序表的缺点： 涉及到插入数据和删除数据的时候会有大量的数据移动 */
int sqlist_insert(sq_link p, data_t value, int pos) 
{
	int i;
	if(p == NULL) {
		printf("param of %s is NULL!\n", __func__);
		return -1;
	}
	if(p->last >= N) {
		printf("squence list is full!\n");
		return -1;
	}

	/* 存储位置必须连接着 */
	if(pos < 0 || pos > p->last + 1) {
		printf("index of arrary is invalid!\n");
		return -2;
	}

	/* 将位于pos位置后的数据移动 */
	for(i = p->last; i >= pos; i--) {
		p->arr[i + 1] = p->arr[i];
	}
	p->arr[pos] = value;
	p->last++;

	return 0;
	
}

void sqlist_show(sq_link p)
{
	int i;
	if(p == NULL) {
		printf("param of %s is NULL!\n", __func__);
		return ;
	}

	if(p->last == -1) {
		printf("squence list is empty!\n");
		return ;
	}
	
	for(i = 0; i <= p->last; i++) {
		printf("%d ", p->arr[i]);
	}
	puts("");
	
}


void sqlist_delete(sq_link p)
{
	if(p == NULL) {
		printf("param of %s is NULL!\n", __func__);
		return;
	}

	free(p);
	p = NULL;         /* 防止野指针页虚悬空指针 */
}


int sqlist_delete_pos(sq_link p, int pos) 
{
	int i;
	if(p == NULL) {
		printf("param of %s is NULL!\n", __func__);
		return -1;
	}

	if(pos < 0 || pos > p->last) {
		printf("index of delete is invalid!\n");
		return -1;
	}

	for(i = pos; i < p->last; i++) {
		p->arr[i] = p->arr[i + 1];
	}

	p->last--;

	return 0;
}

int sqlist_locate(sq_link p, data_t value)
{
	int i;
	if(p == NULL) {
		printf("param of %s is NULL!\n", __func__);
		return -1;
	}

	for(i = 0; i <= p->last; i++) {
		if(p->arr[i] == value) {
			return i;
		}
	}

	return -1;
}


/* 将p1和p2的并集插入到p1中 */
int two_sqlist_merge(sq_link p1, sq_link p2)
{

	int i = 0;
	if(p1 == NULL || p2 == NULL) {
		printf("param of %s is NULL!\n", __func__);
		return -1;
	}

	while(i < p2->last) {
		if(sqlist_locate(p1, p2->arr[i]) == -1) {
			sqlist_insert(p1, p2->arr[i], p1->last + 1);
		}
		i++;
	}

	return 0;
}


/* 删除顺序表中的重复元素 */
int delete_repeate_element(sq_link p)
{
	int i = 0, j = 0;
	if(p ==NULL) {
		printf("param of %s is NULL!\n", __func__);
		return -1;
	}

	if(p->last == 0) {
		return -1;
	}

	while(i < p->last) {
		j = i + 1;
		while(j <= p->last) {
			if(p->arr[i] == p->arr[j]) {
				sqlist_delete_pos(p, j);
			} 
			j++;
		}
		i++;
	}

	return 0;
}