数据结构课后习题答案详解

数据结构习题集答案(C语言版严蔚敏) 第2章 线性表

描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。

解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 填空题。

解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 在什么情况下用顺序表比链表好？

解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 对以下单链表分别执行下列各程序段，并画出结果示意图。 解：

画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解：

已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是__________________。 b. 在P结点前插入S结点的语句序列是__________________。 c. 在表首插入S结点的语句序列是__________________。 d. 在表尾插入S结点的语句序列是__________________。 (1) P->next=S;

(2) P->next=P->next->next; (3) P->next=S->next; (4) S->next=P->next; (5) S->next=L; (6) S->next=NULL; (7) Q=P;

(8) while(P->next!=Q) P=P->next; (9) while(P->next!=NULL) P=P->next; (10) P=Q; (11) P=L; (12) L=S; (13) L=P;

解：a. (4) (1) b. (7) (11) (8) (4) (1) c. (5) (12) d. (9) (1) (6)

已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 a. 删除P结点的直接后继结点的语句序列是____________________。 b. 删除P结点的直接前驱结点的语句序列是____________________。 c. 删除P结点的语句序列是____________________。 d. 删除首元结点的语句序列是____________________。 e. 删除尾元结点的语句序列是____________________。 (1) P=P->next; (2) P->next=P;

(3) P->next=P->next->next; (4) P=P->next->next;

(5) while(P!=NULL) P=P->next;

(6) while(Q->next!=NULL) { P=Q; Q=Q->next; } (7) while(P->next!=Q) P=P->next;

(8) while(P->next->next!=Q) P=P->next; (9) while(P->next->next!=NULL) P=P->next; (10) Q=P;

(11) Q=P->next; (12) P=L;

(13) L=L->next; (14) free(Q);

解：a. (11) (3) (14) b. (10) (12) (8) (3) (14) c. (10) (12) (7) (3) (14) d. (12) (11) (3) (14) e. (9) (11) (3) (14)

已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是_______________________。 b. 在P结点前插入S结点的语句序列是_______________________。 c. 删除P结点的直接后继结点的语句序列是_______________________。 d. 删除P结点的直接前驱结点的语句序列是_______________________。 e. 删除P结点的语句序列是_______________________。 (1) P->next=P->next->next; (2) P->priou=P->priou->priou; (3) P->next=S; (4) P->priou=S; (5) S->next=P;

(6) S->priou=P;

(7) S->next=P->next; (8) S->priou=P->priou;

(9) P->priou->next=P->next; (10) P->priou->next=P; (11) P->next->priou=P; (12) P->next->priou=S; (13) P->priou->next=S;

(14) P->next->priou=P->priou; (15) Q=P->next; (16) Q=P->priou; (17) free(P); (18) free(Q);

解：a. (7) (3) (6) (12) b. (8) (4) (5) (13) c. (15) (1) (11) (18) d. (16) (2) (10) (18) e. (14) (9) (17) 简述以下算法的功能。 (1) {

A??a1,?,am?B??b1,?,bn?A?B?ABA??B??A?BA?B??A?B?A?BA?BAB?a1,?,an??an,?,a1?A??a1,a2,?,am?B??b1,b2,?,bn?m?nStatus A(LinkedList L)

C??a1,b1,?,am,bm,bm?1,?,bn?Status ListChange_DuL(DuLinkList &L) { int i; DuLinkList p,q,r; p=L->next; r=L->pre; i=1; while(p!=r){ if(i%2==0){ q=p; p=p->next;

m?nC??a1,b1,?,an,bn,an?1,?,am?L??a1,a2,?,an?L??a1,a3,?,an,?,a4,a2?.,an)改造为(a1,a3,...,an,...,a2)

Pn?x??c1xe1?c2xe2???cmxemn?em?em?1???e1?0ci?0?i?1,2,?,m?m?1Pn?x0?x0P?x??Pn1?x??Pn2?x?p1p2?pnpjpkpipjpkpipjpkpipipjpkpjpkpi

2n?1olor;

Push(s,g[][]);

while(!StackEmpty(s)){ Pop(s,e); CurPos=; g[][].Color=FillColor; g[][].Visited=1; if0 && !g[][].Visited &&

g[][].Color==OldColor ) Push(s,g[][]); if0 && !g[][].Visited && g[][].Color==OldColor ) Push(s,g[][]); } }

