获取单链表中的指定位置的元素

工作指针的概念
服务器君一共花费了210.760 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

单链表作为一种数据结构,存取数据是其很基本的操作。今天我们来看一下,如何获取单链表指定位置的元素。

  • 在线性表的顺序存储结构中,我们要计算任意一个元素的存储位置是很容易的。因为线性表的顺序存储就是个数组嘛,比如要获取第5个元素,可以直接a[5]就行了。但是单链表就有点不一样,他不是简单的数组。
  • 在单链表中,由于第i个元素到底在哪是没办法一开始就知道,必须得从头开始找。我们可以先设计一下单链表实现获取第i个元素的数据的操作GetElem()函数。
  1. 声明一个结点p指向链表第一个结点,初始化j从1开始;
  2. 当j < i时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1;
  3. 若到链表末尾P为空,则说明第i个元素不存在;
  4. 否则査找成功,返回结点p的数据。

所以函数设计如下:

/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果:用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
	int j;
	LinkList p;		/* 声明一结点p */
	p = L->next;		/* 让p指向链表L的第一个结点 */
	j = 1;		/*  j为计数器 */
	while (p && j < i)  /* p不为空或者计数器j还没有等于i时,循环继续 */
	{
		p = p->next;  /* 让p指向下一个结点 */
		++j;
	}
	if ( !p || j>i )
		return ERROR;  /*  第i个元素不存在 */
	*e = p->data;   /*  取第i个元素的数据 */
	return OK;
}
  • 说白了,就是从头开始找,直到第i个元素为止。由于这个算法的时间复杂度取决于i的位置,当i=l时,则不需遍历,第一个就取出数据了,而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是0(n)。
  • 这个函数里为什么要用while循环,而不用for循环呢?
  • 由于单链表的结构中没有定义表长,所以不能事先知道要循环多少次,因此也就不方便使用for来控制循环。用while的条件控制,当循环执行完毕之后就可以锁定目标结点p。 这里的主要核心思想就是“工作指针后移”,就是先声明一个结点,这个结点与链表的首元结点一致,循环遍历下去。这其实也是很多算法的常用技术。

这里谈到了“工作指针”的概念,后面还会有很多应用。最后附完整的程序:

#include "stdio.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
/* 定义LinkList */
typedef struct Node *LinkList;

/* 初始化顺序线性表 */
Status InitList(LinkList *L)
{
    *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */
    if(!(*L)) /* 存储分配失败 */
    {
        return ERROR;
    }
    (*L)->next=NULL; /* 指针域为空 */

    return OK;
}

/* 初始条件:顺序线性表L已存在。操作结果:返回L中数据元素个数 */
int ListLength(LinkList L)
{
    int i=0;
    LinkList p=L->next; /* p指向第一个结点 */
    while(p)
    {
        i++;
        p=p->next;
    }
    return i;
}

/* 初始条件:顺序线性表L已存在 */
/* 操作结果:依次对L的每个数据元素输出 */
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        visit(p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

Status visit(ElemType c)
{
    printf("-> %d ",c);
    return OK;
}

/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果:用e返回L中第i个数据元素的值 */
Status GetElem(LinkList L,int i,ElemType *e)
{
	int j;
	LinkList p;		/* 声明一结点p */
	p = L->next;		/* 让p指向链表L的第一个结点 */
	j = 1;		/*  j为计数器 */
	while (p && j < i)  /* p不为空或者计数器j还没有等于i时,循环继续 */
	{
		p = p->next;  /* 让p指向下一个结点 */
		++j;
	}
	if ( !p || j>i )
		return ERROR;  /*  第i个元素不存在 */
	*e = p->data;   /*  取第i个元素的数据 */
	return OK;
}

/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L), */
/* 操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1 */
Status ListInsert(LinkList *L,int i,ElemType e)
{
	int j;
	LinkList p,s;
	p = *L;     /* 声明一个结点 p,指向头结点 */
	j = 1;
	while (p && j < i)     /* 寻找第i个结点 */
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)
		return ERROR;   /* 第i个元素不存在 */
	s = (LinkList)malloc(sizeof(Node));  /*  生成新结点(C语言标准函数) */
	s->data = e;
	s->next = p->next;      /* 将p的后继结点赋值给s的后继  */
	p->next = s;          /* 将s赋值给p的后继 */
	return OK;
}

