《数据结构》复习重点精品资料.doc

数据结构复习重点第一章 绪论要求、目标：了解数据逻辑结构的分类；掌握算法的特性及估算算法时间复杂度的方法；熟悉数据结构的基本基本概念和术语。一、 基本概念和术语1数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。2数据：是对客观事物的符号表示，即所有能输入到计算机中并被计算机程序处理的符号的总称。3数据项：数据的不可分割的最小单位。4数据元素（数据结点）：数据的基本单位，在程序中作为一个整体处理，由若干数据项组成。5数据对象：性质相同的数据元素的集合，是数据的一个子集如：四季对象是集合：春，夏，秋，冬自然数对象是集合：0，1，2，3，字母字符对象是集合 ：A，B，Z6数据结构的分类：线性结构和非线性结构。7数据结构的形式化定义：数据结构是一个二元组，可定义为Data_Structure=(D,S)其中：D是数据元素的有限集合，S是D上关系的有限集合8序偶：两个元素间的前后关系。<a,b>a是b的前驱结点，b是a的后继结点例：四季的描述 B=（D，R） D=春，夏，秋，冬 R=<春，夏>,<夏，秋>,<秋，冬>9物理结构（存储结构或映像）：数据结构在计算机中的表示。10存储结构的分类： 顺序存储结构：利用元素的相对位置来表示元素间的位置关系，是一种随机存取结构，逻辑上相邻的数据物理上也紧临，静态分配空间； 链式存储结构：借助元素存储的指针来表示元素之间的关系，逻辑上相邻的数据物理上不一定紧临，动态分配空间。11逻辑结构和物理结构的关系：是密切相关的两个方面，任何一个算法的设计取决于逻辑结构，而算法的实现则依赖于采用的存储结构。12数据类型：是一个值的集合和定义在这个值集上的一组操作的总称，规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。二、 算法和算法分析 1算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。 2算法的特性：有穷性：算法在执行有究步之后结束，每一步在有穷时间内完成。确定性：每一条指令必须有确切的含义，不应产生二义性，相同的输入只能得出相同的输出。可行性：一个算法可以通过已经实现的基本运算执行有限次来实现。输入性：一个算法有零个或多个输入。输出性：一个算法有一个或多个输出。 3算法分析考虑的方面： 正确性 可读性 健壮性 效率与低存储量需求 4语句频度：一条语句被执行的次数5渐近时间复杂度：所有语句频度之和，主要考虑嵌套最深语句的频度，若频度为多项式取指数最高的一项去掉系数即为渐近时间复杂度。 T(n)=O(f(n)-f(n)为时间复杂度值例：(1)+x; s=0; -O(1) (2)for( i=1; i<=n; i+ )+x; s+=x -O(n) (3)for( j=1; j<=n; j+ ) -O(n2) for( k=1; k<=n; k+ )+x; s+=x; (4)for(j=1; j<n; j+) y=y+1; -频度：n-1 for(k=0; k<=(2*n); j+)x+; -频度：(n-1)*(2n+1) -时间复杂度为O(n2) 6算法分析的两个主要方面：空间复杂度和时间复杂度。第一章 复习题一、填空1、数据结构被形式地定义为（D，S），其中D是 数据元素 的有限集合，S是 D上关系 的有限集合。2、数据结构是一门研究非数值计算的程序设计问题中计算机的 数据元素 以及它们之间的 关系 和运算等的学科。3、在数据结构中，逻辑上可以把数据结构分成 线性结构 和 非线性结构 。二、选择1、算法必须具备的五个特性是（ B ）。A输入性、输出性、可执行性、可移植性和可扩充性B输入性、输出性、可行性、确定性和有穷性C输入性、输出性、确定性、有穷性和稳定性D输入性、输出性、可行性、稳定性和安全性2、算法分析的两个主要方面是（ A ）。A空间复杂度和时间复杂度 B正确性和可读性C简单性和文档性 D数据复杂性和程序复杂性三、计算，求下列算法的渐近时间复杂度及带语句的频度1void sort(int *x,int n) int i,j,k,t; for(i=1,i<=n-1;i+) k=i; for(j=i+1;j<n;j+) if(xj>xk)k=j; if(k!=i)t=xi;xi=xk;xk=t; 解：语句频度为： 渐近时间复杂度：O(n2)2sum(int n); int sum=0,i,j; for(i=1;i<=n;i+) p=1;for(j=1;j<=i;j+)p*=j; sum+=p; return sum;解：语句频度为： 渐近时间复杂度：O(n2) 3sum(int n)int i,sum=0;for(i=1;i<=n;i+)sum+=i; printf(“%d”,sum); 解：语句频度为： n 渐近时间复杂度：O(n)第二章 线性表要求、目标：了解线性表的基本概念；掌握顺序存储和链式存储结构的描述方法；掌握循环单链表、双链表的特点一、线性表概述1线性表：具有相同类型的n个数据元素的有限序列，可表示为(a1,a2,an)2线性表长度：数据元素个数n。3空线性表：长度为零的线性表。4关键字/键：能惟一标识元素的字段。5相邻元素关系：ai为ai+1前驱元素，ai+1为ai后继元素，存在序偶关系。a1无前驱元素，an无后继元素。例：字母表：(A,B,C,Z) 学生成绩表：(790631,790632,790645)每个元素为一条记录，由若干数据项组成，线性表中可只写关键字。二、线性表的顺序存储1顺序存储：线性表的各个元素依次存储在一组地址连续的存储单元里。2元素位置确定：LOC(ai)=LOC(a1)+(i-1)*L 其中a1为线性表第一个元素的存储位置，L为每个元素所占字节数。 例：已知a1的地址为1000，每个元素占2字节，求a5的地址LOC(a5)=1000+(5-1)*2=10083顺序表的特点（1）是一种随机存取的存储结构（2）逻辑上相邻的元素物理位置必定紧邻（3）存储空间是静态分配的（4）适用于事先能确定线性表的大小，存取速度快（5）插入和删除操作时需移动大量的元素,4插入或删除元素时移动次数（1）向含有n个元素的线性表第i个位置插入元素，需移动n-i+1次元素，平均移动次（2）删除含有n个元素的线性表第i个位置的元素，需移动n-i次元素，平均移动次5存储结构的描述#define list_max 100typedef structint datalist_max; int len;sqlist;6顺序结构线性表的运算（1）线性表的初始化void InitList(sqlist *L)L.len=0;（2）求线性表的长度int ListLen(sqlist *L)return L.len;（3）在线性表中查询某个个结点，返回结点在线性表中的位置int search( int x; sqlist *L; int n ) int i;for( i=0; i<n; i+)if(x=L.datai) break; if( i=n)return(0); return(i+1); （4）在顺序线性表中第I个位置前插入一新元素 int insert_sq(sqlist *L; int i; int e) int p;if( i<1|I>L.len) return 1;if( L.len>list_max-1) return 2;for( p=L.len; p>i; p- )L.datap=L.datap-1; L.datai=e; L.len+; return 0;（5）在顺序线性表中删除第i个元素 int delete_sq(sqlist *L,int i) int p;if(i<1|i>L.len) return 1;for( p=i+1; p<L.len; p+)L.datap-1=L.datap;L.len-;return 0;（6）合并两个递增有序的顺序线性表，合并后仍为递增有序int mergelist(sqlist *LA,sqlist *LB,sqlist *LC)int I=0,j=0,k=0;while(I<LA.len&&j<LB.len)if(LA.dataI<LB.dataj)LC.datak+=LA.dataI+;else if(LA.dataI=LB.dataj)LC.datak+=LA.dataI+;LC.datak+=LB.dataj+;elseLC.datak+=LB.dataj+;while(I<La.len)LC.datak+=LA.dataI+;while(j<LB.len)LC.datak+=LB.dataj+;return k;三、线性表的链式存储（一）线性链表1特点1）逻辑上相邻的元素，物理上不一定紧邻2）插入和删除操作时，不需移动大量元素，只需修改有限的指针变量3）动态分配和释放存储单元，避免了空间浪费4）不具备随机存取的优点，查找结点需从表头开始，结点的存储利用率较低5）适用于经常进行插入、删除操作或事先不能确定结点的最大数量2线性链表：具有链式存储结构的线性表3单链表：每个结点只包含一个指针域datanext4结点结构：5结点类型typedef struct nodeint data;struct node *next;NODE;6头指针：指向链表的头结点或第一个结点的位置7头结点：在链表第一个结点之前附设的结点，其数据域可不存任何信息或存表长，指针域保存第一个结点的地址8设置头结点的作用：插入或删除首元素时不必对头指针进行修改9第一个结点：第一个实际存储数据的结点10单链表的结构1）不带头结点a0nextnextan-1、nexta1nextnexth 2)带头结点a0nextnextan-1、nexta1nextnextnextnextnexth 11建立带头结点的单链表,在表尾插入，以-1结束NODE *creat( )NODE *h,*p,*r;int x;h=r=(NODE *)malloc(sizeof(NODE);scanf(“%d”,&x);while(x!=-1)p=(NODE *)malloc(sizeof(NODE);p->data=x;r->next=p;r=p;scanf(“%d”,&x);r->next=NULL;return(h);12建立带头结点的单链表,在表头插入，以-1结束NODE *creat( )NODE *h,*p;int x;h= (NODE *)malloc(sizeof(NODE);h->next=NULL;scanf(“%d”,&x);while(x!=-1)p=(NODE *)malloc(sizeof(NODE);p->data=x;p->next=h->next;h->next=p;scanf(“%d”,&x);return(h);13在单链表第I个结点前插入一个元素int insert_L(NODE *h,int I,int x)NODE *p=h, *s;int j=0;s=(NODE *)malloc(sizeof(NODE);s->data=x;while(p!=NULL&&j<I-1)p=p->next; j+;if(!p|j>I-1)return 1;s->next=p->next;p->next=s;return 0;14删除单链表中第I个结点int delete_L(NODE *h, int I, int *e) NODE *p=h, *q;int j=0;while(p->next&&j<I-1)p=p->next; j+;if(!(p->next)|j>I-1)return 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;r=s;while(p!=NULL&&q!=NULL)if(p->data>q->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;（二）循环链表1定义：最后一个结点的指针域指向链表的头结点或第一个结点。2优点：解决了无法从指定结点到达该结点的前驱结点的问题。3结构：a0nextnextan-1、nexta1nextnextha0nextnextan-1、nextnextnexth4判别是否为空1）带头结点：当h->next=h 时为空2）不带头结点：当h=NULL时为空5删除第一个结点1）带头结点：h->next=h->next->next2）不带头结点：h=h->next6建立循环链表将尾结点r->next=NULL;改为r->next=h;（三）双向链表1特点：两个指针域，可用于表示树型结构，一个指向前驱，一个指向后继2结点类型：typedef struct dnodeint data;struct dnode *prior, *next;DNODE;3结构：h 4建立双链表(以0结束)DNODE *creatd()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(“%d”,&x);p->next=NULL; h->prior=NULL;return h;5在双链表的第I个结点之后后插入一新结点 void insertd(DNOD *h,int I, int x) DNODE *s, *p;int j;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=1;while(p!=NULL&&j<i)j+; p=p->next;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; else printf(“No foundn”);6删除双链表中值为x的结点void delete(DNODE *h, int x)DNODE *p;if(*h=NULL) printf(“overflown”);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);elseprintf(“No foundn”);第二章 复习题一、填空1在线性结构中元素之间存在 一对一 关系，第一个结点 没有 前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点 没有 后继结点，其余每个结点有且只有 1 个后继结点。2线性结构的顺序存储结构是一种 随机存取 的存储结构，逻辑上相邻的元素物理位置上 必紧临 ；其链式存储结构是一种 顺序存取 的存储结构，逻辑上相邻的元素物理存储位置 不一定连续 。二、选择1在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ B ）。As->next=p; p->next=s; Bs->next=p->next; p->next=s;Cs->next=p->next; p=s; Dp->next=s; s->next=p;2. 在一个单链表中，若删除p所指结点的后续结点，则执行（ A ）。Ap->next=p->next->next; B p->next=p->next;Cp=p->next; p->next=p->next->next; Dp=p->next->next;3在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ C ）。As->next=p->next; p->next=s;Bp->next=s->next; s->next=p;Cs->next=p; q->next=s;Dp->next=s; s->next=q;4非空的循环单链表头指针为front,p指向尾结点，则应满足（ C ）。A.p->next=NULL; B.p=NULL; C.p->next=front; D.p=front;5. 带头结点的单链表头指针front为空的判定条件是（ B ）。Afront=NULL Bfront->next=NULL Cfront->next=front Dfront!=NULL6不带头结点的单链表头指针front为空的判定条件是（ A ）。Afront=NULL Bfront->next=NULL Cfront->next=front Dfront!=NULL7在循环双链表的p所指结点之后插入s所指结点的操作是（ D ）。Ap->next=s; s->prior=p; p->next->prior=s; s->next=p->next;Bp->next=s; p->next->prior=s; s->prior=p; s->next=p->next;Cs->prior=p; s->next=p->next; p->next=s; p->next->prior=s;Ds->prior=p; s->next=p->next; p->next->prior=s; p->next=s;8. 在双链表的p所指结点之前插入s所指结点的操作是（ A ）。As->prior=p->prior; s->next=p; p->prior->next=s; p->prior=s;Bs->next=p; s->prior=p->prior; p->prior=s; p->prior->next=s;Cp->prior=s; s->next=p; p->prior->next=s; s->prior=p->prior;Ds->prior=p; s->next=p->next; p->next->prior=s; p->next=s;9. 删除双链表中p所指结点的操作是（ C ）。Ap->prior=p->prior->prior; p->prior->next=p; free(p);Bp->next=p->next->next; p->next->prior=p; free(p);Cp->prior->next=p->next; p->next->prior=p->prior; free(p);Dp->next->prior=p->prior; p->prior->next=p; free(p)三、编程1含n个元素的顺序表X按升序排列，删除线性表中值介于a与b之间的元素。void del(int x,int *n,int a,int b) int i=0,k; while(i<*n) if(xi>a&&xi<b) for(k=i;k<*n;k+) xk=xk+1; (*n)-; else i+;2含n个元素的顺序表A按升序排列，删除线性表中多余的值相同的元素。int del(int a,int n) int i=0,j; while(i<=n-1) if(ai!=ai+1)i+; else for(j=i;j<n;j+) aj=aj+1; n-; return n;3含n个元素的顺序表A中元素按升序排列，插入一个元素x后，使A中元素仍有序。int insert(int a,int n,int x) int i,j; if(x>=an-1)an=x; else i=0; while(x>=aii+; for(j=n-1;j>=i;j-)aj+1=aj;ai=x;n+; return n;4求单链表的长度 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栈顶：允许进行添加或删除元素的一端3栈底：不允许进行添加或删除元素的一端4空栈：没有元素的栈5入栈（进栈/压栈）（push）：栈的插入运算6出栈（退栈/弹出）（pop）：栈的删除运算7栈的特点：后进先出（LIFO）在栈中插入和删除的示例（二）栈的顺序存储结构1栈类型的定义#define STACKMAX 100int top;int stackSTACKMAX;2栈的初始化top值为下一个进栈元素在数组中的下标值，入栈操作是先压栈再移动栈顶指针，出栈操作是先移动栈顶指针再取出元素1）栈空：top=02）栈满：top=STACKMAX3进栈与出栈顺序若进栈序列为a、b、c，则全部可能出栈的序列为（表示进，表示出）：a a b b c c 即abca b b c c a 即bcaa a b c c b 即acba b b a c c 即baca b c c b a 即cba4判定栈是否为空 int empty() if(top=0) return 1;else return 0;5压栈的实现 int top=0; int push(int x) if(top>=STACKMAX) rerurn 1;stacktop+=x;return 0;6出栈的实现 int pop(int *p) if(top=0) rreturn 1;*p=stack-top;return 0;7读栈顶元素 void readtop(int *p) if(top=0) printf(“No elementn”);else *p=stack-top;top+;（三）栈的链式存储结构1链栈：用线性链表表示的栈2栈顶指针：链栈的表头指针3栈的变化1）栈空：top=NULL2）非空：top指向链表的第一个结点，栈底结点的指针域为空l 无栈满情况4结点类型 typedef struct snode int data;struct snode *next;SNODE;5进栈的实现SNODE *top=NULL;void push_L(int x)SNODE *p;p=(SNODE *)malloc(sizeof(SNODE);p->data=x;p->next=top;top=p;6判链栈是否为空 int empty_L(SNODE *top) if(top=NULL) return 1;else return 0;7出栈的实现 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;8求链栈中结点的个数 int count_L(SNODE *top) SNODE *p;int n=0;p=top;while(p!=NULL)n+; p=p>next;return n;（四）栈的应用1数数制转换（十进制八进制） 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) printf(“No elementn”);else printf(“%d”,x);2表达式求值1）算术表达式的中缀表示：运算符放在两个操作数中间的算术表达式 例：a+b*c+d/e*f2）中缀表示在计算机处理中的的问题受括号、优先级和结合律的限制，不一定按运算符出现的先后顺序执行，完成运算需对表达式进行多遍扫描，浪费时间。3）算术表达式的后缀表示（逆波兰表示法）例：a+b ab+ a*b ab*4）中缀表达式到后缀表达式的转换规则找出最先运算的运算符，将其移至两个操作数的后面，若有括号则删掉把得到的后缀表达式作为一个整体放在原表达式中找下一个要运算的运算符，重复上述转换直到所有运算符处理完毕例：a+b*c-d/(e*f) a+b*c-d/ef* a+bc*-def*/ abc*+-def*/ abc*+def*/-5后缀表达式的求值从左右扫描，遇到运算符将该运算符前面两个数取出运算，结果带回后缀表达式参与后面的运算，直到扫描到最后一个运算符并计算得最终结果 例：345/6*+2- 3 0.8 6*+2- 3 4.8+2- 7.8 2- 5.86运用栈完成后缀表达式求值运用栈保存操作数和结果，从左右扫描，若为操作数则将其入栈，若为运算符则弹出两个数进行运算，并将结果入栈，直到扫描到表达式的最后一个字符，栈顶的值为最终的结果。7运用栈完成中缀表达式到后缀表达式的转换运用栈保存运算符、(、#，取中缀表达式中的一字符，若为数字则输出；若为(则入栈；若为运算符当其优先级高于栈顶运算符的栈中优先级时则入栈，否则栈顶运算符出栈并输出；若为)则依次退出栈中运算符并输出直到(，将(退栈但不输出；若为0则依次退栈并输出二、队列（一）概述1队列：只允许在表的一端进行插入操作而在另一端进行删除操作的线性表2队尾：允许进行插入操作的一端3队首：允许进行删除操作的一端4特点：先进先出（FIFO）（二）队列的顺序存储结构1顺序队列的类型#define QUEUEMAX 100char queueQUEUEMAX;int front,rear;2顺序队列的变化front指向队首元素的前一个位置，rear指向队尾元素的位置，入队操作是先移动队尾指针，再插入元素；出队操作是先移动队首指针，再取出元素1）空：front=rear=-12）非空：rear>front3）满：rear= QUEUEMAX-13判别队列是否为空 int empty() if(front=rear) return 1;else return 0;4初始化队列 void init() int front=-1,rear=-1;5入队的实现 int ins_queue(char x) if(rear= QUEUEMAX-1) return 1;queue+rear=x;return 0;6出队的实现 int del_queue(char *p) if(front=rear) return 1;*p=queue+front;return 0;7假溢出1）假满：当rear= QUEUEMAX-1时，数组前端有空闲单元，出现假满2）解决方案：一个元素出队时，将所有元素依次向队首方向移动一个位置，修改头尾指针，使空闲单元留在后面，此方案花费时间较多出队时队列不移动，当出现假溢出时，将所有元素依次向队首方向移动，此方案也要花费较多时间把队列看作是一个首尾衍接的循环队列，这是最有效的解决方案（三）循环队列1特点：空闲单元单元总是在尾指针后面，front指向队首前一个位置2循环队列的变化1）空队：front=rear2）队满：front=rear3问题：当队列空和满时条件相同，无法判定队列是空还是满4最好的解决方案设置一个空闲单元，则可用单元为QUEUEMAX-1个，当判别队列是否满时，确定rear的下一个单元的位置是否为front所指的单元队满条件：(rear+1)% QUEUEMAX=front队空条件：rear=front5循环队列指针的移动插入或删除元素时，指针按逆时针方向进1队首指针进1：front=(front+1)% QUEUEMAX队尾指针进1：rear=(rear+1)% QUEUEMAX6入队的实现 int front=0,rear=0; int cir_ins_queue(char x) if(rear+1)% QUEUEMAX=front) return 1;rear=(rear+1)% QUEUEMAX ;queuerear=x;return 0;7出队的实现 int cir_del_queue(char *p) if(rear=front) return 1;front=(front+1)% QUEUEMAX ;*p=queuefront;return 0;（四）队列的链式存储结