数据结构与算法(预习)

发布于 2020-09-05  236 次阅读


前言

因为成电是大二开始学数据结构与算法,算是计院的主科吧,正好这两天考完试有时间所以就先预习了一下数据结构与算法,跳过了前面的基础部分直接从线性结构开始预习了,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:


浪子三唱,不唱悲歌