内容发布更新时间 : 2024/11/16 18:52:44星期一 下面是文章的全部内容请认真阅读。

实验一、顺序表逆置和单链表逆置

1.1 问题的提出

设有一个线性表E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ en , en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。

? 顺序表逆置

1.1.1 算法分析

Step1：将顺序表位置i的元素与位置L->last-i+1的元素进行互换； Step2：重复Step1，直到i=L->last/2，结束。 1.1.2 问题的程序代码

//顺序表逆置

void invert(sequenlist*L) {

int i;

datatype temp; //定义i和temp的类型

for(i=1;i<=L->last/2;i++)//for循环语句，其中的L->last/2当L->last为奇

数时，相当于向下取整

{temp=L->data[i];

L->data[i]=L->data[L->last-i+1];

L->data[L->last-i+1]=temp;//将位置i和位置L->last-i+1的元素进行互换 } }

1.1.3 运行结果

1.1.4 存在的问题

逆置表中的元素只能是单个元素，不能进行多位数的逆置，如下图所示

1

? 单链表逆置 1.2.1 算法分析

Step1：将p指针指向头结点，q指针指向头结点的下一个结点； Step2：将p和q逆置，并将它们分别后移一个结点； Step3：重复Step1~ Step2，直到指针r指向空域，结束。 1.2.2 问题的程序代码

//单链表逆置

void invert(linklist *head) {

linklist *p,*q,*r;

p=head->next;//p指针指向头结点

q=p->next; //q指针指向头结点的下一个结点

while(q!=NULL)//当q指针非空时，进行while循环

{r=q->next; q->next=p;//将r指针指向q的下一个结点，而q指针指

向p

p=q; q=r;//将p指针指向q，q指针指向r，实现p和q的逆置 } head->next->next=NULL;//原链表的第一个结点指针置空，变为新链表的尾结点 head->next=p;// 原链表最后一个结点变为新链表的头结点 }

1.2.3 运行结果

1.2.4 存在的问题

与顺序表逆置一样，逆置表中的元素只能是单个元素，不能进行多位数的逆置，如下图所示

2

实验二、分解单链表

2.1 问题的提出

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

2.2 算法分析

Step1：将单链表中的头结点与字母比较，判断是否在[A,Z]或者[a,z]之间；

Step2：在[A,Z]或者[a,z]之间，则将它写入字母的单链表中,否则转Step3； Step3：将单链表中的头结点与字母比较，判断是否在[0,9]之间； Step4：在[0,9]之间，则将它写入数字的单链表中否则转Step5； Step5：将它写入其他字符的单链表中； Step6：取下一结点，重复Step1~ Step5，直到结点完全进入3个新的单链表，

结束。 2.3 问题的程序代码

//按字母、数字、其它字符分解单链表

void resolve(linklist*head,linklist*letter,linklist*digit,linklist*other) { linklist *p;

while(head->next!=NULL)

{ p=head->next;//p指针指向头结点 head->next=head->next->next;

if((p->data>='A'&&p->data<='Z')||(p->data>='a'&&p->data<='z'))

insert(letter,p); //判断字符是否在[A,Z]或者[a,z]之间，是，插入第

一个单链表中

else if(p->data>='0'&&p->data<='9') insert(digit,p);

else insert(other,p); //判断字符是否在[0,9]，是，插入第二个单链表中；

否，插入第三个单链表中

} }

3