【数据结构复习】线性表

时间:2021-10-02 10:34:57

感觉数据结构和算法很久没有学习过了,这么久的时间都在做功能性的东西,没有研究基础的数据结构和算法,有必要复习一下。

而且发现LeetCode都已经200+的题目了,感觉又可以没事水水题目了。

今天开始第一课数据结构的线性表:

线性表分为两种,一种是顺序结构存储的,一种是链式结构存储的。

两种表之间有明显的不同,前者是在连续的内存空间存储的数据结构,而后者可以在离散的内存空间。

个人觉得虽然两者都有好处,但是依然觉得链式表的优势明显。

下面是实现:

顺序存储

#include <stdio.h>
#include <string.h>
#define MAXSIZE 10

typedef int ElemType;

typedef struct
{
ElemType data[MAXSIZE];
int length;
}SqList;

// get the element at position
int GetElement(SqList L, int pos )
{
// check the list and the pos
if (L.length == 0 || pos < 1 || pos > L.length)
{
printf("您的线性表为空或获取位置有误\n");
return false;
}
return L.data[pos - 1];
}

// insert the element at position
bool InsertElement(SqList L, int pos, ElemType elem)
{
// check the list and the position
if (L.length >= MAXSIZE || pos < 1 || pos > L.length + 1 )
{
printf("您的线性表已满或插入位置有误\n");
return false;
}

if (pos < L.length)
{
for (int index = L.length - 1; index >= pos - 1; index --)
{
L.data[index + 1] = L.data[index];
}
}
L.data[pos - 1] = elem;
L.length++;

return true;
}

// delete the element at position
bool DeleteElement(SqList L, int pos, int elem)
{
// check the list and the position
if (L.length == 0 || pos < 1 || pos > L.length)
{
printf("您的线性表为空或位置有误");
return false;
}
elem = L.data[pos - 1] ;
if (pos < L.length)
{
for (int index = pos; index < L.length ; index++)
{
L.data[index - 1] = L.data[index];
}
}
L.length -- ;
return true;
}

int test()
{
// init the list
SqList list;
for (int index = 0; index < 10; index++)
{
list.data[index] = index;
}
list.length = 10;

int i = GetElement(list, 2);
printf("Get element from the list at position 2 is %d \n", i);
InsertElement(list, 10, 99);
printf("Insert element to the list at position 11 \n");
int elem=0;
DeleteElement(list, 2, elem);
printf("Delete element from the list at position 2 is %d \n", elem);

return 0;
}