美文网首页
线性表🚀

线性表🚀

作者: 你是我患得患失的梦 | 来源:发表于2020-05-05 23:07 被阅读0次
#include<stdio.h>
//void PrintN ( int N )
//{
//  int i;
//  for ( i=1; i<=N; i++ ) {
//      printf("%d\n", i );
//  }
//  return;
//}

//void PrintN ( int N )
//{
//  if ( N ) {
//      PrintN( N - 1 );
//      printf("%d\n", N ); 
//  }
//  return;
//}
int main()
{
    int N;
    scanf("%d", &N);
    PrintN( N );
    return 0;
}
//调用函数我们发现当N的规模达到一个比较大的数的时候用递归的函数直接罢工，而循环的函数能够正常输出，这是因为在递归调用的时候回占用的大量的空间我们计算机把可用的空间都用了但是还是不够所递归的函数就无法执行了

解决问题方法的效率跟数据的组织方式有关。

#include<stdio.h>
#include<time.h>
#include<math.h>
clock_t start, stop;
double duration; //运行时间
#define MAXN 10
#define MAXK 1e7
double f1( int n, double a[], double x);
double f2( int n, double a[], double x);

double f1(int n, double a[], double x)
{
    int i;
    double p = a[0];
    for( i=1; i<=n; i++ ) 
        p += (a[n] * pow(x, i));
    return p;
}
double f2(int n, double a[], double x)
{
    int i;
    double p = a[n];
    for( i=n; i>0; i-- ) 
        p +=  a[n-1] + x*p;
    return p;
}
int main()
{
    int i;
    double a[MAXN];
    for( i=0; i<MAXN; i++ )
        a[i] == (double)i;
    
    start = clock();
    for( i=0; i<MAXK; i++) //这里因为我们函数运行一次的时间远远没有达到计算机一次打点的时间所以我们让它多运行几次然后等捕捉到时间之后再除以循环次数就能算出一次的运行时间
        f1(MAXN-1, a , 1.1);
    stop = clock();
    duration = ((double)(stop - start))/CLK_TCK/MAXK;
    printf("ticks1 = %f\n", (double)(stop - start));
    printf("duration1 = %6.2e\n", duration);
    
    
    start = clock();
    for( i=0; i<MAXK; i++)
        f2(MAXN-1, a , 1.1);
    stop = clock();
    duration = ((double)(stop - start))/CLK_TCK/MAXK;
    printf("ticks2 = %f\n", (double)(stop - start));
    printf("duration2 = %6.2e\n", duration);
    
    return 0;
}
/*结果
ticks1 = 14433.000000
duration1 = 1.44e-006
ticks2 = 9005.000000
duration2 = 9.01e-007
*/

解决问题方法的效率跟算法的巧妙程序有关。

什么是数据结构：

数据对象在计算机中的组织方式：

  • 逻辑存储结构
  • 物理存储结构

数据对象必定与一系列加在其上面的操作相关联，而完成这些操作所用的方式就是算法

抽象数据类型（Abstract Data Type）

数据类型：

  • 数据对象集
  • 数据集合相关联的操作集

抽象：描述数据类型的方法不依赖于具体的实现

  • 与存放数据的机器无关
  • 于数据存储的物理结构无关
  • 与实现操作的算法和编程语言无关

只描述数据对象集合相关的操作集是什么，并不涉及如何做到的问题

什么是算法：

算法（Algorithm）

  • 一个有限指令集
  • 接受一些输入（有些情况下不需要输入）
  • 产生输出
  • 一定在有限步骤之后结束
  • 每一条指令必须
    • 有充分明确的目标，不可以有歧义
    • 计算机能处理的范围之内
    • 描述不应该依赖于任何一种计算机语言以及具体的实现手段

什么是好的算法：

  • 时间复杂度T(n)：根据算法写成的程序在执行时耗费的时间的长度

  • 空间复杂度S(n)：根据算法写成的程序在执行时耗费的空间的长度

    1 < log n < n < nlogn < n^2 < 2^n < n!

