线性表

线性表是最简单的线性结构，线性表的主要操作特点是可以在任意位置插入和删除一个数据元素。

线性表可以用顺序存储结构和链式存储结构存储。

用顺序存储结构事先的线性表称为顺序表，用链式存储结构存储的称为链表。

线性表的抽象数据类型主要包括两个方面：即数据集合和该数据集合上的操作集合。

1、数据集合

DataType类型的a0 a1 a2...an-1

2、操作集合

• 初始化
• 求当前元素个数
• 插入数据元素
• 删除数据元素
• 取数据元素

*******************************************************************************************

顺序表

使用c语言实现顺序表的方式是数组。

数组把线性表的数据元素存储在一块连续地址空间的内存单元。这样在线性表中逻辑上相邻的数据元素在物理地址上也是相邻的。

数据元素之间的前驱、后继关系就体现在物理地址上的前后位置关系。

数组有静态数组和动态数组。静态数组的存储空间的申请与释放是系统决定的。动态数组的存储空间的申请和释放是用户通过调用函数实现的。

顺序表的实现如下：

typedef int DataType;

typedef struct{
    DataType list[MaxSize];
    int size;
}SeqList;

/*初始化*/
void ListInit(SeqList *L){
    L->size = 0;
}

/*获取当前元素个数*/
int ListLength(SeqList *L){
    return L->size;
}

/*插入数据元素*/
int ListInsert(SeqList *L, int i,DataType data){
    int j;
    if(L->size >= MaxSize){
        printf("顺序表已满！
");
        return 0;
    }
    else if(i<0 || i>L->size){
        printf("参数i不合法！
");
        return 0;
    }
    else{
        for(j = L->size; j > i; j--){
            L->list[j] = L->list[j-1];
        }
        L->list[i] = data;
        L->size ++;
        return 1;
    }
}

/*删除数据*/
int ListDelete(SeqList *L, int i){
    int j;
    if(L->size <= 0){
        printf("顺序表已空！
");
        return 0;
    }
    
    if(i<0 || i>MaxSize){
        printf("参数i不合法！
");
        return 0;
    }
    
    for(j=i; j<L->size; j++){
        L->list[j] =L->list[j+1];
    }
    
    L->size --;
    return 1;
}

/*获取数据*/
DataType ListGet(SeqList *L, int i){
    DataType data;
    if(L->size <= 0){
        printf("顺序表已空！
");
        return 0;
    }
    
    if(i<0 || i>MaxSize){
        printf("参数i不合法！
");
        return 0;
    }
    
    return L->list[i];    
}

**********************************************************************************************

链表

链式存储结构存储线性表数据元素的方法是，把存储有数据元素的结点用指针域构造成链。

一个由数据元素域及一个或者若干个指针域组成的结构体称为一个结点。其中数据域用来存储数据，指针域用来构造数据元素之间的关联关系。

链表主要有单链表 双向链表 单循环链表三种。

1、单链表

单链表中，构成链表的结点只有一个指向直接后继结点的指针域。结构如下：

单链表有带头结点结构和不带头结点结构两种。

头指针：指向单链表的指针

头结点：头指针所指的不存放数据元素的第一个结点

首元结点：存放第一个数据元素的结点

在链式存储结构中，初始时为空链，每当有新的数据需要存储的时候，用户才向系统动态申请所需的存储空间插入链中。

因此，在链表中逻辑上相邻的数据元素在物理上不一定相邻。

单链表的实现

typedef int DataType;
typedef struct Node{
    DataType data;
    struct Node *next;
}SLNode;

/*初始化*/
void ListInit(SLNode **head){
    *head = (SLNode *)malloc(sizeof(SLNode));
    (*head)->next = NULL;
}

/*求当前元素个数*/
int ListLength(SLNode *head){
    SLNode *p = head;
    int size =0;

    if(head->next != NULL){
        p = p->next;
        size ++;
    }
    return size;
}

/*插入元素*/
int ListInsert(SLNode *head, int i, DataType d){
    SLNode *p,*q;
    int j;
    p = head;
    j = 0;

    if(i <0){
        printf("不合法的参数！
");
        return 0;
    }

    while((p->next != NULL) && (j < i)){
        p = p->next;
        j++;
    }

    if(j != i){
        printf("不合法的参数！
");
        return 0;
    }

    q = (SLNode *)malloc(sizeof(SLNode));
    q->data = d;
    q->next= p->next;
    p->next = q;
    return 1;
}

/*删除元素*/
int ListDelete(SLNode *head, int i){
    SLNode *p,*q;
    int j = 0;
    p = head;

    if(i <0){
        printf("不合法的参数！
");
        return 0;
    }

    while((p->next != NULL) && (j < i)){
        p = p->next;
        j++;
    }

    if(j != i){
        printf("不合法的参数！
");
        return 0;
    }

    q = (SLNode *)malloc(sizeof(SLNode));

    if(p->next->next == NULL){//如果要删除的元素时最后一个元素
        p->next= NULL;
    }
    else{
        q = p->next;
        p->next = q->next;
    }
    free(q);
    return 1;
}

/*取数据元素*/
DataType ListGet(SLNode *head, int i){
    SLNode *p;
    int j = -1;
    p = head;

    if(i <0){
        printf("不合法的参数！
");
        return 0;
    }

    while((p->next != NULL) && (j < i)){
        p = p->next;
        j++;
    }

    if(j != i){
        printf("不合法的参数！
");
        return 0;
    }

    return p->data;
}

/*撤销单链表*/
void ListDestroy(SLNode **head){
    SLNode *p,*p1;

    p = *head;

    if(p != NULL){
        p1 = p;
        p = p->next;
        free(p1);
    }
    *head = NULL;
}

2、循环单链表

链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。

3、双向链表

双向链表中，每个结点除了一个后继指针域还有一个前驱指针域。