顺序表

数据结构 › C
,
·本篇:617字 大约需要: 3分钟

前言

顺序表的实现以及基本操作

编程语言: C

顺序表

线性表的抽象数据类型

顺序表的定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素

基本操作实现

  • 结构代码
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#define sf scanf
#define pf printf
const int MaxN = 100;

typedef struct SqList
{
    int *data;
    int length;
} SqList;
  • 初始化一个空表
1
2
3
4
5
void InitList(SqList *p)
{
    p->data = (int *) malloc(MaxN * sizeof(int));
    p->length = -1;
}
  • 随机初始化一个顺序表
1
2
3
4
5
6
7
void RandList(SqList *p)
{
    srand((unsigned) time(0));
    p->length = rand() % 10 + 10;
    for(int i = 0; i <= p->length; i++)
        p->data[i] = rand() % 10 + 2;
}
  • 判断顺序表是否为空
1
2
3
4
bool ListEmpty(SqList *p)
{
    return p->length == -1;
}
  • 判断顺序表是否存满
1
2
3
4
bool ListFull(SqList *p)
{
    return p->length == MaxN;
}
  • 将顺序表中第i个元素取出
1
2
3
4
int GetElem(SqList *p, int i)
{
    return p->data[i - 1];
}
  • 查找表中是否存在目标元素
1
2
3
4
5
6
7
8
9
10
11
12
13
int LocateElem(SqList *p, int target)
{
    int pos = -1;
    for(int i = 0; i <= p->length; i++)
    {
        if(p->data[i] == target)
        {
            pos = i;
            break;
        }
    }
    return pos;
}
  • 在顺序表第i个位置插入目标元素
1
2
3
4
5
6
7
8
9
10
11
12
13
void ListInsert(SqList *p, int i, int target)
{
    if(ListEmpty(p))
        p->data[i] = target;
    else if(i < MaxN && !ListFull(p))
    {
        for(int j = p->length; j >= i; j--)
            p->data[j + 1] = p->data[j];
        p->data[i] = target;
    }
    else
        pf("插入失败\n");
}
  • 删除顺序表中第i个元素并返回其值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int ListDelete(SqList *p, int i)
{
    int temp = -1;
    if(i <= p->length && !ListEmpty(p))
    {
        temp = p->data[i];
        for(int j = i; j < p->length; j++)
            p->data[j] = p->data[j + 1];
        p->length--;
    }
    else
        pf("删除失败\n");
    return temp;
}
  • 返回顺序表中的元素个数
1
2
3
4
int ListLength(SqList *p)
{
    return p->length + 1;
}
  • 清空线性表
1
2
3
4
5
6
7
void ClearList(SqList *p)
{
    for(int i = 0; i <= p->length; i++)
        p->data[i] = 0;
    p->length = -1;
    pf("清空成功\n");
}
  • 遍历顺序表中所有元素
1
2
3
4
5
6
7
8
9
10
11
12
void DisplayList(SqList *p) 
{
    pf("表长 = %d\n", p->length + 1);
    if(!ListEmpty(p))
    {
        for(int i = 0; i <= p->length; i++)
            pf("%d ", p->data[i]);
        pf("\n");
    }
    else
        pf("表为空\n");
}

总结

线性表是数据结构中最简单最常用的一种结构，也是我学习数据结构的开端。