线性表及其实现

线性表：

由同类型数据元素构成的y有序序列的线性结构

  • 表中的元素个数成为线性表的长度
  • 线性表没有元素时，成为空表
  • 表的起始位置成为表头，表结束的位置成为表尾

线性表的抽象数据类型描述

类型名称：线性表（List）

数据对象集：线性表是n个元素构成的有序序列

操作集：线性表L∈List，整数i表示位置，元素X∈ElementType,

线性表基本操作主要有：

void PrintL(List L); //打印线性表 
List MakeEmpty(); //初始化一个空的线性表
ElementType FindKth( int K, List L);//根据位序K，返回相对应位置上的元素
void Insert( ElementType X, int i, List L);//在位序i前面插入一个新元素X
void Delete( int i, List L);//删除指定位序i的元素
void Change( int i, ElementType x, List L);//更改指定位置的元素内容 
int Find( ElementType X, List L);//在线性表中查找X第一次出现的位置
int Length( List L); //返回线性表L的长度

线性表的顺序存储实现

  1. 利用数组的连续存储空间顺序存放线性表的各元素
利用数组的连续存储空间 顺序存放线性表的各元素
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
#define MAXSIZE 100

struct Lnode {
    ElementType Data[MAXSIZE];
    int Last;
};
typedef struct Lnode *List; 
struct Lnode Ld;
List PtrL;


void PrintL(List L); //打印线性表 
List MakeEmpty(); //初始化一个空的线性表
ElementType FindKth( int K, List L);//根据位序K，返回相对应位置上的元素
void Insert( ElementType X, int i, List L);//在位序i前面插入一个新元素X
void Delete( int i, List L);//删除指定位序i的元素
void Change( int i, ElementType x, List L);//更改指定位置的元素内容 
int Find( ElementType X, List L);//在线性表中查找X第一次出现的位置
int Length( List L); //返回线性表L的长度


int main()
{
    PtrL = MakeEmpty(); 
    int i;
    for( i=0; i<20; i++)
    {
        PtrL->Data[i] = i+1;
        PtrL->Last = i;
    }
    PrintL(PtrL);
    ElementType x;
    x = FindKth(10, PtrL);
    printf("x = %d\n", x);
    printf("The index of x is :%d\n", Find(x, PtrL));
    Insert(x, 5, PtrL);
    PrintL(PtrL);
    Delete(10, PtrL);
    PrintL(PtrL);
    Change(5, 21, PtrL);
    PrintL(PtrL);
    
    return 0;
}
void PrintL( List L)
{
    int i;
    printf("The List is: \n");
    for( i=0; i<= L->Last; i++)
    {
        printf("%4d", L->Data[i]);
    }
    printf("\n");
    return;
}
List MakeEmpty()
{
    List PtrL;
    PtrL = (List )malloc(sizeof(struct Lnode));
    PtrL->Last = -1;
    return PtrL;
}
ElementType FindKth( int K, List L)
{
    if( K > L->Last )
    {
        printf("exceed!\n");
        return 99;
    } else if( L->Last == -1) {
        printf("This List is empty!\n");
        return -1;
    }
    return L->Data[K];
}
void Insert( ElementType X, int i, List L)
{
    int j;
    if( L->Last == MAXSIZE-1 )
    {//表满
        printf("This list is full!\n"); 
        return;
    }
    for(  j=L->Last+1; j>i; j-- )
    {
        L->Data[j] = L->Data[j-1];
    }
    L->Data[j] = X;
    L->Last++;
    return;
}
void Delete( int i, List L)
{
    if( L->Last == -1)
    {//表空 
        printf("This List is empty!\n");
        return;
    }
    if( i > L->Last )
    {
        printf("The element is not found at this list!\n", i);
        return;
    }
    for( i; i<L->Last; i++)
    {
        L->Data[i] = L->Data[i+1];
    }
    L->Last--;
    return;
}
void Change( int i, ElementType x, List L)
{
    if( L->Last == -1)  {
        printf("This List is empty!\n");
        return;
    } else if( i > L->Last ) {
        printf("The element is not found at this list!\n", i);
        return;
    } else {
        L->Data[i] = x;
        return;
    }
}
int Find( ElementType X, List L)
{
    int i=0;
    while( L->Data[i] != X && i <= L->Last )
    {
        i++;
    }
    if( i > L->Last )
        return -1; //not find ElementType X
    else 
        return i; 
}
int Length( List L)
{
    return L->Last;
}
  1. 利用链式存储来实现线性表的逻辑相邻关系
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
#define MAXSIZE 100
typedef struct Lnode *ptrToLnode; 
struct Lnode {
    ElementType Data;
    ptrToLnode Next;
};
typedef ptrToLnode List;
typedef ptrToLnode Position;
List PtrL; 

