精华内容
下载资源
问答
  • 实习题目:线性表ADT实现之一:线性表ADT基于顺序存储的实现实习目的:帮助学生熟练掌握顺序表的建立及基本操作问题描述:设计一个顺序表并实现对其进行基本操作。基本要求:建立一个顺序表:(1)输入数据;(2)...

    实习题目:线性表ADT实现之一:线性表ADT基于顺序存储的实现

    实习目的:帮助学生熟练掌握顺序表的建立及基本操作
    问题描述:设计一个顺序表并实现对其进行基本操作。
    基本要求:建立一个顺序表:
    (1)输入数据;
    (2)实现数据的插入、删除、搜索、输出等基本操作;
    (3)实现集合的并、交和两个有序顺序表的合并。

     

      测试输入 期待的输出
    测试用例 5
    1 3 5 7 9
    2 10
    10
    9
    22
    6
    1 2 3 4 5 6
    A is created as: 1 3 5 7 9
    After inserted A is 1 10 3 5 7 9
    After deleted A is 1 3 5 7 9
    9 is located at index of 5
    22 is not found
    B is created as: 1 2 3 4 5 6
    A cross B is 1 3 5
    A union B is 1 3 5 7 9 2 4 6

    A union B in sequence is 1 2 3 4 5 6 7 9

    测试数据:

    5  //线性表A的长度
    1 3 5 7 9  //线性表A的数据
    2 10 //表示在第2个位置插入10
    10 //表示删除值=10的数据元素
    9 //查找元素9
    22/ 查找元素22
    6 //线性表B的长度

    1 2 3 4 5 6 

    代码:

     

    #include <stdio.h>
    #include <malloc.h>
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    
    typedef struct
    {
        int *elem,*m;
        int length;
        int listsize;
    } SqList;
    
    int InitList_Sq(SqList &L)
    {
        L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int));
        if(!L.elem)
            return(-1);
        L.length=0;
        L.listsize=LIST_INIT_SIZE;
        return 1;
    }
    
    int Insert_SqList(SqList &L,int i,int x)
    {
        int *p,*q;
        if(i<1||i>L.length+1)
            return(-1);
        if(L.length+1>L.listsize)
        {
            L.m=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
            if(!L.m)
                return(-1);
            L.elem=L.m;
            L.listsize +=LISTINCREMENT;
        }
        q=&(L.elem[i-1]);
        for(p=&(L.elem[L.length-1]); p>=q; --p)
            *(p+1)=*p;
        *q=x;
        ++L.length;
        return 1;
    }
    
    
    //Delete_SqList
    int Delete_SqList(SqList &L,int x) //把x从表中删去
    {
        int index=-1;
        for(int i=0; i<L.length; i++)
        {
            if(L.elem[i]==x)
            {
                index=i;
                break;
            }
        }
        if(index<0)
            return 0;
        for(; index<L.length-1; index++)
        {
            L.elem[index]=L.elem[index+1];
        }
        L.length--;
        return 1;
    }
    
    
    
    int main()
    {
        int i,x,temp;
        int delete_m;
        int search_m,flag_search=0;
        SqList L;
    
        SqList Sum;//※
        InitList_Sq(Sum);//※
    
    
        InitList_Sq(L);
    
        scanf("%d",&x);
    
        for(i=0; i<x; i++)
        {
    
            scanf("%d",&temp);
            Insert_SqList(L,i+1,temp);
            Insert_SqList(Sum,i+1,temp);
    
        }
    
        for(i=0; i<L.length; i++)  //创建后输出
        {
            if(i==0)
            {
                printf("A is created as:");
            }
            printf(" %d",L.elem[i]);
            if(i==L.length-1)
            {
                printf("\n");
            }
        }
    
        //以下为插入操作
    
        scanf("%d",&i);
    
        scanf("%d",&x);
    
        Insert_SqList(L,i,x);
    
        for(i=0; i<L.length; i++)  //插入后输出
        {
            if(i==0)
            {
                printf("After inserted A is");
            }
            printf(" %d",L.elem[i]);
            if(i==L.length-1)
            {
                printf("\n");
            }
        }
    
        //以下为删除操作
        scanf("%d",&delete_m);
        Delete_SqList(L,delete_m);
        for(i=0; i<L.length; i++)
        {
            if(i==0)
            {
                printf("After deleted A is");
            }
            printf(" %d",L.elem[i]);
            if(i==L.length-1)
            {
                printf("\n");
            }
        }
    
        //以下为查找操作
        scanf("%d",&search_m);
        //情况1:找到了 9 is located at index of 5
        //情况2:没找到 22 is not found
        for(int i=0; i<L.length; i++)
        {
            if(search_m==L.elem[i])
            {
                printf("%d is located at index of %d\n",search_m,i+1);
                flag_search=1;
            }
            if((i==L.length-1)&&(flag_search==0))
            {
                printf("%d is not found\n",search_m);
            }
        }
    
        scanf("%d",&search_m);
        flag_search=0;
        for(int i=0; i<L.length; i++)
        {
            if(search_m==L.elem[i])
            {
                printf("%d is located at index of %d\n",search_m,i+1);
                flag_search=1;
            }
            if((i==L.length-1)&&(flag_search==0))
            {
                printf("%d is not found\n",search_m);
            }
        }
    
        //以下是关于B的操作
        SqList B;
        InitList_Sq(B);
        scanf("%d",&x);
        int sum_flag=0;//*
        for(i=0; i<x; i++)
        {
            //printf("Please input nums(%d):\n",i+1);
            scanf("%d",&temp);
            Insert_SqList(B,i+1,temp);
            for(int j=0;j<L.length;j++) //*
            {
                if(temp!=Sum.elem[j])
                    sum_flag++;
            }
            if(sum_flag==L.length)
                Insert_SqList(Sum,L.length+1,temp);//*
            sum_flag=0;
        }
    
    
        for(i=0; i<B.length; i++)  //创建后输出
        {
            if(i==0)
            {
                printf("B is created as:");
            }
            printf(" %d",B.elem[i]);
            if(i==B.length-1)
            {
                printf("\n");
            }
        }
    
        /*B is created as: 1 2 3 4 5 6
          A cross B is 1 3 5
          A union B is 1 3 5 7 9 2 4 6
          A union B in sequence is 1 2 3 4 5 6 7 9 */
        //A corss B:
        printf("A cross B is");
        for(int i=0; i<L.length; i++)
        {
            for(int j=0; j<B.length; j++)
            {
                if(L.elem[i]==B.elem[j])
                {
                    printf(" %d",L.elem[i]);
                }
            }
    
        }
        printf("\n");
    
        //A union B:
        printf("A union B is");
        int flag=0;
        for(int i=0; i<L.length; i++)
        {
            printf(" %d",L.elem[i]);
        }
        for(int i=0; i<B.length; i++)
        {
            for(int j=0; j<L.length; j++)
            {
                if(L.elem[j]==B.elem[i])
                {
                    //printf(" %d",B.elem[i]);
                    break;
                }
                if(L.elem[j]!=B.elem[i])
                {
                    flag++;
                }
    
            }
            if(flag==L.length)
                printf(" %d",B.elem[i]);
            flag=0;
        }
        printf("\n");
    
        //A union B in sequence:
    
        //A union B in sequence is 1 2 3 4 5 6 7 9 */
        temp=0;
        for(int i=0;i<Sum.length;i++)
        {
            for(int j=0;j<Sum.length-1-i;j++)
            {
                if(Sum.elem[j]>Sum.elem[j+1])
                {
                    temp=Sum.elem[j+1];
                    Sum.elem[j+1]=Sum.elem[j];
                    Sum.elem[j]=temp;
                }
            }
        }
        printf("A union B in sequence is");
        for(int i=0;i<Sum.length;i++)
        {
            printf(" %d",Sum.elem[i]);
        }
        printf("\n");
    
        //printf("\n");
        return 0;
    }
    

     

    展开全文
  • 顺序存储结构实现线性表ADT方法一:方法二 线性表是最常见和常用的ADT。假设线性表的元素为整数,请基于顺序存储结构实现线性表ADT。 基本功能包括: (1)建立线性表; 输入有两行,第一行是一个整数n,线性表的...

    顺序存储结构实现线性表ADT


    线性表是最常见和常用的ADT。假设线性表的元素为整数,请基于顺序存储结构实现线性表ADT。
    基本功能包括:
    (1)建立线性表;
    输入有两行,第一行是一个整数n,线性表的长度; 第二行是n和数据元素
    (2)插入:
    输入两个整数,即元素插入的位置和元素值
    (3)删除:
    输入一个整数,即要删除的元素
    (4)搜索:
    输入一个整数,即搜索元素的值
    (5)输出:
    输出线性表的各个元素,空格分开。
    (6)集合的并运算:
    输入创建第二个集合(线性表),完成并运算
    (7)集合的交运算:
    输入创建第二个集合(线性表),完成交运算
    (8)合并两个有序线性表:
    两个有序线性表,合并后仍然有序
    测试数据:
    5 //线性表A的长度
    1 3 5 7 9 //线性表A的数据
    2 10 //表示在第2个位置插入10
    10 //表示删除值=10的数据元素
    9 //查找元素9
    22 / /查找元素22
    6 //线性表B的长度
    1 2 3 4 5 6
    例如:
    输入
    Result
    5
    1 3 5 7 9
    2 10
    10
    9
    22
    6
    1 2 3 4 5 6
    A is created as: 1 3 5 7 9
    After inserted A is 1 10 3 5 7 9
    After deleted A is 1 3 5 7 9
    9 is located at index of 5
    22 is not found
    B is created as: 1 2 3 4 5 6
    A cross B is 1 3 5
    A union B is 1 3 5 7 9 2 4 6
    A union B in sequence is 1 2 3 4 5 6 7 9

    方法一:

    #include <iostream>
    #include <cstdlib>
    
    using namespace std;
    
    typedef int ElemType;
    typedef struct
    {
    ElemType data[105];
    int maxSize;
    int last;
    }PList;
    void Create(PList&l,int n)
    {
        l.last=-1;
        l.maxSize=105;
        for(int i=0;i<n;i++)
        {
            cin>>l.data[i];
            l.last++;
        }
    
    }
    void Input(PList &l)
    {
        for(int i=0;i<=l.last;i++)
        {
            cout<<" "<<l.data[i];
        }
        cout<<endl;
    }
    void Insert(PList & l,int pos,int data)
    {
        if(l.last==l.maxSize-1)
        {
            cerr<<"error"<<endl;
            exit(1);
        }
        if(pos<1||pos-1>l.last+1)
        {
            cerr<<"error"<<endl;
            exit(1);
        }
    
        for(int i=l.last;i>=pos-1;i--)
        {
            l.data[i+1]=l.data[i];
        }
        l.data[pos-1]=data;
        l.last++;
    }
    int  Search(PList &l,int data)
    {
        int i=0;
        while(i<=l.last&&l.data[i]!=data)
        {
            i++;
        }
        if(i>l.last)
        {
            return -1;
        }
        else
        {
            return i+1;
        }
    }
    int Delete(PList&l,int data)
    {
        int pos=Search(l,data);
        if(pos>=0)
        {
        for(int i=pos;i<=l.last;i++)
        {
            l.data[i-1]=l.data[i];
        }
        l.last--;
        return 1;
        }
        return 0;
    
    }
    
    PList cross(PList &A,PList &B)
    {
        PList C;
        Create(C,0);
        int count=1;
      for(int i=0;i<=A.last;i++)
      {
          //cout<<"for"<<endl;
          int temp=A.data[i];
          if(Search(B,temp)>=0)
          {
              Insert(C,count,temp);
              count++;
          }
      }
      return C;
    }
    
    PList Union(PList&A,PList&B)
    {
       // cout<<"enter union"<<endl;
        PList C;
        Create(C,0);
        //cout<<"created"<<endl;
        int count=1;
        int temp;
        for(int i=0;i<=A.last;i++)
        {
            temp=A.data[i];
            //cout<<temp;
            if(Search(C,temp)<=0)
            {
                Insert(C,count,temp);
                count++;
            }
        }
    
        for(int i=0;i<=B.last;i++)
        {
            temp=B.data[i];
             if(Search(C,temp)<=0)
            {
                Insert(C,count,temp);
                count++;
            }
        }//Input(C);
        return C;
    
    }
    PList SortUnion(PList &A,PList &B)
    {
        int indexA=0;
        int indexB=0;
        PList C;
        Create(C,0);
        int count=1;
        int dataA,dataB;
        while(indexA<=A.last&&indexB<=B.last)
        {
            dataA=A.data[indexA];
            dataB=B.data[indexB];
            if(dataA==dataB)
            {
                Insert(C,count,dataA);
                count++;
                indexA++;
                indexB++;
            }
            else if(dataA>dataB)
            {
                Insert(C,count,dataB);
                count++;
                indexB++;
            }
            else
            {
                Insert(C,count,dataA);
                count++;
                indexA++;
            }
        }
    if(indexA<=A.last)
    {
       // cout<<"index"<<indexA<<endl;
        for(int i=indexA;i<=A.last;i++)
        {
            Insert(C,count,A.data[i]);
           // cout<<A.data[i];
            count++;
        }
    }
    if(indexB<=B.last)
    {
         for(int i=indexB;i<=B.last;i++)
        {
            Insert(C,count,B.data[i]);
            count++;
        }
    }
        return C;
    
    }
    int main()
    {
        int n;
        int data;
        cin>>n;
        PList A;
        Create(A,n);
        cout<<"A is created as:";
        Input(A);
        cin>>n>>data;
        Insert(A,n,data);
        cout<<"After inserted A is";
        Input(A);
        cin>>data;
        Delete(A,data);
        cout<<"After deleted A is";
        Input(A);
        cin>>data;
        int temp=Search(A,data);
        if(temp>=0)
        {
            cout<<data<<" is located at index of "<<temp;
        }
        else
        {
            cout<<data<<" is not found";
        }
        cout<<endl;
        cin>>data;
        temp=Search(A,data);
          if(temp>=0)
        {
            cout<<data<<" is located at index of "<<temp<<endl;
        }
        else
        {
            cout<<data<<" is not found"<<endl;
        }
        PList B;
        cin>>n;
        Create(B,n);
         cout<<"B is created as:";
         Input(B);
        PList C;
        C=cross(A,B);
        cout<<"A cross B is";
        Input(C);
        C=Union(A,B);
        cout<<"A union B is";
        Input(C);
        C=SortUnion(A,B);
        cout<<"A union B in sequence is";
        Input(C);
        return 0;
    }
    

    方法二

    #include <iostream>
    #include <stdlib.h>
    
    using namespace std;
    
    typedef int T;
    typedef int ElemType;
    
    class SeqList
    {
    public:
        T *data;
        int MaxSize;
        int last;
        SeqList(int sz);
        ~SeqList(){
            delete []data;
        }
        int Length() const{  //返回元素的个数
            return (last + 1);
        }
        int Search(T &x) const;  //返回元素x在表中的位置
        void Insert(int i, T &x);  //在第i个位置插入元素x
        void Delete(int i);  //删除第i元素
        void Delete1(SeqList &s,T &x);
        int IsEmpty(){  //表空否
            return last == -1;
        }
        int IsFull(){  //判断是否满
            return last == MaxSize-1;
        }
        T GetData(int i){  //获得第i个元素
            return data[i-1];
        }
        //T GetPrior(T &x);  //取x前驱元素
        //T GetNext(T &x);  //取x的后继元素
        void PrintList();  //输出线性表
        SeqList Cross(SeqList &sb);
        SeqList Union(SeqList &sb);
        SeqList SeUnion(SeqList &sb);
    };
    SeqList SeqList::SeUnion(SeqList &sb)
    {
        int m = MaxSize+sb.MaxSize+5;
        SeqList sc(m);
        int d1,d2;
        int i=0;
        int j=0;
        while((i<=last)&&(j<=sb.last))
        {
            d1 = data[i];
            d2 = sb.data[j];
            if(d1 == d2)
            {
                sc.Insert(sc.last+1,d1);
                i++;
                j++;
            }else if(d1 < d2){
                sc.Insert(sc.last+1,d1);
                i++;
            }else{
                sc.Insert(sc.last+1,d2);
                j++;
            }
        }
        if(i<=last){
            for(int q=i; q<=last; q++){
                sc.Insert(sc.last+1,data[q]);
            }
        }
        if(j<=sb.last){
            for(int q=j; q<=sb.last; q++){
                sc.Insert(sc.last+1,data[q]);
            }
        }
        return sc;
    }
    
    
    SeqList SeqList::Union(SeqList &sb)
    {
        int m = MaxSize+sb.MaxSize+5;
        SeqList sc(m);
        for(int i=0; i<=last; i++){
            sc.Insert(sc.last+1,data[i]);
        }
        for(int i=0; i<=sb.last; i++)
        {
            if(sc.Search(sb.data[i])==-1){
                sc.Insert(sc.last+1,sb.data[i]);
            }
        }
        return sc;
    }
    
    SeqList SeqList::Cross(SeqList &sb){
        int m = min(MaxSize,sb.MaxSize);
        SeqList sc(m);
        for(int i=0; i<=last; i++){
            if(sb.Search(data[i])!=-1){
                sc.Insert(sc.last+1,data[i]);
            }
        }
        //sc.PrintList();
        return sc;
    }
    
    void SeqList::Delete1(SeqList &s,T &x){
        if(s.Search(x)==-1){
            cout<<x<<" is not found"<<endl;
        }else{
            s.Delete(s.Search(x)-1);
        }
    }
    //输出线性表
    void SeqList::PrintList()
    {
        int i=-1;
        while(++i < last){
            cout<<data[i]<<" ";
        }
        cout<<data[last]<<endl;
    }
    //构造函数,指定sz定义数组的长度
    SeqList::SeqList(int sz)
    {
        if(sz>0)
        {
            data = new T[sz];  //分配连续空间
            if(data != NULL)
            {
                MaxSize = sz*2;
                last = -1;
            }else{
                cerr<<"存储分配错误!"<<endl;
                exit(1);
            }
        }
    }
    //顺序查找x
    int SeqList::Search(T &x)const
    {
        int i = 0;
        if(last == -1)
            cerr<<"所查询的表为空"<<endl;
        while(i <= last && data[i]!=x)
            i++;
        if(i>last)
            return -1;
        else
            return i+1;
    }
    //插入元素到第i个位置
    void SeqList::Insert(int i, T &x)
    {
        if(last == MaxSize-1)
        {
            cerr<<"顺序表已满,无法插入!"<<endl;
            exit(0);
        }
        if(i<0||i>last+1)
        {
            cerr<<"参数i越界出错!"<<endl;
            exit(1);
        }
        for(int j=last; j>=i; j--){
            data[j+1] = data[j];
        }
        data[i] = x;
        last++;
    }
    //删除第i个元素
    void SeqList::Delete(int i){
        if(i>=0){
            for(int j=i; j<last;j++){
                data[j] = data[j+1];
            }
            last--;
        }else
            cerr<<"下标越界!"<<endl;
    }
    
    int main()
    {
        int n;
        int a0;
        cin>>n;
        SeqList sl(n);
        while(n--){
            cin>>a0;
            sl.Insert(sl.last+1,a0);
        }
        cout<<"A is created as: ";
        sl.PrintList();
        int a1,a2;
        cin>>a1>>a2;
        sl.Insert(a1-1,a2);
        cout<<"After inserted A is ";
        sl.PrintList();
        int a3;
        cin>>a3;
        sl.Delete1(sl,a3);
        cout<<"After deleted A is ";
        sl.PrintList();
        int a4;
        cin>>a4;
        if(sl.Search(a4)==-1){
            cout<<a4<<" is not found"<<endl;
        }else{
            cout<<a4<<" is located at index of "<<sl.Search(a4)<<endl;
        }
        int a5;
        cin>>a5;
        if(sl.Search(a5)==-1){
            cout<<a5<<" is not found"<<endl;
        }else{
            cout<<a5<<" is located at index of "<<sl.Search(a5)<<endl;
        }
        int bn,b0;
        cin>>bn;
        SeqList s2(bn);
        while(bn--){
            cin>>b0;
            s2.Insert(s2.last+1,b0);
        }
        cout<<"B is created as: ";
        s2.PrintList();
        cout<<"A cross B is ";
       // int m = min(sl.MaxSize,s2.MaxSize);
       // SeqList s3(m+5);
        sl.Cross(s2).PrintList();
        cout<<"A union B is ";
        sl.Union(s2).PrintList();
        cout<<"A union B in sequence is ";
        sl.SeUnion(s2).PrintList();
        return 0;
    }
    
    
    
    展开全文
  • 超文本标记语言假设线性表ADT的数据元素类型为正整数,采用带头结点的单链式存储结构。线性表ADT实现的大部分代码已经给出,请补充写出类的两个成员函数insert和reverse。 注意:只需提交需要补充的函数代码,其他...

    题目描述:
    超文本标记语言假设线性表ADT的数据元素类型为正整数,采用带头结点的单链式存储结构。线性表ADT实现的大部分代码已经给出,请补充写出类的两个成员函数insert和reverse。 注意:只需提交需要补充的函数代码,其他代码不能自己重写和修改。

     insert函数:在元素值从小到大有序的线性表中插入一
     个元素,仍然保持有序。
     reverse函数:实现线性表元素的倒置,即将线性表中
     数据元素的顺序反转。
     线性表元素输入时,以 endTag 作为结束标志。
    	
    例如输入: 3 8 7 2 4 9 1 6 5 0
    则输出:9 8 7 6 5 4 3 2 1
    
    预置代码如下: (其中/*   */ 部分是要补充的insert和reverse函数)
    
    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    typedef int ElemType;  //数据元素类型
    class List; //前视定义,否则友元无法定义
    //结点类定义
    class LinkNode
    {  friend  class List; 
       private: 
         LinkNode *link; 
         ElemType data;  
       public: 
         LinkNode (LinkNode *ptr = NULL)    {link=ptr;}
         LinkNode(const ElemType & item, LinkNode *ptr = NULL){  data=item;link=ptr;} 
         ~LinkNode(){}; 
    }; 
    //单链表类定义 
    
    class List   
    
    {  private:    
    
         LinkNode *first; //指向链表头结点的指针          
    
       public:
    
         List (ElemType x) { first = new LinkNode (x);}   // 带头结点
    
         ~List (){ MakeEmpty();}         //析构函数
    
         void MakeEmpty ( );      //线性表置空    
    
         void insert(ElemType val);   //在有序线性表中插入元素val
    
         void reverse();   //线性表的倒置
    
         void output();    //线性表的输出               
    
    }; 
    
    void List:: MakeEmpty ( )
     { LinkNode *q;
       while (  first->link != NULL ) 
    	{ q = first->link;  //指向别摘下结点 
         first->link = q->link;//从链中摘下结点
         delete q;        //释放摘下的结点 
        }
    };	
    void List ::output ( )
    {  LinkNode  *p=first->link; 
       while(p!=NULL)
       { if(p==first->link) cout<<p->data;
    
         else  cout<<" "<<p->data;
         p=p->link;
       }
       cout<<endl;
    }
    /*
    
    **************************************************
    
    请写出 insert 成员函数
    
    **************************************************
    
    **************************************************
    
    请写出 reverse 成员函数
    
    **************************************************
    
    */
    
    int  main()
    {   List list(0);
        ElemType endTag=0;
        ElemType val;
        //下面通过不断读入元素,插入到有序单链表中,建立从小到大的有序单链表
        cin>>val;
        while(val!=endTag) 
         {  list.insert(val);     //在有序表中插入一个元素
    
            cin>>val;  
    
          }
        list.reverse ();   //线性表倒置
        cout<<"The result is:"<<endl;
        list.output ();
        return 0;
    }
    
    

    解题思路:
    1.补全代码insert
    插入排序按照从小到 一边插入一边排序
    2.reverse()
    正序遍历用辅助数组记录数值反序输入原线性表

    实现代码

    void List::insert(ElemType val) {
    	LinkNode *p = new LinkNode(val);
    	LinkNode *tem = first->link;
        LinkNode *pritem = first;//tem的前驱
    	if(first->link == NULL) {
    	//初始adl为空直接插入
    		first->link = p;
    		return;
    	}
    	while(tem && p->data > tem->data) {
    	   插入结点数据大于指针tem指向数据或tem到数据最后
    		pritem = pritem->link;
    		tem =tem->link;
    	}
    	p->link = pritem->link;//插入
    	pritem->link=p;
    }
    
    void List::reverse() {
    	LinkNode *p = first->link;
    	ElemType num=0,*n;
    	while(p!=NULL) {
    		num++;
    		p=p->link;
    	}//确定辅助数组大小
    	p = first->link;
    	n = new ElemType[num]();
    	num = 0;
    	while(p!=NULL)  {
    		n[num] = p->data;//正序记录
    		num++;
    		p = p->link;
    	}
    	p = first->link;
    	for(int i =num-1; i>=0; i-- ) {
    		p->data = n[i];//反序覆盖
    		p=p->link;
    	}
    }
    
    
    展开全文
  • 线性表(一) 线性表ADT+链表入门

    千次阅读 2018-09-20 23:14:20
    线性表ADT中包含的关键设计是对当前位置(current position)的支持,当前位置是指线性表操作(如插入和删除)将会作用的位置。

    线性表ADT设计

    线性表ADT中包含的关键设计是对当前位置(current position)的支持,当前位置是指线性表操作(如插入和删除)将会作用的位置。

    template <typename E> class List
    {
    private:
    	void operator =(const List&) {}
    	List(const List&) {}
    public:
    	List() {}
    	virtual ~List() {}
    	//清空
    	virtual void clear() = 0;
    	//增删
    	virtual void insert(const E& item) = 0;
    	virtual void append(const E& item) = 0;
    	virtual E remove() = 0;
    	//移动
    	virtual void moveToStart() = 0;
    	virtual void moveToStart() = 0;
    	virtual void moveToPos(int pos) = 0;
    	virtual void prev() = 0;
    	virtual void next() = 0;
    	//表的属性及内容
    	virtual int length() const = 0;
    	virtual const E& getValue() const = 0;
    	//被const修饰的常成员函数,在其中不得修改类中任何数据成员的值
    };
    

    使用线性表模板实现的查找函数

    bool find(List<int>& L, int K)
    {
    	int it;
    	for (L.moveToStart(); L.currPos() < L.length(); L.next())
    	{
    		it = L.getvalue();
    		if (K == it) return true;
    	}
    	return false;
    }
    

    注:尽管这个find函数可以改成模板的形式,从而可以处理不同的数据类型,但是依然会收到限制。具体来说,只有当线性表中元素的数据类型和待查元素的数据类型相同时,并且在该数据类型重载了等价运算符 “ == ” 的情况下,该函数才能工作。

    顺序表

    template <typename E>
    class Alist : public List<E>
    {
    private:
    	int maxSize;
    	int listSize;
    	int curr;
    	E* listArray; //首地址
    
    public:
    	AList(int size = defaultSize)
    	{
    		maxSize = size;
    		listSize = curr = 0;
    		listArray = new E[maxSize]; //初始化并分配内存空间
    	}
    	}
    	~AList() { delete[] listArray; }
    
    	void clear()
    	{
    		delete[] listArray;
    		listSize = curr = 0;
    		listArray = new E[maxSize];
    
    	void insert(const E& it)
    	{
    		Assert(listSize < maxSize, "List capacity exceeded");
    		for (int i = listSize; i > curr; i--)
    			listArray[i] = listArray[i - 1];
    		listArray[curr] = it;
    		listSize++;
    	}
    	...
    };
    

    AList继承了List类,需要实现其所有虚函数。从insert函数可以看出,实现AList的关键点在于“当前存储量”和“当前位置”的维护。

    单链表

    相对于顺序表的物理上的强制顺序存储,链表是由一个个自定义的结点组织而成,不强制物理上的连续性,因此在插入、删除操作上更加灵活,效率更高

    单链表结点类Link定义
    template <typename E> class Link
    {
    public:
    	E element; //数据域
    	Link *next; //指针域
    	// 表中结点创建
    	Link(const E& elemval, Link* nextval = NULL)
    	{
    		element = elemval;
    		next = nextval;
    	}
    	// 表头结点创建
    	Link(Link* nextval = NULL)
    	{
    		next = nextval;
    	}
    };
    

    注:这个Link结点的定义十分重要,我们在以后介绍其他线性结构时都会遇到它!

    单链表实现:
    template <typename E> class LList : public List<E>
    {
    private:
    	Link<E>* head;
    	Link<E>* tail;
    	Link<E>* curr;
    	int cnt;
    
    	void init()
    	{
    		curr = tail = head = new Link<E>;
    		cnt = 0;
    	}
    
    	void removeall()
    	{
    		while (head != NULL)
    		{
    			curr = head;
    			head = head->next;
    			delete curr; //一切操作都是对当前位置的操作
    		}
    	}
    
    public:
    	LList(int size = defaultSize) { init(); }
    	~LList() { removeall(); }
    	void clear() { removeall(); init(); }
    
    	// 关键函数实现
    	void insert(const E& it)
    	{
    
    	}
    
    	void append(const E& it)
    	{
    		
    	}
    
    	E remove()
    	{
    
    	}
    
    	void moveToStart()
    	{ }
    
    	void moveToEnd()
    	{ }
    
    	void prev() //前驱
    	{
    
    	}
    
    	void next() //后继
    	{
    
    	}
    
    	void moveToPos(int pos)
    	{
    
    	}
    
    	// 链表当前相关参数
    	int length() const { return cnt; }
    
    	int currPost() const 
    	{
    		Link<E>* temp = head;
    		int i;
    		for (int i = 0; curr != temp; i++)
    			temp = temp->next;
    		return i;
    	}
    
    	const E& getValue() const //Return current element
    	{
    		Assert(curr->next != NULL; "No value");
    		return curr->next->element;
    	}
    };
    

    1. 为了操作的便利性以及考虑对特殊情况的一致性处理,本例的设计考虑了如下两个策略:
      i) 让curr指针指向当前元素的前一个元素
      ii) 增加特殊的表头结点
    2. 单链表的实现关键在于对于head,tail,curr指针的维护
    3. 在关键函数的实现上需要考虑特殊情况的处理,本文一下内容将对于这些函数的具体实现做一个探讨
    insert函数实现

    链表插入元素操作详细过程
    由图可知,insert的操作分为三步:

    1. 创建新结点
    2. 将新结点的指针指向当前位置
    3. 断开当前位置的前驱与当前位置结点的指针并将当前位置的前驱结点的指针指向新结点

    下面来考虑代码:
    首先创建结点
    new Link<E>(it)
    然后将新结点指针指向当前位置
    此处由于有前文Link结点类提供的函数我们可以便利的将1,2步合并为一步
    new Link<E>(it, curr->next)
    最后将前驱的指针指向新结点
    curr->next = new Link<E>(it, curr->next)
    然后将cnt++即完成了insert函数的基本实现

    但是此处应思考一个问题,若是当前位置是表尾,这时完成插入操作后表尾指针tail指向了表中最后第二个元素。
    在链表末尾插入元素
    所以应在插入完成后加入如下语句:
    if (tail == curr) tail = curr->next; // New tail

    insert完整实现

    void insert(const E& it)
    {
    	curr->next = new Link<E>(it, curr->next);
    	if (tail == curr) tail = curr->next; // New tail
    	cnt++;
    }
    

    注 remove(), prev()等函数的实现思考方式类似,本文不做实现,留给读者练习。

    对于链表更详尽的讨论,可以参见博主的另一篇博文线性表(三) 链表

    展开全文
  • 假设线性表ADT的数据元素类型为正整数,采用带头结点的单链式存储结构。线性表ADT实现的大部分代码已经给出,请补充写出类的两个成员函数insert和reverse。 注意:只需提交需要补充的函数代码,其他代码不能自己重写...
  • 1 2 3 4 5 6 A cross B is 1 3 5 A union B is 1 3 5 7 9 2 4 6 A union B in sequence is 1 2 3 4 5 6 7 9 测试数据: 0 //线性表输入结束标志 1 3 5 7 9 0 //线性表A的数据 2 10 //表示在第2个位置插入10 10 //...
  • 线性表 ADT的使用 实验2

    千次阅读 2020-04-03 19:02:43
    线性表ADT的使用 ** 声明:我实在是太久没写博客了,突然想来写一个博客来划划水。这个实验二是真的麻烦,(对于我这个蒟蒻来说),写了一个一个小时多,最后写的自己都晕了,还是重新整理了思路才写了出来,希望...
  • 线性表ADT应用 实验二:一元多项式的基本运算 实验目的:掌握用线性表实现一元多项式的基本运算。 实验内容:使用链式存储实现一元多项式的加法、减法、乘法和求导。即: C(x)= A(x)+B(x);C(x)= A(x)-B(x) C(x)= A...
  • 线性表的最简单理解,线性表ADT定义,求两个集合的并集,合并两个集合并且合并之后有序线性表的最简单理解线性表ADT定义求两个集合的并集合并两个集合并且合并之后有序上面只是一个线性表的开端,我想要把线性表详细...
  • 线性表ADT(List)

    千次阅读 2019-06-12 18:29:18
    线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。
  • 实验目的:掌握用线性表实现一元多项式的基本运算。 实验内容:使用链式存储实现一元多项式的加法、减法、乘法和求导。即: C(x)= A(x)+B(x);C(x)= A(x)-B(x) C(x)= A(x)*B(x) C(x)= A’(x) 菜单: 1)C :分别创建...
  • 数据结构及算法(线性表ADT描述)

    千次阅读 2018-11-13 00:08:10
    实习生来总结一下线性表ADT 抽象数据类型核心是确定了数据元素的一组基本操作,这些操作都是定义在相应逻辑结构上之上,与数据元素的数据类型和存储结构无关。设有线性表list,其中数据元素类型为DataType,List的...
  • 1.线性表定义: 线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。 在稍复杂的线性表中,一个数据元素...
  • 线性表

    2021-03-29 16:10:00
    线性表1. 线性表ADT 1. 线性表ADT 形如 A0,A1,A2,…,An−1A_0,A_1,A_2,…,A_{n-1}A0​,A1​,A2​,…,An−1​的一般的线性表。这个表的大小是 NNN。将大小为 000 的特殊的表称为空表。
  • 数据结构线性表ADT

    千次阅读 2011-02-28 20:06:00
    <br />#include <stdio.h><br />#include <stdlib.h><br />  typedef int type; #define LIST_SIZE 100 #define LIST_ADD 10   struct SqList{  type *elem;...
  • 线性表ADT定义(学生信息表)

    千次阅读 2014-09-27 13:14:04
    ADT Class Date  线性表中的数据元素具有相同的
  • /** list.h** Created on: Oct 31, 2010* Author: jenson*/#ifndef LIST_H_#define LIST_H_#define TRUE 1;#define FALSE 0;typedef int elem_type;typedef struct _sq_list * sq_list;#defin...
  • ADT 线性表

    2017-11-12 16:10:00
    线性表的数据对象集合为 {a1, a2, ..., an},每个元素的类型均为 DataType。 其中,除第一个元素 a1 外,每一个元素有且只有一个直接前驱元素, 除了最后一个元素 an 外,每一个元素有且只有一个直接后继元素。 ...
  • C_线性表(ADT)-顺序表的表示和实现

    千次阅读 2017-07-14 14:27:07
    线性表基本操作: 1.InitList(&L) /*操作结果:构造一个空的线性表*/ 2.DestroyList(&L) /*初始条件:线性表L已存在*/ /*操作结果:销毁线性表L*/ 3.ClearList(&L) /*初始条件:线性表L已存在*/ /*操作结果:将L...
  • ADT中串的基本操作: /*操作结果:构造字符串T*/ CreatHString(&T)// /*初始条件:串S存在*/ /*操作结果:由串S复制得串T*/ StrCopy(&T,S); /*初始条件:串S存在。*/ /*操作结果:若S为空串,则返回TRUE...
  • 基于顺序表实现线性表ADT 基于链表实现线性表ADT 实验步骤及遇到问题分析与解决: 一、基于顺序表实现线性表ADT 线性表的物理实现有顺序表与链表两种,顺序表更简单易用,所以先进行线性表顺序表的实现。 思考过程:...
  • /*操作结果:在带头结点的双链循环线性表L中第i个位置之前插入元素e,i的取值为1≤i≤表长+1。*/ Status ListInsert(DuLinkList L,int i,ElemType e) /*初始条件:双链循环线性表L已存在*/ /*操作结果:删除带头结点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 947
精华内容 378
关键字:

线性表adt