《数据结构》复习重点

1、PAGE PAGE 87数据结构复习重点第一章 绪论要求、目标：了解数据逻辑结构的分类；掌握算法的特性及估算算法时间复杂度的方法；熟悉数据结构的基本基本概念和术语。基本概念和术语1数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。2数据：是对客观事物的符号表示，即所有能输入到计算机中并被计算机程序处理的符号的总称。3数据项：数据的不可分割的最小单位。4数据元素（数据结点）：数据的基本单位，在程序中作为一个整体处理，由若干数据项组成。5数据对象：性质相同的数据元素的集合，是数据的一个子集如：四季对象是集合：春，夏，秋，冬自然数对象是集合：0，1，2，

2、3，字母字符对象是集合 ：A，B，Z6数据结构的分类：线性结构和非线性结构。7数据结构的形式化定义：数据结构是一个二元组，可定义为Data_Structure=(D,S)其中：D是数据元素的有限集合，S是D上关系的有限集合8序偶：两个元素间的前后关系。a是b的前驱结点，b是a的后继结点例：四季的描述 B=（D，R） D=春，夏，秋，冬 R=,9物理结构（存储结构或映像）：数据结构在计算机中的表示。10存储结构的分类：顺序存储结构：利用元素的相对位置来表示元素间的位置关系，是一种随机存取结构，逻辑上相邻的数据物理上也紧临，静态分配空间；链式存储结构：借助元素存储的指针来表示元素之间的关系，逻辑上

3、相邻的数据物理上不一定紧临，动态分配空间。11逻辑结构和物理结构的关系：是密切相关的两个方面，任何一个算法的设计取决于逻辑结构，而算法的实现则依赖于采用的存储结构。12数据类型：是一个值的集合和定义在这个值集上的一组操作的总称，规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。算法和算法分析 1算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。 2算法的特性：有穷性：算法在执行有究步之后结束，每一步在有穷时间内完成。确定性：每一条指令必须有确切的含义，不应产生二义性，相同的输入只能得出相同的输出。可行性：一个算法可以通过已经实现的基本运算执行有限次来实现

4、。输入性：一个算法有零个或多个输入。输出性：一个算法有一个或多个输出。 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; jn; j

5、+) 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输入性、输出性、

