西安电子科技大学出版社：《算法与数据结构》课程教学资源（练习题）第2章练习题

第2章线性表 要求: 1、掌握线性表的逻辑结构; 2、线性表的顺序存储表示及其算法 3、线性表的链式存储表示及其算法; 教材习题参考解答: 2.1略 2.2(1)n/2与(mn=1)/2n (2)也(一定) (3)LL>next上二元素结点的指针域指示。 2.3a4,1 b7,11,8,4,c5,12d11,9,6,1或11,9,13,1或11,9,1,6 2.4/*P49习题2.4示例程序* #define maxsize 100 typedef int ElemType; typedef struct ElemType elem[Maxsize] int last JSlIst int InsertList (SqList *pL, ElemType x) int k if(pL->last>=Maxsize-1) return(0) k=pL->last *k>=0保证线形表不为空,pL->elem[k]>x保证插入位置正确*/ while((k>=0)&&(pL->elem[k]>x)) pL->elem[k+1]=pL->elem[k] pL->elem[k+1]=x L-last++ return (1) id ElemType e Sqlist l;/*定义线形表变量*/

第 2 章 线性表 要求： 1、 掌握线性表的逻辑结构； 2、 线性表的顺序存储表示及其算法； 3、 线性表的链式存储表示及其算法； 教材习题参考解答： 2.1 略 2.2 (1)n/2 与(n-1)/2 n (2)也(一定) 不一定 (3)L L->next 上一元素结点的指针域指示。 2.3 a 4,1 b 7,11,8,4,1 c 5,12 d 11,9,6,1 或 11,9,13,1 或 11,9,1,6 2.4 /*P49 习题 2.4 示例程序 */ #define Maxsize 100 typedef int ElemType; typedef struct { ElemType elem[Maxsize]; int last; }SqList; int InsertList(SqList *pL,ElemType x) { int k; if(pL->last>=Maxsize-1) return (0); k=pL->last; /*k>=0 保证线形表不为空,pL->elem[k]>x 保证插入位置正确*/ while((k>=0) && (pL->elem[k] > x)) { pL->elem[k+1]=pL->elem[k]; k--; } pL->elem[k+1]=x; pL->last++; return (1); } void main() { int i; ElemType e; SqList L; /*定义线形表变量*/

L.1ast=1;/*置线形表为空表状态*/ 任意输入10个整数*/ or(i=0;i<10;i++) scanf(%d", &e) /*将结果输出*/ for(i=0: i<=L last: i++) printf(%d\t", L elem[il) printf("\n") 2.5/*P49习题2.5示例程序* #include <stdio. h> #define maxsize 100 typedef int ElemType typedef struct Elem Type elem [Maxsize] JSlIst int DelElem(SqList apL, int i, int k) /*判断i和k的值的合法性*/ if(i<=o|lik>pL->last+1) return(O) (i=i+k-1: j<=pL L->elem[j-k]=pL->elem [j] pL-last-=k return(1) void Print(sqlist *pL) for (i=0; i<=pL->last: i++) printf( %d\t", pL->elem[il) Sqlist l;/*定义线形表变量*/

L.last=-1; /*置线形表为空表状态*/ /*任意输入 10 个整数*/ for(i=0;i<10;i++) { scanf("%d",&e); InsertList(&L,e); } /*将结果输出*/ for(i=0;i<=L.last;i++) printf("%d\t",L.elem[i]); printf("\n"); } 2.5 /*P49 习题 2.5 示例程序 */ #include <stdio.h> #define Maxsize 100 typedef int ElemType; typedef struct { ElemType elem[Maxsize]; int last; }SqList; int DelElem(SqList *pL,int i,int k) { int j; /*判断 i 和 k 的值的合法性*/ if(i<=0||i+k>pL->last+1) return(0); for(j=i+k-1;j<=pL->last;j++) pL->elem[j-k]=pL->elem[j]; pL->last-=k; return(1); } void Print(SqList *pL) { int i; for(i=0;i<=pL->last;i++) printf("%d\t",pL->elem[i]); printf("\n"); } void main() { int i,k; SqList L; /*定义线形表变量*/

L.1ast=-1;/*置线形表为空表状态*/ /*向线形表中顺序存入1-20*/ for(i=0;i<20;i+) L elem[i]=i+ L last=19 Print(&L);/*将原结果输出* printf("请输入起始位置和删除元素的个数:") scanf (%d %d",&i, &k) /*将删除后结果输出*/ DelElem(&L, i, k) Print(&L) 2.6/*P49习题2.6示例程序*/ #include <stdio. h #include <stdlib. h> #define null o typedef int elemType: typedef struct node data struct node水next }Node,米 Linklist /*初始化带头结点的单链表*/ void InitList(LinkList *pL) *pL=(LinkList)malloc(sizeof ( node)) (*pL)->next=NULL /*头插法插入元素*/ void InsertList(LinkList L, ElemType e) Linklist p: p=(LinkList)malloc(sizeof (Node)) L->next=p void shanchu(LinkList L, int mink, int maxk) //让指针p指向第一个元素比mink大的结点,q指向p前面的结点

L.last=-1; /*置线形表为空表状态*/ /*向线形表中顺序存入 1-20*/ for(i=0;i<20;i++) L.elem[i]=i+1; L.last=19; Print(&L); /*将原结果输出*/ printf("请输入起始位置和删除元素的个数："); scanf("%d %d",&i,&k); /*将删除后结果输出*/ DelElem(&L,i,k); Print(&L); } 2.6 /*P49 习题 2.6 示例程序 */ #include <stdio.h> #include <stdlib.h> #define NULL 0 typedef int ElemType; typedef struct node { ElemType data; struct node *next; }Node,*LinkList; /*初始化带头结点的单链表*/ void InitList(LinkList *pL) { *pL=(LinkList)malloc(sizeof(Node)); (*pL)->next=NULL; } /*头插法插入元素*/ void InsertList(LinkList L,ElemType e) { LinkList p; p=(LinkList)malloc(sizeof(Node)); p->data=e; p->next=L->next; L->next=p; } void shanchu(LinkList L, int mink, int maxk) { LinkList p,q; q = L; p = L->next; //让指针 p 指向第一个元素比 mink 大的结点，q 指向 p 前面的结点

while(p! = NULL & p->data < mink) p=p->next //删除所有比mink大比maxk小的结点 while(p ! NULL & p->data maxk) g->next p->nex free(p) p=g->next void Print(LinkList L) LinkList p: for(p L->next; p!= NULL p= p->next) printf(%d\t", p->data) printf("\n") void maino InitList(&L) /*初始化链表*/ /*向线形表中顺序存入1-20*/ for(i=10;i>0;i一) InsertList(L, i Print (l) /*将原结果输出*/ shanchu(L,6,9);/将大于6小于9地元素删除 /*将逆置后结果输出*/ 2.7/*P49习题2.71示例程序* /*采用顺序存储方法进行线形表的逆置*/ #include <stdio. h #define maxsize 100 typedef int ElemType typedef struct ElemType elem [Maxsize int last I Sqlist void Nizhi(SqList *pL)

while(p != NULL && p->data <= mink) { q = p; p = p->next; } //删除所有比 mink 大比 maxk 小的结点 while(p != NULL && p->data < maxk) { q->next = p->next; free(p); p = q->next; } } void Print(LinkList L) { LinkList p; for(p = L->next; p != NULL; p = p->next) printf("%d\t",p->data); printf("\n"); } void main() { int i; LinkList L; InitList(&L); /*初始化链表*/ /*向线形表中顺序存入 1-20*/ for(i=10; i>0; i--) InsertList(L,i); Print(L); /*将原结果输出*/ shanchu(L, 6, 9); //将大于 6 小于 9 地元素删除 Print(L); /*将逆置后结果输出*/ } 2.7 /*P49 习题 2.71 示例程序 */ /*采用顺序存储方法进行线形表的逆置*/ #include <stdio.h> #define Maxsize 100 typedef int ElemType; typedef struct { ElemType elem[Maxsize]; int last; }SqList; void Nizhi(SqList *pL)

ElemType temp: Int j=pL->last while(i<j /*交换i和j位置的元素* temp=pL->elem[i] pL->elem[i]=pL->elem[j] pL->elem [j]=temp 1++ void Print (Sqlist *pL) for(i=0: i<=pL->last; i++) printf(%d\t", pL->elem[i]) printf( "\n") void maino Int 1 Sqlist L;/*定义线形表变量*/ L.last=-1;/*置线形表为空表状态*/ /*向线形表中顺序存入1-20*/ for(i=0;i<20;i++) L elem[i]=i+1 L last=19 Print(&L);/*将原结果输出*/ Nizhi ( &L) Print(&L) /*将逆置后结果输出* /*P49习题2.71示例程序*/ /*采用链式存储方法进行线形表的逆置*/ #include <stdio. h> #include <stdlib. h> #define null o typedef int ElemType typedef struct node ElemType data

{ ElemType temp; int i,j; i=0; j=pL->last; while(i<j) { /*交换 i 和 j 位置的元素*/ temp=pL->elem[i]; pL->elem[i]=pL->elem[j]; pL->elem[j]=temp; i++; j--; } } void Print(SqList *pL) { int i; for(i=0;i<=pL->last;i++) printf("%d\t",pL->elem[i]); printf("\n"); } void main() { int i; SqList L; /*定义线形表变量*/ L.last=-1; /*置线形表为空表状态*/ /*向线形表中顺序存入 1-20*/ for(i=0;i<20;i++) L.elem[i]=i+1; L.last=19; Print(&L); /*将原结果输出*/ Nizhi(&L); Print(&L); /*将逆置后结果输出*/ } /*P49 习题 2.71 示例程序 */ /*采用链式存储方法进行线形表的逆置*/ #include <stdio.h> #include <stdlib.h> #define NULL 0 typedef int ElemType; typedef struct node { ElemType data;