数据结构顺序表 day19

数据结构

一：基础概念

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

逻辑结构
集合，所有数据在同一个集合中，关系平等。
线性，数据和数据之间是一对一的关系
树， 一对多
图，多对多

物理结构(在内存当中的存储关系)
顺序存储，数据存放在连续的存储单位中。逻辑关系和物理关系一致
链式（链表），数据存放的存储单位是随机或任意的，可以连续也可以不连续。

	struct Per 数据元素
	{
		char name;//数据项
		int age;
		char phone;
	}	

struct Per list[100]; //数据对象

数据的类型，ADT abstruct datatype
是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
原子类型，int，char，float
结构类型，sturct， union，

​ 抽象数据类型， 数学模型 + 操作。
​
​ 程序 = 数据 + 算法

2.算法

​ 算法：是解决特定问题求解步骤的描述，计算机中表现为指令的有限序列，每条指令表示一个或多个操作。
算法的特征，
​ 1，输入，输出特性，输入时可选的，输出时必须的。
​ 2，有穷性，执行的步骤会自动结束，不能是死循环，并且每一步是在可以接受的时间内完成。
​ 3，确定性，同一个输入，会得到唯一的输出。
​ 4，可行性，每一个步骤都是可以实现的。

算法的设计，
1，正确性，
语法正确
合法的输入能得到合理的结果。
对非法的输入，给出满足要求的规格说明
对精心选择，甚至刁难的测试都能正常运行，结果正确
2，可读性，便于交流，阅读，理解
3，健壮性，输入非法数据，能进行相应的处理，而不是产生异常
4，高效，存储低，效率高

算法时间复杂度：也就是执行这个算法所花时间的度量

推导时间复杂度
1，用常数1 取代运行时间中的所有加法常数
2，在修改后的运行函数中，只保留最高阶项。
3，如果最高阶存在且不是1，则取除这个项相乘的常数。

二：各个主要函数

一：CreatSeqList

SeqList *CreateSeqList(int len);

作用：创建一个顺序表，最多可存储 len 个元素。

返回值：创建好的顺序表指针。

二：DestroySeqList

`int DestroySeqList(SeqList *list);`

作用：销毁顺序表，释放所有内存

三：ShowSeqList

int ShowSeqList(SeqList *list);

作用：遍历顺序表，将所有元素打印出来

四：InsertTailSeqList

int InsertTailSeqList(SeqList *list, DATATYPE data);

作用：将一个元素插入到顺序表末尾。

五：IsFullSeqList

int IsFullSeqList(SeqList *list);

作用：判断顺序表是否已满

返回值：

• 1 表示已满。
• 0 表示未满。

六：IsEmptySeqList

int IsEmptySeqList(SeqList *list);

作用：判断顺序表是否为空。

返回值：

• 1 表示为空。
• 0 表示非空。

七：InsertPosSeqList

int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);

作用：将一个元素插入到指定位置 pos。

关键点：

• 判断是否满。
• 判断位置是否有效。
• 从尾部开始向后移动，腾出空间。
• 插入元素到 pos。
• len++。

八：FindSeqList

int FindSeqList(SeqList *list, char *name);

作用：在顺序表中查找名字为 name 的元素

返回值：

• 找到则返回该元素的索引（下标）。
• 未找到返回 -1。

九：ModifySeqList

int ModifySeqList(SeqList *list, char *old, DATATYPE new);

作用：将名字为 old 的元素替换为 new。

流程：

• 调用 FindSeqList 查找旧元素。
• 替换内容。

十：DeleteSeqList

int DeleteSeqList(SeqList *list, char *name);

作用：删除名字为 name 的元素。

流程：

• 找到该元素的下标。
• 用后面的元素依次向前覆盖。
• len--。

十一：ClearSeqList

int ClearSeqList(SeqList *list);

作用：清空顺序表中所有元素，但不释放内存。

等效于：list->len = 0;

三：线性表（升级版的数组）

一：基础定义

1.线性表：零个或多个数据元素的有限序列

​ 元素之间是有顺序了。如果存在多个元素，第一个元素无前驱，最有一个没有后继，其他的元素只有一个前驱和一个后继。
​ 当线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，为空表。在非空的表中每个元素都有一个确定的位置，如果a1是第一个元素，那么an就是第n个元素。

二：memcpy()

void *memcpy(void *str1, const void *str2, size_t n)

参数：

• str1 – 指向用于存储复制内容的目标数组，类型强制转换为 void* 指针。
• str2 – 指向要复制的数据源，类型强制转换为 void* 指针。
• n – 要被复制的字节数。