6、可行性、确定性和有穷性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;jxk)k=j; if(k!=i)t=xi;xi=xk;xk=t; 解：语句频度为： 渐近时间复杂度：O(n2)2sum(int n); int sum=0,i,j; for(i=1

7、;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关键字/

8、键：能惟一标识元素的字段。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=1

9、0083顺序表的特点（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 InitLi

10、st(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; in; 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( iL.len) return 1;if(

11、 L.lenlist_max-1) return 2;for( p=L.len; pi; 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(iL.len) return 1;for( p=i+1; pL.len; p+)L.datap-1=L.datap;L.len-;return 0;（6）合并两个递增有序的顺序线性表，合并后仍为递增有序int mergelist(sqlist *LA,sqlist *LB,sqlist *L

12、C)int I=0,j=0,k=0;while(ILA.len&jLB.len)if(LA.dataILB.dataj)LC.datak+=LA.dataI+;else if(LA.dataI=LB.dataj)LC.datak+=LA.dataI+;LC.datak+=LB.dataj+;elseLC.datak+=LB.dataj+;while(ILa.len)LC.datak+=LA.dataI+;while(jdata=x;r-next=p;r=p;scanf(“%d”,&x);r-next=NULL;return(h);12建立带头结点的单链表,在表头插入，以-1结束NODE *cr

13、eat( )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!

14、=NULL&jnext; j+;if(!p|jI-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&jnext; j+;if(!(p-next)|jI-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-

15、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-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-n

16、ext=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特点：两个指针域，可用于表示树型结构，一个指

17、向前驱，一个指向后继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;ret

18、urn 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&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

19、-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

20、-next; p-next-prior=p-prior; free(p);elseprintf(“No foundn”);第二章 复习题一、填空1在线性结构中元素之间存在 一对一 关系，第一个结点 没有 前驱结点，其余每个结点有且只有 1 个前驱结点；最后一个结点 没有 后继结点，其余每个结点有且只有 1 个后继结点。2线性结构的顺序存储结构是一种 随机存取 的存储结构，逻辑上相邻的元素物理位置上 必紧临 ；其链式存储结构是一种 顺序存取 的存储结构，逻辑上相邻的元素物理存储位置 不一定连续 。二、选择1在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ B ）。As-

21、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

22、;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 D

23、front!=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;

24、 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-pri

25、or=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(ia&xib) for(k=i;k*n;k+) xk=xk+1; (*n)-; else i+;2含n个元素的顺序表A按升序排列，删除线性表中多余的值相同的元素。int del(int a,in

26、t n) int i=0,j; while(i=n-1) if(ai!=ai+1)i+; else for(j=i;j=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;栈和队列要求、目标：熟悉栈和队列特点、数据结构的定义掌握在栈上的各种操作、使用数组和链表实现栈掌握用数组和链表实现队列掌握

27、循环队列的相关操作一、栈（一）概述1堆栈：只允许在表的一端进行插入和删除操作的线性表。2栈顶：允许进行添加或删除元素的一端3栈底：不允许进行添加或删除元素的一端4空栈：没有元素的栈5入栈（进栈/压栈）（push）：栈的插入运算6出栈（退栈/弹出）（pop）：栈的删除运算7栈的特点：后进先出（LIFO）在栈中插入和删除的示例（二）栈的顺序存储结构1栈类型的定义#define STACKMAX 100int top;int stackSTACKMAX;2栈的初始化top值为下一个进栈元素在数组中的下标值，入栈操作是先压栈再移动栈顶指针，出栈操作是先移动栈顶指针再取出元素1）栈空：top=02）栈满

28、：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

29、) 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指向链表的第一个结点，栈底结点的指针域为空无栈满情况4结点类型 typedef struct snode int data;struct snode *next;SNODE;5进栈的实现SNODE *top=NULL;void push_L

30、(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

31、*p;int n=0;p=top;while(p!=NULL)n+; p=pnext;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）中

32、缀表示在计算机处理中的的问题受括号、优先级和结合律的限制，不一定按运算符出现的先后顺序执行，完成运算需对表达式进行多遍扫描，浪费时间。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后缀表达式的求值从左右扫描，遇到运算符将该运算符前面两个数取出运

33、算，结果带回后缀表达式参与后面的运算，直到扫描到最后一个运算符并计算得最终结果 例：345/6*+2- 3 0.8 6*+2- 3 4.8+2- 7.8 2- 5.86运用栈完成后缀表达式求值运用栈保存操作数和结果，从左右扫描，若为操作数则将其入栈，若为运算符则弹出两个数进行运算，并将结果入栈，直到扫描到表达式的最后一个字符，栈顶的值为最终的结果。7运用栈完成中缀表达式到后缀表达式的转换运用栈保存运算符、(、#，取中缀表达式中的一字符，若为数字则输出；若为(则入栈；若为运算符当其优先级高于栈顶运算符的栈中优先级时则入栈，否则栈顶运算符出栈并输出；若为)则依次退出栈中运算符并输出直到(，将(退栈

34、但不输出；若为0则依次退栈并输出二、队列（一）概述1队列：只允许在表的一端进行插入操作而在另一端进行删除操作的线性表2队尾：允许进行插入操作的一端3队首：允许进行删除操作的一端4特点：先进先出（FIFO）（二）队列的顺序存储结构1顺序队列的类型#define QUEUEMAX 100char queueQUEUEMAX;int front,rear;2顺序队列的变化front指向队首元素的前一个位置，rear指向队尾元素的位置，入队操作是先移动队尾指针，再插入元素；出队操作是先移动队首指针，再取出元素1）空：front=rear=-12）非空：rearfront3）满：rear= QUEUEM

35、AX-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时，数组前端有空闲单元

36、，出现假满2）解决方案：一个元素出队时，将所有元素依次向队首方向移动一个位置，修改头尾指针，使空闲单元留在后面，此方案花费时间较多出队时队列不移动，当出现假溢出时，将所有元素依次向队首方向移动，此方案也要花费较多时间把队列看作是一个首尾衍接的循环队列，这是最有效的解决方案（三）循环队列1特点：空闲单元单元总是在尾指针后面，front指向队首前一个位置2循环队列的变化1）空队：front=rear2）队满：front=rear3问题：当队列空和满时条件相同，无法判定队列是空还是满4最好的解决方案设置一个空闲单元，则可用单元为QUEUEMAX-1个，当判别队列是否满时，确定rear的下一个单元的位

37、置是否为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_

38、del_queue(char *p) if(rear=front) return 1;front=(front+1)% QUEUEMAX ;*p=queuefront;return 0;（四）队列的链式存储结构1链队：用线性链表表示的队列2结构形式 front rear3操作：在尾结点后插入，在首结点处删除4结点类型： typedef struct node char data;struct node *next;QNODE;5链队的指针：QNODE *front, *rear;6队列的变化1）队空：front=rear=NULL2）非空：rear-next=NULL7入队的实现 QNODE

39、*front=NULL, *rear=NULL; Void ins_queue_L(char x) QNODE *p;p=(QNODE *)malloc(sizeof(QNODE);p-data=x;p-next=NULL;if(front=NULL)front= p;else rear-next=p;rear=p;8出队的实现 int del_queue_L(char *p) QNODE *q;if(front=NULL) return 1;*p=front-data;q=front;front=front-next;free(q);return 0;第三章 复习题一、填空1表达式a+b*c

40、-d/(e*f)等价的后缀表达式为 abc*+def*/- ，后缀表达式3 4 5 2 */+2的值为 1.4 。2表达式a+(b-c)*d等价的后缀表达式为 abc-d*+ ，后缀表达式3 4 5 /6 *+2的值为 5.8 。3设栈顶指针为下一个待压入元素的下标值，则向栈中压入元素的操作是 先压入元素再移动栈顶指针 ，设队首指针指向队首元素的前一个位置，队尾指针指向队尾元素，则对队列进行出队的操作是 先移动队首指针，再取出元素 。4在循环队列中，设队首指针为front，队尾指针为rear，共有M个单元，可用的存储单元数为 M-1 ，当front=rear时，判别队列是空还是满的解决办法是

41、设置一个空闲单元 ，移动队首指针的操作是 front=(front+1)%M 。5栈和队列都是具有线性结构的数据结构，栈的特点是 后进先出 ，队列的特点是 先进先出 。6在一个循环队列中队首指针指向队首元素的 前一个位置 ，设队首指针为front，队尾指针为rear，共有M个单元，则队列为满的条件是 (rear+1)%M=front ，队列为空的条件是 rear=front 。7栈和队列都是操作受限的线性表，栈只能在 栈顶 插入和删除元素，队列只能在 队尾 插入元素在 队首 删除元素。使用 循环队列 是一种解决顺序存储的队列假溢出问题的有效方法。二、选择1设有编号1，2，3的三辆列车，顺序进入

42、一个栈式结构的站台，这三辆列车开出车站的不可能的顺序是（ D ）。 A1，2，3 B3，2，1 C1，3，2 D3，1，22若栈顶指针top指向栈顶元素的位置，栈的存储单元数为m，则栈满的条件是（ C ）。Atop=0 Btop=-1 Ctop=m-1 Dtop=m3一个队列的入队序列是1，2，3，4，则队列的输出序列是（ D ）。A4，3，2，1 B1，4，3，2 C3，2，4，1 D1，2，3，44在一个非空链队中，假设front和rear分别为队首和队尾指针，则向队列中插入p所指结点的运算应执行（ B ）。Afront-next=p;rear=p; Brear-next=p; rear=

43、p; Crear-next=p; front=p; Dfront-next=p; front=p;5若栈顶指针top指向下一个进栈元素的位置，栈的存储单元数为m，则栈满的条件是（ D ）。 Atop=0 Btop=-1 Ctop=m-1 Dtop=m6一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ B ）。Aedcba Bdceab Cdecba Dabcde7在一个链队中，假设front和rear分别为队首和队尾指针，若用x保存被删结点的值，则删除一个结点的运算应执行（ B ）。 Afront=front-next;x=front-data; Bx=front-data;

44、front=front-nextCx=rear-data;rear=rear-next; Drear=front-next;x=rear-data;第四章 串要求、目标：了解串的基本术语；熟悉两个串相等的充要条件及其特殊性，串的各种运算的实现；掌握串的存储结构，串的比较、连接、求串长、取子串的算法实现一、基本概念1串：由零个或多个字符组成的有限序列，记为：S=”a1a2an”(n0)2子串：一个串中任意个连续字符组成的子序列。3主串：包含子串的字符串为主串4空串：含零个字符的串，其长度为0。形式：”5空格串：由一个或多个空格字符组成的串，其长度为空格的个数6位置：字符在序列中的序号 从左右依次

45、为：1，2，3，n子串在主串中的位置以子串的第一个字符在主串中的位置来表示例：A=” B=” “ C=”Data Structure” D=”Bei” E=”Jing” F=”Bei Jing”其长度分别为：A：0，B：1，C：14，D：3，E：4，F：8D在F中的位置为1，E在F中的位置为57长度：串中字符的个数8特殊性：数据元素是一个字符9两个串相等的充要条件：长度相等且对应位置的字符相同二、串的存储1串的存储方式：顺序存储和链式存储2串的链式存储的结点类型 typedef struct node char data;struct node *next;SNODE;三、串的运算1求串长度1

46、）顺序存储的实现 int s_len(char string) int I;for(I=0; stringI!=0; I+);return I;2）链式存储的实现 int L_len(SNODE *h) SNODE *p=h;int n;for(n=0; p!=NULL; n+)p=p-next;return n;2串的比较1）顺序存储的实现 int s_cmp(char s1, char s2) int j=0;while(s1j=s2j&s1j!=0&s2j!=0)j+;return s1j-s2j;2）链式存储的实现 int L_cmp(SNODE *h1, SNODE *h2) SNO

47、DE *p1, *p2; p1=h1; p2=h2;while(p1-data=p2-data&p1!=NULL&p2!=NULL)p1=p1-next; p2=p2-next;if(p1=NULL&p2=NULL) return 0;else if(p1=NULL) return 1;else if(p2=NULL) return 1;else return p1-data-p2-data;3串的连接1）顺序存储的实现 #define M 100int s_cat(char s1, char s2) int I,j,k;I=strlen(s1);j=strlen(s2);if(I+j=M)

48、trturn 1;for(k=0; knext!=NULL)p1=p1-next;p1-next=s2;4取子串1）顺序存储的实现 int s_sub(char s1,int I, int k, char s2) int m;if(I(m=strlen(s1) return 1;if(km+1) return 1;for(m=0; mk; m+)s2m=s1I-1+m;s2m=0;return 0;2）链式存储的实现 int L_sub(SNODE *h1, int I, int k, SNODE *h2) SNODE *p, *q, *r;int m;if(I(m=L_len(h1) ret

49、urn 1;if(km+1) return 1;if(k=0) *h2=NULL;elsep=s1;for(m=1; mnext;q=(SNODE *)malloc(sizeof(SNODE);q-data=p-data;*s2=q;r=q;for(m=1; mnext;q=(SNODE *)malloc(sizeof(SNODE);q-data=p-data;r-next=q;r=q;r-next=NULL;reurn 0;第四章 复习题一、填空1串是一种特殊的线性表，其特殊性体现在 串中每个元素是一个字符 ；两个串相等的充分必要条件是 长度相等且对应位置的字符相同 。2空格串是 由一个或多

50、个空格字符组成的串 ，其长度等于 空格的个数 。3串的两种最基本的存储方式是 顺序存储方式 和 链接存储方式 。4空串是 零个字符的串 ，其长度等于 零 。二、选择1设串S=ABCDEFG,t=HIJK，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串S的从序号i的字符开始的j个字符组成的子串，则con(subs(s,4,2),con(t,subs(s,6,2)的结果串是（ A ）。 ADEHIJKFG BDEFGHIJK CDEHIFGJK DFGDEHIJK2设串s=A SAMPLE，t=APP，函数subs(s,i,j)返回串S的从序号i的字符开始的j个字符组成的子

51、串，repl(s,s1,s2)返回用串s2替换串s中的子串s1，则repl(s,subs(s,3,4),t)的结果串是（ B ）。 AA SAPPLE BA APPLE CA SAMPAPP DA APP3以下叙述中正确的是（ A ） A串是一种特殊的线性表B串的长度必须大于零C串中元素只能是字母D空串就是空白串第五章 数组要求、目标：了解数组的基本基本概念、性质；掌握二维数组以行序和列序为主序时aij元素存储地址的计算；掌握矩阵的压缩存储、稀疏矩阵的三元组存储及转置运算的实现一、概述1数组：具有相同数据类型的若干元素构成的有序集合2性质：元素个数固定；元素类型相同；每个元素有惟一的下标值；是

52、随机存取结构3二维数组的表示形式（mn）二维数组可看作是一个线性表，其每个元素也是一个线性表多维数组的基本操作是存取元素和修改元素值，不能进行插入和删除操作二、数组的存储（mn）1一维数组的存储设有定义#define 100int aM; 则第i个元素的地址为：Loc(ai)=Loc(a0)+i*d 其中d为每个元素所占的字节数，0iM2二维数组的存储1）以行序为主序（第i行j列）的元素地址计算下标从0开始loc(ai,j)=loc(a0,0)+(i*n+j)*d 例：设有float a54; 起始地址为2000，求a32的地址loc(a3,2)=loc(a0,0)+(i*n+j)*d=200

53、0+(3*4+2)*4=2056下标不从0开始(Ac1d1,c2d2)loc(ai,j)=loc(a c1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*d 例：设有float a-2030,-3020, 起始地址为200，求a2518的地址loc(a25,18)=loc(a -20,-30)+(25+20)*(20+30+1)+(18+30)*4 =200+45*51+48*4 =95722）以列序为主序（第i行j列）的元素地址计算下标从0开始loc(ai,j)=loc(a0,0)+(j*m+i)*d例：设有float a54; 起始地址为2000，求a32的地址loc(a3,2)

54、=loc(a0,0)+(j*n+i)*d=2000+(2*5+3)*4=2052下标不从0开始(Ac1d1,c2d2)loc(ai,j)=loc(a c1,c2)+(j-c2)*(d1-c1+1)+(i-c1)*d 例：设有float a-2030,-3020, 起始地址为200，求a-18-25的地址loc(a-18,-25)=loc(a -20,-30)+(-25+30)*(30+20+1)+(-18+20)*4 =200+5*51+2*4 =1228三、特殊矩阵的压缩存储1压缩存储：为多个值相同的非零元素只分配一个存储空间，对零元素不分配空间2特殊矩阵：值相同的非零元素或零元素的分布有一

55、定规律的矩阵3对称矩阵：若一个n阶方阵A中的元素满足 ai,j=aj,i (0i,jn-1)则称其为n阶对称矩阵4对角矩阵：若一个n阶方阵满足其所有非零元素都集中在以主对角线为中心的带状区域中，则称其为n阶对角矩阵5三角矩阵的压缩存储（非对称）1）下三角矩阵：上三角（不包括主对角线）中的元素都是0的n阶方阵2）压缩存储方法只存储下三角的元素，其余的0不存储下三角矩阵的n2个元素压缩到个元素的存储单元中，可用一维数组s0n(n+1)/2存放下三角矩阵中的元素元素个数：按行序为主序进行存储3）ai,j的地址计算(行序 ij)aij与sk的对应关系 当上三角为常数C时用此单元存放该常数 计算地址lo

56、c(ai,j)=loc(a0,0)+ *d 例：下三角矩阵A18，18按行存储，起始地址为1000，每个元素占4个字节，求A7,5的地址loc(a7,5)=loc(a0,0)+ *d =1000+6*(6+1)/2+4*4 =11006对角矩阵的压缩存储1）特点：非零元素分布在主对角线和其它对角线上，其余元素为02）半带宽：主对角线上面或下面的对角线条数，记为b3）带宽：所有对角线的条数，记为2b+14)m对角矩阵含义：带宽为m5）当0i,jn-1且|i-j|b时，其元素ai,j=06）压缩存储只存储带状区域中的(2b+1)n-b(b+1)个元素，其余区域外的元素不存储按行存储，第1行、最后一

57、行存b+1个元素，其余各行当作有(2b+1)个元素，若不中2b+1则在行前或行后补上一些元素，补上的位置空留，共需(2b+1)n-2b个存储单元，多用b(b-1)个单元7）地址计算用一维数组来存放带状矩阵，则sk与ai,j对应关系：k=i(2b+1)+j-i计算ai,j 的地址loc(ai,j)=loc(a0,0)+i(2b+1)+(j-i)*d 例：将A1100，1100的三对角矩阵按行优先存入一维数组B1298中，A中元素a66,65在B中的位置k为多少？k=i(2b+1)+j-i=(66-1)(2*1+1)+(65-1)-(66-1)=194即k=194+1=195四、稀疏矩阵1定义：大

58、多数元素值为零，且非零元素的分布没有规律的矩阵2形式：（67）3稀疏矩阵的三元组表示1）压缩方法只存储非零元素，同时保存非0元素的行号、列号，用一个三元组（i,j,aij）表示一个非零元素，所有非零元素构成三元组线性表，按行号的递增次序存放在一个由三元组组成的二维数组中例：上面矩阵的三元组线性表为：(0,1,12),(0,2,9),(2,0,-3),(2,5,14),(3,2,24),(4,1,18),(5,0,15),(5,3,-7)2）三元组顺序表（不具有随机存取功能）：用顺序存储结构表示三元组表3）三元组表示方法若有t个非0元素，可定义一个(t+1)3的二维数组at+13，其中第0行分别

59、存放矩阵的行数、列数和非0元素的个数，从第1到t行依次存放t个非0元素对应的t个三元组例：上例中t=8,可定义a93，其存储形式为：a0120678101122029320-342514532246411875015853-74）建立三元组的存储方法#define N 100int aN3;void create(int Amn, int BN3)int I,j,k=1;for(I=0; Im; I+)for(j=0; j0)个结点组成的有限集合（记为T），在一棵树中应满足：1）有且仅有一个根结点2）其余的结点可分为m(m0)个互不相交的有限集合T0，T1，Tm-1其中每个集合又可以是一棵树，

60、称这些集合为根结点的子树2说明：一棵树至少有一个结点；除根结点外，每个结点有且仅有一个直接前驱，可有任意个直接后继，根结点无前驱3结点的度和树的度ABKJIHGFEDC11）结点的度：某结点子树的个数为该结点的度，即其后继结点数例：结点A的度：4 结点B的度：0 结点C的度：2 结点E的度：12）树的度：树中各结点度的最大值，度为m的树称m次（叉）树例：上图树的度为：44分支结点与叶结点1）分支结点（非终端结点）：度不为零的结点。每个结点的分支数就是该结点的度数，度为1称单分支结点，度为2称双分支结点例：上图中分支结点有：A、C、E、H2）叶结点（终端结点）：度为零的结点。 例：上图中叶结点有