数据结构与算法(预习)

前言

因为成电是大二开始学数据结构与算法，算是计院的主科吧，正好这两天考完试有时间所以就先预习了一下数据结构与算法，跳过了前面的基础部分直接从线性结构开始预习了，begin is线性表。

线性表

定义

线性表是具有相同数据类型的 n （n>= 0）个数据元素的有限序列。其中 n 为 表长，当 n = 0时，该线性表是一个空表。若用 L 命名线性表，则其一般表示如下：

L = ( a1 , a2 , a3 , ... , a(i) , a( i + 1) , ... , a(n) )

分类

线性表一般分为两类

1. 顺序表(逻辑相邻，物理也相邻)。一维数组可以看做是特殊的顺序表
2. 链表(逻辑相邻，物理不一定相邻)

基本操作

1. InitList(&L) ： 初始化表。构造一个空的线性表。
2. Length( L ) ： 求表长。返回线性表 L 的长度，即 L 中数据元素的个数。
3. LocateElem( L , e ) : 按值查找操作。在表 L 中 查找具有给定关键字值的元素。
4. GetElem( L , i ) ： 按位查找操作。获取表 L 中第 i 个位置的元素的值
5. ListInsert( &L , i , e ) ：插入操作。在表 L 中的第 i 个位置插入指定元素 e
6. ListDelete( &L , i , &e) ： 删除操作。删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值。
7. PrintList( L ) ： 输出操作。按前后顺序输出线性表 L 的所有元素的值。
8. Empty( L ) ： 判空操作。若 L 为空表，则返回 true ，否则返回 false 。
9. DestroyList( &L ) ： 销毁操作。销毁线性表，并释放线性表 L 所占用的内存空间。

顺序表的基本操作

#include < stdlib.h >
#include < stdio.h >
#define MAXSIZE 100

typedef enum Status {
    success, fail, fatal, range_error
}Status;

typedef int EleType;

typedef struct Sqlist {
    EleType* elem;
    int length;
}Sqlist, * ListPtr;

Status List_init(ListPtr L)
{
    Status status = fatal;
    L->elem = (EleType*)malloc((MAXSIZE) * sizeof(EleType));
    if (L->elem)
    {
        L->length = 0;
        status = success;
    }
    return status;
}

Status List_insert(ListPtr L, int pos, EleType elem)
{
    Status status = range_error;
    int len = L->length, i;
    if (len > MAXSIZE)
        return fail;
    else if (0 <= pos && pos <= len)
    {
        for (i = len;i >= pos;i--)
        {
            L->elem[i+1] = L->elem[i];
            L->elem[pos] = elem;
            L->length++;
            status = success;
        }
    }
    return status;
}
Status List_delete(ListPtr L, int pos)
{
    Status status = range_error;
    int len = L->length, i;
    for (i = pos;i < len;i++)
    {
        L->elem[i] = L->elem[i + 1];
    }
    status = success;
    L->length--;
    return status;
}

void List_destory(ListPtr L)
{
    if (L->elem)
    {
        free(L->elem);
        L->elem = NULL;
    }
    L->length = 0;
}

void List_print(ListPtr L)
{
    int len = L->length;
    for (int i = 0; i < len; i++)
    {
        printf("%d号元素是%d\n",i, L->elem[i]);
    }
}

结语

接着努力吧，马上又要是新学期了:punch: