线性表(什么是线性表的基本理论知)

1.什么是线性表的基本理论知

一、线性表（定义） 线性表（Linear List）：是具有相同属性的数据元素的一个有限序列。

它有顺序、链接、散列等存储结构，第一元素称为表头元素，最后一个元素称为表尾元素。在任意一对；相邻结点ai,ai+1(1 线性表的基本特征：若至少含有有一个结点，则除起始结点没有直接前趋外，其他结点有且仅有一个直接前趋；除终端结点没有直接后继外，其他结点有且仅有一个直接后继。

二、线性表的存储结构及基本运算 线性表根据其物理存储连续性状态及存储顺序可划分为顺序存储结构和链表存储结构。 顺序存储结构：把线性表中的所有元素按照其逻辑顺序依次存储到计算机存储器中从指定存储位置开始的一块连续的存储空间中。

因此，逻辑结构中相邻的结点在存储结构中仍相邻。我们把顺序存储的线性表统称为顺序表，它的顺序存储结构是利用数组来实现的。

顺序存储下的线性表的基本运算： （1）初始化线性表。即构造一个空表，它的长度（length）置0。

(2)清除线性表中的所有元素。 （3）获取线性表的长度。

（4）检查线性表是否为空。 （5）获取线性表中指定序号的元素。

（6）遍历线性表。 （7）从线性表查找具有给定值的元素。

（8）更新线性表中具有给定值的元素。 （9）向线性表的末尾添加一个元素。

（10）向线性表的表头插入一个元素。 （11）向线性表中满足条件的位置插入一个元素。

（12）从线性表中删除表头元素。 （13）从线性表中删除等于给定值的元素。

（14）对线性表进行排序。 链接存储结构：每一个存储单位（称之为存储结点，简称结点），由所存元素本身的信息和元素间逻辑关系信息组成，它可以任意顺序存储任意存储空间里。

也就是说，链接存储结构不要求元素依次存储在一块连续存储空间。 采用链接存储结构的线性表称之为链接表。

在进行链接存储时，每个结点除包含元素本身外，若只设置一个引用指向它后面元素（后继），这样构成的链接表称之为线性单向链接表，简称单链表。 若设置两个引用分别指向它前面元素（前驱）和后面的元素（后继），这样构成的链表称之为线性双向链接表，简称双向链表。

在单链表中，若尾结点的后继不是指向null，而是指头结点，称之为循环链表。 链表的基本运算： （1）初始化，通过new建立一个空表。

（2）求表长size。线性表的表长等于单嘁链表所含表结点的个数。

（3）按序号查找。链表逻辑相邻的结点并不是存贮在物理相邻的单元中，所以不能像顺序表那样按序号i查找结点，在链表中只能从首结点出发，顺后继next逐个往下搜索，直到找到第i个结点为止。

故链表无法实现随机存取。 （4）定位，即按值查找，也就是从前往后的顺序，依次比较各结点数值域（item）与给定值X相等的结点的序号就是运算幽幽结果，若没有这样的结点运算结果为0。

(5)删除。除了remove(Object o)方法需要先定义，其它各重载remove（)方法直接将待删除结点的item、prev、next置为null，然后修改其前驱的后继，后继的前驱，必要是修改first、last。

(6)插入。删除是unlink，插入是link，基本上删除的反向操作。

链表的其他运算： （1）建表，即将一个线性表中的数据元素依次输入并建立该线性表的单链表，也就是初始化运算和插入运算结合应用。 （2）消除重复结点，即删除数据域（item）的值相同的多余结点，只保留其中序号最小的一个。

顺序表和链表的比较： 1）顺序表无需额外空间存储各结点间关系系，较之链表占用存储空间小； 2）顺序表以位置（索引）直接存取各结点，存取方便；插入和删除时需要移动大量数据，效率低；链表在存取结点时需要从头结点或尾结点逐一打开后继或前驱，存取效率较低，而插入和删除时，只需要修改前驱和后继，不需要移动数据，效率较顺序表要高。 3）顺序表要求占用连续空间，只能预先分配（静态分配），分配空间太大，易造成资源浪费，太小，易造成数据溢出；链表没有这方面的要求，存储空间可以动态分配，任意修改空间大小。

