实验1.1顺序表的建立
1.建立含有N个元素的顺序表并输出该表各元素的值。元素的个数及元素的值由键盘输入，元素类型为整型。
2.实验要点及说明
参考程序中首先调用初始化函数InitList_Seq动态分配顺序表的存储空间，如图所示。顺序表L的长度length是表中所含元素的个数，初始值为0。Listsize是当前已分配的存储空间的容量，是以元素大小为单位的。
建立一个头文件SeqList.h，避免在后面的.c程序中代码冗余。.h文件一般包括程序中必须用到的系统包含文件的声明、常量定义、结构定义及线性表的初始化等基本操作。
3.参考代码
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW 0
#define LIST_INIT_SIZE 100 //存储空间初始分配量
#define LISTINCREMENT 10 //存储空间分配增量
typedef struct
{
int *elem;
int length; //当前表长
int listsize; //当前分配的存储容量
}SeqList;
int initList_Seq(SeqList *L) //构造一个空的顺序表
{
L->elem = (int *)malloc(LIST_INIT_SIZE*sizeof(int));
if(!L->elem) //存储空间分配失败
{
printf("Out of space!!\n");
exit(OVERFLOW); //关闭程序
}
L->length = 0; //空表长度为0；
L->listsize = LIST_INIT_SIZE; //分配表存储容量
return OK;
}
int Output_SeqList(SeqList L)
{
int i;
for(i=0;i<L.length;i++)
printf("%4d",L.elem[i]);
printf("\n");
return OK;
}
// 头文件SeqList.h结束
#include "SeqList.h"
int CreateList_Seq(SeqList *L){
int *p,*q,e;
printf("请输入元素值：");
q = &L->elem[0];
for(p=&L->elem[L->length-1];q<=p;q++)
{
scanf("%d",&e);
*q=e;
}
printf("CreateList_Seq OK \n");
}
/*
void CreateList_Seq(SeqList L,int locate)
{
int i, n;
n= L.length;
for(i=locate; i< n; i++){
scanf("%d",&L.elem[i]);
}
}
*/
#include "CreateList_Seq.h"
int main()
{
SeqList L;
initList_Seq(&L);
int n;
printf("请输入元素个数n:");
scanf("%d",&n);
printf("请输入%d个值: ",n);
L.length = n;
CreateList_Seq(L);
printf("调用Output_SeqList输出：\n");
Output_SeqList(L);
return OK;
}
4.思考题
（1）如果按照由表尾至表头的秩序输入数据元素，应如何建立顺序表
把指针指向尾指针插入
include "SeqList.h"
int CreateList_Seq(SeqList *L){
int *p,*q,e;
printf("请输入元素值：");
q = &L->elem[0];
for(p=&L->elem[L->length-1];p>=q;--p)
{
scanf("%d",&e);
*p=e;
}
}
（2）设顺序表L={a1，a2……am，b1,b2……bn}，请设计一个算法将L中元素的两部分互换，互换之后为L={b1,b2……bn，a1，a2……am}
int Exchange_Seq(SeqList *L,int n)
{
int *p,*q,tmp,i;
p=&L->elem[n-1];
for(q=&L->elem[0]; q<=p-1; q++)
{
tmp = *q;
*q = *p;
for(i=0;i<(L->length-n);i++,p++)
*p = *( p + 1 );
*p = tmp;
p=&L->elem[n-1];
Output_SeqList(*L);
printf("\n");
}
return printf("Exchange_Seq OK");
}
int main()
{
SeqList L;
initList_Seq(&L);
int n,m;
printf("请输入元素个数n:");
scanf("%d",&n);
printf("请输入%d个值: ",n);
L.length = n;
CreateList_Seq(&L);
printf("调用Output_SeqList输出：\n");
Output_SeqList(L);
printf("请输入第二部分开始的位置m：");
scanf("%d",&m);
Exchange_Seq(&L,m);
}
实验1.2顺序表元素的插入
1.先建立一个顺序表L={12,13,21,24,28,30,42,77}，然后在第i个位置插入一个数据元素25，并返回是否插入成功标志。如果插入成功，顺序表表长增加1
2.实验要点及说明
注意如何取到第i个元素的地址q，以及如何将原第i至第n个元素（这其中一共有n-i+1个元素）依次后移。顺序表插入前、后的状态图如图所示。
3.参考代码
#include "SeqList.h" //源代码请看实验1.1顺序表的建立
int ListInsert_Seq(SeqList *L,int i,int e) 在第 i 个元素之前插入元素至顺序表
{
int *p,*q,*newbase;
if((i<1)||(i>L->length+1))
return ERROR;
if(L->length>=L->listsize) // 当前空间已满，增加分配
{
newbase = (int *)realloc(L->elem,(L->length+LISTINCREMENT)*sizeof(int));
if(!newbase)
exit(OVERFLOW);
L->elem = newbase;
L->listsize += LISTINCREMENT;
}
q = &L->elem[i-1]; // q 指向插入位置
for(p=&L->elem[L->length-1];p>=q;--p) // 第 n 至第 i 个元素依次后移一个位置
*(p+1) = *p;
*q = e; // 插入新元素 e
L->length++; /// 注意！要传值回去，形参L 必须用指针变量
return OK;
}
int main()
{
SeqList L;
initList_Seq(&L);
int i,n,e;
printf("\nInput the length of the list L: ");
scanf("%d",&n);
L.length = n;
printf("L.length = %d,n=%d\n",L.length,n);
CreateList_Seq(L);
printf("Input the insert location: ");
scanf("%d",&i);
printf("input 要插入 e 的值：");
scanf("%d",&e);
if(ListInert_Seq(&L,i,e))
{
printf("Output the datas: ");
Output_SeqList(L);
}else
printf("Can't insert the data!\n");
}
4.思考题
（1）如何在顺序表A的第i个元素之后插入一个新元素e
把ListInsert_Seq中的q = &L->elem[i-1];改成q = &L->elem[i];即可
（2）若顺序表L中的元素递增有序，请设计一个算法，将e插入到顺序表L的适当位置，使得插入后仍然保持L的有序性。
#include "CreateList_Seq.h"
int ListInsert_2_Seq(SeqList *L,int e) //在第i个元素之前插入元素至顺序表
{
int *p,*q,*newbase,i;
if(L->length>=L->listsize)
{
newbase = (int *)realloc(L->elem,(L->length+LISTINCREMENT)*sizeof(int));
printf("newbase is : %d\n.",newbase);
if(!newbase)
exit(OVERFLOW);
L->elem = newbase;
printf("L->elem is : %d\n",L->elem);
L->listsize += LISTINCREMENT;
}
for(i=0;i<(L->length-1);i++)
{
if(L->elem[i]>e)
break;
}
q = &L->elem[i]; //q指向插入位置
for(p=&L->elem[L->length-1];p>=q;--p)
*(p+1) = *p;
*q = e;
L->length++;
return OK;
}
int main()
{
SeqList L;
initList_Seq(&L);
int i,n,e;
printf("\nInput the length of the list L: ");
scanf("%d",&n);
L.length = n;
printf("L.length = %d,n=%d\n",L.length,n);
CreateList_Seq(&L);
printf("input 要插入 e 的值：");
scanf("%d",&e);
if(ListInsert_2_Seq(&L,e))
{
printf("Output the datas: ");
Output_SeqList(L);
}else
printf("Can't insert the data!\n");
}
实验1.3顺序表元素的删除
1.先建立一个顺序表L={22,13,21,24,38,30,42,77}，然后删除表中第i个元素并用变量*e返回其值。同时返回是否删除成功标志，若删除成功，L的长度减1.
2.实验要点及说明
注意如何取到第i个元素的地址p，以及如何将原第i+1至第n个元素（这其中一共n-i个元素）依次前移。顺序表元素删除前、后的状态示意图如下：
3.参考代码：
#include "SeqList.h" //源代码请看实验1.1顺序表的建立
int ListDelete_Seq(SeqList *L, int i, int *e) 元素删除函数
{
int *p,*q;
if((i<1)||(i>L->length))
return ERROR;
p = &L->elem[i-1];找到第i个元素的地址，并该位置的值存储到e中
*e = *p;
q = L->elem + L->length-1;
for(++p; p<=q; p++)在第i+1至第n个元素依次前移
*(p-1) = *p;
L->length--; 顺序表长度减1
return OK;
}
void main()
{
int i,n,e;
SeqList L;
InitList_Seq(&L);
printf("\nInput the length of the list L: ");
scanf("%d",&n);
L.length = n;
CreateList_Seq(L);
printf("Input the delete location: ");
scanf("%d",&i);
if(ListDelete_Seq(&L,i,&e))
{ printf("Delete the data %d:\n",e);
printf("Output the datas: ");
Output_SeqList(L);
}
else
printf("Can't find the delete data!\n");
}
4.思考题
（1）在一个值递增有序的顺序表中，如何删除所有值大于a而小于b的元素呢？
#include "CreateList_Seq.h"
int ListDelete_1_Seq(SeqList *L,int a,int b)
{
int i,*p,*q;;
for(i=0;i<(L->length-1);)
{
if(L->elem[i] > a && L->elem[i] < b)
{
p = &L->elem[i];
q = &L->elem[(L->length-1)];
for(++p; p<=q;p++) //在第i+1至第n个元素依次前移
*(p-1) = *p;
L->length--;
}else
i++;
}
return OK;
}
void main()
{
int a,b,n;
SeqList L;
initList_Seq(&L);
printf("\nInput the length of the list L: ");
scanf("%d",&n);
L.length = n;
CreateList_Seq(&L);
printf("Input the delete location a b : ");
scanf("%d%d",&a,&b);
if(ListDelete_1_Seq(&L,a,b))
{
printf("Output the datas: ");
Output_SeqList(L);
}else
printf("Can't find the delete data!\n'");
}
（2）若用顺序表表示集合，如何实现集合的差运算A-B
#include "CreateList_Seq.h"
int ListDelete_2_Seq(SeqList *A,SeqList *B)
{
int *p,*q,*l,*m;
p = &A->elem[0];
m = &B->elem[B->length-1];
for(l = &B->elem[0]; l <= m; l++)
{
if(*p == *l) //判断是否相等
{
for(; p<=(q = &A->elem[A->length-1]);p++) //在第i+1至第n个元素依次前移
*(p-1) = *p;
p = &A->elem[0];
A->length--;
}
}
printf("A-B OK!\n");
}
int main()
{
int n;
SeqList A,B;
initList_Seq(&A);
printf("\nInput the length of the list A: ");
scanf("%d",&n);
A.length = n;
CreateList_Seq(&A);
Output_SeqList(A);
initList_Seq(&B);
printf("\nInput the length of the list B: ");
scanf("%d",&n);
B.length = n;
CreateList_Seq(&B);
Output_SeqList(B);
ListDelete_2_Seq(&A,&B);
printf("Output the datas:");
Output_SeqList(A);
}
实验1.4顺序表的查找
1.建立一个顺序表，查找表中第1个与指定元素相等的元素。若存在，则返回该元素在表中的位置（下标）；否则返回-1.
2.实验要点及说明
参考程序中，若找到满足条件的元素，返回的是表中第1个满足条件的元素的下标，而不是其序号。
3.参考代码
#include "SeqList.h" //源代码请看实验1.1顺序表的建立
int LocateElem(SeqList L,int e)
{
int i;
i = 0;
while(i<=L.length-1 && L.elem[i] != e)
++i;
if(i<L.length)
return i;
else
return -1;
}
void main()
{
int i,n,e;
SeqList L;
InitList_Seq(&L);
printf("\nInput the length of the list L: ");
scanf("%d",&n);
L.length = n;
CreateList_Seq(L);
printf("Input the search data: ");
scanf("%d",&e);
if((i=LocateElem(L,e))>=0)
printf("The search data subscript is %d in the L\n",i);
else
printf("There is no search data in the L!\n");
printf("Output the datas: ");
Output_SeqList(L);
}
4.思考题
（1）如何将所有值为x的元素移到顺序表的末尾？
#include "CreateList_Seq.h"
int LocateElem_1(SeqList L,int x)
{
int temp,*p,*q,*e;
q=&L.elem[L.length-1];
p=&L.elem[0];
for(;p<=q;)
{
if(*p==x)
{
temp = *p;
for(e = p+1; e<=q;e++) //在第p+1至第q个元素依次前移
*(e-1) = *e;
*q = temp;
q--; //前移q指针防止判断出错
}
else
p++;
Output_SeqList(L);
}
}
void main()
{
int n,x;
SeqList L;
initList_Seq(&L);
printf("\nInput the length of the list L: ");
scanf("%d",&n);
L.length = n;
CreateList_Seq(&L);
printf("Input the search data: ");
scanf("%d",&x);
LocateElem_1(L,x);
printf("Output the datas: ");
Output_SeqList(L);
}
（2）在按元素值非降序排列的顺序表中，如何找出重复次数最多的元素？
#include "CreateList_Seq.h"
int LocateElem_2(SeqList L)
{
int i,j,maxelem=0,count=0,max=0;
for(i=0; i<L.length-1; i++)
{
for(j=0;j<=L.length-1; j++)
{
if(L.elem[j]==L.elem[i])
count++;
}
if(max<count)
{
max=count;
count=0;
maxelem=L.elem[i];
}
else
count=0;
}
return maxelem;
}
void main()
{
int n,maxelem;
SeqList L;
initList_Seq(&L);
printf("\nInput the length of the list L: ");
scanf("%d",&n);
L.length = n;
CreateList_Seq(&L);
maxelem = LocateElem_2(L);
printf("重复次数最多的元素为：%d",maxelem);
}
版权声明：本文为xiahuayong原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。