线性表（Linear List）
 
是由有限个相同类型的数据元素组成的有序序列，一般记作（a 1 ,a 2 ,…,a n ）
 
特点
 除了a 1 和a n 之外，任意元素a i 都有一个直接前趋a i-1 和一个直接后继a i+1
  a 1 无前趋
  a n 无后继
 
表的长度：线性表中数据元素的个数
空表：元素个数为0的表
 
线性表的运算
 
在线性表中，经常执行下列操作
  确定线性表是否为空
  确定线性表的长度
  查找某个元素
  删除第i个元素
  在第i个位置插入一个新元素
 
线性表的存储结构
 
采用顺序存储结构的称为顺序表
 采用链式存储结构的称为线性链表
 
顺序表
 
 
顺序表中的数据元素按照逻辑顺序依次存放在一组连续的存储 单元中
 
 
每个元素a i 的存储地址是该元素在表中位置i的线性函数
 
 
 
顺序表的定义
 
const int maxsize=200; // 顺序表最大允许长度
struct SeqList {
ElemType data[maxsize]; // 顺序表存储数组的地址
int length;  // 顺序表当前长度
}；
SeqList List;
List.length=0;
 
在顺序表中插入元素
 
① 判断插入位置是否合理以及该表是否已满
 ② 从最后一个元素开始依次向前，将每个元素向后移动一个位置
 ，一直到第i个元素为止
 ③ 向空出的第i个位置存入新元素x
 ④ 将线性表长度加1
 
void Insert( SeqList *L, int i, ElemType x )
{
if( i<1 || i>L->length+1 || L->length==maxsize )
cout<<"插入位置错误或表满";
else {
for( int j=L->length-1; j>=i-1; j-- )
L->data[j+1] = L->data[j]; // 元素依次向后移动
L->data[i-1] = x; // 向第 i 个位置存入新元素 x
L->length++; // 表长度加一
}
}
 
在顺序表中删除元素
 
① 判断要删除元素的位置的合理性
 ② 从第i+1个元素开始，依次向后直到最后一个元素为止，将每
 个元素向前移动一个位置。这时第i个元素已经被覆盖删除
 ③ 将线性表长度减1
 
void Delete( SeqList *L, int i )
{
if(i<1 || i>L->length )
cout<<"表中没有第"<<i<<"个元素";
else {
for ( int j=i; j<=L->length-1; j++ )
L->data[j-1] = L->data[j];
L->length--;
}
}
 
在顺序表中查找元素
 
数据元素是基本数据类型
  与数据元素本身进行对比
 数据元素是结构体或类对象
  往往是与数据元素的某个属性比较
 
int Find( SeqList *L, ElemType x )
{
for( int i = 0; i<L->length; i++ )
{
if( L->data[i]==x ) return i+1; //查找成功，返回元素位置
}
return 0; //查找失败, 返回 0
}
 
顺序存储的特点
 
优点
  不需要为元素间的逻辑关系增加额外的存储空间
  可以方便地随机存取顺序表中任意一个元素
 缺点
  元素进行插入和删除时都要进行大量元素的移动，因此，操作的效率
 较低
  占用连续的存储空间，存储空间的大小在初始化时就必须确定

 
简介
         线性表是最基本、最简单、也是最常用的一种
数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。 
 
 
结构
 　　线性表是一种常用的
数据结构，以下介绍线性表及其顺序存储，并对栈和
队列及它们的顺序实现给出了详细的设计描述。 　　在实际应用中，线性表都是以
栈、队列、
字符串、
数组等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。　　线性表是一个线性结构，它是一个含有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）MakeEmpty(L) 这是一个将L变为空表的方法　　
 
2）Length（L） 返回表L的长度，即表中元素个数　　
 
3）Get（L，i） 这是一个函数，函数值为L中位置i处的元素（1≤i≤n）　　
 
4）Prev（L，i） 取i的前趋元素　　
 
5）Next（L，i） 取i的后继元素　　
 
6）Locate（L，x） 这是一个函数，函数值为元素x在L中的位置　　
 
7）Insert（L，i，x）在表L的位置i处插入元素x，将原占据位置i的元素及后面的元素都向后推一个位置　　
 
8）Delete（L，p） 从表L中删除位置p处的元素　　
 
9）IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false　　
 
10）Clear（L）清除所有元素　　
 
