2.1定义和基本操作
指具有相同数据类型的n个数据元素的有限序列,n为表长,n=0表示空表
特点:元素有限、具有逻辑顺序性、都是逻辑元素、占有相同大小存储空间
基本操作:
2.2顺序表示
1、用顺序存储实现的线性表叫顺序表,用一组地址连续的存储空间依次存储数据元素
数组空间分配:静态分配和动态分配
静态分配
如果没有设置数据元素的默认值,内存中有脏数据,可以有奇怪数据
动态分配
特点:
随机访问,存储密度高,每个节点只存储数据元素;逻辑上相邻物理上也相邻,但插入删除时需要移动大量元素
2、顺序表操作(删除插入查找)
插入:
由于元素的物理地址相邻,所以插入需要整体移动
最好情况:在表尾插入,后移语句不执行,时间复杂度为o(1)
最坏情况:在表头插入,后移语句执行n次,时间复杂度为o(n)
平均情况:平均移动次数为n/2,时间复杂度为o(n)
删除
由于元素的物理地址相邻,所以删除需要整体移动
最好情况:删除表尾元素,后移语句不执行,时间复杂度为o(1)
最坏情况:删除表头元素,前移语句执行n次,时间复杂度为o(n)
平均情况:平均移动次数为n-1/2,时间复杂度为o(n)
查找
按位查找:获取表中第i个位置元素的值
按值查找:获取表中具有给定关键字值的元素
2.3.1链式表示(单链表)
1、单链表定义
指通过一组任意的存储单元来存储线性表中的数据元素
优点-不需要使用大量连续的地质单元,插入删除不需移动元素,只修改指针;缺点-失去顺序存储随机存储的特点
2、插入删除
实现方式:(按位序插入)带头结点;不带头结点;指定节点的后插前插;
1.1带头结点空表判断:L==NULL
带头结点按位序插入:
typedef struct lnode{ //定义单链表节点类型
ElemType data;//数据域
struct lnode *next;//指针域
}lnode, *linkList;
bool listInsert(linkList &l,int i,ElemType e){
if(i<1)return false;
lnode *p;//指针p指向当前的点
int j=0;//p指向的是第几个节点
p=l;//l指向头结点,头结点是第0个
while(p!=null&&jnext;
j++;
}
if(p==null)return false;
lnode *s=(lnode *)malloc(sizeof(lnode));
s->data=e;
s->next=p->next;
p->next=s;//将s连到p之后
return true;
}
1.2不带头结点空表判断:L→NEXT==NULL
不带头结点的按位插入
typedef struct lnode{ //定义单链表节点类型
ElemType data;//数据域
struct lnode *next;//指针域
}lnode, *linkList;
bool listInsert(linkList &l,int i,ElemType e){
if(i<1)return false;
if(i==1){
lnode *s=(lnode *)malloc(sizeof(lnode));
s->data=e;
s->next=l;
l=s;//将s连到l之后
return true;
}
lnode *p;//指针p指向当前的点
int j=0;//p指向的是第几个节点
p=l;//l指向第一个节点
while(p!=null&&jnext;
j++;
}
if(p==null)return false;
lnode *s=(lnode *)malloc(sizeof(lnode));
s->data=e;
s->next=p->next;
p->next=s;//将s连到p之后
return true;
}
指定结点的后插
typedef struct lnode{ //定义单链表节点类型
ElemType data;//数据域
struct lnode *next;//指针域
}lnode, *linkList;
//在第i个位置插入e(带头结点)
bool listInsert(linkList &l,int i,ElemType e){
if(i<1)return false;
lnode *p;//指针p指向当前的点
int j=0;//p指向的是第几个节点
p=l;//l指向头结点,头结点是第0个
while(p!=null&&jnext;
j++;
}
if(p==null)return false;
lnode *s=(lnode *)malloc(sizeof(lnode));
s->data=e;
s->next=p->next;
p->next=s;//将s连到p之后
return true;
}
//指定节点后插操作,在p后面插入e
bool listInsert(lnode *p,ElemType e){
if(p==null)return false;
lnode *s=(lnode *)malloc(sizeof(lnode));
if(s==null)return false;
s->data=e;
s->next=p->next;
p->next=s;//将s连到p之后
return true;
}
3、查找
按值查找
按位查找
4、建立(头插法和尾插法)
头插法
可以理解头插法对头结点的后插操作
应用:链表逆置
尾插法
特点是设置一个指向表尾节点的指针
2.3.2双链表
在单链表基础增加一个指向前驱的prior指针
查找方法和单链表方法相同;插入和删除不同,要注意不造成断链。
插入:
删除:
2.3.3循环链表
循环单链表
表中最后一个节点的指针不是null,而是指向头结点。
判空条件是头结点的指针是否等于头指针;
从尾节点找头结点时间复杂度o(1);从头节点找尾结点时间复杂度o(n);
循环双链表
表中最后一个节点的指针不是null,而是指向头结点。此外,头结点的prior指针还指向尾节点。
判空条件是头结点的prior指针、next指针都等于L;
2.3.4静态链表
借助数组来描述,结点也有数据域和指针域,与前面不同,这里的指针是结点的相对地址(又称光标),静态链表和顺序表一样需要大量连续空间。以next==-1为结束标志。