数据结构-线性表_学生表抽象成一个线性表,每个学生(包括姓名、学号、成绩)作为线性表中的一个元素,

        在日常生活中，线性表的例子比比皆是。例如，26个英文字母的字母表就是一个线性表，表中的数据元素是单个字母。
        在稍复杂的线性表中，一个数据元素可以包含若干个数据项。例如在一个学生基本信息表中，每个学生为一个数据元素，包括学号、姚名、性别、籍贯、专业等数据项。
        由以上示例可以看出，它们的数据元素虽然不同，但同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。

1.线性表的定义和特点

定义：
        由n(n≥0)个数据特性相同的元素构成的有限序列，称为线性表。
        线性表中元素的个数n(n≥0)定义为线性表的长度，当n=0时称之为空表。
特点：
        (1) 存在唯一的一个被称作  “第一个”  的数据元素；
        (2) 存在唯一的一个被称作  “最后一个”  的数据元素；
        (3) 除第一个元素之外，结构中的每个数据元素均只有一个前驱；
        (4) 除最后一个元素之外，结构中的每个数据元素均只有一个后继。

2.线性表

        线性表的  “顺序表示”  指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像，因此称这种存储结构的线性表为顺序表。
        线性表的特点：逻辑上相邻的数据元素，其物理位置也是相邻的。

        设线性表的每个元素需占用n个存储单元，并以所占的第一个单元的存储地址为数据元素的存储位置起始,且第i+1个数据元素的储存位置为LOC(a(i+1))，可得LOC(a(i+1))=LOC(a1)+(i-1)*n。
LOC(a1)是线性表的第一个数据元素a的存储位置，通常称作线性表的起始位置或基地址，表中相邻的元素a1和a2的存储位置LOC(a1)和LOC(a2)是相邻的。
        每一个数据元素的存储位置都和线性表的起始位置相差一个常数，这个常数和数据元素在线性表中的位序成正比。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

1.存储结构

#define MAXSIZE 100      //顺序表可能达到的最大长度
typedef  struct {
      ElemType  *elem;   //指向数据元素的基地址
      int length;        //线性表的当前长度                                                   
 }SqList;                //顺序表的结构类型SqList

2.初始化

1.为顺序表的初始化操作就是构造一个预定义大小的数组空间，使elem指向这段空间的基地址
2.将表的当前长度设为0

int InitList_Sq(SqList &L)
{                                  //构造一个空的顺序表L
   L.elem=new ElemType[MAXSIZE];   //为顺序表分配一个大小为MAXSIZE的数组空间
   if(!L.elem) exit(-2);           //存储分配失败退出
   L.length=0;                     //空表长度为0
   return 1;
}

        动态分配线性表的存储区域可以更有效的利用系统的资源，当不该需要该线性表时，可以使用销毁操作及时释放占用的存储空间

3.输入数据元素

void CreateList_Sq(SqList &L,int n)
{
	L.length=n;
	for(int i=0;i<L.length;i++){
		scanf("%d",&L.elem[i]);
	}
}

4.输出数据元素

void TraverseList_Sq(SqList &L,int n) 
{
    L.length=n;
	for(int i=0;i<L.length;i++)
    {
		printf("%d ",L.elem[i]);
	}
}

5.取值

1.提交指定的位置序号，先判断是否合理
2.在合理的情况下将数据元素赋值给e，最后返回数据元素的值

int GetElem(SqList L,int i,ElemType &e)
{
    if(i<1||i>L.length) return 0;
    e=L.elem[i-1];
    return e;
}

        由于使用随机存储，可以根据数组下标直接定位得到数据元素，显然，顺序表取值算法的时间复杂度为O(1)。

6.查找

1.从第一个元素开始对比，直到其值与e相等，然后返回位置序号
2.若没有找到该元素，则返回0

int LocateElem(SqList L,ElemType e)
{
    for(i=0;i<L.length;i++)
        if(L.elem[i]==e) return i+1;
    return 0;
}

在顺序表中查找一个数据元素时，其时间主要消耗在数据的比较上，因此查找算法的平均时间复杂度为O(n)。

7.插入

1.判断插入位置是否合法，存储空间是否已满
2.将要插入位置i之后的元素依次向后移动一个位置，空出带插入位置
3.将元素e放入位置i，表长加一

int ListInsert(SqList &L,int i,ElemType e)
{
    if((i<1)||(i>L.length+1)) return 0;
    if(L.length==MAXSIZE) return 0;
    for(j=L.length-1;j>=i-1;j--)
        L.elem[j+1]=L.elem[j];
    L.elem[i-1]=e;
    ++L.length;
}

        当在顺序表中某个位置上插入一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于插入元素的位置，由此顺序表插入算法的平均时间复杂度为O(n)。

8.删除

1.判断删除位置是否合法
2.将第i+1个元素及之后的元素向前移动一个位置
3.表长减一

int ListDelete(SqList &L,int i)
{
    if((i<1)||(i>L.length)) return 0;
    for(j=i;j<=L.length-1;j++)
        L.elem[j-1]=L.elem[j];
    --L.length;
}

        当在顺序表中某个位置上删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于删除元素的位置，由此顺序表删除算法的平均时间复杂度为O(n)。