11）Init（L）同第一个，初始化线性表为空　　
 
12）Traverse（L）遍历输出所有元素　　
 
13）Find（L，x）查找并返回元素　　
 
14）Update（L，x）修改元素　　
 
15）Sort（L）对所有元素重新按给定的条件排序
 
结构特点
 　　线性表具有如下的结构特点：　　1.均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的
数据类型和长度。　　2.有序性：各数据元素在线性表中的位置只取决于它们的序与，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个“的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素（直接后继）。　　在实现线性表数据元素的存储方面，一般可用顺序存储结构和
链式存储结构两种方法。链式存储结构将在本网站线性
链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈．队列和串也是线性表的特殊情况，又称为受限的线性结构。 　　 
 

 
 
附一道选择题：　　
 
下列哪个不是线性表（d）　　
 
A. 链表 B. 队列 C.栈 D.关联数组
 
 

设计一个顺序表，实现删除、插入、查找、排序等功能。
 
 
 
解析：根据下列需要实现的功能具体分析
 
1.在长度为n的线性表的第i个位置插入一个新的数据item（尾部插入法）
 
该操作是指在线性表的第i-1个位置与线性表的第i个位置插入一个新的数据元素，使得线性表的长度变为n+1，但是在进行插入时首先应该判断线性表是否已满或者存储空间已被占满，并且还需要测试插入的位置是否恰当，由此插入的步骤分为：先做判断是否插入不当；然后将第i个元素到第n个元素之间的所有元素依次向后移动一个位置；再将item插入到第i个位置上，然后修改线性表的长度。
 
2.删除长度为n的线性表的第i个元素
 
该操作是指线性表的第i个位置上的元素从列表中去掉，使得线性表的长度为n-1，在进行删除操作时，需要先判断线性表是否为空以及删除的位置是否合适，然后进行删除过程：先将表中第i+1个元素到第n个元素依次向前移动一个单位长度，然后将线性表的长度减一。
 
3.确定元素item在长度为n的线性表中的位置
 
该操作只需从第一个元素开始，从前往后依次通过比较来确定给定元素的位置，如果线性表中存在该元素则返回其位置，否则输出-1，表示查找失败。
 
4.删除表中重复的元素
 
该操作从线性表的第1个元素开始到最后1个元素为止，依次检查在某个元素后面的元素中是否存在与之相同的元素，若存在，则删除后面那个元素，并且及时修改表的长度。
 
5. 对线性表中元素进行排序
 
该操作是第i趟排序从线性表的后面的n-i个数据中选择一个值最小的数据元素，并将其与第i个元素交换位置，如此经过n-1趟，形成个值从小到大的线性表。
 
#include<iostream>
#include<cstdio>
#include<cstring>
#define max 1000
using namespace std;

void insertlist(int a[],int &n,int i,int item)
{	
	
	if(n==max||i<1||i>n+1)
		printf("表满或插入位置不正确!");	 
	for(int j=n;j>=i;j--)
		a[j+1]=a[j];
	a[i]=item;
	n++;
}

void deletelist(int a[],int &n,int i)
{
	if(i<1||i>n)
		printf("表空或删除位置不正确!");	
	for(int j=i+1;j<=n;j++)
		a[j-1]=a[j];
	n--;
}

int locate(int a[],int &n,int item)
{
	for(int j=1;j<=n;j++)
		if(a[j]==item)
			return j;
	return -1;//查找失败 
}

void purge(int a[],int &n) 
{
	int i=1,j;
	while(i<=n)
	{
		j=i+1;
		while(j<=n)
		{
			if(a[j]==a[i])
			{
				deletelist(a,n,j);
			}
			else
				j++;
		}
		i++;
	}
}

