「数据结构」线性表

“数据结构”不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。

开始

结构分为物理结构和逻辑结构，前者代表了在物理存储中数据的位置，后者则是代码逻辑中的抽象结构。

目录：

1. 线性表
2. 顺序表示
3. 链式表示
4. 顺序与链式对比
5. 应用实例

---

线性表

线性表

线性表是什么？

• 线性表是n个同类型数据元素构成的有限序列。
  例如：字母表、学生成绩表、月收入表等等

线性表有什么？

线性表的特点是：同一性、有穷性、有序性.

分别对应同类型元素、有限序列以及规范的插入。

抽象例子

这里举一个线性表的抽象例子，注意ADT结构中的函数（方法名）之后会经常用到！

ADT  List{
数据元素： D={ai| ai∈ElemSet, i=1, 2, …，n, n≥0 ， ElemSet为某一数据对象}
关系：Ｓ＝{<ai, ai+1> | ai,  ai+1∈D，i=1, 2, …, n-1}
基本操作函数（方法）：
（1）InitList(L)：将表L初始化为空表。
（2）ListEmpty(L)：判断L是否为空表。
（3）ListLength(L)：求表L的长度。
（4）GetElem(L, i, e)：用e返回表L中第i个元素的值。
（5）ListInsert (L, i, e)：在L中第i个位置之前插入新的数据元素e，L的长度加1。
（6）ListDelete (L, i, e)：删除L的第i个数据元素， 并用e返回其值， L的长度减1。 
 } ADT  List

这就是一个线性表用伪代码的格式写出来的效果，要分为数据元素和基本操作。

数据元素承担了保存数据的任务，基本操作则承担了处理数据的任务，好的数据结构和基本操作的代码层面的定义能够减少运算的时间、空间复杂度。

再举一个例子

例：两个非递减有序的线性表La和Lb的合并
void  MergeList(List La,List Lb,List &Lc){
    InitList(Lc);
    i=j=1;k=0;
    La_len=ListLength(La);Lb_len=ListLength (Lb);
    while((i<=La_Len)&&(j<=Lb_len)){
         GetElem(La,i,ai);GetElem(Lb,j,bj);
         if(ai<= bj){ListInsert(Lc,++k, ai);++i;} 
         else {ListInsert(Lc,++k, bj);++j}
    }
    while (i<=La_len) {
        GetElem(La, i++, ai);ListInsert(Lc, ++k, ai);
    }
    while (j<=Lb_len) {
        GetElem(Lb, j++, bj);ListInsert(Lc, ++k, bj);
    }
} 

例子为合并两个线性表，用简单的扫描两个线性表中数字，对比数字大小并写入新线性表的方式，合并了线性表。

---

顺序表示

顺序表示是什么

顺序存储是逻辑上相邻，物理位置也相邻的存储方式。

具体实现是用数组，实现用一组地址连续的存储单元来存储线性表元素。

优点：查找方便；因为紧密存储，所以空间消耗少。
缺点：从中间存入和删除操作不方便，时间消耗高。

数序存储结构定义

#define LIST_INIT_SIZE  100
#define LISTINCREMENT 10
typedef  struct SqList{  
    ElemType  *elem;   /* 顺序表 */ 
    int     length；    /* 顺序表长度 */    
    int          listsize;      /* 分配空间大小 */
 } SqList； 

每一个存储结构中都应当有的三点：顺序表、顺序表长度、分配空间大小。

顺序表的初始化

这里就是实例化了InitList函数（方法），这个函数应当能够初始化线性表中的数据，给每个数据一个初始值。

Status InitList_Sq(SqList &L){
L.elem=(ElemType*)malloc( LIST_INIT_SIZE*sizeof(ElemType) );
    if(!L.elem) exit(OVERFLOW);
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    return OK;
}  

malloc函数使用格式
(分配类型 *)malloc(分配元素个数 *sizeof(分配类型))
如果成功，则返回该空间首地址，该空间没有初始化，如果失败，则返回0

ElemType是类型的意思，这里代指任意一种类型。

第一句是给L.elem赋地址值，同时分配”LIST_INIT_SIZE“个ElemType类型的空间。

第二句判断L.elem是否复制成功。

第三句给L的长度赋值0。

第四句，给顺序表长度设为“LIST_INIT_SIZE”。

顺序表插入

比起初始化，插入显得更为简单。

逻辑上分为以下几步

1. 查找新元素应该插入的位置。
2. 把位置空出来。
3. 新元素写入。
   4.表长增加1。

Status ListInsert_sq(SqList &L, int i, ElemType e){
    if(i<1||i>L.length+1) return ERROR;
    if(L.length>=L.listsize){
        …/*表空间不够，重新分配更大空间*/
    }
    /*确定插入位置*/
   for(j=L.length-1;j>=i-1;j--)  
         L.elem[j+1]=L.elem[j];     /*元素后移*/
   L.elem[i-1]=e;                        /*插入新元素*/
   ++L.length;                          /*表长增1*/
    return OK；
} 

代码中前一段是对空间大小的检测，后一段是插入新元素。

顺序表删除

删除只有一步，前移。

Status ListDelete_Sq(SqList &L,int i,ElemType &e)
{
           if( (i<1) || (i>L.length) ) return ERROR;
           e=L.elem[i];  
         for(j=i; j<L.length; j++)  
                 L.elem[j-1]=L.elem[j];     
  /*元素前移*/ 
         --L.length;                             
  /*表长减1*/
           return OK;
}

顺序表查找

查找就是用while遍历寻找匹配的值。

int LocateElem_Sq(SqList L,ElemType e, 
                  Status(*compare)(ElemType, ElemType)){
    i=1;
    p=L.elem;
            /*从前向后查找*/  
            while (i<=L.length && !(*compare)(*p++,e))  
        ++i;
    if (i<=L.length)   return i;
    else  return 0;
} 

顺序表的合并

这里通过指针pa，pb，pc指向La\Lb\Lc中的指针elem，然后对比指向结构中的

void MergeList_Sq(SqList La, SqList Lb, SqList &Lc ){
pa=La.elem; pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTpe));
if (!Lc.elem) exit (OVERFLOW);
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
while (pa<=pa_last && pb<=pb_last){
   if (*pa<=*pb) *pc++=*pa++;
   else *pc++=*pb++;
}
while(pa<=pa_last) *pc++=*pa++;
while(pb<=pb_last) *pc++=*pb++;

---

链式表示

链式表是什么

只要求逻辑上相连接，不要求物理上连接，链接依靠结构中定义的next的指针。

链式表有什么

单向链表有存储的数据，直接后继的地址。

接下来讲单链表。

单链表的结构

typedef struct LNode {
   ElemType data;
   struct LNode *next;
}LNode ,*LinkList;      
/* LinkList为结构指针类型*/

单链表操作

• 建立单链表
• 遍历
• 查找
• 插入
• 删除
• 合并

双链表结构

比单链表结构要多一个直接前驱的指针指向。

对比

顺序表和链表的比较

• 主要进行查找操作，宜采用顺序表。
• 频繁进行插入、删除操作，宜采用链表。
• 若表的插入、删除主要发生在表的首尾两端，宜采用尾指针表示的单循环链表。
• 对于没有提供指针类型的高级语言，若要采用链表结构， 可以使用光标实现的静态链表。
• 当线性表长度不变，仅需改变结点之间的相对关系时，也可以选用静态链表。

应用实例

• PAT