void PrintL(List L); //打印线性表 
List MakeEmpty(); //初始化一个空的线性表
int Length( List L); //返回线性表L的长度
List FindKth( int K, List L);//根据位序K，返回相对应位置上的元素
List Find( ElementType x, List L);//在线性表中查找X第一次出现的位置
List Insert( ElementType x, int i, List L);//在位序i前面插入一个新元素X
List Delete( int i, List L);//删除指定位序i的元素
List Change( int i, ElementType x, List L);//更改指定位置的元素内容 


int main()
{
    PtrL = MakeEmpty();
    int i;
    List p = PtrL;
    for( i=0; i<20; i++)
    {
        if( i==0 )
        {
            p->Data = i+1;
            p->Next = NULL;
        }
        else
        {
            List t;
            t = (List )malloc(sizeof(struct Lnode));
            t->Data = i+1;
            t->Next = NULL;
            p->Next = t;
            p = p->Next;
        }
    }
    PrintL(PtrL);
    printf("Length = %d\n", Length(PtrL));
    printf("Findkth(10) = %d\n", FindKth(10, PtrL)->Data);
    printf("Find(12) = %d\n", Find(12, PtrL)->Data);
    PtrL = Insert(99,1,PtrL);
    PrintL(PtrL);
    PtrL = Change(1,0,PtrL);
    PrintL(PtrL);
    PtrL = Delete(1,PtrL);
    PrintL(PtrL);

    return 0;
}
void PrintL( List L)
{
    if( L == NULL )
    {
        printf("This List is empty!\n");
        return; 
    } else {
        List temp = L;
        printf("This List is:\n");
        while( temp->Next != NULL ) 
        {
            printf("%4d", temp->Data);
            temp = temp->Next;
        }
        printf("%4d", temp->Data);
        printf("\n");
        return;
    }
}
List MakeEmpty()
{
    List L;
    L = (List )malloc(sizeof(struct Lnode));
    L->Next == NULL;
    return L;
}
int Length( List L)
{
    List T = L;
    int i = 0;
    while( T != NULL)
    {
        i++;
        T = T->Next; 
    }
    return i;
}
List FindKth(int K, List L)
{
    List T = L; 
    int i=1;
    while( i != K && T != NULL)
    {
        T = T->Next;
        i++;
    }
    if( i==K )
        return T;
    else return NULL;
}
List Find(  ElementType x, List L)
{
    List T = L;
    while( T != NULL && T->Data != x )
    {
        T = T->Next;
    }
    if( T->Data == x)
        return T;
    else return NULL;
}
List Insert( ElementType x, int i, List L)
{
    if( i==1 )
    {
        List s;
        s = (List)malloc(sizeof(struct Lnode));
        s->Data = x;
        s->Next = L;
        return s;
    } else {
        int j = 1;
        List T = L;
        while( j != i - 1 && T != NULL)
        {
            T = T->Next;
            j++;
        }
        if( T == NULL )
        {
            printf("not find position %d\n", i);
            return L;
        } else {
            List s;
            s = (List)malloc(sizeof(struct Lnode));
            s->Data = x;
            s->Next = T->Next;
            T->Next = s;
            return L;
        }
    }
}
List Delete( int i, List L)
{
    if( i==1 )
    {
        return L->Next;
    }
    else {
        int j=1;    
        List T = L;
        while( j != i-1 && T != NULL)
        {
            T = T->Next;
            j++;
        }
        if( T == NULL )
        {
            printf("not found position %d\n", i);
            return L;
        } else {
            Position A = T->Next;
            T->Next = A->Next;
            free(A);
            return L;
        }
    }
}
List Change( int i, ElementType x, List L)
{
    if( i==1 )
    {
        L->Data = x;
        return L;
    }
    else {
        int j=1;    
        List T = L;
        while( j != i-1 && T != NULL)
        {
            T = T->Next;
            j++;
        }
        if( T == NULL )
        {
            printf("not found position %d\n", i);
            return L;
        } else {
            T->Data = x;
            return L;
        }
    }
}