4）顺序表只能存储线性表，而链表除此之外还可以存储非线性表。 三、栈 栈（Stack）又称堆栈：是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。

允许进行插入和删除的一端称为栈项，另一端称为栈底。栈项的第一个元素称为栈顶元素，不含任何数据元素的栈称为空栈。

进栈（也称入栈），即向一个栈插入新元素，它是把该元素放到栈项元素的上面，使之成为新的栈顶元素。 出栈（或退栈），即从一个栈删除元素，它是把栈顶元素删除掉，使其下面相邻的元素成为新的栈顶元素。

栈的特征（栈的修改原则）：后进先出或先进后出（Last In First Out，简称LIFO）。 栈有两种实现方法：顺序实现和链接实现，这和线性表相似。

栈的顺序存储结构称为顺序栈，通常由一个一维数组（Arrays）实现。栈的链式存储结构称为链栈，可以通过链表（LinkedList）实现。

栈的基本运算： （1）初始化栈，构造一个空栈。 （2）清空栈 （3）检查栈是否为空 （4）读取栈顶元素 （5）向栈中插入元素 （6）从栈中删除元素 （7）检查栈是否已满（仅适用于顺序栈） 四、队列 队列（Queue）简称队，也是一种去处受限的线性表，其限制是仅允许在表的一端进。

2.线性表的基本操作

#include#include#include# define null 0 typedef char ElemType； /* 字符型数据*/ typedef struct LNode { ElemType data; struct LNode *next; }; void setnull(struct LNode **p); int length (struct LNode **p); ElemType get(struct LNode **p,int i); void insert(struct LNode **p,ElemType x,int i); int locate(struct LNode **p,ElemType x); void Delete(struct LNode **p,int i); void display(struct LNode **p); struct LNode * reverse(struct LNode **head); main() { struct LNode *head； /*定义变量*/ int select,x1,x2,x3; int i,n; int m,g; char e,y; setnull(&head)； /*建一链表并设置为空表*/ printf（"请输入数据长度： "）； scanf("%d",&n); printf（"将数据插入到单链表中： "）； for(i=1;i { scanf("%c",&y); if(y=='\n') i--; else { printf（"将数据插入到单链表中： "）； insert(&head,y,i)； } } /*插入数据到链表*/ display(&head)； /*显示链表所有数据*/ printf("select 1 求长度 length()\n"); printf("select 2 取结点 get()\n"); printf("select 3 求值查找 locate()\n"); printf("select 4 删除结点 delete()\n"); printf("select 5 链表反转 reverse()\n"); printf("input your select: "); scanf("%d",&select); switch(select) { case 1: { x1=length(&head); printf（"输出单链表的长度%d\n ",x1）; display(&head); }break; case 2: { printf（"请输入要取得结点： "）； scanf("%d",&m); x2=get(&head,m); printf("%c\n",x2); display(&head); }break; case 3: { printf（"请输入要查找的数据： "）； scanf("\n%c",&e); x3=locate(&head,e); printf("%d\n",x3); display(&head); }break; case 4: { printf（"请输入要删除的结点： "）； scanf("%d",&g); Delete(&head,g); display(&head); }break; case 5: { printf（"链表反转："）； reverse(&head); display(&head); }break; } } void setnull(struct LNode **p) { *p=null; } int length (struct LNode **p) { int n=0; struct LNode *q=*p; while (q!=null) { n++; q=q->next; } return(n); } ElemType get(struct LNode **p,int i) { int j=1; struct LNode *q=*p; while (j { q=q->next; j++; } if(q!=null) return(q->data); else printf（"位置参数不正确！\n"）; return null; } int locate(struct LNode **p,ElemType x) { int n=0; struct LNode *q=*p; while (q!=null&&q->data!=x) { q=q->next; n++; } if(q==null) return(-1); else return(n+1); } void insert(struct LNode **p,ElemType x,int i) { int j=1; struct LNode *s,*q; q=*p; s=(struct LNode *)malloc(sizeof(struct LNode)); s->data=x; if(i==1) { s->next=q; *p = s; } else { while(jnext!=null) { q=q->next; j++; } if(j==i-1) { s->next=q->next; q->next=s; } else printf（"位置参数不正确！\n"）; } } void Delete(struct LNode **p,int i) { int j=1; struct LNode *q=*p,*t=null; if(i==1) { t=q; *p=q->next; } else { while(jnext!=null) { q=q->next; j++; } if(q->next!=null&&j==i-1) { t=q->next; q->next=t->next; } else printf（"位置参数不正确！\n"）; } if(t=null) free(t); } void display(struct LNode **p) { struct LNode *q; q=*p; printf（"单链表显示： "）； if(q==null) printf（"链表为空！"）； else if (q->next==null) printf("%c\n",q->data); else { while(q->next!=null) { printf("%c->",q->data); q=q->next; } printf("%c",q->data); } printf("\n"); } struct LNode * reverse(struct LNode **head) { struct LNode *p,*q; p=null; while((*head)->next!=null) { q=p; p=*head; (*head)=(*head)->next; p->next=q; }(*head)->next=p; return *head; }。

