阅读引言： 从本文开始给大家带来我在复习过程中写的数据结构的代码， 分享给需要的同学
一、数据结构引入
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;
}
