综合应用题利用顺序表的操作，实现以下的函数：1. 从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。
实现删除具有最小值元素的函数
bool deleteMin(SeqList&L,DataType&value){
if(L.n==0)return false; //表空,中止操作返回
value=L.data[0];int i,pos=0;//假定1号元素的值最小
for(i=2;i＜=L.n;i++) //循环,寻找具有最小值的元素
if(L.data[i-1]＜value) //让value记忆当前具有最小值的元素
{value=L.data[i-1];pos=i-1;}
for(int j=pos+1;j＜L.n;j++)L.data[j-1]=L.data[j];
L.n--;
return true;
}
2. 从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。
实现删除第i个元素的函数(设第i个元素在data[i-1],i=1,2,3,…,n)
bool deleteNo_i(SeqList &L,int i,DataType&value){
if(L.n==0||i＜1||i＞=L.n)return false; //表空或i不合理,终止操作
value=L.data[i-1];
for(int j=i;j＜L.n;j++)L.data[j-1]=L.data[j];
L.n--;
return true;
}
3. 向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。
实现向第i个位置插入一个新的元素x的函数(设第i个元素在data[i-1]，i=1，2，3，…，n)
bool InsNo_i(SeqList&L,int i,DataType value){
if(L.n==L.maxSize||i＜1||i＞L.n+1);//表满或参数i不合理,中止操作
return false;
for(i=L.n;j＞=i;j--)L.data[j]=L.data[j-1];
L.data[i-1]=value;L.n++:
return true;
}
4. 从顺序表中删除具有给定值x的所有元素。
从顺序表中删除具有给定值x的所有元素
void deleteValue(SeqList&L,DataType value){
int i,j;
for(i=L.n;i＞=1;i--) //循环,寻找具有值x的元素并删除它
if(L.data[i-1]==value){//删除具有值x的元素
for(j=i;j＜L.n;j++)L.data[j-1]=L.data[j];
L.n--;
}
}
5. 从顺序表中删除其值在给定值s与t之间(要求s小于t)的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。
实现删除其值在给定值s与t之间(要求s小于t)的所有元素的函数
bool deleteNo_sto_t(SeqList &L,DataType s,DataType t){
if(L.n==0)return false;
if(s＞t){DataType temp=s;s=t;t=temp;} //保持s≤t
int i,j;
for(i=L.n-1;i＞=1;i--) //循环,寻找在给定范围内的元素并删除它
if(L.data[i-1]＞=s&&L.data[i-1]＜=t){//删除
for(j=i;j＜L.n;j++)
L.data[j-1]=L.data[j];
L.n--;
}
return true;
}
6. 从有序顺序表中删除其值在给定值s与t之间(要求s小于t)的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。
实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数
bool deleteNo_sto_t1(SeqList&L,DataType s,DataType t){
if(L.n==0)return false;
if(s＞t){DataType temp=s;s=t;t=temp;} //保持s≤t
int i,j,k,u;
for(i=1;i＜=L.n&&L.data[i-1]＜s;i++); //寻找值≥s的第一个元素
if(i＞L.n)return false; //没有值≥s的元素
for(j=i;j＜=L.n&&L.data[j-1]＜=t;j++); //寻找值＞t的第一个元素
for(k=j,u=i;k＜=L.n;k++,u++) //前移,填补被删元素位置
L.data[u-1]=L.data[K-1];
L.n=L.n-j+i:
return true;
}
7. 将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。
实现将两个有序顺序表合并成一个新的有序顺序表的函数
bool Merge(SeqList&A,SeqList&B,SeqList&C){
//合并有序顺序表A与B成为一个新的有序顺序表C。
if(A.n+B.n＞C.maxSize)return false;
int i=1,j=1,k=1;
while(i＜=A.n&&j＜=b.n) //循环,两两比较,小者存入结果表
if(A.data[i-1]＜=B.data[j-1])
{C.data[k-1]=A.data[i-1];i++;}
else
{C.data[k-1]=B.data[j-1];j++;k++}
while(i＜=A.n){C.data[k-1]=A.data[I-1];i++;k++}
while(j＜=B.n){C.data[k-1]=B.data[j-1];j++;k++}
C.n=k;
return true;
}
8. 从有序顺序表中删除所有值重复的元素，使表中所有元素的值均不相同。
实现从有序顺序表中删除所有值重复的元素的函数
bool deleteSame(SeqList&L){
if(L.n==0)return false;
int i=1,j;
while(i＜=L.n){ //循环检测
while(L.data[i-1]!=L.data[i])i++; //寻找重复的元素i与元素i+1
j=i+2; //发现重复
while(L.data[i-1]==L.data[j-1])j++;
for(k=i+1,u=j;u＜=L.n;k++,u++)
L.data[k-1]=L.data[u-1];
i++:
}
return true;
}
[解析] 通过顺序表的定义及基本特性来完成。
9. 线性表的每一个表元素是否必须类型相同?为什么?
线性表每一个表元素的数据空间要求相同，但如果对每一个元素的数据类型要求不同时可以用等价类型(union)变量来定义可能的数据元素的类型。如
Typedef union{ //联合
int integerInfo; //整型
char charInfo; //字符型
float floatInfo; //浮点型
}info;
利用等价类型，可以在同一空间(空间大小相同)indo中存放不同数据类型的元素。但要求用什么数据类型的变量存，就必须以同样的数据类型来取。
10. 设有一个带表头结点的链表，结点的结构为(data，link，sort)，其中data为整型值域，link和sort都是指针域。已知链表所有结点都已通过link域指针链接起来，构成单链表，且所有结点数据的值互不相同。试编写一个算法，利用sort域把所有结点按照数据的值从小到大的顺序链接起来。
算法设计的基本思路是：按照链表插入排序的思想，将sort链初始化为只有一个结点(首元结点)的有序单链表，然后扫描link链的每个结点，一边扫描一边将结点按其值插入到sort链中。算法实现如下：
Typedef struct node{ //链表结点类型定义
int data; //数据域
struct node*link; //原有单链表的链接指针
struct node*sort; //将生产的有序单链表的链接指针
}DLNode;
Typedef DLNode*DList; //链表类型定义
Void sortList(DList list){
//利用链表list的sort域建立按照结点数据值升序链接的单链表
List-＞sort=list-＞link:list-＞sort-＞NULL;
DLNode*p,*prep,*s=list-＞link-＞link;
while(s!=NULL){
p=list-＞sort;prep=list;
while(p!=NULL&&P-＞data＜s-＞data)
//寻找sort链中插入位置
{prep=p;p=p-＞soft;}
prep-＞sort=s;s-＞sort=p; //链入sort链
s=s-＞link; //处理link链的下一结点
}
}
此算法有一个嵌套的循环。其中，外层循环执行n-1次，而内层循环的执行次数取决于数据值。最好情况是原链表中所有结点的数据值都按降序排列，每次插入时仅比较1次；最坏情况是原链表中所有结点的数据值都按升序排列，这样在插入第i(2≤i≤n)个结点时需要比较i-1次。所以，最好情况下算法的数据比较次数为O(n)，最坏情况下算法的数据比较次数为O(n2)。
算法的数据移动次数为0，因为链表插入只需修改结点指针，不需移动元素。
11. 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。
实现定位函数的算法
LinkedNode*Locate(LinkList L,int i){
//取得单链表中第i个结点地址,i从0开始计数,i=0定位于表头结点
if(i＜0)return NULL; //位置i在表中不存在
LinkedNode *p=L;Int k=0; //从表头结点开始检测
while(p!=NULL&&k＜i) //p==NULL表示链短,无第i个结点
{p=p-＞link;k++;}
return p; //否则k==i,返回第i个结点地址
}
12. 求最大值函数：Max：通过一趟遍历在单链表中确定值最大的结点。
实现求最大值的函数
LinkedNode *Max(LinkList L){
//在单链表中进行一趟检测,找出具有最大值的结点地址,如果表空,返回指针NULL
if(L-＞link==NULL)return NULL; //空表,返回指针NULL
LinkedNode*pmax=L-＞link,p=L-＞link-＞link;
//假定头结点中数据值最大
while(p!=NULL){ //循环,下一个结点存在
if(p-＞data＞pmax-＞data)pmax=p;
//pmax记忆找到的具有最大值结点
p=p-＞link; //检测下一个结点
}
return pmax;
}
13. 统计函数Count：统计单链表中具有给定值x的所有元素。
实现统计单链表中具有给定值x的所有元素的函数
int Count(LinkList L,DataType x){
//在单链表中进行一趟检测,统计具有给定值x的结点,如果表空,返回0
int n=0;
LinkedNode*p=L-＞link; //从第一个结点开始检测
while(p!=NULL){ //循环,想结点存在
if(p-＞data==x)n++; //找到一个,计数器加1
p=p-＞link; //检测下一个结点
}
return n;
}
14. 建立函数Create：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中各元素的次序相同，要求该程序的时间复杂度为O(n)。
实现从一维数组a[n]建立单链表的函数
void Create(LinkList&L,DtatType a[ ],int n){
//根据书中a[n]建立一个单链表,单链表中各元素次序与a[n]中各元素次序相同
LinkedNode*rear;
L=rear=new LinkedNode; //创建表头结点
for(int i=0;i＜n;i++){
rear-＞link=new LinkedNode; //链入一个新结点,值为a[i]
rear=rear-＞link; //rear指向链中尾结点
rear-＞data=A[i];
}
rear-＞link=NULL;
}
采用递归方法实现时，需要通过引用参数将已建立的单链表各个结点链接起来。为此，在递归地扫描数组a[n]的过程中，先建立单链表的各个结点，在推出递归时将结点的p(被调用层的形参)带回上一层(调用层)的实参p-＞link。
void Create(DataType a[ ],int n,int i,LinkedNode*&p){
if(i==n)p=NULL;
else{
p=new LinkedNode;
p-＞data=A[i];p-＞link=NULL; //建立链表的新结点
createList(A,n,i+1,p-＞link);
//递归返回时通过p-＞link链接
}
}
外部调用递归过程的语句为:
L=new LinkedNode; //建立表头结点
Create(a,n,0,L-＞link); //递归建立单链表
15. 整理函数Tidyup：在非递减有序的单链表中删除值相同的多余结点。
实现在非递减有序的单链表中删除值相同的多余结点的函数
void Tidyup(LinkList L){
LinkedNode*p=L-＞link,temp; //检测指针p指向首元结点
while(p!=NULL&&p-＞link!=NULL) //循环检测链表
if(p-＞data==p-＞link-＞data){
temp=p-＞link:p-＞link=temp-＞link;
delete temp;
}
else p=p-＞link; //指针p进到链表下一个结点
}
[解析] 针对带表头结点的单链表，试编写下列函数：
16. 求链表中的最大整数。
求链表中的最大整数
int Max(LinkedNode*first){
//递归算法:求链表中的最大值
if(first-＞link==NULL)return first-＞data;
//链表仅一个结点,其值即所求
int temp=Max(first-＞link); //否则递归求后继链表中最大值
if(first-＞data＞temp)return first-＞data;
//再与首元之值比较取大者
else return temp;
}
17. 求链表的结点个数。
求链表的结点个数
int Num(LinkedNode*first){
//递归算法:求链表中结点个数
if(first==NULL)return 0; //空链表结点个数为0
return 1+Num(first-＞link);//否则求后继链表结点数再加1
18. 求所有整数的平均值。
求所有整数的平均值
float Avg(LinkedNode*first,int&n){
//递归算法:求链表中所有元素平均值
if(first-＞link==NULL) //链表仅一个结点
{n=1;return(float)(first-＞data);} //其值即所求
else{ //否则
float Sum=Avg(first-＞link,n)*n; //先递归求后继链表的平均值
n++; //再计算总和
return(first-＞data+Sum)/n;
}
}
19. 用单链表存储多项式的结构定义如下：
Typedef struct Term{ //多项式的项
float coef; //系数
int exp; //指数
struct Term
*link;//链指针
}
*Polynomial;
试编写一个算法，输入一组多项式的系数和指数，按指数降幂的方式建立多项式链表，要求该链表具有表头结点。如果输入的指数与链表中已有的某一个项的指数相等，则新的项不加入，并报告作废信息。整个输入序列以输入系数为0标志结束。算法的首部为Polynomial createPoly()；
本题程序使用了一些C++的常用语句，如：“＜＜”输出符，“＞＞”输入符，“cout”输出到屏幕，“cin”从键盘输入，“endl”换行格式符，“new”动态存储分配。
Polynomial createPoly(){
struct pnode*head,*p,*pre,*s;
float c;int e,i=0;
cout ＜＜”建立一个多项式的单链表”＜＜endl; //提示
head=new Term; //创建表头结点和表头指针
head-＞exp=-1;head-＞link=NULL; //表头结点的exp标志为-1
while(1){ //创建结点
cout＜＜”输入第”＜＜++i＜＜”个项:”; //提示:输入第i个项
cin＞＞c＞＞e; //输入:c系数,e指数
cout＜＜endl;
if(c==0)break; //输入系数为0,退出
S=new Term;s-＞coef:c;s-＞exp=e; //创建结点
p=head;pre=NULL; //寻找按升幂插入的位置
while(p!=NULL&&P-＞exp＞e){pre=p;p=p-＞link;}
if(p!=NULL&&p-＞exp==e) //指数与链中某项指数相等
cout＜＜”输入项的指数重复,此次输入作废!”＜＜endl;
else{s-＞link=p;pre-＞link=s;} //按升幂插入
}
return head;
}
P(x)=am-1+am-2+…+a0
用长度为m的单链表表示为(tm-1，tm-2，tm-3，…，t1，t0)。其中，m是多项式P(x)中非零项(term)的个数，每一个ti(0≤i≤m-1)是P(x)的一个非零项，它由三个数据成员coef、exp和link组成，coef是系数(浮点型)，exp是指数(整型)，link是链接指针。各个项的指数ei按递减顺序排列：em-1＞em-2＞…>e0＞0。20. 试描述多项式的数据结构(m可以不出现在定义中)。
一元多项式的结构定义：
Typedef struct Term{
float coef;int exp;
struct Term*link:
}*Polynomial;
21. 给出在多项式中插入新项的算法Insert。该算法的功能是：如果多项式中没有与新项的指数相等的项，则将此新项插入到多项式链表的适当位置；如果多项式中已有与新项的指数相等的项，则将它们合并。
多项式的插入算法：
void Insert(Polynomial first,float c,int e){
//在多项式链表first中插入系数为c，指数为e的新项
Term*pa=first,*pb=NULL;
while(pa!=NULL&&pa-＞exp＞e){pb=pa;pa=pa-＞link;}
if(pa-＞exp==e){ //多项式中有与新项指数相等的项
if(pa-＞coef+c!=0)pa-＞coef=pa-＞coef+c; //合并
else{pb-＞link=pa-＞link;delete pa;} //或删除
}
else{ //多项式中无与新项指数相等的项
Term*pc=new Term; //创建
pc-＞exp=e,pc-＞coef=c;
if(pb==NULL){pc-＞link=first;first=pc;}
//链接：在首部
else{pb-＞link=pc;pc-＞link=pa;} //链接:在链中
}
}
22. 利用这个插入算法给出多项式乘法的实现算法。
多项式乘法的实现算法：
void MUL(Polynomial &A,Polynomial &B,Polynomial &C){
//计算C=A×B.
Term*pa,*pb;
pb=B;c=NULL;
while(pb!=NULL){
pa=A;
while(pa!=NULL){
Insert(c,pa-＞coef*pb-＞coef,pa-＞exp+pb-＞exp);
pa=pa-＞link;
}
pb=pb-＞link;
}
}
23. 没有一个不带表头结点的单链表，表头指针为head。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转。要求逆转结果链表的表头指针head指向原链表的最后一个结点。
void Inverse (LinkList & head){
//head设为引用型,因要返回head改变后的值
if(head==NULL)return; //空表无需逆转
LinkedNode*p=head-＞link,*pr=NULL;
while(p!=NULL){
head-＞link=pr; //逆转head指针
pr=head;head=p;p=p-＞link; //指针前移
}
head-＞link=pr;
}
24. 试设计一个实现下述要求的Locate运算的函数。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针lLink、指向后继结点的指针rLink、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Loeate(L，x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保存按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。
bool Locate(DblList &L,Type x){
//在双向链表中查找值为x的结点,找到后该结点被搬到适当位置,函数返回true,
//否则函数返回false。
DblNode*p=L-＞rLink,*q;
while (p!=NULL&&p-＞data!=x)p=p-＞rLink;
if(p!=NULL){ //链表中存在x
p-＞freq++;q=p; //该结点的访问频度加1
q-＞iLink-＞rLink=q-＞rLink; //从链表中摘下这个结点
q-＞rLink-＞ILink=q-＞iLink;
p=q-＞lLink; //寻找重新插入的位置
while (p!=L&&q-＞freq＞p-＞freq) p=p-＞lLink;
q-＞rLink=p-＞rlink;q-＞llink=p; //插入在p之后
p-＞rLink-＞lLink=q;p-＞rLink=q;
return true;
}
else return false; //没找到
深色：已答题 浅色：未答题