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

数据结构的概念：

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

数据之间关系：

逻辑关系：集合，线性（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