数据结构实验报告-3

1目录实验一线性表的基本操作1．实验目的……………………………………………………22．实验环境……………………………………………………23．实验内容，主要代码，调试与运行……………………24．总结……………………………………………………14实验二栈的基本操作1．实验目的……………………………………………………152．实验环境……………………………………………………153．实验内容，主要代码，调试与运行……………………154．总结……………………………………………………18实验三赫夫曼树1．实验目的……………………………………………………182．实验环境……………………………………………………183．实验内容，主要代码，调试与运行……………………194．总结……………………………………………………322实验一线性表的基本操作一、实验目的１、熟悉Ｃ或VC++语言上机环境。２、会定义线性表的顺序存储结构和链式存储结构。３、熟悉顺序表和链表的一些基本操作和应用。４、加深对线性表的理解，逐步培养解决实际问题的编程能力。二、实验环境运行Ｃ或VC++的微机。三、实验内容1.已知线性表LA的数据元素（n个，n为偶数），现要求将LA拆开成两个新的线性表LB，LC。要求LB中的数据元素为LA中的奇数位序的数据元素（a1,a3,…,an-1），LC中的数据元素为LA中的偶数位序的数据元素（a2,a4,…,an）。实验代码如下：#includestdio.h#includemalloc.h#definemax100//定义线性表的最大长度typedefstruct{charelem;charlist[max];//线性表intlength;//length指示当前线性表的长度}sqlist;voidinitial(sqlist&);//初始化线性表voidinsert(sqlist&,int,char);//在线性表中插入元素voidinitlist(sqlist&);voidprint(sqlist);//显示线性表中所有元素voidmain(){3sqlistla,lb,lc;//la,lb,lc是线性表initial(la);initlist(lb);initlist(lc);inti;for(i=0;ila.length;i++){if(i%2==0)insert(lb,i/2,la.list[i]);//奇数位插入lbelseinsert(lc,i/2,la.list[i]);}//偶数位插入lcprintf(\n您输入的线性表元素为:\n\n);print(la);printf(线性表的奇数位次的元素为:\n\n);print(lb);printf(线性表的偶数位次的元素为:\n\n);print(lc);}voidinitial(sqlist&v){inti,a;printf(请输入一个偶数作为线性表的长度:\n\n);scanf(%d,&a);while(a%2!=0){printf(您输入的数是奇数，请重新输入一个偶数:\n\n);scanf(%d,&a);}v.length=a;printf(\n请输入线性表元素:\n\n);for(i=0;iv.length;i++)scanf(%c,&v.list[i]);//对la进行赋值}voidinitlist(sqlist&v)//构造一个空的线性表{v.elem=(char)malloc(max*sizeof(char));v.length=0;}voidinsert(sqlist&v,intj,charc){v.list[j]=c;//插入cv.length++;}voidprint(sqlistv){inti;for(i=0;iv.length;i++){printf(%c,v.list[i]);}//输出线性表元素printf(\n\n);4}调试通过后运行结果如下：2.已知线性表LA的数据元素（n个），现要求将LA的数据元素复制到另一个线性表LB中。实验代码如下：#includestdio.h#includemalloc.h#definemax100//定义线性表的最大长度typedefstruct{charelem;charlist[max];//线性表intlength;//length指示当前线性表的长度}sqlist;voidinitial(sqlist&);//初始化线性表voidinitlist(sqlist&);voidprintf(sqlist);//显示线性表中所有元素5voidmain(){sqlistla,lb;//la,lb是线性表initial(la);initlist(lb);inti;for(i=0;ila.length;i++)//复制{lb.list[i]=la.list[i];lb.length++;}printf(lb);}voidinitial(sqlist&v)//构造线性表{inti;printf(请输入一个线性表的长度(最大为100):\n);scanf(%d,&v.length);printf(请输入线性表元素:\n);for(i=0;iv.length;i++)scanf(%c,&v.list[i]);}voidinitlist(sqlist&v)//构造空线性表{v.elem=(char)malloc(max*sizeof(char));v.length=0;}voidprintf(sqlistv){inti;printf(\n复制得到的线性表为:\n);for(i=0;iv.length;i++)printf(%c,v.list[i]);printf(\n);}调试通过后运行结果如下：63.设有一个线性表采用顺序存储结构，表中的数据元素值为正整数（n个）。设在O(n)时间内，将线性表分成两为两部分，其中左半部分每个元素都小于原表的第一个元素，而右半部分则相反。实验代码如下：#includestdio.h#includemalloc.h#definemax100//定义线性表的最大长度typedefstruct{intelem;intlist[max];//线性表intlength;//length指示当前线性表的长度}sqlist;voidinitial(sqlist&);//初始化线性表voidinsert(sqlist&,int,int);voidinitlist(sqlist&);voidprint(sqlist);//显示线性表中所有元素voidmain(){sqlistla,lb,lc;7initial(la);initlist(lb);initlist(lc);inti=1,j=0,k=0,x=la.list[0];for(;ila.length;i++)if(la.list[i]x){insert(lb,j,la.list[i]);j++;}else{insert(lc,k,la.list[i]);k++;}printf(\n将输入的线性表以首元素为中心分成两部分:\n);print(lb);printf(%d\n\n,x);print(lc);}voidinitial(sqlist&v){inti;printf(请输入线性表长度:\n);scanf(%d,&v.length);printf(\n请输入线性表元素:\n);for(i=0;iv.length;i++)scanf(%d,&v.list[i]);}voidinitlist(sqlist&v)//构造一个空的线性表{v.elem=(int)malloc(max*sizeof(int));v.length=0;}voidinsert(sqlist&v,intj,intc){v.list[j]=c;//插入v.length++;}voidprint(sqlistv){inti;for(i=0;iv.length;i++){printf(%d,v.list[i]);}//输出线性表元素printf(\n\n);}调试通过后运行结果如下：84.设线性表LA＝（a1,a2,…,am），LB＝（b1,b2,…,bn）。试编写一个算法，将LA、LB合并为线性表LC，使要求LA、LB和LC均以单链表为存储结构，且LC表利用LA和LB中结点空间，这里m和n的值没有保存在头结点中，并分析算法时间复杂度。实验代码如下：#includestdio.h#includemalloc.h#includestdlib.htypedefstructnode{charx;structnode*next;时当时当＝nmaababanmbbbabaLCmnnnnmmm,...,,,,...,,,...,,,,...,,1111119}s;s*s_create(s*head){charch;s*h,*p,*q;h=(s*)malloc(sizeof(s));h-x='';p=h;fflush(stdin);//这一句必须加，不然第二次使用该函数时，ch读到的值是回车scanf(%c,&ch);while(ch!='0'){q=(s*)malloc(sizeof(s));q-x=ch;p-next=q;p=q;scanf(%c,&ch);}p-next=NULL;returnh;}voids_union(s*head1,s*head2){//s*p=head1-next,*q=head2-next,*r=head1;//实现两个链表交叉合并为head1s*h1,*h2;s*uPre;h1=head1;h2=head2;uPre=h1;//puts(合并);//一比一比例交叉合并if(NULL==h1){uPre=h2;printf(表1为空);}elseif(NULL==h2){uPre=h1;10printf(表2为空);}elsewhile(NULL!=(h1-next)&&NULL!=(h2-next)){//插入h1节点，并在插入后把uPre移到h2节点h1=h1-next;//h1下移一个节点uPre-next=h2;//插入h1节点，并转而对h2进行操作uPre=h2;//插入h2节点，并在插入后把uPre移到h1节点h2=h2-next;uPre-next=h1;uPre=h1;}//末尾补齐，在上面的情况，最终uPre=h1if(NULL==(h1-next)){uPre-next=h2;}else{h1=h1-next;uPre-next=h2;h2-next=h1;}while(p!=NULL&&q!=NULL){r-next=p-next;r=p;p=p-next;r-next=q-next;r=q;q=q-next;}if(p){r-next=p;}else{r-next=q;}*/}voidprintf_s(s*head){s*p=head-next;while(NULL!=p){printf(%c,p-x);11p=p-next;}printf(\n);}intmain(){s*head1,*head2;//intlength1=0,length2=0;head1=(s*)malloc(sizeof(s));//为head1申请空间head2=(s*)malloc(sizeof(s));printf(\n输入线性表一(遇0结束):\n);head1=s_create(head1);printf(\n线性表一:\n);printf_s(head1);printf(\n输入线性表二(遇0结束):\n);head2=s_create(head2);printf(\n线性表二:\n);printf_s(head2);printf(\n合并后的线性表为:\n);s_union(head1,head2);printf_s(hea