太原理工数据结构实验答案.pdf

实验一线性表

一．目的与要求

本次实习的主要目的是为了使学生熟练掌握线性表的基本操作在顺序存储结构和链式存储结构上

的实现，提高分析和解决问题的能力。要求仔细阅读并理解下列例题，上机通过，并观察其结果，

然后独立完成后面的实习题。

二．例题

问题描述:

用链表形式存储一个字符串，插入、删除某个字符，最后按正序、逆序两种方式输出字符串。

输入:

初始字符串，插入位置，插入字符，删除字符。

输出:

已建立链表（字符串），插入字符后链表，删除字符后链表，逆转后链表。

存储结构:

采用链式存储结构

算法的基本思想:

建立链表当读入字符不是结束符时，给结点分配存储空间，写数据域，将新结点插到表尾；插入字

符：根据读入的字符在链表中找插入位置，将新结点插入到该位置之前；删除字符：根据读入的删

除字符在链表中找到被删结点后，将其从链表中删除；链表逆转：从链表的第一个结点开始对所有

结点处理，将每个结点的前驱变为它的后继；打印链表：从链表的第一个结点开始，依次打印各

[运行情况]

Inputalinktable(astring):abcde↙

Buildlinkis:abcde

Pleaseinputacharyouwanttoinsertafter:b↙

Pleaseinputacharyouwanttoinsert:c↙

Afterpinserty,linkis:abccde

Pleaseinputacharyouwanttodelete:e↙

afterdeletep,linkis:abccd

Opsiteresultis:dccba

如图显示：

实习题：

问题描述：

设顺序表A中的数据元素递增有序，试写一程序，将x插入到顺序表的适当位置上，使该表仍然有

序。

输入：插入前的顺序表，插入的数，插入后的顺序表

输出：插入前的顺序表，插入的数，插入后的顺序表

存储结构：顺序表存储数据

算法基本思想:其实这个题在学C语言时就已经写过了，这里采用顺序表来存储数据。主要就是考虑

插入的位置是不是在最后一个，如果不在最后一个，那么就要移动数据了，算法很简单就不再说了，

这里的数据都看成是整型的。

源程序：

#includestdio.h

#includestdlib.h

voidInsert(int*p,intlength,intn){

inti,j;

intflag=0;

if(n=p[length-1]){

p[length]=n;

flag=1;

}

else{

for(i=length-2;i=0;i--){

if(n=p[i]){

for(j=length;j=i+2;j--){

p[j]=p[j-1];}

p[i+1]=n;

flag=1;

break;

}

}

}

if(flag==0){

for(j=length;j=1;j--){

p[j]=p[j-1];

}

p[0]=n;

}

}

intmain(){

intL[10]={2,5,8,11,14,17,20};

intlength=7;

inti,x;inti,x;

：：

for(i=0;ilength;i++){

}

：：

Insert(L,length,x);//插入x