精华内容
下载资源
问答
  • 改写的数据结构综合实验源码。不改变现有单链表类,根据具体应用(如学生管理...作者经过充分测试,考虑了各种异常处理,是一个完整的数据结构应用实例。适用于学习数据结构具体应用的中级水平进阶。欢迎大家交流探讨。
  • 数据结构线性表;2.1 线性表的基本概念;线性表的应用实例;2.2 线性表的顺序存储顺序表;2.2.2 顺序表上的运算及其实现;逻辑功能设计;交互页面的设计;Main函数的设计;2.3 线性表的链式存储单链表; 在单链表中,假定每个...
  • 数据结构---线性表应用实例

    千次阅读 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;
      }

       

     

    展开全文
  • 最近敲了下线性结构实例,收获颇丰。线性结构的特点是:在数据元素的非空有限集中,(1)存在唯一的一个被称为“第一个”的数据元素;(2)存在唯一的一个被称作“最后一个”的数据元素;(3)除了第一个之外,...

                          最近敲了下线性结构的实例,收获颇丰。线性结构的特点是:在数据元素的非空有限集中,(1)存在唯一的一个被称为“第一个”的数据元素;(2)存在唯一的一个被称作“最后一个”的数据元素;(3)除了第一个之外,集合中的每个数据元素均只有一个前驱;(4)除最后一个之外,集合中的每个数据元素均只有一个后继。线性 结构的存储结构不外乎两种:顺序存储结构,链式存储结构。

     问题一:

    【问题描述】

                                    约瑟夫(Joseph)问题的一种描述是:编号为1,2,......,n的n个人按顺时针方向围坐一圈,每个人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。是设计一个程序求出出列顺序。

    【基本要求】

                                   利用单向循环链表存储结构模拟此过程,按照出列的顺序印出个人的编号。

    【测试数据】

                                   n=7,7个人的密码依次为:3,1,7,2,4,8,4,首先m值为6(正确的出列顺序为6,1,4,7,2,3,5)。

    【C++代码】

    #include<iostream>
    using namespace std;
    typedef int ElemType;
    struct LNode{       //节点
        ElemType data;
        LNode *next;
    };
    typedef LNode *LinkList;
    int main(){
        LinkList p,q,t;
        int m;
        int Array[7]={3,1,7,2,4,8,4};
        p=(LinkList)malloc(sizeof(LNode));
        for(int i=1;i<=7;i++)
        {
            q=(LinkList)malloc(sizeof(LNode));
            q->data=i;
            if(i==1)      //当i=1时,头结点就是p
            {p=q;
            t=q;}
            else
            {t->next=q;
            t=q;}

        }
        q->next=p;                //以上代码建立一个无头结点的循环链表
        for(int h=1;h<=7;h++)     //下列代码实现从链表中逐渐删去节点
        {
            if(h==1)
                m=5;       //此处是5,不是6
            for(int g=2;g<=m;g++){
                p=p->next;
            }
            q=p;
            p=p->next;
            cout<<p->data<<" ";
            m=Array[p->data-1];
            q->next=p->next;
        }
        cout<<endl;
        return 0;
    }


           

    展开全文
  • 数据结构线性表

    2021-02-08 15:15:53
    线性表是最基本且最常用的一种线性结构,同时也是其他数据结构的基础。本文首先介绍线性表的定义和特点,然后对线性表的主要操作用C语言程序进行实现,最后给出线性表应用实例

    一、线性表的定义与特点

    1.定义

    线性表是由n(n\geq 0)个同类型的数据元素构成的有限序列的线性结构。

    2.特点

    (1)同一性:线性表由同类数据元素组成,每一个数据元素必须属于同一个数据对象;

    (2)有穷性:线性表由有限个数据元素组成,表长度就是表中数据元素的个数;

    (3)有序性:线性表中相邻数据元素之间存在着序偶关系。

    二、线性表的顺序存储

    1.定义

    线性表的顺序存储是指在内存中用一块地址连续的存储空间顺序存放线性表的各数据元素,使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中,即通过数据元素物理存储的连续性来反映数据元素之间逻辑上的相邻关系。

    顺序表的结构体定义如下:

    typedef int ElementType;
    typedef struct
    {
    	ElementType *array;   // 存放元素的数组
    	int length;  // 当前长度
    	int capacity;  // 数组容量
    }SqList;

    2.主要操作的实现

    (1)顺序表的创建

    // 构造一个空的顺序表
    SqList *createList(int capacity)
    {
    	SqList *L;                            // 定义顺序表
    	L=(SqList*)malloc(sizeof(SqList));    // 开辟一块内存空间给顺序表L
    	L->length=0;              // 顺序表的长度为0
    	L->capacity=capacity;    // 数组容量
    	L->array=(ElementType*)malloc(capacity*sizeof(ElementType)); // 在顺序表L上为数组开辟空间
    	
    	return L;
    }

     (2)获得顺序表的数据元素

    int GetElement(SqList *L,int i,ElementType *e)
    {
    	if(i<1||i>L->length)
    	{
    		return 0;
    	}
    	*e=L->array[i-1];
    	return 1;
    }

     (3)顺序表的查找

    顺序表的查找是指在顺序表中查找与给定值 e 相等的数据元素。下面采取从后向前查找的方式,若在顺序表 L 中找到与 e 相等的元素,则返回该元素在顺序表中的下标;否则,返回0。

    int find(SqList *L,ElementType e)
    {
    	int i;
    	i=L->length-1;
    	while(i>=0&&L->array[i]!=e){
    		i--;
    	}
    	if(i<0)
    	{
    		return 0;
    	}
    	return i;
    }

    查找成功的平均比较次数为 (n+1)/2,时间复杂度为O(n) 。

    (4)顺序表的插入

    int insertlist(SqList *L,int i,ElementType e)
    {
    	int k;
    	if(L->length>=L->capacity)   // 1.判断顺序表的存储空间是否满
    	{
    		return 0;
    	}
    	if(i<1||i>L->length+1)     // 2.判断插入位置i是否合法
    	{
    		return 0;
    	}
    	for(k=L->length-1;k>=i-1;k--)
    	{
    		L->array[k+1]=L->array[k];    // 3.从最后一个元素开始向后移动
    	}
    	L->array[i-1]=e;      // 4.在第i个位置插入元素
    	L->length++;         // 5.表长度加1
    
    	return 1;
    }

     在顺序表上做插入操作平均移动数据元素的次数为 n/2,时间复杂度为O(n) 。

    (5)顺序表的删除

    int deletelist(SqList *L,int i,ElementType *e)
    {
    	int k;
    	if(i<1||i>L->length)    // 1.判断删除位置i是否合法
    	{
    		return 0;
    	}
    	*e=L->array[i-1];    // 删除的第i个元素
    	for(k=i;k<L->length;k++)
    	{
    		L->array[k-1]=L->array[k];    // 2. 从i+1个元素开始向前移动
    	}
    	L->length--;
    	return 1;
    }

    在顺序表上做删除操作平均移动数据元素的次数为 (n-1)/2,时间复杂度为O(n) 。

    3.应用实例

    顺序表的合并,求两个顺序表中数据元素的并集

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define SIZE 100
    
    typedef int ElementType;
    typedef struct
    {
    	ElementType *array;   // 存放元素的数组
    	int length;  // 当前长度
    	int capacity;  // 数组容量
    }SqList;
    
    // 顺序表的创建
    SqList *createList(int capacity)
    {
    	SqList *L;
    	L=(SqList*)malloc(sizeof(SqList));
    	L->length=0;
    	L->capacity=capacity;
    	L->array=(ElementType*)malloc(capacity*sizeof(ElementType));
    	
    	return L;
    }
    
    // 获得顺序表的元素
    int GetElement(SqList *L,int i,ElementType *e)
    {
    	if(i<1||i>L->length){
    	return 0;
    	}
    	*e=L->array[i-1];
    	return 1;
    }
    
    // 顺序表的查找
    int find(SqList *L,ElementType e)
    {
    	int i;
    	i=L->length-1;
    	while(i>=0&&L->array[i]!=e){
    		i--;
    	}
    	if(i<0)
    	{
    		return 0;
    	}
    	return i;
    }
    
    // 顺序表的插入
    int insertlist(SqList *L,int i,ElementType e)
    {
    	int k;
    	if(L->length>=L->capacity)   // 1.判断顺序表的存储空间是否满
    	{
    		return 0;
    	}
    	if(i<1||i>L->length+1)     // 2.判断插入位置i是否合法
    	{
    		return 0;
    	}
    	for(k=L->length-1;k>=i-1;k--)
    	{
    		L->array[k+1]=L->array[k];    // 3.从最后一个元素开始向后移动
    	}
    	L->array[i-1]=e;      // 4.在第i个位置插入元素
    	L->length++;         // 5.表长度加1
    
    	return 1;
    }
    
    // 顺序表的删除
    int deletelist(SqList *L,int i,ElementType *e)
    {
    	int k;
    	if(i<1||i>L->length)    // 1.判断删除位置i是否合法
    	{
    		return 0;
    	}
    	*e=L->array[i-1];    // 删除的第i个元素
    	for(k=i;k<L->length;k++)
    	{
    		L->array[k-1]=L->array[k];    // 2. 从i+1个元素开始向前移动
    	}
    	L->length--;
    	return 1;
    }
    
    // 顺序表的长度
    int listlength(SqList *L)
    {
    	return L->length;
    }
    
    //按尾部插入法生成初始数据
    void Addlist(SqList *L)
    {
    	int value;
    	printf("请输入内容,-1结束\n");
    	scanf("%d",&value);
    	while(value!=-1)
    	{
    		insertlist(L,L->length+1,value);   // 顺序表的插入
    		scanf("%d",&value);
    	}
    }
    
    //输出数据
    void Outputlist(SqList *L)
    {
    	int i;
    	for(i=0;i<L->length;i++)
    	{
    		printf("%d ",L->array[i]);
    	}
    	printf("\n");
    }
    
    // 顺序表的合并:取并集
    void mergelist(SqList *L1,SqList *L2)
    {
    	int L1_Len,L2_Len;
    	int i;
    	ElementType e;
    
    	L1_Len=listlength(L1);    // 顺序表的长度
    	L2_Len=listlength(L2);
    
    	for(i=1;i<=L2_Len;i++)
    	{
    		GetElement(L2,i,&e);     // 获得顺序表的元素
    		if(!find(L1,e))     // 在表L1中没找到该元素,则将该元素插入表L1中
    		{
    			insertlist(L1,L1->length+1,e);    // 顺序表的插入
    		}
    	}
    }
    
    int main()
    {
    	SqList *LA,*LB;
    
    	LA=createList(SIZE);
    	LB=createList(SIZE);
    
    	printf("尾部插入法生成初始数据:\n");
    
    	Addlist(LA);
    	printf("LA表中元素为:");
    	Outputlist(LA);
    
    	Addlist(LB);
    	printf("LB表中元素为:");
    	Outputlist(LB);
    
    	mergelist(LA,LB);
    	printf("LA和LB取并集后的元素为:");
    	Outputlist(LA);
    
    	return 0;
    }

    三、线性表的链式存储

    1.定义

    线性表的链式存储是指在线性表中逻辑上相邻的数据元素在物理位置上并不一定相邻,它是通过‘链’建立起数据元素之间的逻辑关系。

    C语言描述单链表类型如下:

    typedef int ElementType;
    typedef struct Node
    {
    	ElementType data;    // 数据域
    	struct Node *next;   // 指针域
    }node;
    typedef struct Node *LinkList;

    2.主要操作的实现

    (1)单链表的创建

    /*===============================================================
    CreateLinkList函数功能:
    创建链表L, 并将给定数组a, 以及数组中元素个数n,尾部插入法建立链表
    ===================================================================*/
    void createlist(LinkList *L,int n,int a[])
    {
    	LinkList p,r;
    	int i;
    
    	(*L)=(LinkList)malloc(sizeof(node));  // 建立头结点
    	r=*L;
    
    	for(i=0;i<n;i++)
    	{
    		p=(LinkList)malloc(sizeof(node));   // 生成新结点
    		p->data=a[i];
    		r->next=p;
    		r=p;
    	}
    	r->next=NULL;
    }

    (2)单链表的输出

    /*===============================================================
    Outputlist函数功能:
    依次输出链表L中的每个数据
    ===================================================================*/
    void Outputlist(LinkList L)
    {
    	LinkList p;
    	p=L->next;
    	while(p!=NULL)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }

    时间复杂度为O(n) 。

    (3)单链表的查找

    单链表的查找有按值查找和按序号查找两种方式。

    // 1.按值查找
    LinkList findvalue(LinkList L,ElementType x)
    {
    	LinkList p;
    	p=L->next;
    	while(p!=NULL && p->data!=x)
    	{
    		p=p->next;
    	}
    	return p;
    }
    // 2.按序号查找
    LinkList locate(LinkList L,int i)
    {
    	LinkList p;
    	int k=0;
    
    	p=L;	
    	while(p!=NULL && k<i)
    	{
    		p=p->next;
    		k++;
    	}
    	return p;
    }

    平均时间复杂度均为O(n) 。

    (4)单链表结点的插入

    // 单链表结点的插入:第i个位置插入数值x
    int Insertlist(LinkList L,int i,ElementType x)
    {
    	LinkList p,s;
    	p=locate(L,i-1);  // 查找第i-1个结点,p指向该结点
    	if(p==NULL || i<1)
    	{
    		return 0;
    	}
    	s=(LinkList)malloc(sizeof(node));
    	s->data=x;
    
    	s->next=p->next;
    	p->next=s;
    
    	return 1;
    }

    (5)单链表结点的删除

    单链表结点的删除有按值删除和按序号删除两种方式。

    // 1.按值删除
    int Deletevalue(LinkList L,ElementType x)
    {
    	LinkList p,q;
    	q=L;
    	p=L->next;
    
    	while(p!=NULL && p->data!=x)
    	{
    		q=p;
    		p=p->next;
    	}
    	if(p==NULL)
    		return 0;
    	else
    	{
    		q->next=p->next;
    		free(p);
    		return 1;
    	}
    }
    // 2.按序号删除
    int Deletelocate(LinkList L,int i)
    {
    	LinkList p,q;
    	ElementType x;
    
    	p=locate(L,i-1);
    	if(p==NULL || i<1 || p->next==NULL)
    	{
    		return 0;
    	}
    	q=p->next;
    	p->next=q->next;
    	x=q->data;
    	printf("删除的值为:");
    	printf("%d\n",x);
    	free(q);
    	return 1;
    }

     注意:一定要找到所删除结点的前驱结点。

    删除算法的时间复杂度为O(n) 。

    (6)以上单链表主要操作的全部程序

    #include<stdio.h>
    #include<stdlib.h>
    typedef int ElementType;
    typedef struct Node
    {
    	ElementType data;
    	struct Node *next;
    }node;
    typedef struct Node *LinkList;
    
    /*===============================================================
    CreateLinkList函数功能:
    创建链表L, 并将给定数组a, 以及数组中元素个数n,尾部插入法建立链表
    ===================================================================*/
    void createlist(LinkList *L,int n,int a[])
    {
    	LinkList p,r;
    	int i;
    
    	(*L)=(LinkList)malloc(sizeof(node));  // 建立头结点
    	r=*L;
    
    	for(i=0;i<n;i++)
    	{
    		p=(LinkList)malloc(sizeof(node));   // 生成新结点
    		p->data=a[i];
    		r->next=p;
    		r=p;
    	}
    	r->next=NULL;
    }
    
    /*===============================================================
    Outputlist函数功能:
    依次输出链表L中的每个数据
    ===================================================================*/
    void Outputlist(LinkList L)
    {
    	LinkList p;
    	p=L->next;
    	while(p!=NULL)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
    
    // 单链表的查找:1.按值查找;2.按序号查找
    LinkList findvalue(LinkList L,ElementType x)
    {
    	LinkList p;
    	p=L->next;
    	while(p!=NULL && p->data!=x)
    	{
    		p=p->next;
    	}
    	return p;
    }
    
    LinkList locate(LinkList L,int i)
    {
    	LinkList p;
    	int k=0;
    
    	p=L;	
    	while(p!=NULL && k<i)
    	{
    		p=p->next;
    		k++;
    	}
    	return p;
    }
    
    // 单链表结点的插入:第i个位置插入数值x
    int Insertlist(LinkList L,int i,ElementType x)
    {
    	LinkList p,s;
    	p=locate(L,i-1);
    	if(p==NULL || i<1)
    	{
    		return 0;
    	}
    	s=(LinkList)malloc(sizeof(node));
    	s->data=x;
    
    	s->next=p->next;
    	p->next=s;
    
    	return 1;
    }
    
    // 单链表的删除:1.按值删除;2.按序号删除
    int Deletevalue(LinkList L,ElementType x)
    {
    	LinkList p,q;
    	q=L;
    	p=L->next;
    
    	while(p!=NULL && p->data!=x)
    	{
    		q=p;
    		p=p->next;
    	}
    	if(p==NULL)
    		return 0;
    	else
    	{
    		q->next=p->next;
    		free(p);
    		return 1;
    	}
    }
    
    int Deletelocate(LinkList L,int i)
    {
    	LinkList p,q;
    	ElementType x;
    
    	p=locate(L,i-1);
    	if(p==NULL || i<1 || p->next==NULL)
    	{
    		return 0;
    	}
    	q=p->next;
    	p->next=q->next;
    	x=q->data;
    	printf("删除的值为:");
    	printf("%d\n",x);
    	free(q);
    	return 1;
    }
    
    int main()
    {
    	int A[]={0};
    	int i,j;
    	int N;
    	LinkList S;
    	ElementType e;
    	int select;
    
    	printf("请输入链表元素的个数:");
    	scanf("%d",&N);
    	for(i=0;i<N;i++)
    	{
    		scanf("%d",&A[i]);
    	}
    	createlist(&S,N,A);
    	printf("单链表中元素为:");
    	Outputlist(S);
    	
    	while(1)
    	{
    		printf("\n\n");
    		printf("                    输入 1 在单链表中插入元素。\n");
    		printf("                    输入 2 则按位置删除单链表中的元素。\n");
    		printf("                    输入 3 则按值删除单链表中的元素。\n");
    		printf("                    输入 4 则显示单链表。\n");
    		printf("                    输入 5 则退出程序。\n");
    
    		printf("请选择输入操作:\n");
    		scanf("%d",&select);
    		switch(select)
    		{
    		case 1:{
    			printf("请输入要插入的位置:\n");
    			scanf("%d", &j);
    			printf("请输入要插入的数值:\n");
    			scanf("%d", &e);
    			Insertlist(S,j,e);
    			printf("插入后表中元素为:");
    			Outputlist(S);
    			   }
    			break;
    
    		case 2:{
    			printf("请输入要删除的位置:\n");
    			scanf("%d", &j);
    			Deletelocate(S,j);
    			printf("删除后表中元素为:");
    			Outputlist(S);
    			   }
    			break;
    
    		case 3:{
    			printf("请输入要删除的值:\n");
    			scanf("%d", &e);
    			Deletevalue(S,e);
    			printf("删除后表中元素为:\n");
    			Outputlist(S);
    				 }
    			break;
    		case 4:{
    			printf("单链表中的元素为:\n");
    			Outputlist(S);
    				 }
    			break;
    		case 5:printf("已退出程序!\n");exit(-1);break;
    		default:printf("输入错误,请重新输入!\n");break;
    		}
    	}
    	return 0;
    }

    3.应用实例

    单链表的合并

    例题1:有两个单链表LA和LB,它们的元素均为非递减有序序列。编写一个算法,将它们合并成一个单链表,要求合并后的单链表中的元素也是非递减有序序列,并且不需要额外申请结点空间。

    #include<stdio.h>
    #include<stdlib.h>
    typedef int ElementType;
    typedef struct Node
    {
    	ElementType data;
    	struct Node *next;
    }node;
    typedef struct Node *LinkList;
    
    /*===============================================================
    CreateLinkList函数功能:
    创建链表L, 并将给定数组a, 以及数组中元素个数n,尾部插入法建立链表
    ===================================================================*/
    LinkList createlist(LinkList *L,int n,int a[])
    {
    	LinkList p,r;
    	int i;
    
    	(*L)=(LinkList)malloc(sizeof(node));  // 建立头结点
    	r=*L;
    
    	for(i=0;i<n;i++)
    	{
    		p=(LinkList)malloc(sizeof(node));   // 生成新结点
    		p->data=a[i];
    		r->next=p;
    		r=p;
    	}
    	r->next=NULL;
    	return *L;
    }
    
    /*===============================================================
    Outputlist函数功能:
    依次输出链表L中的每个数据
    ===================================================================*/
    void Outputlist(LinkList L)
    {
    	LinkList p;
    	p=L->next;
    	while(p!=NULL)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
    
    // 单链表的查找:按值查找
    LinkList findvalue(LinkList L,ElementType x)
    {
    	LinkList p;
    	p=L->next;
    	while(p!=NULL && p->data!=x)
    	{
    		p=p->next;
    	}
    	return p;
    }
    
    // 单链表的合并:非递减有序序列
    void mergelist1(LinkList LA,LinkList LB)
    {
    	LinkList pa,pb,pr;
    	pa=LA->next;
    	pb=LB->next;
    
    	LA->next=NULL;   // 此时LA为带头结点的空单链表
    	pr=LA;   // pr为尾指针
    
    	while(pa!=NULL && pb!=NULL)
    	{
    		if(pa->data <= pb->data)
    		{
    			pr->next=pa;
    			pr=pa;
    			pa=pa->next;
    		}
    		else
    		{
    			pr->next=pb;
    			pr=pb;
    			pb=pb->next;
    		}
    	}
    
    	if(pa!=NULL)
    		pr->next=pa;
    	if(pb!=NULL)
    		pr->next=pb;
    
    	free(LB);    // 释放空间
    }
    
    int main()
    {
    	LinkList La,Lb;
    	int A[]={2,2,3};
    	int B[]={1,3,3,4};
    	int NA=sizeof(A) / sizeof(A[0]);
    	int NB=sizeof(B) / sizeof(B[0]);
    
    	createlist(&La,NA,A);
    	printf("序列A中的元素为:");
    	Outputlist(La);
    
    	createlist(&Lb,NB,B);
    	printf("序列B中的元素为:");
    	Outputlist(Lb);
    
    	mergelist1(La,Lb);
    	printf("序列A和序列B合并后的元素为:");
    	Outputlist(La);
    
    }

    例题2:假设集合A用单链表LA表示,集合B用单链表LB表示,设计算法求这两个集合的差。

    #include<stdio.h>
    #include<stdlib.h>
    typedef int ElementType;
    typedef struct Node
    {
    	ElementType data;
    	struct Node *next;
    }node;
    typedef struct Node *LinkList;
    
    /*===============================================================
    CreateLinkList函数功能:
    创建链表L, 并将给定数组a, 以及数组中元素个数n,尾部插入法建立链表
    ===================================================================*/
    LinkList createlist(LinkList *L,int n,int a[])
    {
    	LinkList p,r;
    	int i;
    
    	(*L)=(LinkList)malloc(sizeof(node));  // 建立头结点
    	r=*L;
    
    	for(i=0;i<n;i++)
    	{
    		p=(LinkList)malloc(sizeof(node));   // 生成新结点
    		p->data=a[i];
    		r->next=p;
    		r=p;
    	}
    	r->next=NULL;
    	return *L;
    }
    
    /*===============================================================
    Outputlist函数功能:
    依次输出链表L中的每个数据
    ===================================================================*/
    void Outputlist(LinkList L)
    {
    	LinkList p;
    	p=L->next;
    	while(p!=NULL)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("\n");
    }
    
    // 单链表的查找:按值查找
    LinkList findvalue(LinkList L,ElementType x)
    {
    	LinkList p;
    	p=L->next;
    	while(p!=NULL && p->data!=x)
    	{
    		p=p->next;
    	}
    	return p;
    }
    
    // 单链表的合并:两个集合的差,A-B,即得到所有属于集合A而不属于集合B的元素
    void mergelist2(LinkList LA,LinkList LB)
    {
    	LinkList pr,pa,temp;
    	pr=LA;
    	pa=LA->next;
    	while(pa!=NULL)
    	{
    		if(findvalue(LB,pa->data)!=NULL)
    		{
    			temp=pa;     // temp为中间变量
    			pr->next=temp->next;
    			pa=temp->next;
    			free(temp);
    		}
    		else
    		{
    			pr=pa;
    			pa=pa->next;
    		}
    	}
    }
    
    int main()
    {
    	LinkList La,Lb;
    	int A[]={2,2,3};
    	int B[]={1,3,3,4};
    	int NA=sizeof(A) / sizeof(A[0]);
    	int NB=sizeof(B) / sizeof(B[0]);
    
    	createlist(&La,NA,A);
    	printf("序列A中的元素为:");
    	Outputlist(La);
    
    	createlist(&Lb,NB,B);
    	printf("序列B中的元素为:");
    	Outputlist(Lb);
    
    	mergelist2(La,Lb);
    	printf("序列A与序列B的差为:");
    	Outputlist(La);
    
    }

    四、总结

    1.顺序存储结构与单链表结构的优缺点

    (1)存储分配方式:

    顺序存储结构用一段连续的存储单元依次存储线性表的数据元素;单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素。

    (2)时间性能:

    查找:顺序表是一种随机存取结构,对表中任意一个结点都可以在O(1)时间内直接存取;单链表是一种顺序存取结构,对表中的结点需要从头指针顺着链查找才能取得,时间复杂度为O(n) 。

    插入和删除:顺序存储结构需要平均移动表长一半的元素,时间复杂度为O(n);单链表在计算出某位置的指针后,插入和删除的时间复杂度仅为O(1) 。

    (3)空间性能:

    顺序存储结构需要预先分配存储空间,分大了,容易造成空间浪费,分小了,容易发生溢出;单链表不需要预先分配存储空间,只要有就可以分配,元素个数也不受限制。

    2.结论

    若线性表需要频繁查找,很少进行插入和删除操作时,宜采用顺序存储结构;若需要频繁插入和删除时,宜采用单链表结构。
     

     

     

    展开全文
  • 数据结构线性表

    2017-03-15 00:29:22
    本文用最简单的语言和实例,一起探讨线形表,从其逻辑结构出发,对应物理结构,从原理上剖析其应用。希望对大家有帮助。2.线形表的逻辑结构线形表的逻辑结构,就是我们在第一章讲到的线形结构。所谓的逻辑结构就是你...

    sf论数据结构(二)

    1.前言

    继上一章的风格特点,今天介绍的内容是最简单的数据结构线形表。本文用最简单的语言和实例,一起探讨线形表,从其逻辑结构出发,对应物理结构,从原理上剖析其应用。希望对大家有帮助。

    2.线形表的逻辑结构

    线形表的逻辑结构,就是我们在第一章讲到的线形结构。所谓的逻辑结构就是你作为程序的创造者,一个God的角色,给你的数据元素组成集合的时候制定的关系上的规则,任何情况不能违背其规则。简单来说就是

    数据元素—-数据元素 之间的关系!

    而线形结构就是说其「数据元素」在组成集合的时候,每个数据元素之间存在「一个接着一个」的关系。如图
    这里写图片描述
    用比较严谨的语言就是:

    除首尾元素,其余所有元素都有唯一的「前趋」和「后继」!
    (注解:根据线性的方向,数据元素“前面“有元素,后继就是“后面“有元素。不太理解的可以对应着图片看)

    3.线形表的物理结构
    简单重复前面物理结构的内容。
    逻辑结构是数据元素与数据元素之间的关系,是人们想象出来的,画出来的。那么怎么去具体实现它呢?在确定好逻辑结构之后,想要在计算机上具体的存储实现,就是数据结构中的物理结构(也称为存储结构)。

    值得注意的一点就是,一种逻辑结构对应多种物理结构。

    3.1 线形表的顺序存储方式
    顺序结构,指的是在内存上开辟一块连续的空间,用来存储一个集合的数据元素。基础较好的看客难免会想到数组就是这个玩意。没错,物理结构中的顺序结构就是借助数组去实现的!

    数据元素与数据元素的物理地址相毗邻。数组的特点注定了它数据元素存储在其中符合我们给它们制定的规则—-逻辑结构。

    首先是结构体的定义

    typedef struct list
    {
        Element data[MAXSIZE]; // 用数组存储 数据元素 
        int length;   // 这个是线形表的长度
    }list;

    如代码所示,结构体里面是一个类型为Element的数组,这个类型可以自己定义(int, double,或者自定义类型) MAXSIZE,因为C语言的特点。声明一个数组必须给它一个长度上限!
    例如:int a[100];
    这个100当然就是上限。这里的MAXSIZE 可以在预编译的时候写!

    #define MAXSIZE 10000

    length就是一个实时状态下的线形表的长度!因为既然作为一个线形表当然要动态的添加和删除数据元素,这里加一个成员可以保持伪动态性。

    这是一个中规中矩的定义!有人嫌它太麻烦,直接用一个数组去表示线形表就可以。这里的数组0号位置是不存元素的,存的就是这个length,是不是简化了很多!
    这里写图片描述

    值得注意的是length与data的类型要相同!也就是说char类型的数组0号位置应该是个’1’这种东西。
    anyway!不管你喜欢用哪种定义方式,都符合其原理!这才是最值得关注的东西!

    至于优缺点的问题,我想介绍完链表之后对比着论述!

    3.2线形表的链式存储结构
    回顾一下上一节课讲的内容,链式存储结构要跟顺序存储结构相反。在内存空间上面,数据元素与数据元素之间不需要连续的空间去存储,但是又要符合线形表的逻辑结构。毕竟是你制定的规则,是不容被打破的!那该怎么做呢?
    这里写图片描述
    如图中的数据元素的集合,数据元素想要这样连接在一起,可以用到指针这个东西,一个节点中(节点就是结构体组成),有一个数据域存放的是数据元素,另外还有一个指针域,存放的是它后继的地址!
    综上所叙,节点的结构体的定义!

    typedef struct QNode
    {
        Element data;   // 数据域
        struct QNode *next; //指针域 
    }QNode;

    有必要解释一下:
    这里的数据域当然只能存一个数据,数据类型为Element。
    而指针域,是一个指针,类型竟然是struct QNode,不要纳闷,这是c语言的特点,在没有typedef之前,结构体类型不是QNode而是struct QNode。具体其他语言有不同,大家自行复习结构体和指针。画一个节点。

    3.3 线形表的基本操作

    3.3.1 顺序表的建立
    .3 线形表的基本操作

    3.3.1 顺序表的建立

    typedef struct list
    {
    Element data[MAXSIZE]; // 用数组存储 数据元素
    int length; // 这个是线形表的长度
    }list;

    这是一个顺序表的结构体定义,其实在实际应用中只需要声明一个数组。数组的0号位等于其length即可。这里的重点在于链表的建立。
    链表的建立分为头插法,尾插法。
    头插法:
    首先把结构体搬出来

    typedef struct Qnode
    {
        Element data;   // 数据域
        struct QNode *next; //指针域 
    }Qnode;
    void CreateListWithF(Qnode *&Head int data[],int size)
    {//假设数据都在data数组里面,数组的大小为size, 注意这里的Head是个引用型,其意思很简单,原来的实参与形参之间是一个单向传值实参————形参。加了引用型之后可以双向传递。
    
        Qnode *s; //Qnode 类型的指针S,用于存储数据元素
    
        //构造成一个节点,使用malloc函数,不明白的可以查查这个函数
        Head=(Qnode*)malloc(sizeof(Qnode)); 
        Head->next=NUll;//这一步不能少
        for(int i=0;i<size;i++){
            s=(Qnode*)malloc(sizeof(Qnode)); 
            s->data=data[i];
            //头插法的重要步骤
            s->next=Head->next;
            Head->next=s;
        }
    }

    如图所示
    原始状态
    这里写图片描述
    第一步
    这里写图片描述
    第二步
    这里写图片描述

    这就是头插法的图示,对应着上述代码

    接下来是尾插法

    void CreateWithR(Qnode *&Head int data[],int size)
    {
        Qnode *s;
        Head=(Qnode*)malloc(sizeof(Qnode)); 
        Head->next=NUll;//这一步不能少
        Head->next=NUll;
        Qnode *r;//标示尾节点
        r=Head;//初始化的时候只有头节点,所以头节点是最后一个,r=Head
        //--------以上都是初始化————————
        for(int i=0;i<size;i++)
        {
            s=(Qnode*)malloc(sizeof(Qnode)); 
            s->data=data[i];
            //尾插法重要步骤
            r->next=s;
            r=s;
        }
    }

    图示
    原始状态
    这里写图片描述
    第一步
    这里写图片描述
    第二步
    这里写图片描述

    其两步对应上述代码的两步

    无论头插法,尾插法进行链表建立都包括了链表的基本插入方法。当然链表的操作不止如此,但是绝对不会脱离图示几个步骤。
    记住诀窍-——找到插入位置——别丢后继!

    展开全文
  • 文章目录线性表的顺序存储结构基本操作应用实例 线性表的顺序存储结构 C/C++中借助数组来实现顺序表 基本操作 //线性表定义 #define MAX_SIZE 50 #define FAILED 0 #define SUCCESS 1 typedef int ElemType ...
  • python数据结构教程第一课python的一些实用的数据结构,原理加上实例源码。目录一、顺序表的实现二、链接表的实现1.单链表2.带尾指针的单链表3.循环单链表4.双链表5.循环双链表三、线性表应用—Josephus问题1.顺序...
  • python 数据结构一 之 线性表

    千次阅读 多人点赞 2017-08-18 15:39:47
    从这里将会正式开始讲解python的一些实用的数据结构,原理加上实例源码。一、简介 二、线性表的抽象数据类型 三、顺序表的实现 四、链接表的实现 1.单链表 2.带尾指针的单链表 3.循环单链表 4.双链表 5...
  • 第二章 线性表(linear list) 本章的基本内容是 2.1 线性表的定义 2.2 线性表的顺序存储及实现 2.3 线性表的链接存储及实现 2.4 线性表的其他存储及实现 2.5 应用实例 2.1 线性表的定义 例1学生成绩登记表 学号 姓 名...
  • 实验 一 线性表的基本操作实现及其应用 一实验目的 1熟练掌握...( * ) 2约瑟夫环问题 3Dr.Kong的艺术品 三实验要求 1按照数据结构实验任务书提前做好实验预习与准备工作 2加*题目必做其他题目任选多选者并且保质保量完
  • python数据结构教程第一课从这里将会正式开始讲解python的一些实用的数据结构,原理加上实例源码。一、简介二、线性表的抽象数据类型三、顺序表的实现四、链接表的实现1.单链表2.带尾指针的单链表3.循环单链表4.双...
  • 线性表(Linear List)”:由同类型数据元素构成有序序列的线性结构。 表中元素个数称为线性表的长度 线性表没有元素时,称为空表 表起始位置称表头,表结束位置称表尾 2.2 堆栈 2.3 队列 2.4 应用实例:多项式...
  • 数据结构C++版 第1章 绪论 第2章 线性表 第3章 排序 第4章 串 第5章 栈与队列 第6章 数组和广义表 第7章 树和二叉树 第8章 查找 第9章 图 第10章 综合应用设计 第9章 图 9.1 图的基本知识 9.2 图的存储结构 9.3 图的...
  • 一、概念  线性结构的特点是:在数据元素的非空有限集中,(1)存在唯一的一个被称做“第一个”的数据元素;...二、线性表应用实例 例1:假设利用两个线性表LA和LB分别表示两个集合A和B(即:线性表中的
  • C#数据结构与算法之二:线性表

    千次阅读 2018-10-25 00:35:47
    目录 第二章 线性表 2.1 CLR中的线性表 2.2线性表的接口定义 2.3线性表的实现方式 2.3.1顺序表 ...2.4.3栈和队列应用实例 ...首先感谢siki老师对C#数据结构与算法的讲解。原视频内容戳这里http:/...
  • 模拟单链表线性表线性表(亦作顺序表)是最基本、最简单、也是最常用的一种数据结构线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑...
  • 线性表逻辑结构的理解掌握线性表的存储结构及基本操作的实现为应用线性表解决实际问题奠定良好 的基础并进一步培养以线性表作为数据结构解决实际问题的应用能力 1掌握线性表的顺序存储结构 2 验证顺序表及其基本操作...
  • 上课啦THE POWERPOINT TEMPALTE模块2线性表54123顺序存储结构逻辑结构实例引入应用举例链式存储结构学习目的与要求重点:掌握顺序表和链表的逻辑描述和存储实现难点:顺序表和单链表的实现和应用线性结构线性结构的...
  • 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储...
  • 数据结构实例分析

    2012-12-29 21:55:43
    详细地介绍了数据结构应用,介绍了学生管理系统,考试报名管理,约瑟夫生者死者游戏,约瑟夫双向生死游戏(线性表应用);迷宫旅行问题,八皇后问题,停车场管理问题(栈与队列的应用);等问题,并且每个实例都给出...
  • 线性表课件

    2011-11-18 01:18:06
    数据结构 线性表的逻辑结构及其基本操作 线性表的顺序存储结构 线性表的链式存储结构 静态链表 应用实例
  • 有广泛的应用实例,指针更灵活,不受空间连续性的限制。 很多很多… 链式描述的线性表的插入、删除操作中内含的思想: 为了保存firstNode,需要新建节点指针类型,即新建一个指针,复制firstNode的地址,
  • 模拟单链表线性表线性表(亦作顺序表)是最基本、最简单、也是最常用的一种数据结构线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑...
  • 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储...
  • 本文实例讲述了JavaScript数据结构中串的表示与应用。分享给大家供大家参考,具体如下: 类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列。下面我们以串联接为例,讲解一下这种存储结构时...
  • 本文实例讲述了JavaScript队列的应用。分享给大家供大家参考,具体如下: 和前面介绍的栈相反,队列是一种先进先出的线性表,它只允许在表的一端进行插入,而在另一端进行删除。JavaScript自己提供了两个队列方法...
  • 在之前的很多教材中,数据结构的实现都是基于C++实现的,对于很多没有学习C++的同学来说,在学习数据结构的过程中造成了一定的阻碍,基于这个原因,希望从标准C语言的角度,来全面描述数据结构的各个算法。...
  • 下面给出顺序栈类代码和应用实例供参考: 顺序栈类:文件名 sq_Stack.h #include using namespace std; template class sq_Stack { private: int mm; //存储空间容量 int top; //栈顶指针 T *s; //...

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 147
精华内容 58
关键字:

数据结构线性表实例应用

数据结构 订阅