【数据结构之线性表】

2.1定义和基本操作

• 2.1定义和基本操作

  指具有相同数据类型的n个数据元素的有限序列，n为表长，n=0表示空表

  特点：元素有限、具有逻辑顺序性、都是逻辑元素、占有相同大小存储空间

  基本操作：

2.2顺序表示

• 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链式表示

• 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&&j<i-1){
//循环找到第i-1个节点
p=p->next;
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&&j<i-1){
//循环找到第i-1个节点
p=p->next;
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&&j<i-1){
//循环找到第i-1个节点
p=p->next;
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为结束标志。