数据结构-线性表-顺序表(c语言)


线性表

线性表的定义

​ 一个数据元素可以由若干个数据项组成。数据元素称为记录,含有大量记录的线性表又称为文件。这种结构具有下列特点:存在一个唯一的没有前驱的(头)数据元素;存在一个唯一的没有后继的(尾)数据元素;此外,每一个数据元素均有一个直接前驱和一个直接后继数据元素。
  

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构,使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。


顺序表头文件(SeqList.c)

#ifndef _SEQLIST_H_
#define _SEQLIST_H_
typedef void SeqList;//void 起别名为SeqList
typedef void SeqListNode;
SeqList* SeqList_Create(int capacity);
void SeqList_Destory(SeqList *list);
void SeqList_Clear();
int  SeqList_Length();
int  SeqList_Capacity();
#endif

一. 创建顺序表(SeqListAll.c)

  1. 定义一个struct来保存顺序表信息

  2. 为头节点分配内存

  3. 为顺序表分配空间,将顺序表空间地址保存在头节点中

  4. 将头节点地址返回给调用者

    //创建顺序表
    SeqList*  SeqList_Create(int capacity)
    {
        int ret;
        TSeqList* temp = NULL;
        temp = (TSeqList *) malloc(sizeof(TSeqList)); //为头节点分配空间
        if(temp==NULL)
        { //中间对象分配失败
            ret = 1;
            printf("func SeqList_Create() error:%d\n",ret);
            return NULL;
        }
    
        //memset(temp,0,sizeof(TSeqList)); //填充
        temp->capacity = capacity;
        temp->length = 0;
        temp->node = (int *)malloc(sizeof(int *)* capacity); //分配一个指针数组
        if(temp->node==NULL)
        { //中间对象投指针分配失败
            ret = 2;
            printf("func SeqList_Create() error:%d\n",ret);
            return NULL;
        }
        return temp;
    }
    

二、求顺序表的容量

  • 直接从头节点获取

    //获取容量
    int SeqList_Capacity(SeqList* list)
    {
        TSeqList* temp = NULL;
        if(list==NULL)
        {
            return -1;
        }
        temp = (TSeqList*) list;
        return temp->capacity;
    }
    

三、获取顺序表长度

  • 直接从头节点获取

    //求顺序表的长度
    int SeqList_Length(SeqList * list)
    {
        TSeqList * temp = NULL;
        if(list==NULL)
        {
            return 0;
        }
        temp = (TSeqList *)list;
        return temp->length;
    }
    

四、插入元素

  • 当顺序表已满时,表中的元素向后无法移动。需要做出特别处理【不插入or开辟一块更大的空间】

  • 当插入的位置是空闲区域时,需要作出相应处理

    //插入元素
    int SeqList_Insert(SeqList* list,SeqListNode* node,int pos){
        int i;
        TSeqList *temp = NULL;
        if(list==NULL || node==NULL){
            return -1;
        }
        temp = (TSeqList *) list;
        //顺序表满了
        if(temp->length >= temp->capacity){
            return -2;
        }
    
        if(pos>temp->length)
            pos = temp->length;
    
        for(i=temp->length;i>pos;i--){
            temp->node[i] = temp->node[i-1];
        }
        temp->node[i] = (int)node;
        temp->length++;
        return 0;
    }
    

五、删除元素

  • 从顺序表中删除某一个元素后需要将后面的元素依次向前移动来不齐空位

    /删除元素
    SeqList* SeqList_Delete(SeqList* list,int pos)
    {
        int i;
        TSeqList*  tlist = NULL;
        SeqListNode* temp = NULL;
        tlist = (TSeqList *)list;
        if(list=NULL|| pos < 0|| pos>= tlist->capacity)
        {
            printf("SeqList_DELET ERROR\n");
            return NULL;
        }
        temp = (SeqListNode * )tlist->node[pos]; //要删除的元素
    
        for(i=pos+1;i<tlist->length;i++)
        {
            tlist->node[i-1] = tlist->node[i];
        }
    
        tlist->length--;
        return temp;
    }
    

六、查找元素

  • 使用数组下标查找,非常方便

    //查找
    SeqList* SeqList_Get(SeqList * list,int pos)
    {
        //健壮性判断
        TSeqList* tlist = NULL;
        SeqListNode* temp = NULL;
        tlist = (TSeqList *) list;
        if(list==NULL|| pos<0 || pos >= tlist->capacity)
        {
            printf("SeqList_Get error\n");
            return NULL;
        }
        temp = (SeqListNode *)tlist->node[pos];
        return temp;
    }
    

七、清空表

  • 将表中的元素全部置为0

    //清空表
    void SeqListClean(SeqList* list)
    {
        TSeqList * temp = NULL;
        if(list==NULL)
        {
            return;
        }
        temp = (TSeqList *) list;
        temp->length=0;
        //menset(temp->node,0,(temp->capacity * sizeof(void *)));
        return;
    }
    

八、销毁表

  • 将整个表销毁

    //销毁表
    void Seqlist_Destory(SeqList* list)
    {
        TSeqList* temp = NULL;
        if(list==NULL)
        {
            return;
        }
        temp = (TSeqList *) list;
        if(temp->node != NULL)
        {
            free(temp->node);
        }
        free(temp);
        return;
    }
    

九、测试(test.c)

#include "SeqList.c"
#include <stdio.h>
#include <malloc.h>

typedef struct _Teacher {
    char name[32];
    int age;
}Teacher;

int main(){
    int ret = 0;
    SeqList* list = NULL;
    Teacher t1,t2,t3,t4,t5;
    t1.age = 31;
    t2.age = 32;
    t3.age = 33;
    t4.age = 34;
    t5.age = 35;
    //创建节点
    list = SeqList_Create(10);

    //插入节点
    ret = SeqList_Insert(list,(SeqListNode *)&t1,0);
    ret = SeqList_Insert(list,(SeqListNode *)&t2,0);
    ret = SeqList_Insert(list,(SeqListNode *)&t3,0);
    ret = SeqList_Insert(list,(SeqListNode *)&t4,0);
    ret = SeqList_Insert(list,(SeqListNode *)&t5,0);

    printf("顺序表容量%d\n",SeqList_Capacity(list));
    printf("顺序表长度%d\n",SeqList_Length(list));

    //遍历顺序表
    printf("遍历顺序表: \n");
    int i = 0;
    for(i = 0;i<SeqList_Length(list);i++)
    {
        Teacher* temp = (Teacher *) SeqList_Get(list,i);
        if(temp==NULL)
        {
            printf("func SeqList_Get error",ret);
            return 0;
            //return;
        }
        printf("age: %d\n",temp->age);
    }

    //销毁链表
    printf("销毁顺序表: \n");
    while(SeqList_Length(list)>0){
        Teacher * temp = (Teacher *)SeqList_Delete(list, 0);
        if(temp==NULL){
            printf("func SeqList_Delete error");
            return 0;
        }
        printf("age :%d\n",temp->age);
    }
    Seqlist_Destory(list);
    system("pause");
    return 0;
}

文章作者: Mr.zhao
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-NC 4.0 许可协议。转载请注明来源 Mr.zhao !
评论
 上一篇
2021-09-17 Mr.zhao
下一篇 
test2 test2
2021-09-12 Mr.zhao
  目录