数据结构-链式结构
数据结构-链式结构
- 线性表的链式表示及实现
线性表的链式表示及实现
链式存储结构
节点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻
- 线性表的链式表示又称为非顺序映像 或链式映像
- 用一组物理位置任意的存储单元来存放线性表的物理元素。
- 这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。
- 链表中元素的逻辑次序和物理次序不一定相同。
- 各结点由两个域组成:
数据域:存储元素数值数据
指针域:存储直接后继结点的存储位置
与链式存储有关的术语
- 结点:数据元素的存储映像。由数据域和指针域两部分组成
- 链表:n个结点由指针链组成一个链表。
它是线性表的链式存储映像,称为线性表的链式存储结构 - 单链表、双链表、循环链表:
-
结点只有一个指针域的链表,称为单链表或线性链表
-
结点有两个指针域的链表,称为双链表
-
首尾相接的链表称为循环链表
- 头指针、头结点和首元结点:
- 头指针:是指向链表中第一个结点的指针
- 首元结点:是指链表中存储第一个数据元素a1 的结点
- 头结点:是在链表的首元结点之前附设的一个结点
- 如何表示空表?
无头结点时,头指针为空时表示空表
有头结点时,当头结点的指针垣为空时表示空表
- 在链表中设置头结点有什么好处?
- 便于首元结点的处理
首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上的操作和其它位置一致,无须进行特殊处理; - 便于空表和非空表的统一处理
无论链表是否为空,头指针都是指向头结点的非空指针,因此空表和非空表的处理也就统一了。
- 头结点的数据域内装的是什么?
头结点的数据域可以为空,也可存放线性表长度等附加信息,但此结点不能计入链表长度值。
链表(链式存储结构)的特点
- 结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。
- 访问时只能通过头指针进入链表,并通过每个结点的指针域依次向后顺序扫描其余结点,所以寻找第一个结点和最后一个结点所花费的时间不等
单链表的定义与表示
带头结点的单链表
单链表是由表头唯一确定,因此单链表可以用头指针的名字来命名若头指针名是L,则把链表称为表L
- 单链表的存储结构
typedef struct Lnode{//声明结点的类型和指向结点的指针类型 ElemType data; //结点的数据域 struct Lnode *next; //结点的指针域}Lnode, *LinkList; //LinkList为指向结构体Lnode的指针类型
- 定义链表L:LinkList L;
- 定义结点指针p:LNode *p;或LinkList p;
单链表基本操作的实现
单链表的初始化(带头结点的单链表),即构造一个空的单链表
【算法步骤】
(1)生成新结点作头结点,用头指针L指向头结点。
(2)将头结点的指针域置空。
【算法描述】
Status InitList_L(LinkList &L){ L=new LNode;//或L= (LinkList) malloc ( sizeof (LNode) L->next=NULL; return OK;}
(补充)判断链表是否为空
空表:链表中无元素,称为空链表(头指针和头结点仍然在)
【算法步骤】判断头节点指针域是否为空
int ListEmpty(LinkList L){//若L为空表,则返回1,否则返回0 if(L->next)//非空 return 0; else return 1;}
(补充)单链表的销毁:销毁链表后不存在
【算法思路】从头指针开始,依次释放所有结点
Status DestroyList_L(LinkList &L){//销毁单链表L Lnode *p;//或LinkList p; while(L){ p=L; L=L->next; delete p;}
(补充)清空链表
链表仍存在,但链表中无元素,成为空链表(头指针和头结点仍然在)
【算法思路】依次释放所有结点,并将头结点指针域设置为空
Status ClearList(LinkList &L){/将L重置为空表 Lnode *p,*q;//或LinkList p,q; p=L->next; while(p){//没到表尾 q=p->next; delete p; p=q; } L->next=NULL;1/头结点指针为空 return OK;}
(补充)求单链表长
【算法思路】从首元结点开始,依次计数所有结点
int ListLength_L(LinkList L){//返回L中数据元素个数 LinkList p; p=L->next; //p指向第一个结点 i=O; while(p){//遍历单链表,统计结点数 i++; p=p->next; } return i;}
单链表取值-取第i个元素
【算法思路】从链表的头指针出发,顺着链域next逐个结点往下搜索,直至搜索到第i个结点为止。因此,链表不是随机存取结构
【算法步骤】
1.从第1个结点(L->next)顺链扫描,用指针p指向当前扫描到的结点,p初值p =L->next。
2.j做计数器,累计当前扫描过的结点数,j初值为1。
3.当p指向扫描到的下一结点时,计数器j加1。
4.当j==i时,p所指的结点就是要找的第i个结点。
【算法步骤】
Status GetElem_L(LinkList L, int i, ElemType &e){//获取线性表L中的某个数据元素的内容,通过变量e返回 p=L->next; j=1; //初始化 while(p&&j<i ){//向后扫描,直到p指向第i个元素或p为空 p=p->next;++j; } if(!p || j>i) return ERROR//第i个元素不存在 e=p->data;//取第i个元素 return OK;}//GetElem_L
单链表查值
- 按值查找:根据指定数据获取该数据所在的位置(该数据的地址)
【算法步骤】
1.从第一个结点起,依次和e相比较。
2.如果找到一个其值与e相等的数据元素,则返回其在链表中的“位置”或地址;
3.如果查遍整个链表都没有找到其值和e相等的元素,则返回0或
“NULL”
Lnode *LocateELem_L (LinkList L, Elemtype e){//在线性表L中查找值为e的数据元素//找到,则返回L中值为e的数据元素的地址,查找失败返回NULL p=L->next; while(p &&p->data!=e) p=p->next; return p;}
- 按值查找:根据指定数据获取该数据所在的位置序号(是第几个数据元素)
//在线性表L中查找值为e的数据元素的位置序号int LocateELem_L (LinkList L, Elemtype e) {//返回L中值为e的数据元素的位置序号,查找失败返回0 p=L->next; j=1; while(p &&p->data!=e){ p=p->next; j++; } if(p) return j; else return 0;}
时间复杂度为O(n)
单链表插入
【算法步骤】
1、首先找到ai-1的存储位置p。
2、生成一个数据域为e的新结点s。
3、插入新结点:①新结点的指针域指向结点a;
②结点a;-的指针域指向新结点
①s -> next = p -> next;
②p -> next = s;
【算法描述】
//在L中第i个元素之前插入数据元素e_Status ListInsert_L(LinkList &L,int i,ElemType e){ p=L; j=0; while(p && j<i-1){ p=p->next; ++j;)//寻找第i-1个结点,p指向i-1结点 if(!p |lji-1)return ERROR;l/i大手表长+1或者小于1,插入位置非法 s=new LNode; s->data=e;//生成新结点s,将结点s的数据域置为 s->next=p->next;//将结点s插入L中 p->next=s; return OK;}//Listlnsert_L
单链表中删除元素–删除第i个结点
【算法步骤】
1、首先找到ai-1的存储位置p,保存要删除的a的值。
2、令p -> next 指向ai+1。
3、释放结点ai的空间。
//将线性表L中第i个数据元素删除Status ListDelete_L(LinkList &L int i,ElemType &e){ p=L;j=O; while(p->next &&j<i-1) { p=p->next;++j; }//寻找第i个结点,并令p指向其前驱if(!(p->next)|l>i-1) return ERROR;//删除位置不合理q=p->next;//临时保存被删结点的地址以备释放p->next=q->next;//改变删除结点前驱结点的指针域e=q->data;//保存删除结点的数据域delete q;//释放删除结点的空间return OK;)//ListDelete_L
单链表的建立-头插法
- 从一个空表开始,重复读入数据;
- 生成新结点,将读入数据存放到新结点的数据域中
- 从最后一个结点开始,依次将各结点插入到链表的前端
void CreateList_H(LinkList &L,int n){ L=new LNode; L->next=NULL;//先建立一个带头结点的单链表 for(i=n;i>0;--i){ p=new LNode;//生成新结点p=(LNode*)malloc(sizeof(LNode)); cin>>p->data;//输入元素值scanf(&p-> data); p->next=L->next;//插入到表头 L->next=p; }}//CreateList_H
时间复杂度为O(n)
单链表的建立-尾插法
- 从一个空表L开始,将新结点逐个插入到链表的尾部,尾指针r指向链表
的尾结点。 - 初始时,r同L均指向头结点。每读入一个数据元素则申请一个新结点,
将新结点插入到尾结点后,r指向新结点。【算法描述】
//正位序输入n个元素的值,建立带表头结点的单链表Lvoid CreateList_R(LinkList&Lint n){ L=new LNode;L->next=NULL; r=L;//尾指针r指向头结点 for(i=O;i<n;++i){ p=new LNode; cin>>p->data;//生成新结点,输入元素值p->next=NULL; r->next=p;//插入到表尾 r=p;//指向新的尾结点 }}//CreateList_R