数据结构简明教程
的地址必须是连续的。其优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。
链式存储结构中，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。其优点是插入或删除元素时很方便，使用灵活；缺点是存储密度小，存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
（2）对于表长为n的顺序表，在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需要移动的元素的平均个数为多少？删除一个元素所需要移动的平均个数为多少？
答：插入一个元素所需要移动的元素的平均个数为(n-1)/2，删除一个元素所需要移动的平均个数为n/2。
（3）在链表中设置头结点的作用是什么？
答：在链表中设置头结点后，不管链表是否为空表，头结点指针均不空，并使得对链表的操作（如插入和删除）在各种情况下统一，从而简化了算法的实现过程。
（4）对于双链表和单链表，在两个结点之间插入一个新结点时需修改的指针各为多少个？
答：对于双链表，在两个结点之间插入一个新结点时，需修改前驱结点的next域、后继结点的prior域和新插入结点的next、prior域。所以共修改4个指针。
对于单链表，在两个结点之间插入一个新结点时，需修改前一结点的next域，新插入结点的next域。所以共修改两个指针。
（5）某含有n（n>1）结点的线性表中，最常用的操作是在尾结点之后插入一个结点和删除第一个结点，则采用以下哪种存储方式最节省运算时间。
①单链表；
②仅有头指针不带头结点的循环单链表； ③双链表；
④仅有尾指针的循环单链表。
答：在单链表中，删除第一个结点的时间复杂度为O(1)。插入结点需找到前驱结点，所以在尾结点之后插入一个结点，需找到尾结点，对应的时间复杂度为O(n)。
在仅有头指针不带头结点的循环单链表中，删除第一个结点的时间复杂度O(n)，因为删除第一个结点后还要将其改为循环单链表；在尾结点之后插入一个结点的时间复杂度也为O(n)。
在双链表中，删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点，也需找到尾结点，对应的时间复杂度为O(n)。
在仅有尾指针的循环单链表中，通过该尾指针可以直接找到第一个结点，所以删除第一个结点的时间复杂度为O(1)；在尾结点之后插入一个结点也就是在尾指针所指结点之后插入一个结点，时间复杂度也为O(1)。因此④最节省运算时间。
练习题及参考答案 4. 算法设计题
（1）设计一个高效算法，将顺序表的所有元素逆置，要求算法空间复杂度为O(1)。 解：遍历顺序表L的前半部分元素，对于元素L.data[i]（0≤i＜L.length/2），将其与后半部分对应元素L.data[L.length-i-1]进行交换。对应的算法如下：
void reverse(SqList &L) { }
int i; ElemType x;
for (i=0;i x=L.data[i]; //L.data[i]与L.data[L.length-i-1]交换 L.data[i]=L.data[L.length-i-1]; L.data[L.length-i-1]=x; 本算法的时间复杂度为O(n)。 （2）设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。 解：对于顺序表L，用i从1开始遍历其元素，设L.data[0..j]（j的初值为0）中没有重复的元素。检测L.data[i]（j void delsame(SqList &L) { } int i,j=0,k; for (i=1;i L.length=j+1; //顺序表长度置新值 k=0; while (k<=j && L.data[k]!=L.data[i]) { } k++; //表示L.data[i]和L.data[0..j]中所有元素都不相同 j++; L.data[j]=L.data[i]; if (k>j) //L为引用型参数 本算法的时间复杂度为O(n2)，空间复杂度为O(1)。 （3）设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。 解：在有序顺序表L中，所有重复的元素应是相邻存放的，用k保存不重复出现的元素个数，先将不重复的有序区看成是L.data[0..0]，置e=L.data[0]，用i从1开始遍历L的所有元素：当L.data[i]≠e时，将它放在L.data[k]中，k增1，置e=L.data[i]，最后将L的length置为k。对应的算法如下： void delsame1(SqList &L) { int i,k=1; ElemType e; 7 //L为引用型参数 //k保存不重复的元素个数 数据结构简明教程 } e=L.data[0]; for (i=1;i L.length=k; //顺序表长度置新值 if (L.data[i]!=e) { } k++; e=L.data[i]; //只保存不重复的元素 L.data[k]=L.data[i]; 本算法是一个高效算法，其时间复杂度为O(n)，空间复杂度为O(1)。如果每次遇到重复的元素，都通过移动其后所有元素来删除它，这样的时间复杂度会变成O(n2)。 （4）设计一个算法删除单链表L中第一个值为x的结点。 解：用p、q遍历整个单链表，p指向*q的前驱结点，q用于查找第一个值为x的结点，当找到后将*q结点删除，返回1；否则返回0。对应的算法如下： int delx(SLink *&L,ElemType x) { } SLink *p=L,*q=p->next; { } if (q!=NULL) { } else return 0; //未找到值为x的结点 free(q); return 1; //找到值为x的结点 p->next=q->next; p=q; q=q->next; //p指向*q的前驱结点 while (q!=NULL && q->data!=x) （5）设计一个算法判定单链表L是否是递增的。 解：判定链表L从第2个结点开始的每个结点的值是否比其前驱的值大。若有一个不成立，则整个链表便不是递增的；否则是递增的。对应的算法如下： int increase(SLink *L) { SLink *pre=L->next,*p; p=pre->next; { } return 1; while (p!=NULL) if (p->data>=pre->data) { } else return 0; pre=p; p=p->next; //若正序则继续判断下一个结点 //pre、p同步后移 //pre指向第一个数据结点 //p指向*pre结点的后继结点 } 练习题及参考答案 （6）有一个整数元素建立的单链表A，设计一个算法，将其拆分成两个单链表A和B，使得A单链表中含有所有的偶数结点，B单链表中所有的奇数结点，且保持原来的相对次序。 解：采用重新单链表的方法，由于要保持相对次序，所以采用尾插法建立新表A、B。用p遍历原单链表A的所有数据结点，若为偶数结点，将其链到A中，若为奇数结点，将其链到B中。对应的算法如下： void Split(SLink *&A,SLink *&B) { } SLink *p=A->next,*ra,*rb; ra=A; B=(SLink *)malloc(sizeof(SLink)); //建立头结点 rb=B; { } ra->next=rb->next=NULL; //r总是指向B链表的尾结点 //偶数结点 //将*p结点链到A中 while (p!=NULL) if (p->data%2==0) { } else { } //奇数结点 //将*p结点链到B中 rb->next=p; rb=p; p=p->next; ra->next=p; ra=p; p=p->next; 本算法的时间复杂度为O(n)，空间复杂度为O(1)。 （7）有一个有序单链表（从小到大排列），表头指针为L，设计一个算法向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序。 解：先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。对应的算法如下： void inorderList(SLink *&L,ElemType x) { SLink *s,*p,*q; s=(SLink *)malloc(sizeof(SLink)); //建立一个待插入的结点 s->data=x;s->next=NULL; if (L==NULL || x q=L; //寻找插入位置,p指向待比较的结点,q指向p的前驱结点 p=q->next; 9 s->next=L; L=s; //把*s结点插入到头结点之后 数据结构简明教程 } } while (p!=NULL && x>p->data) if (x>p->data) { } //将s结点插入到*q和*p之间 q=p; p=p->next; //若x小于p所指结点的data域值 s->next=p; q->next=s; （8）有一个单链表L，其中可能出现值域重复的结点，设计一个算法删除值域重复的结点。并分析算法的时间复杂度。 解：用p遍历单链表，用r遍历*p结点之后的结点，q始终指向*r结点的直接前驱结点，若r->data==p->data，则删除*r结点，否则q、r同步后移一个结点。对应的算法如下： void dels1(SLink *&L) { } SLink *p=L->next,*q,*r,*t; while (p!=NULL) { } q=p; r=q->next; while (r!=NULL) { } p=p->next; if (r->data==p->data) //r指向被删结点 { } else { } q=r; r=r->next; t=r->next; q->next=t; free(r); r=t; 本算法的时间复杂度为O(n2)。 （9）有一个递增有序单链表（允许出现值域重复的结点），设计一个算法删除值域重复的结点。并分析算法的时间复杂度。 解：由于是有序表，所以相同值域的结点都是相邻的。用p遍历递增单链表，若*p结点的值域等于其后结点的值域，则删除后者。对应的算法如下： void dels(SLink *&L) { SLink *p=L->next,*q; while (p->next!=NULL) { if (p->data==p->next->data) //找到重复值的结点