一、数据结构与算法

1.数据结构

数据：是对客观事物的符号表示，如图像、声音等。
数据元素：是数据的基本单位。
数据项：是构成教据元素的不可分割的最小单位。
一个数据元素可由若干个数据项组成，例如，一位学生的信息记录为一个数据元素，它是由学号、姓名、性别等数据项组成。
数据对象：是具有相同性质的数据元素的集合。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构包括三方面的内容：逻辑结构、存储结构、数据的运算
数据结构的形式定义为：数据结构是一个二元组
```
   Data_Structure =（D,S）
```
其中：D是数据元素的有限集，S是D上数据关系的有限集

1.1.逻辑结构

逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，独立于计算机。
c5.

1.2.存储结构

存储结构（物理结构）是指数据结构在计算机中的表示，它包括数据元素的表示和关系的表示。
存储结构分为四种：顺序存储、链式存储、索引存储和散列存储

顺序存储（常用）：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
链式存储（常用）：借助指示元素存储地址的指针来表示元素之间的逻辑关系。
索引存储：在存储元素信息时，建立索引表————索引项(关键字地址)。
散列存储：对于元素的关键字根据散列函数直接计算出元素的存储地址，又称哈希（hash）存储。

2.算法

算法是对特定问题求解步骤的一种描述

2.1.算法具有下列5个特性：

有穷性，一个算法必须在执行有穷步骤后结束，每一步都要在有穷时间内完成。
确定性，算法中每条指令必须有确切的含义，相同的输入只能得到相同的输出。
可行性，算法中描述的操作都必须是可以执行的。
输入，一个算法有零个或多个输入。
输出，一个算法有一个或多个输出。

2.2.通常设计一个“好”的算法应考虑达到以下目标：

正确性，算法应能够正确地求解问题。
可读性，算法能具有良好的可读性，以帮助人们理解。
健壮性，输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
效率与低存储量需求，效率是指算法执行的时间，存储量需求是指算法执行过程中所需的最大存储空间。

2.3.算法效率的度量

算法效率的度量是通过时间复杂度和空间复杂度来描述的。
一个语句的频度：是指该语句在算法中被重复执行的次数。
算法中所有语句的频度之和记为 T(n)=O(f(n)),f(n)表示基本运算的频度，O(f(n))表示f(n)的数量级。
例子：f(n)=2n,则O(f(n))=n
c6.
c7.

二、顺序表

1.线性表

1.1.线性表的定义

线性表：具有相同数据类型的n(n≥0)个数据元素的有限序列。
C8.
除第一个元素外，每个元素有且仅有一个直接前驱。（a1是a2的直接前驱，a2是a3的直接前驱，以此类推）
除最后一个元素外，每个元素有且仅有一个直接后继。（a3是a2的直接后继，a2是a1的直接后继，以此类推）

1.2.线性表的基本操作

c9.

2.顺序表的结构

2.1.顺序表的定义

顺序表：顺序存储的线性表，它是由一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。（用数组存储）
c10.

2.2.顺序表的类型描述

假定线性表的元素类型为 ElemType，则线性表的顺序存储类型描述为

#define MaxSize 50           //定义线性表的最大长度 
typedef struct{              //把结构体改名为SqList
   ElemType data[MaxSize];   //顺序表的元素 
   int length;               //顺序表的当前长度 
}SqList;                     //顺序表的类型定义

上述一维数组是属于静态分配，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据将会产生溢出，进而导致程序崩溃。

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数据空间的目的，而不需要为线性表一次性地划分所有空间。

#define InitSize 50        //表长度的初始定义 
typedef struct{ 
   ElemType *data;         //指示动态分配数组的指针 
   int MaxSize,length;     //数组的最大容量和当前个数 
}SeqList;                  //动态分配数组顺序表的类型定义


C 语言的初始动态分配语句为 
L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);

2.3.顺序表的特点

顺序表最主要的特点是随机存取，即通过首地址和元素序号可在时间O(1)内找到指定的元素。
顺序表的存储密度高，每个结点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

3.顺序表的实现

3.1.插入操作

从16开始依次往后移一位，再插入50
c11.
在顺序表L的第i(1 ≤ i ≤ L.length+1)个位置插入新元素e。若i的输入不合法，则返回false，表示插入失败；否则，将顺序表的第i个元素及其后的所有元素右移一个位置，腾出一个空位置插入新元素e，顺序表长度增加1，插入成功，返回true。

bool ListInsert(SqList &L,int i,ElemType e){  //布尔类型
   if(i<1||i>L.length+1)                      //判断i的范围是否有效（合法）
      return false; 
   for(int j=L.length;j>=i;j--)               //将第i个元素及之后的元素后移 
      L.data[j]=L.data[j-1];                  //赋值
   L.data[i-1]=e;                             //在位置i处放入e
   L.length++;                                //线性表长度增加1
   return true; 
}

插入操作移动结点的平均次数为 n/2,所以插入算法的平均时间复杂度为O(n)

3.2.删除操作

删除线性表L中第i(1 ≤ i ≤ L.length+1)个位置的元素，若成功则返回true，并将被删除的元素用引用变量e返回，否则返回false。

bool ListDelete(SqList &L,int i,ElemType &e){ 
   if(i<1||i>L.length)                         //判断i的范围是否有效（合法）
      return false; 
   e=L.data[i-1];                              //将被删除的元素赋给e
   for(int j=i;j<L.length;j++)                 //将第i个位置后的元素前移 
      L.data[j-1]=L.data[j]; 
   L.length--;                                  //线性表长度减1
   return true; 
}

删除操作移动结点的平均次数为 (n-1)/2,平均时间复杂度为O(n)

3.3.按值查找操作

在顺序表L中查找第一个元素值等于e的元素，并返回其位序(是第几个值)。

int LocateElem(SqList L,ElemType e){          //int类型
    int i; 
    for(i=0;i<L.length;i++)                   //i 的初值赋为0
        if(L.data[i]==e)                      //判断i是否等于e
           return i+1;                        //下标为i的元素值等于e，返回其位序 
    return 0;                                 //退出循环，说明查找失败 
}

3.4.按位查找操作

int GetElem(SqList L,int i){ 
    if(i<1||i>L.length)                    //判断i的范围是否有效 
      return 0;                            //若无效，则返回0
    return L.data[i-1];                    //有效，返回数组下标为i-1的元素
}