老邱链表分册.doc

链表实验题一、 实验内容1. 编程实现链表的基本操作函数。(1). void CreatList(LinkList &La,int m)/依次输入m个数据，并依次建立各个元素结点，逐个插入到链表尾；建立带表头结点的单链表La；(2). void ListPrint(LinkList La) /将单链表La的数据元素从表头到表尾依次显示。(3).void ListInsert (LinkList &L,int i,ElemType e)/在带头结点的单链表L中第i个数据元素之前插入数据元素e(4). void ListDelete(LinkList &La, int n, ElemType &e) /删除链表的第n个元素，并用e返回其值。(5). int Search(LinkList L, ElemType x)/在表中查找是否存在某个元素x，如存在则返回x在表中的位置，否则返回0。(6). int ListLength(LinkList L) /求链表L的表长(7). void GetElem(LinkList L, int i, ElemType &e) /用e返回L中第i个元素的值链表的结点类型定义及指向结点的指针类型定义可以参照下列代码: typedef struct Node ElemType data; / 数据域 struct Node *next; / 指针域LNode, *LinkList;2. 设有链表A和B，其中的数据内容均为整型数值，且都按增序排列，生成新的链表C、D，满足下列要求：(1) (C中元素为A和B的并集)(2) D=A-B (D中元素为在A中出现但不在B中出现的元素)且C、D元素都按增序排列。编程要求：输入：键盘输入链表A的数据元素(至少5个)键盘输入链表B的数据元素(至少5个)输出：屏幕分别打印链表A，B，C，D的数据元素。3. 设有链表A和B，其中的数据内容均为整型数值，且都按增序排列，生成新的链表C、D，满足下列要求：(1) (C中元素为A和B中都出现的元素)(2) D中元素为A中元素的逆序排列编程要求：输入：键盘输入链表A的数据元素(至少5个)键盘输入链表B的数据元素(至少5个)输出：屏幕分别打印链表A，B，C、D的数据元素。4. 约瑟夫(Joseph)问题问题描述 约瑟夫(Joseph)问题的一种描述是：编号为1，2，,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数），一开始任选一个整数作为报数上限m,从第一人开始按顺时针方向从自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。基本要求采用单向循环链表模拟此过程,按照出列的顺序印出各人的编号测试数据m的初值为6；n=7,7个人的密码依次为：3，1，7，2，4，8， 4，正确的出列顺序应为6,1,4,7,2,3,5。实验提示单向循环链表的结点类型定义参照如下：typedef struct LNode int code; /定义整型变量code用来存放序号 int key; /定义整型变量key用来存放密码 struct LNode *next; LNode,*LinkList;5. 一元多项式的相加。利用两个带头结点的单链表La和Lb分别存储两个一元多项式A(x)和B(x)，对这两个一元多项式求和，输出结果。6.已知由一个线性链表表示的线性表中含有3类字符的数据元素(如：字母，数字和其他字符)，试编写算法将该线性链表分割为3个循环链表，其中每个循环链表均只含有一类字符。编程要求：输入：键盘输入一串字符，含上述的3类字符，各类字符数目5个以上输出：屏幕分别打印循环链表A，B，C的元素。7.已知线性表中的元素以值递增顺序排列，并以双向链表为存储结构。试实现以下功能：删除表中所有MinNum, MaxNum范围内的数据。编程要求：输入：键盘输入链表的数据元素(至少5个)键盘输入MinNum, MaxNum值输出：屏幕打印链表操作的结果。/*(1). void CreatList(LinkList &La,int m)/依次输入m个数据，并依次建立各个元素结点，逐个插入到链表尾；建立带表头结点的单链表La；(2). void ListPrint(LinkList La) /将单链表La的数据元素从表头到表尾依次显示。(3).void ListInsert (LinkList &L,int i,ElemType e)/在带头结点的单链表L中第i个数据元素之前插入数据元素e(4). void ListDelete(LinkList &La, int n, ElemType &e) /删除链表的第n个元素，并用e返回其值。(5). int Search(LinkList L, ElemType x)/在表中查找是否存在某个元素x，如存在则返回x在表中的位置，否则返回0。(6). int ListLength(LinkList L) /求链表L的表长(7). void GetElem(LinkList L, int i, ElemType &e) /用e返回L中第i个元素的值*/#include #include #include typedef int ElemType ;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/(1). void CreatList(LinkList &La,int m)/依次输入m个数据，并依次建立各个元素结点，逐个插入到链表尾；建立带表头结点的单链表La；void CreateList(LinkList &L,int n)LinkList p,r;int i;/srand(time(0);L=(LinkList )malloc(sizeof(LNode);L-next =NULL;r=L;for(i=0;idata =rand( )%100+1;cinp-data ;r-next =p;r=p;p-next =NULL;/(2). void ListPrint(LinkList La) /将单链表La的数据元素从表头到表尾依次显示。void PrintList(LinkList &L)LinkList p;p=L-next ;while(p)coutdata next ;coutendl;/(3).void ListInsert (LinkList &L,int i,ElemType e)/在带头结点的单链表L中第i个数据元素之前插入数据元素eint ListInsert(LinkList &L,int i,ElemType &e)int j;LinkList p,s;p=L;j=1;while(p&jnext ;+j;if(!p|ji)return -2;s=(LinkList)malloc(sizeof(LNode);s-data =e;s-next =p-next ;p-next =s;return 0;/(4). void ListDelete(LinkList &La, int n, ElemType &e) /删除链表的第n个元素，并用e返回其值。int ListDelete(LinkList &L,int i,ElemType &e)int j;LinkList p,q;p=L;j=1;while(p-next &jnext ;+j;if(!(p-next )|ji)return -2;q=p-next ;p-next =q-next ;e=q-data ;free(q);return 0;/(6). int ListLength(LinkList L) /求链表L的表长int ListLength(LinkList L)LinkList p;p=L-next ;int i=0;while(p)p=p-next ;i+;return i;/(7). void GetElem(LinkList L, int i, ElemType &e) /用e返回L中第i个元素的值int GetElem(LinkList &L,int i,ElemType &e)int j;LinkList p;p=L-next ;j=1;while(p&jnext ;+j;if(!p|ji)return -2;e=p-data ;return e;int main()LinkList L;L=(LinkList) new LNode;int n;coutinput n:n;CreateList(L,n);PrintList(L);int pos;coutpos;ElemType e;ListDelete(L,pos,e);PrintList(L);coutDelete :eendl;coutpos;coute;ListInsert(L,pos,e);PrintList(L);coutpos;coutpospos:GetElem(L,pos,e)endl;coutListLength:ListLength(L)endl;return 0;/*input n:51 2 3 4 55 4 3 2 1Delete pos :45 4 3 1Delete :2Insert pos :2Insert elem:695 69 4 3 1Get pos:3pos3:4ListLength:5Press any key to continue*/*3. 设有链表A和B，其中的数据内容均为整型数值，且都按增序排列，生成新的链表C、D，满足下列要求：(1) (C中元素为A和B中都出现的元素)(2) D中元素为A中元素的逆序排列编程要求：输入：键盘输入链表A的数据元素(至少5个)键盘输入链表B的数据元素(至少5个)输出：屏幕分别打印链表A，B，C、D的数据元素。*/#include #include #include typedef int ElemType ;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/(1). void CreatList(LinkList &La,int m)/依次输入m个数据，并依次建立各个元素结点，逐个插入到链表尾；建立带表头结点的单链表La；void CreateList(LinkList &L,int n)LinkList p,r;int i;/srand(time(0);L=(LinkList )malloc(sizeof(LNode);L-next =NULL;r=L;for(i=0;idata =rand( )%100+1;cinp-data ;r-next =p;r=p;p-next =NULL;/(2). void ListPrint(LinkList La) /将单链表La的数据元素从表头到表尾依次显示。void PrintList(LinkList &L)LinkList p;p=L-next ;if(!p)coutNoneendl;return;while(p)coutdata next ;coutendl;/(3).void ListInsert (LinkList &L,int i,ElemType e)/在带头结点的单链表L中第i个数据元素之前插入数据元素eint ListInsert(LinkList &L,int i,ElemType &e)int j;LinkList p,s;p=L;j=1;while(p&jnext ;+j;if(!p|ji)return -2;s=(LinkList)malloc(sizeof(LNode);s-data =e;s-next =p-next ;p-next =s;return 0;/(4). void ListDelete(LinkList &La, int n, ElemType &e) /删除链表的第n个元素，并用e返回其值。int ListDelete(LinkList &L,int i,ElemType &e)int j;LinkList p,q;p=L;j=1;while(p-next &jnext ;+j;if(!(p-next )|ji)return -2;q=p-next ;p-next =q-next ;e=q-data ;free(q);return 0;/(6). int ListLength(LinkList L) /求链表L的表长int ListLength(LinkList L)LinkList p;p=L-next ;int i=0;while(p)p=p-next ;i+;return i;/(7). void GetElem(LinkList L, int i, ElemType &e) /用e返回L中第i个元素的值int GetElem(LinkList &L,int i,ElemType &e)int j;LinkList p;p=L-next ;j=1;while(p&jnext ;+j;if(!p|ji)return -2;e=p-data ;return e;void CreateSq(LinkList &L)L=(LinkList) new LNode;int n;coutinput n:n;CreateList(L,n);PrintList(L);void AUB(LinkList La,LinkList Lb,LinkList &Lc)LinkList pa,pb,r;pa=La-next ;pb=Lb-next ;Lc=(LinkList ) new LNode;Lc-next =NULL;r=Lc;LinkList p;while(pa&pb)if(pa-data data )p=(LinkList )new LNode;p-next =NULL;p-data =pa-data ;r-next =p;r=p;pa=pa-next ;else if(pa-data pb-data )p=(LinkList )new LNode;p-next =NULL;p-data =pb-data ;r-next =p;r=p;pb=pb-next ;elsep=(LinkList )new LNode;p-next =NULL;p-data =pa-data ;r-next =p;r=p;pa=pa-next ;pb=pb-next ;if(!pa) r-next =pb;else r-next =pa;void Print(LinkList La,LinkList Lb,LinkList Lc)coutLa:endl;PrintList(La);coutLb:endl;PrintList(Lb);coutLc:endl;PrintList(Lc);int main()LinkList La;CreateSq(La);LinkList Lb;CreateSq(Lb);LinkList Lc;AUB(La,Lb,Lc);Print(La,Lb,Lc);return 0;/*input n:5123451 2 3 4 5input n:624789102 4 7 8 9 10La:1 2 3 4 5Lb:2 4 7 8 9 10Lc:1 2 3 4 5 7 8 9 10Press any key to continue*/*3. 设有链表A和B，其中的数据内容均为整型数值，且都按增序排列，生成新的链表C、D，满足下列要求：(1) (C中元素为A和B中都出现的元素)(2) D中元素为A中元素的逆序排列编程要求：输入：键盘输入链表A的数据元素(至少5个)键盘输入链表B的数据元素(至少5个)输出：屏幕分别打印链表A，B，C、D的数据元素。*/#include #include #include typedef int ElemType ;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/(1). void CreatList(LinkList &La,int m)/依次输入m个数据，并依次建立各个元素结点，逐个插入到链表尾；建立带表头结点的单链表La；void CreateList(LinkList &L,int n)LinkList p,r;int i;/srand(time(0);L=(LinkList )malloc(sizeof(LNode);L-next =NULL;r=L;for(i=0;idata =rand( )%100+1;cinp-data ;r-next =p;r=p;p-next =NULL;/(2). void ListPrint(LinkList La) /将单链表La的数据元素从表头到表尾依次显示。void PrintList(LinkList &L)LinkList p;p=L-next ;if(!p)coutNoneendl;return;while(p)coutdata next ;coutendl;/(3).void ListInsert (LinkList &L,int i,ElemType e)/在带头结点的单链表L中第i个数据元素之前插入数据元素eint ListInsert(LinkList &L,int i,ElemType &e)int j;LinkList p,s;p=L;j=1;while(p&jnext ;+j;if(!p|ji)return -2;s=(LinkList)malloc(sizeof(LNode);s-data =e;s-next =p-next ;p-next =s;return 0;/(4). void ListDelete(LinkList &La, int n, ElemType &e) /删除链表的第n个元素，并用e返回其值。int ListDelete(LinkList &L,int i,ElemType &e)int j;LinkList p,q;p=L;j=1;while(p-next &jnext ;+j;if(!(p-next )|ji)return -2;q=p-next ;p-next =q-next ;e=q-data ;free(q);return 0;/(6). int ListLength(LinkList L) /求链表L的表长int ListLength(LinkList L)LinkList p;p=L-next ;int i=0;while(p)p=p-next ;i+;return i;/(7). void GetElem(LinkList L, int i, ElemType &e) /用e返回L中第i个元素的值int GetElem(LinkList &L,int i,ElemType &e)int j;LinkList p;p=L-next ;j=1;while(p&jnext ;+j;if(!p|ji)return -2;e=p-data ;return e;void CreateSq(LinkList &L)L=(LinkList) new LNode;int n;coutinput n:n;CreateList(L,n);PrintList(L);void AminusB(LinkList La,LinkList Lb,LinkList &Lc)LinkList pa,pb,r;pa=La-next ;pb=Lb-next ;Lc=(LinkList ) new LNode;Lc-next =NULL;r=Lc;LinkList p;while(pa&pb)if(pa-data data )p=(LinkList )new LNode;p-next =NULL;p-data =pa-data ;r-next =p;r=p;pa=pa-next ;else if(pa-data pb-data )pb=pb-next ;elsepa=pa-next ;pb=pb-next ;if(!pa) r-next =pb;else r-next =pa;void Print(LinkList La,LinkList Lb,LinkList Lc)coutLa:endl;PrintList(La);coutLb:endl;PrintList(Lb);coutLc:endl;PrintList(Lc);int main()LinkList La;CreateSq(La);LinkList Lb;CreateSq(Lb);LinkList Lc;AminusB(La,Lb,Lc);Print(La,Lb,Lc);return 0;/*input n:10123456789101 2 3 4 5 6 7 8 9 10input n:32692 6 9La:1 2 3 4 5 6 7 8 9 10Lb:2 6 9Lc:1 3 4 5 7 8 10Press any key to continue*/*3. 设有链表A和B，其中的数据内容均为整型数值，且都按增序排列，生成新的链表C、D，满足下列要求：(1) (C中元素为A和B中都出现的元素)(2) D中元素为A中元素的逆序排列编程要求：输入：键盘输入链表A的数据元素(至少5个)键盘输入链表B的数据元素(至少5个)输出：屏幕分别打印链表A，B，C、D的数据元素。*/#include #include #include typedef int ElemType ;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/(1). void CreatList(LinkList &La,int m)/依次输入m个数据，并依次建立各个元素结点，逐个插入到链表尾；建立带表头结点的单链表La；void CreateList(LinkList &L,int n)LinkList p,r;int i;/srand(time(0);L=(LinkList )malloc(sizeof(LNode);L-next =NULL;r=L;for(i=0;idata =rand( )%100+1;cinp-data ;r-next =p;r=p;p-next =NULL;/(2). void ListPrint(LinkList La) /将单链表La的数据元素从表头到表尾依次显示。void PrintList(LinkList &L)LinkList p;p=L-next ;if(!p)coutNoneendl;return;while(p)coutdata next ;coutendl;/(3).void ListInsert (LinkList &L,int i,ElemType e)/在带头结点的单链表L中第i个数据元素之前插入数据元素eint ListInsert(LinkList &L,int i,ElemType &e)int j;LinkList p,s;p=L;j=1;while(p&jnext ;+j;if(!p|ji)return -2;s=(LinkList)malloc(sizeof(LNode);s-data =e;s-next =p-next ;p-next =s;return 0;/(4). void ListDelete(LinkList &La, int n, ElemType &e) /删除链表的第n个元素，并用e返回其值。int ListDelete(LinkList &L,int i,ElemType &e)int j;LinkList p,q;p=L;j=1;while(p-next &jnext ;+j;if(!(p-next )|ji)return -2;q=p-next ;p-next =q-next ;e=q-data ;free(q);return 0;/(6). int ListLength(LinkList L) /求链表L的表长int ListLength(LinkList L)LinkList p;p=L-next ;int i=0;while(p)p=p-next ;i+;return i;/(7). void GetElem(LinkList L, int i, ElemType &e) /用e返回L中第i个元素的值int GetElem(LinkList &L,int i,ElemType &e)int j;LinkList p;p=L-next ;j=1;while(p&jnext ;+j;if(!p|ji)return -2;e=p-data ;return e;void CreateSq(LinkList &L)L=(LinkList) new LNode;int n;coutinput n:n;CreateList(L,n);PrintList(L);void ANB(LinkList La,LinkList Lb,LinkList &Lc)LinkList pa,pb,r;pa=La-next ;pb=Lb-next ;Lc=(LinkList ) new LNode;Lc-next =NULL;r=Lc;LinkList p;while(pa&pb)if(pa-data data )pa=pa-next ;else if(pa-data pb-data )pb=pb-next ;elsep=(LinkList )new LNode;p-next =NULL;p-data =pa-data ;r-next =p;r=p;pa=pa-next ;pb=pb-next ;void Print(LinkList La,LinkList Lb,LinkList Lc)coutLa:endl;PrintList(La);coutLb:endl;PrintList(Lb);coutLc:next ;Ld=(LinkList ) new LNode;Ld-next =NULL;while(p)q=(LinkList)new LNode;q-data =p-data ;p =p-next ;q-next =Ld-next ;Ld-next =q;int main()LinkList La;CreateSq(La);LinkList Lb;CreateSq(Lb);LinkList Lc;ANB(La,Lb,Lc);Print(La,Lb,Lc);LinkList Ld;coutListOppose:endlLd:endl;ListOppose(La,Ld);PrintList(Ld);return 0;/*input n:5123451 2 3 4 5input n:63456783 4 5 6 7 8La:1 2 3 4 5Lb:3 4 5 6 7 8Lc:3 4 5ListOppose:Ld:5 4 3 2 1Press any key to continue*/*3. 设有链表A和B，其中的数据内容均为整型数值，且都按增序排列，生成新的链表C、D，满足下列要求：(1) (C中元素为A和B中都出现的元素)(2) D中元素为A中元素的逆序排列编程要求：输入：键盘输入链表A的数据元素(至少5个)键盘输入链表B的数据元素(至少5个)输出：屏幕分别打印链表A，B，C、D的数据元素。*/#include #include #include typedef int ElemType ;typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;/(1). void CreatList(LinkList &La,int m)/依次输入m个数据，并依次建立各个元素结点，逐个插入到链表尾；建立带表头结点的单链表La；void CreateList(LinkList &L,int n)LinkList p,r;int i;/srand(time(0);L=(LinkList )malloc(sizeof(LNode);L-next =NULL;r=L;for(i=0;idata =rand( )%100+1;cinp-data ;r-next =p;r=p;p-next =NULL;/(2). void ListPrint(LinkList La) /将单链表La的数据元素从表头到表尾依次显示。void PrintList(LinkList &L)LinkList p;p=L-next ;if(!p)coutNoneendl;return;while(p)coutdata next ;coutendl;/(3).void ListInsert (LinkList &L,int i,ElemType e)/在带头结点的单链表L中第i个数据元素之前插入数据元素eint ListInsert(LinkList &L,int i,ElemType &e)int j;LinkList p,s;p=L;j=1;while(p&jnext ;+j;if(!p|ji)return -2;s=(LinkList)malloc(sizeof(LNode);s-data =e;s-next =p-next ;p-next =s;return 0;/(4). void ListDelete(LinkList &La, int n, ElemType &e) /删除链表的第n个元素，并用e返回其值。int ListDelete(LinkList &L,int i,ElemType &e)int j;LinkList p,q;p=L;j=1;while(p-next &jnext ;+j;if(!(p-next )|ji)return -2;q=p-next ;p-next =q-next ;e=q-data ;free(q);return 0;/(6). int ListLength(LinkList L) /求链表L的表长int ListLength(LinkList L)LinkList p;p=L-next ;int i=0;while(p)p=p-next ;i+;return i;/(7). void GetElem(LinkList L, int i, ElemType &e) /用e返回L中第i个元素的值int GetElem(LinkList &L,int i,ElemType &e)int j;LinkList p;p=L-next ;j=1;while(p&jnext ;+j;if(!p|ji)return -2;e=p-data ;return e;void CreateSq(LinkList &L)L=(LinkList) new LNode;int n;coutinput n:n;Create