学习嵌入式的第二十天——数据结构

数据结构的概念：

相互之间存在一种或多种特定关系的数据元素的集合。

数据之间关系：

逻辑关系：集合，线性（1对1，中间位置的值有且仅有一个前驱，一个后继），树（1对多），图（多对多）

物理关系：

顺序结构（类似于数组）：存储空间连续，有序

链表：存储空间不连续

算法：

对特定问题求解步骤的描述。(类似函数)

算法的特性：输入输出特性（输入可省，输出必须有，数值的改变就可以称为输出），可读性（便于阅读）， 可行性（可以用代码执行出来），有穷性（是有限的），确定性（同一个输入会是同一个输出）

衡量算法好坏的方法。

时间复杂度，时间的度量(事前分析法) ，大O 记法。

O(1)<O(lgn)<O(N)<O(nLgN)<O(N^2)<O(N^3)

顺序表

存储空间是连续

 特征：  支持随机访问   head+5 head[0] O(1)
插入，删除， 整体移动。   O(N)
不具有动态存储功能。

关于顺序表的操作

#include "seqlist.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>SeqList *CreateSeqList(int len)
{SeqList *sl = malloc(sizeof(SeqList));if (NULL == sl){perror("CreateSeqlist malloc error\n");return NULL;}sl->head = malloc(sizeof(DATATYPE) * len);if (NULL == sl->head){perror("CreateSeqlist malloc2 error\n");return NULL;}sl->clen = 0;sl->tlen = len;return sl;
}int InsertTailSeqList(SeqList *list, DATATYPE *data)
{if (IsFullSeqList(list)){printf("seqlist is full\n");return -1;}memcpy(&list->head[list->clen], data, sizeof(DATATYPE));list->clen++;return 0;
}int IsFullSeqList(SeqList *list)
{return list->clen == list->tlen;
}int ShowSeqList(SeqList *list)
{int len = GetSizeSeqList(list);int i = 0;for (i = 0; i < len; i++){printf("name :%s sex :%c age : %d score :%d\n", list->head[i].name, list->head[i].sex, list->head[i].age,list->head[i].score);}return 0;
}int GetSizeSeqList(SeqList *list)
{return list->clen;
}int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{if (IsFullSeqList(list)){printf("seqlist full\n");return -1;}int len = GetSizeSeqList(list);if (pos < 0 || pos > len){printf("pos is incorrect\n");return -1;}for (int i = list->clen; i > pos; i--){// list->head[i]=list->head[i-1];memcpy(&list->head[i], &list->head[i - 1], sizeof(DATATYPE));}memcpy(&list->head[pos], data, sizeof(DATATYPE));list->clen++;return 0;
}int FindSeqList(SeqList *list, char *name)
{int len = GetSizeSeqList(list);for (int i = 0; i < len; i++){if (0 == strcmp(list->head[i].name, name)){return i;}}return -1;
}DATATYPE *GetIetmSeqlist(SeqList *list, int pos)
{int len = GetSizeSeqList(list);if (pos < 0 || pos > len){printf("pos is incorrect\n");return NULL;}return &list->head[pos];
}/*** @brief 删除** @param list  要进行删除的表* @param name  要删除的名字* @return int  成功0 失败-1*/
int DeleteSeqList(SeqList *list, char *name)
{if (0 == list->clen){printf("delete fail\n");return -1;}int ret = FindSeqList(list, name);if (-1 == ret){printf("delete fail\n");return -1;}int i = 0;for (i = ret; i < list->clen; i++){// list->head[i]=list->head[i=1];memcpy(&list->head[i], &list->head[i + 1], sizeof(DATATYPE));}list->clen--;return 0;
}int ClearSeqList(SeqList *list)
{list->clen = 0;return 0;
}//修改
int ModifySeqList(SeqList *list, char *olddata, DATATYPE *newdata)
{int ret = FindSeqList(list, olddata);if (-1 == ret){printf("modify fail\n");return -1;}memcpy(&list->head[ret], newdata, sizeof(DATATYPE));return 0;
}int DestroySeqList(SeqList *list)
{free(list->head);free(list);return 0;
}

Makefile

用于工程管理，可以设定规则将文件一起编译

SRC=main.o
SRC+=seqlist.o
DST=all
CC=gcc
LIB=-lm%o:%.c$(CC) -c $^ -o $@$(DST) :$(SRC)$(CC) $^ -o $@ $(LIB)clean:rm $(DST) *.o