【数据结构之线性表】熬夜暴肝,有亿点详细
前言
我们今天来学习线性表,线性表是数据结构中比较简单的一个数据结构了,但是它的重要性不容忽略,废话不多,直接正文。
目录
- 前言
- 初识线性表
-
- 线性表的定义
- 线性表的基本操作
- 顺序表
-
- 顺序表的定义
-
- 顺序表与数组
- 定义的实现
- 顺序表的基本操作
-
- 顺序表的插入
- 顺序表的删除
- 顺序表的查找
- 链表
-
- 单链表的定义
-
- 定义的实现
- 单链表的基本操作
-
- 创建单链表
- 单链表的查找
- 单链表的插入
- 单链表的删除
- 特殊链表
-
- 双链表
- 循环链表
- 静态链表
- 线性表的常用操作
-
- 最值
- 逆置
- 归并
- 顺序表与链表的比较及选择
- 结言
初识线性表
线性表的定义
线性表是具有相同类型的n(n>=0)个元素的有限序列,其中n为表长,当n=0时,该表为空表
线性表的特点:
1.表中元素个数有限
2.表中元素具有逻辑上的顺序性,在序列中各个元素排序有其先后次序
3.表中元素都是数据元素,每个元素都是单个元素
4.表中元素的数据类型都相同,这意味着每个元素占有相同大小的存储空间
5.表中元素具有抽象性,即讨论元素间一对一的逻辑关系,而不考虑元素究竟表示的内容
6.线性表是一种逻辑结构,表示元素之间一对一相邻的关系
7.线性表在数据元素有限集中,除第一个元素无直接前驱,最后一个元素无直接后续以外,每个数据元素有且仅有一个直接前驱元素和一个直接后继元素。
线性表的基本操作
还记得之前说过运算的定义依靠数据的逻辑结构实现,运算的实现针对于数据的存储结构吗?不过不记得你可以去看看数据结构入门篇
线性表是一种逻辑结构,因此具体操作我们是无法实现的,不过我们可以定义这些操作。
我们主要从参数,返回值来说一下基本操作吧
&L指传入一个引用,这个引用指向线性表表头
InitList(&L):
初始化表。构造一个空的线性表。
DestroyList(&L):
销毁操作。销毁线性表,并释放线性表L所占用的内存空间。 LocateElem(L,e):
按值查找操作。在表中L查找具有给定关键字值得元素。
GetELem(L,i):
按位查找操作。获取表L中第i个位置的元素的值。
ListInsert(&L,i,e):
插入操作。在表L中的第i个位置上插入指定元素e。
LIstDelete(&L,i,&e):
删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
PrintList(L):
输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L):
判空操作。若L为空表,则返回TRUE,否则返回FALSE。
Length(L):
求表长。返回线性表L的长度,即L中数据元素的个数。
以上就是线性表的对基本操作的定义,对这些操作的实现我们得依靠存储结构来说了。
线性表根据存储结构的不同又分为顺序表与链表,接下来我们就逐一说一下他们两个吧!
顺序表
顺序表就是线性表的顺序表示,它的主要特点是逻辑结构与存储结构相同都是连续的。
顺序表的定义
一组地址连续存放的存储单元依次存放线性表的元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻
这样一说会感觉这个和数组十分相似啊。的确十分相似,但是却有所不同,详见下文。
顺序表与数组
相同之处:数组与线性表相同都是一组地址连续存放的存储单元依次存放元素
不同之处:数组下标从0开始,而顺序表下标从1开始。数组有最大存储空间是静态的,而顺序表可以是动态的。
定义的实现
顺序表定义的实现有两种分别是静态分配和动态分配。它们的区别是使用静态分配时顺序表的容量是被规定好的,无法增加的。使用动态分配时顺序表的容量可以变大。
实现数组静态分配:
# define MaxSize 100;typedef struct{ElemType date[MaxSize];//ElemType是某种元素类型int length ;//顺序表长度}sqList;//顺序表名字
我们使用结构体实现顺序表的定义,这里使用了某种类型的数组存放某种数据,数组容量为常量MaxSize。
实现数组动态分配:
# define MaxSize 100;typedef struct{ElemType *date;int length;}sqList;
动态分配语句:
C: L.data = (Elemtype*)malloc(sizeof(ElemType)*InitSize);C++:L.data = new ElemType[InitSize]
顺序表的基本操作
顺序表的基本操作有插入,删除,查找
顺序表的插入
这个是给顺序表L在指定位置i处,插入元素e
bool ListInsert (SqList &L,int i,ElemType e){//除去不合法的i,保证不能空下一个位置//length+1是因为有可能最后一个位置插入if(i<1||i>L.length+1){return false;}if(i>=MaxSize){return false;}//每个元素向后移动给i-1下标位置空出来for(int j=L.length;j>=i;j--){L.date[j]=L.date[j-1];}L.date[i-1]=e;return true;}
顺序表的删除
传入要删除的位置和一个元素的引用来保存要删除元素的值
bool ListDelete(SqList &L,int i,ElemType &e){if(i<1||i>L.length){return false;}//保存要删除的元素e=L.date[i-1];//后面的元素向前逐个移动for(int j=i;j<L.length;j++){L.date[j-1]=L.date[j];}L.length--;return true;}
顺序表的查找
按值查找元素位置(位置从1开始)
int ListDelete(Sqlist L,ElemType e){int i;for(i=0;i<L.length;i++){if(L.date[i]==e)return i+1;}return 0;}
如果是按位置查找直接L.date[i-1]即可得位置为i处的值是多少。
链表
链表我们最常见的就是单链表,除此之外还有一些特殊链表,我们重点还是说说单链表。
单链表的定义
单链表是线性表的链式存储,通过一组任意的存储单元来存储线性表中的数据元素,通过指针来实现逻辑关系
定义的实现
单链表的每一块都分为数据域和指针域,指针域用来存放逻辑上下一块内存的地址
typedef struct LNode{ElemType date;struct LNode *next;}LNode,*LinkList;
链表又有两种,一种是有头结点的,一种是没有头结点的。我们为了提高效率一般使用带头结点的单链表,后面操作讲解也都是带头结点的链表。
头结点放在链表的最前面,结构与每一块结点相同,不过数据域中为空或者存放链表长度等重要元素,头结点的指针域指向链表的第一个元素。
使用头结点能帮助我们处理头部时方法与其他位置处理方法相同,操作时不需要判断是否为首元素了,大大提高了代码效率。
单链表的基本操作
单链表基本操作有:创建单链表,查找,插入和删除。
创建单链表
创建单链表我们分为头插法创建和尾插法创建,区别就是生成的链表顺序与插入时顺序是否相同。显然头插法创建单链表是顺序相同。
头插法
头插法就是每次插入元素时在链表的头结点后插入,最后生成的链表顺序与插入时顺序相反。
LinkList List_HeadInsert (LinkList &L){LNode *s;int x;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;scanf("%d",&x);while(x!=99999){s=(LNode*)malloc(sizeof(LNode));s->date=x;s->next=L->next;L->next=s;scanf("%d",&x);}return L;}
尾插法
尾插法就是每次插入元素时在链表的末尾插入元素,最后生成的链表顺序与插入时顺序相同。
LinkList List_HeadInsert (LinkList &L){LNode *s,*r;int x;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;*r=L;scanf("%d",&x);while(x!=99999){s=(LNode*)malloc(sizeof(LNode));s->date=x;r->next=s;r=s;scanf("%d",&x);}r->next=NULL;return L;}
单链表的查找
查找又根据需求分为按序查找和按值查找。
按序查找
如果查找时需要查找某个位置元素的结点,那么就是按序查找。传入的参数为一个链表和需要查找的位置。
LNode *GetElem(LinkList L,int i){int j=1;LNode *p=L->next;if(i==0)return L;if(i<1)return NULL;while(p&&j<i){p=p->next;j++;}return p;}
按值查找
如果需要在链表中查找某个值e的结点,则:
LNode *LocateElem(LinkList L,ElemType e){LNode *p=L->next;while(p!=NULL&&p->date!=e){p=p->next;}return p;}
单链表的插入
插入有两种,第一种是插入到指定位置,第二种是默认在链表头部插入
插入到指定位置
要求插入到i位置处时,需要先找到i-1处的结点,然后插入
p=GetElem(L,i-1);s->next=p->next;p->next=s;
默认插入头部
在链表头部插入元素时:
s->next=head;head=s;
单链表的删除
删除i位置的结点:
p=GetElem(L,i-1);q=p->next;p->next=q->next;free(q);
如果需要删除指定结点*q那么只需要:
q=p->next;p->date=p->next->date;p->next=q->next;free(q);
特殊链表
特殊链表有:双链表,循环链表和静态链表。
双链表
双链表顾名思义就是比单链表高级了一点,一个双链表的结点在单链表的基础上又增加了一个指针,这个指针指向它的前一个结点
结点情况如下:
指针域 | 数据域 | 指针域 |
---|---|---|
prior | date | next |
定义的实现:
typedef struct DNode{ElemType date;struct DNode *prior,*next;}DNode,*DLinklist;
结点发生改变了。对链表的一些操作也会发生改变
插入操作:
s->next=p->next;p->next->prior=s;s->prior=p;p->next=s;
删除操作:
p->next=q->next;q->next->prior=p;free(q);
循环链表
之前的链表都是条状的,循环链表是头尾相连了,就是将链表的尾部与头部连接起来。有因为条状链表有单链表与双链表之分,所以循环链表也有两种分别是:循环单链表与循环双链表
对于循环单链表我们一般设置尾指针这样操作效率会更高。
对于循环双链表我们头结点的prior结点指向最后一个节点,尾结点的next指针指向头结点,以形成循环双链表。
之前的链表我们判断是否为空表都是看最后一个结点的next结点是否为空。显然,循环链表不可以这样判断,我们判断方式如下:
循环单链表判断空链表条件:
if(L->next==L)
循环双链表判断空链表条件:
if(L->next==L&&L->prior==L)
静态链表
静态链表这个名字听起来高大上,其实也是非常简单的,它和数组是非常相似的。先来看它的结构组成:
#define MaxSize 50typedef struct DNode{ElemType date;int next;}SLinkList[MaxSize];
它其实就是一个数组只不过不连续而已,结点分为两部分。date域存放数据,而next域存放下一个存放数据的数组的下标。
使用数组下标索引实现了逻辑结构。
线性表的常用操作
到此为止我们已经学过了线性表按照存储结构不同的两种分类,分别是顺序表与链表,以及他们的一些基本操作。但是在我们以后在做题时候,不会直接来考插入,删除等操作,它们都是贯穿在很多的大的操作中去的,我愿把他们称为非基本操作。。
下面我们来讲一下对于线性表的一些常考的操作分别是:最值,逆置,归并
最值
最值顾名思义就是求出线性表中的最大以及最小值,我们分别用顺序表与链表实现。
顺序表实现:
int min = L[0];int max = L[0];for(int i = 0; i < n; i++){if(min > L[i])min = L[i];if(max < L[i])max = L[i];}
链表实现:
int min = p -> next ->data;int max = p -> next ->data;p = p -> next;while(p != NULL){if(min > p ->data)min = p ->data;if(max < p ->data)max = p ->data;p = p ->next;}
逆置
逆置就是把线性表中元素顺序调反
顺寻表实现
int i = 0;int j = n-1;while(i < j){temp = L[i];L[i] = L[j];L[j] = temp;i++;j--;}
链表实现
//r为尾结点while(p ->next != r){temp = p -> next;p -> next = temp -> next;temp -> next = r -> next;r -> next = temp;}
归并
归并就是把两个线性表变为一个,这里其实又有两种了,一种是无序归并,还有一种是有序的归并。无序归并十分简单,这里就不说了,我们主要讲的就是有序归并。
有序归并的栗子:
L1=(1,8,6)
L2=(5,6,9)
归并后为:L3=(1,5,6,6,8,9)
顺序表实现
int i = 0, j = 0;int k = 0;for( ; i < L1_Size && j < L2_Size; k++){if(L1[i] < L2[j])L[k] = L1[i++];elseL[k] = L2[j++];}while(i < L1_Size)L[k++] = L1[i++];while(j < L2_Size)L[k++] = L2[j++];
链表实现归并
while(p->next!=NULL && q->next!=NULL){if(p->next->data < q->next->data){r->next = p->next;p->next= p->next->next;r = r->next;}else{r->next = q->next;q->next= q->next->next;r = r->next;}}if(p->next != NULL) r -> next = p ->next;if(q->next != NULL) r -> next = q ->next;free(p); free(q)
顺序表与链表的比较及选择
到这里我们的顺序表与链表就全部学习完了,那我们在什么时候应该选择顺序表,什么时候又该选择链表呢?我们对顺序表与链表做一个比较来看看吧!!
逻辑结构和物理结构
顺序表:
逻辑相邻物理上也相邻,通过相邻表示逻辑关系
单链表:
逻辑相邻物理上不一定相邻,通过指针表示逻辑关系
基本操作的时间复杂度
插入和删除:
单链表为O(1)(节点指针已知);O(n)(节点指针未知),但操作时只需修改指针
顺序表为O(n)且需要大量移动元素
查找:
按值查找中单链表和顺序表(无序)都为O(n)
按序查找中单链表为O(n),顺序表为O(1)
内存空间
顺序存储:
无论静态分配还是非静态都需要预先分配合适的内存空间 静态分配时预分配空间太大回造成浪费,太小会造成溢出
动态分配时虽不会溢出但是扩充需要大量移动元素,操作效率低
链式存储:
在需要时分配结点空间即可,高效方便,但指针要使用额外空间
如何选择合适的线性表呢?
根据上面的比较做了以下选择总结:
问题情况 | 顺序表(较稳定) | 单链表(较动态) |
---|---|---|
规模难以估计 | * | |
存储密度大 | * | |
按序号访问 | * | |
插入与删除 | * | |
基于数组 | * | |
基于指针 | * |
结言
本来打算两天就总结一篇数据结构的,但是我大意了,写起来属实很费劲,很累,甚至一度向放弃。
But我是不会放弃的,下一篇栈与队列,敬请关注!
有问题请指正,感谢支持!