查找元素（线性表实训）

78 阅读 0 评论 52 点赞

我是靠谱客的博主内向镜子，最近开发中收集的这篇文章主要介绍查找元素（线性表实训），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在线性表中查找特定元素是线性表的常用操作之一。要求补全函数search，实现在一个链表中搜索包含指定数据的结点。如果链表中有多个结点包含该数据，则返回第一个。

相关知识

由于链表结点都是动态内存分配得到的，在内存中不是连续存储，没法使用二分法之类的算法来实现信息检索，但可以使用顺序查找的方法。
顺序查找需要遍历整个链表，逐个检查每个结点是否满足条件。程序中的printList函数已实现了遍历功能，可以参照其来实现查找函数。其中printList函数的实现代码如下：

// 函数printList：输出链表，每个数据之间用一个空格隔开
// 参数：h-链表头指针
void printList(node *h)
{
    cout << "List:";
    while(h)
    {// h为真，即h指向的结点存在，则输出该结点的数据
        cout << " " << h->data;  // 输出结点数据
        h=h->next;  // 将该结点的指针域赋值给h，h就指向了下一个结点
    }
    cout << endl; // 输出换行符
}

#include <iostream>
//#include "linearList.h"
using namespace std;
// 定义结点结构
struct node
{
    int data;  // 数据域
    node * next;  // 指针域,指向下一个结点
};
// 函数search：在链表中查找包含数据num的结点
// 参数：h-链表头指针，num-要查找的数据
// 返回值：找到了返回该结点的地址，否则返回NULL
node * search(node * h, int num);
// 函数insertSort：链表排序插入
// 参数：h-链表头指针，t-指向要插入的结点
// 返回值：插入结点后链表的首结点地址
node * insertSort(node *h, node *t);
// 函数insertHead：链表头部插入
// 参数：h-链表头指针，t-指向要插入的结点
// 返回值：插入结点后链表的首结点地址
node * insertHead(node *h, node *t);
// 函数printList：输出链表，每个数据之间用一个空格隔开
// 参数：h-链表头指针
void printList(node *h);
// 函数insertTail：链表尾部插入
// 参数：h-链表头指针，t-指向要插入的结点
// 返回值：插入结点后链表的首结点地址
node *insertTail(node *h, node *t);
// 函数delList：删除链表，释放空间
// 参数：h-链表头指针
void delList(node *h);
int main()
{
 int n,i,num;
 node *t;
 node *head=NULL; //头指针为NULL，表示线性表为空，结点数为0
 //输入结点数
 cin>>n;
 for(i=0;i<n;i++)
 {
  //为新节点动态分配空间
  t = new node;
  cin>>t->data; //输入结点数据
  t->next=NULL;  //结点指针域值为空
  //构建有序链表
  head = insertSort(head, t);
 }
 //输入要查找的数
 cin>>num;
 //在链表中查找num
 node *np = search(head,num);
 //输出从np开始的后半截链表（如果np为NULL，则输出空链表）
 printList(np);
 //删除结点，释放空间
 delList(head);
 return 0;
}
//函数delList：删除链表，释放空间
//参数：h-链表头指针
void delList(node *h)
{
 node *p=h; //指针p指向头结点，第一个要删除的结点
 while(p) //这个结点是存在的
 {
  h = h->next; //头指针h指向下一个结点（下一个结点的地址存在当前结点的指针域中，即h->next中
  delete p; //删除p指向的结点
  p = h; //p指向当前的头结点，即下一个要删除的结点
 }
}
//函数printList：输出链表，每个数据之间用一个空格隔开
//参数：h-链表头指针
void printList(node *h)
{
 cout<<"List:"; 
 while(h)
 {//h为真，即h指向的结点存在，则输出该结点的数据
  cout<<" "<<h->data;  //输出结点数据
  h=h->next;  //将该结点的指针域赋值给h，h就指向了下一个结点
 }
 cout<<endl; //输出换行符
}
//函数insertTail：链表尾部插入
//参数：h-链表头指针，t-指向要插入的结点
//返回值：插入结点后链表的首结点地址
node *insertTail(node *h, node *t)
{
 if(h==NULL) //空链表单独处理
 {
  t->next=NULL; //链表尾指针置为NULL
  return t; //返回第一个结点的地址（即链表头指针）
 }
 //非空链表的情况
 node *p=h;
 //让p指向最后一个结点
 while(p->next)
 {
  p=p->next;
 }
 p->next = t; //让最后一个结点的指针域指向结点t
 t->next=NULL; //链表尾指针置为NULL
 return h;  //返回第一个结点的地址（即链表头指针）
}
//函数insertHead：链表头部插入
//参数：h-链表头指针，t-指向要插入的结点
//返回值：插入结点后链表的首结点地址
node * insertHead(node *h, node *t)
{
 t->next=h;
 return t;
}
//函数insertSort：链表排序插入
//参数：h-链表头指针，t-指向要插入的结点
//返回值：插入结点后链表的首结点地址
node * insertSort(node *h, node *t)
{
      node *p=NULL,*q=h; //定位第一个插入点：链首
      while(q && q->data<t->data) //查找插入点
      {//两个指针并行后移
            p=q;
            q=q->next;
      }
      if(p==NULL) //插入链首
      {
            t->next = h;
            return t;
      }
      if(q==NULL) //插入链尾
      {
            p->next = t;
  	    t->next = NULL;
  	    return h;
      }
      //插入p、q之间
      t->next=q;
      p->next=t;
      return h;
}
node * search(node * h, int num)
{
    while(h)
    {// h为真，即h指向的结点存在
        if(h->data == num)
        {
              return h;
        } 
        h = h->next;  // 将该结点的指针域赋值给h，h就指向了下一个结点
    }
    return NULL; // 没找到包含num的结点
}