数据结构 用C语言描述 课后答案(3)

{

p=(cnode *)malloc(sizeof(cnode)); if (p==null) return OVERFLOW; p->data=i; p->next=clist; clist=p; if(i==n) q=p; }

q->next=clist; joseph=clist; return ok; }

status joseph(cnode *clist,int m,int n,int k) { int i;

cnode *p,*q;

if(m>n) return ERROR;

if(!create_clist(clist,n)) return ERROR; p=joseph;

for (i=1;inext; while(p)

{ for (i=1;inext; q=p->next;

printf(\ \ if (p->next==p) p=null; else

{ p->next=q->next; p=p->next; free(q); } }

clist=null; }

main()

{

int m,n,k,i; cnode *clist; clist=null;

printf(\ scanf(\

printf(\ scanf(\

printf(\ out:\ scanf(\ create_clist(clist,n);

printf(\ joseph(clist,m,n,k); getch(); }

课后练习

一、术语理解

描述以下三个概念的区别：头指针，头结点，首元素结点。 二、填空题

（1）在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元

素个数与 有关。

（2）在顺序表中，逻辑上相邻的元素，其物理位置 相邻。在单链表中，逻

辑上相邻的元素，其物理位置 相邻。

（3）在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点

的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 指示。

三、已知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(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。

五、写一算法，从顺序表中删除自第i个元素开始的k个元素。

六、 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。

七、试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。

（1） 以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2） 以单链表作存储结构。

八、假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C。

九、已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

十、设线性表A=(a1, a2,…,am)，B=(b1, b2,…,bn)，试写一个按下列规则合并A、B为线性表C的算法，使得：

C= (a1, b1,…,am, bm, bm+1, …,bn) 当m≤n时；

或者 C= (a1, b1,…,an, bn, an+1, …,am) 当m>n时。 线性表A、B、C均以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。

十一、将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。

十二、建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位。并在此链表上实现对二进制数加1的运算。

十三、设多项式P(x)采用课本中所述链接方法存储。写一算法，对给定的x值，求P(x)的值。

十三、顺序表基本操作实现

【解答】

#include \

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct {int *elem; int length; int listsize;

} sqlist;

void initlist_sq(sqlist *l) {

int i,j,e;

l->elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int)); if (!l->elem)

printf(\ else {

/*l->length=0;

l->listsize=LIST_INIT_SIZE; printf(\

printf(\ scanf(\ l->length=i;

l->listsize=LIST_INIT_SIZE; for (j=1;j<=i;j++)

{ printf(\ scanf(\ l->elem[j-1]=e; }

printf(\ } }

void listinsert_sq(sqlist *l,int i,int e) {

int *newbase,*p,*q; if (i<1||i>l->length+1)

printf(\ else {

if (l->length>=l->listsize)

{newbase=(int *)realloc(l->elem,(l->listsize+LISTINCREMENT)*sizeof(int)); if (!newbase)

printf(\ else {

l->elem=newbase;

l->length+=LISTINCREMENT; } }

q=&(l->elem[i-1]);

for (p=&(l->elem[l->length-1]);p>=q;p--) *(p+1)=*p; *q=e;

l->length++; } }

void listdelete_sq(sqlist *l,int i,int *e) {

int *p,*q;

if (i<1||ilength)

printf(\ else {

p=&(l->elem[i-1]); *e=*p;

q=l->elem+l->length-1;

for (++p;p<=q;++p) *(p-1)=*p; l->length--; } }

void listprint_sq(sqlist *l) {

int *p;int i;

printf(\ for (i=0;ilength;++i) printf(\

/* for (p=&(l->elem[0]);p<=&(l->elem[l->length-1]);++p) printf(\ printf(\ }

void reverselist(sqlist *l) {

int i,temp;

for (i=1;i<=l->length/2;i++)