C语言数据结构线性表的基本操作实验报告.doc

实验一 线性表的基本操作 一、实验目的与基本要求1掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系。2 了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数据的逻辑结构的关系。3 掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4 掌握运用C语言上机调试线性表的基本方法。二、实验条件1 硬件：一台微机2 软件：操作系统和C语言系统三、实验方法确定存储结构后，上机调试实现线性表的基本运算。四、实验内容1 建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。2 建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序表，判断是否为空，取表中第i个元素，定位函数（返回第一个与x相等的元素位置），插入，删除。3 假设有两个按数据元素值非递减有序排列的线性表A和B，均以顺序表作为存储结构。编写算法将A表和B表归并成一个按元素值非递增有序（允许值相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4 假设有两个按数据元素值非递减有序排列的线性表A和B，均以单链表作为存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性表C。五、附源程序及算法程序流程图1.源程序（1）源程序(实验要求1和3)#include#include#include#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct arrint * elem;int length;int listsize;Sqlist;void menu(); /菜单void InitList(Sqlist *p);/ 创建线性表 void ShowList(Sqlist *p);/ 输出顺序线性表 void ListDelete(Sqlist *p,int i,int &e);/ 在顺序线性表中删除第i个元素，并用e返回其值void ListInsert(Sqlist *p);/ 在顺序线性表中第i个元素前插入新元素evoid ListEmpty(Sqlist *p);/ 判断L是否为空表void GetList(Sqlist *p,int i,int &e);/ 用e返回L中第i个数据元素的值void ListInsert(Sqlist *p,int i,int e);bool compare(int a,int b);void LocateElem(Sqlist *L,int e);/ 在顺序线性表L中查找第1个值与e满足compare()d元素的位序void MergeList_L(Sqlist *La,Sqlist *Lb); / 归并 void main()Sqlist La;Sqlist Lb;int n,m,x;menu();scanf(%d,&n);while(n)switch(n)case 0: ; break;case 1:InitList(&La);break;case 2:ListEmpty(&La);break;case 3:printf(请输入插入的位序:n);scanf(%d,&m);printf(请出入要插入的数:n);scanf(%d,&x);ListInsert(&La,m,x);break;case 4:printf(请输入删除元素的位序:n);scanf(%d,&m);ListDelete(&La,m,x);printf(删除的元素为:%dn,x);break;case 5:printf(请输入要找的与线性表中相等的数:n);scanf(%d,&m);LocateElem(&La,m);break;case 6:printf(请输入查找的位序:n);scanf(%d,&m);GetList(&La,m,x);printf(La中第%d个元素的值为%dn,m,x);break;case 7:ShowList(&La);break;case 8:InitList(&Lb);break;case 9:MergeList_L(&La,&Lb);printf(归并成功!);break;menu();scanf(%d,&n);/*菜单*/void menu()printf(*nn);printf( 0.退出nn);printf( 1.创建线性表Lann);printf( 2.判断La是否为空表nn);printf( 3.插入元素(La)nn);printf( 4.删除元素(La)nn);printf( 5.定位元素(La)nn);printf( 6.取元素(La)nn);printf( 7.输出线性表nn);printf( 8.创建线性表Lbnn);printf( 9.归并为一个线性表Lann);printf(*nn);/*创建顺序线性表L*/void InitList(Sqlist *L)int n;int i=0;L-elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int);if(NULL=L-elem)printf(储存分配失败!n);elseL-length=0;L-listsize=LIST_INIT_SIZE;printf(输入顺序表a:n);scanf(%d,&n);while(n)L-elemi=n;i+;L-length+;L-listsize=L-listsize-4;scanf(%d,&n);/*输出顺序线性表*/void ShowList(Sqlist *p)int i;if(0=p-length)printf(数组为空!n);elsefor(i=0;ilength;i+)printf(%d ,p-elemi);printf(n);/*判断L是否为空表*/void ListEmpty(Sqlist *p)if(0=p-length)printf(L是空表!n);elseprintf(L不是空表!n);/*在顺序线性表中第i个元素前插入新元素e */void ListInsert(Sqlist *p,int i,int e)int *newbase;int *q1;int *q2;while(ip-length+1)printf(您输入的i超出范围!n请重新输入要插入的位置n:);scanf(%d,&i);if(p-length=p-listsize)newbase=(int *)realloc(p-elem,(p-listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);elsep-elem=newbase;p-listsize+=LISTINCREMENT;q1=&(p-elemi-1);for(q2=&(p-elemp-length-1);q2=q1;-q2)*(q2+1)=*q2;*q1=e;+p-length;/*/在顺序线性表中删除第i个元素，并用e返回其值*/void ListDelete(Sqlist *p,int i,int &e)int *q1,*q2;while(ip-length)printf(您输入的i超出范围!请重新输入:);scanf(%d,&i);q1=&(p-elemi-1); e=*q1;q2=p-elem+p-length-1;for(+q1;q1length;/*对比a与b相等*/bool compare(int a,int b) if(a=b)return 1;elsereturn 0;/*在顺序线性表L中查找第1个值与e满足compare()d元素的位序*/void LocateElem(Sqlist *L,int e)int i=1;int *p;p=L-elem;while(ilength & !compare(*p+,e)+i;if(ilength)printf(第1个与e相等的元素的位序为%dn,i);elseprintf(没有该元素!n);/*用e返回L中第i个数据元素的值*/void GetList(Sqlist *p,int i,int &e)Sqlist *p1;p1=p;e=p1-elemi-1;/* 已知顺序线性表La和Lb是元素按值非递减排列 */* 把La和Lb归并到La上,La的元素也是按值非递减 */void MergeList_L(Sqlist *La,Sqlist *Lb)int i=0,j=0,k,t;int *newbase;Sqlist *pa,*pb;pa=La;pb=Lb;while(ilength & jlength)if(pa-elemi = pb-elemj)if(pa-listsize=0)newbase=(int *)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);for(k=pa-length-1; k=i; k-)pa-elemk+1=pa-elemk;pa-length+;pa-elemi=pb-elemj;i+;j+;elsei+;while(jlength)if( pa-listsize length-j )newbase=(int *)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);for(j;jlength;j+,i+)pa-elemi=pb-elemj;pa-length+;for(i=0;ilength/2;i+)t=pa-elemi;pa-elemi=pa-elempa-length-i-1;pa-elempa-length-i-1=t;（2）源程序(实验要求2和4)#include#include#includetypedef struct LNodeint data;struct LNode *next;LNode, *LinkList;void menu();LinkList InitList();void ShowList(LinkList L);void ListDelete(LinkList L,int i,int &e);void ListEmpty(LinkList L);void GetList(LinkList L,int i,int &e);void ListInsert(LinkList L,int i,int e);bool compare(int a,int b);void LocateElem(LinkList L,int e);LinkList MergeList_L(LinkList La,LinkList Lb);int total=0;void main()LinkList La;LinkList Lb;La=(LinkList)malloc(sizeof(struct LNode);La-next=NULL;Lb=(LinkList)malloc(sizeof(struct LNode);Lb-next=NULL;int n;int m;int x;menu();scanf(%d,&n);while(n)switch(n)case 0: ; break;case 1:La-next=InitList();break;case 2:ListEmpty(La);break;case 3:printf(请输入要插入到第几个节点前:n);scanf(%d,&m);printf(请输入插入的数据:n);scanf(%d,&x);ListInsert(La,m,x);break;case 4:printf(请输入删除元素的位序:n);scanf(%d,&m);ListDelete(La,m,x);printf(删除的元素为:%dn,x);break;case 5:printf(请输入要找的与线性表中相等的数:n);scanf(%d,&m);LocateElem(La,m);break;case 6:printf(请输入查找的位序:n);scanf(%d,&m);GetList(La,m,x);printf(La中第%d个元素的值为%dn,m,x);break;case 7:ShowList(La);break;case 8:Lb-next=InitList();break;case 9:La=MergeList_L(La,Lb);printf(归并成功n);break;menu();scanf(%d,&n);void menu()printf(*nn);printf( 0.退出nn);printf( 1.创建线性表Lann);printf( 2.判断是否为空表nn);printf( 3.插入元素nn);printf( 4.删除元素nn);printf( 5.定位元素nn);printf( 6.取元素nn);printf( 7.输出线性表nn);printf( 8.创建线性表Lbnn);printf( 9.归并两线性表nn);printf(*nn);/ 创建链式线性表LLinkList InitList()int count=0;LinkList pHead=NULL;LinkList pEnd,pNew;pEnd=pNew=(LinkList)malloc(sizeof(struct LNode);printf(请输入数据:n);scanf(%d,&pNew-data);while(pNew-data)count+;if(count=1)pNew-next=pHead;pEnd=pNew;pHead=pNew;elsepNew-next=NULL;pEnd-next=pNew;pEnd=pNew;pNew=(LinkList)malloc(sizeof(struct LNode);printf(请输入数据:n);scanf(%d,&pNew-data);free(pNew);total=total+count;return pHead;/ 判断L是否为空表void ListEmpty(LinkList L)if(NULL=L-next)printf(此表为空表!n);elseprintf(此表不为空表!n);/ 在链式线性表中第i个元素前插入新元素evoid ListInsert(LinkList L,int i,int e)LinkList p;LinkList s;p=L;int j=0;while(p&jnext;+j;if(!p|ji-1)printf(不存在您要找的节点!n);elses=(LinkList)malloc(sizeof(int);s-data=e;s-next=p-next;p-next=s;printf(插入节点成功!n);/ 输出链式线性表void ShowList(LinkList L)LinkList p;p=L-next;if(p=NULL)printf(此表为空表!n);elsewhile(p)printf(%d ,p-data);p=p-next;printf(n);/ 在链式线性表中删除第i个元素，并用e返回其值void ListDelete(LinkList L,int i,int &e)LinkList p;LinkList q;p=L;int j=0;while(p-next & jnext;+j;if(!(p-next)|ji-1)printf(没有找到要删除的位置!);elseq=p-next;p-next=q-next;e=q-data;free(q);/ 用e返回L中第i个数据元素的值void GetList(LinkList L,int i,int &e)LinkList p;p=L-next;int j=0;while(p-next & jnext;+j;if(!(p)|ji-1)printf(没有找到要查找的位置!);elsee=p-data;/ 对比a与b相等bool compare(int a,int b) if(a=b)return 1;elsereturn 0;/ 在链式线性表L中查找第1个值与e满足compare()d元素的位序void LocateElem(LinkList L,int e)int i=0;LinkList p;p=L;while(p-next & !compare(p-data,e)p=p-next;i+;if(NULL=p-next)if(0=compare(p-data,e)printf(没有该元素!n);elseprintf(第1个与e相等的元素的位序为%dn,i);elseif(compare(p-data,e)printf(没有该元素!n);LinkList MergeList_L(LinkList La,LinkList Lb)int i,j,k;LinkList pa_1,pb_1,pa_2,pb_2,pc,pd;pa_1=La-next;pc=pa_2=La;pb_1=pb_2=Lb-next;if(pa_1-data pb_1-data)pc=pa_2=Lb;pa_1=Lb-next;pb_1=pb_2=La-next;while(pa_1 & pb_1)if(pa_1-data = pb_1-data)pa_2-next=pb_1;pb_2=pb_1-next;pb_1-next=pa_1;pb_1=pb_2;pa_2=pa_2-next;elsepa_1=pa_1-next;pa_2=pa_2-next;if(pb_1)pa_2-n