漫谈数据结构(二)——线性表1

风景图

作者个人博客 https://www.you3xuan.top/ 查看原文。

1、线性表的定义和特征

1.1 定义

  线性表是具有相同类型元素组成的一个线性序列。元素的个数即为元素的长度，元素为0时称为空表。如下：
<center>(A,B,C,D,E,F,G)</center>
  这就表示一个线性表。

1.2 特征

1. 有且只有一个头结点，头结点没有前驱结点。
2. 有且只有一个尾结点, 尾结点没有后继节点。
3. 除头尾结点外，其他结点都有一个前驱结点和后继节点。

1.3 存储特征

  线性表的存储结构分为顺序存储和链式存储，它们都具有如下特点：

1. 唯一性：一个线性表只能存储一种类型的元素
2. 有序性：各元素在线性表中的位置只取决于它的序号，数据元素之间的相对位置为线性的（并不是内存结构上的有序）。

1.4 基本操作

1. 创建 create()
2. 初始化 init()
3. 添加数据 addData()
4. 获取长度 getLength()
5. 获取指定元素 get()
6. 插入 insert()
7. 删除 delete()
8. 清空表 clear()

这8种只是线性表的最基本操作，如果想要进阶，请自己谷歌。

2、线性表的顺序存储

  数据被存储在指定长度的连续存储单元，通过对应的索引(一般从0开始)找到对应的元素。在高级语言中，顺序存储可以用数组表示。

  前面提到过线性表的顺序存储查询效率高，插入和删除效率低。适合存储需要连续存取的数据。

2.1 顺序存储的实现

2.1.1 创建顺序表并初始化

  使用结构体创建一个结点，这个结点存储了这个顺序表的基本信息，包括capacity,length,node。为了简单起见，只存储整形数据，其中用到了malloc和memset函数 ，代码如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//创建结点
typedef struct SeqList {       //包含表的各种属性
    int capacity;          // 容量
    int length;         //长度
    int * node;         //指针数组
} HSeqList;

//创建顺序表
HSeqList * createSeqList(int capacity) {
    int ret;
    HSeqList * head = (HSeqList *)malloc(sizeof(HSeqList));

    if(head == NULL) {
        ret = 1;
        printf("create seqList error %d\n",ret);
        return NULL;
    }

    memset(head,0,sizeof(HSeqList));       //清空头结点
    head->capacity = capacity;
    head->length = 0;
    head->node = (int *) malloc(sizeof(void *)*capacity);

    if(head->node == NULL) {
        ret = 2;
        printf("create seqList error %d\n",ret);
        return NULL;
    }

    return head;
}

2.1.2 获取长度，容量并且封装打印方法。

//求顺序表容量
int getCapacity(HSeqList * list) {
    HSeqList * temp = NULL;
    if(list == NULL) {
        return;
    }
    temp = list;
    return temp->capacity;
}
//求顺序表长度
int getLength(HSeqList * list) {
    HSeqList * temp = NULL;
    if(list == NULL) {
        return;
    }
    temp = list;
    return temp->length;
}

//输出
void print(HSeqList * list){
    if(list == NULL) {
        printf("not init SeqList\n");
        return;
    }
    int length = getLength(list);
    int i;
    printf("[");
    for(i=0;i<length-1;i++){
        printf("%d,",list->node[i]);
    }
    printf("%d]\n",list->node[i]);
} 

2.1.3 添加数据

//添加数据
int addData(HSeqList * list,int data) {
    if(list == NULL){
        printf("not init SeqList\n");
        return 0;
    }
    if(list->length>=list->capacity){
        printf("SeqList is full,not add data,current data is %d\n",data);
        return 0;
    }
    int index = list->length;
    list->node[index] = data; 
    list->length++;
    return 1;
}

2.1.4 插入

  如果要在顺序表中插入数据，则需要将该位置后的所有元素往后移动。
例如，在[A,B,C,D,E,F]中把G插入到第二个位置。要先移位然后插入。如图所示：

插入1
移位 插入2

代码如下：

//插入
int insert(HSeqList *list,int data,int pos){
    int i;
    if(list == NULL) {
        printf("not init SeqList\n");
        return -1;
    }
    if(list->length>=list->capacity){
        printf("SeqList is full,not insert data,current data is %d\n",data);
        return -2;
    }
    
    //如何插入位置在length之前，则默认插入到最后一位 
    if(pos>list->length){
        pos = list->length;
    }
    //从后往前移位，防止数据丢失 
    for(i=list->length;i>pos;i--){
        list->node[i] = list->node[i-1];
    }
    //插入数据 
    list->node[i] = data;
    //增加长度 
    list->length ++;
    
    return 1;
} 

2.1.5 删除

  删除指定位置的元素后，该位置往后的元素依次往前移动。

 delete(HSeqList *list, int pos) {
    if(list == NULL) {
        printf("not init SeqList!\n");
        return -1;
    }
    if(list->length <= 0) {
        printf("SeqList not data!\n");
        return -2;
    }
    
    if(pos < 0 || pos >list->length){
        printf("delete position error!\n");
        return -3;
    }
    
    int i;
    for(i=pos; i<=list->length;i++){
        list->node[i] = list->node[i+1];
    }
    
    list->length--;
    return 1;
}

2.1.6 查找某个位置上的指定元素

//查找某个位置上的指定元素
int getData(HSeqList *list,int pos){
    if(list == NULL) {
        printf("not init SeqList!\n");
        return -1;
    }
    if(pos < 0 || pos >=list->length){
        printf("position error!\n");
        return -3;
    }
    
    return list->node[pos];
} 

2.1.7 清空表

//清空表
int clear(HSeqList *list){
    if(list == NULL) {
        printf("not init SeqList!\n");
        return -1;
    }
    list->length = 0;
    memset(list->node,0,(list->capacity * sizeof(void *)));
    return 1;
}

2.1.8 测试代码

int main() {
    
    printf("init:\n");
    int capacity = 100;
    HSeqList *list = createSeqList(capacity);
    int s = getCapacity(list);
    printf("Capacity = %d\n",s);

    printf("addData:\n");
    int i;
    for(i=0; i<10; i++) {
        addData(list,i);
    }
    print(list);
    
    printf("insert:\n");
    insert(list,100,3);
    print(list);
    printf("delete:\n");
    delete(list,3);
    print(list);
    
    printf("getData:\n");
    printf("index %d is %d\n",0,getData(list,0));
    
    printf("clear:\n");
    clear(list);
    print(list);
    return 0;
}

输出结果：

输入结果

源码地址 https://github.com/ThinkingXuan/DataStructure