线性表的建立与遍历

线性表的建立与遍历

计算机软件辅助设计

实验报告

实验名称： 线性表的建立与遍历 实验地点： 信息学院机房 实验类别：□设计型 ■验证型 □综合型 班级：电子08-1班 学号： 姓名： 成绩： 指导教师： 谢秀兰 实验时间： 2011年12月

线性表的建立与遍历

实验一 线性表的建立与遍历

一、实验目的

进一步理解线性表的逻辑结构和存储结构，掌握线性表的建立与遍历算法 二、实验题目

线性表的建立与遍历 三、实验类型

验证性 四、实验内容

1、给定一个输入序列，建立顺序表，访问输出顺序表中各结点的内容。 2、给定一个输入序列，建立线性链表，访问输出线性链表中各结点的内容。 五、实验要求

根据实验内容，用C语言编程实现，上机调试运行得出实验结果，写出实验报告。 六、实验提示

1、线性结构中的所有结点按它们之间的关系可以排成一个线性序列： k1，k2， ，kn

其中k1是开始结点，kn是终端结点，ki是ki+1的前驱结点，而ki+1是ki的后继结点(i=1，2， ，n-1)。通常把上述线性序列称为“线性表”，把线性结构中的结点称为元素或“表目”。将一个线性表存放到计算机中，可以采用不同的方法，其中最简单而自然的就是顺序的方法，即把表目按其索引值从小到大一个接一个地存放在相邻的单元里。顺序方法存储的线性表简称“顺序表”，顺序表是一种紧凑结构。

2、常用的链表有单链表和双链表。在单链表中分配给每个结点的存储单元可分为两个部分：一部分存放结点的数据，称为data域，另一部分存放指向结点后续结点的指针，称为next域，终端结点没有后继结点，其next域为NULL，在计算机中可以表示成零或负数，另外还需要一个表头变量head指向链表的第一个结点。

七、实验程序及结果 /*顺序表操作*/

#include<stdio.h> #define init_size 30 //初始存储空间分配大小

线性表的建立与遍历

为全局变量 static int list_size; void create_sqlist() {//建立一个顺序表 int i;

p_list=(elem_type*) malloc

(init_size*sizeof(elem_type)); if(p_list==NULL)

printf("存储空间分配失败！"); else {

elem_type *p_temp=p_list;//空间基址备份

for(i=0;i<init_size;i++)//先清空上面分

配的空间 ，然后建表 { *p_list=NULL; p_list++; }

p_list=p_temp;//空间基址还原

printf("请键入您想要建立的线性表大小：");

scanf("%d",&list_size); if(list_size<1||list_size>init_size) printf("对不起，您所要建立的表大小不合法或已超出分配的空间大小！"); else {

printf(" 请输入您的 %d 个数值：\n",list_size);

for(i=1;i<=list_size;i++) scanf("%d",p_list++);//输入格式要根据elem_type变化 }

printf("您已成功输入以下数值：\n"); p_list=p_temp;//空间基址还原 for(i=1;i<=list_size;i++)

{

printf("%d ",*p_list++); }

p_list=p_temp;//空间基址还原 } } }

void find_sqlist()

{//在已建好的线性表中查找一个数值 int temp,i,flag=0;

elem_type *p_temp=p_list;//空间基址备份 printf("\n请输入您要查找的数值："); scanf("%d",&temp); for(i=1;i<=list_size;i++) {

if(*p_list==temp) {

printf("\n 找到了！它是表中第%d 号元素；",i); flag++; } p_list++; }

printf("\n搜索完毕！共找到%d个元素。

线性表的建立与遍历

p_list=p_temp;//空间基址还原 }

void delete_sqlist()

{//在已建好的线性表中删除一个数值 int i;

elem_type *p_temp=p_list;//空间基址备份 printf("\n 您想删除表中第几个元素？请键入位序号："); scanf("%d",&i); if(i<1||i>list_size)

printf("\n错误！删除位置已超出线性表范围。"); else {

if(i==list_size) {

p_list+=list_size-1; *p_list=NULL; p_list=p_temp; } else {

int *q=p_list+i-1;

for(q;q<p_list+list_size;q++) {

*q=*(q+1); } } list_size--;

printf("删除后的新表为：\n");

运用前提是事先分配的空间在建表之前已被清空 p_list=p_temp; } }

void insert_sqlist()

{//在已建好的线性表中插入一个数值 int i,value,j,*q;

elem_type *p_temp=p_list;//空间基址备份 if(list_size==init_size) printf("\n对不起，此表已占满分配的存储空间，无法插入。"); else {

printf("\n您将在表中第几个元素之前(包括末尾)插入？请键入位序号："); scanf("%d",&i); if(i<1||i>(list_size+1))

printf("\n 错误！插入位置已超出线性表范围。"); else {

if(i==(list_size+1)) {

printf("请输入您要插入的数值："); scanf("%d",&value); p_list+=list_size; *p_list=value; p_list=p_temp; } else

线性表的建立与遍历

printf("请输入您要插入的数值："); scanf("%d",&value); q=p_list;

for(q+=list_size;q>=p_list+i;q--) {

*q=*(q-1); }

*q=value; } list_size++;

printf("插入后的新表为：\n"); /* for(j=1;j<=list_size;j++) {

printf("%d ",*p_list++); }//方法（一）*/

while(*p_list) printf("%d ",*p_list++);//此方法运用前提是事先分配的空间在建表之前已被清空 p_list=p_temp; }

实验结果如下图所示：

} } int main() {

int xuan,yn; create_sqlist();

sf: printf("\n 接下来，请选择下面一种操作的标号：");

printf("\n1.查询；2.删除；3.插入；4.退出.\n"); scanf("%d",&xuan); if(xuan==1) find_sqlist(); if(xuan==2) delete_sqlist(); if(xuan==3) insert_sqlist();

printf("\n是否确定进行新的操作？按 1 确定，按 0结束:\n"); scanf("%d",&yn); if(yn==1) goto sf; }

线性表的建立与遍历

/*链表操作*/

#include<stdio.h> #define elem_type int typedef struct linknode {

elem_type data; struct linknode *next; }node;

static node *head; node *p,*s; int x,cycle=1;

printf("现在要建立线性链表，请依次键入数值并用空格隔开，以 0为结束符：\n");

head=(node*)malloc(sizeof(node));//建立头结点并由head指向

p=head; while(cycle)

线性表的建立与遍历

if(x!=0) {

s=(node *)malloc(sizeof(node)); s->data=x; p->next=s; p=s; }

else cycle=0; }

head=head->next;//删除头结点 p->next=NULL;//最后一个结点的指针域为空

printf("OK!您已成功建立如下线性链表：\n p=head");

while(p!=NULL) {

printf("%d ",p->data); p=p->next; } }

