数据结构实验指导书:线性结构的插入和删除 关注我 发私信 下载此文档 正在努力加载中... 文档星级: 内容提示:掌握线性结构的定义、组织形式、结构特征和类型说明以及在这两...
合肥师范学院实验报告 姓名：李珍 院（系）：计算机学院 课程名称：数据结构 专业/年级：2013 级计算机科学与技术 实验一 ——线性结构 一、实验目的 1. 理解线性表的顺序存储结构； 2. 熟练掌握顺序表结构及其有关算法的设计； 3. 4. 5. 6. 理解线性表的链式存储结构； 熟练掌握动态链表结构及其有关算法的设计； 根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法； 深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们，同时巩固对这两种结构的构造方法的理解。 二、实验预习内容 请在上机前认真阅读教材及实验指导书，并在以下空白处填写相应的内容。 1. 请写出顺序表的结构体类型定义及 6 大基本运算。
定义：
#define maxlen 100 tyedef struct {elementtype int }seqlist;
1.初始化：
void initial_list(seqlist *L) {L->listlen=0;
} 2.求表长: int list_length(seqlist *L) { return L.listlen ;} data[maxlen];
listlen; 3.按序号求元素：
void get_element(seqlist L,int i,elementtype &
x) { if(i<1 || i>L.listlen) error(“超出范围”);
Else x=L.data[i-1];
} 4.查找：
int list_locate(seqlist elementtype x) { int i;
for (i=0;i<L.listlen;i++) if（L.data[i]==x）return (i+1);
return(0);
} 5.插入：
void list_insert(seqlist *L,element x,int i) {int j;
if (L->listlen==maxlen) error(“overflow”);
else if(i<1|| i>L->listlen+1) error(“position error”);
else {for(j=L->listlen-1;j>=i-1;j--) L->data[j+1]=L->data[j];
L->data[i-1]=x;
L->listlen++;
} } 2. 请写出单链表结点的结构体类型定义及 6 大基本运算。
定义：
tyedef struct {elementtype data;
Struct node *next;
}node;
1.初始化：
Void initial_list(node * &L) { L=(node *)malloc(sizeof(node));
L->next=null;
} 2.求链表长：
int list_length(node *L) { int n=0;node *p=L->next;
while(P!=null) { n++ ;
P=P->next;
} Return n;
} 3.按序号取元素：
node * get_element(node *,int i) { node * P=L->next;int j=1;
while(j!=i&&P!=NULL) { P=P->next;j++;
} return P;
} 4.查找：
node * list_locate(node *, elementtype { node * P=L->next;
while(P!=NULL&&P->data!=x) P=P->next;
return P;
} x) 5.插入：
void list_insert(node *L,int i,element x) { node *P=L;int k=0;node *s;
while(k!=i-1&&P!=NULL) { P=P->next;k++;} if(P==NULL) error(“序号错”)； else { S=new node;
S->data=x;
S->next=P->next;P->next=S;
} } 6.删除：
void list_delete(node*L,int i) {node *u,*P=L;int k=0;
while(k!=i-1&&P!=NULL) {P=P->next;k++} if(P==NULL||P->next=NULL) error(“删除序号出错”);
else{ u=P->next;
P->next=u->next;
delete u;
} } 3. 请写出顺序栈的结构体类型定义及 6 大基本运算。
定义：
typpedef struct {elementtype data[maxsize];
int top;
}seqstack 1.初始化：
Void init_stack(seqstack * &s) { s->top=-1;} 2.判断 s 是否为空：
BOOL stack_empty(seqstack s) {if (s.top==-1) return TURE;else return FALSE;} 3.取栈顶元素：
void stack_top(seqstack *s,elementtype &x) {if (stack_empty(*s))error (“栈为空”)； else x=s->data[s->top];
} 4.入栈：
void push_stack(seqstack *s,elementtype x) { if(s->top==maxsize-1)error(“溢出”);
else s->data[++s->top]=x;
} 5.出栈：
void pop_stack(seqstack *s,elementtype x) { if(stack_empty(*s))error(“栈空，不能删除”);
else x=s->data[s->top--];
} 6.判断是否栈满：
BOOL stack_full(seqstack s) {if(s.top==maxsize-1)return TURE;else return FALSE;
4. 请写出链队列的结构体类型定义及 5 大基本运算。
定义：typedef struct{ node *front,*rear;
}linkqueue; } 1.初始化：
void init_queue(linkqueue *&Q) {Q->front=new node;
Q->rear=Q->front;
Q->front->next=NULL;
} 2.判断队列是否为空：
BOOL queue_empty(linkqueue Q) {reutrn Q.front==Q.rear;} 3.取队头元素：
void queue_front(linkqueue *Q,elementtype &x) {if(queque_empty(*Q)error(“队空，不能取元素”)) else x=Q->front->next->data;
} 4.入队：
void En_queue(linkqueue *Q,elementtype &x) { node *p;
P=(node *)malloc(sizeof(node));
P->data=x;
P->next=NULL;
Q->rear->next=P;
Q->rear=P;
} 5.出队：
void Out_queue(linkqueue *Q,elementtype &
x) { node *u; if(queue_empty(*Q)error(“下溢出，不能出列”))； else{x=Q->front->next->data;
u=Q->front->next;
Q->front->next=u->next;
delete u;
If(Q->front->next==NULL) Q->rear=Q->front;
} } 三、上机实验 1. 实验内容。
1） 以顺序表作存储结构，实现线性表的插入、删除； 2） 以单链表作存储结构，实现有序表的合并； 3） 利用栈（以顺序栈作存储结构）实现进制转换，并用队列（以链队列作存储结构）计算并打印杨辉三角。
2. 实验源程序。
1) #include <stdio.h>
#include <malloc.h>
#define maxlen 100 typedef struct {int data[maxlen];
int listlen;
}seqlist;
void initlist (seqlist *&L) { L =(seqlist *)malloc (sizeof(seqlist)); L->listlen=0;
} void insert (seqlist *L,int x) { int i =L ->
listlen - 1;
if (i>=maxlen -1) printf ("error overflow.");
else { while (i>=0 &&
L ->
data [i]>x) { L->
data[i+1]=L ->data [i];
i--;
} L->data[i+1]=x;
L->listlen++;
} } void list_delete(seqlist *L, int i) { int j;
if (L->listlen<=0 || i <= 0) printf("下溢出错");
if (i >
L->listlen || i <= 0) printf("删除位置错");
else { for (j = i;
j <= L->listlen - 1;
j++) L->data[j - 1] = L->data[j];
L->listlen--;
} } void displist (seqlist *L) { int i;
if (L->listlen==0) return ;
for (i=0;i<L->listlen;i++) printf ("%d",L->data[i]);
printf ("\n");
} int main () { int n;
seqlist *L;
initlist (L);
insert (L,1);
insert (L,2);
insert (L,3);
printf("输出顺序列表 L：");
displist(L);
printf("删除 L 的第 n 个元素\n");
scanf("%d",&n);
list_delete(L,n);
displist (L);
return 0;
} （2）#include <stdio.h>
#include <malloc.h>
typedef struct node { int data;
struct node *next;
}LinkList;
void nitial_list(node* &L)//定义链表 { L=(node*)malloc(sizeof(node));
L->next=NULL;
} int list_length(node *L)//求表长 { int n=0;node *p=L->next;
while(p!=NULL) { n++;p=p->next;
} return n;
} void list_insert(node *L,int i,int x)//插入 { node *P=L;int k=0;node *S;
while(k!=i - 1&&P!=NULL) { P=P->next;k++;
} if(P==NULL) printf ("error");
else { S = (node*)malloc(sizeof(int));
S->data=x;
S->next=P->next;
P->next=S;
} } void Displist (node *L) { node *p=L->next;
while(p!=NULL) { printf ("%d",p->data);
p=p->next;
} printf ("\n");
} void Union(LinkList *ha,LinkList *hb,LinkList *&hc) { LinkList *pa=ha->next,*pb=hb->next,*s,*tc;
hc= (node*)malloc(sizeof(node));
tc=hc;
while (pa!=NULL&&pb!=NULL) { if (pa->data<pb->data) { s=(node*)malloc(sizeof(node));
s->data =pa->data;
tc->next =s;
tc=s;
pa=pa->next;
} else if (pa->data>pb->data) { s=(node*)malloc(sizeof(node));
s->data =pb->data;
tc->next =s;
tc=s;
pb=pb->next;
} else { s=(node*)malloc(sizeof(node));
s->data =pa->data;
tc->next =s;
tc=s;
pa=pa->next;
pb=pb->next;
} } if (pb!=NULL) pa=pb;
while (pa!=NULL) { s=(node*)malloc(sizeof(node));
s->data =pa->data;
tc->next =s;
tc=s;
pa=pa->next;
} tc->next=NULL;
} int main () { node *ha,*hb,*hc;
nitial_list(ha);
nitial_list(hb);
nitial_list(hc);
list_insert(ha,1,2);
list_insert(ha,2,4);
list_insert(ha,3,6);
list_insert(ha,4,8);
list_insert(ha,5,11);
list_insert(hb,1,3);
list_insert(hb,2,7);
list_insert(hb,3,9);
Union (ha,hb,hc);
printf("第一个有序表："); Displist (ha);
printf("第二个有序表：");
Displist (hb);
printf("合并后的有序表：");
Displist (hc);
return 0;
} （3） 1）# include <stdio.h>
# include <malloc.h>
# define maxsize 100 typedef struct { int data[maxsize];
int top;
}seqstack;
void init_stack(seqstack* &s) //初始化 { s->top=-1;} /*void stack_full(seqstack* s)//判断栈满 {if(s->top==maxsize-1) printf("栈满\n");}*/ void push_stack(seqstack *s,int x) //进栈 { if(s->top==maxsize-1) { printf("栈满\n");} else s->data[++s->top]=x;
} void pop_stack(seqstack *s,int &x)//出栈 { if(s->top==-1) printf("栈空\n");
else { x=s->data[s->top];
s->top--;} } void change(int n)//转换进制,n 为要转换的进制 { int i,j=0,x,y,mod;
seqstack *s;
s=(seqstack*)malloc(sizeof(seqstack));
init_stack(s);
printf("请输入你需要转换的数: ");
scanf("%d",&x);
getchar();
while(x!=0) { mod=x%n;
push_stack(s,mod);
x=x/n; j++;
} printf("以下是转换后的结果:\n");
for(i=0;i<j;i++) {pop_stack(s,y);
printf("%d",y);} printf("\n\n");
} void main() { int n;
//seqstack *s;
//init_stack(s);//初始化 //push_stack(s);//进栈 printf("你需要进行多少进制转换: ");
scanf("%d",&n);
//getchar();
change(n);
} 2） #include<stdio.h>
#include<malloc.h>
#define l sizeof(struct node) #define m sizeof(struct linkqueue) typedef struct node {int data; struct node *next;
}node;
typedef struct linkqueue {node*front,*rear;
}linkqueue;
void init_queue(linkqueue*Q) //初始化链队列 {node*p;
p=(node*)malloc(l);
Q->front=Q->rear=p;
Q->rear->next=NULL;
} void en_queue(linkqueue*Q,int x) //入队 {node*p;
p=(node*)malloc(l);
p->data=x;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
} int out_queue(linkqueue*Q) //出队 { int x;
node*u;
if(Q->front==Q->rear) printf("NULL"); else { x=Q->front->next->data;
u=Q->front->next;
Q->front->next=u->next;
free(u);
if(Q->front->next==NULL) {Q->rear=Q->front;} return x;
}} void yhsj(int n) //输出杨辉三角 {int i,j,a,b;
linkqueue*Q;
Q=(struct linkqueue*)malloc(m);
if(n<=0) printf("error\n");
else {init_queue(Q);
for(i=1;i<n;i++) {printf("
");
//第一行 1 前的空格 } printf("
1\n");
en_queue(Q,1);
for(i=2;i<=n;i++) {for(j=1;j<n-i+1;j++) {printf("
");} a=0;
for(j=1;j<i;j++) {b=out_queue(Q);
printf("%3d ",a+b);
en_queue(Q,a+b);
a=b;
} printf("
1\n");
en_queue(Q,1);
}}} void main() {int n;
printf("您想输出杨辉三角的行数为：\n");
scanf("%d",&n);
yhsj(n);
} 3. (1) 实验结果。 . (2) (3) 1) 2) 四、实验总结（实验过程中出现的问题、解决方法、结果或其它） 在这次实验中，我学到很多东西，加强了我的动手能力，并且培养了我的独立思考能力。我们坚持理论联系实际的思想， 以实践证实理论，从实践中加深对理论知识的理解和掌握。实验是我们快速认识和掌握理论知识的一条重要途径。通过这次课 程设计，我们对 C 语言以及数据结构有了更深刻的了解，增强了程序的编写能力，巩固了专业知识，对程序的模块化观念也 又模糊逐渐变的清晰了。
在程序的运行与调试过程中出现了很多错误， 通过反复地复习课本上的相关知识， 不停地修改与调试， 我们终于完成了这段程序。在调试过程中，我们认识到了数据结构的灵活性与严谨性，同一个功能可以由不同的语句来实现， 但编写程序时要特别注意细节方面的问题， 因为一个小小的疏忽就能导致整个程序不能运行。
我们也认识到了自己的薄弱之处， 如对链表相关知识的欠缺，文件运用的不熟练，在以后的学习中我们要集中精力、端正态度，争取把知识学得更扎实、更全面。
第 1 页 共 2 页 数据结构实验报告 课程名称:数据结构(c++语言描述) 实验编号 及实验名称 实验二:线性结构的链式存储 系 别 计科系 姓 名 学 号 班 级 实验地点 实验日期 实验时...
数据结构线性表实验报告 隐藏>> 《 数据结构 》实验报告 数据结构 》 院系 应用科技学院 专业 电子信息工程 姓名 陈高雪 学号 120352010054 10 级 电信 班2011 年... 沈阳工程学院 ...
实验 室 实验 内容 实习单元 2 线性表 一二 实验 题目抽象数据类型 List[1] 的顺序存储结构 ... 二、 实验 内容 1. 建立含有若干个... 实验报告 线性表的顺序存储 试验项目名称 线性表的...