站长之家ppt,贵溪网站建设,wordpress搭建博客,企业管理培训课程感想【前面使用的所有链表的定义在第29节】
试题1#xff1a;
设计一个递归算法#xff0c;删除不带头结点的单链表L中所有值为x的结点。
首先来看非递归算法#xff0c;暴力遍历#xff1a;
int Del(LinkList L,ElemType x){
//此函数实现删除链表中为x的元素LNode *…【前面使用的所有链表的定义在第29节】
试题1
设计一个递归算法删除不带头结点的单链表L中所有值为x的结点。
首先来看非递归算法暴力遍历
int Del(LinkList L,ElemType x){
//此函数实现删除链表中为x的元素LNode *p,*q;p L; //p指向头结点q L-next; //q指向首元结点while(q-next!NULL){if(q-data x){p-next q-next;free(q);q p-next;}else{p p-next;q q-next;}}return 0;
}int main(){LinkList L;InitList(L);Create(L);PrintList(L);Del(L, 3);PrintList(L);return 0;
}
然后看递归算法
int Del(LinkList L,ElemType x){
//此函数实现递归删除链表中为x的元素LNode *p;if(LNULL)return 0;if(L-datax){p L;L L-next;free(p);Del(L, x);}else{Del(L-next, x);}return 0;
}int main(){LinkList L;InitList(L);Create(L);PrintList(L);Del(L, 3);PrintList(L);return 0;
}
这里分析一下怎么递归的从头开始如果首元结点就是被删掉的x那很显然如果不是这时候执行Del(L-next, x)如果第2个是被删掉的元素进入if(L-next-datax)分支此时pL实际上执行pL-nextp指向了第2个被删除的结点第2行L L-next执行的是L-nextL-next-next把首元结点的next域修改为指向第3个结点然后free(p)释放空间最后继续执行Del(L,x)相当于Del(L-next, x)这时L-next是第3个结点依次递归。
试题2与题1差不多
试题3L是带头结点的单链表编写算法实现从尾到头反向输出每个结点的值
此题可以使用栈来解决这里主要提书上的递归方法
void AdversePrint(LinkList L){
//此函数实现反向打印链表L的元素if(L!NULL){AdversePrint(L-next); //递归printf([%d] , L-data); //打印当前元素}
}int main(){LinkList L;InitList(L);Create(L);PrintList(L);AdversePrint(L-next); //带头结点的链表这里L-next指向首元结点return 0;
}
试题4编写在带头结点的单链表L中删除一个最小值结点的高效算法。
注意不要写野指针
void Deletexmin(LinkList L){
//此函数实现删除链表最小值元素LNode *p, *q, *m, *n;int a;p L; //p指向头结点q L-next; //q指向首元结点a q-data; //首元结点元素赋给am p;n q;while (q-next ! NULL){q q-next; //指针后移p p-next; //指针后移if(q-data a){a q-data; //更新am p; //记录当前最小值的前驱结点n q; //记录当前最小值结点}}m-next n-next;free(n);
}int main(){LinkList L;InitList(L);Create(L);PrintList(L);Deletexmin(L);PrintList(L);return 0;
}
试题5将单链表的元素就地逆置
利用头插法重新建立链表
void ReverseL(LinkList L){
//此函数实现逆置单链表所有元素LNode *p, *q;p L;q L-next; //q指向首元结点p q;q q-next; //q指向第二个结点p-next NULL;if(qNULL)return ;else{while (q!NULL){p q-next; //p移向首元结点q-next L-next; L-next q; //修改头结点指针头插法q p;} }
}int main(){LinkList L;InitList(L);Create(L);PrintList(L);ReverseL(L);PrintList(L);return 0;
}试题6有一个带头结点的单链表L设计算法使其递增有序。
采用插入排序的思想
void SortL(LinkList L){
//此函数实现递增排序单链表所有元素LNode *p, *q, *r;p L-next; //p工作在排好序的链表q p-next; //q是待排序元素即第二个结点断开之后的第一个结点r q-next; //r在q之后p-next NULL; //断开while(q!NULL){r q-next;p L; while(q-data p-next-data p-next!NULL){p p-next;}q-next p-next;p-next q;q r;}
}int main(){LinkList L;InitList(L);Create(L);PrintList(L);SortL(L);PrintList(L);return 0;
}输出
请输入要输入元素的个数5
请输入第1元素的值5
请输入第2元素的值3
请输入第3元素的值1
请输入第4元素的值2
请输入第5元素的值4
当前单链表的所有元素[5] [3] [1] [2] [4]
当前单链表的所有元素[1] [2] [3] [4] [5]
试题7修改试题1的参数条件if(q-data x)即可
试题8求两个链表的公共链表
如果有公共链表一定是这样的Y型拓扑结构 int LengthL(LinkList L){
//此函数实现求解链表长度LNode *p;p L;int i 0;while(p-next!NULL){p p-next;i;}return i;
}LinkList Search_1st_common(LinkList L1,LinkList L2){
//此函数实现查找两个链表的公共结点int L1length LengthL(L1);int L2length LengthL(L2);printf(%d, LengthL(L1));printf(%d, LengthL(L2));int delta 0; //记录长链表比短链表多多少LNode *longList, *shortList;if(L1length L2length){longList L1-next; //L1更长,longList指向L1首元结点shortList L2-next;delta L1length - L2length;}else{longList L2-next; //L2更长longList指向L2首元结点shortList L1-next;delta L2length - L1length;}printf(%d, longList-data);printf(%d, shortList-data);printf(%d, delta);for (int i 0; i delta;i){ // 移动longList指针至delta位置longList longList-next;}printf(%d, longList-data);//经过以上移动此时longList指针与shortList指针指的剩余长度一样while (longList!shortList longList ! NULL){longList longList-next;shortList shortList-next;}return longList;
}void PrintResult(LinkList L){if(L NULL)printf(公共结点不存在);elsePrintList(L);
}int main(){LinkList L1,L2;InitList(L1);Create(L1);PrintList(L1);InitList(L2);Create(L2);PrintList(L2);PrintResult(Search_1st_common(L1, L2));return 0;
}
输出
请输入要输入元素的个数2
请输入第1元素的值1
请输入第2元素的值2
当前单链表的所有元素[1] [2]
请输入要输入元素的个数5
请输入第1元素的值3
请输入第2元素的值4
请输入第3元素的值5
请输入第4元素的值6
请输入第5元素的值7
当前单链表的所有元素[3] [4] [5] [6] [7]
253136公共结点不存在请输入要输入元素的个数2
请输入第1元素的值1
请输入第2元素的值2
当前单链表的所有元素[1] [2]
请输入要输入元素的个数3
请输入第1元素的值3
请输入第2元素的值4
请输入第3元素的值5
当前单链表的所有元素[3] [4] [5]
233114公共结点不存在
在写这段代码的时候踩了一个坑大家观察下面两段代码
void Search_1st_common(){
//此函数实现查找两个链表的公共结点int L1length 3;int L2length 5;int delta 0; //记录长链表比短链表多多少if(L1length L2length){delta L1length - L2length;}else{delta L2length - L1length;}printf(%d, delta);
}int main(){Search_1st_common();return 0;
}
void Search_1st_common(){
//此函数实现查找两个链表的公共结点int L1length 3;int L2length 5;int delta 0; //记录长链表比短链表多多少if(L1length L2length){int delta L1length - L2length;}else{int delta L2length - L1length;}printf(%d, delta);
}int main(){Search_1st_common();return 0;
}
打印delta的结果分别是2和0.后一段代码中if...else...结构体内相当于重新定义了一个delta当结构体执行结束后又被释放掉了所以delta的返回结果是0.
试题9试写出算法按递增次序输出单链表中各节点的数据元素并释放结点所占的内存空间。
此题可以仿照试题4.不多解释。
void Printelement(LinkList L){
//此函数实现按递增次序输出单链表数据元素并释放结点所占的存储空间LNode *p, *q; // q记录了每次遍历的最小值结点的前驱int min;while(L-next!NULL){ //最后结束条件是L删成空p L;q L;min p-next-data; //第1个元素while(p-next ! NULL){if(p-next-data min){min p-next-data;q p;}p p-next;}printf([%d], q-next-data);p q-next;q-next p-next;free(p);}
}int main(){LinkList L1;InitList(L1);Create(L1);PrintList(L1);Printelement(L1);return 0;
}
试题10将一个链表A分解成两个链表A和B使得A表中含有原表中序号是奇数的元素B表中含有原表中序号是偶数的元素。
这里不采用书上写的设置访问序号变量。由于有周期性适当控制指针即可
void Printelement(LinkList L){
//此函数实现将一个链表A分解成两个链表A和B使得A表中含有原表中序号是奇数的元素B表中含有原表中序号是偶数的元素。LNode *p, *q, *r; //r指针工作在新链表中LinkList L0; //L0相当于题目中的BInitList(L0);p L-next;q p-next; //q指向第2个结点r L0;while(p!NULLq!NULL){r-next q;p-next q-next;if(p-next NULL)break;p p-next;if(q-next NULL)break;q p-next;r r-next;r-next NULL;}PrintList(L);PrintList(L0);
}int main(){LinkList L1;InitList(L1);Create(L1);PrintList(L1);Printelement(L1);return 0;
}
输出
当前单链表的所有元素[1] [2] [3] [4] [5] [6]
当前单链表的所有元素[1] [3] [5]
当前单链表的所有元素[2] [4] [6]当前单链表的所有元素[1] [2] [3] [4] [5] [6] [7]
当前单链表的所有元素[1] [3] [5] [7]
当前单链表的所有元素[2] [4] [6]
试题11设为线性表采用带头结点的hc单链表存放设计一个就地算法将其拆分成两个线性表使得
此题跟第10题很像修改指针即可。
void Printelement(LinkList L){
//此函数实现将一个链表A分解成两个链表A和B使得A表中含有原表中序号是奇数的元素B表中含有原表中序号是偶数倒序的元素。LNode *p, *q, *r; //r指针工作在新链表中LinkList L0; //L0相当于题目中的BInitList(L0);p L-next;q p-next; //q指向第2个结点r L0-next;while(p!NULLq!NULL){L0-next q; //头插法p-next q-next;q-next r;if(p-next NULL)break;p p-next;if(p-next NULL)break;q p-next;r L0-next;}PrintList(L);PrintList(L0);
}int main(){LinkList L1;InitList(L1);Create(L1);PrintList(L1);Printelement(L1);return 0;
}
输出
当前单链表的所有元素[1] [2] [3] [4] [5] [6]
当前单链表的所有元素[1] [3] [5]
当前单链表的所有元素[6] [4] [2]
试题12在一个递增有序的单链表中删除所有数值相同的元素使表中不再有重复的元素。
void DeleteSame(LinkList L){
//此函数实现把递增单链表的重复元素删除LNode *p, *q;p L-next; //第一个元素q p-next;while(q!NULL){if(p-data q-data){q q-next;free(p-next);p-next q;}else{p p-next;q q-next;}}
}int main(){LinkList L1;InitList(L1);Create(L1);PrintList(L1);DeleteSame(L1);PrintList(L1);return 0;
}
输出
当前单链表的所有元素[1] [2] [2] [3] [3] [4] [4] [5]
当前单链表的所有元素[1] [2] [3] [4] [5]
试题13假设有两个按元素值递增次序排列的线性表以单链表形式存储。编写算法把这两个单链表归并为一个按元素值递减的单链表并要求利用原来两个单链表的结点存放归并后的单链表。
此题属于简单题最后使用头插法倒序即可。
LinkList Merge(LinkList L1,LinkList L2){
//此函数实现把两个递增的单链表合并成递减的单链表LNode *p, *q; //L1指针LNode *m, *n; //L2指针LNode *r; //新表头插法LinkList L;InitList(L); //初始化p L1-next; //L1第1个结点m L2-next; //L2第1个结点q p-next; //L1第2个结点n m-next; //L2第2个结点r L-next; while(L1-next!NULL L2-next!NULL){if(p-data m-data){L-next p;p-next r;p q;r L-next;if(q NULL)break;q q-next;}else{L-next m;m-next r;m n;r L-next;if(n NULL)break;n n-next;}}if(L1-next NULL){while(L2-next!NULL){L-next m;m-next r;m n;r L-next;if(n NULL)break;n n-next;}}else{while(L1-next!NULL){L-next p;p-next r;p q;r L-next;if(q NULL)break;q q-next;}}return L;
}int main(){LinkList L1, L2;InitList(L1);Create(L1);PrintList(L1);InitList(L2);Create(L2);PrintList(L2);PrintList(Merge(L1,L2));return 0;
}输出
请输入要输入元素的个数3
请输入第1元素的值1
请输入第2元素的值2
请输入第3元素的值4
当前单链表的所有元素[1] [2] [4]
请输入要输入元素的个数2
请输入第1元素的值1
请输入第2元素的值2
当前单链表的所有元素[1] [2]
当前单链表的所有元素[4] [2] [2] [1] [1]
试题14设A和B是两个单链表带头结点其中元素递增有序设计一个算法从A和B中公共元素产生单链表C要求不破坏AB的结点。
LinkList Intersection(LinkList L1,LinkList L2){
//此函数实现产生单链表包含两个链表的公共元素LNode *p; //L1指针LNode *q; //L2指针LNode *r; //新表的指针LinkList L;InitList(L);p L1-next;q L2-next;r L;while(p!NULL q!NULL){if(p-data q-data){p p-next;}else if(p-data q-data){LNode *s (LNode *)malloc(sizeof(LNode));s-data p-data;s-next NULL;r-next s;r r-next;p p-next; //后移q q-next;}else{q q-next;}}return L;
}int main(){LinkList L1, L2;InitList(L1);Create(L1);PrintList(L1);InitList(L2);Create(L2);PrintList(L2);PrintList(Intersection(L1,L2));return 0;
}输出
请输入要输入元素的个数4
请输入第1元素的值1
请输入第2元素的值2
请输入第3元素的值3
请输入第4元素的值4
当前单链表的所有元素[1] [2] [3] [4]
请输入要输入元素的个数4
请输入第1元素的值2
请输入第2元素的值3
请输入第3元素的值4
请输入第4元素的值5
当前单链表的所有元素[2] [3] [4] [5]
当前单链表的所有元素[2] [3] [4]
试题15此题要求同14但要求合并链表存储在A中。
LinkList Intersection(LinkList L1,LinkList L2){
//此函数实现产生单链表包含两个链表的公共元素LNode *p, *m; // L1指针,m保存待删结点的前驱p待删结点LNode *q; //L2指针m L1;p L1-next;q L2-next;while(p!NULL q!NULL){if(p-data q-data){m-next p-next;free(p);p m-next;}else if(p-data q-data){p p-next;q q-next;m m-next;}else{q q-next;}}if(q NULL){while(p!NULL){m-next p-next;free(p);p m-next;}}return L1;
}int main(){LinkList L1, L2;InitList(L1);Create(L1);PrintList(L1);InitList(L2);Create(L2);PrintList(L2);PrintList(Intersection(L1,L2));return 0;
}输出
当前单链表的所有元素[3] [5] [7] [9]
当前单链表的所有元素[4] [5] [8] [9]
当前单链表的所有元素[5] [9]当前单链表的所有元素[2] [3] [4] [5]
当前单链表的所有元素[1] [2] [3] [4]
当前单链表的所有元素[2] [3] [4]当前单链表的所有元素[5] [6] [7] [8]
当前单链表的所有元素[1] [2] [3] [4]
当前单链表的所有元素
