线性表 - JUZI's blog

线性表–n个数据元素的有限序列

一个数据元素可以由若干个数据项组成。
同一线性表中的元素必定具有相同特性，即属同一数据对象
i称为a_i在线性表中的位序
a_i-1称为a_i的直接前驱元素

a_i称为a_i-1的直接后继元素
n=0时称为空表
线性表的存储结构有顺序存储结构和链式存储结构

线性表的顺序表示

用一组地址连续的存储单元依次存储线性表的数据元素
通常称这种存储结构的线性表为顺序表
随机访问特性：通过序号可以找到任意位置的数据
占用连续的存储空间

#define maxSize 100
typedef struct
{
    int data[maxSize];  //存放顺序表元素的数组
    int length;  //顺序表的长度
}Sqlist;   //顺序表类型的定义

####顺序表的增删改查

顺序表在做插入删除操作时需要移动多个元素

int findElem(Sqlist L, int x)//查找x
{
    int i;
    for(i=0;i<L.length;i++){
        if(x == L.data[i]){
			return i;
        }
    }
    return -1;
}
//在顺序表L的第p个位置插入元素e
int insertElem(Sqlist &L, int p, int e)  //引用型
{
    int i;
    if(p<0||p>L.length||L.length==maxSize)  //位置错误或表长已经达到最大值
        return 0;
    for(i=length-1;i>=p;--i){
        L.data[i+1] = L.data[i];
    }
    L.data[p] = e;
    ++(L.length);  //表长加1
    return 1;  //插入成功，返回1
}
//删除顺序表L中下标为p的元素，并把删除的元素的值赋给e
int deleteElem(Sqlist &L, int p, int &e)
{
    int i;
    if(p<0||p>L.length-1)
        return 0;
    e=L.data[p];
    for(i=p;i<L.length-1;++i){
        L.data[i] = L.data[i+1];  //p位置开始，后边的元素逐个前移一个位置
    }
    --(L.length);
    return 1;
}

线性表的链式表示

任意的存储单元
结点：由数据域和指针域构成
数据域：存储数据元素信息的域
指针域：存储直接后继存储位置的域，指针（链）
链表：线性表的链式存储结构
线性链表（单链表）：结点中只包含一个指针域
头结点：有时在单链表第一个结点之前附设的结点，头结点的数据域可以不存储任何信息，也可存储线性表的长度等类的附加信息
带头结点的单链表中，头指针head指向头结点，head->next为NULL时，链表为空；不带头结点的单链表中的头指针head直接指向开始结点，当head等于NULL时，链表为空。
不支持随机访问，结点的存储空间利用率较顺序表稍低，支持存储空间的动态分配

单链表的定义

typedef struct LNode
{
    int data;  //data中存放结点数据域
    struct LNode *next;  //指向后继结点的指针
}LNode; //定义单链表结构类型

单链表的增删改查

链表的增删操作不需要移动元素，只需要修改指针

//完整的删除操作
q = p->next;	//要删除的结点
p->next = p->next->next;
free(q);	//调用free函数释放q所指结点的空间

尾插法

//有n个元素已经存储在数组a中，用尾插法建立链表C
void createlistR(LNode *&C, int a[], int n)
{
    LNode *s, *r;	//s用来指向新申请的结点，r始终指向C的终端结点
    int i;
    C = (LNode *)malloc(sizeof(LNode));		//申请C的头结点空间
    C->next = NULL;
    r = C;
    for(i=0;i<n;++i)
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];		//用新申请的结点来接收a中的一个元素
        r->next = s;		//用r来接纳新结点
       	r = r->next;		//r指向终端结点，以便接纳下一个到来的结点
    }
    r->next = NULL;			//将C的终端结点指针域置为NULL，C建立完成
}

头插法

void createlistF(LNode *&C, int a[], int n)
{
    LNode *s;
    int i;
    C = (LNode*)malloc(sizeof(LNode));
    C->next = NULL;
    for(i=0;i<n;i++)
    {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = C->next;	//s所指新结点的指针域next指向C中的开始结点
        C->next = s;		//头结点的指针域next指向s结点，使得s成为新的开始结点
    }
}

单链表的合并

//将A，B两个元素递增有序的单链表(含头结点)合并成一个按元素值非递减有序的链表C
void merge(LNode *A, LNode *B, LNode *&C)
{
    LNode *p = A->next;		//p跟踪A的最小值结点
    LNode *q = B->next;		//q跟踪B的最小值结点
    LNdoe *r;	//r指向C的终端结点
    C = A;		
    C->next = NULL;		
    free(B);	//B的头结点已无用，释放
    r = C;		//r指向C，此时头结点也是终端结点
    while(p!=NULL&&q!=NULL)
    {
        if(p->data <= q->data)
        {
            r->next = p;
            p = p->next;
            r = r->next;
        }
        else
        {
            r->next = q;
            q = q->next；
            r = r->next;
        }
    }
    //r->next = NULL;
    if(p != NULL) r->next = p;
    if(q != NULL) r->next = q;
}

静态链表

借助一维数组实现
数组中的每个结点含有两个分量：一个数据元素分量，一个指针分量，指示当前结点的直接后继结点在数组中的位置
指针分量不是通常的存储内存地址的指针型变量，而是一个存储数组下标的整型变量

循环链表

表中最后一个结点的指针域指向头结点，整个链表形成一个环

双向链表

结点有两个指针域，一个指向直接后继，一个指向直接前驱

typedef struct DLNode
{
    int data;
    struct DLNode *prior; //指向前驱结点的指针
    struct DLNode *next;  //指向后继结点的指针
}DLNode;  //定义双链表结点类型

循环双向链表

//以下4句任意一句为真，即可判断循环双链表为空
head->next == head;
head->prior == head;
head->next == head && head->prior == head;
head->next == head || head->prior == head;