2020-09-25 08:08:34

线性链表 免费编辑 添加义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
所属类别 :
计算机语言
计算机语言
编辑分类

具有链接存储结构的线性表,它用一组地址任意的存储单元存放线性表中的数据元素,逻辑上相邻的元素在物理上不要求也相邻,不能随机存取。一般用结点描述:结点(表示数据元素) =数据域(数据元素的映象) + 指针域(指示后继元素存储位置)

折叠 编辑本段 概念

在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。链式存储方式即可以用于表示线性结构,也可用于表示非线性结构

一般来说,在线性表的链式存储结构中,各数据结点的存储符号是不连续的,并且各结点在存储空间中的位置关系与逻辑关系也不一致。对于线性链表,可以从头指针开始,沿各结点的指针扫描到链表中的所有结点。

折叠 编辑本段 实现

(1) 线性表的操作GetElem(L, i, &e)在链表中的实现:

基本操作为: 使指针p始终指向线性表中第j个数据元素

Status GetElem_L(LinkList L, int i, ElemType &e)// L为带头结点的单链表的头指针。当线性表中存在第i个元素时,则将第i个数据元素的值赋给e并返回OK,否则返 回ERROR

{p = L->next; j = 1; // 初始化,p指向第一个结点,j为计数器

while (p && j); // 顺指针向后查找,直到p指向第i个元素或p为空

p = p->next; ++j; }

if ( !p || j>i ) return ERROR; // 第i个元素不存在

e = p->data; // 取第i个元素

return OK;

} // GetElem_L算法的时间复杂度为:O(ListLength(L))

(2) 线性表的操作ListInsert(&L, i, e)在链表中的实现:

基本操作为: 找到线性表中第i-1个结点,修改其指向后继的指针

有序对<ai-1, ai> 改变为 <ai-1, e> 和 <e, ai>

Status ListInsert_L(LinkList L, int i, ElemType e) {

// 在带头结点的单链表L中第i个数据元素之前插入数据元素e

p = L; j = 0;

while (p && j < i-1)

{ p = p->next; ++j; } // 寻找第i-1个结点

if (!p|| j > i-1) return ERROR; // i小于1或者大于表长

s = (LinkList) malloc (sizeof (LNode)); // 生成新结点

s->data = e; s->next = p->next; // 插入L中

p->next = s;

return OK;

} // LinstInsert_L算法的时间复杂度为:O(ListLength(L))


(3) 线性表的操作ListDelete(&L, i, &e)在链表中的实现:

基本操作为: 找到线性表中第i-1个结点,修改其指向后继的指针

有序对<ai-1, ai> 和 <ai, ai+1> 改变为<ai-1, ai+1>

Status ListDelete_L(LinkList L, int i, ElemType &e)

{ p = L; j = 0;} // 在带头结点的单链表L中,删除第i个元素,并由e返回其值

while (p->next && j < i-1)

{p = p->next; ++j; // 寻找第i个结点,并令p指向其前趋}

if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理

q = p->next; p->next = q->next; // 删除并释放结点

e = q->data; free(q);

return OK;

} // ListDelete_L算法的时间复杂度为:O(ListLength(L))

折叠 编辑本段 单链线性表

在线性表的链接存储中,为了方便在表头插入和删除结点的操作,经常在表头结点(存储第一个元素的结点)的前面增加一个结点,称之为头结点表头附加结点。这样原来的表头指针由指向第一个元素的结点改为指向头结点,头结点的数据域为空,头结点的指针域指向第一个元素的结点。

定义一个带头结点的线性链表类型:

typedef struct LNode // 结点类型

{

ElemType data;

struct LNode *next;

} *Link,*Position;

typedef struct // 链表类型

{ Link head, tail; // 指向头结点和最后一个结点

int len; // 指示链表长度

Link current; // 指向当前访问的结点的指针,初始位置指向头结点

}

LinkList;

Status MakeNode( Link &p, ElemType e );

// 分配由p指向的值为e的结点,并返回OK;若分配失败,则返回ERROR

void FreeNode( Link &p ); // 释放p所指结点

创建带头结点的单链线性表:

void CreateList_L(LinkList&L, int n) // 逆位序输入n个元素的值,建立带表头结点的单链线性表L。

{ L = (LinkList) malloc (sizeof (LNode));

L->next = NULL; // 先建立一个带头结点的单链表

for (i = n; i > 0; --i) {

p = (LinkList) malloc (sizeof (LNode)); // 生成新结点

scanf(&p->data); // 输入元素值

p->next = L->next; L->next = p; // 插入到表头

}

} // CreateList_L算法的时间复杂度为:O(Listlength(L))

阅读全文

热点资讯