int length(node *head) {

int n=0; node *p; p=head;

while(p!=NULL) {

n++;

p=p->next; }

printf("\n该链表的长度为：%d",n); return n; }

void find() {

int i=1,x; node *p; p=head;

printf("\n请输入您要查找的数值："); scanf("%d",&x);

while(p!=NULL&&p->data!=x) {

i++;

p=p->next; }

素！",i);

else

printf("\n未找到！"); }

void insert() {

int i,x,j; node *p,*s;

printf("\n 您要在第几号元素之后插入新结点？请键入：");

scanf("%d",&i);

printf("\n请输入您要新建结点的数值：");

scanf("%d",&x);

s=(node *)malloc(sizeof(node));//建立一个待插入的新结点

s->data=x; if(i==0) {

s->next=head; head=s;

printf("OK!您已成功插入，新的线性链表为：\n");

p=head;

while(p!=NULL) {

printf("%d ",p->data); p=p->next; } } else {

p=head; j=1;

while(p!=NULL&&j<i) {

j++;

p=p->next; }

if(p!=NULL) {

s->next=p->next; p->next=s;

printf("OK!您已成功插入，新的线

线性表的建立与遍历

while(p!=NULL) {

printf("%d ",p->data); p=p->next; } }

else printf("\n未找到插入点！"); } }

void delet() {

int x,i=2,num=0; node *p,*q;

printf("\n请输入您要删除的数值："); scanf("%d",&x);

if(head==NULL)printf("该链表为空，不能删除！");

else {

if(head->data==x) {

p=head;

head=head->next; free(p);

printf("找到了！该数值等于头结点数值;\n");

num++; }

q=head;p=head->next; while(p!=NULL) {

if(p->data==x&&p->next!=NULL) {

num++;

q->next=p->next; free(p); p=q->next;

printf("找到了！该数值等于第%d个结点数值;\n",i+num-1);

}

if(p->data==x&&p->next==NULL) {

num++;

q->next=NULL; free(p);

printf("找到了！该数值等于第%d个结点数值;\n",i+num-1);

goto dt1; }

q=q->next;p=p->next;i++; }

dt1: if(num==0) printf("\n未找到要删除的数值！");

else {

printf("共删除%d 个结点，删除后的表为：\n",num);

p=head;

while(p!=NULL) {

printf("%d ",p->data); p=p->next; } } } }

void main() {

int xuan,yn; create();

sf: printf("\n接下来，请选择下面一种操作的标号：");

printf("\n1.查询；2.删除；3.插入；4.求长度；5.退出.\n");

scanf("%d",&xuan); if(xuan==1) find(); if(xuan==2) delet(); if(xuan==3) insert();

if(xuan==4) length(head);

printf("\n是否确定进行新的操作？按1 确定，按 0 结束:\n");

scanf("%d",&yn); if(yn==1) goto sf; }

线性表的建立与遍历

线性表的建立与遍历

报告

1、写出每个算法的思想。 2、画出算法流程图。

3、调试程序出现的问题及解决的方法。 4、打印实验报告及程序清单。

5、报告给出测试的结果并写出实验体会。 6、报告按信息学院统一格式书写。

本文来源：https://www.bwwdw.com/article/1k3m.html