second.分类笔记 线性表
定义：线性表具有相同数据类型的n（n>0）个数据元素的有限序列。n为表长。n=0表示此表为空表。
基本操作：初始化表：构造空表L，分配内存空间。? ? ? ? InitList(&L)
? ? ? ? ? ? ? ? ? 销毁操作：销毁线性表，释放表L占用的空间。? ? ? ? DestroyList(&L)
? ? ? ? ? ? ? ? ? 插入操作：在表的第i个位置上插入指定元素e。? ? ? ? ListInsert&(L,i,e)
? ? ? ? ? ? ? ? ? 删除操作：删除表的第i个位置的元素，并用e返回被删元素值。ListDelete(&L,i,e)
? ? ? ? ? ? ? ? ? 按值查找操作：在表中查找给定关键字值的元素。? ? ? ? LocateElem(&L,e)
? ? ? ? ? ? ? ? ? 按位查找操作：获取表中第i个位置元素的值。? ? ? ? GetElem(&L,i)
? ? ? ? ? ? ? ? ? ···············（综合即为 增删改查）
one.顺序表
定义：用顺序储存的方式实现线性顺序储存。把逻辑上相邻的元素储存在位置上也相邻的存储单元中。
实现方式：静态分配
例：
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 10
//定义最大长度（由于是静态数组的最大长度，因此，若数组存储满了，则不可更改了）
typedef struct{
int data[MaxSize];//用静态数组存放数据
int length;//顺序表当前长度
}SqList; //顺序表类型定义
//初始化顺序表
void InitList(Sqlist &L){ //没有给数据设置默认值，则内存会遗留一些奇怪的数据
L.length=0; //初始化长度为0
}
int main(int argc, char *argv[]) {
SqList L; //声明一个顺序表
InitList(L); //初始化顺序表
return 0;
}动态分配：
#include <stdio.h>
#include <stdlib.h>
#define InitSize 10 //顺序表初始长度 ，动态分配数组
typedef struct{
int *data; //只是动态分配数组的指针
int MaxSize; //顺序表最大容量
int length;//顺序表当前长度
}SqList; //顺序表类型定义（动态）
/* c语言中 有两个函数，malloc和free函数
malloc 会申请一整片连续的存储空间 ，需要返回一个指针，强制转换类型
例：L.data=(Elem Type*)malloc(sizeof(Elem Type)*InitSize);
*/
//初始化顺序表
void InitList(Sqlist &L){ //没有给数据设置默认值，则内存会遗留一些奇怪的数据
L.data=(int *)malloc(InitSize*sizeof(int));//用malloc函数申请一片连续的存储空间
L.length=0; //初始化长度为0
L.MaxSize=InitSize;
}
void IncreaseSize(SeqList &L,int len){
int *p=L.data;
L.data=(int *)malloc((L.MaxSize+len)*sizeof(int));
for(int i=0; i<L.length;i++){
L.data[i]=p[i]; //将数据复制到新区域
}
L.MaxSize=L.MaxSize+len; //顺序表最大长度加len
free(p); //释放原来的内存空间
}
int main(int argc, char *argv[]) {
SqList L; //声明一个顺序表
InitList(L); //初始化顺序表
//往顺序表中插入几个元素
IncreaseSize(L,5);
return 0;
}懒······就看了这么多，下次再继续改·····