数据结构复习

1、数据结构复习第1章绪论基本知识点：数据结构和算法的概念重点：数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系；算法时间复杂度分析。难点：分析算法的时间复杂度。例题1_1：用C/C+语言描述下列算法，并给出算法的时间复杂度。（1）求一个n阶方阵的所有元素之和。（2）对于输入的任意三个整数，将它们按照从小到大的顺序输出。（3）对于输入的任意n个整数，输出其中的最大和最小元素。解：（1）算法如下：int sum(int Ann, int n) int i, j, s=0;for(i=0;in;i+)for(j=0;jb) if(bc) coutcbc) coutbca;else cout

2、bac;else if(ca) coutcab; else if(cb) coutacb; else coutabc;本算法的时间复杂度为O(1)。（3）算法如下：void maxmin(int a, int n, int &max, int &min) int k; min=a0; max=a0;for(k=1;kmax) max=ak; else if(akmin) min=ak;本算法的时间复杂度为O(n)。第2章 线性表基本知识点：线性表的逻辑结构特征，线性表的基本运算，线性表的两种存储结构以及为两种存储结构下线性表基本运算算法的实现，顺序表和链表的优缺点比较。重点：掌握线性表的定义和

3、特点，线性表的存储结构；顺序表和链表的组织方法和算法设计。难点：单链表和双链表的各种算法设计。例题2_1：在线性表的如下链表存储结构中，若未知链表头结点的指针，仅已知p指针指向的结点，能否将它从该结构中删除？为什么？（1）单链表；（2）双链表；（3）循环链表。答：（1）不能删除。因为无法知道*p结点的前趋结点的地址。（2）能删除。由*p结点的左指针找到其前趋结点的地址，然后实施删除。（3）能删除。循环查找一周，可以找到*p结点的前趋结点的地址，然后实施删除。例题2_2：已知长度为n的线性表A采用顺序存储结构，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为i

