数据结构代码.docx

第二章线性表1.线性表/*实现了线性表的定义，创建空的线性表，线性表元素的输入，输出操作，对线性表进行增删的操作以及对两个顺序线性表按照顺序进行合并*/#include#include#include#define LIST_INIT_SIZE 100 /定义线性表的长度#define INCREMENT 2 /定义存储空间的分配增量typedef structint *elem; /线性表存储空间的首地址int length; /线性表的长度 int listsize; /现性表的大小 Sqlist;void init(Sqlist &L) /初始化一个线性表L.elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int);if(!L.elem) exit(0);L.length=0;L.listsize=LIST_INIT_SIZE;return ;void listinsert(Sqlist &L,int e,int i) /在第i个元素之前插入数据eint *newbase=NULL; /创建新的起始地址int *q;int *p;if(iL.length+1) /插入元素失败exit(0);if(L.length=L.listsize) /存储空间不足，重新分配空间newbase=(int *)realloc(L.elem,(LIST_INIT_SIZE+INCREMENT)*sizeof(int);if(!newbase)exit(0);L.elem=newbase;L.listsize+=INCREMENT;q=&L.elemi-1; /找到第i个元素for(p=&L.elemL.length-1;p=q;p-) *(p+1)=*p; /把第i个元素及之后的每一个元素向后移动一位*q=e; /插入目标元素L.length+;return ;void listdelete(Sqlist &L,int i,int &e) /删除第i个元素,返回被删除的元素的值int *p;int *q;if(iL.length)exit(0);e=L.elemi-1;q=&L.elemL.length-1;for(p=&L.elemi;pL.listsize)exit(0);for(j=0;ji;j+)scanf(%d,&L.elemj);L.length+;void listput(Sqlist L)/输出线性表中全部的元素int i=0;if(L.length=0)exit(0);for(i=0;iL.length;i+)printf(%d ,L.elemi);printf(n);return ;void mergin(Sqlist La,Sqlist Lb,Sqlist &Lc)int *pa=La.elem;int *pb=Lb.elem;int *pa_last=&La.elemLa.length-1;int *pb_last=&Lb.elemLb.length-1;int *pc;int i=0;init(Lc);pc=Lc.elem;while(pa=pa_last&pb=pb_last) /这里以及下面的判断条件一定要指针指出去才能算把数据放大Lc中去了if(*pa=*pb)Lc.elemi=*pa;pa+;elseLc.elemi=*pb;pb+;i+;Lc.length+;while(pa=pa_last)Lc.elemi=*pa;pa+;i+;Lc.length+;while(pb=pb_last)Lc.elemi=*pb;pb+;i+;Lc.length+;/*int main() /测试线性表的增删操作int e;Sqlist L;init(L); /创建一个新的空的线性表printf(请输入5个数n);listinput(L,5); /输入5个整数printf(输入的5个整数为: );listput(L);printf(在第2个数之前插入整数99);listinsert(L,99,2);printf(n输出线性表中的数据);listput(L);printf(删除线性表中第4位元素);listdelete(L,4,e); printf(删除的数为:%dn,e);printf(输出线性表中的数据);listput(L);return 0;*/int main() /测试两个顺序线性表的合并操作printf(创建两个线性表);Sqlist La,Lb,Lc;init(La);init(Lb);printf(输入线性表1中的数据，5个整数n);listinput(La,5);printf(输入线性表2中的数据，5个整数n);listinput(Lb,5);mergin(La,Lb,Lc);printf(n输出合并和线性表3中的数据n);listput(Lc);return 0;线性链表#include#include#includetypedef struct LNode /定义一种数据类型，它是由一个整数数据和一个指向这中数据的指针组成的int data; /存放整形数据struct LNode *next; /指向下一个数据的指针 *linklist;/创建一个有n个数据的数据链表（带头结点,且是向前插入，后面数据一个个往前输）void createlinklist1(linklist &L,int n)int i;linklist p;L=(linklist)malloc(sizeof(LNode); /创建一个头结点（线性表的空间不是连在一起的，不能一起申请完了，只能用一个申请一个）L-next=NULL;for(i=n;i0;i-)p=(linklist)malloc(sizeof(LNode);scanf(%d,&p-data);p-next=L-next; L-next=p;/创建一个有n个数据的数据链表（带头结点，且是向后插入，前面数据一个个往后输）void createlinklist2(linklist &L,int n)int i;linklist p,r; /把p作为要新创建的节点，r永远是p节点前面的节点，这样链就不会断L=(linklist)malloc(sizeof(LNode);L-next=NULL;r=L;for(i=0;idata);r-next=p;p-next=NULL;r=p;/输出线性链表中的数据void putoutlinklist(linklist &L)linklist p;if(!L-next)exit(0);p=L; /p指向头结点while(p-next) /p指下一个数据向的数据后面还有数据p=p-next; /p指向printf(%d ,p-data);printf(n);/获取链表中第n位的元素void getelem(linklist &L,int n,int &e)linklist p;int i=0;p=L;while(p&inext; /不断获取下一位元素i+;if(!p|in) exit(0);e=p-data;/在链表第n位之前插入一个元素void insertlinklist(linklist &L,int n,int e)linklist p,q;int i=0;p=L;while(p&inext;i+; if(!p|in-1) exit(0); q=(linklist)malloc(sizeof(LNode);q-data=e;q-next=p-next;p-next=q;void deletelinklist(linklist &L,int n,int &e) /删除链表中第n个数据linklist p;int i=0;p=L;while(p&inext;i+;if(!q|in) exit(0);e=p-next-data;p-next=p-next-next;int main()linklist l; int e=0;printf(创建一个有5个元素的链表n);/createlinklist1(l,5);createlinklist2(l,5);printf(输入链表中的内容:n);putoutlinklist(l);printf(删除链表