链表:通过一组任意的存储单元来存储线性表中的数据元素

LinkList表示单链表

有时为了操作方便,在单链表的第一个节点之前附加一个节点,称为头节点。头节点的数据域可以存储标题、表长等信息,也可以不存储任何信息,其指针域存储第一个节点的首地址。头指针变量定义:LinkList H;

p = (LinkList)malloc(sizeof(LNode));

表示申请一块LNode类型的存储单元的操作,并将其地址赋值给变量p;free(p)表示释放指针p指向的节点空间。

单链表的建立有两种方法:1.在头部插入节点。2.在尾部插入节点。

头插法:在链表的头部插入节点建立单链表,简称“头插法”。建立思想:首先申请一个头节点,并且将头节点指针域置空(NULL);然后每读入一个数据元素则用molloc函数申请一个节点,并插在链表的头节点之后。

完整算法:

尾插法:在单链表的尾部插入节点建立单链表,简称“尾插法”。由于每次是将新节点插入到链表的尾部,所以增加一个指针r来始终指向链表中的为节点,以便能够将新节点插入到链表的尾部。

完整算法

单链表存储结构描述

插入算法:

单链表的删除:

欲在带头结点的单链表L中删除第i个节点,则首先要通过计数方式找到第i-1个节点并使pre指向第i-1个节点,而后删除第i个节点并释放节点空间。

删除算法:

线性表的概念及运算

定义:线性表是由n个类型相同的数据元素a1,a2……an组成的有限序列

记作(a1,a2……ai,ai+1……an)

数据元素之间是一对一的关系,即每个数据元素最多有一个直接前驱和一个直接后继

逻辑结构图

线性表的特点:

1.同一性:线性表由同类数据元素组成,每一个ai必须属于同一数据对象

2.有穷性:线性表由有限个数据元素组成,表长度就是表中数据元素的个数

3.有序性:线性表中相邻数据元素之间存在着序偶关系<ai,ai+1>

线性表的顺序存储

定义:是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中。

采用顺序存储结构的线性表通常称为顺序表。

假设线性表中每个元素占k个单元,第一个元素的地址为loc(a1),则第i个元素的地址为:loc(ai)=loc(ai)+(i-1)*k

基本运算:1.查找操作 2.插入操作 3.删除操作

1.查找操作:按序号查找GetData(L,i): 要求查找线性表L中第i个数据元素,其结果是L.elem[i]。

(1).按内容查找Locate(L,x): 要求查找线性表L中给定值x相等的数据元素,其结果是:若在表L中找到与x相等的元素,则返回该元素在表中的序号;若找不到,则返回一个“空序号”,如-1.

int Locate(SeqList L,ElemType x){
int i;
while(i<=L.length)&&(L.elem[i]!=x)
i++;
if(i<=L.length) return(i);
else return(-1);
}

2.插入操作:是指在表的第i(1<=i<=n+1)个位置,插入一个新元素e,使长度为n的线性表(e1,……ei-1,ei……en)变成长度为n+1的线性表(e1,……ei-1,X,ei……en)

3.删除操作:是指将表的第i(1<=i<=n)个元素删去,是长度为n的线性表 (e1,……ei-1,ei,ei+1……en) ,变成长度为n-1的线性表 (e1,……ei-1,ei+1……en)

线性表的顺序存储优缺点

优点

1.用数据存储元素,操作方法简单,容易实现

2.无须为表示节点间的逻辑关系而增加额外的存储开销。

3.存储密度高。

4.顺序表可按元素位序随机存取节点。

缺点

1.插入或删除运算不方便,除表尾的位置外,在表的其他位置上进行插入或删除操作都必须移动大量的节点,其效率较低;

2.由于顺序表要求占用连续的存储空间,存储分配只能预先进行静态分配。因此当表长变化较大时,难以确定合适的存储规模。