实验一、顺序表逆置和单链表逆置
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