《数据结构》复习重点.docx

数据结构复习重点第一章绪论要求、目标：了解数据逻辑结构的分类；掌握算法的特性及估算算法时间复杂度的方法；熟悉数据结构的基本基本概念和术语。一、基本概念和术语.数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象 以及它们之间的关系和操作等的学科。1 .数据：是对客观事物的符号表示，即所有能输入到计算机中并被计算机程序处理的符号的总称。2 .数据项：数据的不可分割的最小单位。3 .数据元素(数据结点)：数据的基本单位，在程序中作为一个整体处理， 由假设干数据项组成。4 .数据对象：性质相同的数据元素的集合，是数据的一个子集如：四季对象是集合：春，夏，秋，冬自然数对象是集合：0, 1, 2, 3,字母字符对象是集合： A B,Z 5 .数据结构的分类：线性结构和非线性结构。6 .数据结构的形式化定义：数据结构是一个二元组，可定义为Data_Structure=(D,S)其中：D是数据元素的有限集合，S是D上关系的有限集合.序偶：两个元素间的前后关系。a,ba是b的前驱结点，b是a的后继 结点例：四季的描述 B= (D, R)D=春，夏，秋，冬R= 春，夏,夏，秋,秋，冬7 .物理结构(存储结构或映像)：数据结构在计算机中的表示。8 .存储结构的分类：while(p-next&jnext; j+;)if(! (p-next) | |j 1-1 )retum 1;q=p-next;*e=q-data;p-next=q-next;free(q);return 0;15 .查找与给定值相同的第一个结点NODE *locatenode(NODE *h, int key) NODE *p=h-next;while(p&p-data!=key) p=p-next;return p;16 .合并两个递减有序的链表，合并后仍为递减有序NODE *merge_L(NODE *ha, NODE *hb) NODE *p=ha-next, *q=hb-next, *r, *s; s=(NODE *)malloc(sizeof(NODE);s-next=NULL;while(p!=NULL&q! =NULL) if(p-dataq-data)r-next=p; r=p; p=p-next; elser-next=q; r=q; q=q-next; if(p二二NULL) r-next=q;else r-next=p;return s;（二）循环链表return (0);编译：gcc -oxmlCreator xmlCreator.cpp -I /home/usr/libxml2/xmlinst/includ e/libxml2/-L /home/usr/libxml2/xmlinst/lib/ -lxml2(绿色文字为libxml2安装路径)7后接头文件目录-L后接lib库目录2、解析XML文档解析文档时仅仅需要文件名并只调用一个函数，并有错误检查，常 用的相关函数有xmlParseFileO, xmlParseDoc (),获取文档指针后， 就可以使用xmlDocGetRootElement ()来获取根元素节点指针，利用 该指针就可以在DOM树里漫游了，结束后要调用xmlFreeDoc()释放。例如2：xmlDocPtr doc;定义解析文档指针xmlNodePtr cur;定义结点指针(你需要它为了在各个结点间移动)xmlChar *key;doc = xmlReadFile(url, MY_ENCODING, 256); 解析文件/*检查解析文档是否成功，如果不成功，libxml将指一个注册的 错误并停止。一个常见错误是不适当的编码。XML标准文档除了用 UTF-8或UTFT6外还可用其它编码保存。如果文档是这样，libxml 将自动地为你转换到UTF-8o更多关于XML编码信息包含在XML标准 中。*/if (doc = NULL ) fprintf (stderr, Document not parsed successfully. n)； return;)cur = xmlDocGetRootElement (doc); 确定文档根元素/*检查确认当前文档中包含内容*/if (cur = NULL) fprintf (stderr, empty documentnz/);xmlFreeDoc (doc);return;/*在这个例子中，我们需要确认文档是正确的类型。“root是在这个例如中使用文档的根类型。*/if (xmlStrcmp(cur-name, (const xmlChar *) root) fprintf (stderr, document of the wrong type, root node != root);xmlFreeDoc(doc);return;)cur = cur-xmlChiIdrenNode;while(cur!=NULL) if (! xmlStrcmp (cur-name, (const xmlChar *) “keyword) key = xmlNodeListGetString(doc, cur-xmlChiIdrenNode, 1); printf (keyword: %sn，key);xmlFree(key);)cur = cur-next;xmlFreeDoc(doc);3、修改XML元素及属性等信息要修改XML文档里的元素及属性等信息，先需要解析XML文档，获得一个节点指针(xmlNodePtr node),利用该节点指针漫游DOM树,就 可以在XML文档中获取，修改，添加相关信息。例如3：得到一个节点的内容：xmlChar lvalue = xmlNodeGetContent(node);返回值value应该使用xmlFree(value)释放内存得到一个节点的某属性值：xmlChar lvalue = xmlGetProp(node, (const xmlChar*)prop);返回值需要xmlFree (value)释放内存设置一个节点的内容：xmlNodeSetContent(node, (const xmlChar *)test)；设置一个节点的某属性值：xmlSetProp(node, (const xmlChar *)propl， (const xmlChar *)vl);添加一个节点元素：xmlNewTextChiId (node, NULL, (const xmlChar *)“keyword”, (const xmlChar *)test Element);添加一个节点属性：xmlNewProp(node, (const xmlChar *)propl， (const xmlChar *)test Prop);4、查找XML节点有时候对一个XML文档我们可能只关心其中某一个或某几个特定 的Element的值或其属性，如果漫游D0M树将是很痛苦也很无聊的事, 利用XPath可以非常方便地得到你想的Elemento下面是一个自定义 函数：例如4：xmlXPathObjectPtr get_nodeset (xmlDocPtr doc, const xmlChar*xpath) xmlXPathContextPtr context;xmlXPathObjectPtr result;context = xmlXPathNewContext(doc);if (context = NULL) printf (context is NULLn)；return NULL;)result = xmlXPathEvalExpression(xpath, context);xmlXPathFreeContext(context);if (result = NULL) printf (z/xmlXPathEvalExpression return NULLn);return NULL;)if (xmlXPathNodeSetlsEmpty(result-nodesetval) , xmlXPathFreeObject(result);printf (/znodeset is emptyn)；return NULL;return result;在doc指向的XML文档中查询满足xpath表达式条件的节点，返回满足这一条件的节点集合查询条件xpath的写法参见xpath相关资 料。在查询完毕获取结果集后，就可以通过返回的xmlXPathObjectPtr结构访问该节点：例如5：xmlChar *xpath = (/root/node/key=keyword)；xmlXPathObjectPtr app_result = get_nodeset(doc, xpath);if (app_result = NULL) printf (/zapp_result is NULLn)；return;int i=0;xmlChar lvalue;if (appresult) xmlNodeSetPtr nodeset = app_result-nodesetval;for (i=0; i nodeNr; i+) cur = nodeset-nodeTabi;cur = cur-xmlChildrenNode;while (cur!=NULL) value = xmlGetProp (cur, (const xmlChar *)key)；if (value != NULL) printf (value: %snnz/, d_ConvertCharset (utf8,GBK, (char *)value);xmlFree(value);value = xmlNodeGetContent(cur);if (value != NULL) printf (value: %snn，d_ConvertCharset(utf8,GBK, (char *)value);xmlFree(value);xmlXPathFreeObject (app_result);通过get_nodeset ()返回的结果集，我们可以获取该节点的元素及属性，也可以修改该节点的值。例如中在获取值打印的时候用到d_ConvertCharset ()函数来改变编码格式为GBK,以方便正确读取可能的中文字符。5、编码问题由于Libxml 一般以UTF-8格式保存和操纵数据，如果你的程序使 用其它的数据格式，比方中文字符(GB2312, GBK编码)，就必须使用 Libxml函数转换到UTF-8O如果你想你的程序以除UTF-8外的其它编 码方式输出也必须做转换。下面的例如程序提供几个函数来实现对数据编码格式的转 换，其中有的要用到Libiconv,因此为了确保他们能正常工作，先 检查以下系统中是否已经安装libiconv库。例如6：xmlChar *Convertlnput (const char *in, const char encoding) (unsigned char *out;int ret;int size;int out_size;int temp;xmlCharEncodingHandlerPtr handler;if (in = 0)return 0;handler = xmlFindCharEncodingHandler(encoding);if (!handler) printf (，zConvertInput: no encoding handler found for %sn， encoding ? encoding : );return 0;)size = (int) strlen(in) + 1;out_size = size * 2 - 1;out = (unsigned char *) xmlMalloc(size_t) out_size);if (out != 0) temp = size - 1;ret = handler-input (out, &out_size, (const unsigned char *) in, &temp);if (ret 0) | (temp - size + 1) if (ret next=h时为空2）不带头结点：当h=NULL时为空3 .删除第一个结点带头结点：h-next=h-next-next2）不带头结点：h=h-next.建立循环链表将尾结点 r-next=NULL;改为 r-next=h;（三）双向链表.特点：两个指针域，可用于表示树型结构，一个指向前驱，一个指向后继1 .结点类型：typedef struct dnodeint data;struct dnode *prior, *next; DNODE;.结构：h.建立双链表（以0结束）DNODE *creatd()xmlFree(out);out = 0; else out = (unsigned char *) xmlRealloc (out, out_size + 1);outout_size = 0; /*null terminating out */) else (printf (Z/Convertlnput: no memn)；return out;例如7 ：char * Convert ( char *encFrom, char *encTo, const char * in)static char bufin1024, bufout1024, *sin, *sout;int mode, lenin, lenout, ret, nline;iconv_t c_pt;if (c_pt = iconv_open(encTo, encFrom) = (iconv_t)-1)printf (z/iconv_open false: %s = %sn，encFrom, encTo); return NULL;)iconv(c_pt, NULL, NULL, NULL, NULL);lenin = strlen (in) + 1;lenout = 1024;sin = (char *)in;sout = bufout;ret = iconv(c_pt, &sin, (size_t *)&lenin, &sout, (size_t *)&lenout);if (ret = -1) return NULL;)iconv_close(c_pt);return bufout;例如8：char *d_ConvertCharset(char *cpEncodeFrom, char*cpEncodeTo, const char *cplnput) static char s_strBufOut1024, *sin, *cp0ut;size_t ilnputLen, iOutLen, iReturn;iconv_t c_pt;if (c_pt = iconv open (cpEncodeTo, cpEncodeFrom)= (iconv_t)-1) printf (z/iconv_open failed! nzz);return NULL;iconv(c_pt, NULL, NULL, NULL, NULL);ilnputLen = strlen (cplnput) + 1;iOutLen = 1024;sin = (char *)cplnput;cpOut = s_strBufOut;iReturn = iconv(c_pt, &sin, &iInputLen, &cp0ut, &i0utLen);if (iReturn =二-1) return NULL;iconv_close(c_pt);return s strBufOut;DNODE *h, *p, *q;int x;h=p=(*DNODE)malloc(sizeof(DNODE);scanf(“d”,&x);while(x!=0)q=(*DNODE)malloc(sizeof(DNODE);q-data=x;p-next=q;q-prior=p;p=q;scanf(cT,&x);p-next=NULL; h-prior=NULL;return h;2 .在双链表的第I个结点之后后插入一新结点void insertd(DNOD *h,int I, int x)DNODE *s, *p;intj；s=(DNODE *)malloc(sizeof(DNODE);s-data=x;if(I=0)s-next=*h; *h-prior=s; *h=s; *h-prior=NULL; elsep=*h;j=l;while(p!=NULL&jnext;if(p!=NULL)if(p-next=NULL)p-next=s; s-prior=p; s-next=NULL;elses-next=p-next; p-next-prior=s; s-prior=p; p-next=s; elseprintfCNo foundn);.删除双链表中值为x的结点void delete(DNODE *h, int x)DNODE *p;if(*h=NULL) printfCoverflown,9);if(*h-data=x)p=*h; *h= *h-next; *h-prior=NULL; free(p);elsep=*h-next;while(p! =NULL&p-data! =x)p=p-next;if(p!=NULL)if(p-next=NULL)p-prior-next=NULL; free(p);elsep-prior-next=p-next; p-next-prior=p-prior; free(p); elseprintfCNo foundn);第二章复习题一、填空.在线性结构中元素之间存在一对一关系,第一个结点没有 前驱结点,其 余每个结点有且只有一个前驱结点；最后一个结点没有后继结点,其余每个 结点有目只有一个后继结点。1 .线性结构的顺序存储结构是一种随机存取的存储结构,逻辑上相邻的元素 物理位置上必紧临；其链式存储结构是一种顺序存取的存储结构,逻辑上相 邻的元素物理存储位置不一定连续。二、选择.在一个单链表中，假设P所指结点不是最后结点，在P之后插入S所指结点， 那么执行（B ）oA. s-next=p; p-next=s;B. s-next=p-next; p-next=s;C. s-next=p-next; p=s;D. p-next=s; s-next=p;2.在一个单链表中，假设删除p所指结点的后续结点，那么执行（A ）。A. p-next=p-next-next;B. p-next=p-next;C. p=p-next; p-next=p-next-next; D. p=p-next-next;3 .在一个单链表中，q所指结点是p所指结点的前驱结点，假设在q和p之 间插入s结点，那么执行（C ）。A. s-next=p-next; p-next=s;p-next=s-next; s-next=p;B. s-next=p; q-next=s;p-next=s; s-next=q;4 .非空的循环单链表头指针为front, p指向尾结点，那么应满足（C ）。A. p-next=NULL; B. p=NULL; C. p-next=front; D. p=front;.带头结点的单链表头指针front为空的判定条件是（B ）。A. front-NULLB. front-next=NULLC. front-next=frontD. front!=NULL6.不带头结点的单链表头指针front为空的判定条件是（A ）0A. front二二NULLB. front-next二二NULLC. front-next=frontD. front!=NULL.在循环双链表的p所指结点之后插入s所指结点的操作是（D ）oA. p-next=s; s-prior=p; p-next-prior=s; s-next=p-next;p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;B. s-prior=p; s-next=p-next; p-next=s; p-next-prior=s;s-prior=p; s-next=p-next; p-next-prior=s; p-next=s;7 .在双链表的p所指结点之前插入s所指结点的操作是（A ）0s-prior=p-prior; s-next=p; p-prior-next=s; p-prior=s;A. s-next=p; s-prior=p-prior; p-prior=s; p-prior-next=s;p-prior=s; s-next=p; p-prior-next=s; s-prior=p-prior;B. s-prior=p; s-next=p-next; p-next-prior=s; p-next=s;.删除双链表中p所指结点的操作是(C )0A. p-prior=p-prior-prior; p-prior-next=p; free (p);p-next=p-next-next; p-next-prior=p; free(p);B. p-prior-next=p-next; p-next-prior=p-prior; free(p);p-next-prior=p-prior; p-prior-next=p; free (p)三、编程.含n个元素的顺序表X按升序排列，删除线性表中值介于a与b之间的元素。 void del (int x, int *n, int a, int b) int i=0, k;while (ia&xib) for(k=i;k*n;k+)xk=xk+l;(*n) ;)else i+;.含n个元素的顺序表A按升序排列，删除线性表中多余的值相同的元素。int del (int a, int n) int i=0, j;while (i=n-l)if (ai!=ai+l) i+;else for(j=i;j=an-l)an=x;else i=0;while(x=aii+;for(j=n-l; j=i; j) aj+l=aj;ai=x;n+;return n;.求单链表的长度int count (NODE *h)int n=0;NODE *p;P=h;if (h=NULL) n=0;elsewhile (p!=NULL)n+; p=p-next;return n;第三章栈和队列要求、目标：熟悉栈和队列特点、数据结构的定义掌握在栈上的各种操作、使用数组和链表实现栈掌握用数组和链表实现队列掌握循环队列的相关操作 一、栈（一）概述.堆栈：只允许在表的一端进行插入和删除操作的线性表。1 .栈顶：允许进行添加或删除元素的一端.栈底：不允许进行添加或删除元素的一端2 .空栈：没有元素的栈.入栈（进栈/压栈）（push）：栈的插入运算3 .出栈（退栈/弹出）（pop）：栈的删除运算.栈的特点：后进先出（LIFO）在栈中插入和删除的例如（二）栈的顺序存储结构.栈类型的定义#define STACKMAX 100int top;int stackSTACKMAX;.栈的初始化top值为下一个进栈元素在数组中的下标值，入栈操作是先压栈再移动栈顶 指针，出栈操作是先移动栈顶指针再取出元素1）栈空：top=02）栈满：top=STACKMAX.进栈与出栈顺序假设进栈序列为a、b、c,那么全部可能出栈的序列为（，一，表示进，一，表示出）：af a- bf b- cf c-即 abcaf b b- c- c- a即 bca af a- bf cf c- b-即 acb af bf b- a- cf c-即 bac af bf cf c b a即 cba 4.判定栈是否为空int empty()if(top=0) return 1;else return 0;).压栈的实现int top=0;int push(int x)if(top=STACKMAX) rerurn 1; stacktop+=x;return 0;.出栈的实现 int pop(int *p) if(top=0) rreturn 1;*p=stacktop;return 0;.读栈顶元素 void readtop(int *p) if(top=0) printfCNo elementrT);else *p=stacktop;top+;(三)栈的链式存储结构.链栈：用线性链表表示的栈1 .栈顶指针：链栈的表头指针.栈的变化1)栈空：top=NULL2)非空：top指向链表的第一个结点，栈底结点的指针域为空无栈满情况.结点类型typedef struct snodeint data;struct snode *next; SNODE;.进栈的实现SNODE *top=NULL;void push_L(int x)SNODE *p;p二(SNODE *)malloc(sizeof(SNODE);p-data=x;p-next=top;top=p；.判链栈是否为空int empty_L(SNODE *top)if(top=NULL) return 1;else return 0;.出栈的实现int pop_L(SNODE *top, int *p)SNODE *q;if(top=NULL) return 1;*p=top-data;q=top;top=top-next;free(q);return 0;.求链栈中结点的个数int count_L(SNODE *top)SNODE *p;顺序存储结构：利用元素的相对位置来表示元素间的位置关系，是一 种随机存取结构，逻辑上相邻的数据物理上也紧临，静态分配空间； 链式存储结构：借助元素存储的指针来表示元素之间的关系，逻辑上 相邻的数据物理上不一定紧临，动态分配空间。11 .逻辑结构和物理结构的关系：是密切相关的两个方面，任何一个算法的 设计取决于逻辑结构，而算法的实现那么依赖于采用的存储结构。12 .数据类型：是一个值的集合和定义在这个值集上的一组操作的总称，规 定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值 上允许进行的操作。二、算法和算法分析1 .算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。2 .算法的特性：有穷性：算法在执行有究步之后结束，每一步在有穷时间内完成。确定性：每一条指令必须有确切的含义，不应产生二义性，相同的输入只 能得出相同的输出。可行性：一个算法可以通过已经实现的基本运算执行有限次来实现。输入性：一个算法有零个或多个输入。输出性：一个算法有一个或多个输出。3 .算法分析考虑的方面：正确性可读性健壮性效率与低存储量需求4 .语句频度：一条语句被执行的次数.渐近时间复杂度：所有语句频度之和，主要考虑嵌套最深语句的频度，假设频 度为多项式取指数最高的一项去掉系数即为渐近时间复杂度。T(n)=O(f(n)f(n)为时间复杂度值例：(l)+x; s=0;0(1)(2)for( i=l; iv=n; i+ )+x; s+=x0(n)(3)for( j=1; j=n; j+ )O(n2)for( k=l; k=n; k+ )+x; s+=x;(4)for(j=l;jnext;return n;(四)栈的应用.数数制转换(十进制一八进制)void convert()int x,n,m;top=0;scanf(d”,&n);while(n)m=push(n%8);if(m) printf(overflown);else n/=8;while(! empty ()m=pop(&x);if(m) printfCNo elementrT);else printf(d”,x);.表达式求值1)算术表达式的中缀表示：运算符放在两个操作数中间的算术表达式例：a+b*c+d/e*f2)中缀表示在计算机处理中的的问题受括号、优先级和结合律的限制，不一定按运算符出现的先后顺序执行，完 成运算需对表达式进行多遍扫描，浪费时间。3)算术表达式的后缀表示(逆波兰表示法)例：a+b- ab+ a*b- ab* 4)中缀表达式到后缀表达式的转换规那么找出最先运算的运算符，将其移至两个操作数的后面，假设有括号那么删掉把得到的后缀表达式作为一个整体放在原表达式中找下一个要运算的运算符，重复上述转换直到所有运算符处理完毕例：a+b*c-d/（e*f）f a+b*c-d/ef*f a+bc*-def*/f abc*+-def*/f abc*+def*/-.后缀表达式的求值从左f右扫描，遇到运算符将该运算符前面两个数取出运算，结果带回后缀 表达式参与后面的运算，直到扫描到最后一个运算符并计算得最终结果例：345/6*+2- 3 0.8 6*+2- 3 4.8+2- 7.8 2- 5.8.运用栈完成后缀表达式求值运用栈保存操作数和结果，从左一右扫描，假设为操作数那么将其入栈，假设为运 算符那么弹出两个数进行运算，并将结果入栈，直到扫描到表达式的最后一个字符, 栈顶的值为最终的结果。5 .运用栈完成中缀表达式到后缀表达式的转换运用栈保存运算符、取中缀表达式中的一字符，假设为数字那么输出； 假设为（那么入栈；假设为运算符当其优先级高于栈顶运算符的栈中优先级时那么入栈， 否那么栈顶运算符出栈并输出；假设为）那么依次退出栈中运算符并输出直到（， 将（退栈但不输出；假设为0那么依次退栈并输出二、队列（一）概述.队列：只允许在表的一端进行插入操作而在另一端进行删除操作的线性表1 .队尾：允许进行插入操作的一端.队首：允许进行删除操作的一端2 .特点：先进先出（FIFO）（二）队列的顺序存储结构.顺序队列的类型#define QUEUEMAX 100char queue QUEUEMAX;int front,rear;.顺序队列的变化front指向队首元素的前一个位置，rear指向队尾元素的位置，入队操作是先 移动队尾指针，再插入元素；出队操作是先移动队首指针，再取出元素1) 空：front=rear=-12)非空：rearfront3)满：rear二二 QUEUEMAX-13 .判别队列是否为空int empty()if(front=rear) return 1;else return 0;.初始化队列void init()int front=-1 ,rear=-1;.入队的实现int ins_queue(char x)if(rear= QUEUEMAX-1) return 1;queue +rear=x;return ();.出队的实现int del_queue(char *p)if(front=rear) return 1;*p=queue+front;return 0;.假溢出1)假满：当rear=QUEUEMAX-l时，数组前端有空闲单元，出现假满2)解决方案：一个元素出队时，将所有元素依次向队首方向移动一个位置，修改头尾指针， 使空闲单元留在后面，此方案花费时间较多出队时队列不移动，当出现假溢出时，将所有元素依次向队首方向移动，此方 案也要花费较多时间把队列看作是一个首尾衍接的循环队列，这是最有效的解决方案（三）循环队列.特点：空闲单元单元总是在尾指针后面，front指向队首前一个位置1 .循环队列的变化ARRAYMAX = 16ARRAYMAX = 16队列的队首0 1