京东秒杀
国美-超级5
索尼Xperia旗舰
限时优惠页 - 京东
自营热卖

单链表基础概念,线性表的链式表示和实现,单链表基本操作的实现

弦上春雪 1年前   阅读数 62 0

单链表基础概念,线性表的链式表示和实现


以下博客代码段我都以完整的C++语言编写了下来详情可看C++实现单链表基本操作


线性表链式存储(链表)

链表(linked list)是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

  • 特点

    1.用一组物理位置任意的存储单元来存放线性表的数据元素。
    这组存储单元既可以是连续的,也可以是不连续的,甚至是零散分布在内存中的任意位置上的。

    2.访问时只能通过头指针进入链表,并通过每个结点的指针域依次向后顺序扫描其余结点,所以寻找第一个结点和最后一个结点所花费的时间不等(也被称为顺序存取法) (顺序表是随机存取)
    3.链表中元素的逻辑次序和物理次序不一定相同

  • 与链式存储有关的术语

    1.结点:数据元素的存储映像。由数据域指针域两部分组成
    2.链表:n个结点由指针链组成一个链表。
    它是线性表的链式存储应映像,称为线性表的链式存储结构。
    3.单链表、双链表、循环链表

    • 结点只有一个指针域的链表,称为单链表或线性链表
    • 结点有两个指针域的链表,称为双链表
    • 首尾相接的链表称为循环链表

    如图:
    在这里插入图片描述
    4.头指针、头结点和首元结点
    头指针:是指向链表中第一个结点的指针
    首元结点:是指链表中存储第一个数据元素a1的结点
    头结点:是在链表的首元结点之前附设的一个结点

    在这里插入图片描述

  • 在链表中设置头结点的好处

    1.便于首元结点的处理
    首元结点的地址保存在头结点的指针域中,所以在链表的第一个位置上 的操作和其他一致,无须进行特殊处理;
    2.便于空表和非空表的统一处理
    无论链表是否为空,头指针都是指向头结点的非空指针,因此空表和非空表的处理也就统一了。


单链表

单链表(Singly Linked List)是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

单链表是有表头唯一确定,因此单链表可以用头指针的名字来命名
若头指针名是L,我们把链表称为表L

  • 单链表的存储结构

    结点结构=数据域+指针域
    data域–存放结点值的数据域
    next域–存放结点的直接后继的地址(位置)的指针域(链域)

    在这里插入图片描述

typedef struct LNode{    //类型定义 
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;

LinkList L;  //定义链表L
LNode *p;    //定义结点指针p

  • 单链表基本操作的实现

1.单链表的初始化

Status InitList(LinkList &L){   //构造一个空的单链表L 
	L=new LNode;     //生成新结点作为头结点,用头指针L指向头结点 
	L->next=NULL;   //头结点的指针域为空 
	return OK;
} 

2.判断链表是否为空

int  ListEmpty(LinkList L){   //若L为空表,则返回1,否则返回0 
	if(L->next)    //非空 
		return 0;
	else
		return 1;	
} 

3.销毁单链表

Status DestroyList_L(LinkList &L){   //销毁单链表L 
	LNode *p;    //或LinkList p; 
	while(L){
		p=L;
		L=L->next;
		delete p;
	}
}

4.清空单链表

tatus 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;   //头结点指针域为空 
	return OK;
} 

5.求单链表的表长

//求单链表L的表长 
int ListLength_L(LinkList L){  //返回L中数据元素个数 
	LinkList p;
	p=L->next;      //p指向第一个结点 
	int i=0;
	while(p){       //遍历单链表,统计结点数 
		i++;
		p=p->next;
	}
} 

6.取值:取单链表中第i个元素的内容

Status  GetElem_L(LinkList L,int i,ElemType &e){   //获取线性表L中的某个数据元素的内容,通过变量e返回 
	p=L->next;int j=1;  //初始化 
	while(p&&j<i){    //先后扫描,直到p指向第i个元素或p为空 
		p=p->next;
		++j;
	}
	if(!p||j>i)
		return ERROR;   //第i个元素不存在 
	else{
		e = p->data;       //取第i个元素 
		return OK;
	}	
}  //GetElem_L

算法的时间复杂度是:O(n)

7.查找
返回地址

//在线性表L中查找值为e的数据元素并返回该元素的地址,查找失败则返回NULL 
LNode *LocateElem_L (LinkList L,ElemType e){  
	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)

8.插入:在第i个结点前插入新结点

//在L中第i个元素之前插入数据元素e
Status ListInsert_L(LinkList &L,int i,ElemType e){
	p=L;j=0;
	while(p && j < i-1){    //寻找第i-1个结点,p指向i-1结点 
		p=p->next;          
		++j;      
	}
	if(!p||j>i-1)           //i大于表长+1或者小于1,插入位置非法 
		return ERROR;
	s = new LNode;          //生成新结点s,将结点s的数据域置为e
	s->data	= e;           
	s->next = p->next;      //将结点s插入L中 
	p->next = s;
	return OK;
} // ListInsert_L

算法的时间复杂度是:O(n)

9.删除:删除第i个结点

Status ListDelete_L(LinkList &L,int i,ElemType &e){  //将线性表L中第i个数据元素删除 
	p=L;j=0;
	while(p->next && j < i-1){   //寻找第i个结点,并令p指向其前驱 
		p=p->next;
		++j;
	}
	if(!(p->next)||j>i-1)  //删除位置不合理 
		return ERROR;
	q=p->next;                //临时保存被删结点的地址以备释放 
	p->next=q->next;         //改变删除结点前驱节点的指针域 
	e=q->data;               // 保存删除结点的数据域 
	delete q;                // 释放删除结点的空间 
	return OK;	
} //ListDelete_L

算法的时间复杂度是:O(n)

10.创建单链表
前插法
1.从一个空表开始,重复读入数据;
2.生成新结点,将读入数据存放到新结点的数据域中
3.从最后一个结点开始,依次将各结点插入到链表的前端
在这里插入图片描述

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)

后插法
1.从一个空表L开始,将新结点逐个插入到链表的尾部,尾指针r指向链表的尾结点
2.初始时,r同L均指向头结点。每读入一个数据元素则申请一个新结点,将新结点插入到尾结点后,r指向新结点

////正位序输入n个元素的值,建立带头表结点的单链表L
void CreateList_R(LinkList &L,int n){
	L=new LNode;  L->next=NULL;
	r = L;           //尾指针r指向头结点 
	for(i=0;i<;++i){
		p=new LNode;  cin >> p->data;  //生成新结点,输入元素值 
		p->next=NULL;
		r->next=p;   //插入到表尾 
		r=p;   //指针r指向新的尾结点 
	}
} //CreateList_R

算法的时间复杂度是:O(n)


声明:此博客只是作者为了熟悉知识点而写的笔记
借鉴:《数据结构》(C语言版)(第2版)严蔚敏

发布了7 篇原创文章 · 获赞 35 · 访问量 8370

注意:本文归作者所有,未经作者允许,不得转载

全部评论: 0

    我有话说: