目  录
第一章 线性表
1.1 基本概念    2
1.1.1 预定义的常量和类型    2
1.1.2 抽象数据类型定义    2
1.1.3 顺序表    3
1.1.4 链表    5
1.2 链表的基本操作    7
1.2.1 单链表（重点）    7
1.2.2 双向链表    11
1.2.3 链表的一种改进表示    11
1.3 有序表    11
1.4 线性表的应用    12
1.4.1 链表的合并和分解    12
1.4.2 线性表的合并    13
1.4.3 有序表的合并    15
1.4.4 简单的单表分解释放    15
1.4.5 双向循环链表的自身变换    16
第1章 
线性表
1.1  基本概念
1.1.1  预定义的常量和类型
/* 函数结果状态代码        */
#define    TRUE    1
#define    FALSE    0
#define    OK        1
#define    ERROR    0
#define    INFEASIBLE    -1
#define    OVERFLOW    -2
/* 函数结果状态类型，其值为上述的状态代码    */
typedef    int    Status;
1.1.2  抽象数据类型定义
指一个数学模型和定义在该模型上的一组操作。
◆ 反映其逻辑特征，而与其在计算机的内部表示和实现无关。
◆ 包含固有的数据类型和用户自定义的数据类型。
分类：原子类型、固定聚合类型、可变聚合类型、多形数据类型
抽象数据类型定义：(D,S,P)    D-数据对象，S-数据关系，P-基本操作
线性表的抽象数据类型定义：
ADT List{
数据对象：D={ai|ai∈ElemSet, i=1,2,…,n,  n≥0}
数据关系：R={R1},R1={<ai-1,ai>|ai-1,a数组和链表i∈D, i=2,3,…,n }
基本操作：
InitList(&L)
操作结果：构造一个空的线性表L
DestroyList(&L)
初始条件：线性表L已存在
操作结果：销毁线性表L
ClearList(&L)
初始条件：线性表L已存在
操作结果：将线性表L重置为空表
ListEmpty(L)
初始条件：线性表L已存在
操作结果：若L为空表，则返回TRUE，否则返回FALSE
ListLength(L)
初始条件：线性表L已存在
操作结果：返回线性表L中数据元素的个数
GetElem(L, i ,&e)
初始条件：线性表L已存在，1≤i≤ListLength(L)
操作结果：用e返回L中第i个数据元素的值
LocateElem(L, e, compare())
初始条件：线性表L已存在，compare()是数据元素的判定函数
操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的元素不存在，则返回值为0
PriorElem(L, cur_e ,&pre_e)
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失
败，pre_e无定义
NextElem(L, cur_e ,&next_e)
初始条件：线性表L已存在
操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义
ListInsert(&L, i, e)
初始条件：线性表L已存在，1≤i≤ListLength(L)+1
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
ListDelete(&L, i, &e)
初始条件：线性表L已存在，1≤i≤ListLength(L)
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
ListTraverse(L, visit())
初始条件：线性表L已存在
操作结果：依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
}ADT List
1.1.3  顺序表
1、顺序表定义：方案一
#define  LIST_SIZE  100
typedef  struct{
ElemType    elem[LIST_SIZE];        /* 存储空间                */
int            length;                /* 当前长度                */
}SqList_static;
1) LIST_SIZE过小，则会导致顺序表上溢；
2) LIST_SIZE过大，则会导致空间的利用率不高。
2、顺序表定义：方案二
#define  LIST_INIT_SIZE  100            /* 存储空间的初始分配量    */
#define  LISTINCREMENT  10            /* 存储空间的分配增量    */
typedef  struct{
ElemType    *elem;                /* 存储空间的基址        */
int            length;                /* 当前长度                */
int            listsize;                /* 当前分配的存储容量    */
}SqList;
这种方法可以比方案一较好地解决“上溢”问题和“空间利用率不高”问题。
1) 必须记载当前线性表的实际分配的空间大小；
2) 当线性表不再使用时，应释放其所占的空间；
3) 这种方法要求实现级的语言能提供空间的动态分配与释放管理。
void *malloc(unsigned int size)
生成一大小为size的结点空间，将该空间的起始地址赋给p；
free(void *p)
回收p所指向的结点空间;
void *realloc(void *p, unsigned int size)   
将p所指向的已分配内存区的大小改为size，size可以比原分配的空间大或小。
3、插入操作ListInsert_Sq
1) 算法设计
参数：顺序表&L(以这种记法表明该参数是变参)、插入位置i、插入元素e
插入分析：第i个位置放e，则原来第i~L.length个数据元素必须先后移，以腾出第i个位置;
注意后移的顺序为：从最后一个元素开始，逐个往后移
for ( j=L.length; j > = i; j--)    L.elem[j] = L.elem[j-1];        // 后移
L.elem[i-1]= e; //第i个元素存放在L.elem[i-1]中，数组下标的起始为0
                  L.length=L.length+1;
合法的位置：i:1..L.length+1
上溢及处理：上溢发生的条件：L.length≥L.listsize，此时要先申请一个有一定增量的空间：申请成功则原空间的元素复制到新空间，修改L.listsize，再进行插入工作；否则报错退出。
算法
Status  ListInsert_Sq( SqList &L, int i, ElemType e) {
/* 位置合法性的判断 */
if ( i<1 || i>L.length +1 )    return ERROR;
/* 上溢时增加空间的分配    */
if( L.length>=L.listsize){
newbase = (ElemType *) realloc(L.elem,
            (L.listsize+ LISTINCREMENT)*sizeof(ElemType));
if ( !newbase) exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
/* 插入元素    */
for ( j=L.length; j > = i; j--)    L.elem[j] = L.elem[j-1];
L.elem[i-1]= e;
L.length++;
return OK;
}
2) 算法分析——时间
频次最高的操作：①上溢时的复制(隐含在realloc操作中)②移动元素。但前者的发生机会很少，并且平均的时间复杂度可视为O(1)。
若线性表的长度为n，则：
最好情况：插入位置i为n+1，此时无须移动元素，时间复杂度为O(1);
最坏情况：插入位置i为1，此时须移动n个元素，时间复杂度为O(n);
平均情况：假设pi为在第i个元素之前插入一个元素的概率，则：
插入时移动次数的期望值：
等概率时，即，
∴ T(n) = O(n)
4、删除操作ListDelete_Sq
1) 算法设计
参数：顺序表&L、删除位置i
删除分析：去掉第i个元素，则原来第i+1~L.length个数据元素须前移，以覆盖第i个位置;
              前移的顺序为    for ( j = i; j < L.length ; j++)    L.elem[j-1] = L.elem[j];
            L.length=L.length-1
合法的位置：i:1..L.length
下溢：L.length≤0 —— 隐含在i的条件中
算法
Status  ListDelete_Sq( SqList &L, int i) {
/* 位置合法性的判断 */
if ( i<1 || i>L.length )    return ERROR;
/* 删除    */
for ( j = i; j < L.length ; j++)    L.elem[j-1] = L.elem[j];
L.length--;
return OK;
}
2) 算法分析——时间
频次最高的操作：移动元素
若线性表的长度为n，则：
最好情况：删除位置i为n，此时无须移动元素，时间复杂度为O(1);
最坏情况：删除位置i为1，此时须前移n-1个元素，时间复杂度为O(n);
平均情况：假设pi为在删除第i个元素的概率，则：
删除时移动次数的期望值：
等概率时，即，
∴ T(n) = O(n)
1.1.4  链表
1、顺序映像的弱点
1）空间利用率不高（预先按最大空间分配）；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。