昨天完成了单链表ADT的一个功能，就是查找指定位置的元素，很多时候我们也需要，给定一个数，查找这个数是否在单链表中，如果单链表中有，那么它又是第几个元素。今天我们就来解决这个问题。

• 先设计函数，函数名设计为 LocateElem，需要传入的参数有两个，一个数链表 L，还有需要查找的数。

这里也同样需要用到“工作指针”。首先声明一个工作指针，并让它指向链表的首元结点 LinkList p=L->next。参数 L 其实就是头指针，L->next 就是头结点。然后用工作指针遍历链表，当 p->data 与传入的查找数 e 相等，返回其位置即可。

方法体设计如下：

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(LinkList L,ElemType e)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(p->data==e) /* 找到这样的数据元素 */
                return i;
        p=p->next;
    }

    return 0;
}

附完整的可执行程序：

#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已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(LinkList L,ElemType e)
{
    int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(p->data==e) /* 找到这样的数据元素 */
                return i;
        p=p->next;
    }

    return 0;
}

/* 初始条件：顺序线性表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.获取结点数据 \n5.查找某个数是否在链表中 \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 '5':
                printf("输入你需要查找的数：");
                scanf("%d",&pos);
                k=LocateElem(L,pos);
                if(k)
                    printf("第%d个元素的值为%d\n",k,pos);
                else
                    printf("没有值为%d的元素\n",pos);
                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/2228，欢迎访问原出处。