线性表的概念
线性表是数据结构中最基本的一种，它是由n个具有相同数据类型的数据元素组成的有限序列。线性表的特点是数据元素之间的关系是一对一的，即每个数据元素都只有一个直接前驱和一个直接后继。线性表可以用顺序存储结构或链式存储结构来实现。
顺序存储结构是将线性表中的数据元素按其逻辑顺序依次存储在一组地址连续的存储单元中，这样就可以通过元素在存储器中的相对位置来表示元素之间的逻辑关系。而链式存储结构则是通过指针来实现数据元素之间的逻辑关系，每个数据元素都有一个指针域，指向其直接后继元素的存储位置。
线性表的应用十分广泛，它在计算机科学领域中有着重要的地位。下面我们将从几个方面来探讨线性表的应用。
首先，线性表可以用来实现栈和队列。栈是一种先进后出的数据结构，而队列是一种先进先出的数据结构。它们都可以通过线性表来实现，栈可以用顺序存储结构或链式存储结构来实现，而队列通常使用链式存储结构来实现。
其次，线性表可以用来实现线性表。在实际的软件开发中，经常需要对数据进行排序操作，而线性表提供了一个非常方便的数据结构来实现排序算法。常见的排序算法有冒泡排序、选择排序、插入排序、快速排序等，它们都可以通过线性表来实现。
另外，线性表还可以用来实现线性表。线性表可以用来表示多项式，多项式的加法、减法、乘法等运算都可以通过线性表来实现。这在数学计算和科学计算中有着重要的应用。
此外，线性表还可以用来实现图的邻接表。图是一种非线性的数据结构，它由顶点的有限集合和顶点之间边的集合组成。图的邻接表是一种常用的表示方法，它可以通过线性表来实现。邻接表中的每个顶点都对应一个线性表，用来存储与该顶点相邻的顶点。
总的来说，线性表作为数据结构中最基本的一种，它在计算机科学领域中有着广泛的应用。通过线性表，我们可以实现栈和队列、排序算法、多项式运算、图的邻接表等功能。因此，对线性表的深入理解和掌握对于计算机科学领域的学习和工作都是非常重要的。希望通过本文的介绍，读者能对线性表有一个更深入的理解，并能够在实际的应用中灵活运用线性表。
/************线性表的顺序存储结构定义和基本操作算法实现************/
#include "stdio.h"
/***********************线性表的顺序存储结构定义*******************/
#define MAX 11 /*线性表可能达到的最大长度值*/
typedef int datatype;
typedef struct
{datatype data[MAX];
int last;}list;
/************************1.线性表的初始化***************************/
void init(list *lp)
{lp->last=0;}
/************************2.求线性表的长度***************************/
int length(list *lp)
{ return (lp->last);}
/***************3.插入运算,在表第i个位置插入一个值为 x的新元素******/
void insert(list *lp,int i,datatype x)
{ int j;
if(lp->last==MAX-1)
printf("Overflow!\n"); /*表已满*/
else if(i<1||i>lp->last+1)
printf("Error!\n"); /*插入位置错误*/
else
{for(j=lp->last;j>=i;j--)
lp->data[j+1]=lp->data[j]; /*数据元素后移*/
第1讲 线性表
本章主要掌握如下内容：
线性表的定义和基本操作，线性表的实现,线性表的顺序存储结构及链式存储结构，线性表的应用。
知识点分析
（一）线性表的定义和基本操作
1．线性表基本概念
1）定义：是由相同类型的结点组成的有限序列。如：由n个结点组成的线性表
（ a1, a2, …, an）
a1是最前结点，an是最后结点。结点也称为数据元素或者记录。
2）线性表的长度：线性表中结点的个数称为其长度。长度为0的线性表称为空表。
3）结点之间的关系：设线性表记为（a1,a2,„ai-1 , ai, ai+1 ,„an），称ai-1是ai的直接前驱结点．．．．（简称前驱），ai+1是ai的直接后继结点．．．．（简称后继）。
4）线性表的性质：
① 线性表结点间的相对位置是固定．．的，结点间的关系由结点在表中的位置确定。
② 如果两个线性表有相同的数据结点，但它们的结点顺序不一致，该两个线性表也是不相等的。
注意：线性表中结点的类型可以是任何数据（包括简单类型和复杂类型），即结点可以有多个成分，其中能唯一标识表元的成分称为关键字（key），或简称键。以后的讨论都只考虑键，而忽略其它成分，这样有利于把握主要问题，便于理解。
『经典例题解析』
线性表的特点是每个元素都有一个前驱和一个后继。( )
【答案】错误。
【解析】线性表的第一个数据元素没有前驱，最后一个元素没有后继。其余的所有元素都有一个前驱和后继。
2．线性表的抽象数据类型
线性表是一个相当灵活的数据结构，其长度可以根据需要增加或减少。从操作上讲，用户不仅可以对线性表的数据元素进行访问操作，还可以进行插入、删除、定位等操作。
#include ""
/***********************线性表的顺序存储结构定义*******************/
#define MAX 11 /*线性表可能达到的最大长度值*/
typedef int datatype;
typedef struct
{datatype data[MAX];
int last;}list;
/************************1.线性表的初始化***************************/
void init(list *lp)
{lp->last=0;}
/************************2.求线性表的长度***************************/
int length(list *lp)
{ return (lp->last);}
/***************3.插入运算,在表第i个位置插入一个值为 x的新元素******/
void insert(list *lp,int i,datatype x)
{ int j;
if(lp->last==MAX-1)
printf("Overflow!\n"); /*表已满*/
else if(i<1||i>lp->last+1)
printf("Error!\n"); /*插入位置错误*/
else
{for(j=lp->last;j>=i;j--)
lp->data[j+1]=lp->data[j]; /*数据元素后移*/
lp->data[i]=x; /*插入x */
