第二章 线性表
目录
2.1 线性表的类型定义（逻辑结构）
线性表的概念：具有相同特性的数据元素的一个有限序列
关于线性表的概念性描述：
- 数据的逻辑结构是指数据元素之间的逻辑结构，是用户按使用需要建立的
- 线性表的逻辑结构定义是唯一的，不依赖于计算机
- 线性结构反映节点间的逻辑关系是一对一的
- 一维向量是线性表，二维或N维数组依旧是
2.2 线性表的顺序表示和实现（存储结构）
2.2.1 顺序表的表示：
顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构
顺序存储方法：用一组连续地址的存储单元依次存储线性表的元素
线性表的顺序存储特点：
- 逻辑上相邻的数据元素其物理上也相邻
- 若已知表中首元素在存储器中的位置，则其他元素的存放位置亦可求出
“顺序表是一种随机存取的存储结构”——含义：在顺序表这样的存储结构上进行查找操作，其时间性能为O（1）
存储结构与存取结构是两种不同的概念：
- 存储结构是数据及其逻辑结构在计算机中的表示
- 存取结构实在某种数据结构上对查找操作的时间性能的描述（如随机存取或顺序存取）
2.2.2 顺序表的实现：
#include<iostream>
#include<stdlib.h>
using namespace std;
//宏常量定义链表长度
#define LISST_INIT_SIZE 100
//宏常量定义链表增长量
#define LISTINCREMENT 10
typedef int ElemType;
typedef int Status;
//定义线性表
typedef struct{
int* elem; //定义存储基址
int length; //当前顺序表长度
int listsize; //当前的分配大小
}SqList;
//封装菜单函数
void menu(){
cout<<"---- 1.初始化链表 ---------------"<<endl;
cout<<"---- 2.销毁链表 -----------------"<<endl;
cout<<"---- 3.清空链表 -----------------"<<endl;
cout<<"---- 4.判断链表是否为空 ---------"<<endl;
cout<<"---- 5.求链表长度 ---------------"<<endl;
cout<<"---- 6.获取链表中指定位置元素 ---" <<endl;
cout<<"---- 7.获取链表元素位置 ---------"<<endl;
cout<<"---- 8.前驱 ---------------------"<<endl;
cout<<"---- 9.后继 ---------------------"<<endl;
cout<<"---- 10.在链表指定位置插入元素 --"<<endl;
cout<<"---- 11.删除链表指定位置元素 ----"<<endl;
cout<<"---- 12.显示链表 ----------------"<<endl;
cout<<"---- 13.合并两个非递减有序的链表 "<<endl;
cout<<"---- 14.退出（输入一个负数） ----"<<endl;
cout<<"--> 请选出你的选择"<<endl;
}
//初始化构建
void IntList(SqList &L){
L.elem=(ElemType *)malloc(LISST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)
{
cout<<"链表初始化失败"<<endl;
}
L.length=0;
L.listsize=LISST_INIT_SIZE;
if(L.elem){
cout<<"链表初始化成功"<<endl;
}
}
//销毁线性表
void DestoryList(SqList &L){
free(L.elem);
L.elem=NULL;
cout<<"销毁链表成功"<<endl;
}
//清空链表
void ClearList(SqList &L){
if(!L.elem)
{
cout<<"链表未初始化！"<<endl;
}
else{
L.length=0;
cout<<"清空成功"<<endl;
}
}
void Kong(SqList &L){
if(L.length==0){
cout<<"该线性表长度为空"<<endl;
}
else cout<<"该线性表长度不为空，它的长度为"<<L.length<<endl;
}
void Length(SqList &L){
cout<<"该线性表长度为"<<L.length<<endl;
}
void GetElem(SqList &L,int i){
if(i<1||i>L.length){
cout<<"此位置非法，无法访问"<<endl;
}
else
cout<<"第"<<i<<"个位置的元素为"<<L.elem[i-1];
}
void Locate(SqList &L,int e){
int i,note1=0,note2=0;
for(i=0;i<L.length;i++){
if(e==L.elem[i]){
cout<<"该元素位置是"<<i+1<<endl;
note1=1;
}
else note2=2;
}
if(note1==0&¬e2==0){
cout<<"未查找到该元素"<<endl;
}
}
int Qianqu(SqList &L,int e){
int i;
for(i=0;i<L.length;i++){
if(e==L.elem[i]){
return L.elem[i-1];
}
}
return 0;
}
int Houji(SqList &L,int e){
int i;
for(i=0;i<L.length;i++){
if(e==L.elem[i]){
return L.elem[i+1];
}
}
return 0;
}
void Insert(SqList &L,int e,int i){
if(i<1||i>L.length+1){
cout<<"插入失败"<<endl;
}
else if(L.length==L.listsize){
cout<<"链表已满"<<endl;
}
else{
for(int j=i-1;j<L.length+1;j++){
L.elem[j+1]=L.elem[j];
}
L.length++;
L.elem[i-1]=e;
cout<<"插入成功"<<endl;
}
}
void shanchu(SqList &L,int i){
if(i<1||i>L.length){
cout<<"删除失败"<<endl;
}
else{
for(int j=i-1;j<L.length;j++){
L.elem[j]=L.elem[j+1];
}
L.length--;
cout<<"删除成功"<<endl;
}
}
void show(SqList &L){
cout<<"该线性表元素为";
for(int i=0;i<L.length;i++){
cout<<L.elem[i]<<" ";
}
}
//封装合并两个线性表的函数
void Combine(SqList &L1,SqList &L2,SqList &L3){
int i=0;
int j=0;
int k=0;
int a,b;
int length1=L1.length,length2=L2.length;
while(i<length1&&j<length2){
a=L1.elem[i];
b=L2.elem[j];
if(a<b){
L3.elem[k]=a;
L3.length++;
k++;
i++;
}
else if(a==b){
L3.elem[k]=a;
k++;
i++;
j++;
L3.length++;
}
else{
L3.elem[k]=b;
L3.length++;
k++;
j++;
}
}
while(i<length1){
a=L1.elem[i];
L3.elem[k]=a;
L3.length++;
k++;
i++;
}
while(j<length2){
b=L2.elem[j];
L3.elem[k]=b;
L3.length++;
k++;
j++;
}
show(L3);
}
int main(){
int a,i,e;
SqList L;
SqList L1;
SqList L2;
SqList L3;
while(1){
system("cls");
menu();
cin>>a;
switch(a){
//创建链表
case 1:IntList(L);
system("pause");
break;
//销毁链表
case 2:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else{
DestoryList(L);
}
system("pause");
break;
//清空链表
case 3:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else
{
ClearList(L);
}
system("pause");
break;
//判断链表是否为空
case 4:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else{
Kong(L);
}
system("pause");
break;
//输出链表长度
case 5:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else{
Length(L);
}
system("pause");
break;
//获取链表中指定元素的位置
case 6:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else{
cout<<"请输入你想查找的元素位置"<<endl;
cin>>i;
GetElem(L,i);
}
system("pause");
break;
//获取指定元素在链表中的位置
case 7:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else{
cout<<"请输入你想查询的元素"<<endl;
cin>>e;
Locate(L,e);
}
system("pause");
break;
//获取指定元素的前驱
case 8:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else{
cout<<"请输入元素"<<endl;
cin>>e;
int a = Qianqu(L,e);
if(a==0){
cout<<"元素不存在！"<<endl;
}else{
cout<<"该元素的前驱是"<<a<<endl;
}
}
system("pause");
break;
//获取指定元素的后继
case 9:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else{
cout<<"请输入元素"<<endl;
cin>>e;
int b = Houji(L,e);
if(b==0){
cout<<"元素不存在！"<<endl;
}
else{
cout<<"该元素的后继是"<<b<<endl;
}
}
system("pause");
break;
//在链表指定位置插入元素
case 10:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else{
cout<<"请输入你想插入的元素"<<endl;
cin>>e;
cout<<"请输入你想插入元素位置"<<endl;
cin>>i;
Insert(L,e,i);}
system("pause");
break;
//删除链表指定位置元素
case 11:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else{
cout<<"请输入你想删除的位置"<<endl;
cin>>i;
shanchu(L,i);
}
system("pause");
break;
//显示链表
case 12:
if(!L.elem)
{
cout<<"请先初始化链表"<<endl;
}
else
{
show(L);
}
system("pause");
break;
//合并两个非递减有序的链表
case 13:
IntList(L1);
IntList(L2);
IntList(L3);
cout<<"请输入第一个链表的长度"<<endl;
cin>> L1.length;
cout<<"请输入第一个链表的元素"<<endl;
for(i=0;i<L1.length;i++){
cin>>L1.elem[i];
}
cout<<"请输入第二个链表的长度"<<endl;
cin>>L2.length;
cout<<"请输入第二个链表的元素"<<endl;
for(i=0;i<L2.length;i++){
cin>>L2.elem[i];
}
Combine(L1,L2,L3);
system("pause");
break;
}
}
}
2.2.3 顺序表的运算效率分析：
时间效率分析：算法时间主要消耗在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）T（n） = O（移动元素次数）
移动元素的个数取决于插入或删除元素的位置
- 若在长度为n的线性表的i位置前插入元素，则向后移动的元素次数为：f(n)=n-i+1
- 若在长度为n的线性表的i位置删除元素，则向前移动的元素次数为：f(n)=n-i
假定在表中任意位置插入、删除元素都是等概率的，插入概率p(i) = 1/(n+1)，删除概率p(i) = 1/n，则：
插入操作时间效率（平均移动次数）：n/2
删除操作时间效率（平均移动次数）：(n-1)/2
因此时间复杂度T（n） = O（n）
顺序表的空间复杂度S（n） = O（1）
2.3 线性表的链式表示和实现（存储结构）
2.3.1 链表的表示
链式存储特点：逻辑上相邻，物理上不一定相邻
- 每个存储结点都包含两个部分：数据域和指针域（链域）
- 在单链表中，首结点除外，任一结点的存储位置由其直接前驱的链域的值指示
- 结点只有一个指针域的链表是单链表
- 有两个指针域的链表是双链表
- 首尾相联结的链表是循环链表
头指针、头结点与首元结点：
头指针 是指向链表第一个结点的指针（或为 头结点/首元结点 的指针）
首元结点 是指链表中存储线性表第一个数据元素的结点
头结点 是在链表的首元结点之前附设的一个结点，数据域内只存放空表标志和表长信息
问题一：如何表示空表
无头结点时，当头指针的值为空时表示空表
有头结点时，当头结点的指针域为空时表示空表
问题二：在链表中设置头结点有什么样的好处
头结点即在链表的首元结点之前附设的一个结点，该节点的数据域中不存储数据元素，无论链表是否为空，头指针总是为空，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对寿元结点进行统一处理
- 对于带头结点的链表，在表的任何结点之前插入节点或删除结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点，若没有头结点，即首元结点无前驱结点，操作会变得复杂
- 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。这样就可以区分空链表和空指针，也减小了程序的复杂性和出现bug的机会
例如:在进行删除操作时，L为头指针，p指针指向被删结点，q指针指向被删结点的前驱，对于非空的单链表:
1.带头结点时
删除第1个结点(q指向的是头结点):q->next=p->next;
free§;
删除第i个结点(i不等于1):q->next=p->next;free§;
2.不带头结点时
删除第1个结点时(q为空):L=p->next; free§;
删除第i个结点(i不等于1):q->next=p->next;free§;
带头结点时，不论删除哪个位置上的结点，用到的代码都一样;不带头结点时，删除第1个元素和删除其它位置上的元素用到的代码不同，相对比较麻烦
2.3.2 链表的实现
单链表的实现：
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(Stu)
using namespace std;
typedef struct student{
int data;
struct student *next;
}Stu;
//封装菜单函数
void Tips()
{
cout << "可执行操作有：" << endl;
cout << "*********************************************************" << endl;
cout << "*************** 1.初始化或重置链表 ****************" << endl;
cout << "*************** 2.销毁链表 ****************" << endl;
cout << "*************** 3.清空链表 ****************" << endl;
cout << "*************** 4.返回链表长度 ****************" << endl;
cout << "*************** 5.指定位置的元素 ****************" << endl;
cout << "*************** 6.链表已存在元素的位序 ****************" << endl;
cout << "*************** 7.求输入元素的直接前驱 ****************" << endl;
cout << "*************** 8.求输入元素的直接后继 ****************" << endl;
cout << "*************** 9.在第i个位置插入一个元素 **************" << endl;
cout << "*************** 10.删除第i个元素 ****************" << endl;
cout << "*************** 11.输出有的链表元素 ****************" << endl;
cout << "*************** 12.初始化并用头插法（或尾插法）输入元素*" << endl;
cout << "*************** 13.实现单链表的逆序存放 ****************" << endl;
cout << "*********************************************************" << endl;
}
Stu* InitList(){
Stu *p;
p=(Stu*)malloc(LEN);
if(p==NULL){
cout<<"内存分配失败！"<<endl;
return 0;
}
//将尾结点指针指空，代表链表结束
p->next=NULL;
return p;
}
//销毁链表函数
void Destory(Stu* S){
Stu *p;
p=NULL;
while(S){
p=S;
S=S->next;
free(p);
}
}
//清空链表函数
int Clear(Stu *S){
Stu* p=S->next;
while(p!=NULL){
Stu * q=p->next;
delete p;
p=q;
}
S->next=NULL;
return 0;
}
//链表长度函数
int Length(Stu *S){
Stu *p;
int j=0;
p=S;
while(p->next){
j++;
p=p->next;
}
return j;
}
//插入元素函数
int Insert(Stu *S,int n,int e){
Stu *p,*s;
int j=0;
//插入元素：1.找到插入位置 2.申请插入结点的空间 3.改变两个指针的指向
p=(Stu*)malloc(LEN);
s=S;
while(s && j<n-1){
j++;
//找到元素位置并用j表示
s=s->next;
}
if(!s){
return -1;
}
if(p==NULL){
cout<<"申请内存空间失败！"<<endl;
}
p->data=e;
//改变两个指针的指向
p->next=s->next;
s->next=p;
return 0;
}
//显示链表元素函数
void Show(Stu *S,int l){
Stu* p;
p=S->next;
for(int i=1;i<=l;i++){
cout<<"第 "<<i<<" 个元素："<<p->data<<endl;
p=p->next;
}
}
//指定位置的元素
int GetElme(Stu *S,int n){
Stu *p;
p=S->next;
int j;
//寻找位序
while(p && j<n-1){
p=p->next;
j++;
}
return p->data;
}
//已存在元素的位序
int FindElme(Stu *S,int e){
Stu *p;
p=S->next;
int j=1;
//遍历链表元素
while(p->next){
if(p->data==e){
return j;
}else{
return -1;
}
p=p->next;
j++;
}
return 0;
}
//求指定元素的直接前驱
int QianQu(Stu *S,int e){
//求前驱和后继的方法：1.根据传入的元素，遍历链表，找到该元素结点的上一个结点的位置 2.输出这个结点的数据域
Stu *p;
p=S->next;
if(e==p->data){
return -1;
}
while(p->next){
p=p->next;
if(p->next->data==e){
return p->data;
}else{
return 0;
}
}
return 0;
}
//求指定元素的直接后继
int HouJi(Stu *S,int e){
Stu *p;
p=S->next;
if(!p->next){
return 0;
}
while(p->next){
if(p->data==e){
return p->next->data;
}else{
return -1;
}
p=p->next;
}
return -1;
}
//删除指定位置的元素
int Delete(Stu *S,int n){
//首先要找到指定位置的元素
Stu *p,*q;
p=S;
int j=0;
while(p->next && j<n-1){
j++;
p=p->next;
}
q=p->next;//用q储存p的下一个结点
p->next=q->next;//此时p指向原来的p的下一个的下一个
free(q);//再将q释放，即将原来的p的下一个删除了
return -1;
}
//链表元素的逆序存放
void NiXu(Stu *S){
Stu *p,*q;
p=S->next;
S->next=NULL; //头插法思想.
while(p!=NULL){ //用q和p来记录第一个和第二个节点.
q=p;
p=p->next;
q->next=S->next;
S->next=q;
}
int l = Length(S);
Show(S,l);
}
//封装主函数
int main(){
Stu *S=NULL;
while(true){
int n;
Tips();
cout<<"请输入服务编号："<<endl;
cin>>n;
switch(n){
case 1:{
S=InitList();
if(S){
cout<<"链表创建成功！"<<endl;
}
break;
}
case 2:{
if(!S){
cout<<"没有可销毁的链表！"<<endl;
}else{
Destory(S);
S=NULL;
cout<<"销毁链表成功！"<<endl;
}
break;
}
case 3:{
if(!S){
cout<<"没有可清空的链表！"<<endl;
}else{
if(Clear(S)==0){
cout<<"链表清空成功！"<<endl;
}
}
break;
}
case 4:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
int a=Length(S);
cout<<"链表长度为："<<a<<endl;
}
break;
}
case 5:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
cout<<"请输入元素位序：";
int n;cin>>n;
if(n>Length(S)){
cout<<"位置非法！"<<endl;
break;
}
int e=GetElme(S,n);
cout<<endl;
cout<<"该位序的元素："<<e<<endl;
}
break;
}
case 6:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
cout<<"请输入要查询位序的元素：";
int e;cin>>e;
cout<<endl;
int c = FindElme(S,e);
if(c==-1){
cout<<"鏈表中不存在該元素！"<<endl;
}
cout<<"该元素出现的位序："<<c<<endl;
}
break;
}
case 7:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
cout<<"请输入要查看其直接前驱的元素：";
int e;cin>>e;
cout<<endl;
int d = QianQu(S,e);
if(d==-1){
cout<<"链表的头结点没有直接前驱！"<<endl;
break;
}
else if(d==0){
cout<<"操作异常！可能查詢位置非法！"<<endl;
}else{
cout<<"该元素的直接前驱："<<d<<endl;
}
}
break;
}
case 8:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
cout<<"请输入要查看其直接后继的元素：";
int e;cin>>e;
cout<<endl;
int d = HouJi(S,e);
if(d==0){
cout<<"链表的尾结点没有直接后继！"<<endl;
break;
}else if(d==-1){
cout<<"操作异常！可能查詢位置非法！"<<endl;
}
else{
cout<<"该元素的直接后继："<<d<<endl;
}
}
break;
}
case 9:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
int a=Length(S);
cout<<"当前链表长度："<<a<<" 请选择要插入元素的位置：";
int n;cin>>n;cout<<endl;
if(n>Length(S)){
cout<<"插入位置非法！"<<endl;
break;
}
cout<<"请输入元素值：";
int e;cin>>e;
int b=Insert(S,n,e);
if(b==-1){
cout<<"元素插入失败！"<<endl;
}else{
cout<<"元素插入成功！"<<endl;
}
}
break;
}
case 10:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
int n;
cout<<"请输入要删除元素的位置：";
cin>>n;
if(n>Length(S)){
cout<<"插入位置非法！"<<endl;
break;
}
int a = Delete(S,n);
if(a==-1){
cout<<"删除成功！"<<endl;
}else{
cout<<"操作异常! "<<endl;
}
}
break;
}
case 11:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
cout<<"链表元素："<<endl;
int l = Length(S);
Show(S,l);
}
break;
}
case 12:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
cout<<"请输入初始元素数量：";
int m;cin>>m;
cout<<endl;
int start = Length(S) + 1;
for(int i=0;i<m;i++){
cout<<"请输入元素值：";
int e;cin>>e;
Insert(S,start+i,e);
}
cout<<"链表元素初始化成功！"<<endl;
}
break;
}
case 13:{
if(!S){
cout<<"请先创建链表！"<<endl;
}else{
cout<<"单链表的逆序存放结果："<<endl;
NiXu(S);
}
break;
}
}
system("pause");
system("cls");
}
}
循环链表：表中最后一个结点的指针域指向头结点，整个链表形成一个环
- 循环链表的实现无需增加存储量，仅对表的链接方式稍作改变，即可使表处理更加方便灵活，从任一结点出发均可找到表中其他结点
- 循环链表的操作与线性链表基本一致，差别在于算法中的循环条件不是o或p->next是否为空，而是它们是否等于头指针
双链表：结点有两个指针域，一个指向直接前驱，一个指向直接后继
- 克服了单链表的单向性（查询后继O（1），查询前驱O（n））的缺点
- 双向链表是由头指针head唯一决定的
- 双向链表进行插入和删除操作时必须同时修改两个方向的指针
2.3.3 链表的运算效率分析
时间效率分析：
- 查找：由于线性链表只能顺序存储，即在查找是要从头结点找起，查找的时间复杂度为O（n）
- 插入和删除：线性链表不需要移动元素，在给出合适位置的指针后，插入和删除操作所需的时间仅为O（1）
空间效率分析：
链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)
练习：
1.线性表的逻辑结构特点：只有一个首结点和尾结点，除首尾结点以外其他结点只有一个直接前驱和一个直接后继，简言之，线性结构反映结点间的逻辑关系是一对一的
2.线性表的顺序存储结构和链式存储结构的特点：
顺序存储时，逻辑上相邻的数据元素的存储地址也相邻（逻辑与物理统一）
链式存储时，逻辑上相邻的数据元素可以随意存放，下一个结点的数据域的存放地址由上一个结点的指针域的值所指示（每一个结点的存储空间分为两部分，一部分存放结点值，一部分存放表示结点间关系的指针）
3.顺序存储结构与链式存储结构的优缺点：
顺序存储结构的优点是密度大，存储空间利用率高，缺点是增删操作不便
链式存储结构的优点是增删操作方便，使用灵活，缺点是存储密度小，存储空间利用率低
（事实上链表增删运算的快慢是以空间代价来换取时间，存储密度=结点数据本身所占据的存储量/结点结构所占的存储总量）
4.静态链表中指针域中存储的是：下一元素在数组中的下标
5.在一个长度为n的单链表上，设有头尾两个指针，执行删除单链表最后一个元素链表的长度会发生改变
6.与单链表相比，双向链表的优点是：顺序访问相邻结点更加灵活
7.与单链表相比，循环链表的优点是：随机访问