数据结构-之-线性表

Posted on | In

数据结构底层实现的物理结存储构说到底无非就是 —— 数组（Array） 和 链表（LinkList）。

线性表定义

具有相同特征的数据元素的一个有限序列。

顺序存储结构 —— 顺序表

  • 连续的一段存储空间，逻辑上相邻元素，物理存储上也是相邻的。
  • 直接通过一个下标获取到表中某个元素。
  • 顺序表存储数据时，会提前申请一整块足够大小的物理空间

头文件：”OrderList.h”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define MAX_SIZE 10       // 定义顺序表默认能存储的最大空间大小
#define TRUE 1
#define FALSE 0

typedef int *elem;     // 定义指针类型
typedef int bool;

/*顺序表数据结构定义*/
typedef struct {
    elem head;      // 表头结点指针
    int length;     // 表当前数据大小
    int size;       // 表最大空间
} myTable;

extern myTable initList(int size);
extern bool listInsert(myTable *t, int i, int x);
extern bool listAppend(myTable *t, int x);
extern bool listDelete(myTable *t, int i);
extern bool listDeleteByVal(myTable *t, int val, bool delAll);
extern void listBoomSort(myTable *t);
extern int listSearch(myTable *t, int val);
extern int listBinarySearch(myTable *t, int val);
extern void showList(myTable *t);
extern bool isEmpty(myTable *t);
extern void destroyList(myTable *t);
extern void showListInfo(myTable t);

以下：“OrderList.c”

1、初始化顺序表：

这里可以指定初始化大小size，通过malloc函数动态获取内存空间，返回一个已经定义好的结构的表。

  • 初始化分配内存空间
  • 指针指向内存空间
  • 设置总空间size
  • 设置当前使用长度length
1
2
3
4
5
6
7
8
9
10
11
12
/*初始化顺序表*/
myTable initList(int size) {
    if (size <= 0) {
        printf("顺序表大小必须大于0！这里采用默认大小初始化为10");
        size = MAX_SIZE;
    }
    myTable t;
    t.head = (int *) malloc(size * sizeof(int));
    t.size = size;
    t.length = 0;
    return t;
};

2、动态扩容操作

在使用过程中，我们可能会往表里面不断加入数据，但是我们刚才默认申请的内存空间是10，当空间不够用了，我们需要灵活的增加，如下：

  • 定义一个数据指针
  • 开辟一片原来空间大小2倍的新内存空间，用指针指向它
  • 拷贝原来数据指针指向空间的数据，到新开辟区域内
  • 重置空间大小参数size
  • 原来的表数据指针指向新申请的空间地址
1
2
3
4
5
6
7
8
9
10
/*动态扩容*/
void dilation(myTable *t) {
    elem data = NULL;
    data = (int *) malloc((t->size * 2) * sizeof(int));
    for (int i = 0; i < t->length; ++i) {
        data[i] = t->head[i];
    }
    t->size = t->size * 2;
    t->head = data;
}

3、销毁表

只需要 使用 free() 函数 释放掉数据指针即可

1
2
3
4
5
6
/*销毁顺序表*/
void destroyList(myTable *t) {
    free(t->head);
    t->size = 0;
    t->length = 0;
}

4、判断为空

1
2
3
4
5
6
/*是否为空*/
bool isEmpty(myTable *t) {
    if (t->length > 0)
        return FALSE;
    return TRUE;
}

5、插入元素【从数据中间和末尾都要考虑】

  • 指定插入位置
  • 如果插入位置在已有元素中间，则要往后移动元素，如果空间不足要动态扩容
  • 如果插入位置没有存储数据，直接放入即可
  • 长度length增加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*插入新元素*/
bool listInsert(myTable *t, int i, int x) {
    if (t->length == t->size - 1)
        dilation(t);
    if (i < 0 || i > t->size - 1)
        return FALSE;
    if (i < t->length) {
        // 后移 插入位置 后面的 数据
        for (int j = t->length; j > i; j--) {
            t->head[j] = t->head[j - 1];
        }
        t->head[i] = x;
    } else {
        // 如果插入数据在后面空闲位置，不管，直接放进去
        t->head[i] = x;
    }
    t->length++;
    return TRUE;
}

6、末尾追加元素

在现有数据的最后追加元素

  • 直接放在length位置，并增加长度即可
1
2
3
4
5
6
7
8
/*末尾添加元素*/
bool listAppend(myTable *t, int x) {
    if (t->length == t->size - 1)
        dilation(t);
    t->head[t->length] = x;
    t->length++;
    return TRUE;
}

7、按照下标删除元素

指定位置往后的元素向前移动，长度减少

  • 删除第i位，从第i 位 开始往后到元素末尾，依次往前移动
1
2
3
4
5
6
7
8
9
10
/*删除元素-按照下标*/
bool listDelete(myTable *t, int i) {
    if (i < 0 || i > t->length - 1)
        return FALSE;
    for (int j = i; j < t->length; j++) {
        t->head[j] = t->head[j + 1];
    }
    t->length--;
    return TRUE;
}

