推荐书籍:《算法导论》 《编程之美》
什么是数据结构?
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