发布时间 : 星期六 文章数据结构练习题 第二章 线性表 习题及答案更新完毕开始阅读
结点的链域；③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、循环单链表、循环双链表。 ; 五、算法设计 13
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;(i
} (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;} } } 15
(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->data