分数 5
作者 李卫明
单位 杭州电子科技大学
1.3 在第1题( 编写程序,建立2个带头结点单链表,输入若干整数将正整数插入第1个单链表,将负整数插入第2个单链表,插入前和插入后单链表保持递增或相等次序,显示2个单链表,最后销毁。程序不可存在内存泄漏。)建立2个单链表基础上,设计和实现就地逆置单链表函数,即利用原单链表结点建立元素次序相反的单链表。编写程序,建立2个单链表,就地逆置这2个单链表,显示逆置前后的各单链表。注意不可存在内存泄漏。
若干整数。
每个单链表输出占一行,元素间用分隔符分隔;两个初始单链表和两个就地逆置后单链表,4个单链表,共4行。
100 2 3 -2 -8 -6 -9 -10 50 2 -1
- 2->2->3->50->100
- -10->-9->-8->-6->-2->-1
- 100->50->3->2->2
- -1->-2->-6->-8->-9->-10
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
C程序如下:
- printf("%d", p->Data); //先输出数据
- p = p->Next; //再指向下一结点
- if (p) printf("->"); //若不为空则输出“->”
- }
- printf("\n"); //换行
- }
-
- void Destroy(List L) {
- List p = L;
- while (p->Next) { //先删除头结点后的所有结点
- List q = p->Next;
- p->Next = q->Next;
- free(q);
- }
- free(p); //最后删除头结点
- }
-
- void Sort(List L) {//选择排序
- List pStar, pcur,pMin;
- pStar = L->Next;//指向第一有效结点
- int temp;
- for (;pStar != NULL;pStar = pStar->Next) {//外循环,遍历整个单链表
- pMin = pStar;//假设最小值为pStar
- for (pcur = pMin->Next;pcur != NULL; pcur = pcur->Next) {//内循环找出包括pStar及之后的最小值
- if (pcur->Data < pMin->Data) {
- pMin = pcur;//找到更小值则将其地址赋值给pMin
- }
- }
- if (pStar != pMin) {//若最小值与假设的不一致,则交换数据。不改变链接关系
- temp = pMin->Data;
- pMin->Data = pStar->Data;
- pStar->Data = temp;
- }
- }
- }
-
- void Reverse(List L){//单链表的反转
- List pHead = NULL;//反装后的头结点
- List pCur = L->Next;//待反转的结点
- List pNext = NULL;//待反转结点的下一结点,防止找不到要反转的结点,因为反转过程中会不断出现连个分开的单链表
- while(pCur!=NULL){//要反转的结点为空时则退出循环
- pNext = pCur->Next;//待反转结点的下一结点
- pCur->Next = pHead;//反转该结点,改变其指向关系
- pHead = pCur;//更新头结点的位置
- pCur = pNext;//更新待反转结点
- }
- L->Next = pHead;//最终的头结点即为pHead,将原来头结点的地址赋值为pHead
- }
- /*
- void Reverse(List L) {//单链表的原地反转
- if(L==NULL){
- return;
- }
- List pstar = L->Next;
- List pend = pstar->Next;
- while (pend) {
- pstar->Next = pend->Next;//链接链表防止锻链
- pend->Next = L->Next;//调转
- L->Next = pend;//接
- pend = pstar->Next;//指针移动
- }
- }*/