文章目录
- 2.1 线性表的定义和基本操作
- 2.2 顺序表
- 2.2.1 顺序表的定义
- 2.2.2 顺序表的插入、删除(实现是基于静态分配)
- 2.2.3 顺序表的查找
- 2.3 链表
- 2.3.1 单链表的定义
- 2.3.2 单链表的插入删除
- 2.3.3 单链表的查找
- 2.3.4 单链表的建立
- 2.3.4 双链表
- 2.3.5 循环链表
- 2.3.6 静态链表
- 2.3.7 顺序表和链表的对比
2.1 线性表的定义和基本操作
线性表
:是具有相同数据类型的 n ( n > = 0 ) n(n>=0) n(n>=0)个元素的有限序列,其中n为表长,当 n = 0 n=0 n=0时线性表是一个空表。若用L命名线性表,则其一般表示为
L = ( a 1 , a 2 , . . . , a i , a i + 1 , . . . , a n ) L=(a_1,a_2,...,a_i,a_{i+1},...,a_n) L=(a1,a2,...,ai,ai+1,...,an)
- 相同的数据类型意味着每个元素所占的空间一样大
- a i a_i ai是表头元素: a n a_n an是表尾元素
- 除第一个元素外,每个元素有且仅有一个直接前驱;除最后一个元素外,每个元素有且仅有一个直接后继
线性表的基本操作
InitList(&L):初始化表。构造一个空的线性表L,分配内存空间。
DestroyList(&L):销毁线性表,并释放线性表L所占用的内存空间
ListInsert(&L,i,e):插入操作。在表L中的第i个位置上插入指定元素e
ListDelete(&L,i,&e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值
LocateElem(L,e):按值查找操作。在表L中查找具有给定关键字值得元素。
GetElem(L,i):按位查找操作。获取表L中第i个位置得元素得值。
其他常用操作:
Lengt h(L):求表长。返回线性表L得长度,即L中数据元素的个数。
PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L):判空操作。若L为空表,则返回true,否则返回false.
2.2 顺序表
2.2.1 顺序表的定义
顺序表
:用顺序存储的方式实现线性表。所谓顺序存储,把逻辑上相邻的元素存储在物理上也相邻的存储单元中,元素之间的关系由存储单元的临界关系来体现。
顺序表的实现-静态分配
#define MaxSize 10 //定义最大长度
typedef struct {ElemType data[MaxSize]; //用静态的数组存放数据元素int length; //顺序表的当前长度
}SqList;
实现
#include <bits/stdc++.h>using namespace std;
#define MaxSize 10
typedef struct {int data[MaxSize]; //用静态的数组存放数据元素int length; //顺序表的当前长度
}SqList;void InitList(SqList &L){for(int i=0; i<MaxSize; i++){L.data[i]=0; //将所有数据元素设置为默认初始值}L.length=0; //顺序表初始长度为0
}int main() {SqList L; //生命一个顺序表InitList(L);return 0;
}
顺序表的实现-动态分配
#define InitSize 10
typedef struct {ElemType *data; //指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义(动态分配方式)
c语言中提供了malloc和free函数动态申请和释放内存空间
#include <bits/stdc++.h>using namespace std;
#define InitSize 10
typedef struct {int *data; //指示动态分配数组的指针int MaxSize; //顺序表的最大容量int length; //顺序表的当前长度
}SeqList; //顺序表的类型定义(动态分配方式)void InitList(SeqList &L){L.data=(int*)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;
}//增加动态数组的长度
void IncreaseSize(SeqList &L, int len){int *p=L.data;L.data=(int *) malloc((L.MaxSize+len)*sizeof(int));for(int i=0; i<L.length; ++i){L.data[i]=p[i]; //将数据复制到新区域}L.MaxSize=L.MaxSize+len; //顺序表最大长度增加lenfree(p);
}int main() {SeqList L; //声明一个顺序表InitList(L); //初始化顺序表cout<<L.MaxSize<<'\n';IncreaseSize(L,5);cout<<L.MaxSize<<'\n';return 0;
}
顺序表的特点
- 随机访:即可以在 O ( 1 ) O(1) O(1)时间内找到第i个元素
- 存储密度高,每个节点只存储数据元素
- 拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
- 插入、删除操作不方便,需要移动大量元素
2.2.2 顺序表的插入、删除(实现是基于静态分配)
ListInsert(&L,i,e)
:插入操作。在表L中的第i个位置上插入指定元素e。
#include <bits/stdc++.h>using namespace std;
#define MaxSize 10
typedef struct {int data[MaxSize]; //用静态的数组存放数据元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(动态分配方式)void InitList(SqList &L){for(int i=0; i<MaxSize; i++){L.data[i]=0; //将所有数据元素设置为默认初始值}L.length=0; //顺序表初始长度为0
}void ListInsert(SqList &L, int i, int e){for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1];L.data[i-1]=e; //在位序i处放入eL.length++; //插入元素后长度增加1
}void Print(SqList L){for(int i=0; i<L.length; ++i) cout<<L.data[i]<<' ';cout<<'\n';}int main() {SqList L; //生命顺序表InitList(L);ListInsert(L,1,1);ListInsert(L,2,2);Print(L);ListInsert(L,3,3);Print(L);return 0;
}
更健壮的代码
考虑了插入位置是否合法,空间容量是否合法
bool ListInsert(SqList &L, int i, int e){if(i<1||i>L.length+1||L.length>=MaxSize) return false;for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1];L.data[i-1]=e; //在位序i处放入eL.length++; //插入元素后长度增加1return true;
}
插入操作的时间复杂度
关注最深层for循环语句执行的次数与问题规模n的关系
顺序表的删除
bool ListDelete(SqList &L, int i, int &e){if(i<1||i>L.length) return false; //判断i的位置是否合法e=L.data[i-1]; //回带删除元素的值for(int j=i; j<L.length; j++) L.data[j-1]=L.data[j]; //将第i个位置后的元素前移L.length--; //线性表当前长度加1return true;
}
egg
#include <bits/stdc++.h>using namespace std;
#define MaxSize 10
typedef struct {int data[MaxSize]; //用静态的数组存放数据元素int length; //顺序表的当前长度
}SqList; //顺序表的类型定义(动态分配方式)void InitList(SqList &L){for(int i=0; i<MaxSize; i++){L.data[i]=0; //将所有数据元素设置为默认初始值}L.length=0; //顺序表初始长度为0
}bool ListInsert(SqList &L, int i, int e){if(i<1||i>L.length+1||L.length>=MaxSize) return false;for(int j=L.length;j>=i;j--) L.data[j]=L.data[j-1];L.data[i-1]=e; //在位序i处放入eL.length++; //插入元素后长度增加1return true;
}bool ListDelete(SqList &L, int i, int &e){if(i<1||i>L.length) return false; //判断i的位置是否合法e=L.data[i-1]; //回带删除元素的值for(int j=i; j<L.length; j++) L.data[j-1]=L.data[j]; //将第i个位置后的元素前移L.length--; //线性表当前长度加1return true;
}void Print(SqList L){for(int i=0; i<L.length; ++i) cout<<L.data[i]<<' ';cout<<'\n';}int main() {SqList L; //生命顺序表InitList(L);ListInsert(L,1,1);ListInsert(L,2,2);ListInsert(L,3,3);Print(L);int e=0;ListDelete(L,3,e);cout<<"Delete element's value is "<<e<<'\n';Print(L);return 0;
}
删除操作的时间复杂度
2.2.3 顺序表的查找
查找有两种一种是按位茶盅,一种是按值查找
按位查找
int GetElem(SqList L, int i){return L.data[i-1];
}
按值查找
//按值查找,在顺序表L找查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SqList L, int e){for(int i=0; i<L.length; ++i){if(L.data[i]==e) return i+1; //数组下标为i的元素值等于e,返回其位序i+}return 0; //查找失败返回0
}
2.3 链表
关于链表的实现可以看这篇博客(侧重于实现)链表的实现
2.3.1 单链表的定义
typedef struct LNode{ //定义单链表的节点类型ElemType data; //每个节点存放一个数据元素struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;
不带头节点的单链表的初始化
bool InitList(LinkList &L){L=NULL; //空表,暂时还没有任何节点return true;
}void test(){LinkList L; //声明一个指向单链表的指针InitList(L);
}
带头结点的单链表
typedef struct LNode{ //定义单链表的节点类型int data; //每个节点存放一个数据元素struct LNode *next; //指针指向下一个节点
}LNode, *LinkList;bool InitList(LinkList &L){L=(LNode *) malloc(sizeof(LNode)); //分配一个头节点if(L==NULL) return false; //内存不足,分配失败L->next=NULL; //头节点之后暂时还有没节点return true;
}bool Empty(LinkList L){if(L->next==NULL) return true;else return false;
}void test(){LinkList L; //声明一个指向单链表的指针InitList(L);
}
2.3.2 单链表的插入删除
带头结点的插入
//在第i各位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, int e){if(i<1) return false;LNode *p; //指针p指向当前扫描到的节点int j=0;p=L; //L指向头节点,头节点是第0各节点(不存数据)while(p!=NULL&&j<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;return true;
}
不带头结点需要对第一个位置进行特殊处理
指定节点的后插操作
//后插操作,在p节点之后插入元素e
bool InsertNextNode(LNode *p, int 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;return true;
}
指定节点的前插操作(头天换日O(1))
//前插操作:在p节点之前插入元素e
bool InsertPriorNode(LNode *p, int e){if(p==NULL) return false;LNode *s = (LNode *) malloc(sizeof(LNode));if(s==NULL) return false; //内存分配失败s->next=p->next;p->next=s; //新节点s连到p之后s->data=p->data; //将p中元素复制到s中p->data=e; //p中元素覆盖为ereturn true;
}
按位序删除
bool ListDelete(LinkList &L, int i, int e){if(i<1) return false;LNode *p; //指针p指向当前扫描到的节点int j=0; //当前o指向的是第几个节点p=L; //L指向头节点,头节点是第0个节点while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL) return false; //i值不合法if(p->next==NULL) return false; //第i-1个节点之后已经无其他节点LNode *q=p->next; //q指向被删除节点e=q->data; //用e返回元素的值p->next=q->next; //将*q节点从链中断开free(q); //释放节点的存储空间return true;
}
删除指定节点
//删除指定节点p
bool DeleteNode(LNode *p){if(p==NULL) return false;LNode *q=p->next;p->data=p->next->data;p->next=q->next;free(q);return true;
}
上面代码是有bug的,当是最后一个结点的是偶p->next->data这个会出错,因为p->next=NULL
2.3.3 单链表的查找
按位序查找
//按位查找,返回第i个元素(带头结点)
LNode *GetElem(LinkList L, int i){if(i<0) return NULL;LNode *p; //当指针p指向当前扫描到的结点int j=0; //当前p指向的是第几个结点p=L;while(p!=NULL&&j<i){//循环找到第i个结点p=p->next;j++;}return p;
}
按值查找
//按值查找,找到数据域==e的结点
LNode * LocateElem(LinkList L, int e){LNode *p=L->next;while(p!=NULL&&p->data!=e) p=p->next;return p; //找到后返回该结点指针,否则返回NULL;
}
2.3.4 单链表的建立
尾插法可以设置一个变量length记录当前链表的长度,然后调用之前的按位序插入函数这样的话时间复杂度是 O ( n 2 ) O(n^2) O(n2)的,因为每次我们都需要从头开始遍历这是没有必要的,我们可以用一个指针去指向最后一个结点
LinkList List_Tailnsert(LinkList &L){int x;L=(LinkList) malloc(sizeof(LNode)); //建立头节点LNode *s,*r=L; //r为表尾指针scanf("%d",&x); //输入结点的值while(x!=9999){//输入9999表示结束s=(LNode *) malloc(sizeof(LNode));s->data=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL; //尾结点指针置空return L;
}
头插法
//头插法
LinkList List_HeadInsert(LinkList &L){//逆向建立单链表LNode *s;int x;L=(LinkList) malloc(sizeof (LNode)); //创建头节点L->next=NULL; //初始化空链表scanf("%d",&x);while(x!=9999){//输入9999表示结束s=(LNode *) malloc(sizeof(LNode));s->data=x;s->next=L->next;L->next=s; //将新节点插入到表中,L为头指针scanf("%d",&x);}return L;
}
头插法可以实现链表的逆置
2.3.4 双链表
双链表的定义
typedef struct DNode{int data;struct DNode *prior, *next; //前驱和后继
}DNode, *DLinklist;
双链表的初始化
bool InitDLinkList(DLinklist &L){L=(DNode *) malloc(sizeof(DNode)); //分配一个头节点if(L==NULL) return false; //内存不足,分配失败L->prior=NULL; //头节点的prior永远指向NULLL->next=NULL; //头节点之后暂时还没有结点return true;
}
双链表的插入
//在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){if(p==NULL||s==NULL) return false; //非法参数s->next=p->next;//如果p有后继结点if(p->next!=NULL) p->next->prior=s;s->prior=p;p->next=s;return true;
}
双链表的删除
bool DeleteNextDNode(DNode *p){if(p==NULL) return false;DNode *q=p->next; //找到p的后继节点qif(q==NULL) return false; //p没有结点p->next=q->next;if(q->next!=NULL) q->next->prior=p;free(q);return true;
}
2.3.5 循环链表
循环单链表
初始化循环单链表
//初始化一个循环单链表
bool InitList(LinkList &L){L=(LNode *) malloc(sizeof (LNode));if(L==NULL) return false;L->next=L; //头节点next指向头结点return true;
}
判空
//判断循环单链表是否为空
bool Empty_(LinkList L){if(L->next==L) return true;else return false;
}
循环单链表可以从任意结点出发找到任何单链表中的结点
循环双链表
循环双链表的初始化
//初始化空的循环双链表
bool InitDLinkList_(DLinklist &L){L=(DNode*) malloc(sizeof (DNode));if(L==NULL) return false;L->prior=L; //头节点的prior指向头节点L->next=L; //头节点的next指向头节点return true;
}
判空的和循环单链表一样
//判断结点p是否为循环双链表的表尾结点
bool isTaol(DLinklist L, DNode *p){if(p->next==L) return true;else return false;
}
双链表的插入
//在p结点之后插入s结点
bool InsertDNode_(DNode *p, DNode *s){s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;
}
2.3.6 静态链表
参考现实博客