8、删除元素-按照元素名

可设置是否删除所有重复的，delAll 为 FALSE只删除查找到的第一个

  • 注意，删除一个元素，会移动元素，下标随之改变，所以，需要从头再搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*删除元素-按照元素值*/
bool listDeleteByVal(myTable *t, int val, bool delAll) {
    // 首先要找到元素
    for (int i = 0; i < t->length; i++) {
        if (t->head[i] == val) {
            for (int j = i; j < t->length; j++) {
                t->head[j] = t->head[j + 1];
            }
            t->length--;
            if (!delAll) break;
            i = -1;
        }
    }
    return TRUE;
}

9、排序

1
2
3
4
5
6
7
8
9
10
11
12
13
/*冒泡排序*/
void listBoomSort(myTable *t) {
    int temp;
    for (int i = 0; i < t->length; ++i) {
        for (int j = i + 1; j < t->length; ++j) {
            if (t->head[j] < t->head[i]) {
                temp = t->head[j];
                t->head[j] = t->head[i];
                t->head[i] = temp;
            }
        }
    }
}

10、查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*暴力查找元素*/
int listSearch(myTable *t, int val) {
    for (int i = 0; i < t->length; ++i) {
        if (t->head[i] == val)
            return i;
    }
    return -1;
}

/*二分法查找*/
int listBinarySearch(myTable *t, int val) {
    int l = 0, r = t->length - 1, mid;
    while (l < r){
        mid = (l + r) / 2;
        if (val == t->head[mid])
            return mid;
        else if (val > t->head[mid])
            l = mid + 1;
        else
            r = mid - 1;
    }
    return -1;
}

int listBinarySearch1(myTable *t, int val, int l, int r) {
    int mid = (l + r) / 2;
    if (val == t->head[mid])
        return mid;
    if (val > t->head[mid]) {
        l = mid + 1;
        return listBinarySearch1(t, val, l, r);
    }
    if (val < t->head[mid]){
        r = mid - 1;
        return listBinarySearch1(t, val, l, r);
    }
    return -1;
}

11、打印输出

1
2
3
4
5
6
7
8
/*打印顺序表所有元素*/
void showList(myTable *t) {
    printf("\n顺序表元素如下：\n");
    for (int i = 0; i < t->length; ++i) {
        printf("%d->%d\t addr: %p \n", i, t->head[i], &t->head[i]);
    }
    printf("\n");
}

主程序使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<stdio.h>
#include <stdlib.h>
#include "OrderList.h"

int main() {
    myTable t = initList(15);
    showListInfo(t);
    for (int i = 0; i < 12; ++i) {
        listAppend(&t, i * 2 );
    }

    listInsert(&t, 2, 99);
    listInsert(&t, 6, 54);
    listDelete(&t, 2);
    listDeleteByVal(&t, 10, FALSE);

    int res = listSearch(&t, 16);
    printf("listSearch: %d -> 16", res);

    showList(&t);

    listBoomSort(&t);

    showList(&t);

    int  res1 = listBinarySearch(&t, 111);
    printf("listBinarySearch: %d -> 111", res1);

    showListInfo(t);

    destroyList(&t);
    showList(&t);
    return 0;
}

链式存储结构 —— 链表

在链式存储结构中，不仅含有元素本身信息（数据域），而且包含元素之间的逻辑关系信息（指针域）。

单链表

除了数据元素本身外，应该包含一个指针域，用以指向当前元素的后继节点。

定义如下：

1、结构体

1
2
3
4
5
6
typedef char *elemType;

typedef struct singleLinkList{
    elemType data;
    struct singleLinkList *next;
} singleLinkList;

2、创建一个单链表节点

1
2
3
4
5
6
7
/*创建一个数据节点*/
singleLinkList * createSingleLinkListNode(elemType data){
    singleLinkList *node = (singleLinkList *)malloc(sizeof(singleLinkList));
    node->data = data;
    node->next = NULL;
    return node;
}

3、尾插法

1
2
3
4
5
6
7
8
9
10
11
12
/*尾插*/
void insertSingleLinkListNodeEnd(singleLinkList **list, elemType data){
    singleLinkList *node = createSingleLinkListNode(data);
    if (*list == NULL){
        *list = node;
    }
    singleLinkList *cur = *list;
    while (cur->next != NULL){
        cur = cur->next;
    }
    cur->next = node;
}

4、头插法

1
2
3
4
5
6
/*头插*/
void insertSingleLinkListNodeFirst(singleLinkList **list, elemType data){
    singleLinkList *node = createSingleLinkListNode(data);
    node->next = *list;
    *list = node;
}

打印单链表

1
2
3
4
5
6
7
/*打印单链表*/
void showSingleLinkList(singleLinkList *list){
    for (singleLinkList *cur= list;  cur != NULL ; cur = cur->next) {
        printf("%s->", cur->data);
    }
    printf("NULL\n");
}