数据结构（1）（顺序表）

作者：黑客灵魂 | 2024-07-27 23:12:07

踩

数据结构（1）（顺序表）

数据结构

数据结构
相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构
       集合，所有数据在同一个集合中，关系平等。（数组中的每一个int）
       线性，数据和数据之间是一对一的关系（队列，链表，数组（线性表的一种体现））
       树，一对多（高效）
       图，多对多

物理结构(在内存当中的存储关系)
顺序存储，数据存放在连续的存储单位中。逻辑关系和物理关系一致
链式，数据存放的存储单位是随机或任意的，可以连续也可以不连续。

struct Per 数据元素
   {
       char name;//数据项（变量）
       int age;
       char phone;
   }

   struct Per list[100]; //数据对象（数据元素的集合）

数据的类型，ADT abstract datatype（抽象数据类型）
       是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
       原子类型，int，char，float
       结构类型，sturct， union，

       抽象数据类型，数学模型 + 操作。（相当于c语言.h的内容，=变量+函数）

       程序 = 数据 + 算法

算法：
是解决特定问题求解步骤的描述，计算机中表现为指令的有限序列，每条指令

算法的特征，
   1，输入，输出特性，输入是可选的，输出是必须的。（输出-->内存上必须要发生变化）
   2，有穷性，执行的步骤会自动结束，不能是死循环，并且每一步是在可以接受的时间内完成。
   3，确定性，同一个输入，会得到唯一的输出。
   4，可行性，每一个步骤都是可以实现的。

算法的设计，
   1，正确性，
       语法正确
       合法的输入能得到合理的结果。
       对非法的输入，给出满足要求的规格说明
       对精心选择，甚至刁难的测试都能正常运行，结果正确
   2，可读性，便于交流，阅读，理解
   3，健壮性，输入非法数据，能进行相应的处理，而不是产生异常
   4，高效，存储低，效率高

时间复杂度

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。也就是执行这个算法所花时间的度量。

（大O阶方法）
       1，用常数1 取代运行时间中的所有加法常数（不论输入数据的大小如何变化，
                                               执行时间都是一个常数）
       2，在修改后的运行函数中，只保留最高阶项。（An²，Bn³）
       3，如果最高阶存在且不是1，则忽略这个项相乘的常数。（-->n²，n³）

常见的时间复杂度：

O(1) - 常数时间复杂度：算法的执行时间不随输入数据规模变化，如数组访问某个元素。
O(log n) - 对数时间复杂度：二分查找就是一个典型的例子，每一步都将问题规模减半。
O(n) - 线性时间复杂度：遍历数组或列表中的每个元素。
O(n log n) - 线性对数时间复杂度：快速排序、归并排序等高效排序算法。（n体现在拿数的过程需要n次，logn表现在把数放在固定位置上）
O(n^2) - 平方时间复杂度：冒泡排序、选择排序，插入排序等简单排序算法。
O(n^3)、O(2^n)、O(n!) - 随着问题规模的增长，所需时间急剧增加，分别对应立方、指数、阶乘复杂度。

空间复杂度

空间复杂度是衡量算法在运行过程中所需存储空间的度量。

常见空间复杂度：

O(1)：算法使用的额外空间不随输入数据规模改变，如原地排序算法。

O(n)：额外空间正比于输入数据规模，如某些动态规划问题中需要的数组。

O(n^2)：随着输入规模增大，所需空间平方增长，例如某些矩阵运算。数组：整型数组arr的长度为5，因此其空间复杂度为O(5)，即O(n

    int arr[5] = {1, 2, 3, 4, 5};

链表：定义了一个包含一个节点的单向链表，其空间复杂度为O(1)。


struct Node {
    int data;
    struct Node* next;
};

栈：随着MAX_SIZE线性增长，其空间复杂度为O(n)


#define MAX_SIZE 100
struct Stack {
    int data[MAX_SIZE];
    int top;
};

线性表：

顺序表是物理地址连续的存储单元依次存储数据的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改。
当线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，为空表。
在非空的表中每个元素都有一个确定的位置，如果a1是第一个元素，那么an就是第n个元素。

顺序表基本操作：


#ifndef SEQLIST_H
#define SEQLIST_H
 
 
typedef struct{
    char name[32];
    char sex;
    int age;
    int score;
}DATATYPE;
//typedef int Datatype;
typedef struct list {
    DATATYPE *head; //开辟的空间首地址
    int tlen;  //总长度
    int clen;  //当前长度
}SeqList;
 
SeqList* CreateSeqList(int size); //创建
int DestroySeqList(SeqList*sl);  /销毁
int InsertTailSeqList(SeqList *list, DATATYPE *data); //尾插
int IsFullSeqList(SeqList *list);  //顺序表是否满
int IsEmptySeqList(SeqList *list); //顺序表是否为空
int ShowSeqList(SeqList* list);  //打印全部节点数据
int GetSizeSeqList(SeqList* list);  //获取当前长度
int FindSeqList(SeqList *list, char *name);  //根据名字获取节点下标
DATATYPE* GetSeqListItem(SeqList *list,int ind);  //根据下标查询节点
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos);  //指定位置插入
int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata); //修改及诶带你
int DeleteSeqList(SeqList *list, char *name);  //删除顺序表
int ClearSeqList(SeqList *list);  //删除该表所有元素
#endif // SEQLIST_H