3.单链表

        线性表链式存储结构的特点是:用一组任意的存储单元存储线性表的数据元素。因此，为了表示每个数据元素a与其直接后继数据元素ai之间的逻辑关系，对数据元素a来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息。这两部分信息组成数据元素a的存储映像，称为节点(node)。它包括两个域:其中存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个节点链接成一个链表。又由于此链表的每个节点中只包含一个指针域，故又称线性链表或单链表。

        根据链表节点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表多用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。

        线性表的单链表存储结构，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个节点的存储位置。同时，由于最后一个数据元素没有直接后继，则单链表中最后一个节点的指针为空。

 1.存储结构

typedef struct LNode
{
      ElemType data;     //节点的数据域
      struct LNode *next //节点的指针域                                                   
}LNode,*LinkList;        //LinkList为指向结构体LNode的指针类型

2.初始化

1.生成新节点作为头节点，用头指针L指向头节点
2.头节点的指针域置空

void InitList_Sq(SqList &L)
{                       //构造一个空的单链表L
    L=new LNode;        //生成新节点作为头节点，用头指针L指向头节点
    L->next=NULL;       //头节点的指针域置空
}

 3.输入数据元素

void CreateList_L(LinkList &L,int n)
{ 
    LNode *p=new LNode;
	L=p; 
	p->next=NULL;
	for(int i=0;i<n;i++){
		LNode *q=new LNode;
		scanf("%d",&q->data);
		q->next=NULL;
		p->next=q; 
		p=q; 
	}
}

4.输出数据元素

void TraverseList_L(LinkList &L) 
{	
    LNode *p=new LNode;
	p=L;
	p=p->next;
	while(p!=NULL){
		printf("%d,",p->data);
		p=p->next;
	}
} 

5.取值

1.用指针p指向首元节点，用j做计数器初值赋为1
2.从首元节点开始依次顺着链域next向下访问，只要指向当前节点的指针p不为空
3.退出循环时，如果指针p为空，或者计数器j大于指定序号i，说明指定的序号i不合法，取值失         败；否则取值成功返回第i个节点的数据域e

int GetElem(LinkList L,int i,ElemType &e)
{
    p=L->next;
    j=1;
    while(p&&j<i)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i) return 0;
    e=p->data;
    return e;
}

        该算法比较j和i并后移指针p，while循环体中的语句频度与位置i有关。由此，单链表取值算法的时间复杂度为O(n)。

6.查找

1.用指针p指向首元节点
2.从首元节点开始依次顺着链域next向下查找，只要指向当前节点的指针p不为空，并且p所指节点     的数据域不等于给定值e
3.查找成功，p指向节点的地址值返回p

LNode *LocateElem(LinkList L,ElemType e)
{
    p=L->next;
    while(p&&p->data!=e)
        p=p->next;
    return p;
}

        算法的执行时间与待查找的值e有关，因此单链表查找算法的平均时间复杂度为O(n)。

7.插入

1.查找节点a(i-1)并由指针p指向该节点
2.生成一个新节点*s
3.将新节点*s的数据域置为e
4.将新节点*s的指针域指向节点ai
5.将节点*p的指针域指向新节点*s

void ListInsert(LinkList &L,int i,ElemType e)
{
    p=L;j=0;
    while(p&&(j<i-1))
        {p=p->next;++j;}
    if(!p||j>i-1) return ERROR;
    s=new LNode;
    s->data=e;
    s->next=p->next;
    p->next=s;
}

        单链表的插入操作虽然不像顺序表的插入那样移动元素，但在第i个节点之前插入一个新节点，必须首先找到第i-1个节点，由此单链表插入算法的平均时间复杂度为O(n)。

8.删除

1.查找节点a(i-1)并由指针p指向该节点
2.临时保存待删除节点ai的地址在q中，以备释放
3.将节点*p的指针域指向ai的直接后继节点
4.释放节点ai的空间

int ListDelete(SqList &L,int i)
{
    p=L;j=0;
    while((p->next)&&(j<i-1))
        {p=p->next;++j;}
    if(!(p->next)||(j>i-1)) return 0;
    q=p->next;
    p->next=q->next;
    delete q;
}

        当在单链表中某个位置上删除一个数据元素时，其时间主要耗费在移动元素上，而移动元素的个数取决于删除元素的位置，由此单链表删除算法的平均时间复杂度为O(n)。

9.前插法创建单链表

1.创建一个只有头节点的空链表
2.根据待创建链表包括的元素个数n，循环n次执行以下操作：
   【生成一个新节点*p；
       输入元素值赋给新节点*p的数据域；
       将新节点*p插入到头节点之后】

void CreateList_H(LinkList &L,int n)
{
    L=new LNode;
    L->next=NULL;
    for(i=0;i<n;++i)
    {
        p=new LNode;
        scanf("%d",&p->data);
        p->next=L->next;
        L->next=p;
    }
}

        建立一个带头节点的空链表，每次都将新节点插入在链表头节点之后，算法的时间复杂度为O(n).

10.后插法创建单链表

1.创建一个只有头节点的空链表
2.尾指针r初始化，指向头节点
3.根据创建链表包括的元素个数n，循环n次执行以下操作：
   【生成一个新节点*p；
       输入元素值赋给新节点*p的数据域；
       将新节点*p插入到尾节点*r之后；
       尾指针r指向新的尾节点*p】

void CreateList_R(LinkList &L,int n)
{
    L=new LNode;
    L->next=NULL;
    r=L;
    for(i=0;i<n;++i)
    {
        p=new LNode;
        scanf("%d",&p->data);
        p->next=NULL;
        r->next=p;
        r=p;
    }
}

        建立一个带头节点的空链表，每次都将新节点插入在链表尾指针之前，算法的时间复杂度为O(n).