数据结构之顺序表完成

功能测试代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "seqlist.h"

typedef struct student{
    char name[20];
    int age;
}student;

int main(int argc, char *argv[])
{
    student stu1,stu2,stu3,stu4,stu5;

    stu1.age = 20;
    stu2.age = 21;
    stu3.age = 22;
    stu4.age = 23;
    stu5.age = 24;

   TSeqList *pslist = (TSeqList*)SeqList_Create(5);

    SeqList_Insert(pslist, (SeqListNode*)&stu1, 0);
    SeqList_Insert(pslist, (SeqListNode*)&stu2, 1);
    SeqList_Insert(pslist, (SeqListNode*)&stu3, 2);
    SeqList_Insert(pslist, (SeqListNode*)&stu4, 3);
    SeqList_Insert(pslist, (SeqListNode*)&stu5, 4);
    printf("length: %d\n",SeqList_Length(pslist));
    SeqList_Traverse(pslist,student,age);

    SeqList_Delete(pslist,2);
    printf("length: %d\n",SeqList_Length(pslist));
    int i;
    student *ptmp = NULL;
    for(i=0; i < SeqList_Length(pslist); i++)
    {   
        ptmp = SeqList_Get(pslist,i);   
        printf("age: %d\n",ptmp->age);
    }
    SeqList_Clear(pslist);
    SeqList_Destroy(pslist);
    return 0;
}

效益测试代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "seqlist.h"

typedef struct student{
    char name[20];
    int age;
}student;

int main(int argc, char *argv[])
{
    student stu1,stu2,stu3,stu4,stu5;

    stu1.age = 20;
    stu2.age = 21;
    stu3.age = 22;
    stu4.age = 23;
    stu5.age = 24;

   TSeqList *pslist = (TSeqList*)SeqList_Create(5);

    SeqList_Insert(pslist, (SeqListNode*)&stu1, 0);
    SeqList_Insert(pslist, (SeqListNode*)&stu2, 1);
    SeqList_Insert(pslist, (SeqListNode*)&stu3, 2);
    SeqList_Insert(pslist, (SeqListNode*)&stu4, 3);
    SeqList_Insert(pslist, (SeqListNode*)&stu5, 4);
    printf("length: %d\n",SeqList_Length(pslist));
    SeqList_Traverse(pslist,student,age);

    SeqList_Delete(pslist,2);
    printf("length: %d\n",SeqList_Length(pslist));
    int i;
    student *ptmp = NULL;
    for(i=0; i < SeqList_Length(pslist); i++)
    {   
        ptmp = SeqList_Get(pslist,i);   
        printf("age: %d\n",ptmp->age);
    }
    SeqList_Clear(pslist);
    SeqList_Destroy(pslist);
    return 0;
}

头文件注解

//seqlist.h
#ifndef _SEQLIST_H_
#define _SEQLIST_H_

typedef void SeqList;
typedef void SeqListNode;

typedef struct tag_SeqList{
    int length;
    int capacity;
    unsigned int **pnode;
}TSeqList;

//创建并且返回一个空的线性表
SeqList *SeqList_Create(int capacity);

//销毁一个线性表
void SeqList_Destroy(SeqList* plist);

//将一个线性表list中的所有元素清空,线性表回到创建时的状态
void SeqList_Clear(SeqList* plist);

//返回一个线性表list中的所有元素个数
int SeqList_Length(SeqList* plist);

//向一个线性表list的pos位置处插入新元素node节点
int SeqList_Insert(SeqList* plist, SeqListNode* pnode, int pos);

//获取一个线性表list的pos位置处的元素
SeqListNode* SeqList_Get(SeqList* plist, int pos);

//删除一个线性表list的pos位的node节点元素,返回值为被删除的元素,NULL表示删除失败
SeqListNode* SeqList_Delete(SeqList* plist, int pos);

//遍历顺序表
#define SeqList_Traverse(plist,node_type,number) \
({ \
    int i;\
    for(i=0; i < plist->length; i++) { \
        printf("number: %d\n",((typeof(node_type)*)(plist->pnode[i]))->number);\
    }  })
#endif //seqlist.h

