《第2章 线性表及其应用》习题解答(5)

第2章 线性表及其应用

表的头结点的指针。并将其cur域的值置0值。如果操作成功返回1，否则返回0。

算法设计代码如下：

int InitList_S(SLinkList &Space,int &p) { if(p=NewSNode(Space)) { Space[p].cur=0; return 1; } return 0; } （2）静态链表p的插入操作InsertList_S(&Space,&p,i,e)

该操作从Space中摘取一个结点将data域的值置为e并将其插入到p中第i个位置。如果操作成功返回1，否则返回0。算法设计代码如下：

int InsertList_S(SLinkList &Space,int &p,int i,ElemType e) { int h=p,q,k=1; while(Space[h].cur&&k

该操作删除p中第i个结点将data值赋值给e,并将资源归还给Space。如果操作成功返回1，否则返回0。算法设计代码如下：

int DeleteList_S(SLinkList &Space,int &p,int i,ElemType &e) { int h=p,q,k=1; while(Space[h].cur&&k

-.33.-

《数据结构与算法》

}

（4）静态链表p的遍历操作TraverseList_S(Space,p)

该操作按序显示链表p中每一个结点的值。算法设计代码如下： void TraverseList_S(SLinkList Space,int p) { int i=Space[p].cur; while(i) { cout<

4．静态链表的综合演示程序

void main_S() { SLinkList SS; int p,i,num,n,k; ElemType e; InitSpace_S(SS); if(!InitList_S(SS,p)) { cout<<\初始化不成功！\\n\return; } cout<<\建立一个静态链表，输入长度:\ cin>>n; cout<<\输入\个结点的值:\ for(i=0;i>e; if(!InsertList_S(SS,p,i+1,e)) { cout<<\空间已满!\\n\break; } } cout<<\链表的初始内容为:\\n\ TraverseList_S(SS,p);

cout<<\在第i个结点前插入一个结点,2-删除第i个结点\\n\ cout<<\显示当前链表的内容,4-显示可用空间长度\\n\ cout<<\退出演示程序. \ while(1) { cout<<“输入选择:”; cin>>num; switch(num) { case 1: cout<<\输入插入位置i和值e:\cin>>i>>e;

-.34.-

第2章 线性表及其应用

if(!InsertList_S(SS,p,i,e)) cout<<\插入的位置不合理,或空间已满。\\n\ break; case 2: cout<<\输入删除位置i:\cin>>i; if(!DeleteList_S(SS,p,i,e)) cout<<\删除位置不合理,或链表已空\\n\ else cout<<\第\个结点被删除，其值为：\ break; case 3: TraverseList_S(SS,p); break; case 4: for(i=0,k=0;;) { if(!(i=SS[i].cur))break; k++; } cout<<\当前的可用空间长度为: \ break; case 5: cout<<\欢迎使用顺序表演示程序\\n\ return; default: cout<<\选择不合理重新选择\\n\ }//end_switch }//end_while }//end_main_S() 运行结果为：

建立一个静态链表，输入长度:12

输入12个结点的值:100 200 300 400 500 600 700 800 900 1000 1100 1200 链表的初始内容为:

100 200 300 400 500 600 700 800 900 1000 1100 1200 1-在第i个结点前插入一个结点,2-删除第i个结点 3-显示当前链表的内容,4-显示可用空间长度 5-退出演示程序. 输入选择: 1 输入插入位置i和值e:3 333 输入选择: 4 输入选择: 1 当前的可用空间长度为: 984 输入插入位置i和值e:5 555 输入选择: 2 输入选择: 1 输入删除位置i:11 输入插入位置i和值e:7 777 第11个结点被删除，其值为：900 输入选择: 3 输入选择: 4 100 200 333 300 555 400 777 500 600 700 800 900 当前的可用空间长度为: 985 1000 1100 1200 输入选择: 3 输入选择: 4 100 200 333 300 555 400 500 600 700 800 1000 1100 当前的可用空间长度为: 983 1200 输入选择: 2 输入选择: 5 输入删除位置i:7 欢迎使用顺序表演示程序 第7个结点被删除，其值为：777

说明：

-.35.-

《数据结构与算法》

（1）可用空间中应该去掉链表的头结点和空闲链表的头结点。 （2）可由多个静态链表共享同一个空闲链表。

（3）由于假定系统不能使用指针类型变量，即不能动态分配内存，因此当空间Space中的空闲链表为空时，将使静态链表的插入操作失败。

2.6线性链表的应用举例

【例2.6】有n个人围成一圈，顺序排号：1、2、3、?、n。从第一个人开始报数（从1到m报数），凡报到m的人退出圈子并记下此人的排号，当最后一个人退出圈子时，按出圈次序依次输出所有人原来的排号序列（用单链表编程实现）。 算法思想

（1）建立一个长度为n的单链表L，其结点值依次为1、2、?、n；

（2）指针p（开始时指向头结点）每次向后移动m-1次使其指向出圈结点的直接前区结点； （3）如果p的后继结点为NULL则p=L；

（4）从链表L中删除p的后继结点q并输出q中的编号值； （5）重复执行（2）、（3）、（4）n次。 算法实现

void main() { int m,n,i,k; LinkList L=new Node,p,q; //定义头指针L指向头结点以及结点指针变量p、q cout<<\ cin>>n>>m; p=L; for(i=1;i<=n;i++) //建立有n个结点的单链表并且依次赋于相应的编号值 { p->next=new Node; p=p->next; p->data=i; } p->next=NULL; //最后一个结点的指针域为NULL p=L; cout<<\所求编号序列为:\\n\ for(i=0;inext)p=L; p=p->next; } if(!p->next)p=L; q=p->next; //以下语句实现：删除结点q并输出其编号的值 p->next=q->next; cout<data<<\

-.36.-

第2章 线性表及其应用

delete q; } cout<

程序运行演示结果为：

input n m:10 3↙ 所求编号序列为: 3 6 9 2 7 1 8 5 10 4

算法分析

由算法设计过程可知该算法的时间复杂度为O(n×m)，空间复杂度为O(1)。 【方法二】类似[例2.4]，通过直接调用单链表的基本操作来求解。 void main() { int m,n,i,k; //定义人数n、间隔数m、循环变量i和出圈人前驱结点的位置k ElemType e; //定义出圈人编号e LinkList L; //定义线性链表L cout<<\ //输入n、m的值 InitList_L(L); //初始化L为空链表 for(i=1;i<=n;i++)InsertList_L(L,i,i); //置第i个人的编号为i cout<<\所求编号序列为:\\n\ for(k=0,i=n;i>0;i--) //i为当前的链表长度 { k=(k+m-1)%i; //计算出圈人结点在链表L中的前驱结点位置k DeleteList_L(L,k+1,e); //删除第k+1个结点并提取其编号到e中 cout<

【例2.7】逆置一个具有头结点的单向链表。

链表L逆置前的结构如图2.12(a)所示，L逆置后的结构如图2.12(b)所示。

算法思想

（1）如果长度≤1程序结束；

（2）指针p指向第一个结点，q指向第二个结点； （3）置p的next域为NULL，r为q的直接后继； （4）如果r为NULL转入（7）否则执行（5）；

（5）置q的直接后继为p，置p的值为q，置q的值为r，置r为q的直接后继；

-.37.-

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《第2章 线性表及其应用》习题解答(5)在线全文阅读。