数据结构第二章练习题答案

/*文件名:exp2-1.cpp*/ #include #include #define MaxSize 50 typedef char ElemType; typedef struct { ElemType data[MaxSize]; int length; } SqList;

extern void InitList(SqList *&L); extern void DestroyList(SqList *L); extern int ListEmpty(SqList *L); extern int ListLength(SqList *L); extern void DispList(SqList *L);

extern int GetElem(SqList *L,int i,ElemType &e); extern int LocateElem(SqList *L, ElemType e); extern int ListInsert(SqList *&L,int i,ElemType e); extern int ListDelete(SqList *&L,int i,ElemType &e); void main() { SqList *L; ElemType e; printf(\初始化顺序表L\\n\ InitList(L); printf(\依次采用尾插法插入a,b,c,d,e元素\\n\ ListInsert(L,1,'a'); ListInsert(L,2,'b'); ListInsert(L,3,'c'); ListInsert(L,4,'d'); ListInsert(L,5,'e'); printf(\输出顺序表L:\ DispList(L); printf(\顺序表L长度=%d\\n\ printf(\顺序表L为%s\\n\空\非空\ GetElem(L,3,e); printf(\顺序表L的第3个元素=%c\\n\ printf(\元素a的位置=%d\\n\ printf(\在第4个元素位置上插入f元素\\n\ ListInsert(L,4,'f'); printf(\输出顺序表L:\ DispList(L); printf(\删除L的第3个元素\\n\ ListDelete(L,3,e);

printf(\输出顺序表L:\ DispList(L); printf(\释放顺序表L\\n\ DestroyList(L); }

//文件名:exp2-2.cpp #include

#include using namespace std;

typedef struct LNode //定义单链表结点类型 { string data;

struct LNode *next; } LinkList;

void InitList(LinkList *&L) { L=(LinkList *)malloc(sizeof(LinkList)); //创建头结点 L->next=NULL; }

void DestroyList(LinkList *&L) { LinkList *p=L,*q=p->next; while (q!=NULL) { free(p); p=q; q=p->next; } free(p); }

int ListEmpty(LinkList *L) { return(L->next==NULL); }

/*int ListLength(LinkList *L) { LinkList *p=L;int i=0; while (p->next!=NULL) { i++; p=p->next;

} return(i); }

void DispList(LinkList *L) { LinkList *p=L->next; while (p!=NULL) { printf(\ p=p->next; } printf(\}

int GetElem(LinkList *L,int i,ElemType &e) { int j=0; LinkList *p=L; while (jnext; } if (p==NULL) return 0; else { e=p->data; return 1; } }

int LocateElem(LinkList *L,ElemType e) { LinkList *p=L->next; int n=1; while (p!=NULL && p->data!=e) { p=p->next; n++; } if (p==NULL) return(0); else return(n); }*/

int ListInsert(LinkList *&L,int i,string e) { int j=0; LinkList *p=L,*s; while (jnext; } if (p==NULL) //未找到第i-1个结点 return 0; else //找到第i-1个结点*p { s=(LinkList *)malloc(sizeof(LinkList)); //创建新结点*s s->data=e; s->next=p->next; //将*s插入到*p之后 p->next=s; return 1; } }

/*int ListDelete(LinkList *&L,int i,ElemType &e) { int j=0; LinkList *p=L,*q; while (jnext; } if (p==NULL) //未找到第i-1个结点 return 0; else //找到第i-1个结点*p { q=p->next; //q指向要删除的结点 if (q==NULL) return 0; e=q->data; p->next=q->next; //从单链表中删除*q结点 free(q); //释放*q结点 return 1; } } */

void main() {

LinkList *h; string e; printf(\初始化单链表h\\n\ InitList(h); printf(\依次采用尾插法插入a,b,c,d,e元素\\n\ ListInsert(h,1,\ /*ListInsert(h,2,'b'); ListInsert(h,3,'c'); ListInsert(h,4,'d'); ListInsert(h,5,'e'); printf(\输出单链表h:\ DispList(h); printf(\单链表h长度=%d\\n\ printf(\单链表h为%s\\n\空\非空\ GetElem(h,3,e); printf(\单链表h的第3个元素=%c\\n\ printf(\元素a的位置=%d\\n\ printf(\在第4个元素位置上插入f元素\\n\ ListInsert(h,4,'f'); printf(\输出单链表h:\ DispList(h); printf(\删除h的第3个元素\\n\ ListDelete(h,3,e); printf(\输出单链表h:\ DispList(h); printf(\释放单链表h\\n\ DestroyList(h);*/ }

//文件名:exp2-3.cpp #include #include typedef char ElemType;

typedef struct DNode //定义双链表结点类型 { ElemType data; struct DNode *prior; //指向前驱结点 struct DNode *next; //指向后继结点 } DLinkList;

extern void InitList(DLinkList *&L); //以下均为外部函数 extern void DestroyList(DLinkList *&L); extern int ListEmpty(DLinkList *L); extern int ListLength(DLinkList *L); extern void DispList(DLinkList *L);