void selectsort(int a[],int &n)
{
	int temp;
	for(int i=1;i<n;i++)
	{
		for(int j=i+1;j<=n;j++)
		{
			if(a[i]>a[j])
			{
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
	}
}

void selectsort1(int a[],int &n)
{
	int temp,d;
	for(int i=1;i<n;i++)
	{
		d=i;//假设最小元素为未排序线性表的第1个元素 
		for(int j=i+1;j<=n;j++)
		{
			if(a[j]>a[d])
				d=j;//寻找最小的元素，并记录其位置 
			if(d!=i)//当最小元素不是第1个元素时 
			{
				temp=a[i];
				a[i]=a[j];
				a[j]=temp;
			}
		}
	}
}

void printinfo(int a[max],int n)//输出 
{
	for(int j=1;j<=n;j++)
		printf("%d ",a[j]);
	printf("\n");
}

int main()
{
	int a[max],n,i,item;
	scanf("%d",&n);
	for(int j=1;j<=n;j++)
		scanf("%d",&a[j]);
		
	//在长度为n的线性表的第i个位置插入一个新的数据item 	
	scanf("%d %d",&i,&item); 
	insertlist(a,n,i,item);
	printinfo(a,n);
	
	//删除长度为n的线性表的第i个元素
	scanf("%d",&i);
	deletelist(a,n,i);
	printinfo(a,n);
	
	//确定元素item在长度为n的线性表中的位置 
	scanf("%d",&item);
	printf("%d\n",locate(a,n,item));
	
	//删除表中重复的元素
	purge(a,n);
	printinfo(a,n);
	
	//对线性表中元素进行排序
	selectsort(a,n);
	printinfo(a,n);
	
	//对线性表中元素进行排序
	selectsort1(a,n);
	printinfo(a,n);

	return 0;
}
 
 

 
 
线性表及其实现
   

     
多项式的表示
什么是线性表
线性表的抽象数据类型描述
线性表的顺序存储实现
线性表的链式存储实现
 
 
 
 
 
线性表及其实现
 
多项式的表示
 
[例] 一元多项式及其运算 
 一元多项式 ：  
 主要运算：多项式相加、相减、相乘等 
 【分析】如何表示多项式? 
 多项式的关键数据： 
 多项式项数n 
 各项系数ai 及指数 i 
 方法1：顺序存储结构直接表示 
 数组各分量对应多项式各项： a[i]: 项xi的系数ai 
  
 方法2：顺序存储结构表示非零项 
  
 按指数大小有序存储！ 
 相加过程：从头开始，比较两个多项式当前对应项的指数 
 
 
方法3：链表结构存储非零项 
 
 
什么是线性表
 
多项式表示问题的启示： 
 1. 同一个问题可以有不同的表示（存储）方法 
 2. 有一类共性问题：有序线性序列的组织和管理 
 线性表(Linear List) : 由同类型数据元素构成有序序列的线性结构 
 1.表中元素个数称为线性表的长度 
 2.线性表没有元素时，称为空表 
 3.表起始位置称表头，表结束位置称表尾
 
线性表的抽象数据类型描述
 
类型名称：线性表（List） 
 
数据对象集：线性表是 n (≥0)个元素构成的有序序列( a1, a2,… ,an ) 
 
操作集：线性表L属于 List，整数i表示位置，元素X 属于 ElementType， 线性表基本操作主要有： 
 
1、List MakeEmpty()：初始化一个空线性表L； 
 2、ElementType FindKth( int K, List L )：根据位序K，返回相应元素 ； 
 3、int Find( ElementType X, List L )：在线性表L中查找X的第一次出现位置； 
 5、void Delete( int i, List L )：删除指定位序i的元素； 
 6、int Length( List L )：返回线性表L的长度n。 
 
线性表的顺序存储实现
 
利用数组的连续存储空间顺序存放线性表的各元素 
  
 主要操作的实现 
 
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last;
};

/* 初始化 */
List MakeEmpty()
{
    List L;

    L = (List)malloc(sizeof(struct LNode));
    L->Last = -1;

    return L;
}

/* 查找 */
#define ERROR -1

Position Find( List L, ElementType X )
{
    Position i = 0;

    while( i <= L->Last && L->Data[i]!= X )
        i++;
    if ( i > L->Last )  return ERROR; /* 如果没找到，返回错误信息 */
    else  return i;  /* 找到后返回的是存储位置 */
}

/* 插入 */
/*注意:这里P是存储下标位置（从0开始）*/
bool Insert( List L, ElementType X, Position P ) 
{ /* 在L的指定位置P前插入一个新元素X */
    Position i;

    if ( L->Last == MAXSIZE-1) {
        /* 表空间已满，不能插入 */
        printf("表满"); 
        return false; 
    }  
    if ( P<0 || P>L->Last+1 ) { /* 检查插入位置的合法性 */
        printf("位置不合法");
        return false; 
    } 
    for( i=L->Last; i>=P; i-- )
        L->Data[i+1] = L->Data[i]; /* 将位置P及以后的元素顺序向后移动 */
    L->Data[P] = X;  /* 新元素插入 */
    L->Last++;       /* Last仍指向最后元素 */
    return true; 
} 

/* 删除 */
/*注意:这里P是存储下标位置（从0开始）/
bool Delete( List L, Position P )
{ /* 从L中删除指定位置P的元素 */
    Position i;

    if( P<0 || P>L->Last ) { /* 检查空表及删除位置的合法性 */
        printf("位置%d不存在元素", P ); 
        return false; 
    }
    for( i=P+1; i<=L->Last; i++ )
        L->Data[i-1] = L->Data[i]; /* 将位置P+1及以后的元素顺序向前移动 */
    L->Last--; /* Last仍指向最后元素 */
    return true;   
}
 
