精华内容
下载资源
问答
  • 数据结构---线性表应用实例

    千次阅读 2018-09-22 20:07:43
    将顺序表(a1,a2,a3,...,an)重新排列为以a1为界的两部分:a1前面的值均比a1小,后面的值均比a1大(数据类型均具有可比性,都设为整型) #include <stdio.h> #include <stdlib.h> #...

     将顺序表(a1,a2,a3,...,an)重新排列为以a1为界的两部分:a1前面的值均比a1小,后面的值均比a1大(数据类型均具有可比性,都设为整型)

    #include <stdio.h>
    #include <stdlib.h>
    #define maxsize 100
    
    typedef struct  //顺序表结构
    {
        int data[maxsize];
        int last;
    }seqlist;
    
     seqlist *init_seqlist(int arrsize)  //顺序表初始化
     {
         seqlist *L;
         L=(seqlist*)malloc(sizeof(seqlist));
         L->last=arrsize-1;
         return L;
     }
    
    void input(seqlist *L)
    {
        int i;
        for(i=0;i<=L->last;i++)
        {
            scanf("%d",&L->data[i]);
        }
    }
    
    void show(seqlist*L)
    {
        int i;
        for(i=0;i<=L->last;i++)
        {
            printf("%d ",L->data[i]);
        }
    }
    
    void part(seqlist*L)
    {
        int x,y,i,j;
        x=L->data[0];//将基准置入x中
        for(i=1;i<=L->last;i++)//注意i从1开始
        {
            if(L->data[i]<x)
            {
                y=L->data[i];//记录比基准小的数,防止挪位后丢失
                for(j=i-1;j>=0;j--)//该数前的数字向后挪一位
                {
                    L->data[j+1]=L->data[j];
                    L->data[0]=y;//将小的数置入第一个数
                }
            }
        }
    }
    
    int main()
    {
        int arrsize;
        seqlist *L;
        scanf("%d",&arrsize);
        L=init_seqlist(arrsize);
        input(L);
        part(L);
        show(L);
        return 0;
    }

    两个递增有序的单链表A和B,合成链表C,不改变排序性。

    输入输出样例:1组

    • 样例输入:
      5 //A链表元素个数
      2 3 4 10 11 //A链表元素内容,递增有序
      3 //B链表元素个数
      5 6 12 //B链表元素内容,递增有序

    样例输出:

    2 3 4 5 6 10 11 12
    #include <stdio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define maxsize 1000
    typedef struct
    {
        int data[maxsize];
        int last;
    } seqlist;
    
    seqlist *init_seqlist(int arrsize)
    {
        seqlist *L;
        L=(seqlist *)malloc(sizeof(seqlist));
        L->last=arrsize-1;
        return L;
    }
    
    void input(seqlist *A)
    {
        int i;
        for(i=0; i<=A->last; i++)
        {
            scanf("%d",&A->data[i]);
        }
    }
    
    void bubblesort(seqlist *A)//j将表进行冒泡排序
    {
        int i,j,temp;
        for(i=0; i<A->last; i++)
        {
            for(j=i+1; j<A->last+1; j++)
            {
                if(A->data[j]<A->data[i])
                {
                    temp=A->data[j];
                    A->data[j]=A->data[i];
                    A->data[i]=temp;
                }
            }
        }
    }
    
    seqlist * merge(seqlist *A,seqlist *B,seqlist *C)
    {
        int i=0,j=0,k=0;
        while(i<=A->last&&j<=B->last)
        {
            if(A->data[i]<B->data[j])
            {
                C->data[k++]=A->data[i++];
            }
            else
            {
                C->data[k++]=B->data[j++];
            }
        }
        while(i<=A->last)//表B先结束
        {
            C->data[k++]=A->data[i++];
        }
        while(j<=B->last)//表A先结束
        {
            C->data[k++]=B->data[j++];
        }
        C->last=k-1;
        return C;
    }
    
    int main()
    {
        int i,arrsize1,arrsize2;
        seqlist *A,*B,*C;
        C=(seqlist *)malloc(sizeof(seqlist));
        scanf("%d",&arrsize1);
        A=init_seqlist(arrsize1);
        input(A);
        scanf("%d",&arrsize2);
        B=init_seqlist(arrsize2);
        input(B);
        bubblesort(A);
        bubblesort(B);
        C=merge(A,B,C);
        for(i=0;i<=C->last;i++)
        {
            printf("%d ",C->data[i]);
        }
      return 0;
    }
    

    顺序表A中删除值在x~y(x<=y)之间的所有元素。

    输入输出样例:1组

    • 样例输入:
      7 //输入顺序表中结点个数,数组规模可以很大。但是用这个值来指定当前大数组中的前几个用于顺序表中的值
      1 2 3 3 4 4 2 //输入当前顺序表中的元素都有哪些
      3 6 //分别输入x和y的值,即范围
    • 样例输出:
      1 2 2 
      #include <stdio.h>
      #include <stdlib.h>
      #define maxsize 100
      
      typedef struct
      {
          int data[maxsize];
          int last;
      } seqlist;
      
      seqlist *init_seqlist(int arrsize)
      {
          seqlist *L;
          L=(seqlist *)malloc(sizeof(seqlist));
          L->last=arrsize-1;
          return L;
      }
      
      seqlist *result_seqlist(seqlist *L,int x,int y)
      {
          int k=0,j,i;
          seqlist *S;
          S=(seqlist *)malloc(sizeof(seqlist));
      
              if(x==y)
              {
                  for(i=0; i<=L->last; i++)
                  {
                      if(L->data[i]==x)
                      {
                          for(j=i+1; j<=L->last; j++)
                          {
                              L->data[j-1]=L->data[j];
                          }
                          L->last--;i--;
                      }
                      else
                      {
                          S->data[k++]=L->data[i];
                      }
                  }
              }
              else  //x,y不相等
              {
                  for(i=0; i<=L->last; i++)
                  {
                      if(L->data[i]>=x&&L->data[i]<=y) 
                      {
                          for(j=i+1; j<=L->last; j++) //将数据进行向前移一位,即删除在此范围内的数
                          {
                              L->data[j-1]=L->data[j];
                          }
                          L->last--;i--; //表长减一,i减一,从挪位后的新一个数据判断
                      }
                      else
                      {
                          S->data[k++]=L->data[i];
                      }
                  }
      
          }
          S->last=k-1;
          return S;
      }
      
      int main()
      {
          int i,arrsize,x,y;
          seqlist *L,*S;
          scanf("%d",&arrsize);
          L=init_seqlist(arrsize);
          for(i=0; i<=L->last; i++)
          {
              scanf("%d",&L->data[i]);
          }
              scanf("%d %d",&x,&y);
          S=result_seqlist(L,x,y);
          for(i=0; i<=S->last; i++)
          {
              printf("%d ",S->data[i]);
          }
        return 0;
      }
      

      已知带头结点的单链表L中的结点是按整数值递增排列的,试写一算法,将值为x的结点插入到表L中,使得L仍然递增有序(这里我们将插入和排序用一个函数完成,不用排序和插入两个函数实现)

      #include <stdio.h>
      #include <stdlib.h>
      #define maxsize 1000
      typedef struct node
      {
          int data;
          struct lnode *next;
      } LNode,*LinkList;
      
      LinkList init_LNode()
      {
          LinkList L;
          L=(LinkList)malloc(sizeof(LNode));
          L->data=0;
          L->next=NULL;
          return L;
      }
      
      LinkList insert_linklist(LinkList L,int insert_data)
      {
          LNode *p,*q,*s;
          p=L->next;
          q=p;
          while(p!=NULL&&insert_data<p->data)
          {
              q=p;//q记录前驱结点
              p=p->next;
          }
          if(p==NULL)//为空代表走到了最后或表开始为空
          {
              s=(LinkList)malloc(sizeof(LNode));
              s->data=insert_data;
              s->next=NULL;
              q->next=s;
          }
          else
          {
              s=(LinkList)malloc(sizeof(LNode));
              s->data=insert_data;
              s->next=p;
              q->next=s;
          }
          return L;
      }
      
      void output_link(LinkList L)
      {
          LNode *p;
          p=L->next;
          while(p!=NULL)
          {
              printf("%d ",p->data);
              p=p->next;
          }
      }
      
      int main()
      {
          int input_data;
          LinkList L=init_LNode();
          printf("please input the data for the list,100 represent the end\n");
          scanf("%d",&input_data);
          while(input_data!=100)
          {
              L=insert_linklist(L,input_data);
              scanf("%d",&input_data);
          }
          output_link(L);//输入结束,输出该表内容
          printf("please input the insert data:");
          scanf("%d",&input_data);
          L=insert_linklist(L,input_data);
          output_link(L);
          return 0;
      }
      
      

      下面的实例就只写核心过程:

    • 实现单链表的逆置

      typedef struct lnode
      {
          int data;
          struct lnode *next;
      }LNode,*LinkList;
      
      void reverse(LinkList* L)
      {
          LNode *p;
          p=L->next; //p指向第一个数据结点
          L->next=NULL;//将原链表置为空
          while(p)
          {
              q=p;//q为p的前驱结点
              p=p->next;
              q->next=L->next;//头插法实现逆转
              L->nect=q;
          }
      }
      

      删除一链表中的重复结点

      typedef struct lnode
      {
          int data;
          struct lnode *next;
      }LNode,*LinkList;
      
      void put_linklist(LinkList *L)
      {
          LinkList *q,*p,*r;
          p=L->next;//p指向第一个数据结点
          while(p->next)//p作为基准比较
          {
              q=p;
              if(p==NULL)return;
              while(q->next)//q作为待删前驱结点  
              {
                  if(q->next->data==p->data)
                  {
                      r=q->next;//r为待删结点
                      q->next=r->next;
                      free(r);
                  }
                  q=q->next;
              }
              p=p->next;
          }
      }

      有两个单链表A,B,其中元素递增且有序,编写算法将A,B归并成一个按元素之递减(允许有相同值)有序的链表C,要求用A,B中的原结点形成,不能重新申请结点

      typedef struct lnode
      {
          int data;
          struct lnode *next;
      }LNode,*LinkList;
      
      LinkList merge(LinkList A,LinkList B)//设A,B为带头结点的单链表
      {
          LNode *p,*q,*s;LinkList C;
          p=A->next;q=B->next;
          C=A;
          free(B);
          while(p&&q)
          {
              if(p->data<q->data)//从原A,B中取下较小者
              {
                  s=p;p=p->next;
              }
              else
              {
                  s=q;q=q->next;
              }
              s->next=C->next;//插到C的头部
              C->next=s;
          }
          if(p==NULL)p=q;//p已结束
          while(p)//将剩余的结点一个个摘下,插到C表的头部
          {
              s=p;p=p->next;
              s->next=C->next;
              C->next=s;
          }
      }

      将单链表转换为双向循环链表

      typedef struct dlnode
      {
          int data;
          struct dlnode *next,*prior;
      } DLNode,*DLinkList;
      
      DLinkList Creat_DLinkList(LinkList L)
      {
          DLinkList H;
          DLNode *s,,*p,*rear;
          H=(DLNode*)malloc(sizeof(DLNode));//生成H的头结点
          H->next=H;//构造H为空的双向循环链表
          H->prior=H;
          rear=H;
          p=L->next;//p指向L的第一个结点
          while(p)
          {
              s=(DLNode*)malloc(sizeof(DLNode));
              s->data=p->data;//申请、填充结点
              s->next=rear->next;
              s->prior=rear;
              rear->next=s;
              H->prior=s;//结点s插到H的链表尾
              rear=s;//修改H的尾指针rear
              p=p->next;
          }
          return H;
      }

       

     

    展开全文
  • 改写的数据结构综合实验源码。不改变现有单链表类,根据具体应用(如学生管理...作者经过充分测试,考虑了各种异常处理,是一个完整的数据结构应用实例。适用于学习数据结构具体应用的中级水平进阶。欢迎大家交流探讨。
  • 数据结构线性表;2.1 线性表的基本概念;线性表的应用实例;2.2 线性表的顺序存储顺序表;2.2.2 顺序表上的运算及其实现;逻辑功能设计;交互页面的设计;Main函数的设计;2.3 线性表的链式存储单链表; 在单链表中,假定每个...
  • 一、线性表合并 <删除重复元素> La=(7,5,3,11) Lb=(2,6,3) => La=(7,5,3,11,2,6) 算法实现 依次从Lb中去除每个元素:1.在La中查找该元素 2.如果找不到就将其插入La后面 void Union(List &La,...

    一、线性表合并 <删除重复元素>

            La=(7,5,3,11)   Lb=(2,6,3)   =>    La=(7,5,3,11,2,6) 

            算法实现                        

            依次从Lb中去除每个元素:1.在La中查找该元素        2.如果找不到就将其插入La后面

    void Union(List &La,List Lb){
        La_Len=ListLength(La);
        Lb_Len=ListLength(Lb);
        for(i=1;i<=Lb_Len;i++)
        {
            GetElem(Lb,e);
            if(!LocateElem(La,e))     ListInsert(&La,++La_Len,e);
        }
    }

    二、有序表合并 <按序列排序>

            La=(1,7,8)   Lb=(2,4,6,8,10,11)   =>    La=(1,2,4,6,8,8,10,11) 

            算法实现:1.建立空表Lc        2.依次从La或Lb中摘出元素值较小的结点插入到Lc表的最后,直至其变为空表        3.继续讲剩下的表的剩余结点插入Lc后面

            顺序表实现

    void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
        pa=LA.elem;
        pb=LB.elem;
        LC.Length=LA.length+LB.Length;      //指定长度
        LC.elem=new ElemType[LC.length];    //分配空间
        pc=LC.elem;                        //指向第一个元素
        pa_last=LA.elem+LA.length-1;    //LA最后一个元素
        pb_last=LB.elem+LB.length-1;    //LB最后一个元素
    
        while(pa<=pa_Last && pb<=pb_last){//两个表都不为空
            if(*pa<=*pb)                //找出较小值
                *pc++=*pa++;
            else
                *pc++=*pb++;
        }
        while(pa<=pa_Last) *pc++=*pa++;    //继续添加非空表
        while(pb<=pb_Last) *pc++=*pb++;
    }

     

            链表实现

    void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
        pa=LA->next;    pb=LB->next;
        pc=LC=LA;    //用La的头结点作为LC的头结点
        while(pa && pb){
            if(pa->data<=pb->data)
            {
                pc->next=pa;
                pc=pa;
                pa=pa->next;
            }
            else
            {
                pc->next=pb;
                pc=pb;
                pa=pb->next;
            }
        }
        pc->next=pa?pa:pb;    //插入剩余表
        delete LB;//释放lb头结点
    }

     三、案例分析

            1.完成一元多项式的运算:实现多项式的加减乘除

            实现思路:将多项式系数视为线性表

             2.稀疏多项式运算

            使用链表实现(顺序表缺点:空间分配灵活度不高;运算空间复杂程度高)

      

                     算法步骤↓

             3.图书馆管理系统(吐槽:这么大个系统您上个SQL能死啊)

                    略...

     

    展开全文
  • 线性表的合并3.有序表的合并(1)顺序表实现(2)链表实现4.多项式运算5.稀疏多项式运算6.图书信息管理 1.顺序表和链表的比较 2.线性表的合并 3.有序表的合并 (1)顺序表实现 (2)链表实现 (前提是有序...

    1.顺序表和链表的比较

    在这里插入图片描述
    在这里插入图片描述

    2.线性表的合并

    在这里插入图片描述
    在这里插入图片描述

    将lb中的元素取出,一一与la比对,la中没有则插入到表尾,且la表长+1,直到遍历完lb。la和lb共有的元素只取一次。

    3.有序表的合并

    在这里插入图片描述

    有序表的合并相对于线性表会保留两个表重复拥有的元素,故合并后的表长为原来两个表长之和。

    (1)顺序表实现

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    • 1,初始化操作:pa和pb分别指向la和lb的第一个元素,计算新表长度为两表之和,根据lc表长分配数组空间。
    • 2,在两个表均为非空的情况下(根据表头指针以及表长可计算出表尾指针),将两个表头指针指向的数据进行比较,较小的存入lc,并将pc和较小数据的指针都+1。
    • 3,重复上述步骤,直至其中一个表为空时,将另一个表剩余部分依次放入lc中。

    (2)链表实现

    在这里插入图片描述
    (前提是有序链表)

    • 1,两个指针pa,pb指向待操作链表的首元结点,以la的头结点作为lc的的头结点,pc指向lc头结点。
    • 2,当pa和pb都非空时,比较指向结点的data域,将data域较小的结点地址赋给pc指向结点的next域,再移动pc和较小结点指针,直到有一个链表遍历完全。
    • 3,将剩余链表尾部全部插入lc。

    在这里插入图片描述
    空间复杂度为O(1)。

    4.稀疏多项式运算

    多项式的系数存入线性表来进行运算,对于完整记录每一项系数的多项式,求和用顺序表更方便,顺序表对应位置数据相加存入新的顺序表。对于某些次项系数为0的多项式(稀疏多项式),如果将每一项系数存入会浪费空间,故只存系数非零项及相应次数。
    顺序表方式:分别从头遍历两个顺序表

    • 1,指数相同时,指数不变,对应系数相加,和不为零时则将系数和及指数存入新顺序表。
    • 2,指数不同时,将指数较小项复制到新顺序表,继续遍历直至其中一个表为空后,将另一个表剩余部分依次复制到新顺序表。
      存在问题:为提前分配空间时,不确定新的顺序表表长。
      但是有一个缺点

    链表方式
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    经过以上步骤可以获得按指数从小到大顺序排列的两个链表pa,pb。
    直接利用pa的头结点作为新的链表pc的头结点,分别从头遍历两个链表pa,pb。

    • 1,指数相同时(p1->expn=p2->expn),指数不变,对应系数相加;和为零则删除p1,p2所指结点;和不为零时修改p1所指结点的系数为系数和,并删除p2所指结点。
    • 2,指数不同时,将指数较小项插入到链表c的尾部,继续遍历直至其中一个表为空后,将另一个表剩余部分插入到新链表c。最后释放pb的头结点。

    5.图书信息管理系统

    在这里插入图片描述

    经常做插入删除操作或者书目变化大用链表,图书书目变化不大,很少做插入删除操作且经常要通过序号找书就用顺序存储结构。
    在这里插入图片描述

    展开全文
  •  线性表即有限个数据元素的序列,而其顺序存储结构则指的是用一段地址连续的存储单元依次存储线性表中的数据。在高级语言中(如C语言)一般可用一维数组来实现顺序存储结构。 二、元素获取、插入、删除的实现  ...

    文章向导

    线性表及顺序存储结构
    各部分接口的实现
    完整的验证实例
    插入、删除操作的算法时间复杂度

    一、线性表及顺序存储结构
      线性表即有限个数据元素的序列,而其顺序存储结构则指的是用一段地址连续的存储单元依次存储线性表中的数据。在高级语言中(如C语言)一般可用一维数组来实现顺序存储结构。

    二、各部分接口的实现
      定义在一个线性表上的操作有许多,比如初始化、清空、读/写、查找定位、插入/删除等。对于不同的应用,线性表的基本操作是不同的,但对于实际问题中所涉及到的复杂操作,基本上都是由这些基本操作来组合实现。
      这里主要讲解读写、插入、删除三种基本操作的算法实现,现在先在头文件中给出其抽象数据类型的定义。

    #ifndef SQLIST_H
    #define SQLIST_H
    
    #include <stdlib.h>
    
    #define MAXSIZE 10
    
    typedef int ElemType;
    typedef struct
    {
        ElemType data[MAXSIZE]; //存放数据元素
        int length; //线性表的长度
    } SqList;
    
    /*Public Interface*/
    int sqlist_get_elm(SqList list, int get_loc, ElemType* e);
    int sqlist_ins_elm(SqList* list, int ins_loc, ElemType e);
    int sqlist_del_elm(SqList* list, int del_loc, ElemType* e);
    
    #endif
    

    1.获取元素操作

    获取线性表L中某个位置的元素值。
      算法思路:
       - 若未创建线性表或查找位置不合理,则抛出异常;
       - 将查找位置对应的数组元素返回给变量e 。

    /* 函数名:sqlist_get_elm
     *
     * 功能:获取顺序线性表中第get_loc个位置处的元素值(用e返回)
     *
     * 入口参数:
     *         > list: 整个顺序线性表
     *         > get_loc: 待查找的位置
     *         > e: 查找后返回的值
     * 
     * 返回值:-1: fail, 0: success
    */
    int sqlist_get_elm(SqList list, int get_loc, ElemType* e)
    {
        /*输入参数检查*/
        if (get_loc < 1 || get_loc > list.length) {
    		printf("get_loc err!\n");
            return -1;
        } else {
            *e = list.data[get_loc-1]; //查找位置与数组下标的关系
            return 0;
        }
    }
    

    读者阅读时可思考下接口sqlist_get_elm的第一个参数定义为SqList* list与定义为SqList list的区别,以及第三个参数定义为ElemType* e与ElemType e的区别。


    2.插入元素操作

    在线性表L中的第i个位置插入新元素e。
      算法思路:
       - 若插入位置不合理,则抛出异常;
       - 若线性表长度大于数组存储长度,则抛出异常或动态增加容量(本例为抛出异常);
       - 从表尾元素开始向前遍历到第i个位置,然后将它们都向后移动一个位置;
       - 将要插入元素填入位置i处;
       - 表长加1

    /* 函数名:sqlist_ins_elm
     *
     * 功能:在顺序线性表中第ins_loc个位置插入元素
     *
     * 入口参数:
     *         > list: 整个顺序线性表
     *         > ins_loc: 待插入的位置
     *         > e: 待插入的元素值
     * 
     * 返回值:-1: fail, 0: success
    */
    int sqlist_ins_elm(SqList* list, int ins_loc, ElemType e)
    {
        int i;
    	
    	if (list->length == MAXSIZE) {
    		printf("list is crowed!\n");
    		return -1;
    	}
        /*使用list->length+1是考虑到插入表尾时的情况*/
        if (ins_loc < 1 || ins_loc > (list->length + 1)) {
    		printf("ins_loc err!\n");
            return -1;
        }
    
        if (ins_loc <= list->length) { /*若插入数据位置不在表尾*/
    
            /*list->length-1为位置与下标的关系
             *ins_loc-1也为位置与下标的关系, 同时也是作为从表尾遍历到第ins_loc个位置的判据
            */
            for (i = list->length - 1; i >= ins_loc - 1; i--) {
                list->data[i+1] = list->data[i]; //将要插入位置后的数据元素均向后移动一位
            }
        }
        list->data[ins_loc-1] = e; //将新元素插入
        list->length++;
    
        return 0;
    }
    

    3.删除操作

    删除线性表L中第i个位置的元素,并用变量e返回删除的值。
      算法思路:
       - 若删除位置不合理,则抛出异常;
       - 取出删除元素;
       - 从删除元素位置遍历至最后一个元素的位置,分别将它们向前移动一个位置;
       - 表长减1

    /* 函数名:sqlist_del_elm
     *
     * 功能:删除顺序线性表中第del_loc个位置的元素
     *
     * 入口参数:
     *         > list: 整个顺序线性表
     *         > del_loc: 待插入的位置
     *         > e: 返回删除位置后面一个位置的元素
     * 
     * 返回值:-1: fail, 0: success
    */
    int sqlist_del_elm(SqList* list, int del_loc, ElemType* e)
    {
    	int i;
    
        /*删除位置检查*/
        if (del_loc<1 || del_loc>list->length) {
    		printf("del_loc err!\n");
            return -1;
        }
    
        *e = list->data[del_loc]; //用e返回待删除元素的后一个位置的元素值
    
    	//若删除的位置不是表尾
        if (del_loc < list->length) { 
            /*将删除位置处的后继元素前移*/
            for (i=del_loc; i<list->length; i++) {
                list->data[i-1] = list->data[i]; //注意理解位置与下标的关系
            }
        }
        list->length--; //删除为表尾时的偷懒处理
    
        return 0;
    }
    

    三、完整的测试实例

    #include <stdio.h>
    #include <string.h>
    
    #include "seq.h"
    
    /* 函数名:sqlist_get_elm
     *
     * 功能:获取顺序线性表中第get_loc个位置处的元素值(用e返回)
     *
     * 入口参数:
     *         > list: 整个顺序线性表
     *         > get_loc: 待查找的位置
     *         > e: 查找后返回的值
     * 
     * 返回值:-1: fail, 0: success
    */
    int sqlist_get_elm(SqList list, int get_loc, ElemType* e)
    {
        /*输入参数检查*/
        if (get_loc < 1 || get_loc > list.length) {
    		printf("get_loc err!\n");
            return -1;
        } else {
            *e = list.data[get_loc-1]; //查找位置与数组下标的关系
            return 0;
        }
    }
    
    /* 函数名:sqlist_ins_elm
     *
     * 功能:在顺序线性表中第ins_loc个位置插入元素
     *
     * 入口参数:
     *         > list: 整个顺序线性表
     *         > ins_loc: 待插入的位置
     *         > e: 待插入的元素值
     * 
     * 返回值:-1: fail, 0: success
    */
    int sqlist_ins_elm(SqList* list, int ins_loc, ElemType e)
    {
        int i;
    	
    	if (list->length == MAXSIZE) {
    		printf("list is crowed!\n");
    		return -1;
    	}
        /*使用list->length+1是考虑到插入表尾时的情况*/
        if (ins_loc < 1 || ins_loc > (list->length + 1)) {
    		printf("ins_loc err!\n");
            return -1;
        }
    
        if (ins_loc <= list->length) { /*若插入数据位置不在表尾*/
    
            /*list->length-1为位置与下标的关系
             *ins_loc-1也为位置与下标的关系, 同时也是作为从表尾遍历到第ins_loc个位置的判据
            */
            for (i = list->length - 1; i >= ins_loc - 1; i--) {
                list->data[i+1] = list->data[i]; //将要插入位置后的数据元素均向后移动一位
            }
        }
        list->data[ins_loc-1] = e; //将新元素插入
        list->length++;
    
        return 0;
    }
    
    /* 函数名:sqlist_del_elm
     *
     * 功能:删除顺序线性表中第del_loc个位置的元素
     *
     * 入口参数:
     *         > list: 整个顺序线性表
     *         > del_loc: 待插入的位置
     *         > e: 返回删除位置后面一个位置的元素
     * 
     * 返回值:-1: fail, 0: success
    */
    int sqlist_del_elm(SqList* list, int del_loc, ElemType* e)
    {
    	int i;
    
        /*删除位置检查*/
        if (del_loc<1 || del_loc>list->length) {
    		printf("del_loc err!\n");
            return -1;
        }
    
        *e = list->data[del_loc]; //用e返回待删除元素的后一个位置的元素值
    
    	//若删除的位置不是表尾
        if (del_loc < list->length) { 
            /*将删除位置处的后继元素前移*/
            for (i=del_loc; i<list->length; i++) {
                list->data[i-1] = list->data[i]; //注意理解位置与下标的关系
            }
        }
        list->length--; //删除为表尾时的偷懒处理
    
        return 0;
    }
    
    int main(void)
    {
    	int i, ret;
    	int location;
        SqList list;
    	ElemType e; //用于插入或返回获取到的值
    
    	printf("Please Enter length of list(<= MAXSIZE): "); //自定义表长
    	scanf("%d", &(list.length));
    	if (0 == list.length) {
    		printf("list is empty!\n");
    		return -1;
    	}
    	
    	/*初始化表元素,便于后续测试*/
    	printf("Init list elements...\n");
    	srand(time(0));
    	for (i=0; i<list.length; i++) {
    		list.data[i] = rand()%100 + 1;
    	}
    	printf("Init list successfully!\n");
    	
    	/*验证获取元素操作*/
    	printf("Please Enter get_loc: ");
    	scanf("%d", &location);
    	ret = sqlist_get_elm(list, location, &e);
    	if (ret == -1) {
    		printf("call sqlist_get_elm err!\n");
    		return -1;
    	} 
    	printf("get_loc: %p, ret = %d, e = %d\n", &list.data[location-1], ret, e);
    	
    	/*验证插入元素操作*/
    	printf("Please Enter ins_loc: ");
    	scanf("%d", &location);
    	printf("Please Enter element inserted: ");
    	scanf("%d", &e);
    	ret = sqlist_ins_elm(&list, location, e);
    	if (ret == -1) {
    		printf("call sqlist_ins_elm err!\n");
    		return -1;
    	} 
    	sqlist_get_elm(list, location, &e); //插入元素后再次获取
    	printf("ins_loc: %p, ret = %d, e = %d\n", &list.data[location-1], ret, e);
    	
    	/*验证删除元素操作*/
    	printf("Please Enter del_loc: ");
    	scanf("%d", &location);
    	ret = sqlist_del_elm(&list, location, &e);
    	if (ret == -1) {
    		printf("call sqlist_del_elm err!\n");
    		return -1;
    	} 
    	printf("del_loc: %p, ret = %d, e = %d\n", &list.data[location-1], ret, e);
    	
    return 0;
    }
    

    测试结果:
    这里写图片描述


    四、算法时间复杂度的分析

    由“获取元素操作”的示例可知,线性表的顺序存储结构在读、写操作时,不论是哪个位置其时间复杂度都为O(1)。而插入或删除时,因为程序的执行次数取决于问题的输入规模(即Ins_Loc或Del_Loc的值),程序的直接体现则为for循环的执行次数。下面具体分析插入、删除元素是的时间复杂度。

    1.插入操作的时间复杂度
    假定在任意位置插入元素的概率Pi相等: (表长为n,n+1个位置)
    这里写图片描述
    元素插入位置的可能值:i=1,2,3, … ,n, n+1
    相应的移动次数:(n-i+1) = n,n-1, … ,1,0

    由概率论中数学期望的观点可得平均移动次数:
    这里写图片描述
    最后由时间复杂度的推导可知,插入操作的平均时间复杂度为O(n)。
      为何要分析平均移动次数呢?因为插入位置的不同,移动次数自然也不同,而考虑最坏或最好的情况都不具有代表性,自然应分析平均情况。

    2.删除操作的时间复杂度
    假定在线性表中的任意位置删除元素的概率相等:(表长为n,n个位置)
    这里写图片描述
    元素删除位置的可能值:i=1,2,…,n
    相应向前移动的次数:(n-i)=n-1,n-2,…,0
    由概率论中数学期望的观点可得平均移动次数:
    这里写图片描述
    最后由时间复杂度的推导可知,删除操作的平均时间复杂度也为O(n)。

    参阅资料
    大话数据结构
    算法精解—C语言描述
    http://www.docin.com/p-1723299970.html

    展开全文
  • do { printf("请输入第%d个数据\n", i); i++; scanf("%d", &e); getchar(); if (rearinsertList(p, e)) printf("添加成功!是否继续添加数据?\n"); yn = getchar(); } while (yn == 'Y' || yn =...
  • C# 线性表使用实例

    2012-09-21 23:53:38
    定义接口,在泛型类中实现了线性表中的各种操作,包含增、删、改、查等。通过本实例,可以学习C#线性表相关内容,也可以学习到接口、类、泛型、索引器等相关知识,为下一步数据结构的学习打下坚实的基础。
  • 线性表定义:有限序列 a1,a2.....ai....an,ai有前驱或者后继 线性表:1.顺序存储结构---数组  2.链式存储结构---1.单链表  2.静态链表  3.循环链表(单向)  4.双向链表(双向循环链表) 单链表,静态链表,...
  • 问题描述:假设利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合是两个并集 算法步骤:一次去除Lb中的每个元素,执行以下操作: 在La中查找该元素 如果找不到,则将其插入La的最后...
  • 数据结构线性表

    2017-03-15 00:29:22
    本文用最简单的语言和实例,一起探讨线形表,从其逻辑结构出发,对应物理结构,从原理上剖析其应用。希望对大家有帮助。2.线形表的逻辑结构线形表的逻辑结构,就是我们在第一章讲到的线形结构。所谓的逻辑结构就是你...
  • 数组数据在内存中顺序存储,可以通过下标索引。特点:支持随机访问,索引元素效率高,插入元素和删除元素效率低。数组存放空间连续,插入元素时需要将插入位置及后面的元素一次往后移动一位,然后将元素插入到空出的...
  • 最近敲了下线性结构实例,收获颇丰。线性结构的特点是:在数据元素的非空有限集中,(1)存在唯一的一个被称为“第一个”的数据元素;(2)存在唯一的一个被称作“最后一个”的数据元素;(3)除了第一个之外,...
  • 数据结构线性表

    2021-02-08 15:15:53
    线性表是最基本且最常用的一种线性结构,同时也是其他数据结构的基础。本文首先介绍线性表的定义和特点,然后对线性表的主要操作用C语言程序进行实现,最后给出线性表应用实例
  • 数据结构 第一章 绪论 1.数据结构的基本概念 数据的基本概念 默认情况下,程序中处理的数据都是数据对象。 数据结构定义 数据结构 = 数据对象 + 结构 结构:数据元素之间的关系 数据结构的组成 逻辑结构:数据元素...
  • 本文实例讲述了JavaScript数据结构中串的表示与应用。分享给大家供大家参考,具体如下: 类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列。下面我们以串联接为例,讲解一下这种存储结构时...
  • 数据结构 基于线性表的图书信息管理

    千次阅读 多人点赞 2020-07-16 18:13:28
    数据结构实验1 基于线性表的图书信息管理实验目的实验内容代码1.基于顺序存储结构的图书信息表的创建和输出个人小结 实验目的 1.掌握线性表的顺序存储表示和链式存储表示 2.掌握顺序表和链表的基本操作,包括创建、...
  • 数据结构中,线性表是一种入门级的数据结构线性表分为序列表和链表,在下文中爱站技术频道小编将实例详解C语言线性表的顺序与实现步骤,下面一起跟着爱站技术频道的步伐来学习吧!1.概述通常来说顺序表是在计算机...
  • 应用实例:多项式加法运算 1. 线性表 2. 堆栈 3. 队列 4. 应用实例:多项式加法运算   例: 将多项式P1=3x5+4x4−x3+2x−1P_{1}=3x^{5}+4x^{4}-x^{3}+2x-1P1​=3x5+4x4−x3+2x−1与P2=2x4+x3−7x2+3x−1P_{2}=2x^...
  • 本文实例讲述了JavaScript队列的应用。分享给大家供大家参考,具体如下: 和前面介绍的栈相反,队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端进行删除。JavaScript自己提供了两个队列方法...
  • 线性表 由结点集N以及定义在结点集N上的线性关系R (1)有一个唯一的开始节点,无前驱,有唯一后继 (2)对于有限集N 存在一个唯一的终止结点,无后继,有唯一前驱 (3)其他为内部结点,有唯一前驱和唯一后继 (4)...
  • 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储...
  • 本文内容是数据结构第二弹——栈及其应用。首先会介绍栈的基本结构和基本操作以及代码实现,文后会讲解几个栈的典型应用。栈是一个比较简单但是用途及其广泛的重要的数据结构,所以对于栈的学习重在理解应用而非实现...
  • 数据结构与算法入门 问题1:为什么要学习数据结构 如果说学习语文的最终目的是写小说的话,那么能不能在识字、组词、造句后就直接写小说了,肯定是不行的, 中间还有一个必经的阶段:就是写作文。写作文的...
  • 目录- [线性结构-1 Java中的线性表的测试](#1)- [线性结构-2 Java中的线性表应用](#2)- [线性结构-3 顺序表的实现](#3)- [线性结构-4 链表的实现](#4)- [线性结构-5 源码分析](#5)线性结构-1 线性表的测试实验过程...
  • 线性表数据结构中最简单最常用的一种线性结构,也是学习数据结构全部内容的基础,其掌握的好坏直接影响 着后续知识的学习。本章通过四个模拟项目来学习线性表的顺序和链式存储结构,首先通过使用有关数组的操作...
  • 循环链表的应用之约瑟夫环问题以及线性表总结之顺序表与链表的比较 1.1问题说明 问题描述:编号为1,2,···,n的n个人围坐在一圆桌旁,每人持有一个正整数的密码。从第一个人开始报数,报到一个预先约定的正整数m...
  • 实验 一 线性表的基本操作实现及其应用 一实验目的 1熟练掌握...( * ) 2约瑟夫环问题 3Dr.Kong的艺术品 三实验要求 1按照数据结构实验任务书提前做好实验预习与准备工作 2加*题目必做其他题目任选多选者并且保质保量完
  • 数据结构实验一 3、队列的链式存储结构的实现 (1) 用随机函数生成10个3位整数(100~999),把这些整数应用入队操作存于队列中; (2) 应用遍历操作输出队列的内容; (3) 把队列的内容翻转,应用出队操作输出队列的内容...
  • 常用八大数据结构总结及应用场景-附示例截图

    千次阅读 多人点赞 2020-08-03 21:32:42
    什么是数据结构? 官方解释:数据结构是一门研究非数值计算的程序设计问题中的操作对象,以及他们之间的关系和操作等相关问题的学科。 大白话:数据结构就是把数据元素按照一定的关系组织起来的集合,用来组成和...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,986
精华内容 3,194
关键字:

数据结构线性表实例应用

数据结构 订阅