数据结构与算法（c语言）--day01_综合

一，线性表 --顺序存储结构

1.定义顺序表的结构类型（数组静态分配）

#define List_max 100typedef struct List{ElemType data[List_max];    // 顺序表的最大存储空间,首地址//ElemType 是类c语言，C语言不能运行，只是数据结构的一种表是方式，相当于类型（int float....）//给他就相当于什么    int length; //表中的当前长度
} Sqlist; //定义顺序表类型//typedef struct List相当于 给这个结构体一个便利方式吧，Sqlist == struct ListSqlist L 相当于定义了L,L是Sqlsit这种类型的顺序表

数组动态分配

#define List_max 100typedef struct List{ElemType *data;int length;} Sqlist;//开始分配空间
Sqlist L;
L.data = (ELemType*)malloc(sizeof(ElemType)*list_max);

内存分配函数

#define List_max 100typedef struct List{ElemType *data;int length;} Sqlist;//开始分配空间
Sqlist L;
L.data = (ELemType*)malloc(sizeof(ElemType)*list_max);1          2        3      4       5         6看标的序号，可以分析
malloc函数是需要引入#include<stdlib.h>3. malloc()函数开辟设定的空间并且返回这段空间的首地址，可以看出L.data正好是该数组的首地址4,5  4表示的sizeof函数得到数据类型的字节，而EemType是数据类型6. 表示分配多大的空间2. 表示的是按照神魔类型来进行划分块，比如int类型是四个字节那么就是按照4个字节进行分块，
此处的是指针类型。free（）释放空间

操作元素

引用成员

一，
Sqlist L 引用成员 L.data[i]     L.length二，用指针Sqlist *L引用成员 L->data       L->length

2. 开始实操

2.1 开始准备

2.2 线性表L的初始化

status InitList(Sqlist &L){ // 参数用引用L.data = (Elemtype*)malloc(sizeof(ElemType)*list_max);//给数组分配空间if(!L.data)exit(OVERFLOW); //分配空间失败L.length = 0; //初始化表的长度为0return OK;}

2.3 线性表L的销毁

void DeleteList(Sqlist &L){ // 参数用引用if(L.data) delete L.data; //销毁}

2.4 清空线性表

void ClearList(Sqlist &L){L.length = 0;
}

2.5 求线性表的长度

status Getlength(Sqlist L){return L.length;
}

2.5 判断线性表是否为空

status isEmpty(Sqlist L){if(L.length == 0) return OK;else return 0;
}

2.6根据位置找到元素的值

status Getdata(Sqlist &L , int i , ElemType &e){ // e 相当于得到那个元素并且返回if(i<1 || i>L.length) return ERROR;//判断i是否符合表长e = L.data[i-1];// 赋值给e，并且返回return OK;
}

2.7顺序表的查找

status LocateData (Sqlist L , ElemType e){for (i=0;i<L.length;i++)if(e == L.data[i])return i+1;return 0;//如果找到返回位置，未找到返回0；}

查找算法分析

O(n)

2.8 顺序表插入

status InsertData(Sqlist &L ,int i , ElemType e){if(i<1 || i>L.length+1) return ERROR; 未在指定范围中if(i >= list_max) return ERROR; 溢出for (j = L.length-1 ; j >= i-1 ; j--)L.data[j+1] = L.data[j];L.data[i-1] = e;return OK;
}

插入算法分析

O(n)

2.9 顺序表的删除

status DeleteData(Sqlist &L , int i){if(i<1 || i>L.length-1)return ERROR;for(j = i-1 ; j <= L.length-1 ; j++)L.data[j] = L.data[j+1];L.length--;return OK;
}

3 总结