线性表的链式存储实现
 
不要求逻辑上相邻的两个元素物理上也相邻；通过“链”建 立起数据元素之间的逻辑关系。 
 插入、删除不需要移动数据元素，只需要修改“链”。 
 访问序号为 i 的元素？ 求线性表的长度？ 
 
int  Length ( List  PtrL ) {    
    List  p = PtrL;       /* p指向表的第一个结点*/ 
    int  j = 0;      
        while ( p ) {             
            p = p->Next;             
            j++;    /* 当前p指向的是第 j 个结点*/      
        }         
    return  j; 
}
 
typedef struct LNode *PtrToLNode;
struct LNode {
    ElementType Data;
    PtrToLNode Next;
};
typedef PtrToLNode Position;
typedef PtrToLNode List;

/* 查找 */
#define ERROR NULL

Position Find( List L, ElementType X )
{
    Position p = L; /* p指向L的第1个结点 */

    while ( p && p->Data!=X )
        p = p->Next;

    /* 下列语句可以用 return p; 替换 */
    if ( p )
        return p;
    else
        return ERROR;
}

/* 带头结点的插入 */
/*注意:这里P是链表结点指针，在P之前插入新结点 */
bool Insert( List L, ElementType X, Position P )
{ /* 这里默认L有头结点 */
    Position tmp, pre;

    /* 查找P的前一个结点 */        
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            
    if ( pre==NULL ) { /* P所指的结点不在L中 */
        printf("插入位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 在P前插入新结点 */
        tmp = (Position)malloc(sizeof(struct LNode)); /* 申请、填装结点 */
        tmp->Data = X; 
        tmp->Next = P;
        pre->Next = tmp;
        return true;
    }
}

/* 带头结点的删除 */
/*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */
bool Delete( List L, Position P )
{ /* 这里默认L有头结点 */
    Position tmp, pre;

    /* 查找P的前一个结点 */        
    for ( pre=L; pre&&pre->Next!=P; pre=pre->Next ) ;            
    if ( pre==NULL || P==NULL) { /* P所指的结点不在L中 */
        printf("删除位置参数错误\n");
        return false;
    }
    else { /* 找到了P的前一个结点pre */
        /* 将P位置的结点删除 */
        pre->Next = P->Next;
        free(P);
        return true;
    }
}
 
广义表(Generalized List) 
 广义表是线性表的推广 
 对于线性表而言， n个元素都是基本的单元素； 
 广义表中，这些元素不仅可以是单元素也可以是另一个广义表 
  
 多重链表： 
 链表中的节点可能同时隶属于多个链 
 多重链表中结点的指针域会有多个，如前面例子包含了Next和 SubList两个指针域；但包含两个指针域的链表并不一定是多重链表，比如在双向链表 不是多重链表。 
 多重链表有广泛的用途： 基本上如树、图这样相对 复杂的数据结构都可以采 用多重链表方式实现存储。 
 
 
矩阵可以用二维数组表示，但二维数组表示有两个缺陷： 
 数组的大小需要事先确定，对于“稀疏矩阵 ”，将造成大量的存储空间浪费 
 采用一种典型的多重链表——十字链表来存储稀疏矩阵 
 只存储矩阵非0元素项结点的数据域：行坐标Row、列坐标Col、数值Value 
 每个结点通过两个指针域，把同行、同列串起来; 
 行指针(或称为向右指针)Right 
 列指针（或称为向下指针）Down 
 
 
 用一个标识域Tag来区分头结点和非0元素结点： 
 头节点的标识值为“Head”，矩阵非0元素结点的标识值为“Term”。