操作实现：


#include "seqlist.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
SeqList *CreateSeqList(int size)
{
    if(size<=0)
    {
        fprintf(stderr,"size is error,range >1");
        return NULL;
    }
    SeqList* sl = ( SeqList*)malloc(sizeof(SeqList));
    if(NULL == sl)
    {
        perror("CreateSeqList malloc");
        exit(1);
    }
 
    sl->head = (DATATYPE*)malloc(sizeof(DATATYPE)*size);
    if(NULL == sl->head)
    {
        perror("CreateSeqList malloc");
        exit(1);
    }
 
    sl->tlen = size;
    sl->clen = 0;
    return sl;
}
 
 
int DestroySeqList(SeqList *sl)
{
    if(NULL == sl)
    {
        fprintf(stderr,"SeqList point not NULL");
        return 1;
    }
    if(sl->head)
        free(sl->head);
    free(sl);
    return 0;
}
 
int InsertTailSeqList(SeqList *list, DATATYPE *data)
{
    if(NULL == list)
    {
        fprintf(stderr,"InsertTailSeqList error,list is null\n");
        return -1;
    }
 
    if(IsFullSeqList(list))
    {
        fprintf(stderr,"InsertTailSeqList error ,seqlist is full\n");
        return 1;
    }
    //list->head[list->clen] = *data;
    memcpy(&list->head[list->clen] , data,sizeof(DATATYPE));
    list->clen++;
    return 0;
}
 
int IsFullSeqList(SeqList *list)
{
    if(NULL == list)
    {
        fprintf(stderr,"IsFullSeqList error,list is null\n");
        return -1;
    }
    return list->clen == list->tlen;
}
 
int IsEmptySeqList(SeqList *list)
{
    return 0==list->clen;
}
 
int ShowSeqList(SeqList *list)
{
    if(NULL == list)
    {
        fprintf(stderr,"list error,list is null\n");
        return -1;
    }
    int i = 0 ;
    int len = GetSizeSeqList(list);
    for(i=0;i<len;i++)
    {
        printf("name:%s sex:%c age:%d score:%d\n",list->head[i].name,list->head[i].sex,list->head[i].age
               ,list->head[i].score);
    }
    return 0;
}
 
int GetSizeSeqList(SeqList *list)
{
    if(NULL == list)
    {
        fprintf(stderr,"GetSizeSeqList error,list is null\n");
        return -1;
    }
    return list->clen;
}
 
int FindSeqList(SeqList *list, char *name)
{
    if(NULL == list)
    {
        fprintf(stderr,"FindSeqList error,list is null\n");
        return 1;
    }
    if(IsEmptySeqList(list))
    {
        fprintf(stderr,"FindSeqList error,seqlist is empty\n");
        return -1;
    }
    int len = GetSizeSeqList(list);
    int i = 0 ;
    for(i=0;i<len;i++)
    {
        if(0==strcmp(list->head[i].name,name))
        {
 
            return i;
        }
    }
    return -1;
 
}
 
DATATYPE *GetSeqListItem(SeqList *list, int ind)
{
    if(NULL == list)
    {
        fprintf(stderr,"seqlist is NULL\n");
        return NULL;
    }
    if(ind<0 || ind>GetSizeSeqList(list))
    {
        fprintf(stderr,"index is error . range>0  && <size\n");
        return NULL;
 
    }
    return &list->head[ind];
}
 
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{
 
    if(NULL == list)
    {
        fprintf(stderr,"list is null\n");
        return 1;
    }
    if(IsFullSeqList(list))
    {
        fprintf(stderr,"list is full\n");
        return 1;
    }
    if(pos<0 ||pos>GetSizeSeqList(list))
    {
        fprintf(stderr,"pos is error\n");
        return 1;
    }
 
    int i = 0 ;
 
    for(i =GetSizeSeqList(list); i>=pos ; i-- )
    {
        memcpy(&list->head[i],&list->head[i-1],sizeof(DATATYPE));
 
    }
    memcpy(&list->head[pos],data,sizeof(DATATYPE));
    list->clen++;
    return 0;
}
 
int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata)
{
    if(NULL == list)
    {
        fprintf(stderr,"ModifySeqList error,list is null\n");
        return 1;
    }
    int ret = FindSeqList(list,old);
    if(-1 == ret)
    {
        fprintf(stderr,"modify error,can't find\n");
        return 1;
    }
    DATATYPE* tmp = GetSeqListItem(list,ret);
    memcpy(tmp,newdata,sizeof(DATATYPE));
    return 0;
}
 
int DeleteSeqList(SeqList *list, char *name)
{
    if(NULL == list)
    {
        fprintf(stderr,"DeleteSeqList error,list is null\n");
        return 1;
    }
    int ret = FindSeqList(list,name);
    if(-1 == ret)
    {
        return 1;
    }
    else
    {
        int i = 0 ;
        for(i =ret; i <GetSizeSeqList(list)-1 ; i++)
        {
            memcpy(&list->head[i] ,&list->head[i+1],sizeof(DATATYPE));
        }
    }
 
    list->clen--;
    return 0 ;
}
 
int CleanSeqList(SeqList *list)
{
    if(NULL == list)
    {
        fprintf(stderr,"CleanSeqList error,list is null\n");
        return 1;
    }
    list->clen = 0 ;
    return 0;
 
}

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】