天使丶无情吧 关注:22贴子:2,050
  • 12回复贴,共1

实验一 线性表(一) 实验目的掌握线性表的顺序存储掌握线性表

只看楼主收藏回复

实验一 线性表
(一) 实验目的
掌握线性表的顺序存储
掌握线性表的链式存储
掌握基本算法(建表、插入、删除)的实现
(二) 实验内容
实现单链表的基本操作,必须包括初始化链表(元素为空)、销毁链表、求表长、查找、插入、删除、遍历(打印)等操作。请编写程序,实现上述单链表的基本操作。
注意:1.节点结构如下定义
2.可使用带头结点的单链表
template <class DataType>
struct Node
{
DataType data;
Node<DataType> *next;
};
提示代码:
编写LinkedList.h头文件实现单链表的基本操作
//定义单链表节点结构
template <class DataType>
struct Node{
DataType data;
Node *next;
};
template <class DataType>
class LinkList
{
public:
LinkList( );
LinkList(DataType a[ ], int n);


来自Android客户端1楼2020-11-05 13:32回复
    ~LinkList( );
    int Length( );
    DataType Get(int i);
    int Locate(DataType x);
    void Insert(int i, DataType x);
    DataType Delete(int i);
    DataType Deletev(DataType x);
    void PrintList();
    private:
    Node<DataType> *first;
    };
    template <class DataType>
    LinkList<DataType>::LinkList()//无参构造方法
    {
    first=new Node<DataType>();
    first->next=NULL;
    }
    template <class DataType>
    LinkList<DataType> :: LinkList(DataType a[ ], int n)
    {
    first = new Node<DataType>; //生成头结点
    Node<DataType> *r = first;
    Node<DataType> *s;
    for (int i = 0; i < n; i++)
    {
    s = new Node<DataType>; s->data = a[i];
    r->next = s; r = s;
    }
    r->next = NULL;
    }
    template <class DataType>
    void LinkList<DataType> :: PrintList()
    {
    Node<DataType> *p;
    p = first->next;
    while (p != NULL)
    {
    cout<<p->data<<" ";
    p=p->next;
    }
    cout<<endl;
    }


    来自Android客户端2楼2020-11-05 13:32
    回复
      template <class DataType>
      int LinkList<DataType> :: Length()
      {
      Node<DataType> *p;
      p = first->next; int count = 0;
      while (p != NULL)
      {
      count++;
      p=p->next;
      }
      return count; //退出循环表明查找失败
      }
      template <class DataType>
      DataType LinkList<DataType> :: Get(int i )
      {
      Node<DataType> *p;
      p = first->next; int count = 0;
      while (p != NULL)
      {
      count++;
      if(count==i) return p->data;
      p=p->next;
      }
      return 0; //退出循环表明查找失败
      }
      template <class DataType>
      int LinkList<DataType> :: Locate(DataType x)
      { Node<DataType> *p;
      p = first->next; int count = 1;
      while (p != NULL)
      {
      if (p->data == x) return count; //查找成功,返回序号
      p = p->next;
      count++;
      }
      return 0; //退出循环表明查找失败
      }
      template <class DataType>
      void LinkList<DataType> :: Insert(int i, DataType x)
      { Node<DataType> *p;
      p = first ; int count = 0; //工作指针p应指向头结点
      while (p != NULL && count < i - 1) //查找第i – 1个结点
      {
      p = p->next;


      来自Android客户端3楼2020-11-05 13:33
      回复
        count++;
        }
        if (p == NULL) throw "位置"; //没有找到第i – 1个结点
        else {
        Node<DataType> *s = new Node<DataType>; s->data = x; //申请一个结点s
        s->next = p->next; p->next = s; //结点s插入结点p之后
        }
        }
        template <class DataType>
        DataType LinkList<DataType> :: Delete(int i)
        { Node<DataType> *p;
        Node<DataType> *q;
        p = first ; int count = 0;
        while (p != NULL && count < i - 1)
        {
        p = p->next;
        count++;
        }
        if (p == NULL || p->next == NULL) throw "无此位置";
        else {
        q = p->next; DataType x = q->data;
        p->next = q->next;
        delete q; return x;
        }
        }
        template <class DataType>
        DataType LinkList<DataType> :: Deletev(DataType x)
        {
        int loc= Locate(x);
        if (loc==0)
        {
        throw "链表中无此数据";
        }
        else
        {
        return Delete(loc);
        }
        return 0;
        }


        来自Android客户端4楼2020-11-05 13:33
        回复
          template <class DataType>
          LinkList<DataType> :: ~LinkList( )
          { Node<DataType> *q;
          while (first != NULL)
          {
          q = first;
          first = first->next;
          delete q;
          }
          }
          测试test.cpp 测试单链表的功能:
          #include <iostream>
          #include "LinkedList.h"
          using namespace std;
          const MAX=100;
          int main( ) {
          cout<<"输入正数数据构造单链表,并以负数作为结束标记\n";
          float a[MAX];
          int i=0,k=0;
          cin>>k;
          while(k>0)
          {
          a[i++]=k;
          cin>>k;
          }
          LinkList<float> list(a,i);
          int choice=1;
          cout<<" 欢迎,欢迎!"<<endl;
          cout<<"1.显示链表中的信息\n";
          cout<<"2.按位置删除数据\n";
          cout<<"3.按值删除数据\n";
          cout<<"4.查找数据的位置信息\n";
          cout<<"5.在链表的某个位置插入数据\n";
          cout<<"6.读取某位置上的信息\n";
          cout<<"0.退出程序\n";
          cout<<"请输入您的选择:";
          cin>>choice;
          while(1){
          switch (choice){
          case 0: exit(0);//退出程序
          case 1:
          {
          cout<<"链表详细信息:\n";
          list.PrintList();break;}


          来自Android客户端5楼2020-11-05 13:33
          回复
            case 2:
            {cout<<"输入要删除的数据的位置?\n";
            int del;
            cin>>del;
            try
            {list.Delete(del);
            }catch(char *s){cout<<s<<endl;}
            break;}
            case 3:
            {cout<<"输入要删除的数据?\n";
            int del;
            cin>>del;
            try{
            list.Deletev(del);}catch(char *s) {cout<<s<<endl;}break;}
            case 4:
            {if(list.Length()==0)
            {cout<<"链表为空,不能查找\n";}
            else{
            cout<<"请输入要查找数据为?";
            float search;
            cin>>search;
            cout<<"数据"<<search<<"在链表中的位置是"<<list.Locate(search)<<endl;
            } break;}
            case 5:
            {cout<<"输入要添加的数据?";
            int des;
            float it;
            cin>>it;
            cout<<"想让该数据存储为第几个节点?";
            cin>>des;
            if((des>list.Length())||des<1)
            cout<<"输入位置错误\n";
            else
            list.Insert(des, it);break;}
            case 6:
            {cout<<"想读取第几个节点?";
            int c;
            cin>>c;
            if(c<1||c>list.Length())
            cout<<"位置不合法\n";
            else
            cout<<"链表中的位置"<<c<<"的数据是:"<<list.Get(c)<<endl;
            break;


            来自Android客户端6楼2020-11-05 13:34
            回复
              }
              default :cout<<"输入错误!\n";
              }
              cout<<"\n1.显示链表中的信息\n";
              cout<<"2.按位置删除数据\n";
              cout<<"3.按值删除数据\n";
              cout<<"4.查找数据的位置信息\n";
              cout<<"5.在链表的某个位置插入数据\n";
              cout<<"6.读取某位置上的信息\n";
              cout<<"0.退出程序\n";
              cout<<"请输入您的选择:";
              cin>>choice;
              }
              return 0;
              }


              来自Android客户端7楼2020-11-05 13:34
              回复
                实验一 线性表的操作
                实验类型:验证性
                实验要求:必修
                实验学时: 2学时
                一、实验目的:
                参照给定的线性表顺序表类和链表类的程序样例,验证给出的线性表的常见算法。
                二、实验要求:
                1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。
                2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
                三、实验内容:
                题目一.设计一个静态数组存储结构的顺序表类,要求编程实现如下任务:建立一个线性表,首先依次输人数据元素1,2,3,…,10,然后删除数据元素6,最后依次显示当前线性表中的数据元素。要求采用顺序表实现,假设该顺序表的数据元素个数在最坏情况下不会超过50个。
                题目二、设有线性表LA=(3,5,8,11),LB=(2,6,8,9,11,15,20);要求用顺序表实现.
                若LA和LB分别表示两个集合A和B,求新集合A=A∪B(相同元素保留)预测输出LA=(2,3,5,6,8,8,9,11,11,15,20)
                四、程序样例
                顺序表类定义:将该类保存在文件SeqList.h中。
                const int MaxSize=100;
                template <class T> //模板类
                class SeqList
                {
                public:
                SeqList() {length=0;} //无参构造函数
                SeqList(T a[],int n); //有参构造函数
                ~SeqList(){} //析构函数
                int Length() {return length;} //求线性表长度
                T Get(int i); //按位查找
                int Locate(T x); //按值查找
                void Insert (int i, T x); // 插入函数
                T Delete(int i); //删除函数
                void PrintList(); //遍历线性表,按序号依次输出各个元素。
                private:
                T data[MaxSize];
                int length;
                };


                来自Android客户端8楼2020-11-05 13:35
                回复
                  template<class T>
                  SeqList<T>::SeqList(T a[],int n) //有参构造函数
                  {
                  if(n>MaxSize)throw"参数非法";
                  for(int i=0;i<n;i++)
                  data[i]=a[i];
                  length=n;
                  }
                  template <class T>
                  void SeqList<T>::Insert(int i,T x) //插入函数
                  {
                  if (length>=MaxSize) throw "上溢";
                  if(i<1||i>length+1) throw "位置异常";
                  for (int j=length;j>=i;j--)
                  data[j]=data[j-1];
                  data[i-1]=x;
                  length++;
                  }
                  template <class T>
                  T SeqList<T>::Get(int i) //按位查找函数
                  {
                  if(i<1||i>length) throw "查找位置非法";
                  else return data[i-1];
                  }
                  template <class T>
                  int SeqList<T>::Locate(T x) //按值查找函数
                  {
                  for (int i=0;i<length;i++)
                  if (data[i]==x)return i+1;
                  return 0;
                  }
                  template <class T>
                  T SeqList<T>::Delete(int i) //删除函数
                  {
                  if (int length=0)throw "下溢";
                  if(i<1||i>length)throw "位置异常";
                  T x=data[i-1];
                  for(int j=i;j<length;j++)
                  data[j-1]=data[j];
                  length--;
                  return x;


                  来自Android客户端9楼2020-11-05 13:36
                  回复
                    }
                    template<class T>
                    void SeqList<T>::PrintList() // 遍历线性表
                    {
                    for (int i=0;i<length;i++)
                    cout<<data[i]<<" ";
                    cout<<endl;
                    }
                    第一题测试:
                    #include <iostream>
                    #include "SeqList.h"
                    using namespace std;
                    void menu()
                    {
                    cout<<" 欢迎,欢迎!"<<endl;
                    cout<<" 1.插入查询"<<endl;
                    cout<<" 2.删除函数"<<endl;
                    cout<<" 3.求表长"<<endl;
                    cout<<" 4.按值查找"<<endl;
                    cout<<" 5.按位查找"<<endl;
                    cout<<" 6.遍历线性表"<<endl;
                    cout<<" 7.退出"<<endl;
                    cout<<" "<<endl;
                    cout<<" 请选择编号:"<<endl;
                    }
                    int main()
                    {
                    int i,j,x;
                    int a[7]={12,15,24,56,67,68,86};
                    SeqList<int> s1(a,7);
                    int flag=1;
                    while(flag)
                    {
                    menu();
                    cin>>j;
                    switch(j)
                    {
                    case 1:
                    {
                    try


                    来自Android客户端10楼2020-11-05 13:36
                    回复
                      {
                      cout<<"显示要插入的位序及数值:"<<endl;
                      cin>>i>>x;
                      cout<<endl;
                      s1.Insert(i,x);
                      s1.PrintList();
                      }
                      catch (char *s){cout<<s<<endl;}
                      };
                      break;
                      case 2:
                      {
                      try
                      {
                      cout<<"输入元素所在位置";
                      cin>>i;
                      x=s1.Delete(i);
                      cout<<"已删除:"<<x<<endl;
                      cout<<"删除数据后表变为:"<<endl;
                      s1.PrintList();
                      }
                      catch (char *s){cout<<s<<endl;}
                      };
                      break;
                      case 3:
                      {
                      try
                      {
                      s1.Length();
                      cout<<"线性表长度为:"<<s1.Length()<<endl;
                      }
                      catch(char *s){cout<<s<<endl;}
                      };
                      break;
                      case 4:
                      {
                      try
                      {
                      cout<<"输入查找数据x:"<<endl;
                      cin>>x;
                      s1.Locate(x);
                      cout<<"所查数据在第"<<s1.Locate(x)<<"位"<<endl;
                      }
                      catch(char *s){cout<<s<<endl;}


                      来自Android客户端11楼2020-11-05 13:37
                      回复
                        };
                        break;
                        case 5:
                        {
                        try
                        {
                        cout<<"查找位置i=";
                        cin>>i;
                        s1.Get(i);
                        cout<<"该位置元素为:"<<s1.Get(i)<<endl;
                        }
                        catch(char *s){cout<<s<<endl;}
                        };
                        break;
                        case 6:
                        {
                        try
                        {
                        s1.PrintList();
                        }
                        catch(char *s){cout<<s<<endl;}
                        };
                        break;
                        case 7:
                        flag=0;
                        break;
                        default:cout<<"错误!!!"<<endl;
                        break;
                        }
                        }
                        return 0;
                        }
                        第二题代码:
                        #include <iostream>
                        #include "SeqList.h"
                        using namespace std;
                        void MergeList(SeqList<int> A,SeqList<int> B, SeqList<int> &C)
                        {


                        来自Android客户端12楼2020-11-05 13:37
                        回复
                          int i=1,j=1,k=0;
                          int n3=A.Length()+B.Length();
                          int c[MaxSize];
                          while (i <= A.Length() && j<= B.Length())
                          {
                          if(A.Get(i) <= B.Get(j))
                          c[k++] = A.Get(i++);
                          else
                          c[k++] = B.Get(j++); }
                          while(i <= A.Length()) //表示B链表已经全部归入C中去了,而A还有剩余
                          c[k++] = A.Get(i++); //将A链表剩下的值,逐一归入链表C
                          while(j <= B.Length()) //表示A链表已经全部归入C中去了,而B还有剩余,
                          c[k++] = B.Get(j++); //将B链表剩下的值,逐一归入链表C
                          SeqList<int> LC(c,n3);
                          C=LC;
                          }
                          //测试 MergeList
                          void main()
                          {
                          int n1,n2;
                          cout<<"请输入链表A的长度:"<<endl;
                          cin>>n1;
                          int a[MaxSize];
                          cout<<"请输入链表A的各个元素:"<<endl;
                          for(int i=0;i<n1;i++)
                          cin>>a[i];
                          cout<<"请输入链表B的长度:"<<endl;
                          cin>>n2;
                          int b[MaxSize];
                          cout<<"请输入链表B的各个元素:"<<endl;
                          for(i=0;i<n2;i++)
                          cin>>b[i];
                          SeqList<int> La(a,n1);
                          SeqList<int> Lb(b,n2);
                          SeqList<int> Lc;
                          MergeList(La,Lb,Lc);
                          Lc.PrintList();
                          }


                          来自Android客户端13楼2020-11-05 13:37
                          回复