数据结构与算法

算法入门概念

算法(Algorithm):一个计算过程，解决问题的方法Niklaus Wirth:“程序 = 数据结构 + 算法”
输入—->算法—–>输出

物理结构中数据元素的存储结构形式有两种: 顺序存储和链式存储。

计算1-100的和

#include <stdio.h>

int main ()
{
  int i, sum = 0, n = 100;
  for(i = 0;i <= 100;i++) {
    sum = sum + i;
  }
  printf("%d",sum);
  return 0;
}

#include <stdio.h>

int main ()
{
  int i, sum = 0, n = 100;
  sum = (1+100)*n/2;
  printf("%d",sum);
  return 0;
}

时间复杂度是用来估计算法运行时间的一个式子(单位)
一般来说，时间复杂度高的算法比复杂度低的算法慢
常用的时间复杂度所耗费的时间从小到大依次是:O(1) < O(logn) < (n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)< O(n!) < O(n^n)

[例]将一维数组a中的n个数逆序存放到原数组中

for(i=0;i<n/2;i++) {
  t = a[i];
  a[i] = a[n-i-1];
  a[n-i-1] = t;
}
// O(1)

for(i=0;i<n;i++)
  b[i]=a[n-i-1];
for(i=0;i<n;i++)
  a[i]=b[i];
// O(n)

算法设计的要求：正确性，可读性，健壮性，高效性

一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长

所以线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，称为空表。

顺序存储结构存在问题:

InitList(&L): 初始化操作，建立一个空的线性表L。
ClearList(&L): 将线性表清空。
DestroyList(&L)：初始条件，线性表L已经存在。操作结果: 销毁线性表L。
ListEmpty(L): 判断线性表是否为空表，若线性表为空返回true，否则返回false。
ListLength(L): 返回线性表L的元素个数。
GetElem(L,i,&e): 将线性表L中的第i个位置元素值返回给e。
LocateElem(L,e,compare()): 返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。
PriorElem(L, cur_e, &pre_e)
初始条件: 线性表L已经存在，操作结果: 若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱,否则操作失败; pre_e无意义。
NextElem(L, cur_e, &next_e)
初始条件: 线性表L已经存在,操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继否则操作失败, next_e无意义.
Listlnsert(&L, i, e)：初始条件，线性表L已经存在,1 <= i <= ListLength(L)+1 操作结果，在L的第i个位置之前插入新的数据元素e,L的长度加一。
ListDelete(&L, i, &e):初始条件,线性表L已经存在，1 <= i <= ListLength(L),操作结果,删除L的第i个数据元素,并用e返回其值, L的长度减一
ListTraverse(&L, visited()):初始条件,线性表L已经存在,操作结果,依次对线性表中每个元素调用visited()

顺序存储定义: 把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

地址计算方法：
假设ElemType占用的是x个存储单元(字节),那么线性表中第i+1个数据元素和第i个数据元素的存储位置的关系是 (LOC表示获得存储位置的函数): LOC(ai+1) = LOC(ai) + x

所以对于第i个数据元素ai的存储位置可以由a1推算得出: LOC(ai) = LOC(a1) + (i-1)*x

#define LISTINIT SIZE 100 //线性表存储空间的初始分配量
typedef struct {
    ElemType elem[LIST_INIT_SIZE];
    int length; // 当前长度
}SqList;

typedef struct{
  ElemType *elem;\
  int length;
} SqList; //顺序表类型
L.elem=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);