数据结构
相互之间存在一种或多种特定关系的数据元素的集合。
(解决海量的数据,研究数据与数据的关系)
逻辑结构
集合,所有数据在同一个集合中,关系平等。
线性,数据和数据之间是一对一的关系
树, 一对多
图,多对多
物理结构(在内存当中的存储关系)
顺序存储 (数组)
数据存放在连续的存储单位中。逻辑关系和物理关系一致
链式
数据存放的存储单位是随机或任意的,可以连续也可以不连续。
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,无法动态存储。