数据结构基础| 线性表

线性表

定义

没有元素则为空表

例子:

稀疏多项式的运算

图书信息管理系统

特点

线性结构

同类型

线性表的类型定义

1.基本操作:

InitList(&L)
操作结果:构造空的线性表L

DestroyList(&L)
初始化条件:线性表L存在
操作结果:销毁线性表L(线性表L不存在)

ClearList(&L)
初始化条件:线性表L存在
操作结果:将线性表L重置为空表(线性表L存在)

ListEmpty(L)
初始化条件:线性表L存在
操作结果:如果线性表为空表,则返回Ture,否则返回False

GetElem(L,i,&e) 返回线性表中第i个元素的值存储在e中

LocateElem(L,e,compare())
compare()判定条件返回第一个元素 没有返回0

PriorElem(L,cur_e,&pre_e)

NextElem(L,cur_e,&next_e)

ListTraverse(&L,visited())
依次对线性表中每个元素调用visited()遍历

线性表的顺序表示和实现

顺序存储的定义

线性表中相邻元素存储地址也相邻(与数组类似)

不同:

线性表长度可变,数组长度不可动态定义

#define LIST INIT SIZE 100
typedef struct{ElemType elem[LIST_INIT_SIZE];//ElemType可以变成我们需要的类型int length;//当前长度
}SqList;

例子:

一个函数的表示

#sefine MAXSIZE 1000 //多项式可以达到的最大长度typedef struct {      //多项式非零项的定义float p;         //系数int e;           //指数
}Polynomial;   typedef struct{ Polynomial*elem;     //存储空间的基地址int length;          //多项式当前项的个数
}SqList;                //多项式顺序存储结构类型为SqList

顺序表的类型定义

数组静态分配

数组动态分配

SqList L;
L.date = (ElemType*)malloc(size(ElemType)*MaxxSize);

c中free§释放指针p所指变量的存储空间,即彻底删除一个变量

类型决定分配的空间

参数传递

实参与形参

参数传递的方式

• 传值方式
• 传地址

线性表与顺序表的存储表达

逻辑位序和物理位序相差1

算法预定义常量:

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1  
#define ERROR 0
#define INFASLBLE -1
#define OVERFLOW -2
//Status 是函数的类型,其值是函数结果状态代码
typedef int Status;
typedef char ElemType;

算法

线性表L初始化(参数引用)

Status InitList_Sq(SqList&L){        //构造一个空的顺序表L.elem = new ElemType[MAXSIZE];  //为顺序表分配空间if(!L.elem)exit(OVERFLOW);       //存储分配失败异常处理对错误要提前处理防止后面出错导致程序崩溃L.length = 0;                    //空表长度为0return OK;
}

求线性表L的长度

判断线性表L是否为空

顺序表取值(随机存取)(按值查找)

顺序表的插入(小心溢出length判断,插入范围)

Status ListInsert_Sq(SqList &L,int i,ElemType e){if(i<1||i>L.length+1) return ERROR;  //i值不合法if(L.length==MAXSIZE) return ERROR;  //当前存储空间已满for(j=L.length-1;j>=i;j--)   L.elem[j+1]=L.elem[j];       //插入位置及之后的元素后移L.elem[i-1]=e;                   //将新元素e放入第i个位置L.length++;                      //表长加1return OK;
}

线性表删除算法(在执行前要进行异常判断)

小结

线性表访问每个元素的时间是相等的