//图的基本操作算法
//1.
void CreatGraph (AdjList g) //建立有n个顶点和m 条边的无向图的邻接表存储结构
5
{
int n,m;
scanf("%d%d",&n,&m);
for(i =1,i<=n;i++) //输入顶点信息,建立顶点向量
{
scanf(&g[i].vertex);
10
g[i].firstarc=null;
}
for(k=1;k<=m;k++) //输入边信息
{
15
scanf(&v1,&v2); //输入两个顶点
i=GraphLocateVertex (g,v1);
j=GraphLocateVertex (g,v2); //顶点定位
p=(ArcNode *)malloc(sizeof(ArcNode)); //申请边结点
p->adjvex=j;
20
p->next=g[i].firstarc;
g[i].firstarc=p; //将边结点链入
p=(ArcNode *)malloc(sizeof(ArcNode)); //无向图双向连接
p->adjvex=i;
p->next=g[j].firstarc;
25
g[j].firstarc=p;
}
}//算法CreatGraph结束
//2.
30
void CreatAdjList(AdjList g) //建立有向图的邻接表存储结构
{
int n;
scanf("%d",&n);
35
for (i=1;i<=n;j++)
{
scanf(&g[i].vertex);
g[i].firstarc=null;
}//输入顶点信息
40
scanf(&v1, &v2);
while(v1 && v2) //题目要求两顶点之一为0表示结束
{
i=GraphLocateVertex(g2,v1);
p=(ArcNode*)malloc(sizeof(ArcNode)); //有向图只需要单边
45
p->adjvex=j;
p->next=g[i].firstarc;
g[i].firstarc=p;
scanf(&v1,&v2);
}
50
}
//5．
void InvertAdjList(AdjList gin,gout) //将有向图的出度邻接表改为按入度55
建立的逆邻接表
{
for(i=1;i<=n;i++) //设有向图有n个顶点,建逆邻接表的顶点向量。
{
gin[i].vertex=gout[i].vertex;
60
gin.firstarc=null;
}//逆邻接表顶点初始化
for(i=1;i<=n;i++) //邻接表转为逆邻接表
{
p=gout[i].firstarc; //取指向邻接表的指针邻接表头结点i的第一65
条边
while(p!=null)
{
j=p->adjvex; // 邻接表
s=(ArcNode *)malloc(sizeof(ArcNode)); //申请逆邻接表的边70
结点空间
s->adjvex=i; //对逆邻接表的
s->next=gin[j].firstarc; //对逆邻接表的
gin[j].firstarc=s; //
p=p->next; // 邻接表中找下一个邻接点。
75
}//while
}//for
}
80
//6.
void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm) //将图的邻接表表示转换为邻接矩阵表示
{
for(i=1;i<=n;i++) //设图有n个顶点,邻接矩阵初始化。
85
for(j=1;j<=n;j++)
gm[i][j]=0;
for(i=1;i<=n;i++)
{
90
p=gl[i].firstarc; //取第一个邻接点。
while(p!=null)
{
gm[i][p->adjvex]=1;
p=p->next;
95
} //下一个邻接点
}//for
}//算法结束
//7.
100
void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl ) //图的邻接矩阵表示法转换为邻接表表示法
{
for(i=1;i<=n;i++) //邻接表表头向量初始化。
105
{
scanf(&gl[i].vertex);
gl[i].firstarc=null;
}
for(i=1;i<=n;i++)
110
for(j=1;j<=n;j++)
if(gm[i][j]==1)
{
p=(ArcNode *)malloc(sizeof(ArcNode)) ; //申请结点空间。
115
p->adjvex=j; //顶点i的邻接点是j
p->next=gl[i].firstarc; //下一个邻接边结点
gl[i].firstarc=p; //链入顶点i的邻接点链表中
}
}//end
120
//[算法讨论] 算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。
//9.
125
void DeletEdge(AdjList g,int i,j)
//在用邻接表方式存储的无向图g中,删除边(i,j)
{
p=g[i].firstarc;
pre=null; //删顶点i 的边结点(i,j),pre是前驱指针
130
while(p)
if(p->adjvex==j) //找到了要删除的结点
{
if(pre==null)
g[i].firstarc=p->next; //要删除的是第一个邻接点,重新设135
置第一邻接点
else
pre->next=p->next; //要删除的不是第一邻接点重新设置pre后链跳过p 链上p->next
free(p);
140
} //释放结点空间。
else
{
pre=p;
p=p->next;
145
}//没找到,沿链表继续查找
p=g[j].firstarc;
pre=null; //删顶点j 的边结点(j,i)
while(p)
if(p->adjvex==i)
150
{
if(pre==null)g[j].firstarc=p->next;
else
pre->next=p->next;
free(p);
155
}//释放结点空间。
else
{
pre=p;
p=p->next;
160
}//沿链表继续查找
}// DeletEdge
//[算法讨论] 算法中假定给的i,j 均存在,否则应检查其合法性。若未给顶点编号,而给出顶点信息,
//则先用顶点定位函数求出其在邻接表顶点向量中的下标i和j。
165
//10.
void DeleteArc(AdjList g,vertype vi,vj)
//删除以邻接表存储的有向图g的一条弧
{
i=GraphLocateVertex(g,vi);
j=GraphLocateVertex(g,vj); //顶点定位
p=g[i].firstarc;
pre=null;
175
while(p)
if(p->adjvex==j)
{
if(pre==null)
g[i].firstarc=p->next;
180
else
pre->next=p->next;
free(p);
}//释放结点空间。
else
185
{
pre=p;
p=p->next;
}
}//结束不用再查找j 比无向图省事
190
//★★图的遍历算法★★
//12.在有向图的邻接表中,求顶点的出度容易,只要简单在该顶点的邻接点链表中查结点个数即可。
195
//而求顶点的入度,则要遍历整个邻接表。
int count (AdjList g , int k )
//在n个顶点以邻接表表示的有向图g中,求指定顶点k(1<=k<=n)的入度。
{
int count =0;
200
for(i=1;i<=n;i++) //求顶点k的入度要遍历整个邻接表。
if(i!=k) //顶点k的邻接链表不必计算
{
p=g[i].firstarc;//取顶点i 的邻接边
while(p)
{
205
if(p->adjvex==k)
count++;
p=p->next;
}//while
210
}//if
return(count); //顶点k的入度.
}
//8.在有向图中,判断顶点Vi和顶点Vj间是否有路径,可采用遍历的方法,从215
顶点Vi出发,
//不论是深度优先遍历(dfs)还是宽度优先遍历(bfs),在未退出dfs或bfs前,若访问到Vj,
//则说明有通路,否则无通路。设一全程变量flag,初始化为0,若有通路,则220
flag=1。
//算法1:
int visited[]=0; //全局变量,访问数组初始化
int dfs(AdjList g , vertype vi ,vj)
//以邻接表为存储结构的有向图g,判断顶点Vi到Vj是否有通路,返回1或0 225
表示有或无
{
visited[vi]=1; //visited是访问数组,假设顶点的信息就是顶点编号。
p=g[vi].firstarc; //第一个邻接点。
while( p!=null)
230
{
j=p->adjvex;
if (j==vj)
{
flag=1;
235
return(1);
} //vi 和vj 有通路。
if (visited[j]==0)
dfs(g,j,vj); //递归进行深度遍历
p=p->next; //遍历完返回,继续下一边
240
}//while
if(!flag)
return(0); //最后没有通路返回0
}//结束
//[算法讨论] 若顶点vi和vj 不是编号,必须先用顶点定位函数,查出其在邻245
接表顶点向量中的下标i和j。
//下面算法2输出vi 到vj的路径,其思想是用一个栈存放遍历的顶点,遇到顶点vj时输出路径。
//算法2:
void dfs(AdjList g , int i,j)
250
//有向图g的顶点vi(编号i)和顶点vj(编号j)间是否有路径,如有,则输出。
{
int top=0, stack[]; //stack是存放顶点编号的栈
visited[i]=1; //visited 数组在进入dfs前已初始化。
stack[++top]=i;
255
p=g[i].firstarc; //求第一个邻接弧结点.
while(p)
{
if(p->adjvex==j) //弧p的顶点即为j,遇到顶点vj 输出路径
{
stack[++top]=j; //顶点j入栈
260
printf( "顶点vi 和vj 的路径为:\n");
for(i=1; i<=top; i++)
printf( "%4d",stack[i]);
exit(0);
265
}//if
else
if (visited[p->adjvex]==0) //弧p的顶点p->adjvex尚未被访问
{
dfs(g,p->adjvex,j);
270
top--;
p=p->next;
}//递归进行深度遍历出栈
}//while
}//结束算法2
275
//算法3:本题用非递归算法求解。
int Connectij (AdjList g , vertype vi , vj )
//判断n个顶点以邻接表表示的有向图g中,顶点Vi 各Vj 是否有路径,有则返回1,否则返回0。
280
{
for(i=1;i<=n;i++)
visited[i]=0; //访问标记数组初始化。
i=GraphLocateVertex(g,vi); //顶点定位,不考虑vi或vj不在图中的情285
况。
j=GraphLocateVertex(g,vj);
int stack[],top=0;
stack[++top]=i;
while(top>0)
290
{
k=stack[top--];
p=g[k].firstarc;
while(p!=null && visited[p->adjvex]==1)
p=p->next; //查第k个链表中第一个未访问的弧结点。
295
if(p==null)
top--;
else
{
i=p->adjvex;
300
if(i==j)
return(1);//顶点vi和vj 间有路径。
else
{
visited[i]=1;
305
stack[++top]=i;
}//else
}//else
}//while
310
return(0);
}//顶点vi和vj 间无通路。
//13.有向图判断回路要比无向图复杂。利用深度优先遍历,将顶点分成三类: 315
未访问;
//已访问但其邻接点未访问完;已访问且其邻接点已访问完。下面用0,1,2表示这三种状态。
//前面已提到,若dfs(v)结束前出现顶点u到v的回边,则图中必有包含顶点v 和u的回路。
320
//对应程序中v的状态为1,而u是正访问的顶点,若我们找出u的下一邻接点的状态为1,就可以输出回路了。
void Print(int v,int start ) //输出从顶点start开始的回路。
{
for(i=1;i<=n;i++)
325
if(g[v][i]!=0 && visited[i]==1 ) //若存在边(v,i),且顶点i的状态为1。
{
printf("%d",v);
if(i==start)
330
printf("\n");
else
Print(i,start);//递归
break;
}
335
void dfs(int v)
{
340
visited[v]=1; //0:未访问;1:已访问但其邻接点未访问完; 2:已访问且其邻接点已访问完
for(j=1;j<=n;j++ )
if (g[v][j]!=0) //存在边(v,j)
345
if (visited[j]!=1) //0:未访问或2:已访问且其邻接点已访问完
{
if(!visited[j])
dfs(j);
} //0:未访问j未访问深度遍历j
350
else
{
cycle=1;
Print(j,j);
} // 1:已访问且其邻接点未访问完
355
visited[v]=2; //访问v完成2:已访问且其邻接点已访问完}//dfs
360
void find_cycle() //判断是否有回路,有则输出邻接矩阵。visited数组为全局变量。
{
for(i=1;i<=n;i++)
visited[i]=0;
365
for(i=1;i<=n;i++ )
if(!visited[i])
dfs(i);
}//find_cycle
370
//16.本题应使用深度优先遍历,从主调函数进入dfs(v)时,开始记数,若退出
dfs()前,
//已访问完有向图的全部顶点(设为n个),则有向图有根,v为根结点。
//将n个顶点从1到n编号,各调用一次dfs()过程,就可以求出全部的根结点。375
//题中有向图的邻接表存储结构、记顶点个数的变量、以及访问标记数组
等均设计为全局变量。
//建立有向图g的邻接表存储结构参见上面第2题,这里只给出判断有向图
是否有根的算法。
380
int num=0, visited[]=0; //num记访问顶点个数,访问数组visited初始化。
const n=用户定义的顶点数;
AdjList g; //用邻接表作存储结构的有向图g。
void dfs(v)
385
{
visited[v]=1;
num++; //访问的顶点数＋1
if(num==n)
{
printf("%d是有向图的根。\n",v);
390
num=0;
}//重新计数
p=g[v].firstarc; //第一边结点
while (p)
395
{
if(visied[p->adjvex]==0)
dfs(p->adjvex); //未访问递归深度遍历
p=p->next;
400
}//while
visited[v]=0;
num--; //恢复顶点v 全局变量重新计数便于后边遍历
}//dfs
405
void JudgeRoot() //判断有向图是否有根,有根则输出之。
{
static int i ;
for(i=1;i<=n;i++ ) //从每个顶点出发,调用dfs()各一次。
410
{
num=0;
visited[1..n]=0;
dfs(i);
}
415
}// JudgeRoot
//算法中打印根时,输出顶点在邻接表中的序号(下标),若要输出顶点信息,可使用g[i].vertex。
420
//17.图的遍历可以求出图的连通分量。进入dfs或bfs一次,就可以访问到图的一个连通分量的所有顶点。
void dfs ()
{
425
visited[v]=1;
printf("%3d",v); //输出连通分量的顶点。
p=g[v].firstarc;
while(p!=null)
{
430
if(visited[p->adjvex]==0)
dfs(p->adjvex); //深度递归访问
p=p->next;
}//while
}// dfs
435
void Count() //深度优先遍历求图中连通分量的个数
{
int k=0;
static AdjList g ; //设无向图g有n个结点
440
for(i=1;i<=n;i++ )
if(visited[i]==0)
{
printf ("\n第%d个连通分量:\n",++k);
dfs(i);
}
445
}//Count
//算法中visited[]数组是全程变量,每个连通分量的顶点集按遍历顺序输出。
//这里设顶点信息就是顶点编号,否则应取其g[i].vertex分量输出。
450
//18.
void bfs(AdjList GL,vertype v ) //从v发非递归广度优先遍历以邻接表为
存储结构的无向图GL。
{
visited[v]=1;
455
printf( "%3d",v); //输出第一个遍历的顶点。
QueueInit(Q);
QueueIn(Q ,v); //先置空队列,然后第一个顶点v入队列,设队列容量足够大
460
while(!QueueEmpty(Q))
{
v=QueueOut(Q); // v出队列。
p=GL[v].firstarc; // GL是全局变量,第一个邻接边结点
while(p!=null)
465
{
if(visited[p->adjvex]==0) //第一个邻接点未访问
{
printf("%3d",p->adjvex);
visited[p->adjvex]=1;
470
QueueIn(Q,p->adjvex);
}//if //访问入队
p=p->next; //下一个邻接边结点即广度优先
}//while
}// while (!QueueEmpty(Q))
475
}//bfs
void BFSCOM() //广度优先搜索,求无向图Ｇ的连通分量。
{
int count=0; //记连通分量个数。
480
for (i=1;i<=n;i++)
visited[i]=0;
for (i=1;i<=n;i++)
if (visited[i]==0)
485
{
printf("\n第%d个连通分量:\n",++count);
bfs(i);
}//if
}//BFSCOM
490
//27.D_搜索类似BFS,只是用栈代替队列,入出队列改为入出栈。
//查某顶点的邻接点时,若其邻接点尚未遍历,则遍历之,并将其压入栈中。
//当一个顶点的所有邻接点被搜索后,栈顶顶点是下一个搜索出发点。
495
void D_BFS(AdjList g ,vertype v0) // 从v0顶点开始,对以邻接表为存储结构的图g进行D_搜索。
{
int s[], top=0; //栈,栈中元素为顶点,仍假定顶点用编号表示。500
for(i=1,i<=n;i++)
visited[i]=0; //图有n个顶点,visited数组为全局变量初始化for(i=1,i<=n;i++) //对n个顶点的图g进行D_搜索
if(visited[i]==0) //未访问
{
505
s[++top]=i;
visited[i]=1;
printf( "%3d",i); //入栈;访问
while(top>0)
{
510
i=s[top--]; //退栈,准备找邻接点
p=g[i].firstarc; //取第一个邻接边结点
while(p!=null) //处理顶点的所有邻接边结点
{
j=p->adjvex; //邻接点
515
if(visited[j]==0) //未访问的邻接点
{
visited[j]=1;
printf( "%3d",i);
s[++top]=j;
520
} //访问并入栈
p=p->next; //广度优先遍历
} //下一个邻接点
}//while(top>0)
} //if
525
}//D_BFS
//20.
void Traver(AdjList g,vertype v)
530
//图g以邻接表为存储结构,算法从顶点v开始实现非递归深度优先遍历。
{
struct arc *stack[];
visited[v]=1;
535
printf(v); //输出顶点v
top=0;
p=g[v].firstarc;
stack[++top]=p;
540
while(top>0 || p!=null)
{
while(p)
if( p && visited[p->adjvex])
p=p->next; //已访问找下一个
545
else
{
printf(p->adjvex);
visited[p->adjvex]=1; //访问
stack[++top]=p;
550
p=g[p->adjvex].firstarc; //入栈深度遍历
}//else
if (top>0)
{
555
p=stack[top--];
实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题
要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE;
实现顺序表的各种基本运算 一、实验目的 了解顺序表的结构特点及有关概念，掌握顺序表的各种基本操作算法思想及其实现。 二、实验内容 编写一个程序，实现顺序表的各种基本运算： 1、初始化顺序表； 2 、顺序表的插入； 3、顺序表的输出； 4 、求顺序表的长度 5 、判断顺序表是否为空； 6 、输出顺序表的第i位置的个元素； 7 、在顺序表中查找一个给定元素在表中的位置； 8、顺序表的删除； 9 、释放顺序表 三、算法思想与算法描述简图
主函数main
四、实验步骤与算法实现 #in clude
《数据结构》实验报告一 顺序表的基本操作 班级：网络工程学号：12015242183 实验日期：2016.9.25 姓名：邓宗永 程序文件名及说明：sequenlist 顺序表 一、实验目的 1、掌握使用Turbo C3.0上机调试线性表的基本方法； 2、掌握顺序表的基本操作：插入、删除、查找以及线性表合并等运算。 二、实验要求 1、认真阅读和掌握实验的程序。 2、上机运行程序。 3、保存和打印出程序的运行结果，并结合程序进行分析。 4、按照你对线性表的操作需要，编写写主程序并运行，打印出文件清单和运行结果 三、注意事项： 在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 四、实验内容 1.顺序表的查找、插入与删除。设计算法，实现线性结构上的顺序表的产生以及元素的查找、插入与删除。具体实现要求： （1）从键盘输入10个整数，产生顺序表，并输入结点值。 （2）从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。 （3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x 插入在对应位置上，输出顺序表所有结点值，观察输出结果。 （4）从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 五、实验报告必须写明内容 1.程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设 计，符号名说明等） 程序的结构：通过子函数实现输出，删除，插入，查找等功能，高耦合低内聚 数据结构：线性结构，顺序储存 输入/输出设计：根据屏幕提示，从键盘读取数据 2.源程序及注释： #include
顺序表的基本操作 /*sqList.h 文件*/ #define LIST_INIT_SIZE 50 /*初始分配的顺序表长度*/ #define INCREM 10 /*溢出时，顺序表长度的增量*/ #define OVERFLOW 1 #define OK 0 #define ERROR -1 typedef int ElemType; /*定义表元素的类型*/ typedef struct SqList{ ElemType *elem; /*存储空间的基地址*/ int length; /*顺序表的当前长度*/ int listsize; /*当前分配的存储空间*/ }SqList; /*sqListOp.h 文件*/ #include "Sqlist.h" int InitList_sq(SqList &L); //顺序表创建函数定义 void FreeList_sq(SqList &L); //顺序表销毁函数定义 int ListInsert_sq(SqList &L, int i, ElemType e); //在顺序表的位置i插入元素e void PrintList_sq(SqList &L); //遍历并输出顺序表所有元素 int ListDelete_sq(SqList &L, int i,ElemType &e); //删除顺序表第i个元素的 bool ListEmpty(SqList &L); //判断顺序表是否为空 int LocateElem_sq(SqList L,ElemType e); //在顺序表里查找出第1个与e相等的数据元素位置//已知线性表La和Lb的元素按值非递减排列 //归并后的La和Lb得到新的顺序线性表Lc，Lc的元素也是按值非递减排列 void MergeList_sq(SqList La,SqList Lb, SqList &Lc); /*sqListOp.cpp文件*/ #include
数据结构实验顺序表的实现 姓名 学号 专业班级
实验名称：顺序表的实现 一．实验目的： 1.掌握线性表的顺序存储结构； 2.验证顺序表的基本操作的实现； 3.理解算法与程序的关系，能够将顺序表转换为对应程序； 二.实验内容： 1.建立含有若干元素的顺序表； 2.对已建立的顺序表实现插入、删除、查找等基本操作； 三.算法设计 1.建立顺序表并初始化 1)顺序表的大小为MaxSize，存入元素的下标为n a.如果n>MaxSize，则抛出参数非法； b.将元素a[i]赋值给线性表中元素序号为i的元素； 2.顺序表的插入 1）如果表满了，则抛出上溢异常； 2）如果元素插入的位置不合理，则抛出位置异常； 3）将最后一个元素及第i个元素分别向后移动一个位置； 4）将要插入的元素x填入为位置i处； 5）表长加1； 3.顺序表的删除 1）如果表空，则抛出下一异常；
2）如果删除的位置不合理，则抛出删除位置异常； 3）取出被删元素； 4）将下表为i至n-1的元素分别向前移动1个元素； 5）表长减一，返回被删元素值； 4.顺序表的查找 A.按位查找 1）如果查找的位置不合理，则抛出查找的不合理； 2）返回被查找的元素值； B.按值查找 1）若查找成功，返回被查找元素的序号； 2）若查找失败，则返回0； 四.部分代码 文件名称：SeqList.h #define SEQLIST_H const int MaxSize = 5; template
数据结构实验报告-顺序表的创建、遍历及有序合并操作二、实验内容与步骤 实现顺序表的创建、遍历及有序合并操作，基本数据结构定义如下： typedef int ElemType; #define MAXSIZE 100 #define FALSE 0 #define TRUE 1 typedef struct {ElemType data[MAXSIZE]; int length; }seqlist; 创建顺序表，遍历顺序表 #include
#define TRUE 1 typedef int ElemType; //用户自定义数据元素类型 // 顺序表结构体的定义 typedef struct { ElemType *elem; //顺序表的基地址 int length; //顺序表的当前长度 int listsize; //预设空间容量 }SqList; //线性表的顺序存储结构 SqList* InitList() //创建空的顺序表 { SqList* L = (SqList*)malloc(sizeof(SqList));//定义顺序表L if(!L) { printf("空间划分失败，程序退出\n"); return NULL; } L->elem=(ElemType *)malloc(MAXSIZE*sizeof(ElemType)); if(!L->elem) { printf("空间划分失败，程序退出\n");
#define OVERFLOW 0 #define List_size 100 #define Listincrement 10 #include
creat_Sq(&L); printf("\n"); print_Sq(&L); printf("\n"); ascend(&L,i); print_Sq(&L); printf("\n"); Insert(&L,e); print_Sq(&L); printf("\n"); } Sqlist creat_Sq(Sqlist*L)//创建顺序表 { ElemType *newbase; int i,n; L->elem=(ElemType*)malloc(List_size*sizeof(ElemType)); if(!L->elem) exit(OVERFLOW);//存储分配失败
printf("请输入元数个数：\n"); scanf("%d",&n); if(n>=List_size)//如果所需空间大于线性表的初始空间，则增加空间容量 { newbase=(ElemType*)malloc((List_size+Listincrement)*sizeof(E lemType)); L->elem=newbase; L->length=n; L->listsize=List_size+Listincrement; for(i=0;i
山东师范大学 实验报告 课程：数据结构班级：2016级通信2班实验序号： 1 姓名：韩明达 学号: 201611030230 实验日期：9.17 题目: 顺序表的建立和运算 一、实验目的和要求 （1）熟悉C语言的上机环境，进一步掌握C语言的结构特点。 （2）掌握线性表的顺序存储结构的定义及基本运算 二、实验环境 Windows10，Visual Studio 2017 三、实验内容及实施 实验内容 1、建立一个顺序表，输入n个元素并输出； 2、查找线性表中的最大元素并输出； 3、在线性表的第i个元素前插入一个正整数x； 4、删除线性表中的第j个元素； 5、将线性表中的元素按升序排列； 【程序流程图】
【程序】 #include
int i; for (i = 0; i < L.length; i++) { cout << L.data[i] << " "; } //依次输出顺序表 cout << endl; } void FindMax(SqList &L) //找最大值 { cout << "该组数据的最大值为：" << endl; int m = L.data[0]; int i; for (i = 0; i < L.length; i++) //依次比较两个数的大小，取大者赋给m { if (m < L.data[i]) { m = L.data[i]; } } cout << m << endl; //输出最大值 }
实验目的及要求： 了解和掌握顺序表的特点； 掌握顺序表基本操作的实现； 要求完成顺序表的初始化、插入、删除、显示操作的实现。实验设备环境及要求： PC机一台，内存要求128M以上，VC++6.0集成开发环境。实验内容与步骤： 1、在VC++6.0环境中新建一个工程和C++文件； 2、实现顺序表初始化、插入、删除算法，代码如下： #include
实验一顺序表的基本操作 一、实验目的 掌握线性表的顺序表基本操作：建立、插入、删除、查找、合并、打印等运算。 二、实验要求包含有头文件和main函数； 1.格式正确，语句采用缩进格式； 2.设计子函数实现题目要求的功能； 3.编译、连接通过，熟练使用命令键； 4.运行结果正确，输入输出有提示，格式美观。 三、实验设备、材料和工具 1.奔腾2计算机或以上机型 2.turboc2,win-tc 四、实验内容和步骤 1. 建立一个含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2. 往该顺序表中第i位置插入一个值为x的数据元素。 3. 从该顺序表中第j位置删除一个数据元素，由y返回。 4. 从该顺序表中查找一个值为e的数据元素，若找到则返回该数据元素的位置，否则返回“没有找到”。 五、程序 #include
typedef struct { int *elem; int length,listsize; }sqlist; //类型定义 void initlist_sq(sqlist &L) //初始化顺序表 { } void output(sqlist L) //输出顺序表 { } void insertlist(sqlist &L,int i, int x) //顺序表中插入x { } void deletelist(sqlist &L,int j, int y) //顺序表中删除y { } int locateelem(sqlist &L,int e) //顺序表中查找e { } void main() { } 【运行结果】 void initlist_sq(sqlist &L) //初始化顺序表 { L.elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); if(!L.elem) exit (OVERFLOW);
要求：编写一个程序（）实现顺序表的各种基本操作，并在此基础上设计一个主程序（）完成如下功能： （1）初始化顺序表L （2）依次采用尾插法插入a,b,c,d,e元素 （3）输出顺序表L （4）输出顺序表L的长度 （5）判断顺序表L是否为空 （6）输出顺序表L的第3个元素 （7）输出元素a的位置 （8）在第4个元素位置上插入f元素 （9）输出顺序表L （10）删除L的第3个元素 （11）输出顺序表L （12）释放顺序表L /*文件名:*/ #include <> #include <> #define MaxSize 50 typedef char ElemType; typedef struct { ElemType elem[MaxSize]; int length; } SqList; extern void InitList(SqList *&L); extern void DestroyList(SqList *L); extern int ListEmpty(SqList *L); extern int ListLength(SqList *L); extern void DispList(SqList *L); extern int GetElem(SqList *L,int i,ElemType &e); extern int LocateElem(SqList *L, ElemType e); extern int ListInsert(SqList *&L,int i,ElemType e); extern int ListDelete(SqList *&L,int i,ElemType &e); void main() { SqList *L; ElemType e; printf("(1)初始化顺序表L\n"); InitList(L); printf("(2)依次采用尾插法插入a,b,c,d,e元素\n"); ListInsert(L,1,'a'); ListInsert(L,2,'b'); ListInsert(L,3,'c'); ListInsert(L,4,'d');
//头文件 #include
#include 实验题目：顺序表的基本操作 一、实验目的 1、掌握线性表的顺序存储实现； 2、掌握在存储体（顺序表）上的基本操作（插入、删除）。 二、实验作业 在给出部分代码的基础上完成： 1.已知元素在顺序表上的插入位置（序号），编写程序完成在顺序表上的插 入功能，将编写好的函数在主函数的调用。 SeqList insertlocal(SeqList L,int i,int x) 2.已知顺序表中删除元素的位置（序号），请编写程序完成在顺序表上的删 除功能，将编写好的函数在主函数的调用。 SeqList deletelocal(SeqList L,int i) 3.创新加分题 两个顺序表L1,L2,它们的元素是整型、无序的，请编写一个函数完成将两个顺序表合并成一个有序的新顺序表。 SeqList hebing(SeqList L1, SeqList L2) 三、实验内容 1、SeqList insertlocal(SeqList L,int i,int x) ｛ int j; int f=0; if(i<=L.length-1) { f=1; for(j=L.length-1;j>=i;j--) L.data[j+1]=L.data[j]; L.data[i]=x; L.length++; } else; if(f==0) printf("sorry"); printf("\n"); return L; ｝ 2、SeqList deletelocal(SeqList L,int i) ｛ int j; int f=0; if(i<=L.length-1) { f=1; for(j=i+1;j<=L.length-1;j++) L.data[j-1]=L.data[j]; L.length--; } else; if(f==0) printf("sorry"); printf("\n"); return L; ｝ 3、SeqList hebing(SeqList L1, SeqList L2) ｛ SeqList L; int i,j,k,temp; for(i=0;i<=L1.length-1;i++) L.data[i]=L1.data[i]; for(j=0;j<=L2.length-1;j++,i++) L.data[i]=L2.data[j]; L.length=i; for(k=L.length-1;k>0;k--) { for(i=0,temp=L.data[i];i<=k;i++) { if(temp<=L.data[i]) { temp=L.data[i]; j=i; } } L.data[j]=L.data[k]; L.data[k]=temp; } return L; ｝ 实验日期： 2017 年 3 月 6 日 实验目的及要求 1. 熟练掌握线性表的基本操作在顺序存储上的实现； 2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3. 掌握线性表的顺序存储结构的定义和基本操作的实现； 4. 通过本实验加深对C语言的使用（特别是函数调用的参数传递、指针类型的应用）。实验内容 已知程序文件已给出学生身高信息顺序表的类型定义和基本运算函数定义。 （1）顺序表类型定义 typedef struct { int xh; /*学号*/ float sg; /*身高*/ int sex; /*性别，0为男生，1为女生*/ } datatype; typedef struct{ datatype data[MAX]; /*存放顺序表元素的数组*/ int last; /*表示data中实际存放元素个数*/ }Seqlist; （2）基本运算函数原型 void initList(Seqlist *lp);/*置一个空表*/ void createList(Seqlist *lp);/*建一个学生顺序表*/ void sort_xh(Seqlist *lp);/*按学号排序*/ void Error(char *s);/*自定义错误处理函数*/ void pntList(Seqlist *lp);/*输出学生表*/ void save(Seqlist *lp,char strname[]);/*保存学生顺序表到指定文件*/ 任务一 创建程序文件，其代码如下所示，理解顺序表类型Seqlist和基本运算函数后回答下列问题。 /*程序文件代码*/ #include <> #include <> #define MAX 50 typedef struct { int xh; /*学号*/ float sg; /*身高*/ int sex; /*性别，0为男生，1为女生*/ } datatype; typedef struct{ datatype data[MAX]; /*存放顺序表元素的数组*/ int last; /*表示data中实际存放元素个数*/ }Seqlist; void initList(Seqlist *lp);/*置一个空表*/ void createList(Seqlist *lp);/*建一个学生顺序表*/ void sort_xh(Seqlist *lp);/*按学号排序*/ void Error(char *s);/*自定义错误处理函数*/ void pntList(Seqlist *lp);/*输出学生表*/ void save(Seqlist *lp,char strname[]);/*保存学生顺序表到指定文件*/ /*置一个空表*/ void initList(Seqlist *lp) { lp->last=0; } /*建一个学生顺序表*/ void createList(Seqlist *lp) { FILE *fp; int xh ,sex; float sg; if((fp=fopen("","r"))==NULL) { Error("can not open file !"); } while(!feof(fp)) { fscanf(fp,"%d%f%d",&xh,&sg,&sex); lp->data[lp->last].xh=xh; lp->data[lp->last].sg=sg; lp->data[lp->last].sex=sex; lp->last++; } #include 实验一-顺序表操作实现 实验一顺序表操作实现 实验日期：2017 年 3 月 6 日 实验目的及要求 1. 熟练掌握线性表的基本操作在顺序存储上的实现； 2. 以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3. 掌握线性表的顺序存储结构的定义和基本操作的实现； 4. 通过本实验加深对C语言的使用（特别是函数调用的参数传递、指针类型的应用）。 实验内容 已知程序文件seqlist.cpp已给出学生身高信息顺序表的类型定义和基本运算函数定义。 （1）顺序表类型定义 typedef struct { int xh; /*学号*/ float sg; /*身高*/ int sex; /*性别，0为男生，1为女生*/ } datatype; typedef struct{ datatype data[MAX]; /*存放顺序表元素的数组*/ int last; /*表示data中实际存放元素个数*/ }Seqlist; （2）基本运算函数原型 void initList(Seqlist *lp);/*置一个空表*/ void createList(Seqlist *lp);/*建一个学生顺序表*/ void sort_xh(Seqlist *lp);/*按学号排序*/ void Error(char *s);/*自定义错误处理函数*/ void pntList(Seqlist *lp);/*输出学生表*/ void save(Seqlist *lp,char strname[]);/*保存学生顺序表到指定文件*/ 任务一 创建程序文件seqlist.cpp，其代码如下所示，理解顺序表类型Seqlist和基本运算函数后回答下列问题。 /*seqlist.cpp程序文件代码*/ #include 1、顺序表基本操作的实现 [问题描述] 在顺序表中查找值为x的元素的位置，在线性表的某个位置插入一个元素，删除线性表某个位置的元素。 [基本要求] 要求建立生成顺序表，可以键盘上读取元素，用顺序存储结构实现存储。 [实现提示] 要实现基本操作，可用实现的基本操作，也可设计简单的算法实现。[建议步骤] 1）建立顺序表的存储结构； 2）利用1）的存储结构建立有实际数据的数据表； 3）实现查找操作； 4）实现插入操作； 5）实现删除操作。 6）写出main函数测试上述操作。 实验源码： #include SqList L; //打印菜单 void menu() { printf("**************************************\n"); printf(" 顺序表操作的验证实验\n"); printf("**************************************\n"); printf(" 1、初始化表\n"); printf(" 2、创建表\n"); printf(" 3、按值查询\n"); printf(" 4、在指定位置插入一个元素\n"); printf(" 5、删除指定位置上的一个元素\n"); printf(" 6、输出表\n"); printf(" 0、退出\n"); printf("***************************************\n"); } //初始化表，置表长为0 void Init(SqList *L) { L->length=0; } 顺序表的定义及基本操作 一、实验目的、意义 （1）掌握线性表顺序存储结构的特点。 （2）熟练掌握顺序表的基本运算，理解用它们表示时插入与删除操作的算法。（3）加深对顺序存储数据结构的理解，逐步培养解决实际问题的编程能力 二、实验内容及要求 说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。 具体要求： 建立顺序表，完成顺序表的基本操作：初始化、插入、删除、输出（遍历）、销毁, 置空表、求表长、查找元素、判线性表是否为空等。（参见教材19页） 实验提示： （1）定义顺序表：SqList，完成顺序表的基本操作，生成头文件SqList.h。 参考运行界面： 三、实验所涉及的知识点 数据结构、C语言语法函数、指针、数组、循环语句等。 四、实验结果及分析 （所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。） 五、总结与体会 （调试程序的心得与体会，若实验课上未完成调试，要认真找出错误并分析原因等。） 调试程序时，出现了许多错误。如：头结点的建立出错、忽略了创建释放节点，另外还有一些语法上的错误。单单排查错误就用满了实验课的时间，课上未完成。后来经过查阅教材，浏览网页等方式，才完成试验。这次试验出现错误最重要的原因就是对课本知识点理解不深刻以及编写代码时的粗心。以后要都去练习、实践，完善自己的不足之处。 六、程序清单(包含注释) #include 实验1 顺序表的基本操作
实验一 顺序表操作实现
顺序表基本操作(C++版)
实验一-顺序表操作实现
顺序表基本操作的实现
顺序表的定义及基本操作
相关主题
文本预览