/* 初始条件:顺序线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果:删除L的第i个数据元素,并用e返回其值,L的长度减1 */
Status ListDelete(LinkList *L,int i,ElemType *e)
{
	int j;
	LinkList p,q;
	p = *L;
	j = 1;
	while (p->next && j < i)	/* 遍历寻找第i个元素 */
	{
        p = p->next;
        ++j;
	}
	if (!(p->next) || j > i)
	    return ERROR;           /* 第i个元素不存在 */
	q = p->next;
	p->next = q->next;			/* 将q的后继赋值给p的后继 */
	*e = q->data;               /* 将q结点中的数据给e */
	free(q);                    /* 让系统回收此结点,释放内存 */
	return OK;
}

int main()
{
    LinkList L;
    Status i;
    int j,k,pos;
    char opp;
    ElemType e;

    i=InitList(&L);
    printf("链表L初始化完毕,ListLength(L)=%d\n",ListLength(L));

    printf("\n1.遍历操作 \n2.插入操作 \n3.删除操作 \n4.获取结点数据 \n0.退出 \n请选择你的操作:\n");
    while(opp != '0'){
        scanf("%c",&opp);
        switch(opp){
            case '1':
                ListTraverse(L);
                printf("\n");
                break;

            case '2':
                srand((unsigned)time(NULL));
                for(j=1;j<=10;j++)
                {
                    i=ListInsert(&L,1,rand()%100);
                }
                printf("在L的表头依次插入10个随机数后:\n");
                ListTraverse(L);
                printf("\n");
                break;

            case '3':
                printf("要删除第几个元素?");
                scanf("%d",&pos);
                ListDelete(&L,pos,&e);
                printf("删除第%d个元素成功,现在链表为:\n", pos);
                ListTraverse(L);
                printf("\n");
                break;

            case '4':
                printf("你需要获取第几个元素?");
                scanf("%d",&pos);
                GetElem(L,pos,&e);
                printf("第%d个元素的值为:%d\n", pos, e);
                printf("\n");
                break;

            case '0':
                exit(0);
        }
    }

}

延伸阅读

此文章所在专题列表如下:

  1. 第01话:线性表的概念与定义
  2. 第02话:线性表的抽象数据类型ADT定义
  3. 第03话:线性表的顺序存储结构
  4. 第04话:线性表的初始化
  5. 第05话:线性表的遍历、插入操作
  6. 第06话:判断线性表是否为空与置空操作
  7. 第07话:线性表的查找操作
  8. 第08话:线性表删除某个元素
  9. 线性表顺序存储的优缺点
  10. 线性表链式存储结构的由来与基本概念
  11. 单链表的头指针、头结点与首元结点
  12. 单链表的结构体定义与声明
  13. 单链表的初始化
  14. 单链表的插入与遍历操作
  15. 单链表的删除某个元素的操作
  16. 获取单链表中的指定位置的元素
  17. 查找某数在单链表中的位置
  18. 用头插法实现单链表整表创建
  19. 用尾插法实现单链表整表创建
  20. 将单链表重置为空表
  21. 单链表反转/逆序的两种方法
  22. 单链表反转/逆序的第三种方法
  23. 求单链表倒数第N个数
  24. 用标尺法快速找到单链表的中间结点
  25. 如何判断链表是否有环的存在
  26. 单链表建环,无环链表变有环
  27. 删除单链表中的重复元素

本文地址:http://www.nowamagic.net/librarys/veda/detail/2225,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2225

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《C专家编程》 林登 (LinDen.P.V.D) (作者), 徐波 (译者)

《C专家编程》展示了最优秀的C程序员所使用的编码技巧,并专门开辟了一章对C++的基础知识进行了介绍。书中C的历史、语言特性、声明、数组、指针、链接、运行时、内存以及如何进一步学习C++等问题进行了细致的讲解和深入的分析。全书撷取几十个实例进行讲解,对C程序员具有非常高的实用价值。《C专家编程》可以帮助有一定经验的C程序员成为C编程方面的专家,对于具备相当的C语言基础的程序员,《C专家编程》可以帮助他们站在C的高度了解和学习C++。

更多计算机宝库...