建设一个企业网站需要多少钱,网页设计图片排版怎么设置,浏览器禁止网站怎么做,东莞网络营销班数据结构指的是数据元素及数据元素之间的相互关系#xff0c;包含下面三方面的内容#xff1a; 其中#xff0c;线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系#xff0c;即除了第一个和最后一个数据元素之外#xff0c;其… 数据结构指的是数据元素及数据元素之间的相互关系包含下面三方面的内容 其中线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系即除了第一个和最后一个数据元素之外其它数据元素都是首尾相接的。线性表的逻辑结构简单便于实现和操作。因此线性表这种数据结构在实际应用中是广泛采用的一种数据结构。 线性表是一个线性结构它是一个含有n≥0个结点的有限序列对于其中的结点有且仅有一个开始结点没有前驱但有一个后继结点有且仅有一个终端结点没有后继但有一个前驱结点其它的结点都有且仅有一个前驱和一个后继结点。 特征 1集合中必存在唯一的一个“第一元素” 2集合中必存在唯一的一个 “最后元素” 3除最后一个元素之外均有 唯一的后继(后件) 4除第一个元素之外均有 唯一的前驱(前件) 线性表作为一种基本的数据结构类型在计算机存储器的映像或表示一般有两种形式 1、顺序映像---即我们常用的数组 2、链式映像---即我们常用的链表 今天我们先来学习顺序存储结构 一、顺序存储结构的表示 1、顺序存储结构的特点 1逻辑上相邻的元素A(i) A(i1)其存储位置也是相邻的 2对数据元素A(i)的存取为随机存取或地址存取。 3存储密度高。存储密度D数据结构中的元素所占存储空间/(整个数据结构所占空间) 2、顺序存储结构的不足 对表的插入和删除等运算的时间复杂度较差。 3、顺序存储结构的表示 在C语言中一维数组的元素也是存放于一片连续的存储空间中故可借助于C语言中一维数组类型来描述线性表的存储结构即 [cpp] view plaincopy #define N 100 typedef int data_t;//这样定义的目的是为了代码便于维护如果下次表中数据类型为char修改比较方便 typedef struct { data_t data[N];//表的存储空间 int last;//当前表尾指针对我们对数据的定位起到很大的作用 }sqlist_t,*sqlink_t;//顺序表类型 指针 L 指向一个顺序表,我们的数据{a0,a1,a2........ last}; [cpp] view plaincopy sqlink_t L; L (sqlink_t *)malloc(sizeof(sqlink_t)); 这里我们定义的 int last 可以表示{ } 、{ a0 }、{a0,a1}、{a0,a1......a99}; ai可以表示为 L-data[i] (0iL-last)一般情况下0 L-last N如果是空表{ }此时L-last -1; 下面我们通过一个实例来看线性表基本算法的相关算法如何使用 seqlist.h [cpp] view plaincopy #ifndef _SEQ_LIST_H_ #define _SEQ_LIST_H_ #include datatype.h #define MAX 100 typedef struct { data_t data[MAX]; int last; /* pointer to the position * in the array data where * stores the last element of * the list */ } seqlist_t; /* * create a list and init it as empty * Input : void * Output: void * Return: new list, NULL when failed */ seqlist_t *CreateEmptySqlist(); /* * destroy a list * Input : the list to be destroied. * Output: void * Return: void */ void DestroySqlist(seqlist_t *list); /* * clear the list and reset it as empty * Input : the list to be cleared. * Output: void * Return: void */ void ClearSqlist(seqlist_t *list); /* * judge if the list is empty * Input: the list to be tested. * Output: void * Return: * 1: list is empty * 0: not * -1: error, e.g. the list is invalid */ int EmptySqlist(seqlist_t *list); /* * judge if the list is full * Input : the list to be tested. * Output: void * Return: * 1 : list is full * 0 : not * -1: error */ int FullSqlist(seqlist_t *list); /* * get length of the list * Input : the list to be tested. * Output: void * Return: * 0: length of the list; * -1 : means error */ int LengthSqlist(seqlist_t *list); /* * get data of element at specified position * Input : * list : the list to be operated. * at : the position where to get the element at, * position index starts from zero. * Output: * x : the data value returned * Return: * 0 : success; * -1: error, e.g. list is invalid; at extends * the range of the list */ int GetSqlist(seqlist_t *list, int at, data_t *x); /* * set/update data of element at specified position * Input : * list : the list to be operated. * at : the position at where to set the element, * position index starts from zero * x : the new data value * Output: void * Return: * 0 : success; * -1: error, e.g. list is invalid; at extends the * range of the list */ int SetSqlist(seqlist_t *list, int at, data_t x); /* * Insert element at the specified position. If the at exceed the * upper limit of the list, append the data at the end of the list. * e.g. insert a new data into a {}. * Input : * list : the list to be operated. * at : the position at which to insert the new element, * position index starts from zero. * x : the data to be inserted * Output: void * Return: * 0 : success; * 0: error */ int InsertSqlist(seqlist_t *list, int at, data_t x); /* * delete the element by the position * Input : * list : the list to be operated. * at : the position at which to delete the element, * position index starts from zero * Output : void * Return : * 0 : success; * !0 : error */ int DeleteSqlist(seqlist_t *list, int at); #endif /* _SEQ_LIST_H_ */ seqlist.c [cpp] view plaincopy #include stdio.h #include stdlib.h #include seqlist.h seqlist_t *CreateEmptySqlist() { seqlist_t *list; list (seqlist_t *)malloc(sizeof(seqlist_t)); if(list ! NULL) { list-last -1;//list-last初始化空表中list-last -1; } return list; } void DestroySqlist(seqlist_t *list) { if (list NULL) return ; free(list); return; } void ClearSqlist(seqlist_t *list) { if (list NULL) return ; list-last -1;//清空线性表 } int EmptySqlist(seqlist_t *list) { if (list NULL) return -1; if(list-last -1)//空表的标志 return 1; else return 0; } int FullSqlist(seqlist_t *list) { if (list NULL) return -1; if (MAX - 1 list-last) return 1; else return 0; } int LengthSqlist(seqlist_t *list) { if (list NULL) return -1; else return (list-last 1); } int GetSqlist(seqlist_t *list, int at, data_t *x) //data_t *x为出参 { if(list NULL || at 0 || at list-last) return -1; *x list-data[at]; return 0; } int SetSqlist(seqlist_t *list, int at, data_t x)//data_t x为入参 { if(list NULL || at 0 || (at list-last)) return -1; list-data[at] x; return 0; } int InsertSqlist(seqlist_t *list, int at, data_t x) { int j; if(list NULL || at 0 || FullSqlist(list)) return -1; if(at list-last)//此情况比较特殊如表中长度是50却要插在60前面我们这里将其插在50后面即at list-last 1 { at list-last 1;//若是空表{}list-last为-1此时将其放在第0位 } else { for(j list-last; j at; j--) { list-data[j1] list-data[j]; } } list-data[at] x; list-last;//list-last要1 return 0; } int DeleteSqlist(seqlist_t *list, int at) { int i; if(list NULL || at 0 || (at list-last)) return -1; for(i at 1; i list-last;i) list-data[i-1] list-data[i]; list-last--; return 0; } main.c [cpp] view plaincopy #include stdio.h #include stdlib.h #include seqlist.h #include datatype.h void iterate_list(seqlist_t *list) { int i; printf(list.last %d, list {, list-last); for (i -1; i list-last;) { printf(%d,, list-data[i]); } if (LengthSqlist(list) 0) printf(\b}\n); else printf(}\n); } int main(int argc, const char *argv[]) { int i; int length; data_t a[10] {2,4,6,8,10,12,14,16,18,20}; data_t x; seqlist_t *list; list CreateEmptySqlist(); if (list NULL) return -1; for(i 0; i 10;i) { if((InsertSqlist(list,i,a[i])) 0) break; } iterate_list(list); length LengthSqlist(list); printf(The length of the list is %d\n,length); GetSqlist(list,4,x); printf(The NO.4 data of the list is %d\n,x); SetSqlist(list,4,5); GetSqlist(list,4,x); printf(After updataing! The NO.4 data of the list is %d\n,x); printf(Delete data[4]!\n); DeleteSqlist(list,4); GetSqlist(list,4,x); printf(Now data[4] %d\n,x); printf(Now the legth of the list is %d\n,LengthSqlist(list)); ClearSqlist(list); if(EmptySqlist(list)) printf(The list is empty!\n); printf(Now the legth of the list is %d\n,LengthSqlist(list)); DestroySqlist(list); printf(The list is destroyed!\n); return 0; } makefile: [cpp] view plaincopy OBJS seqlist.o main.o CFLAGS -c -g -Wall CC gcc Test:$(OBJS) $(CC) -o Test -g $(OBJS) main.o:main.c seqlist.h datatype.h $(CC) $(CFLAGS) main.c seqlist.o:seqlist.c seqlist.h datatype.h $(CC) $(CFLAGS) seqlist.c clean: rm -rf Test *.o 执行结果如下 [cpp] view plaincopy fsubuntu:~/qiang/list$ make gcc -c -g -Wall seqlist.c gcc -c -g -Wall main.c gcc -o Test -g seqlist.o main.o fsubuntu:~/qiang/list$ ./Test list.last 9, list {2,4,6,8,10,12,14,16,18,20} The length of the list is 10 The NO.4 data of the list is 10 After updataing! The NO.4 data of the list is 5 Delete data[4]! Now data[4] 12 Now the legth of the list is 9 The list is empty! Now the legth of the list is 0 The list is destroyed!