返回值：该函数返回一个指向目标存储区 str1 的指针。

memcpy(&sl->head[sl->clen], data, sizeof(DATATYPE));

//练习InsertPosSeqList
//由于顺序表的原因，当旧数据和clen一样大时，无法插入新数据
//当旧数据比clen小至少2个数据时，新数据不能直接插入最后一位的位置
//当新数据插入旧数据时，且当旧数据比clen小至少1个数据时，
//新数据前的旧数据不变位置，新数据后的旧数据由于新数据的插入，向后顺延一个数据的位置
int InsertPosSeqList(SeqList *sl, DATATYPE *data, int pos)
{
    if(pos > sl->clen || pos < 0) 
    {
        fprintf(stderr,
              "CreateSeqList malloc2 error\n");  // strerr 专门输出错误信息的
    }
    
    if(pos < sl->clen)
    {
        memcpy(&sl->head[pos+1], &sl->head[pos], sizeof(DATATYPE)*(sl->clen-pos));
    }

    strcpy(sl->head[pos].name, data->name);
    sl->head[pos].age = data->age;
    sl->head[pos].sex = data->sex;
    sl->head[pos].score = data->score;
    

    sl->clen++;
    return 0;
}

二：顺序表（Seqlist）

1.组成

​ Head组头：Head[0]—Head[1]--------------Head[n]·

​ Tlen：总长度

​ Clen：当前长度

sl（顺序表）寻求Head中，其实也是一个名字为head的数组，从零开始放入，head数组长度一开始由自己设置

​ 由图可见，head[0]中存放DATA数据

SeqList *CreateSeqList(int len);
int DestroySeqList(SeqList *list);//销毁
int ShowSeqList(SeqList *list);//展示
int InsertTailSeqList(SeqList *list, DATATYPE data);//尾插
int IsFullSeqList(SeqList *list);//判断是否满
int IsEmptySeqList(SeqList *list);//判断是否空
int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);//按位置插
int FindSeqList(SeqList *list, char *name);//查找
int ModifySeqList(SeqList *list, char *old, DATATYPE new);//修改
int DeleteSeqList(SeqList *list, char *name);//删除
int ClearSeqList(SeqList *list);//清空表

SeqList *CreateSeqList(int n)
{
  SeqList *sl = malloc(sizeof(SeqList));
  if (NULL == sl)
    {
      fprintf(stderr,
              "CreateSeqList malloc error\n");  // strerr 专门输出错误信息的
      return NULL;
    }
  sl->head = malloc(sizeof(DATATYPE) * n);
  if (NULL == sl->head)
    {
      fprintf(stderr,
              "CreateSeqList malloc2 error\n");  // strerr 专门输出错误信息的
      return NULL;
    }
  sl->tlen = n;
  sl->clen = 0;
  return sl;
}
/**
 * @brief  顺序表的尾插
 *
 * @param sl 被插入的 顺序表
 * @param data 被存储的数据的指针
 * @return int  0表示成功 1 表示失败
 */
int InsertTailSeqList(SeqList *sl, DATATYPE *data)
{
  if (IsFullSeqList(sl))
    {
      return 1;
    }
  // strcpy
  memcpy(&sl->head[sl->clen], data, sizeof(DATATYPE));
  sl->clen++;
  return 0;
}


int InsertPosSeqList(SeqList *sl, DATATYPE *data, int pos)
{
    if(pos > sl->clen || pos < 0) 
    {
        fprintf(stderr,
              "CreateSeqList malloc2 error\n");  // strerr 专门输出错误信息的
    }
    
    if(pos < sl->clen)
    {
        memcpy(&sl->head[pos+1], &sl->head[pos], sizeof(DATATYPE)*(sl->clen-pos));
    }

    strcpy(sl->head[pos].name, data->name);
    sl->head[pos].age = data->age;
    sl->head[pos].sex = data->sex;
    sl->head[pos].score = data->score;
    

    sl->clen++;
    return 0;
}
/**
 * @brief 遍历整个顺序表
 *
 * @param sl 被遍历的顺序表的指针
 * @return int 0表示成功 1 表示失败
 */
int ShowSeqList(SeqList *sl)
{
  int size = GetSizeSeqList(sl);
  int i = 0;
  for (i = 0; i < size; i++)
    {
      printf("name:%s sex:%c age:%d score:%d\n", sl->head[i].name,
             sl->head[i].sex, sl->head[i].age, sl->head[i].score);
    }
  return 0;
}

int IsFullSeqList(SeqList *sl) { return sl->clen == sl->tlen; }
int GetSizeSeqList(SeqList *sl) { return sl->clen; }