企业微信app_站长工具官方网_厦门seo百度快照优化_好f123网站

说明

• 本文参照严蔚敏《数据结构(C语言版)题集》一书中包含的问答题和算法设计题目，提供解答和算法的解决方案。
• 请读者在自己已经解决了某个题目或进行了充分的思考之后，再参考本解答，以保证复习效果。
• 由于作者水平所限，本解答中一定存在不少这样或者那样的错误和不足，希望读者们在阅读中多动脑、勤思考，争取发现和纠正这些错误，写出更好的算法来。

2.12 设$A=(a_1,\cdots ,a_m)$和$B=(b_1,\cdots ,b_n)$均为顺序表

$A^{\prime }$和$B^{\prime }$分别为$A$和$B$中除去最大共同前缀后的子表，
例如，$A=(x,y,y,z,x,z)$，$B=(x,y,y,z,y,x,x,z)$，
则两者中最大的共同前缀为$(x,y,y,z)$，
在两表中除去最大公共前缀后的子表分别为：
$A^{\prime }=(x,z)$和$B^{\prime }=(y,x,x,z)$。
若$A^{\prime }=B^{\prime }=$空表，则$A=B$；
若$A^{\prime }=$空表，而$B^{\prime }\ne$空表，或者两者均不为空表，
且$A^{\prime }$的首元小于$B^{\prime }$的首元，则$A<B$；否则$A>B$。
试写一个比较$A,B$大小的算法；
请注意：在算法中，不要破坏原表$A$和$B$，并且，也不一定先求得$A^{\prime }$和$B^{\prime }$才进行比较。

解：
用同一个下标变量控制两个线性表。注意你的算法对空表也应能正确执行。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10#define MAX_TEST_LENGTH 50
#define MAX_TEST_ELEM 26
typedef char ElemType;
typedef struct{ElemType *elem; // 存储空间基址int length; // 当前长度int listsize; // 当前分配的存储容量
} SqList; // 顺序表类型
typedef struct LNode{ElemType data;struct LNode *next;
} LNode, *LinkList; // 线性链表类型Status InitList_Sq(SqList *pL){// 构造一个空的线性表(*pL).elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!(*pL).elem) exit(OVERFLOW); // 存储分配失败(*pL).length = 0; // 空表长度为0(*pL).listsize = LIST_INIT_SIZE; // 初始存储容量return OK;
}// InitList_SqStatus ListInsert_Sq(SqList *pL, int i, ElemType e){// 在顺序线性表L中第i个位置之前插入新的元素e// i的合法值范围：[1,ListLength_Sq(L)+1]if(i<1 || i>((*pL).length+1)) return ERROR; // i值不合法if((*pL).length>=(*pL).listsize){ // 当前存储空间已满，增加分配ElemType *newbase = (ElemType *)realloc((*pL).elem,((*pL).listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase) exit(OVERFLOW); // 存储分配失败(*pL).elem = newbase; // 新基址(*pL).listsize += LISTINCREMENT; // 增加存储容量}ElemType *p = NULL;ElemType *q = &((*pL).elem[i-1]); // q为插入位置for(p=&((*pL).elem[(*pL).length-1]);p>=q;--p) *(p+1) = *p; // 插入位置及之后的元素右移*q = e; // 插入e++((*pL).length); // 表长增1return OK;
}// ListInsert_SqStatus FreeList_Sq(SqList *pL){// 释放线性表if(NULL!=(*pL).elem){free((*pL).elem);return OK;}else{return ERROR;}
}// FreeList_SqStatus rand_init_two_list(SqList *pL, SqList *qL){time_t t;int c1,c2,count = MAX_TEST_LENGTH;if(OK!=InitList_Sq(pL)) return ERROR;if(OK!=InitList_Sq(qL)) return ERROR;srand((unsigned)time(&t)); //初始化随机数发生器c1 = rand()%MAX_TEST_LENGTH;while(c1--){if(OK!=ListInsert_Sq(pL,1+rand()%((*pL).length+1),'A'+(rand()%MAX_TEST_ELEM)))return ERROR; // 随机找一个合法位置插入新随机元素}c2 = rand()%MAX_TEST_LENGTH;while(c2--){if(OK!=ListInsert_Sq(qL,1+rand()%((*qL).length+1),'A'+(rand()%MAX_TEST_ELEM)))return ERROR; // 随机找一个合法位置插入新随机元素}return OK;
}void display_two_list(SqList La, SqList Lb){int i;printf("List A:\n");if(!La.length) printf("List A is empty.");for(i=1;i<=La.length;i++){printf("%c",La.elem[i-1]);}printf("\nList B:\n");if(!Lb.length) printf("List B is empty.\n");for(i=1;i<=Lb.length;i++){printf("%c",Lb.elem[i-1]);}putchar('\n');
}void the_same_prefix(SqList *pL, SqList *qL){// 随机使两表有相同前缀time_t t;int len,choice;srand((unsigned)time(&t));len=(*pL).length<(*qL).length?(*pL).length:(*qL).length;len=rand()%(len+1);choice = rand()%2;if(choice) (*pL).length=(*qL).length=len;while(len--) (*pL).elem[len]=(*qL).elem[len];
}void test_list_null(SqList *pL, SqList *qL){// 随机将两表长度变为0，为空表 time_t t;srand((unsigned)time(&t));int choice = rand()%3;if(choice==0){(*pL).length=0;}else if(choice==1){(*qL).length=0;}else{(*pL).length=(*qL).length=0;}
}void free_two_list(SqList *pL, SqList *qL){if(OK==FreeList_Sq(pL))printf("\nFree List A success!");if(OK==FreeList_Sq(qL))printf("\nFree List B success!\n");
}int ListComp(SqList A,SqList B){int i;//比较字符表A和B,并用返回值表示结果,值为1,表示A>B;值为-1,表示A<B;值为0,表示A=Bfor(i=0;i<A.length&&i<B.length;i++)if(A.elem[i]!=B.elem[i])return A.elem[i]>B.elem[i]?1:-1;if(A.length==B.length) return 0;//当两个字符表可以互相比较的部分完全相同时,哪个较长,哪个就较大return A.length>B.length?1:-1;
}//ListCompint main(){SqList La,Lb;int result;if(OK==rand_init_two_list(&La,&Lb)){display_two_list(La,Lb);result=ListComp(La,Lb);if(result==1) printf("A>B\n");else if(result==-1) printf("A<B\n");else printf("A=B\n");putchar('\n');// 测试两表有相同前缀，有可能相等the_same_prefix(&La,&Lb);display_two_list(La,Lb);result=ListComp(La,Lb);if(result==1) printf("A>B\n");else if(result==-1) printf("A<B\n");else printf("A=B\n");putchar('\n');// 测试随机将其中一个表变空，或者两表都为空test_list_null(&La,&Lb);display_two_list(La,Lb);result=ListComp(La,Lb);if(result==1) printf("A>B\n");else if(result==-1) printf("A<B\n");else printf("A=B\n");free_two_list(&La,&Lb);}return 0;
}

