投稿
  1. 首页
  2. C

数据结构-线性表的链式表示

code • 2022-4-16 • C • 阅读 23

数据结构-线性表的链式表示,第1张

单链表


每个节点除了存放数据元素外, 还存储指向下一个节点的指针(地址)

优点: 不要求大片连续的空间, 改变容量方便
缺点: 不可随机存储, 要耗费一定空间存放指针

定义单链表

typedef struct LNode{	//定义单链表的节点类型
	ElemType data;		//数据域
	struct LNode *next;
}LNode,*LinkList;		//定义了一个节点和指针

申请添加一个节点

struct LNode *p = (struct LNode*)molloc(sizeof(struct LNode));//强制类型转换

typedef关键词—>数据类型重命名

要表示一个单链表时, 只需声明一个头指针, 指向单链表的第一个结点
下面是两种方式:

LNode *L;
Linklist L;

无带头结点的单链表

带头结点的单链表

头结点便于插入删除
空表时, head指向一个结点, 即头结点
除头结点外其余结点均是直接前驱结点的指针的指针域所指向的结点, 即…->next

定义一个不带头结点的单链表 
typedef struct LNode{		//定义单链表结点的类型
	ElemType data;			//每个结点存放一个数据元素
	struct LNode *next;		//指针指向下一个结点
}LNode, *LinkList;

//初始化一个单链表(带头结点)
bool InitList(Linklist &L){
	L=(LNode*)malloc(sizeof(LNode));	//分配一个头结点
	if(L==NULL){						//内存不足, 分配失败
		return false;
	}
	L->next=NULL;						//头结点之后暂时还没有结点
	return ture;
}

头结点一般不存放数据, 存放表名

判断单链表是否为空 
bool Empty(LinkList L){
	if(L->next==NuLL){
		return true;
	}else{
		return false;
	}
}
单链表按位插入(带头结点)

LinkList(&L, i, e): 插入 *** 作, 在表L中第i个位置插入指定元素e

关键: 找到第i-1个结点, 将新结点插入其后面

status ListInsert(LinkLIst &L, int i, ElemType e){
	p=L;
	int j=0;
	while(j<i-1 && p!=NULL){	//遍历到第i-1个结点或表尾
		j++;
		p = p->next;
	}
	if(p==NULL && j>i-1){
		return ERROR;		
	}
	s=(LinkList)malloc(sizeof(LNode));		//创建新的结点
	if(s==NULL){
		exit(OVERFLOW);						//存储分配失败
	}
	s->data=e;								//将s的数据域设置为e
	s->next = p->next;						//将s插入到p之后
	p->next = s;
	return OK;
}
单链表按位插入(不带头结点)

LinkList(&L, i, e): 插入 *** 作, 在表L中第i个位置插入指定元素e

status ListInsert(LinkLIst &L, int i, ElemType e){
	if(i==1){
		//对i为1的插入位置进行特殊处理
		s= (LinkList)malloc (sizeof(LNode));//新建结点s
		if(s==NULL){
			exit(OVERFLOW);
		}
		s->data=e;	//插入元素e
		s->next=L;	//插入结点s
		L=s;		//修改头结点
	}
	else{// 与头结点类似
		P=L;
		j=1;
		while(j<i-1 && p!=NULL){	//遍历到第i-1个结点或表尾
			j++;
			p = p->next;
		}
		if(p==NULL && j>i-1){
		return ERROR;		
		}
		s=(LinkList)malloc(sizeof(LNode));		//创建新的结点
		if(s==NULL){
			exit(OVERFLOW);						//存储分配失败
		}
		s->data=e;								//将s的数据域设置为e
		s->next = p->next;						//将s插入到p之后
		p->next = s;
		return OK;
	}
}
单链表的删除(带头结点)

ListDelete(&L, int i, &e): 删除 *** 作
删除L表中第i个元素, 并用e返回删除元素的值

int ListDelete(LinkList &L, int i, ElemType &e){
	//设L带头结点
	j=0;
	p=L;
	while(j<j-1 && p->next){
		j++;
		p=p->next;
	}
	if(!(p->next)||j>j-1){
		return ERROR;			//位置不合理
	}
	q=p->next;					//q指向删除的结点
	e=q=>data;					//用e将被删除元素带回到主调函数中
	p->next=q->next;			//从单链表中删除q结点
	free(q);					//释放q结点
	return OK;
}

单链表按为序插入(带头结点)

ListInsert(&L, i , e): 插入 *** 作 , 在表L中的第i个位置上插入指定元素e

