数据结构练习题 第二章 线性表 习题及答案

精品文档

结点的链域;③lklist与pointer相同类型,用来说明头指针变量的类型,因而lklist也就被用来作为单链表的类型。 3、typedef struct dnode *dpointer; struct dnode {datatype data; dpointer prior,next; } typedaf dpinter dlklist; 链域prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋和后继指针链接在一起,再加上起标识作用的头指针,就得到双向循环链表。 4、顺序串的类型定义与顺序表类似,可描述如下: const maxlen=串的最大长度 typedef struct {char ch[maxlen] int curlen; }string 5、链串的类型定义为: const nodesize=用户定义的结点大小; typedef struct node *pointer; struct node {char ch[nodesize] poinernext; } typedef pointer strlist; 当结点大小为1时,可将ch域简单地定义为:char ch 6、head称为头指针变量,该变量的值是指向链表的第一个结点的指针,称为头指针。头指针变量是用于存放头指针的变量。 为了便于实现各种运算,通常在单链表的第一个结点之前增设一个类型相同的结点,称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。

头指针变量的作用:对单链表中任一结点的访问,必须首先根据头指针变量中存放的头指针找到第一个结点,再依次按各结点链域存放的指针顺序往下找,直到找到或找不到。头指针变量具有标识单链表的作用,故常用头指针变量为命名单链表。 头结点的作用:头结点的数据域可以不存储任何信息,也可以存放一个特殊标志或表长。其作用是为了对链表进行操作时,将对第一个结点煌处理和对其它结点的处理统一起来。 7、循环单链表、循环双链表。 ; 五、算法设计 .

精品文档

1、 分析:(1)当A、B表都不为空时,比较A,B表中各元素对应位置的内容的大小,进而判断A,B的大小。 (2)当A,B表都不为空时,且A,B表中各各元素对应位置的内容相同时,比较A,B的长度,进而判断A,B的大小或是否相等。 const maxsize=顺序表的容量; typedef struct {int data[maxsize] int last; }sqlist; int CMP_sqlist(sqlist A ,sqlist B) { for (i=0;(iB.data[i])return(1); } if(A.last= =B.last) return(0); else if(A.last>B.last) return(1); else return(-1); } 2、(1)定位LOCATE(L,X) 在带头结点类单链表上实现的算法为: int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的的序号,不存在这种结点时结果为0*/ {p=head->next;j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经,继续扫描*/ if (p->data = =x) return(j); else return(0); } 在无头结点的单链表上实现的算法为: int Wlocate(lklist head,datatype X) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ {p=head; j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经,继续扫描*/ if( p->data = =X) return(j); else return(0); .

精品文档

} (2)按序号查找find(L,i) 在带头结点的单链表上实现的算法为: pointer find_lklist(lklist head , int i); { j=1; p=head->next; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } 在无头结点的单链表上实现的算法为: pointer find_lklist(lklist head , int i); { j=1; p=head; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } (3)、插入INSERT(L,X,i) 在带头结点单链表上实现的算法为: void insert_lklist(lklist head,datatype x,int I) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {p=find_lklist(head,i-1); /*先找第i-1个结点*/ if(p= =NULL)reeor(“不存在第i个位置”)/*若第i-1个结点不存在,退出*/ else{s=malloc(size);s->data=x /*否则生成新结点*/ s->next=p->next /*结点*p在链域值传给结点*s的链域*/ p->next=s; /*修改*p的链域*/ } } 在无头结点的单链表上实现的算法为: void Winsert(lklist head,dataytpe X,int i) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {if(i<=0) error(“i<=0”); else{ s=malloc(size);s->data=X; /*否则生成新结点*/ if(i= =1){s->next=head;head=s;} else{ p=wfind_lklist(lklist head,i-1); if(p= =NULL) error(“i>n+1”); else{s->next=p->next;p->next=s;} } } .

精品文档

(4)删除DELDTE(L,i) 在带头结点的单链表上实现的算法为: void delete_lklist(lklist head,int i) /*删除表head的第i个结点*/ {p=find_lklist(head,i-1) /*先找待删结点的直接前驱*/ if((p!==NULL)&&(p->next!=NULL))/*若直接前趋存在且待结点存在*/ (q=p->next; /*q指向待删结点*/ p->next=q->next/*摘除待结点*/; free(q);/*释放已摘除结点q*/ } else error(“不存在第i个结点”)/*否则给出相关信息*/ } 在无头结点的单链表上实现的算法为: void Wdelete(lklist head,int i) /* 删除表head的第i个结点,若该链表仅有一个结点时,赋该结点指针NULL*/ {if(i<=0) error(“I<=0” else{if(i= =0){q=head;head=head->next;free(q);} else{p=wfind_lklist(head,i-1);/*找链表head中第i-1结点指针*/ if(p!=NULL)&&(p->next!=NULL) {q=p->next; p->next=q->next; free(q);} else error(“不存在第I个结点”); } } } 3、 分析:从第一个结点开始访问,只要是非空计数一次。 Int wlength_lklist(lklist head) /*求表head的长度*/ {p=head;j=0; while(p!=NULL){p=p->next;j++;} return(j); /*回传表长*/ } 4、 设A,B,C均为无头结点单链表 分析:(1)当有序表A,B均非空时,找出两表中元素最小的一个元素,然后将此结点插入到C表中,重复上述步骤。 (2)当A,B两表有一个为空表时,将另一表中元素顺序地插入到C表中。 (3)由于C按递减排序,因此在C表中插入元素时,应始终插入到C表表头。 Lklist Wlink_lklist(lklist A,lklist B) { while((A!=NULL)&&(B!=NULL)) if(A->datadata){p=A;A=A->next;} else .

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4