2.13 试写一算法

在带头结点的单链表结构上实现线性表操作LOCATE(L,X)。

解：
上面用动态开辟空间建立和扩展数组，这里用数组来表达静态链表，为什么会这样？
这和我们通常遇到问题的规模有关，一般需要存在数组中可顺序随机存取的数据，
往往需要很大的空间，这样空间的大小往往是我们预料不到的，
所以不得不求助链式开辟，获得一个相对较大的堆空间，而不会形成碎片。
但是链表不一样，互相之间有链式关系的模式通常是有限的，其规模是可以预测到的，
比如树、图和网。所以，从动态数组到静态链表，它们各自取长补短、相辅相成。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;// 线性表的静态单链表存储结构
#define MAXSIZE 20
typedef int ElemType;typedef struct{ElemType data;int cur;
}component, SLinkList[MAXSIZE];#define MAX_TEST_ELEM 1000void InitSpace_SL(SLinkList space){// 将一维数组space中各分量链成一个备用链表// space[0].cur为头指针，0表示空指针int i;for(i=0;i<MAXSIZE-1;++i) space[i].cur=i+1;space[MAXSIZE-1].cur=0;
} // InitSpace_SLvoid rand_init_space_data(SLinkList space){// 随机生成静态链表中每个元素的数据int i;time_t t;srand((unsigned)time(&t)); //初始化随机数发生器for(i=0;i<MAXSIZE;++i) space[i].data=rand()%MAX_TEST_ELEM;
}void init_order_space_data(SLinkList space){// 有序生成静态链表中每个元素的数据int i;for(i=0;i<MAXSIZE;++i) space[i].data=i;
}void display_space(SLinkList space){// 显示静态链表int i;for(i=space[0].cur;i;i=space[i].cur)printf("space[%d].data=%d,next=%d\n",i,space[i].data,space[i].cur);
}int LocateElem_SL(SLinkList s,ElemType x){// 在静态链表中查找第一个值为x的元素// 若找到，则返回它在链表中的位序，否则返回0int i;for(i=s[0].cur;i&&s[i].data!=x;i=s[i].cur);return i;
}
int main(){int x;SLinkList space;InitSpace_SL(space);printf("Ordered List:\n");init_order_space_data(space);display_space(space);printf("\nRand List's data:\n");rand_init_space_data(space);display_space(space);printf("Input x and locate its position:");scanf("%d",&x);printf("Locate x in List,pos=%d",LocateElem_SL(space,x));return 0;
}