实习二 线性表
一、实验目的
1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。
2. 重点是线性表的基本操作在两种存储结构上的实现；其中以链表的操作为侧重点；并进一步学习结构化的程序设计方法。
二、实例
1. 线性表的顺序存储表示（结构）及实现。
阅读下列程序请注意几个问题：
（1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含‘动态分配’一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。我们采用的是含‘静态’一维数组和线性表长的结构体： typedef struct
{ ElemType a[MAXSIZE]; /* 一维数组 子域 */ int length; /* 表长度子域 */ }SqList; /* 顺序存储的结构体类型 */
（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料，供学生参考。比如，主函数中简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术。在学习数据结构的初级阶段，并不强要求学生一定使用“菜单设计”技术，同学们可以在main()函数中直接写几个简单的调用语句，就象前面的复数处理程序中的main()一样。但是随着学习的深入，尽早学会使用“菜单设计”技术，会明显提高编程和运行效率。 [源程序]
#include
#define MAXSIZE 20 /* 数组最大界限 */ typedef int ElemType; /* 数据元素类型 */ typedef struct
{ ElemType a[MAXSIZE]; /* 一维数组 子域 */ int length; /* 表长度子域 */ }SqList; /* 顺序存储的结构体类型 */ SqList a,b,c; /* 函数声明 */
void creat_list(SqList *L); void out_list(SqList L);
void insert_sq(SqList *L,int i,ElemType e);
16
ElemType delete_sq(SqList *L,int i); int locat_sq(SqList L,ElemType e); /* 主函数 */ main()
{ int i,k,loc; ElemType e,x; char ch; do { printf(\
printf(\建立线性表 \
printf(\在i位置插入元素e\
printf(\删除第i个元素，返回其值\ printf(\查找值为 e 的元素\ printf(\结束程序运行\
printf(\ printf(\请输入您的选择（1，2，3，4，6）\ scanf(\ switch(k) { case 1:{ creat_list(&a); out_list(a); } break; case 2:{ printf(\ insert_sq(&a,i,e); out_list(a); } break; case 3:{ printf(\ x=delete_sq(&a,i); out_list(a); printf(\ } break; case 4:{ printf(\ loc=locat_sq(a,e); if (loc==-1) printf(\未找到 %d\ else printf(\已找到，元素位置是 %d\ } break; } /* switch */ }while(k!=6);
printf(\再见！\
printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */ /* 建立线性表 */
void creat_list(SqList *L) { int i;
printf(\
for(i=0;i
17
scanf(\ } } /* creat_list */ /* 输出线性表 */
void out_list(SqList L) { int i; char ch; printf(\
for(i=0;i<=L.length-1;i++) printf(\ printf(\打回车键，继续。“); ch=getch(); } /* out_list */
/* 在线性表的第i个位置插入元素e */
void insert_sq(SqList *L,int i,ElemType e) { int j;
if (L->length==MAXSIZE) printf(\ else if(i<1||i>L->length+1) printf(\
else { for(j=L->length-1; j>i-1; j--) L->a[j+1]=L->a[j]; /* 向后移动数据元素 */ L->a[i-1]=e; /* 插入元素 */ L->length++; /* 线性表长加1 */ }
} /* insert_sq */
/* 删除第i个元素，返回其值 */
ElemType delete_sq(SqList *L, int i) { ElemType x; int j;
if( L->length==0) printf(\是空表。underflow !\ else if(i<1||i> L->length){ printf(\ x=-1;} else { x=L->a[i-1]; for(j=i; j<=L->length-1; j++) L->a[j-1]=L->a[j]; L->length--; } return(x);
} /* delete_sq */
/* 查找值为 e 的元素，返回它的位置 */ int locat_sq(SqList L, ElemType e) { int i=0;
while(i<=L.length-1 && L.a[i]!=e) i++; if(i<=L.length-1) return(i+1); else return(-1);
18
}/* locat_sq */
2. 线性表的链表存储表示（结构）及实现。 阅读下列程序请注意几个问题：
（1）关于线性表的链表存储结构的本质是：在逻辑上相邻的两个数据元素ai-1, ai，在存储地址中可以不相邻,既地址不连续。不同的教材的表示基本是一致的。 typedef struct LNode
{ ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */ }LNode; /* 结点结构类型 */
（2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供关于链表操作的资料，供学生参考。可以看到本程序的main()与前一程序的main()函数的结构十分相似。稍加改动还可为其他题目的源程序所用。 [源程序]
#include
{ ElemType data; /* 数据子域 */ struct LNode *next; /* 指针子域 */ }LNode; /* 结点结构类型 */ LNode *L;
/* 函数声明 */ LNode *creat_L();
void out_L(LNode *L);
void insert_L(LNode *L,int i ,ElemType e); ElemType delete_L(LNode *L,int i); int locat_L(LNode *L,ElemType e); /* 主函数 */ main()
{ int i,k,loc; ElemType e,x; char ch; do { printf(\
printf(\建立线性链表 \
printf(\在i位置插入元素e\
printf(\删除第i个元素，返回其值\ printf(\查找值为 e 的元素\ printf(\结束程序运行\
printf(\
printf(\请输入您的选择 (1,2,3,4,5)\
19
switch(k) { case 1:{ L=creat_L( ); out_L(L); } break; case 2:{ printf(\ insert_L(L,i,e); out_L(L); } break; case 3:{ printf(\ x=delete_L(L,i); out_L(L); if(x!=-1) printf(\ } break; case 4:{ printf(\ loc=locat_L(L,e); if (loc==-1) printf(\未找到 %d\ else printf(\已找到，元素位置是 %d\ } break; } /* switch */ printf(\ }while(k>=1 && k<5);
printf(\再见！\
printf(“\\n 打回车键，返回。“); ch=getch(); } /* main */
/* 建立线性链表 （ 11，22 ，33 ） */ LNode *creat( )
{ LNode *h,*p,*s; ElemType x;
h=(LNode *)malloc(sizeof(LNode)); /* 分配头结点 */
h h->next=NULL; ∧ p=h;
printf(\输入第一个数据元素 */ while( x!=-111) /* 输入-111，结束循环 */ { s=(LNode *)malloc(sizeof(LNode)); /* 分配新结点 */ s->data=x; s->next=NULL; p->next=s; p=s;
printf(\输入下一个数据*/ }
return(h); h 11 33 ∧ 22 } /* creat_L */
建成后的链表h
20