seqlist.h头文件是对顺序表数据结构和职能接口的抽象。在那里面,重要注意一下几点:

  • SeqList和SeqListNode的数据类型:
    是将void数据类型的包裹。原因之一是增高代码的可读性,其二,将void封装,是为着同盟更各类类型的政工节点。
  • 以宏函数情势遍历顺序表:先是,作者想说名的少数是,遍历的效益实在在大家规划数据结构的操作函数时是没供给设计的。大家统一筹划的是对业务节点的军管,是“增加和删除改查”,“查”本就足以获得想要的工作节点,但当自个儿设计是,大家平常会波及遍历的功能,可在本身布署时发现,数组指针中数组元素指向的事务节点的数据类型不显著,所以不可能用printf函数直接打字与印刷想要的节点数据。想尝尝的消除这些标题,于是自身才设计了这几个宏函数。不用定义的函数的法门去达成遍历功用,是因为不可能在形参中央直机关接得到工作节点的数据类型,只可以通过宏的样式取得职业节点的数据类型。测试代码如下:

#include <stdio.h>
#include <stdlib.h>

typedef struct a{
    char ch;
    int num;
}A; 
int main ()
{
    A a;
    void *ptype = NULL;
    ptype = (void *)&a;
    printf("%lu\n",sizeof(typeof(ptype)));
    return 0;
}

运行的结果是:4,而不是8。得到的是ptype指针的数据类型,而不是struct
a这种数据类型。即使大家用定义函数的措施而不是概念宏函数的措施去落到实处遍历时,那么,大家接收工作节点的形参只好是“void
*”类型,但我们无能为力在函数内部采纳typeof关键子获取到形参指向的数据的数据类型,而宏函数能做到。

效果函数完成

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "seqlist.h"

//创建并且返回一个空的线性表
SeqList *SeqList_Create(int capacity)
{
    TSeqList *plist = NULL;

    plist = (TSeqList*)malloc(sizeof(TSeqList));
    memset(plist, 0, sizeof(TSeqList));
    if(NULL == plist)
    {
        perror("SeqList_Create TSeqList");
        return NULL;
    }
    plist->pnode = (unsigned int**)malloc(sizeof(unsigned int)*capacity);
    memset(plist->pnode, 0, sizeof(unsigned int)*capacity);
    if(NULL == plist->pnode)
    {
        perror("SeqList_Create pnode");
        return NULL;
    }
    //plist->length = 0;
    plist->capacity = capacity;

    return plist;
}

//销毁一个线性表
void SeqList_Destroy(SeqList* plist)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Destroy)!\n ");
        return ;
    }

    if(ptlist->pnode != NULL)
    {
        free(ptlist->pnode);
    }
    free(plist);
    return ;
}

//将一个线性表list中的所有元素清空,线性表回到创建时的状态
void SeqList_Clear(SeqList* plist)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Clear)!\n ");
        return ;
    }
    ptlist->length = 0;
    return ;
}

//返回一个线性表list中的所有元素个数
int SeqList_Length(SeqList* plist)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Length)!\n ");
        return -1;
    }

    return ptlist->length;
}

//向一个线性表list的pos位置处插入新元素node节点
int SeqList_Insert(SeqList* plist, SeqListNode* pnode, int pos)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist || NULL == pnode )
    {
        printf("SeqList is empty(SeqList_Insert)!\n ");
        return -1;
    }

    if( pos<-1 || pos >= ptlist->capacity )
    {
        printf("pos is unvalid(SeqList_Insert)!\n");
        return -2;
    }       

    int i;
    for(i=ptlist->length; i>pos; i--)
        ptlist->pnode[i] = ptlist->pnode[i-1];

    ptlist->pnode[pos] = (unsigned int*)pnode;
    ptlist->length ++;

    return 0;
}

//获取一个线性表list的pos位置处的元素
SeqListNode* SeqList_Get(SeqList* plist, int pos)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Get)!\n ");
        return NULL;
    }

    if( pos<-1 || pos > ptlist->capacity )
    {
        printf("pos is unvalid(SeqList_Insert)!\n");
        return NULL;
    }       
    return ptlist->pnode[pos];
}

