实验一 线性表

1、实验一 线性表实验项目名称线性表实验日期实验室9#405实验室机 号4实验类型设计型 学时2一、实验目的及要求（本次上机实践所涉及并要求掌握的知识点）1、掌握顺序表的存储结构形式及其描述和基本运算的实现。2、掌握动态链表结构及相关算法设计。3、正确设计和调试本实验程序并上机运行，记录程序运行结果，结合运行结果，对程序进行分析。4、完成实验报告。二、实验环境（本次上机实践所使用的平台和相关软件）微型计算机windows xp，visual c+三、实验内容及步骤实验内容：1、实现顺序表的创建（输入）、输出、查找、插入和删除功能。2、单链表的查找、插入和删除等基本操作的实现。3、利用基本操作，实现

2、两个有序单链表的合并。实验步骤：1、实现顺序表的创建（输入）、输出、查找、插入和删除功能。l 顺序表类型定义和相关的常量定义。l 创建顺序表：初始化顺序表。l 编写函数，为顺序表录入数据。l 编写顺序表输出函数，通过循环依次输出sqlist中的各个元素的内容。l 编写函数实现查找、插入和删除等基本操作。2、实现单链表设计以及各种基本操作的实现。l 单链表类型定义和相关的常量定义。l 创建单链表：初始化单链表。l 编写函数，为单链表录入数据。l 编写单链表输出函数，通过循环依次输出单链表中的各个元素的内容。l 编写函数实现单链表的查找、插入和删除等基本操作。3、实现两个有序单链表的合并。算法分析

3、和设计为使算法的时间复杂度为o(n+m)只能采用“平移指针，一次扫描”的方法，于是设两个指针分别指向两个线性表表头。为使合并后仍为一个有序表，需对指针所指结点的数据域进行比较。要使合并后的有序表为递减有序表，比较后选出较小的一个将其从原链表中取出插入到新表的表首。指针后移，重复，步，直到其中一个表结束，将尚未结束表的元素依次取出插入新表。为减少头指针的变化，采用带有头结点的链表。算法如下：struct nodeint data; struct node *link;typedef struct node node;node *merge_link(node *head_a,node *head

4、_b)node *p,*q,*head;head=(node*)malloc(sizeof(node);head->link=null;p=head_a->link;q=head_b->link;while(p!=null)&&(q!=null)if(p->data<q->data)head_a->link=p->link;p->link=head->link;head->link=p;p=head_a->link;elsehead_b->link=q->link;q->link=head

5、->link;head->link=q;q=head_b->link;while(p!=null) head_a->link=p->link; p->link=head->link; head->link=p; p=head_a->link; while(q!=null) head_b->link=q->link; q->link=head->link; head->link=q; q=head_b->link; free(head_a);free(head_b);return(head);四、实验结果（

6、本实验源程序清单及运行结果或实验结论、实验设计图）实验程序1. #include <stdio.h>#define ok 1#define error 0#define maxsize 100/*顺序表的容量*/typedef int elemtype;typedef struct elemtype elemmaxsize;/*存放顺序表的元素*/int last;/*顺序表的实际长度*/ sqlist;void initlist(sqlist &sq)/*初始化线性表*/sq.last=-1;void inputlist(sqlist &sq)/*输入线性表*/

7、int i=0,n=0; printf("输入线性表的长度:"); scanf("%d",&n); printf("输入线性表元素:");while(i<n)scanf("%d",&sq.elemi); i+; sq.last=n-1; printf("n");void displist(sqlist sq)/*输出线性表*/ int i; printf("输出线性表元素:");for (i=0;i<=sq.last;i+) printf(&quo

8、t;%d ",sq.elemi); printf("n");int locate(sqlist sq,elemtype x)/*按值查找*/ int i=0; while (i<=sq.last)&&(sq.elemi!=x)/*查找值为x的第1个结点*/ i+; if (i>sq.last) return(-1);/*未找到*/ else return(i+1);int inslist(sqlist &sq,elemtype e,int i) /*插入*/ int k;if(i<1)|(i>sq.last+2)pr

9、intf("插入位置i值不合法");return error;if(sq.last>=maxsize-1)printf("表已满，无法插入");return error;for(k=sq.last;k>=i-1;k-)sq.elemk+1=sq.elemk;sq.elemi-1=e;sq.last+;return ok; int dellist(sqlist &sq,int i,elemtype *e) /*删除*/int k;if(i<1)|(i>sq.last)printf("删除位置不合法");

10、return error;else*e=sq.elemi-1;for(k=i;k<=sq.last;k+)sq.elemk-1=sq.elemk;sq.last-;return ok; void main()sqlist sq; elemtype x,r; int m,n,q,t,w,e,v;initlist(sq);/*初始化顺序表sq*/inputlist(sq);displist(sq); printf("输入待查找的元素:");scanf("%d",&x); printf("输入待插入的元素:"); scanf(

11、"%d",&e);printf("输入待插入的位置:"); scanf("%d",&q);m=locate(sq, x); if (m=-1) printf("线性表中没有元素%d!n",x); else printf("%d是线性表的第%d个元素!n",x,m); v=inslist(sq,e,q);if(v=ok)displist(sq);elseprintf("待插入位置不合法:"); printf("输入待删除的位置:"); sca

12、nf("%d",&t); w=dellist(sq,t,&r); if(w=ok) displist(sq); printf("%dn",r); else printf("删除位置不合法 ");运行结果：实验程序.#include <stdio.h>#include <malloc.h>typedef char elemtype;typedef struct node elemtype data;/*数据域*/struct node *next; /*指针域*/ slink;void initl

13、ist(slink *&l) /*l作为引用型参数*/ l=(slink *)malloc(sizeof(slink); /*创建头结点*l*/l->next=null;void displist(slink *l)/*输出单链表*/ slink *p=l->next; while (p!=null) printf("%c ",p->data);p=p->next; printf("n");void createfromtail(slink *&l)/*输入单链表，当输入$时结束*/slink *r,*s;char

14、 c; int flag=1; r=l; while(flag) c=getchar(); if(c!='$') s=(slink *)malloc(sizeof(slink); s->data=c;r->next=s;r=s; else flag=0; r->next=null; /*while*/*createfromtail*/slink mergelinklist(slink *la,slink *lb)slink *pa,*pb;slink *lc,*r;pa=la->next;pb=lb->next;lc=la;lc->next=

15、null;r=lc;while(pa!=null&&pb!=null)if(pa->data<=pb->data)r->next=pa;r=pa;pa=pa->next;elser->next=pb;r=pb;pb=pb->next;if(pa)r->next=pa;elser->next=pb;free(lb);return (*lc);void main()slink *la,*lb;initlist(la);initlist(lb);/*初始化单链表l*/ printf("输入单链表la中的元素（字符型），$符号是结束标志！n");createfromtail(la);printf("输入单链表lb中的元素（字符型），$符号是结束标志！n");createfromtail(lb);printf("线性表:");displist(la);displist(lb); mergelinklist( la, lb); displist(la);运行结果：五、实验总结（对本实验结果进行分析，实验心得体会及改进意见）通过