status ListInsert(LinkList &L, int i, ElemType e){
	//将值为e的结点插入到第i个位置
	p=L;
	j=0;
	while(j<i-1 && p!=NULL){		//遍历到i-1的位置
		j++;
		p=p->next;
	}
	if(p==NULL || j>i-1){
		return ORROR;
	}
	s=(LinkList)malloc(sizeof(LNode));		//创建新的结点
	if(s==NULL){
		exit(OVERFLOW);						//存储分配失败
	}
	s->data=e;								//将s的数据域设置为e
	s->next=p->next;						//将s插入p之后
	p->next=s;								
	return OK;
}


最好的时间复杂度是O(1)
最坏的时间复杂度是O(n)
平均的时间复杂度是O(n)

单链表按为序插入(不带头结点) 
int ListDelete(LinkList &L, int i, ElemType &e){
	if(i=1){
		//对i=1的插入位置进行特殊处理
		s=(LinkList)malloc(sizeof(LNode));		//创建新的结点s
		if(s==NULL){
			exit(OVERFLOW);
		}
		s->data=e;
		s->next=L;//插入结点s
		L=s;//修改头指针
	}
	else{
		p=L;
		j=0;
		while(j<i-1 && p!=NULL){		//遍历到i-1的位置
			j++;
			p=p->next;
		}
		if(p==NULL || j>i-1){
			return ORROR;
		}
		s=(LinkList)malloc(sizeof(LNode));		//创建新的结点
		if(s==NULL){
			exit(OVERFLOW);						//存储分配失败
		}
		s->data=e;								//将s的数据域设置为e
		s->next=p->next;						//将s插入p之后
		p->next=s;	
	}
	return OK;
}
单链表的删除(带头结点)

ListDelete(&L,i, &e): 删除 *** 作, 删除表L中第i个位置的元素, 并用e返回删除元素的值

int ListDelete(LinkList &L, int i, ElemType &e){
	//设L带头结点
	j=0;
	p=L;
	while(j<i-1 && p->next){
		j++;
		p=p->next;
	}
	if(!(p->next)||j>j-1){		//位置不合理
		return ERROR;
	}
	q=p->next;					//q指向删除的结点
	e=q->data;					//用e将被删除的要素带回到主调函数中
	p->next=q->next				//从单链表中删除q结点
	free(q);					//释放q结点
	return OK;
}
单链表查找-按位查找(带头结点)

求表中指定位置的某个数据元素 GetElem(L, i, &e)
在单链表L中从头开始找到第i个结点, 若存在第i个结点, 则将其data域赋值给变量e

int GetElem(LinkList L, int i, ElemType &e){
	p=L->next;
	j=1;
	while(j<i && p!NULL){	//判断是否找到指定位置或表尾
		j++;
		p=p->next;
	}
	if(j>i||p==NULL){		//不存在第i个结点
		return 0;
	}
	//存在第i个结点
	e=p->data;
	return 1;
}

平均时间复杂度O(n)

单链表按值查找

LocateElem(L, e)
在单链表L中从头开始找第1个值域与e相等的节点, 若存在, 则返回位置, 否则返回0

int LocateElem( LinkLIst L, ElemType &e){
	p=L->next;
	n=1;
	while(p->data!=e && p!=NULL){
		j++;
		p=p->next;
	}
	if(p==NULL){
		return 0;
	}else{
		return n;	
	}	
}

平均时间复杂度 O(n)

单链表的建立-尾插法

新节点插入到最后一个结点之后

  1. 新建一个结点s
  2. 向新节点s添入内容
  3. 将新节点s链入链尾 r->next=s
  4. 改变尾指针 r=s
void CreateList_LR(LinkList &L, int n){
	//尾插法创建
	L=(LinkList)malloc (sizeof(LNode));//创建头节点
	L->next=NULL;	//将头节点next域置空
	r=L;			//r始终指向为节点
	for(int i=0; i<n;i++){
		s=(LinkList)malloc(sizeof(LNode));//创建新的结点
		scanf(&s->data);
		r->next=s;		//将s插入r之后
		r=s;			//r指向新尾结点
	}
	r->next=NULL;		//尾结点的next域置为空值
}

插入一个结点的时间:O(1)
尾插法创建单链表的时间复杂度: T(n)=O(n)

单链表的建立-头插法

