当前位置: 首页> 游戏> 网游 > 数据结构(基础知识)

数据结构(基础知识)

时间:2025/7/11 23:47:39来源:https://blog.csdn.net/kxy102852/article/details/140600137 浏览次数:0次

数据结构


  相互之间存在一种或多种特定关系的数据元素的集合。
(解决海量的数据,研究数据与数据的关系)


逻辑结构


        集合,所有数据在同一个集合中,关系平等。
        线性,数据和数据之间是一对一的关系
        , 一对多
        ,多对多
        

物理结构(在内存当中的存储关系)


顺序存储   (数组)    

数据存放在连续的存储单位中。逻辑关系和物理关系一致


链式      

数据存放的存储单位是随机或任意的可以连续也可以不连续


 struct Per 数据元素
    {
        char name ; // 数据项(可以输入输出)
        int age ;
        char phone ;
    }             
    struct Per list[100] ;  // 数据对象


        
    数据的类型(ADT    abstruct datatype )


        是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
        原子类型,int,char,float
        结构类型,sturct, union,

        抽象数据类型, 数学模型 + 操作。
        
        程序 =  数据 + 算法


    
算法


    是解决特定问题求解步骤的描述,计算机中表现为指令的有限序列,每条指令表示一个或多个操作。 
 

 算法的特征


    1,输入,输出特性,输入时可选的,输出时必须的。
    2,有穷性,执行的步骤会自动结束,不能是死循环,并且每一步是在可以接受的时间内完成。
    3,确定性,同一个输入,会得到唯一的输出。
    4,可行性,每一个步骤都是可以实现的 


    
    算法设计


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



    算法时间复杂度



    也就是执行这个算法所花时间的度量
    n  1  = O(n)   O(1)
    推到时间复杂度
        1,用常数1 取代运行时间中的所有加法常数
        2,在修改后的运行函数中,只保留最高阶项。
        3,如果最高阶存在且不是1,则取除这个项相乘的常数。
        
 

线性表


    零个或多个数据元素的有限序列
    元素之间是有顺序了。如果存在多个元素,第一个元素无前驱,最有一个没有后继,其他的元素只有一个前驱和一个后继。
    当线性表元素的个数n(n>=0)定义为线性表的长度,当n=0时,为空表。在非空的表中每个元素都有一个确定的位置,如果a1是第一个元素,那么an就是第n个元素。



线性表的常规操作  ADT

typedef struct    person {
    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 len) ;(创建数据表)
int DestroySeqList(SeqList *list) ;(释放数据表)
int ShowSeqList(SeqList *list) ;(显示)
int InsertTailSeqList(SeqList *list, DATATYPE data);(插入Tail尾差,head头插)
int IsFullSeqList(SeqList *list);(是否满了)
int IsEmptySeqList(SeqList *list);(是否空)
int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);
int FindSeqList(SeqList *list, char *name);(查找)
int ModifySeqList(SeqList *list, char *old, DATATYPE new);(修改)
int DeleteSeqList(SeqList *list, char *name);(清理干净)
int ClearSeqList(SeqList *list);(清空内容)
 

  1 实例 样本

#ifndef SEQLIST_H
#define SEQLIST_Htypedef 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 <stdio.h>
#include "seqlist.h"
int main()
{SeqList* sl = CreateSeqList(10);DATATYPE data[5]={{"zhangsan",'m',20,70},{"lisi",'f',21,60},{"wangmazi",'m',25,80},{"liubei",'f',30,85},{"caocao",'f',40,90},};InsertTailSeqList(sl,&data[0]);InsertTailSeqList(sl,&data[1]);InsertTailSeqList(sl,&data[2]);ShowSeqList(sl);//    char find_name[50]="li1si";//    int ret = FindSeqList(sl,find_name);//    if(-1 == ret)//    {//        printf("can't find person ,%s\n",find_name);//    }//    else//    {//       DATATYPE* tmp   =  GetSeqListItem(sl,ret) ;//       printf("name:%s score:%d\n",tmp->name,tmp->score);//    }printf("----------------pos------------------\n");InsertPosSeqList(sl,&data[3],3);ShowSeqList(sl);printf("----------------modify------------------\n");ModifySeqList(sl,"li1si",&data[4]);ShowSeqList(sl);printf("----------------del------------------\n");DeleteSeqList(sl,"lisi");ShowSeqList(sl);DestroySeqList(sl);printf("Hello World!\n");return 0;
}

#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)//先销毁head在销毁slfree(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));//w尾插入将数据给到数组第head[clen]上;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;}

2 实例 实现字典模式,终端打印的单词进行查找 

#include <stdio.h>
#include "seqlist.h"
#include <string.h>
#include <stdlib.h>
int main()
{SeqList* sl = CreateSeqList(20000);FILE*fp = fopen("/home/linux/dict.txt","r");if(NULL == fp){perror("fopen");DestroySeqList(sl);exit(1);}DATATYPE data;while(1){bzero(&data,sizeof(data));char buf[1024]={0};if(fgets(buf,sizeof(buf),fp)){char *word=NULL;char * mean = NULL;word =strtok(buf," ");mean=strtok(NULL,"\r");strcpy(data.word , word);strcpy(data.mean , mean);InsertTailSeqList(sl,&data);}else{break;}}while(1){printf("input want word:");char want_word[64]={0};fgets(want_word,sizeof(want_word),stdin);want_word[strlen(want_word)-1]='\0';if(0==strcmp(want_word,"#quit")){break;}int ret = FindSeqList(sl,want_word);if(-1 == ret){printf("cant find word %s\n",want_word);}else{DATATYPE* tmp = GetSeqListItem(sl,ret);printf("%s:%s\n",tmp->word,tmp->mean);}}DestroySeqList(sl);printf("Hello World!\n");return 0;
}
#ifndef SEQLIST_H
#define SEQLIST_Htypedef struct{char word[64];char mean[256];}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);
#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);}bzero(sl->head,sizeof(DATATYPE)*size);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(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)
{return list->clen == list->tlen;
}int IsEmptySeqList(SeqList *list)
{return 0==list->clen;
}//int ShowSeqList(SeqList *list)
//{
//    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)
{return list->clen;
}int FindSeqList(SeqList *list, char *word)
{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].word,word)){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];
}

内存泄露检测工具
sudo apt-get install valgrind
valgrind ./all

char buf[1024];

线性表顺序存储的优点,缺点
优点
    1,无需为表中的逻辑关系增加额外的存储空间
    2,可以快速随机访问元素O(1)
缺点
    1,插入,删除元素需要移动元素o(n)
    2,无法动态存储。
 

      

关键字:数据结构(基础知识)

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: