数据结构与算法实验报告-线性表.doc

沈 阳 工 程 学 院学 生 实 验 报 告（课程名称： 数据结构与算法 ）实验题目： 线性表 班 级 软本111 学 号 2011417104 姓 名 吴月芬 地 点 F座606 指导教师 姜柳 祝世东 实 验 日 期 : 2012年9月27日 一、实验目的1 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2 掌握线性表的顺序存储结构的定义及其C语言的实现。3 掌握线性表的链式存储结构单链表的定义及其C语言的实现。4 掌握线性表的基本操作二、实验环境Turbo C或是Visual C+三、实验内容与要求实验1 顺序表的操作请编制C程序，利用顺序存储方式来实现下列功能：根据键盘输入数据建立一个线性表，并输出该线性表；然后根据屏幕菜单的选择，可以进行表的创建，数据的插入删除并在插入和删除数据后再输出线性表；最后在屏幕菜单中选择0，即可结束程序的运行。分析：当我们要在顺序表的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素一次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。当要删除第i个元素时，也只需将第i个元素之后的所有元素前移一个位置。算法描述：对每个算法，都要写出算法的中文描述。本实验中要求分别写出在第i个（从1开始计数）结点前插入数据为x的结点、删除指定结点、创建一个线性表。打印线性表等的算法描述。实验2 单链表的操作请编制C程序，利用链式存储方式来实现线性表的创建、插入、删除和查找等操作。具体地说，就是要根据键盘输入的数据建立一个单链表；然后根据屏幕菜单的选择，可以进行数据的插入或删除，并在插入或删除数据后，再输出单链表；最后在屏幕菜单中选择0，即可结束程序的运行。算法描述：本实验要求分别写出在单链表中第i（从1开始计数）个位置之后插入元素、创建单链表、在单链表中删除第i个位置的元素、顺序输出单链表的内容等的算法描述。四、实验过程及结果分析（一）、顺序表的顺序表示与实现1.其源代码如下：#include#include#include /清屏#define NULL 0#define LIST_SIZE 10int length=0,listsize=0;struct sqlistchar dateLIST_SIZE;void displayMenu()printf( 欢 迎 使 用 顺 序 表 系 统);printf(n -);printf(n |=菜单=|n);printf(n |HHHH HH HH HH HH HHH HHHH|); printf(n |HHHH HH HH HH HH HHH HHHH|);printf(n|HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n|HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHH 1 : HHHHHHHHHHHHH|);printf(n |HHHHHHHHHH 建立链表 HHHHHHHHHHHHH|);printf(n |HHHHHHHHHH HHHHHHHHHHHHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHHH 2 : HHHHHHHHHHHH|);printf(n |HHHHHHHHHHH 插入信息 HHHHHHHHHHHH|);printf(n |HHHHHHHHHHH HHHHHHHHHHHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHHH 3 : HHHHHHHHHHHH|);printf(n |HHHHHHHHHHH 删除信息 HHHHHHHHHHHH|);printf(n |HHHHHHHHHHH HHHHHHHHHHHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHHH 4 : HHHHHHHHHHHH|);printf(n |HHHHHHHHHHH 输出所有信息 HHHHHHHHHHHH|);printf(n |HHHHHHHHHHH HHHHHHHHHHHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHHH 0 :退出系统 HHHHHHHHHHHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(nChoice:);struct sqlist * creatlist(void)struct sqlist * head;struct sqlist *p1;int i=0;head=p1=(struct sqlist * ) malloc( sizeof(struct sqlist);while (1)printf(请输入信息：n);scanf(%d,&p1-datei);if(p1-datei=0)break;elsep1+;i+;printf(结束请按“0”n);p1-datei=NULL;system(cls);return(head);struct sqlist * inserlist(struct sqlist * head)struct sqlist *p,*p1,*p2;int n,i,w=1,j;printf(请输入插入数据：);scanf(%d,&n);p=head;for(j=0;p-datej!=NULL;j+,p+)p+;p-datej+1=NULL;i=j;p1=head+i;p2=head+i-1;if(n(p2-datei-1)p1-datei=n;elsewhile(1)p1-datei=p2-datei-1;i-;p2-;p1-;if(p2-datei-1datei-1=n)p1-datei=n;break;while(w=1)printf(n返回主菜单：n);printf(请按“0”：);scanf(%d,&w);system(cls);return(head);struct sqlist * detelist(struct sqlist * head)struct sqlist *p1,*p2;int i=0,w=1,n,m=0;p1=p2=head;printf(请输入要删除的数据：);scanf(%d,&n);for(;p1-datei!=NULL;p1+,p2+,i+)if(p1-datei=n)for(;p2-datei!=NULL;i+,p1+)p2+;p1-datei=p2-datei+1;m+;break;if(m=0)printf( 对不起！没有要删除的信息！);while(w=1)printf(n返回主菜单：n);printf(请按“0”：);scanf(%d,&w);system(cls);return(head);void printlist(struct sqlist * head,int length,int listsize)struct sqlist *p1;int w=1,i=0;p1=head;for(;p1-datei!=NULL;p1+)printf(%d tt,p1-datei);length+;i+;printf(n已存空间为：%dn,length);printf(还有内存为：%dn,listsize=LIST_SIZE-length); while(w=1)printf(n返回主菜单：n);printf(请按“0”：);scanf(%d,&w);system(cls);void main ()int choice;struct sqlist *p;dodisplayMenu();scanf(%d,&choice);if(choice4)printf(nnnn);system(cls);printf(ttt您的输入有误，请重新输入！);continue;elseif(choice=1)system(cls);p=creatlist();if(choice=2)system(cls);p=inserlist(p);if(choice=3)system(cls);p=detelist(p);if(choice=4)system(cls);printlist(p,length,listsize);while(choice!=0);2.运行过程运行的菜单如图1.1所示。图1.1菜单首先是建立顺序表，其建立过程如图1.2所示。图1.2顺序表的建立之后可以作插入、删除和输出操作。数据的插入如图1.3所示。图1.3数据的插入可以输出所有数据，查看数据是否插入成功。其运行结果如图1.4所示。图1.4查看数据还可以删除数据，其操作运行的结果如图1.5所示。图1.5删除数据 查看数据是否被删除其运行结果如图1.6所示。图1.6查看数据最后结束程序运行结果如图1.7所示。图1.7结束程序（二）顺序表的链式表示与实现1.其源代码如下所示：#include#include#include /清屏#define NULL 0#define LEN sizeof(struct sqlist)struct sqlist/*-结构体-*/int num;struct sqlist * next;struct sqlist * creat(void)/*-新建链表-*/int w=1;struct sqlist *head;struct sqlist * p1,* p2;head=p1=p2=(struct sqlist * ) malloc(LEN);printf(请输入编号：);scanf(%d,&p1-num);printf(建立完成请按0n);while(1)p1=(struct sqlist * ) malloc(LEN);printf(请输入编号：);scanf(%d,&p1-num);if(p1-num=0)break;p2-next=p1;p2=p1;printf(ttt建立完成请按0n);p2-next=NULL;while(w=1)printf(ntttt返回主菜单：n);printf(请按“0”：);scanf(%d,&w);system(cls);return(head);void print(struct sqlist * head)/*-输出所有人信息-*/int w=1;struct sqlist * p;p=head;printf(n);doprintf(%-3dtt,p-num);p=p-next;while(p!=NULL);while(w=1)printf(n返回主菜单：n);printf(请按“0”：);scanf(%d,&w);system(cls);struct sqlist * del(struct sqlist * head)/*-删除指定信息-*/int w=0,n;struct sqlist * p1,* p2;if(head=NULL)printf(n此链表为空！);return(head);p1=head;printf(请输入delete的编号：);scanf(%d,&n);while(p1-num!=n)p2=p1;p1=p1-next;if(p1-num=n)if(p1=head)head=p1-next;/*删除的是第一个结点*/elsep2-next=p1-next;/*删除的是中间结点或是尾结点*/elseprintf(没有%d的信息。 n,n);printf(nnnn);printf(ttt您已成功删除%d的信息,n);printf(nnnn);while(w=1)printf(n返回主菜单：n);printf(请按“0”：);scanf(%d,&w);system(cls);return(head);struct sqlist *insert(struct sqlist * head)/*-插入一新纪录-*/int w=1;struct sqlist * tx;struct sqlist * p0, * p2, * p1;p1=head;tx=(struct sqlist * ) malloc(LEN);printf(输入新建人信息n);printf(请输入编号：);scanf(%d,&tx-num);p0=tx;if(head=NULL)head=p0;p0-next=NULL;elsewhile(p0-nump1-num)&(p1-next!=NULL)p2=p1;p1=p1-next;if(p0-numnum)if(head=p1)head=p0;/*插入首结点*/elsep2-next=p0;/*插到中间结点*/p0-next=p1;elsep1-next=p0;p0-next=NULL;/*插到尾结点*/while(w=1)printf(nttt返回主菜单：n);printf(请按“0”：);scanf(%d,&w);system(cls);return(head);void displayMenu()/*-菜单-*/printf(n);printf( 欢 迎 使 用 通 讯 录 系 统);printf(n -);printf(n |=菜单=|n); printf(n |HHHH HH HH HH HH HH HHH|); printf(n |HHHH HH HH HH HH HH HHH|); printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|); printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|); printf(n |HHH 1 : HHH 2 : HHH|);printf(n |HHH 建立链表 HHH 新建一个信息 HHH|); printf(n |HHH HHH HHH|); printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|); printf(n |HHH 3 : HHH 4 : HHH|);printf(n |HHH 删除某人信息 HHH 输出所有信息 HHH|); printf(n |HHH HHH HHH|);printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|); printf(n |HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(n |HHHHHHHHHHH 0 :退出系统 HHHHHHHHHHHHH|);printf(n HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH|);printf(nChoice:);/*-主函数-*/void main()struct sqlist * TXL;int choice;do displayMenu();scanf(%d,&choice);if(choice8)printf(nnnn);system(cls);printf(ttt您的输入有误，请重新输入！);continue;elseif(choice=1) system(cls);TXL=creat();if(choice=2)system(cls);TXL=insert(TXL);if(choice=3)system(cls);TXL=del(TXL);if(choice=4)system(cls);print(TXL);while(choice!=0);2.运行过程运行的菜单如图2.1所示。图2.1菜单首先是建立顺序表，其建立过程如图2.2所示。图2.2顺序表的建立之后可以作插入、删除和输出操作。数据的插入如图2.3所示。图2.3数据的插入可以输出所有数据，查看数据是否插入成功。其运行结果如图2.4所示。图2.4查看数据还可以删除数据，其操作运行的结果如图2.5所示。图2.5删除数据 查看数据是否被删除其运行结果如图2.6所示。图2.6查看数据最后结束程序运行结果如图1.7所示。图2.7结束程序五、成绩评定优良中及格不及格出 勤内 容格 式创 新效 果总 评指导教师： 年 月 日