3.线性表的定义是什么

线性表不仅是指在VF中，任何涉及到数据的知识都有线性表：线性表是最基本、最简单、也是最常用的一种数据结构。

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。

因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。 线性表是一种常用的数据结构，以下介绍线性表及其顺序存储，并对栈和队列及它们的顺序实现给出了详细的设计描述。

在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。

线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。一般地，一个线性表可以表示成一个线性序列：k1,k2，…，kn，其中k1是开始结点，kn是终端结点。

是一个数据元素的有序（次序）集 线性结构的基本特征为： 1.集合中必存在唯一的一个“第一元素”； 2.集合中必存在唯一的一个“最后元素”； 3.除最后一个元素之外，均有唯一的后继（后件）； 4.除第一个元素之外，均有唯一的前驱（前件）。 由n(n≥0)个数据元素（结点）a1,a2，…，an组成的有限序列。

数据元素的个数n定义为表的长度。 当n=0时称为空表。

常常将非空的线性表（n>0）记作： （a1,a2，…an） 数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。 线性表的基本操作 1)Setnull(L)置空表 2)Length(L)求表长度；求表中元素个数 3)Get(L,i)取表中第i个元素（1≤i≤n） 4)Prior(L,i)取i的前趋元素 5)Next(L,i)取i的后继元素 6)Locate(L,x)返回指定元素在表中的位置 7)Insert(L,i,x)插入元素 8)Delete(L,x)删除元素 9)Empty(L)判别表是否为空 线性表具有如下的结构特点： 1.均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数所类长度。

2.有序性：各数据元素在线性表中的位置只取决于它们的序与，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个“的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前趋和后面均只有一个数据元素（直接后继）。 在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。

链式存储结构将在本网站线性链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈.队列和串也是线性表的特殊情况，又称为受限的线性结构。

4.线性表的基本特征是什么

线性表的基本特征是：

1、集合中必存在唯一的一个第一元素。

2、集合中必存在唯一的一个最后元素 。

3、除最后一个元素之外，均有唯一的后继。

4、除第一个元素之外，均有唯一的前驱。

扩展资料：

线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，称为线性表的顺序存储结构或顺序映像。

它以物理位置相邻来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。链式表示指的是用一组任意的存储单元存储线性表中的数据元素，称为线性表的链式存储结构。

它的存储单元可以是连续的，也可以是不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息，这两部分信息组成数据元素的存储映像，称为结点。

参考资料来源：百度百科—线性表