4、tem的数据元素。解：存储结构如下：typedef struct SeqList ElemTyep *elem;int length;int ListSize;SeqList; 用k记录顺序表A中等于item的元素个数，边扫描A边统计k，并将不为item的元素向前移动k个位置，最后修改A的长度。算法如下：void DeleteNode(SeqList &A, ElemType item) int k=0, i=0;while(inext;A=C; A-next=0; B=new LNode; B-next=0; pa=A; pb=B;while(p) s=p-next; pa-next=p;

5、pa=p; p=s; s=s-next;if(p) pb-next=p; pb=p; p=s; s=s-next;pa-next=0; pb-next=0;C=0; /C已经被拆分，拆分后不再存在。/A和B采用尾插法建立。例题2_4：设计一个算法，将x插入一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。解：设存储结构如下：typedef struct SeqListElemType *elem;int length;int ListSize;SeqList;算法如下：void fun(SeqList &L, ElemType x) int i; if(L.l

6、ength=L.ListSize) ElemType *p=new ElemType2*L.ListSize; L.ListSize=2*L.ListSize; for( i=0;i=0 & xdata=x;pre=L;while(pre-next & pre-next-datanext;p-next=pre-next;pre-next=p;例题2_6：设计一个算法判断带头结点的单链表L是否是按值递增的。解：设存储结构如下：typedef struct LNodeElemType data;struct LNode *next;LNode, *LinkList;算法如下：int IsIncre

7、ase(LinkList &L)/若递增返回1，否则返回0。 LNode *pre, *p;p=L-next; if(p=0) return 1;while(p-next)pre=p; p=p-next; if(pre-datap-data) return 0;else p=p-next;return 1;例题2_7：分别设计有关单链表、单循环链表、双链表、双循环链表的插入、删除、查找、遍历等算法。第3章 栈和队列基本知识点：理解栈和队列的定义、特点及与线性珠的异同；掌握顺序栈和链栈的组织方法，栈满、栈空的判断及其描述；掌握顺序队列、循环队列和链队列的组织方法，队满、队空的判断及描述。递归的相

8、关概念。重点：栈和队列的特点，顺序栈和链栈的基本运算的实现算法；顺序队列、循环队列和链队列的基本运算算法。递归模型，递归算法的执行过程和递归设计思想。难点：灵活运用栈和队列设计解决应用问题的算法。将递归算法转化为非递归算法。例题3_1：设有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？答：要使C第一个且D第二个出栈，应是A入栈，B入栈，C入栈，C出栈，D入栈，D出栈，之后可以有以下几种情况：（1）B出栈，A出栈，E入栈，E出栈，输出序列为CDBAE；（2）B出栈，E入栈，E出栈，A出栈，输出序列为CDBEA；

9、（3）E入栈，E出栈，B出栈，A出栈，输出序列为CDEBA。例题3_2：假设以不带头结点的循环单链表表示队列，并且只设一个指针rear指向队尾结点，但不设头指针，请写出相应的队初始化、入队、出队和判队空的算法。解：设存储结构如下：typedef struct LNodeElemType data;struct LNode *next;LNode, *LinkQueue;则相应的算法如下：（1）队列的初始化void InitLinkQueue(LinkQueue &rear)rear=0;（2）入队列void EnQueue(LinkQueue &rear, ElemType x)LNode *

10、p=new LNode; p-data=x;if(rear=0) rear=p; rear-next=rear;else p-next=rear-next; rear-next=p; reat=p; （3）出队列void DeQueue(LinkQueue &rear, ElemType &x) if(rear=0) return;LNode *p=rear-next; x=p-data;if(rear=p) rear=0;else rear-next=p-next;delete p;（4）判别队列是否为空in QuEmpty(LinkQueue &rear) return rear=0; 第

11、4章串基本知识点：串的基本概念和串的基本运算。重点：串的顺序存储方法和串的链接存储方法；串的基本运算算法的实现。难点：模式匹配Brute-Force算法和KMP算法。例题4_1：两个串相等的充分必要条件是什么？答：两个串相等的充分必要条件是：两个串的长度相等且对应位置上的字符相等。例题4_2：空串和空格串有何区别?答：空串是指不含任何字符的串，其长度为0，空串是任意串的子串。空格串是指仅仅含有空格字符的串，其长度是串中空格字符的个数。例题4_3：设计在链串上实现判定两个串是否相等的算法。解：存储结构如下：typedef struct LNode char data; struct LNode

12、*next;LNode, *LinkString;算法如下：int Equal(LinkString &S, LinkString &T) LNode *ps=S, *pt=T;int flag=1;while(ps & pt & flag) if(ps-data!=pt-data) flag=0; pt=pt-next; ps=ps-next; if(ps | pt) return 0;else return flag;第5章数组和广义表基本知识点：数组的顺序存储结构；特殊矩阵的压缩存储方法；稀疏矩阵的压缩存储方法。广义表的定义及其与线性表的关系；广义表的存储结构。重点：数组的复杂算法设计。

13、广义表的存储结构以及基本运算的实现算法。难点：稀疏矩阵和各种存储结构及基本运算的实现算法。广义表的递归算法设计。例题5_1：编写一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。解：存储结构如下：typedef struct int i,j; /行下标和列下标。ElemType elem;Triple;typedef struct Triple dataMaxSize+1; /非0元三元组表，data0未用。int mu, nu, tu; /矩阵的行数、列数、非0元素个数。TSMatrix;算法如下：int Diagonal(TSMatrix &A, ElemType &sum)/用s

14、um返回对角线元素之和。int k; sum=0;if(A.mu!=A.nu) cout”不是正方阵，不能求对角线元素之和n”; return 0;for(k=1; kkey=x) return T; if(xkey) return FindX(T-left, x);else return FindX(T-right, x);非递归算法如下：LNode* FindY(BiSortTree &T, KeyType y)LNode *p=T; if(p=0 | p-key=y) return p;while(p)if(p-key=y) return p;else if(xkey) p=p-left;else p=p-right;return p;例题9_4：给出一组数据，要求用相应的方法构造哈希表