数据结构：线性表全解

您所在的位置：网站首页 › 线性表的特点是每个元素都有前驱和后继 › 数据结构：线性表全解

数据结构：线性表全解

2024-01-01 00:52| 来源: 网络整理| 查看: 265

导图

在这里插入图片描述

线性表定义

线性表是由n个数据元素组成的有限序列，其中n≥0。线性表中的每个数据元素都有一个唯一的前驱元素和一个唯一的后继元素，除了第一个元素没有前驱元素，最后一个元素没有后继元素。线性表可以为空表，即n=0。线性表中的数据元素可以是任意类型的，如整数、字符、字符串、结构体等。线性表通常用一维数组来实现，也可以用链表、栈、队列等数据结构来实现。

顺序表 1、概念

用一组地址连续的存储单元依次存储线性表的数据元素特点：元素在内存中的存储是连续的，元素之间的顺序与其在表中的顺序一致。

顺序表的最大特点是随机存储，只要确定了线性表的起始存储位置，就可以做到将每一项元素随机存储。与一维数组一样，都是随机存储。

2、存储结构

在这里插入图片描述访问顺序表中的元素

使用下标arry[i]使用指针p，p+i 3、构建顺序表

顺序表的两大必要元素：基地址、存储长度。

typedef int ElemType; //ElemType的类型根据实际情况而定，这里假定为int #define maxsize 100 //顺序表可能达到的最大长度 typedef struct { ElemType *elem; //存储空间的基地址 int length; //存储长度 }SqList;

注意：length表示顺序表中存储数据的个数。因为数组的下标是从0开始的，而位置序号是从1开始的。所以数据元素a1、a2…an在数组的位置依次为elem[0]、elem[1]…elem[n-1]。

4、顺序表的初始化

算法步骤：

为顺序表L动态分配应该预定义大小的数组空间，使elem指向这段空间的基地址。将表的当前长度设置为0。 Status InitList(SqList* L){ //构造一个空的线性表L L -> elem = (ElemType *)malloc(MAXSIZE*sizeof(ElemType)); //动态分配空间、避免空间的浪费 if(!L -> elem){ return ERROR; //无地址分配、分配失败，退出程序 } L -> length = 0; return OK; } 5、顺序表的取值

算法步骤：

判断指定的位置序号为 i 是否合理(1 int k; if(L->length == 0){ //线性表为空 return ERROR; } if(i L->length){ //删除位置不正确 return ERROR; } *e = L -> elem[i-1]; if(i length){ //如果删除位置不在最后位置 for(k = i;k length;k++){ L->elem[k-1] = L->elem[k]; } } L->length--; //长度减1 return OK; } 7、顺序表的删除

算法步骤：

判断删除位置 i 是否合法(i 值的合法范围是1 //线性表为空 return ERROR; } if(i L->length){ //删除位置不正确 return ERROR; } *e = L -> elem[i-1]; if(i length){ //如果删除位置不在最后位置 for(k = i;k length;k++){ L->elem[k-1] = L->elem[k]; } } L->length--; //长度减1 return OK; } 链表

用一组任意的存储单元存储线性表的数据元素

一、单链表

整个链表的存取必须从头指针开始进行，头指针指示链表中的第一个节点(首元节点)的存储位置。同时，由于最后一个数据元素没有直接后继，则单链表中最后一个节点的指针为空。在这里插入图片描述

根据上述图片，1的后继节点为2，1的指针域存储的是2的地址，同理，2是1的前驱节点。

1、单链表的存储结构 //------单链表的存储结构------ typedef struct LNode { ElemType data; //节点的数据域 struct LNode *next; //节点的指针域 }LNode,*LinkList; //LinkList 是指向结构体 LNode 的指针类型

为了提高程序的可读性。再次对同一结构体指针类型起了两个名称，LinkList与LNode * ，两者的本质是等价的。通常习惯上用LinkList定义单链表，强调定义的是某个单链表的头指针；用LNode 定义指向点链表中任意节点的指针变量。

2、单链表的构建

算法步骤：

生成新节点作为头节点，用头指针L指向头节点。头节点的指针域置空。 Status InitList(LinkList &L) { L = new LNode; L->next = NULL: return Ok; } 3、单链表的取值

算法步骤：

用指针p指向首元结点，用 j 做计数器初始值赋值为1。从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针不为空（NULL），并且没有达到序号为 i 的节点，则循环执行： p指向下一个节点；计数器 j 相应加 1。退出循环时，如果指针 p 为空，或者计数器 j 大于 i ，说明指定的序号 i 值不合法（i 大于表长 n 或者 i 小于等于 0），取值失败返回Error；否则取值成功，此时j = i时，p所指的结点就是要找的结点就是要找的第 i 个结点，用参数e保存当前结点的数据域，返回Ok。 Status GetElem(LinkList L,int i,ElemType &e) { p=L->next; j=1; while(p&&j p=L->next; whlie(P&&p->data!=e) p==->next; return p; } 5、单链表的插入

算法步骤：

查找结点ai-1并由指针 p 指向该结点。生成一个新结点*s。将新结点*s的数据域置位e。将新结点*s的指针域指向ai。将结点*p的指针域指向新结点 *s。 Status ListIsert(LinkList &L,Int I,ElemType e) { p=L;i=0; while(p && (j p=L;i=0; while((p->next) && (j L=new LNode; L->next=NULL; for(i=0;i L=new LNode; L->next=NULL; r=L; for(i=0;i ElemType data; struct DuLNode *prior; struct DoLNode *next; }DuLNode,*DuLinkList;

在这里插入图片描述

2、双向链表的插入 Status ListIsert_DuL(DuLinList &L,int i,ElemType e) { if(!(P=GetElem_DuL(L,i))) return Error; s=new DuLNode; s->data=e; s->prior=p->prior; p->prior->next=s; s->next=p; p->prior=s; return Ok; }

在这里插入图片描述

3、双向链表的删除 Status ListDelete_DuL(DuLinList &L,int i,ElemType e) { if(!(P=GetElem_DuL(L,i))) return Error; p->prior-next=p->next; p->nextprior=p-prior; deleye p; return Ok; } 顺序表与链表的比较

在这里插入图片描述

【本文地址】

数据结构：线性表全解

数据结构：线性表全解

今日新闻

推荐新闻