//删除一个线性表list的pos位的node节点元素,返回值为被删除的元素,NULL表示删除失败
SeqListNode* SeqList_Delete(SeqList* plist, int pos)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty!(SeqList_Delete)\n ");
        return NULL;
    }

    if( pos<-1 || pos > ptlist->capacity )
    {
        printf("pos is unvalid!(SeqList_Delete)\n");
        return NULL;
    }       

    SeqListNode *pnode = NULL;
    pnode = (SeqListNode*)ptlist->pnode[pos];

    int i;
    for(i=pos; i < ptlist->length; i++)
        ptlist->pnode[i] = ptlist->pnode[i+1];
    ptlist->length --;

    return pnode;
}

总结

学数据结构大家要做的不单是读书数据结构的算法完毕,更主要的是能写出一种具备普适性的工具,站在三个更高的规划计策的角度去规划代码,那一点对于学习数据结构来讲很首要,未有那一点做支撑,学到的数据结构就只是三个空壳子,不可能灵活的应用。

逐条表简要介绍

顺序表正是以数组的款式来囤积和治本工作节点。具体的数据结构如下图:

图片 1

由上海体育场所能够,seqlist结构体便是有血有肉的顺序表数据结构,length变量表示存款和储蓄的事体节点的个数,capacity变量表示pnode指向的堆区空间体积。该堆区是3个指针数组,每八个数组成分存款和储蓄一个思想政治工作节点的地点,来针对各样业务节点,因而,管理这么些指针数组的是3个二级指针pnode;

梯次表简要介绍

顺序表正是以数组的花样来存款和储蓄和管制业务节点。具体的数据结构如下图:

图片 2

由上海教室能够,seqlist结构体正是切实的顺序表数据结构,length变量表示存款和储蓄的事务节点的个数,capacity变量表示pnode指向的堆区空间体量。该堆区是1个指南针数组,每叁个数组成分存款和储蓄1个政工节点的地点,来针对各类业务节点,由此,管理这几个指针数组的是3个二级指针pnode;

头文件表达

//seqlist.h
#ifndef _SEQLIST_H_
#define _SEQLIST_H_

typedef void SeqList;
typedef void SeqListNode;

typedef struct tag_SeqList{
    int length;
    int capacity;
    unsigned int **pnode;
}TSeqList;

//创建并且返回一个空的线性表
SeqList *SeqList_Create(int capacity);

//销毁一个线性表
void SeqList_Destroy(SeqList* plist);

//将一个线性表list中的所有元素清空,线性表回到创建时的状态
void SeqList_Clear(SeqList* plist);

//返回一个线性表list中的所有元素个数
int SeqList_Length(SeqList* plist);

//向一个线性表list的pos位置处插入新元素node节点
int SeqList_Insert(SeqList* plist, SeqListNode* pnode, int pos);

//获取一个线性表list的pos位置处的元素
SeqListNode* SeqList_Get(SeqList* plist, int pos);

//删除一个线性表list的pos位的node节点元素,返回值为被删除的元素,NULL表示删除失败
SeqListNode* SeqList_Delete(SeqList* plist, int pos);

//遍历顺序表
#define SeqList_Traverse(plist,node_type,number) \
({ \
    int i;\
    for(i=0; i < plist->length; i++) { \
        printf("number: %d\n",((typeof(node_type)*)(plist->pnode[i]))->number);\
    }  })
#endif //seqlist.h

seqlist.h头文件是对顺序表数据结构和功能接口的空洞。在那其间,主要注意一下几点:

  • SeqList和SeqListNode的数据类型:
    是将void数据类型的包装。原因之一是拉长代码的可读性,其2,将void封装,是为了合作更几类别型的事务节点。
  • 以宏函数方式遍历顺序表:首先,作者想说名的一点是,遍历的效果实在在我们统一筹划数据结构的操作函数时是没要求设计的。大家设计的是对事剧情点的管住,是“增删改查”,“查”本就能够获取想要的事剧情点,但当自家安排是,大家常常会涉嫌遍历的法力,可在笔者设计时意识,数组指针中数组成分指向的工作节点的数据类型不分明,所以不能够用printf函数直接打字与印刷想要的节点数据。想尝试的缓解那一个难点,于是笔者才设计了那么些宏函数。不用定义的函数的主意去贯彻遍历作用,是因为无法在形参中央直机关接得到职业节点的数据类型,只可以通过宏的款型取得工作节点的数据类型。测试代码如下:

#include <stdio.h>
#include <stdlib.h>

