搜索
数据结构实验报告一．顺序表要求：实现顺序表的初始化、在指定位置插入和删除元素。算法思路：线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。顺序表的初始化操作就是为顺序表分配一个预定义大小的空间，并将线性表的当前长度设为“0”。线性表的插入操作是在线性表的第i-1个数据元素和第i个元素之间插入新的数据元素，使得长度为n的线性表变成长度为n+1的线性表，而删除恰好相反长度变为n-1的线性表，而且删除点后面的元素要往前移动一个位。程序代码：#includestdio.h#includemalloc.h#defineMAXSIZE50typedefcharelemtype;typedefstruct//类型定义{elemtypev[MAXSIZE];intlast;}SeqList;SeqList*Init_SeqList()//初始化操作{SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L-last=-1;returnL;}voidCreate(SeqList*L)//建立顺序表{inti=0;elemtypech;scanf(%c,&ch);while(ch!='\n'){L-v[i++]=ch;scanf(%c,&ch);L-last=i-1;}}voidPrintL(SeqList*L)//输出顺序表{inti;printf(此表为:\n);for(i=0;iL-last;i++){printf(%c,L-v[i]);}printf(%c\n,L-v[i]);}voidLength(SeqList*L)//顺序表长度函数{printf(此表长度:\n%d,L-last+1);printf(\n);}voidinsert(SeqList*L,inti,elemtypex)//插入函数{intj;if(L-last==0)printf(Error!\n);if(i1||iL-last)printf(Error!);for(j=L-last;j=i-1;j--)L-v[j+1]=L-v[j];L-v[i-1]=x;L-last++;PrintL(L);Length(L);}voidDelete(SeqList*L,inti)//删除函数{intj;if(L-last==-1)printf(Error!);if(i1||iL-last+1)printf(Error!);for(j=i;j=L-last;j++)L-v[j-1]=L-v[j];L-last--;PrintL(L);Length(L);}voidmain()//程序主函数{inti,j,k;elemtypea,b;SeqList*L;L=Init_SeqList();printf(建立顺序表：\n);Create(L);PrintL(L);Length(L);printf(\n);printf(请输入你想插入的元素及其位置：\n);scanf(%s%d,&b,&j);insert(L,j,b);printf(请输入你想删除的位置：\n);scanf(%d,&k);Delete(L,k);}程序运行：二．单链表要求：实现单链表的初始化、在指定位置插入和删除元素。算法思路：线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素。因此，为了表现每个元素与后继元素的逻辑关系需要用到指针。单链表的插入就是先生成一个数据域为插入元素的界点然后插入单链表中，并且修改前后节点的指针域，完成插入操作。反之删除链表元素时仅需修改前后两个元素的节点使之相连便可。程序代码：#defineNULL0#includestdlib.h#includestdio.htypedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;voidCreateList_L(LinkList*L);voidShowList(LinkList*L);LNode*GetElem(LinkListhead);voidInsertList(LinkList*head);voidDeleteList(LinkListhead);voidmain(){LNode*L;intj,loop=1;printf(\n);while(loop){printf(1.建立单链表\n);printf(2.在单链表插入元素\n);printf(3.删除单链表元素\n);printf(请选择序号(1-3):);scanf(%d,&j);switch(j){case1:CreateList_L(&L);break;case2:InsertList(&L);break;case3:DeleteList(L);break;}printf(结束此程序吗？（0——结束1——继续）：\n);scanf(%d,&loop);printf(\n);}}voidCreateList_L(LinkList*L){LNode*p;intflag=1;(*L)=(LinkList)malloc(sizeof(LNode));(*L)-next=NULL;printf(请输入链表元素(输0结束):\n);while(flag){p=(LinkList)malloc(sizeof(LNode));p-next=NULL;scanf(%d,&p-data);if(p-data==0)break;p-next=(*L)-next;(*L)-next=p;}ShowList(L);}voidShowList(LinkList*L){LinkListp;printf(头节点-);for(p=(*L)-next;p!=NULL;p=p-next){printf(%d-,p-data);}printf(NULL!\n);}voidInsertList(LinkList*head){LNode*pre,*s;inti,j,x;printf(请输入插入位置:);scanf(%d,&i);printf(请输入插入元素:);scanf(%d,&x);pre=*head;j=0;while(pre!=NULL&&ji-1){pre=pre-next;j++;}s=(LNode*)malloc(sizeof(LNode));s-data=x;s-next=pre-next;pre-next=s;ShowList(head);printf(\n);}voidDeleteList(LinkListhead){LNode*pre,*r;inti,j;pre=head;printf(请输入删除位置:);scanf(%d,&i);j=0;/*查找第i-1个结点*/while(pre-next!=NULL&&ji-1){pre=pre-next;j++;}r=pre-next;pre-next=r-next;free(r);ShowList(&head);}程序运行：三．链表的合并要求：给定的2个有序线性链表的合并（合并到1个新的链表中以及合并到其中的1个链表中两种方式）。算法思路：先创建两个有序线性链表a，b。然后将两个有序线性链表a，b合并到a或者h中，得运用指针分别指向a，b当前待比较插入的节点，最后将两个链表的元素有序归并到表a或者h中。程序代码：#includestdlib.h#includestdio.h#includeconio.h#includemalloc.h#defineLsizeof(structNode)structNode{longintnumber;structNode*next;};structNode*create(inta){intn;structNode*p1,*p2,*head;head=NULL;n=0;p2=p1=(structNode*)malloc(L);scanf(%ld,&p1-number);while(a){n=n+1;if(n==1)head=p1;elsep2-next=p1;p2=p1;p1=(structNode*)malloc(L);if(a!=1)scanf(%ld,&p1-number);a--;}p2-next=NULL;return(head);}voidprint(structNode*head){structNode*p;p=head;printf(数字:\n);if(head!=NULL)do{printf(%ld,p-number);printf();p=p-next;}while(p!=NULL);printf(\n);}structNode*inter_link(structNode*chain1,inta,structNode*chain2,intb){inttemp;structNode*head,*p1,*p2,*pos;if(a=b){head=p1=chain1;p2=chain2;}else/*ba*/{head=p1=chain2;p2=chain1;temp=a,a=b,b=temp;}pos=head;while(p2!=NULL){p1=p1-next;pos-next=p2;pos=p2;p2=p2-next;pos-next=p1;pos=p1;}returnhead;}voidInsertSort(structNode*p,intm){inti,j,t;structNode*k;k=p;for(i=0;im-1;i++){for(j=0;jm-i-1;j++){if(p-number(p-next)-number){t=p-number;p-number=(p-next)-number;(p-next)-number=t;}p=p-next;}p=k;}}intmain(){structNode*p1,*p2;inta;intb;inth;printf(请输入第一个链表:\n);printf(\n输入链表的长度a:\n);scanf(%d,&a);printf(请输入链表数据：);p1=create(a);printf(\n你刚才输入的第一个链表信息:\n);print(p1);printf(\n请输入第二个链表:\n);printf(\n输入链表的长度b:\n);scanf(%d,&b);printf(请输入链表数据：);p2=create(b);printf(\n你刚才输入的第二个链表的信息:\n);print(p2);p1=inter_link(p1,a,p2,b);h=a+b;a=h;print(p1);InsertSort(p1,h);InsertSort(p1,a);printf(\n排序后的链表a:\n);print(p1);printf(\n排序后的链表h:\n);print(p1);return0;}程序运行：四．双向链表要求：实现双向链表的初始化、在指定位置插入和删除元素。算法思路：因为单链表的节点中只有一个指示直接后继的指针域，因此只能从某节点出发顺指针往后寻查其它节点，若需寻查节点的直接前趋，则需从表头指针出发。所以在双向链表节点中有两个指针域，一个指向后继，一个指向前趋。程序代码：#includestdio.h#includemalloc.h#defineERROR0#defineOK1typedefintElemtype;typedefstructmyNode{Elemtypedata;structmyNode*prior,*next;}Node;Node*InitList(){Node*H;H=(Node*)malloc(sizeof(Node));if(!H)returnERROR;H-next=H-prior=H;returnH;}