数据结构(基础知识)

数据结构

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

逻辑结构

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

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

顺序存储（数组）

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

链式

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

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，无法动态存储。