发布时间 : 2024/6/26 16:59:40 星期三 文章数据结构练习题 第三章 栈、队列和数组 习题及答案更新完毕开始阅读

typedef stuct node { DataType data; struct node *next; }LstackTp; 单链表的第一个结点就是链栈栈顶结点，链栈由栈顶指针惟一确定。栈中的其它结点通过它们的next域链接起来不。栈底结点的next域为NULL。 3、顺序队列的类型定义如下： #define maxsize 顺序栈的容量 typedef struct sqqueue {DataType data[maxsize]; int fornt,rear }SqQueueTp SqQueueTp sq; 该类型变量有三个域：data,front,rear。其中data存储队中元素的一维数组。队头指针front和队尾指针rear定义为整型变量，实际取值范围为0~maxsize－1。 循环队列的类型定义如下： #define maxsize 循环队的容量 typedef struct cycqueue{ DataType data[maxsize] Int front,rear }CycqueueTp; CycqueueTp sq; 4、typedef struct linked_queue { DataType data; struct linked_queue *next; }LqueueTp; typedef struct queueptr { LqueueTp *front, *rear; }QueptrTp; QueptrTp lq; 5、#define maxnum 非零元素的容量 typedef struct node { int i,j ; /*非零元素所在的行号、列号*/ DataType v; /*非零元素的值*/ }NODE; typedef struct spmatrix { int mu,nu,tu; /*行数、列数、非零元素的个数*/ NODE data[maxnum+1];/*这里假定三元组的下标的起始值为1*/ }SpMatrixTp 6、int length(CycqueueTp sq) {len=、1234、4321、2143、3421、3241、1324、1432、1342、1243、3214、2134、2314、2341、2431 8、运行结果：ABCDEFGHIJKLM MLKJIHGFEDCBA 9、借助栈将一个带头结点的单链表倒置。 10 r r’ r 5 r’’ r’ r r’’’ r’’ r’ r Top-> 1 2 3 4 5 rTop-> 2 3 4 5 rTop-> 3 4 5 r Top-> 4 r Top-> 5 rTop-> f(1)前 调用f(5)前 调用f(5)前 调用f(4)前 调用f(3)前 调用f(2)前 调用 r Top-> 2 3 4 5 r’’’ r’’ r’ r Top-> 3 4 5 r’’ r’ r Top-> 4 5 r’ r Top-> 5 后 五、算法设计 Top-> 返回f(1)后 返回f(2)后 返回f(3)后 返回f(4)后 返回f(5)1．本程序中，将客车类定义一个队KE，货车类定义一个队HE，过江渡船定义成一个栈DC。栈采用顺序存储结构，队采用链式存储结构。 #define sqstack_maxsize 10 typedef struct sqstack {DataType data[sqstack_maxsize]; int top; }SqStackTp; typedef struct linked_queue {DataType data; struct linked_queue *next; }LqueueTp; typedef struct queueptr {LqueueTp *front,*rear; }QueptrTp; int InitStack(SqStackTp *sq) {sq->top=0; return(1);} void InitQueue (QueptrTp *lp) {LqueueTp *p; p=(LqueueTp * )malloc(sizeof(LqueueTp)); lq->front=p; lq->rear=p; ( lq->front)->next=NULL; } int QutQueue(QueptrTp *lp,Data Type *x) {LqueueTp *s; if (lq->front==lq->rear) {error(“队空”);return(0);} else {s=(lq->front)->nest; *x=s->data; (lq->front)->next=s->next; if (s->next == NULL) lq->rear=llq->front; free(s); return(1); } } int EmptyQueue(QueptrTp lq) {if == return(1); return(0); } int Push (SqStackTp *sq , DataType x) { if (sq ->top = =sqstack_maxsize-q) {return(0);} else {sq ->top++; sq->data[sq->top]=x; return(1);} } void main() { SqStackTp DC; 表达式已存入字符数组A[n]中。 Void prool(A[n]) {Initstack (d); I=0; flag =true; while ((I0,n≥1。背包问题如果有解，其选择只有两种可能：一种是选择的一组物品中不包含Wn，这样Knap(S,n)的解就是Knap(S,n-1)的解，另一种是选择中包含Wn，这时Knap(S,n)的解就是Knap(S-Wn,n)的解。另外可以定义：当S=0时，背包问题总有解，即Knap(0,n)=true ，只要不选择任何物品放入背包即可：当S〈0时，背包问题无解，即Knap(S,n)=false，因为无论怎样选择总不能使重量之和为负值，当S>0但n<1时，背包问题也无解，即Knap(S,n)=false，因为不取任何东西就要使重量为正值总是办不到的。从而，背包问题可以递归定义如下： ╭ | true, 当S=0 | false, 当S<0 Knap(S,n)= < false, 当 s>0且 n<1 | Knap(S,n-1)或Knap(S- ,n-1)， 当s>0 且 n>=1 |