数据结构顺序表(代码片段)

前言：本章介绍的主要内容是顺序表

1.线性表

线性表 （linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串等

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2.顺序表

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表的本质就是数组，动态增长，并且要求里面存储的数据必须是从左往右连续的。逻辑结构与物理结构是一致的。

这里介绍下逻辑结构与物理结构的概念：

• 逻辑结构: 人为想象出来的,实际并不存在.
• 物理结构: 实际存在,可以被观察到

2.2顺序表分类

1.静态顺序表：使用定长数组存储。
2.动态顺序表：使用动态开辟的数组存储，容量不受限制,支持数据插入,删除,修改等一系列操作。（接下来着重介绍）

3.动态顺序表项目创建

3.1 定义顺序表

typedef int SQDataType;

typedef struct SeqList

    SQDataType* data;    
    int size;      
    int capacity;  
SLT;  

思考下为何使用typedef？

如果一开始我们就确定了结构体中的变量类型，后续在项目过程中如果需要对这个变量类型进行调整，那么所需的操作是很繁琐的。故使用typedef，后续若是需要修改，改动typedef就足够了。

3.2 顺序表的初始化

思考这样进行初始化可行否？

//SeqList.c
void SeqListInit(SLT ps)

    ps.a=NULL;
    pa.size=ps.capacity=0;

//test.c
int main()

	SLT plist =  1 ;
	SeqListInit(plist);

	return 0;

这种初始化方式显然不行，大家可以回想下函数传参的内容，函数内的ps只是plist的一份临时拷贝,此时拷贝量的改变不会影响plist。那我们想要改变plist怎么办？传址！

修改后的正确初始化：

//SeqList.c
void SeqListInit(SLT* ps)

	assert(ps);  //加个断言，ps不能为空指针
	ps->a = NULL;
	ps->size = ps->capacity = 0;


//test.c
int main()

	SLT plist =  1 ;
	SeqListInit(&plist);

	return 0;

3.3 顺序表的打印

直接用for进行打印

void SeqListPrint(SLT* ps)

    for(int i = 0;i<ps->size;i++)
    
        printf("%d->",ps->data[i]);
    
    printf("\\n");

3.4 顺序表的增容

1.首先检查是否容量已经满了（ps->size == ps->capacity）

2.如果没满就无所谓，如果满了并且ps->capacity！=0,就增加容量,增加方式是2倍增加，如果满了并且ps->capacity=0，说明还是空容量,就增加4个空间。

void SeqListCheckCapacity(ps)

    if(ps->size == ps->capacity)
    
        //如果capacity为0就给他4个空间,否则进行2倍增容.
        int newcapacity = (ps->capacity) ==  0 ? 4:(ps->capacity)*2;
        SQDataType* p =
            (SQDataType*)realloc(ps->data,sizeof(SLT)*newcapacity);
        //判断下p是否为空
        if(p==NULL)
        
            perror("错误原因:");
            return;
        
        ps->data = p;
        ps->capacity = newcapacity;
   

3.5 顺序表的尾插

1.和初始化类似，需要进行传址。

2.检查顺序表是否还有容量。

3.在最后一个位置上插入新数据

void SeqListPushBack(SLT* ps,SQDataType elem)

    assert(ps); 
    
    SeqListCheckCapacity(ps);//检查容量是否足够，不够就增容
    ps->data[ps->size] = elem; //尾部插入
    ps->size++;//实际容量加1

3.6 顺序表的头插

1.和初始化类似，需要进行传址。

2.检查顺序表是否还有容量。

3.挪动数据,给第一个位置空出来，在空出来的位置上插入新数据

void SeqListPushFront(SLT* ps,SQDataType elem)

	assert(ps);    
    SeqListCheckCapacity(ps);//检测是否还有空间
    
    for(int i= ps->size;i>0;i--)
    
        ps->data[i] = ps->data[i-1];
    
    
    ps->data[0] = elem;
    ps->size++;

3.7 顺序表的尾删

很简单，直接让ps->size-1即可。

void SeqListPopBack(SLT* ps)

    assert(ps->size > 0); //必须保证有数据可以删除
    ps->size--;

3.8 顺序表的头删

直接挨个把数据向前挪进行覆盖,然后ps->size-1

void SeqListPopFront(SLT* ps)

    assert(ps->size > 0);
    
	for(int i= 0;i<ps->size-1;i++)
    
        ps->data[i] = ps->data[i+1];
    
    ps->size--;

3.9 顺序表的查找操作

1.给一个元素,查找是否在顺序表内,如果在,返回下标.

2.如果不在,返回-1

int SeqListFind(SLT* ps,SQDataType elem)

    assert(ps->size > 0);
    assert(ps);
    for(int i= 0;i<ps->size;i++)
    
        if(ps->data[i] == elem)
            return i;
    
    return -1;

3.10 顺序表的插入操作

函数包含：指定插入下标,和想插入的元素

实现方法: 输入的下标位置及其后,所有数据都往后面挪，然后插入数据,ps->size+1

void SeqListInsert(SLT* ps,size_t index,SQDataType elem)

    assert(ps);
    assert(ps->size >= index); //被插入的位置必须小于等于size

	SeqListCheckCapacity(ps); 
	
    for(int i = ps->size;i>index;i--)
    
        ps->a[i] = ps->a[i-1];
    
    ps->a[index] = elem;
    ps->size++;

3.11 顺序表的删除操作

函数包含：指定被删除元素的下标

实现方法: 直接覆盖被删除元素,并挨个往前覆盖，然后ps->size+1

void SeqListErease(SLT* ps,size_t index)

    assert(ps->size > 0);//必须有元素可以删除
    
    for(int i = index;i< ps->size-1;i++)
    
        ps->data[i] = ps->data[i+1];
    
    ps->size--;

3.12 顺序表的元素数量查看操作

size_t SeqListSize(SLT* ps) 

	assert(ps);
	return ps->size;

3.13 顺序表某个元素的修改操作

void SeqListAt(SLT* ps, size_t index, SQDataType elem)

	assert(ps);
	assert(index < ps->size);
	ps->a[index] = elem;

3.14 顺序表的销毁操作

void SeqListDestroy(SLT* ps)

    assert(ps);
    if(ps->data != NULL)
    
        free(ps->data);
        ps->data = NULL;        
    
    ps->size = ps->capacity = 0;

4.源码链接

https://gitee.com/linkylo/c_code_2021/tree/master/c_code_2021_8_11

数据结构的顺序表内容到此设计结束了，感谢您的阅读！！！如果内容对你有帮助的话，记得给我三连（点赞、收藏、关注）——做个手有余香的人。