typedef struct a{
    char ch;
    int num;
}A; 
int main ()
{
    A a;
    void *ptype = NULL;
    ptype = (void *)&a;
    printf("%lu\n",sizeof(typeof(ptype)));
    return 0;
}

运作的结果是:4,而不是捌。获得的是ptype指针的数据类型,而不是struct
a那种数据类型。若是我们用定义函数的秘诀而不是概念宏函数的章程去落到实处遍历时,那么,大家收到工作节点的形参只可以是“void
*”类型,但大家鞭长莫及在函数内部使用typeof关键子获取到形参指向的数额的数据类型,而宏函数能不辱职务。

效能函数达成

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "seqlist.h"

//创建并且返回一个空的线性表
SeqList *SeqList_Create(int capacity)
{
    TSeqList *plist = NULL;

    plist = (TSeqList*)malloc(sizeof(TSeqList));
    memset(plist, 0, sizeof(TSeqList));
    if(NULL == plist)
    {
        perror("SeqList_Create TSeqList");
        return NULL;
    }
    plist->pnode = (unsigned int**)malloc(sizeof(unsigned int)*capacity);
    memset(plist->pnode, 0, sizeof(unsigned int)*capacity);
    if(NULL == plist->pnode)
    {
        perror("SeqList_Create pnode");
        return NULL;
    }
    //plist->length = 0;
    plist->capacity = capacity;

    return plist;
}

//销毁一个线性表
void SeqList_Destroy(SeqList* plist)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Destroy)!\n ");
        return ;
    }

    if(ptlist->pnode != NULL)
    {
        free(ptlist->pnode);
    }
    free(plist);
    return ;
}

//将一个线性表list中的所有元素清空,线性表回到创建时的状态
void SeqList_Clear(SeqList* plist)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Clear)!\n ");
        return ;
    }
    ptlist->length = 0;
    return ;
}

//返回一个线性表list中的所有元素个数
int SeqList_Length(SeqList* plist)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Length)!\n ");
        return -1;
    }

    return ptlist->length;
}

//向一个线性表list的pos位置处插入新元素node节点
int SeqList_Insert(SeqList* plist, SeqListNode* pnode, int pos)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist || NULL == pnode )
    {
        printf("SeqList is empty(SeqList_Insert)!\n ");
        return -1;
    }

    if( pos<-1 || pos >= ptlist->capacity )
    {
        printf("pos is unvalid(SeqList_Insert)!\n");
        return -2;
    }       

    int i;
    for(i=ptlist->length; i>pos; i--)
        ptlist->pnode[i] = ptlist->pnode[i-1];

    ptlist->pnode[pos] = (unsigned int*)pnode;
    ptlist->length ++;

    return 0;
}

//获取一个线性表list的pos位置处的元素
SeqListNode* SeqList_Get(SeqList* plist, int pos)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty(SeqList_Get)!\n ");
        return NULL;
    }

    if( pos<-1 || pos > ptlist->capacity )
    {
        printf("pos is unvalid(SeqList_Insert)!\n");
        return NULL;
    }       
    return ptlist->pnode[pos];
}

//删除一个线性表list的pos位的node节点元素,返回值为被删除的元素,NULL表示删除失败
SeqListNode* SeqList_Delete(SeqList* plist, int pos)
{
    TSeqList *ptlist = (TSeqList*)plist;
    if(NULL == ptlist)
    {
        printf("SeqList is empty!(SeqList_Delete)\n ");
        return NULL;
    }

    if( pos<-1 || pos > ptlist->capacity )
    {
        printf("pos is unvalid!(SeqList_Delete)\n");
        return NULL;
    }       

    SeqListNode *pnode = NULL;
    pnode = (SeqListNode*)ptlist->pnode[pos];

    int i;
    for(i=pos; i < ptlist->length; i++)
        ptlist->pnode[i] = ptlist->pnode[i+1];
    ptlist->length --;

    return pnode;
}

总结

学数据结构大家要做的不仅是上学数据结构的算法完成,更要紧的是能写出一种具备普适性的工具,站在2个更加高的安插攻略的角度去设计代码,那点对于学习数据结构来讲很关键,未有那点做支撑,学到的数据结构就只是三个空壳子,不可能灵活的行使。