沈 阳 工 程 学 院
学 生 实 验 报 告
（课程名称： 数据结构与算法 ）
实验题目： 线性表
班 级 网本112班 学 号 2011414217 姓 名 樊鹏鹏 地 点 F606 指导教师 吕海华、祝世东 实 验 日 期 : 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 long num; struct number *head,*p1; p1=head=(struct number*)malloc( SIZE * sizeof(struct number)); scanf(\"%ld\for(;p1->num!=0;L++) { } return(head); p1++; scanf(\"%ld\struct number *p; 2 } int s=L; p=head; if(p!=0) { } printf(\"\\n您输入的数据为：\\n\"); for(;s>0;p++,s--) printf(\"%ld \/*------------------查找顺式线性表中的元素------------------*/ void search(struct number *head) { struct number *p; long num1; int n=0,s=0; p=head; printf(\"\\n请输入您要查找的数据：\\n\"); scanf(\"%ld\if(head!=0) for(;p->num!=0;p++) { } if(s==0) 3 n++; if(p->num==num1) { } s=1; break; } printf(\"\\n没有您所要查找的数据\\n\"); printf(\"\\n找到您所需数据'%ld'在表中第%d个\\n\else /*------------------插入顺式线性表的元素------------------*/ struct number *insert(struct number*head) { } /*------------------删除顺式线性表的元素------------------*/ struct number *del(struct number*head) { struct number *p1,*p2; 4 struct number *p1,*p2; int n=1; long num1; p1=p2=head; p2=p2+L-1; printf(\"\\n请输入您要插入的数据：\\n\"); scanf(\"%ld\if(num1 } long num1; int n=1; p1=p2=head; printf(\"\\n请输入要删除的数据：\\n\"); scanf(\"%ld\p2=p2+L-1; for(;p1->num!=num1 && n<=L;p1++) { } else { } for(;p1<=p2;p1++) p1->num=(p1+1)->num; L--; printf(\"\\n没有您要删除的数据\\n\"); return(0); n=n+1; if(n>L) return(head); void main() { struct number *head,*head1,*head2; int a; /*head=creat(); printf(\"\\n************************************\\n\"); print(head);*/ printf(\" 按1：创建\\n\"); 5 printf(\" 按2：插入\\n\"); printf(\" 按3：查找\\n\"); printf(\" 按4：删除\\n\"); printf(\" 按5：输出\\n\"); printf(\" 按0：退出\\n\"); printf(\"*************************************\\n\"); } scanf(\"%d\while(a!=0) { } switch(a) { case 1:printf(\"请创建顺序表:\"); head=creat();break; case 2:head1=insert(head);break; case 3:search(head);break; case 4:head2=del(head);break; case 0:break; } printf(\"\\n继续操作请输入，否则请按0退出：\\n\"); scanf(\"%d\ case 5:print(head); 6 图1 图2 链表： #include \"stdio.h\" #include \"malloc.h\" typedef struct node { int data; struct node *next; }LNode,*LinkList; 7 int len; /*------------------创建链式线性表------------------*/ LinkList CreatLink() { int x,count=0; LinkList p,q,h; h=NULL; p=(LinkList)malloc(sizeof(LNode)); scanf(\"%d\ p->data=x; p->next=NULL; while(x!=0) { count++; { q->next=p; q=p; } q=h=p; if(count==1) else p=(LinkList)malloc(sizeof(LNode)); scanf(\"%d\ p->data=x; p->next=NULL; } return h; } /*------------------删除链式线性表的元素------------------*/ 8 LinkList del(LinkList h,int data) { } /*------------------输出链式线性表的元素------------------*/ void PrintLink(LNode *h) { LNode *p; 9 LinkList p1,p2; if(h==NULL) { } p1=h; while(data!=p1->data&&p1->next!=NULL) { } if(data==p1->data) { } else printf(\"%ld not been found!\\n\return(h); if(p1==h) h=p1->next; else p2->next=p1->next; printf(\"delete:%ld\\n\len=len-1; p2=p1; p1=p1->next; printf(\"\\n list null!\\n\"); return h; p=h; while(p!=NULL) { printf(\"%d \ } /*------------------计算链式线性表的长度------------------*/ int LinkLen(LinkList h) { LinkList p=h; int count=0; while(p!=NULL) { count++; p=p->next; } return count; } /*------------------查找链式线性表中的元素------------------*/ LinkList QueryLink(LinkList h,int x) { LinkList q,p; q=p=h; while(p!=NULL) { if(p->data==x) break; else 10 p=p->next; } } { q=p; p=p->next; } if(p!=NULL) return q; return NULL; else } /*------------------向链式线性表插入元素------------------*/ LinkList InsertLink(LinkList h,int i,int x) { LinkList p,q; int j; p=(LinkList)malloc(sizeof(LNode)); p->data=x; if(i==0) { p->next=h; h=p; } else { q=h; j=1; while(q!=NULL && j { switch(a) { case 1:printf(\"请输入:\"); h=CreatLink(); printf(\"创建链表成功!\"); break; case 2:printf(\"请输入要插入的元素:\");scanf(\"%d\h=InsertLink(h,1,x); break; case 3:len=LinkLen(h); printf(\"该链表的长度 case 4:printf(\"请输入要查找的元素:\");scanf(\"%d\ if(p!=NULL) printf(\"find=%d\\n\ else 为:%d\p=QueryLink(h,x); printf(\"no found\\n\"); break; case 5: printf(\"\\n请输入要删除的元素:\"); scanf(\"%d\ if(x!=0) h=del(h,x);break; case 6: printf(\"输出链表:\");PrintLink(h); break; case 0: break; } } printf(\"\\n继续操作请选择，退出请安0\\n\"); scanf(\"%d\ } 13 图3 图4 14 五、成绩评定 出 勤 内 容 格 式 创 新 效 果 总 评 优 良 中 及格 不及格 指导教师： 年 月 日 15 16 17 因篇幅问题不能全部显示，请点此查看更多更全内容