网站建设公司名称,网站建设包括哪些方面选择题,杭州商标设计,宿迁装饰网站建设公司排名数据结构 相互之间存在一种或多种特定关系的数据元素的集合。 逻辑结构 集合#xff0c;所有数据在同一个集合中#xff0c;关系平等。
线性#xff0c;数据和数据之间是一对一的关系。数组就是线性表的一种。
树#xff0c; 一对多 图#xff0c;多对多 …数据结构 相互之间存在一种或多种特定关系的数据元素的集合。 逻辑结构 集合所有数据在同一个集合中关系平等。
线性数据和数据之间是一对一的关系。数组就是线性表的一种。
树 一对多 图多对多 可能用在地图里a 物理结构(在内存当中的存储关系)
顺序存储数据存放在连续的存储单位中。逻辑关系和物理关系一致 链式数据存放的存储单位是随机或任意的可以连续也可以不连续。 struct Per 数据元素 { char name;// 数据项--》给数据赋予一定的意义 int age; char phone; } struct Per list[100]; //数据对象 结构体集合 数据的类型ADT abstruct datatype 抽象数据类型 是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。 原子类型intcharfloat 结构类型sturct union 抽象数据类型 数学模型 操作。 程序 数据 算法
算法
是解决特定问题求解步骤的描述计算机中表现为指令的有限序列每条指令表示一个或多个操作 算法的特征 1输入输出特性输入时可选的输出时必须的。输出是必须有某个东西会改变 2有穷性执行的步骤会自动结束不能是死循环并且每一步是在可以接受的时间内完成。 3确定性同一个输入会得到唯一的输出。 4可行性每一个步骤都是可以实现的. 算法的设计 1正确性 语法正确 合法的输入能得到合理的结果。 对非法的输入给出满足要求的规格说明 对精心选择甚至刁难的测试都能正常运行结果正确 2可读性便于交流阅读 A理解 3健壮性输入非法数据能进行相应的处理而不是产生异常 4高效存储低效率高
算法时间效率度量
1可以忽略加法常数
O(2n 3) O(2n) 2与最高次项相乘的常数可忽略
O(2n^2) O(n^2) 3 最高次项的指数大的函数随着 n 的增长结果也会变得增长得更快
O(n^3) O(n^2) 4判断一个算法的时间效率时函数中常数和其他次要项常常可以忽略而更应该关注主项最高阶项的阶数
O(2n^2) O(n^23n1) O(n^3) O(n^2
算法时间复杂度
也就是执行这个算法所花时间的度量 n 1 O(n) O(1)
推到时间复杂度 1用常数1 取代运行时间中的所有加法常数 2在修改后的运行函数中只保留最高阶项。 3如果最高阶存在且不是1则取除这个项相乘的常数。
3.举例 int i,j; for ( i 0; i n; i){ for(j i; j n; j){ /*时间复杂度为 O(1) 的程序步骤序列 */ } } for(i0;in;i) { i5*i; } for()n { for()n } O(1)O(logn)O(N)O(nlogn)O(n^2)O(n^3)O(2^n)O(n!)O(n^n) for(int i 0 ;i100; i *5) { } 线性表
一.定义 零个或多个数据元素的有限序列 元素之间是有顺序了。如果存在多个元素第一个元素无前驱最有一个没有后继其他的元素只有一个前驱和一个后继。 当线性表元素的个数nn0定义为线性表的长度当n0时为空表。在非空的表中每个元素都有一个确定的位置如果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; 1. SeqList *CreateSeqList(int len);
功能创建一个长度为len的顺序表。实现思路 动态分配一个足够大的内存空间通常是len个元素加上一个可能的头部或尾部用于管理信息如记录当前长度。初始化顺序表的长度、容量等信息。返回指向新创建的顺序表的指针。 2. int DestroySeqList(SeqList *list);
功能销毁顺序表释放其占用的内存。实现思路 释放顺序表所占用的内存。将指针置为NULL避免野指针问题。返回成功或失败的状态码。 3. int ShowSeqList(SeqList *list);
功能显示顺序表中的所有元素。实现思路 遍历顺序表依次打印每个元素。返回成功或失败的状态码通常是成功。 4. int InsertTailSeqList(SeqList *list, DATATYPE data);
功能在顺序表的尾部插入一个元素。实现思路 检查顺序表是否已满。如果未满将新元素插入到顺序表的末尾并更新长度信息。如果已满可能需要扩容。返回成功或失败的状态码。 5. int IsFullSeqList(SeqList *list);
功能判断顺序表是否已满。实现思路 比较顺序表的当前长度与容量。如果长度等于容量返回true或1否则返回false或0。 6. int IsEmptySeqList(SeqList *list);
功能判断顺序表是否为空。实现思路 检查顺序表的当前长度是否为0。如果是返回true或1否则返回false或0。 7. int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);
功能在顺序表的指定位置pos插入一个元素。实现思路 检查位置pos是否有效即在0到长度之间。如果有效将pos及其之后的所有元素向后移动一位为新元素腾出空间。在pos位置插入新元素并更新长度信息。如果顺序表已满可能需要扩容。返回成功或失败的状态码。 8. int FindSeqList(SeqList *list, char *name);
注意这里假设顺序表存储的是某种具有名称的对象且DATATYPE可能不是直接相关的。这个函数的具体实现取决于SeqList和DATATYPE的具体定义。功能在顺序表中查找具有指定名称的元素。实现思路 遍历顺序表检查每个元素的名称是否与name匹配。如果找到匹配项返回其位置或某种表示找到的信息。如果遍历结束仍未找到返回未找到的信息。 9. int ModifySeqList(SeqList *list, char *old, DATATYPE new);
注意与FindSeqList类似这里也假设顺序表存储的是具有名称的对象。功能将顺序表中名称与old匹配的元素替换为新的值new。实现思路 遍历顺序表找到名称与old匹配的元素。如果找到将其替换为new。返回成功或失败的状态码或修改的元素数量。 10. int DeleteSeqList(SeqList *list, char *name);
功能从顺序表中删除名称与name匹配的元素。实现思路 遍历顺序表找到名称与name匹配的元素。如果找到将该元素之后的所有元素向前移动一位以覆盖被删除的元素。更新顺序表的长度信息。返回成功 11.清楚顺序表。 示例代码
sqelist.h
#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
seqlist.c
#include seqlist.h
#include string.h
#include stdlib.h
#include stdio.h
SeqList *CreateSeqList(int size)
{if(size0){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 0list-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(i0;ilen;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(i0;ilen;i){if(0strcmp(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(ind0 || indGetSizeSeqList(list)){fprintf(stderr,index is error . range0 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(pos0 ||posGetSizeSeqList(list)){fprintf(stderr,pos is error\n);return 1;}int i 0 ;for(i GetSizeSeqList(list); ipos ; 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,cant 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[i1],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;}
main.c
#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(cant 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;
}
内存泄露检测工具 sudo apt-get install valgrind valgrind ./all
char buf[1024]; 练习
1.把dict.txt 内容放到顺序表中。 提供查询功能。找到了显示意思。 如果没找到显示输入错误。 #quit 退出程序。
dict.h
#ifndef DICT_H
#define DICT_Htypedef struct
{char word[20];char meaning[1022];int ret;
}MSG;typedef struct list
{MSG *head;int tlen;int clen;
}SeqList;SeqList* CreateSeqList(int size);
int DestroySeqList(SeqList *sl);
int InsertTailSeqList(SeqList *list, MSG*data);
int IsFullSeqList(SeqList *list);
int IsEmptySeqList(SeqList *list);
int ShowSeqList(SeqList* list);
int GetSizeSeqList(SeqList* list);
int FindSeqList(SeqList *list, char *name);
MSG* GetSeqListItem(SeqList *list,int ind);#endif // DICT_Hdict.c
#include dict.h
#include stdio.h
#includestring.h
#includestdlib.hSeqList *CreateSeqList(int size)
{if(size0){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 (MSG*)malloc(sizeof(MSG)*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, MSG*msg)
{if(IsFullSeqList(list)){fprintf(stderr,InsertTailSeqlist error,seqlist is full\n);return -1;}memcpy(list-head[list-clen],msg,sizeof(MSG));list-clen;return 0;
}
int IsFullSeqList(SeqList *list)
{return list-clen list-tlen;
}int IsEmptySeqList(SeqList *list)
{return 0list-clen;
}
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(i0;ilen;i){if(0strcmp(list-head[i].word,word))
{return i;}}return -1;}
MSG *GetSeqListItem(SeqList *list, int ind)
{if(NULL list){fprintf(stderr,seqlist is NULL\n);return NULL;}if(ind0 || indGetSizeSeqList(list)){fprintf(stderr,index is error . range0 size\n);return NULL;}return list-head[ind];
}
main.c
#include stdio.h
#include string.h
#include dict.h
#include fcntl.h
#include stdlib.h
int main()
{SeqList* sl CreateSeqList(20000);MSG msg[2000];FILE *fpfopen(/home/linux/cpz/dict.txt,r);if(NULLfp){perror( );exit(1);}while(1){bzero(msg,sizeof(msg));int i0;char buf[1024]{0};if(NULLfgets(buf,sizeof(buf),fp)){break;}char *word NULL;char *mean NULL;wordstrtok(buf, );meanstrtok(NULL,\r);strcpy(msg[i].word,word);strcpy(msg[i].meaning,mean);InsertTailSeqList(sl,msg[i]);}while(1){char find_word[50]{0};fgets(find_word,sizeof(find_word),stdin);find_word[strlen(find_word)-1]\0;if(0strcmp(find_word,#quilt)){break;}int ret FindSeqList(sl,find_word);if(-1 ret){printf(cant find word ,%s\n,find_word);}else{MSG* tmp GetSeqListItem(sl,ret) ;printf(word:%s mean:%s\n,tmp-word,tmp-meaning);}
}printf(Hello World!\n);return 0;
}线性表顺序存储的优点缺点 优点 1无需为表中的逻辑关系增加额外的存储空间 2可以快速随机访问元素O(1) 缺点 1插入删除元素需要移动元素o(n) 2无法动态存储。 优点
随机访问顺序表支持随机访问即可以通过下标快速访问表中的任意元素访问时间复杂度为O(1)。存储密度高顺序表在物理存储上是连续的因此它的存储密度高不会出现为了存储数据元素而额外申请大量空间的情况相较于链表等数据结构。 空间利用率高在顺序表扩容之前其空间是固定的这有助于减少空间碎片提高空间利用率。 易于实现顺序表的基本操作如插入、删除、查找等相对简单易于理解和实现。
缺点
插入和删除操作成本高当在顺序表中进行插入或删除操作时可能需要移动大量的元素以保持顺序表的连续性特别是在表的前端或中间位置进行操作时时间复杂度较高最坏情况下为O(n)。空间分配问题顺序表在初始化时需要预先分配一定大小的存储空间如果预估不准确可能会导致空间浪费分配过多或溢出分配不足。虽然可以通过动态扩容来解决溢出问题但每次扩容都需要重新分配内存并复制数据增加了时间成本。扩容问题当顺序表需要扩容时虽然可以动态申请更大的内存空间但这个过程涉及到旧数据的复制和新空间的申请可能会影响到程序的性能。表的大小固定虽然可以通过动态扩容来解决表大小固定的问题但在某些场景下如果需要存储的数据量非常大而内存空间有限那么顺序表可能就不是一个很好的选择。