广义表

  • 广义表是线性表的推广
  • 对于线性表而言，n个元素都是基本的单元素
  • 广义表中，这些元素不仅可以是单元素也可以是另一个广义表
    广义表 
typedef struct Gnode *GList;
struct Gnode {
    int Tag; //标志域：0表示节点是单元素，1表示节点是广义表
    union { //子表指针域SubList和单元素数字域Data复用，及公用存储空间 
        ElementType Data;
        GList SubList;
    }URegion;
    Glist Next; //指向后继节点 
}
广义表节点示意图

多重链表

多重链表链表中的节点可能同时隶属于多个链

  • 多重链表中节点的指针域会有多个，如前面的例子中SubList和Next两个指针域

  • 注意包含多个指针域的链表不一定就是多重链表，比如在双向链表不是多重链表


    多重链表1
    多重链表2
    多重链表3

相关文章

  • 线性表的相关操作

    集合 --- 创建线性表 解散 --- 销毁线性表 长度 --- 得到线性表的长度 出列 --- 从线性表删除一个...

  • [数据结构]第二章线性表(1)——线性表

    线性表 线性表的基本概念 线性表的定义 线性表是具有相同数据类型的n(n>=0)个元素的有限序列。 线性表的基本操...

  • 数据结构与算法（二）

    线性表及其顺序存储结构 线性表的基本概念 线性结构又称为线性表，线性表是最简单也是最常用的一种数据结构。 线性表的...

  • 线性表及应用

    线性表 “线性表（List）：零个或多个数据元素的有限序列。” 线性表的顺序存储结构 线性表的顺序存储结构，指的是...

  • 数据结构03-线性表之顺序表

    第三章 线性表之顺序表 第三章 线性表之顺序表一、什么是线性表？1> 概念2> 线性表的基本操作二、线性表的顺序存...

  • 数据结构之线性表

    1、线性表-顺序表线性表-顺序表

  • 线性表数据结构

    线性表 线性表就是数据排成像一条线的结构，每个线性表上的数据最多只有前和后两个方向。与线性表对立的是非线性表，如二...

  • 大话数据结构 - 线性表

    代码GitHub地址 线性表 线性表需要相同的数据类型 线性表的处理方式都是先取代，后目的。比如删除链式线性表的某...

  • 数据结构-线性表（顺序表和链表）

    大纲：理解线性表的逻辑结构掌握线性表的顺序存贮结构和链式存贮结构；掌握线性表基本操作的实现。了解线性表的应用。 线...

  • 数据结构 线性表 单链表 c语言实现可运行

    线性表 线性表概念 线性表定义:具有相同特性数据元素的有限序列。线性表的逻辑结构:线性结构。只有一个表头，只有一个...

网友评论

      本文标题：线性表🚀

      本文链接：https://www.haomeiwen.com/subject/maqbghtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|线性表🚀|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！