推荐书籍：《算法导论》 《编程之美》
什么是数据结构？
1.数据
数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。（数据不仅包含整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型。）
2.数据元素
数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被成为记录。（比如：鸡鸭牛羊猪狗等动物就是禽类的数据元素）
3.数据项
数据项：一个数据元素可以由若干个数据项组成。（比如：人可以有眼耳口鼻这些数据项）。
数据项是数据不可分割的最小单位。
4.数据对象
数据对象：是性质相同的数据元素的集合，是数据的子集。（什么是性质相同呢，是指数据元素具有相同数量和类型的数据项，比如：人都有姓名、生日、性别等相同的数据项）
既然数据对象是数据的子集，在实际应用中，处理的数据元素通常具有相同性质，在不产生混淆的情况下，我们都将数据对象简称为数据。
5.数据结构
不同的数据元素之间不是独立的，而是存在特定的关系，我们将这些关系成为结构。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
开课了！！
数据逻辑结构大概分为两大类：线性结构和非线性结构。
线性结构：线性表，栈，队列。（一对一）
非线性结构：树，图，集合。（一对多，多对多，独立）
存储形式：顺序存储，链式存储
顺序存储：arr数组
链式存储：单链表，双向链表
面试常考：单项循环链表，单项不循环链表，有头节点单链表，无头节点单链表。
现实常用：双向链表。
线性表实现
存储结构
#ifndef _SQLIST_H
#define _SQLIST_H
#define DATASIZE 1024
typedef int datatype;
typedef struct node_st
{
datatype data[DATASIZE];
int last;
}sqlist;
#endif创建
sqlist* sqlist_create()
{
sqlist*me;
me = malloc(sizeof(*me) );
if(me == NULL)
return NULL;
me->last = -1;
return me;
}
void sqlist_create1(sqlist** ptr)
{
*ptr = malloc(sizeof(**ptr));
if(*ptr ==NULL)
return;
(*ptr)->last = -1;
return;
}
int main()
{
sqlist* list;
printf("sizeof = %ld \n",sizeof(*list) );
list = sqlist_create();
sqlist_create1(&list);
if(list == NULL)
{
printf("err \n");
}
sqlist_destory(list);
exit(0);
}
插入
int sqlist_insert(sqlist* me,int i,datatype *data)
{
if(me->last == DATASIZE-1 ) //存满失败
return -1;
if(i<0 || i >me->last +1 )
return -2;
int j = me->last; //j是最后一个数据有效位置的值
for(;i<=j;j--)
me->data[j+1] = me->data[j];
me->data[i] = *data;
me->last++;
return 0;
}
显示
void sqlist_display(sqlist*me)
{
if(me->last == -1)
return;
for(int i=0;i<= me->last;i++)
{
printf("%d ",me->data[i]);
}
printf("\n");
return ;
}
测试输出
int main()
{
sqlist* list;
printf("sizeof = %ld \n",sizeof(*list) );
list = sqlist_create();
sqlist_create1(&list);
if(list == NULL)
{
printf("err \n");
}
int err;
datatype arr [] = {12,22,33,44,55};
for(int i=0;i< sizeof(arr)/sizeof(*arr);i++)
{
if( (err = sqlist_insert(list,0,&arr[i])) != 0 )
{
printf("insert error \n");
if(err == -1)
fprintf(stderr,"the arr is full \n");
else if(err == -2)
fprintf(stderr,"the pos is not continuous\n");
else
fprintf(stderr,"Error\n");
exit(-1);
}
}
sqlist_insert(list,2 ,&arr[0]);
sqlist_display(list);
sqlist_destory(list);
}删除元素
int sqlist_delete(sqlist* me,int i)
{
int j;
if(i<0 || i > me->last )
return -1;
for(j = i+1; j< me->last;j++)
{
me->data[j-1] =me->data[j]
}
me->last--;
return 0;
}
完整实现
main.c
#include <stdlib.h>
#include <stdio.h>
#include "sqlist.h"
int main()
{
sqlist* list,*list1;
printf("sizeof = %ld \n",sizeof(*list) );
list = sqlist_create();
sqlist_create1(&list);
sqlist_create1(&list1);
if(list == NULL)
{
printf("err \n");
}
int err;
datatype arr [] = {12,22,33,44,55};
for(int i=0;i< sizeof(arr)/sizeof(*arr);i++)
{
if( (err = sqlist_insert(list,0,&arr[i])) != 0 )
{
printf("insert error \n");
if(err == -1)
fprintf(stderr,"the arr is full \n");
else if(err == -2)
fprintf(stderr,"the pos is not continuous\n");
else
fprintf(stderr,"Error\n");
exit(-1);
}
}
// sqlist_setempty(list);
sqlist_insert(list,0 ,&arr[0]);
sqlist_insert(list1,0 ,&arr[0]);
printf("list: \n");
sqlist_display(list);
printf("list1: \n");
sqlist_display(list1);
sqlist_union(list,list1);
// sqlist_delete(list,0);
sqlist_display(list);
sqlist_destroy(list);
sqlist_destroy(list1);
exit(0);
}
sqlist.c
#include "sqlist.h"
#include <stdlib.h>
#include <stdio.h>
sqlist* sqlist_create()
{
sqlist*me;
me = malloc(sizeof(*me) );
if(me == NULL)
return NULL;
me->last = -1;
return me;
}
void sqlist_create1(sqlist** ptr)
{
*ptr = malloc(sizeof(**ptr));
if(*ptr ==NULL)
return;
(*ptr)->last = -1;
return;
}
int sqlist_insert(sqlist* me,int i,datatype *data)
{
if(me->last == DATASIZE-1 ) //存满失败
return -1;
if(i<0 || i >me->last +1 )
return -2;
int j = me->last; //j是最后一个数据有效位置的值
for(;i<=j;j--)
me->data[j+1] = me->data[j];
me->data[i] = *data;
me->last++;
return 0;
}
int sqlist_delete(sqlist* me,int i)
{
int j;
if(i<0 || i > me->last )
return -1;
for(j = i+1; j< me->last;j++)
{
me->data[j-1] =me->data[j];
}
me->last--;
return 0;
}
int sqlist_find(sqlist* me,datatype*data)
{
if(sqlist_isempty(me) == 0 )
return -1;
for(int i=0;i<= me->last ;i++)
{
if(me->data[i] == *data)
return i;
}
return -2;
}
int sqlist_isempty(sqlist*me)
{
if(me->last == -1)
return 0;
return -1;
}
int sqlist_setempty(sqlist*me)
{
me->last = -1;
return 0;
}
int sqlist_getnum(sqlist*me)
{
return me->last+1 ;
}
void sqlist_display(sqlist*me)
{
if(me->last == -1)
return;
for(int i=0;i<= me->last;i++)
{
printf("%d ",me->data[i]);
}
printf("\n");
return ;
}
int sqlist_destroy(sqlist*me)
{
free(me);
return 0;
}
int sqlist_union(sqlist*list1,sqlist* list2)
{
for(int i=0;i<list2->last;i++)
{
if(sqlist_find(list1,&list2->data[i]) < 0 )
{
sqlist_insert(list1,list1->last,&list2->data[i]);
}
}
return 1;
}
sqlist.h
#ifndef _SQLIST_H
#define _SQLIST_H
#define DATASIZE 1024
typedef int datatype;
typedef struct node_st
{
datatype data[DATASIZE];
int last;
}sqlist;
sqlist* sqlist_create();
void sqlist_create1(sqlist**);
int sqlist_insert(sqlist*,int i,datatype *);
int sqlist_delete(sqlist*,int i);
int sqlist_find(sqlist*,datatype*);
int sqlist_isempty(sqlist*);
int sqlist_setempty(sqlist*);
int sqlist_getnum(sqlist*);
void sqlist_display(sqlist*);
int sqlist_destroy(sqlist*);
int sqlist_union(sqlist*,sqlist*);
#endif
makefile
CC = gcc
OBJS = main.o sqlist.o
CFLAGS= -g -c -Wall
all:$(OBJS)
$(CC) $^ -o $@
%.o:%.c
$(CC) $^ $(CFLAGS) -o $@
clean:
$(RM) -r *.o all
