「数据结构」线性表
“数据结构”不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。
开始
结构分为物理结构和逻辑结构，前者代表了在物理存储中数据的位置，后者则是代码逻辑中的抽象结构。
目录：
- 线性表
- 顺序表示
- 链式表示
- 顺序与链式对比
- 应用实例
线性表
线性表
线性表是什么？
- 线性表是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”。
顺序表插入
比起初始化，插入显得更为简单。
逻辑上分为以下几步
- 查找新元素应该插入的位置。
- 把位置空出来。
- 新元素写入。
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为结构指针类型*/
单链表操作
- 建立单链表
- 遍历
- 查找
- 插入
- 删除
- 合并
双链表结构
比单链表结构要多一个直接前驱的指针指向。
对比
顺序表和链表的比较
- 主要进行查找操作，宜采用顺序表。
- 频繁进行插入、删除操作，宜采用链表。
- 若表的插入、删除主要发生在表的首尾两端，宜采用尾指针表示的单循环链表。
- 对于没有提供指针类型的高级语言，若要采用链表结构， 可以使用光标实现的静态链表。
- 当线性表长度不变，仅需改变结点之间的相对关系时，也可以选用静态链表。