新结点插入到链表中的第一个数据结点之前, 即头结点之后
`

  1. 建立新结点s
  2. 向新结点s中添加内容
  3. 使新节点s的指针域指向第1个数据点 s->next=L->next
  4. 改变头节点指针域: L->next=s;
void CreateList_LF(LinkList	&L, int n){
	//建立链表,含n个数据元素
	L=(LinkList)malloc(sizeof(LNode));//创建头结点
	L->next=NULL;	//将头结点的next域指空
	for(i=0; i<n; i++){
		//创建新结点
		s=(LinkList)malloc(sizeof()LNode);
		scanf(&s->next);
		//将s插在第一个数据结点之前, 即紧跟头结点后
		s->next=L->next;
		L->next=s;
	}
}

插入一个结点的时间复杂度是O(1)
头插法创建单链表的时间复杂度O(n)

双链表

单链表无法逆向检索,有时使用不是很方便
双链表可进可退, 存储密度更低

双链表的定义 
typedef struct DNode{		//定义双链表的结点类型
	ElemType data;
	struct DNode *prior;		//指向直接前驱结点
	struct DNode *next;			//指向直接后继结点
}DNode, *DLinkList;
双链表的插入

双链表的插入: 在p结点后插入s

  1. 找到插入位置的前驱p
  2. 创建新结点s
  3. s->data=x
  4. s->next=p->next
  5. p->next->prior=s
  6. s->prior=p
  7. p->next=s

双链表的删除

删除第i个结点

  1. 找到被删除的结点q
  2. q->prior->next=q->next
  3. q->next->prior=q->prior
  4. free(q)
双链表的编历

后向遍历

while(p!=NULL){
	p=p->next;
}

前向遍历

while(p!=NULL){
	p=p->prior;
}

向前遍历(跳过头结点)

while(p->prior != NULL){
	p=p->prior;
}

双链表不可以随机存储, 按位查找,按值查找都只能用遍历的方式实现
时间复杂度O(n)

循环链表

循环链表的特点是表中最后一个结点的指针域不再是空, 而是指向头结点, 整个链表形成一个环

由此, 从表中任意一个结点出发均可找到链表中的其他结点

循环单链表

循环双链表

定义循环单链表 
typedef struct LNode{		//定义单链表结点类型
	ElemType data;			//每个结点存放一个数据元素
	struct LNode *next;		//指针指向下一个结点
} LNode, *LinkList;

初始化一个循环链表

bool InitList(LinkList &L){
	L=(LNode*)malloc(sizeof(LNode));//分配一个头结点
	if(L==NULL){
		return false;	//内存不足, 分配失败
	}
	L->next=L;			//头结点next指向头节点
	return true;
}

判断结点p是否为循环单链表的表尾结点

bool isTail(LinkList L, LNode *p){
	if(p->next==L){
		return true;
	}else{
		return false;
	}
}

判断循环单链表是否为空

bool Empty(LinkList L){
	if(L->next==L){
		return true;
	}else{
		return false;
	}
}
定义双循环链表 
typedef struct DNode(){
	ElemType data;
	struct DNode *prior, *next;
}DNode,*DLinkList;

初始化空的循环双链表

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 isTail(DLinklist L , DNode *p){
	if(p->nxt==L){
		return true;
	}else{
		return false;
	}
}

判断双链表是否为空

bool Empty(DLinkList L){
	if(L->next==L){
		return true;
	}else{
		return false;
	}
}
静态链表

静态链表可借用一维数组来描述

数组元素(元素的值, 指示器)表示结点

指示器: (游标cur)代替指针以指示结点在数组中的相对位置–>伪指针

数组中的第0个分量可以看成头结点, 其指针域指示静态链表的第一个结点
需要预先分配一个较大的空间, 但是在进行插入和删除 *** 作时不需要移动元素, 仅需要修改"指针", 因此仍具有链式存储结构的主要优点

静态链表初始化

把a[0]的next设置为-1;
把其他结点的next设为一个特殊值用来表示结点空闲, 如-2

typedef struct {	//静态链表结构类型的定义
	ElemType data;	//存储数据元素
	int next;		//下一个元素的数组下标
}SLinkList[MaxSize];

静态链表的基本 *** 作

查找:

从头结点出发往后遍历结点

插入位序为i的结点

  1. 找到一个空的结点, 存入数据元素
  2. 从头结点出发找到位序为i-1的结点
  3. 修改新结点的next
  4. 修改i-1号结点的next

删除某个结点

  1. 从头结点出发找到前驱结点
  2. 修改前驱结束点的游标
  3. 被删除结点next设为-2

欢迎分享，转载请注明来源：内存溢出

原文地址: https://outofmemory.cn/langs/634699.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-16
下一篇 2022-04-16

发表评论

登录后才能评论

评论列表（0条）

保存