void CreateGDS(ElemType g[M][N]) { int i,j; for(i=0;i

void ShowGraphArray(ElemType g[M][N]) { int i,j; for(i=0;i

假设表达式有单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。 解： .#格式

void InversePolandExpression(char Buffer[]) { Stack s; InitStack(s); int i=0,j=0; ElemType e; Push(s,Buffer[i]); i++; while(Buffer[i]!='#'){ if(!IsOperator(Buffer[i])){

Afn?maxfn?1?maxk?i?j?10?k?3n?1n2?aadd(a,b)???add(??a,??b)a(a?1)i(i?1)?bk?ni?(n?j)??1i?1j?1i?j22n2n2n2s(n)?s(n?1)?an?s(n?1)?a1?(n?1)db?0b?0.，总共需进行n-k次交换。注意最后一组可能出现不足k个元素的情况，此时

最后一组为剩余元素加第一组的前几个元素共k个构成最后一组。 void RRMove(ElemType A[],int k,int n) { ElemType e; int i=0,j,p; while(i

i++; } } } 解：

#include <> #define RS 4 #define CS 4

typedef int ElemType; typedef struct{ ElemType e; int i,j; int Flags; }NodeType;

void Initialize(NodeType a[RS][CS],ElemType A[RS][CS]); void SaddlePoint(NodeType a[RS][CS]);

ElemType RowMin(NodeType a[RS][CS],int k); ElemType ColMax(NodeType a[RS][CS],int k); void Show(NodeType a[RS][CS]); int main() { ElemType A[RS][CS]={ {2,1,3,4}, {1,3,1,2}, {2,7,1,3}, {3,2,4,1} }; NodeType a[RS][CS]; Initialize(a,A); SaddlePoint(a); Show(a); return 0; }

void Initialize(NodeType a[RS][CS],ElemType A[RS][CS]) { int i,j; for(i=0;i

void SaddlePoint(NodeType a[RS][CS]) { int i,j; ElemType x,y; for(i=0;i

ElemType RowMin(NodeType a[RS][CS],int k) { ElemType x; x=a[k][0].e; int i; for(i=1;ia[k][i].e){ x=a[k][i].e; } return x; }

ElemType ColMax(NodeType a[RS][CS],int k) { ElemType x; x=a[0][k].e; int i; for(i=1;i

void Show(NodeType a[RS][CS]) {

for(int i=0;i

typedef int ElemType; class Triple{ public: int row; int col; ElemType e; Triple(){} virtual ~Triple(){} BOOL operator<(Triple b); BOOL operator==(Triple b); };

BOOL Triple::operator<(Triple b) { if(row< return TRUE; if(row==&&col< return TRUE; return FALSE; }

BOOL Triple::operator==(Triple b) { if(row== && col== return TRUE; else return FALSE; }

class CSparseMat {

public: CSparseMat(){} virtual ~CSparseMat(){} CSparseMat(int r,int c,int n); CSparseMat operator+(CSparseMat B); void ShowSparse(CDC* pDC); Triple *m_pt; ow=; m_pt[i].col=; m_pt[i].e=; } } }

void CSparseMat::ShowSparse(CDC *pDC) { char str[10]; int k=0; for(int i=0;iTextOut(0+j*20,0+i*20,str,strlen(str)); } } }

ow=m_pt[i].row; [k].col=m_pt[i].col; [k].e=m_pt[i].e; i++; } else{ if(m_pt[i]==[j]){ [k].row=m_pt[i].row; [k].col=m_pt[i].col; [k].e=m_pt[i].e+[j].e; i++; j++; } else{ [k].row=[j].row; [k].col=[j].col; [k].e=[j].e; j++; } } k++; } while(i