《数据结构》实验指导书（C语言版）

{ Elemtype elem[MAXLEN]; /*顺序表中存放元素的数组，其中elemtype为抽象数据类型，在程序具体实现时可以用任意类型代替*/

int length; /*顺序表的长度，即元素个数*/

}Sqlist; /*顺序表的类型*/

【核心算法提示】

1．顺序表插入操作的基本步骤：要在顺序表中的第i个数据元素之前插入一个数据元素x,首先要判断插入位置i是否合法，假设线性表的表长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表是否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的表长增加1。

2．顺序表删除操作的基本步骤：要删除顺序表中的第i个数据元素，首先仍然要判断i的合法性，i 的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据元素都前移一个位置，最后将线性表的表长减1。

3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素，则可以采用顺序查找的方法，从顺序表中第1个数据元素开始依次将数据元素值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回0值。 【核心算法描述】

status Sqlist_insert(Sqlist &L,int i,Elemtype x)

/*在顺序表L中第i个元素前插入新元素x*/

{ if (i<1||i>L.length+1) return ERROR; /*插入位置不正确则出错*/ if (L.length>=MAXLEN) return OVERFLOW;

/*顺序表L中已放满元素，再做插入操作则溢出*/

for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/ L.elem[i-1]=x; /*在第i个元素位置处插入新元素x*/ L.length++; /*顺序表L的长度加1*/ return OK; }

status Sqlist_delete(Sqlist &L,int i,Elemtype &e)

/*在顺序表L中删除第i个元素*/

{ if (i<1||i>L.length) return ERROR; /*删除位置不正确则出错*/ for(j=i;j<=L.length-1;j++)

L.elem[j-1]=L.elem[j]; /*将第i+1个元素及后继元素位置向前移一位*/ L.length--; /*顺序表L的长度减1*/ return OK；

}

int Sqlist_search(Sqlist L,Elemtype x)

/* 在顺序表中查找值为x的元素，如果找到，则函数返回该元素在顺序表中的位置，否则返回0*/

5

{ for (i=0;i

/*从第一个元素开始依次将每个元素值与给定值x比较*/

if (i

3．源程序代码参考 #define MAXLEN 50

typedef struct{int elem[MAXLEN]; int length;}Sqlist;

Sqlist Sqlist_insert(Sqlist L,int i,int x) /*顺序表插入函数*/ {int j;

if(i<1||i>L.length+1) printf(\ else if(L.length>=MAXLEN) printf(\

else { for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];

L.elem[i-1]=x; L.length++;

} return L; }

Sqlist Sqlist_delete(Sqlist L,int i) /*顺序表删除函数*/ {int j;

if(i<1||i>L.length) printf(\ else { for(j=i;j<=L.length-1;j++) L.elem[j-1]=L.elem[j];

L.length--;

} return L; }

int Sqlist_search(Sqlist L,int x)/* 顺序表查找函数*/ { int i;

for (i=0;i

6

else

return 0; }

void Sqlist_display(Sqlist L) /*顺序表元素输出函数*/ { int j;

for(j=0;j<=L.length-1;j++) printf(\ printf(\}

main() /*主函数 */ { Sqlist L; int i,x,j;

printf(\请求输入顺序表中元素个数*/ scanf(\

printf(\请求输入顺序表中各个元素*/ for(j=0;j<=L.length-1;j++)

scanf(\

printf(\请求输入插入操作位置*/ scanf(\

printf(\请求输入需要插入的新元素*/ scanf(\

L=Sqlist_insert(L,i,x);/*调用顺序表插入函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/

printf(\请求输入删除操作位置*/ scanf(\

L=Sqlist_delete(L,i);/*调用顺序表删除函数*/ Sqlist_display(L);/*调用顺序表元素输出函数*/ printf(\ scanf(\

if (Sqlist_search(L,x)) /*如果查找成功，则显示查找成功和找到的元素位置，否则显示查

找不成功*/

printf(\ else

printf(\ }

7

4．运行结果参考如图1-1所示：

图1-1: 验证性实验运行结果

七、设计性实验(以下两个设计题目学生可根据自己的掌握程度或兴趣自行选择完成) 1．编程实现删除有序顺序表中的所有重复元素，即使有序顺序表中相同的元素只保留一个。 ⑴ 实验要求

① 根据输入的n个非递减的有序数据建立一个有序顺序表，并输出有序顺序表中各元素值。

② 删除有序顺序表中所有的重复元素，并显示删除后的有序顺序表中各元素值。 ⑵ 核心算法提示

要在有序顺序表中删除重复的元素，首先就要抓住有序顺序表的特性：重复的元素总是在相邻的位置上，如：12，15，15，15，35，56，56，78。则删除重复元素后所得的有序表为：12，15，35，56，78。下面给出大致的操作步骤：从第1 个元素开始，依次将它与后面相邻的元素进行比较，如果相等则将前面那个相等的元素从顺序表中删除；如果不相等，则继续往下比较，如此重复，直到最后一个元素为止。

⑶ 核心算法描述 Sqlist delSqlist(Sqlist L)

{int i=0,j;

while(i

if (L.elem[i]==L.elem[i+1]) /*如果第i个及第i+1个相邻元素值相等*/

{ for (j=i+1;j

除第i个元素的目的*/

L.elem[j-1]=L.elem[j];

L.length--; /*有序顺序表的表长减1*/ } else i++; return L; }

2．编程实现一个简单学生成绩表的操作。

8