数据结构顺序表与单链表的建立.docx
- 文档编号:17916798
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:16
- 大小:55.66KB
数据结构顺序表与单链表的建立.docx
《数据结构顺序表与单链表的建立.docx》由会员分享,可在线阅读,更多相关《数据结构顺序表与单链表的建立.docx(16页珍藏版)》请在冰点文库上搜索。
数据结构顺序表与单链表的建立
封面:
安徽大学
网络工程
数据结构顺序表与单链表的建立
——2012/4/7
一实验目的
1.熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。
2.以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点。
3.通过本章实验加深对c语言的使用(特别是函数的参数调用、指针类型的应用
和链表的建立等各种基本操作)。
二实验内容
1.顺序表的基本操作的实现.包括:
(1).顺序表的类型定义;
(2).创建一个元素为1,10,9,5的顺序表;
(3).向
(2)中表的指定位置插入一个元素;
(4).删除(3)中顺序表中指定位置的元素;
(5).依次输出
(2)~(4)顺序表中的元素.
2.链表的基本操作的实现.包括:
(1).链表的类型定义;
(2).创建一个元素为5,-4,9,10,3的链表;
(3).向
(2)表中指定位置插入一个元素;
(4).删除(3)表中指定位置的元素;
(5).依次输出
(2)~(4)表中的元素.
三、实验步骤
1.本实验用到的数据结构
(1)逻辑结构:
线性结构
(2)存储结构;顺序存储结构,链式存储结构
2.各程序的功能和算法设计思想
程序一//数据结构实验.cpp:
定义控制台应用程序的入口点。
//
#include"stdafx.h"
#include
#include
#include
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineLISTINITSIZE100
#defineLISTINCREMENT10
typedefintstatus;
typedefstruct{
int*elem;
intlength;
intlistsize;
}sqlist;
voidInitlist(sqlist*l)
{
(*l).elem=(int*)malloc(LISTINITSIZE*sizeof(int));
if(!
(*l).elem)
exit(OVERFLOW);
(*l).length=0;
(*l).listsize=LISTINITSIZE;
}
statusListInsert(sqlist*l,inti,inth)
{
int*newbase,*q,*p;
if(i<1||i>(*l).length+1)
{
printf("插入位置不合法!
\n");
returnERROR;
}
if((*l).length>=(*l).listsize)
{
newbase=(int*)realloc((*l).elem,((*l).listsize+LISTINCREMENT)*sizeof(int));
if(!
newbase)
exit(OVERFLOW);
(*l).elem=newbase;
(*l).listsize+=LISTINCREMENT;
}
q=(*l).elem+i-1;
for(p=(*l).elem+(*l).length-1;p>=q;--p)
{
*(p+1)=*p;
}
*q=h;
++(*l).length;
returnOK;
}
statusGetelem(sqlistl,inti,int*e)
{
if(i<1||(i>l.length))
{
printf("输入位置不合法!
\n");
returnERROR;
}
*e=*(l.elem+i-1);
printf("第%d个元素的值是:
%d\n",i,*e);
printf("\n");
returnOK;
}
statusListDelete(sqlist*l,inti)
{
int*p,*q;
if(i<1||i>((*l).length))
{
printf("删除元素位置不合法!
\n");
returnERROR;
}
p=(*l).elem+i-1;
printf("删除第%d个元素%d\n",i,*p);
q=(*l).elem+(*l).length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
(*l).length--;
returnOK;
}
voidListTraverse(sqlistl)
{
int*p;
inti;
p=l.elem;
for(i=1;i<=l.length;i++)
printf("%d\n",*p++);
printf("\n");
}
voidmain()
{
intn,i,j,k,e,h,m=1;
sqlistla;
Initlist(&la);
printf("请输入顺序表的长度n\n");
scanf("%d",&n);
printf("请输入%d个数据\n",n);
for(j=1;j<=n;j++)
{
scanf("%d",&e);
ListInsert(&la,j,e);
}
printf("输出各元素\n");
printf("la=");
ListTraverse(la);
fflush(stdin);
printf("\n");
printf("请依次输入插入元素的位置i,插入元素的值h\n");
scanf("%d",&i);
scanf("%d",&h);
printf("在第%d个元素前面插入元素%d\n",i,h);
ListInsert(&la,i,h);
printf("输出各元素\n");
printf("la=");
ListTraverse(la);
fflush(stdin);
printf("\n");
while(m)
{
printf("请输入查找元素的位置k\n");
scanf("%d",&k);
if(Getelem(la,k,&e))
m=0;
fflush(stdin);
}
printf("请输入删除元素的位置\n");
scanf("j=%d",&j);
printf("删除的第%d各元素是\n",j);
ListDelete(&la,j);
printf("la=");
ListTraverse(la);
printf("\n");
}
功能:
建立一个线性顺序结构,能够实现初始化顺序表,查找元素,插入元素,删除元素和输出顺序表等。
算法设计思想:
单独建立具有初始化,插入,删除,查找,输出功能的函数,其后按照合理的顺序构建一个主函数。
调试情况如下:
输入/输出要求
输入数据:
数据类型:
有符号整型((signed)int)
值域范围:
-32768~32767
程序二//shuju2.cpp:
定义控制台应用程序的入口点。
//
//shuju2.cpp:
定义控制台应用程序的入口点。
//
#include"stdafx.h"
#include
#include
#include
#defineOK1
#defineERROR0
typedefintstatus;
typedefstructLNode{
intdata;
structLNode*next;
}Lnode,*Linklist;
voidCreatelist(Linklist*l,intn){
inti;
Linklistp;
*l=(Linklist)malloc(sizeof(Lnode));
(*l)->next=NULL;
printf("请输入%d个元素\n",n);
for(i=n;i>0;--i){
p=(Linklist)malloc(sizeof(Lnode));
scanf("%d",&(p->data));
p->next=(*l)->next;
(*l)->next=p;
}
}
statusGetelem(Linklist*l,inti,int*e){
intj=1;
Linklistp;
p=(*l)->next;
while(p&&j
p=p->next;
++j;
}
if(!
p||j>i){
printf("第%d个元素不存在\n",i);
returnERROR;
}
*e=p->data;
printf("第%d个元素是%d\n",i,*e);
returnOK;
}
statusListinsert(Linklistl,inti,inte){
intj=0;
Linklistp,s;
p=l;
while(p&&j p=p->next; ++j; } if(! p||j>i-1) { printf("插入位置不合法\n"); returnERROR; } s=(Linklist)malloc(sizeof(Lnode)); s->data=e; s->next=p->next; p->next=s; returnOK; } statusListDelete(Linklistl,inti){ intj=0,h; Linklistp,q; p=l; while(p->next&&j { p=p->next; ++j; } if(! (p->next)||j>i-1) { printf("删除位置不合法\n"); returnERROR; } q=p->next; p->next=q->next; h=q->data; printf("删除的元素是%d",h); free(q); returnOK; } voidListTraverse(Linklistl){ Linklistp; p=l->next; while(p){ printf("%d",p->data); p=p->next; } } voidmain(){ inti,j,n,k,e,m=1; Linklistla; printf("请输入单链表的长度\n"); scanf("%d",&n); printf("逆位序建表\n"); Createlist(&la,n); printf("输出各元素\n"); printf("la="); ListTraverse(la); fflush(stdin); printf("\n"); while(m){ printf("请输入查找元素的位置k\n"); scanf("%d",&k); if(Getelem(&la,k,&e)) m=0; fflush(stdin); printf("\n"); } m=1; while(m){ printf("请输入要插入元素的位置i及数值e\n"); scanf("%d",&i); scanf("%d",&e); if(Listinsert(la,i,e)) m=0; printf("输出各元素\n"); printf("la="); ListTraverse(la); fflush(stdin); printf("\n"); } m=1; while(m){ printf("请输入删除元素的位置j\n"); scanf("%d",&j); if(ListDelete(la,j)) m=0; printf("输出各元素\n"); printf("la="); ListTraverse(la); printf("\n"); } } 功能: 建立一个单链表,能够实现初始化单链表,查询,删除,插入以及输出个功能。 算法设计思想: 利用逆序的方法构建一个Createlist子函数,再分别建立具有插入,查询,删除,输出功能的子函数,最后建立一个main函数按一定顺序调用各个子函数,实现程序设计。 调试情况如下: 输入/输出要求 输出数据: 数据类型: 有符号整型((signed)int) 值域范围: -32768~32767 实验总结: (1)实验时碰到过函数指针调用错误,以及结构体类数据调用错误,如将(*L)的形式写成L。 缺乏部分数据类型定义也常遇等…… (2)通过本次实验,加深了对函数指针调用和结构体内部成员调用的认识,进一步熟悉了构建顺序表,单链表和删除,查询,插入元素等方法。 (3)实验前应该编号基本的程序,尽量熟悉。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 顺序 单链表 建立