链式存储
标签: 数据结构
学习人数: 29.9k


高清播放
赞赏支持

单链表的定义

顺序表它虽然可以实现随机存取,但是在初始化时需要申请一大块连续的存储空间,而且它在执行例如插入、删除操作时也需要大量的移动元素,时间复杂度较高。今天讲述线性表的一种新的存储表示方法,也就是线性表的链式表示。

 

首先,还是先来看单链表的定义。书中说,线性表的链式存储,把它称作为单链表。来看一个小例子,今天又是周末,小明和他的小伙伴们又想来吃火锅。今天与上次不同,他们不是一同前来的,而是各自来的火锅店,所以他们被安排在等候区等候的位置就不一定连续了。这与线性表的链式存储,也就是单链表相同,它们在存储单元上是不一定连续的。单链表通过一组任意的存储单元来存储线性表中的数据元素,也就是数据元素存储的位置不一定连续。

接下来,如果一号小朋友知道了有位置消息,他会通过手机告诉下一个小伙伴他等到了位置,接下来四号小朋友也会用手机通知下面的小伙伴,接着依旧六号小朋友会通知最后的小伙伴,告诉他等到位置了,这样就用手机维持这样一个线性的逻辑关系。

在链式存储中,手机这样的用以维持线性逻辑关系的事物叫做指针,所以,在单链表中,是通过指针来实现线性的逻辑关系的,它与顺序存储是不同的。顺序存储是通过存储单元相连就可以实现逻辑上的线性关系,但是在单链表中,数据元素是存储在任意位置的,所以只能通过指针来实现线性逻辑关系。

 


单链表的实现

首先给出一个线性表,存放数据元素,a1 到 an 有这样的线性逻辑关系。单链表在存储空间上是这样存放的,它是存放在任意位置的,这个任意位置表示它们不一定要连续。如图所示的 a2、a3 与 a3、a4 。

第二个很明显的差别是单链表在存放数据元素同时,不仅仅存放了数据本身,还存放了下一个数据元素地址,通过这样的地址来维持了线性的逻辑关系。表示 a2 是 a1 的后继,a3 是 a2 的后继。这样地址像一条链子一样,把所有的数据元素串了起来,形成了一个单链表,我们管这样的数据加地址的组合叫做单链表的一个节点。该节点是由存放数据元素的数据 data 和存放下一个数据元素的地址的指针域 next 共同来组成。

typedef struct LNode {  
    ElemType data;  
    struct LNode *next;  
} LNode, *LinkList;  

在程序设计语言上,我们会通过一个结构体来实现这样一个节点,它的名字叫做 LNode ,其中包含保存数据元素的变量 data 和存放下一个数据元素的指针 LNode *next 。它这个结构体的名字不仅仅叫做 LNode,还叫做 LinkList。通过名字可以发现一个节点也可以表示为一个单链表。因为只要给出第一个节点的地址,就可以依次找到属于这个单链表的所有节点。所以通过一个指针,还可以表示该单链表。

 

单链表虽然有一些优点,但是它也存在一些弊端。比如说单链表在存放数据元素的同时,还要存放指向下一个节点位置的指针域,那么这些指针域会造成空间的浪费。单链表在存放数据元素时,没有像顺序表那样存储空间连续相邻这样一个特点,所以不能实现随机存取,只能实现顺序存取。也就是说,想要找到其中的一个数据元素,只能从第一个数据元素的位置依次查找,遍历单链表。这就是单链表的具体实现方式。

这是所画出的一个单链表 L。其中保存的数据元素是 a1 到 an ,并且 a2 是 a1 后继 ,a3 是...

登录查看完整内容


课后作业

课后习题


【2016年真题】已知表头元素为c的单链表在内存中的存储状态如下表所示。

现将f存放于1014H处并插入到单链表中,若f在逻辑上位于a和e之间,则a,e,f的“链接地址”依次是()
A.1010H,1014H,1004H            B.1010H,1004H,1014H
C.1014H,1010H,1004H            D.1014H,1004H,1010H

参考答案:D


【2016年真题】已知一个带有表头结点的双向循环链表L,结点结构为

其中,prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点,正确的语句序列是()
A.p->next->prev=p->prev;p->prev->next=p->prev;free(p);
B.p->next->prev=p->next;p->prev->next=p->next;free(p);
C.p->next->prev=p->next;p->prev->next=p->prev;free(p);
D.p->next->prev=p->prev;p->prev->next=p->next;free(p);

参考答案:D


【2015年真题】用单链表保存m个整数,结点的结构为:[data][link],且|data|≤n(n 为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中 data 的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。例如,若给定的单链表 head 如下:

则删除结点后的 head 为:

要求:
1)给出算法的基本设计思想。
2)使用 C 或C++语言,给出单链表结点的数据类型定义。
3)根据设计思想,采用 C 或C++语言描述算法,关键之处给出注释。
4)说明你所设计算法的时间复杂度和空间复杂度。

参考答案:
1、算法的基本设计思想
算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值,从而只需对链表进行一趟扫描。
因为|data|<=n,故辅助数组q的大小为n+1,各元素的初值均为0。依次扫描链表中的各结点,同时检查q[|data|]的值,如果为0,则保留该节点,并令q[|data|] = 1;否则,将该结点从链表中删除。

 

2、使用C语言描述的单链表节点的数据类型定义
 

typedef struct node {  
    int data;  
    struct node *link;  
}NODE;  
Typedef NODE *PNODE;  

 

3、算法实现
 

void func(PNODE h,int n) {   
    PNODE p=h,r;  
    int *q,m;  
    q=(int *)malloc(sizeof(int)*(n+1));//申请 n+1 个位置的辅助空间  
    for(int i=0;i<n+1;i++) //数组元素初值置 0  
        *(q+i)=0;  
    while(p->link!=NULL) {  
        m=p->link->data>0? p->link->data:-p->link->data;  
        if(*(q+m)==0) //判断该结点的 data 是否已出现过  
        {  
            *(q+m)=1; //首次出现  
            p=p->link; //保留  
        }  
        else //重复出现  
        {  
            r=p->link; //删除  
            p->link=r->link  
            free(r);  
        }  
    }  
    free(q);  
}  

 

4、时间复杂度O(m),空间复杂度O(n)


登录后开始许愿

1 条上岸许愿
曲中遇曲终
2021年11月12日 20:19

yes

赞(0)