数据结构笔记目录：

  1. 数据结构与算法（一）—— 线性表的顺序表示及常用操作
  2. 数据结构与算法（二）—— 线性表的链式表示及常用操作
  3. 数据结构与算法（三）—— 线性表的应用
  4. 数据结构与算法（四）—— 栈和队列
  5. 数据结构与算法（五）—— 串、数组和广义表
  6. 数据结构与算法（六）—— 数和二叉树

顺序表的构建

1
2
3
4
5
#define max_Size 100
typedef struct{
    ElemType elem[max_Size];
    int length;//当前长度
}SqList;

Ex:1

1
2
3
4
5
6
7
8
9
10
#define max_Size 100 //宏定义最大长度
typedef struct{
    char ISBN[20];
    char name[50];
    float price;
}Book;
typedef struct SqList{
    Book* add;//存储空间基地址
    int length;//当前图书个数
}SqList;//这是一个存放图书信息的顺序表

EX:2：使用动态分配内存方式的顺序表

1
2
3
4
5
6
7
8
#define max_Size 100
typedef struct SqList{
    ElemType* elem;
    int length;//当前长度
}SqList;
//主函数中内容
SqList L;//定义顺序表变量L
L.elem = (ElemType*)malloc(sizeof(ElemType)*max_Size);//动态分配内存

顺序表的查找

1
2
3
4
5
6
7
8
int LocateElem(SqList *L,ElemType e){
    for(i=0;i<L->length;i++){
    if(L->elem[i] == e){
    return i+1;
        }
    }
return 0;
}

顺序表的查找算法分析：平均查找长度ASL（Average Search Length）

需要与给定值进行比较的关键字的个数的期望值（即查找次数的平均值）叫做查找算法的平均查找长度，用于分析查找算法的时间复杂度

ASL=P1*N1+P2*N2+P3*N3…..(P为第i个记录被查找的概率，系数N为找到第i个元素须比较的次数)

关于顺序表的查找算法，有：ASL=P*0+P*1+…P*n(P=1/n)=(n+1)/2（查找次数从0到n次）

顺序表的插入

1
2
3
4
5
6
7
8
9
10
int ListInsert_Sq(SqList *L,int i，ElemType e){
    if(i>L->length+1||i<1) return 0;//i值不合法
    if(L->length == max_Size) return 0;//顺序表已满
    for(j=L->Length-1;j<i;j--){
        L->elem[j+1] = L->elem[j];
        }//将元素依次向后移空出下标为i-1的位置
    L->elem[i-1] = e;
    l->length++;
    return 1;
}

顺序表的插入算法分析

INS=P*1+P*2+…P*n(P=1/n+1)=n/2（移动次数从0次到n次）

顺序表的删除

1
2
3
4
5
6
7
8
9
10
int ListDelete(Sqlist *L,int i,ElemType *e){
    if(i>L->length||i<1) return 0;//i值不合法
    if(L->length == 0) return 0;//顺序表为空
    *e = L->elem[i-1];
    for(j=i-1;j<L.length;j++){
        L->elem[j] = L->elem[j+1];
    }
    L->length--;
    return 1;
}

顺序表的插入算法分析

DEL=P*1+P*2+…P*(n-1)(P=1/n)=(n-1)/2（移动次数从0到(n-1)）