PTA数据结构作业一

6-1 链表的插入算法

本题要求实现一个插入函数，实现在链表llist中的元素x之后插入一个元素y的操作。

函数接口定义：

int InsertPost_link(LinkList llist, DataType x, DataType y); 其中 llist是操作的链表，x是待插入元素y的前驱节点元素，y是待插入的元素

int InsertPost_link (LinkList llist,DataType x,DataType y)
{LinkList m=llist->next;LinkList n;while(m->data!=x){m=m->next;if(m==NULL){printf ("not exist data %d\n",x);return 0;}}n=(LinkList) malloc (sizeof(struct Node));if (n!=NULL){n->data=y;n->next=m->next;m->next=n;return 0;}
}

6-2 链表的删除算法

本题要求实现一个函数，实现删除链表llist中的指定元素deldata。

函数接口定义：

void DelNode_Link(head, deldata);

其中head是操作的链表表头结点，deldata是待删除的元素。

1.创建结构体和宏定义类型名
#include<stdio.h>
#include<stdlib.h>typedef int DataType;
struct Node {DataType	  data;struct Node*  next;
};
typedef struct Node  *PNode;
typedef struct Node  *LinkList;2.创建头节点。
LinkList SetNullList_Link ()
{LinkList head=(LinkList)malloc(sizeof(struct Node));if(head!=NULL){head->next=NULL;return head;}elseprintf("alloc failure");return head;
}3.利用尾插法创建单向链表。
void CreatList(struct Node* head)
{int data;LinkList p=head->next,pre=head;scanf("%d",&data);while(data!=-1){p=(struct Node*)malloc(sizeof(struct Node));p->data=data;p->next=NULL;pre->next=p;pre=p;scanf("%d",&data);}
}
4.删除值为x的节点。
void DelNode_Link(LinkList head, DataType x)
{LinkList p=head->next;LinkList beforep=head;  //通过beforep和p遍历整个链表while(p!=NULL){if(p->data==x){beforep->next=p->next;free(p);//释放节点p,否则占用内存空间break;}else{beforep=p;p=p->next;if(p==NULL)printf("not exist %d\n",x);}}
}5.打印整个链表。
void print(LinkList head)
{LinkList p=head->next;while (p!=NULL){printf("%d ",p->data);p=p->next;}
}6.主函数
int main()
{   int x;LinkList head;head=SetNullList_Link();CreatList(head);scanf("%d",&x);DelNode_Link(head,x);print(head);return 0;
}

6-3 移动链表中的最大值到尾部

编写函数MoveMaxToTail()，实现查找单链表中值最大的结点，并将其移动到链表尾部，注意其他结点的相对次序不变。要求尽量具有较高的时间效率。
例如输入8 12 46 30 5，输出为8 12 30 5 46

函数接口定义：

void MoveMaxToTail (LinkList H );

void MoveMaxToTail(LinkList head)
{ 
LinkList pre=head;
LinkList r=head;LinkList q=pre->next;while(q!=NULL){ if(pre->data<q->data){ pre=q;}q=q->next;}while(r->next!=pre)r=r->next;      //指针r指向最大元素的上一个元素，便于进行删除操作q=head;while(q->next!=NULL)q=q->next;       //使q重新指向链表中的最后一个元素，便于进行插入操作if(pre->next==NULL)return;         //若最后一个元素为最大元素，则直接返回，不需要进行其他操作else{ r->next=pre->next;pre->next=NULL;q->next=pre;}
}

6-4 合并两个递增有序的单循环链表

本题要求实现一个合并函数，实现对有序单循环链表tail1和tail2的合并，要求合并时实现去重操作，即合并后的链表中没有重复的元素，并且合并后的链表为递增有序链表。

函数接口定义：

PNode mergeNDeduplicateList(PNode tail1, PNode tail2)；

其中tail1是待合并的第一个有序单循环链表，采用的尾指针表示方法；tail2是待合并的第二个有序单循环链表，采用的尾指针表示方法；

解法一：

1.创建结构体和宏定义类型名。
#include<stdio.h>
#include<stdlib.h>typedef int DataType; 
struct Node {DataType	  data; struct Node*  next;  
};
typedef struct Node  *PNode;    
typedef struct Node  *LinkList;   2.创建尾节点，给尾节点的赋值-1。
PNode createEmptyLinkedList()
{PNode current;  //尾结点current = (PNode)malloc(sizeof(Node));current->next = NULL;current->data = -1;return current;
}3.创建单循环链表。注意，尾节点并未插入链表中，tail->next指向最后一个节点，并不是tail指向最后一个节点。tail->data的值为-1。
PNode buildCircularLinkedList(int n, PNode tail)
{PNode current=NULL, prev;prev = tail; for (int i = 0; i < n; i++){current = (PNode)malloc(sizeof(Node));current->next = NULL;scanf("%d", &current->data);prev->next = current;prev = current;}current->next = tail->next;     //形成循环tail->next = current;     //tail在此时才变成了尾指针，并指向尾结点；之前一直担任头指针的角色，指向的是首元节点。return tail;
}4.实现有序单循环链表tail1和tail2的合并，要求合并时实现去重操作，即合并后的链表中没有重复的元素，并且合并后的链表为递增有序链表。
PNode mergeNDeduplicateList(PNode tail1, PNode tail2)
{int temp;PNode pre, q;//合并tail1和tail2链表，并将循环链表拆成单向链表LinkList head=tail1->next->next;        //head为tail1的首元节点tail1->next->next= tail2->next->next;    //将tail1的尾结点与tail2的首元节点相连接tail2->next->next=NULL;    //将tail2尾结点的指针域置空//通过指针pre和p的移动，对链表进行冒泡排序（从小到大）。pre=head;         //pre指向首元节点q=head->next;for(pre=head; pre->next!=NULL; pre=pre->next)for(q=pre->next; q!=NULL; q=q->next){if(pre->data>q->data){temp=pre->data;pre->data=q->data;q->data=temp;}}//对链表进行去重操作，代码如下pre=head;q=pre->next;while(q!=NULL){if(pre->data==q->data)   //两个结点中的数据元素相等{ if(q== tail2->next)        //当最后两个元素相等时，需要做特殊处理{tail2->next=pre;          //因为q->next=NULL,当执行pre->next=q->next时，会导致pre->next=NULL，pre->next=NULL;      //即tail2节点会丢失，不便于等会链表首尾结合和返回tail2指针}                              else                                //相等的不是最后两个结点{pre->next=q->next;    //删除后一个结点free(q);q=pre->next;}}else    //两个结点中的值不相等，则后移，继续对比{pre=q;q=q->next;}}tail2->next->next=head;  //对链表进行首尾接合,并使tail2作为尾指针return tail2;
}
5.打印链表。
void printCircularLinkedList(PNode tail)
{PNode current, last;last = tail->next;current = last->next;do{printf("%d ", current->data);current = current->next;} while (current != last->next);
}
6.将函数整合进主函数中。代码如下
int main()
{PNode list1, list2;int list1_number, list2_number;list1 = createEmptyLinkedList();list2 = createEmptyLinkedList();scanf("%d", &list1_number);buildCircularLinkedList(list1_number, list1);scanf("%d", &list2_number);buildCircularLinkedList(list2_number, list2);list1 = mergeNDeduplicateList(list1, list2);printCircularLinkedList(list1);return 0;
}

解法二：

#include<stdio.h>
#include<stdlib.h>typedef int DataType;      
struct Node
{DataType data;struct Node * next;
};
typedef struct Node Node;  
typedef struct Node  *PNode;
typedef struct Node  *LinkList;PNode createEmptyLinkedList()
{PNode current;current = (PNode)malloc(sizeof(Node));current->next = NULL;current->data = -1;return current;
}PNode buildCircularLinkedList(int n, PNode tail)
{PNode current=NULL, prev;prev = tail; for (int i = 0; i < n; i++){current = (PNode)malloc(sizeof(Node));current->next = NULL;scanf("%d", &current->data);prev->next = current;prev = current;}current->next = tail->next;tail->next = current;return tail;
}PNode mergeNDeduplicateList(PNode tail1, PNode tail2)
{PNode LinkNode;LinkNode = tail2->next->next;tail2->next->next = tail1->next->next;tail1->next->next = LinkNode;free(tail2);PNode StopNode,pre,p;StopNode = tail1->next->next;while(StopNode != tail1->next){pre = StopNode;p = pre->next;while(pre != tail1->next){if(p->data == StopNode->data){if(p == tail1->next)tail1->next = pre;PNode temp;temp = p;pre->next = p->next;p = pre->next;free(temp);}else{pre = pre->next;p = pre->next;}}StopNode = StopNode->next;}do{pre = tail1->next->next;p = pre->next;while(pre != tail1->next){if(p->data < pre->data){DataType TempData;TempData = p->data;p->data = pre->data;pre->data = TempData; }else{pre = pre->next;p = pre->next;}}StopNode = StopNode->next;}while(StopNode != tail1->next);return tail1;
}void printCircularLinkedList(PNode tail) 
{PNode current, last;last = tail->next;current = last->next;do{printf("%d ", current->data);current = current->next;} while (current != last->next);
}int main()
{PNode list1, list2;int list1_number, list2_number;list1 = createEmptyLinkedList();list2 = createEmptyLinkedList();scanf("%d", &list1_number);buildCircularLinkedList(list1_number, list1);scanf("%d", &list2_number);buildCircularLinkedList(list2_number, list2);list1 = mergeNDeduplicateList(list1, list2);printCircularLinkedList(list1);return 0;
}

6-5 链表中奇偶结点的移动

本题要求实现一个函数，实现对单循环链表中奇数和偶数结点的移动，要求奇数在前面，偶数在后面，且结点之间的相对顺序不变。

函数接口定义：

PNode Move_Odd_Even(LinkList tail);

tail是单循环链表的尾指针

解法一：

奇偶点移动函数，此函数是本题的重点，采用的方法大致为：
①建立两个新链表，head1链表负责装偶数，head2链表负责装奇数。
②遍历链表每一个节点，若为奇数，则利用尾插法插入head2链表；若为偶数，则利用尾插法插入head1链表；
③将head1和head2的链表头尾连接，形成一个新的单向循环链表，并将次链表的尾指针作为返回值。

PNode  Move_Odd_Even(LinkList tail)
{PNode head=tail->next, pre=head->next, q=pre->next;free(head);    //释放原链表的头指针，因为头指针无数据LinkList head1=(LinkList)malloc(sizeof(struct Node));PNode pre1=head1;    //pre1指针随着新插入的节点移动，便于进行尾插法LinkList head2=(LinkList)malloc(sizeof(struct Node));PNode pre2=head2;    //pre2指针随着新插入的节点移动，便于进行尾插法while(q!=head->next)    //原链表是循环链表，当q遍历到原来pre的位置（首元节点）时，遍历结束{if (pre->data%2==0)    //判断元素是否为偶数{pre->next=pre1->next;pre1->next=pre;pre1=pre1->next;}else    //若不是偶数，则为奇数{pre->next=pre2->next;pre2->next=pre;pre2=pre2->next;}pre=q;q=q->next;     //pre始终保持在q的前面}
//将head1链表和head2链表合成一个新的单循坏链表head1=head1->next;  //head1链表在后，不需要其头结点pre2->next=head1;    //两个链表相连接pre1->next=head2;    //形成循坏return pre1;               //返回新循坏链表的尾指针
}

解法二：

该程序的主要思想在于：

1、遍历栈，找到偶数

2、利用尾插法将偶数插入队尾

#include<stdio.h>
#include<stdlib.h>typedef int DataType; 
struct Node 
{DataType      data; struct Node*  next;  
};
typedef struct Node  *PNode;    
typedef struct Node  *LinkList;   LinkList CreateList_Tail_loop()
{LinkList head = (LinkList)malloc(sizeof(struct Node));PNode cur = NULL;PNode tail = head;DataType data;scanf_s("%d", &data);while (data != -1){   cur = (struct Node*)malloc(sizeof(struct Node));cur->data = data;tail->next = cur;tail = cur;scanf_s("%d", &data);}tail->next = head;return tail;
}
PNode  Move_Odd_Even(LinkList tail)
{PNode pre = tail->next;PNode head = tail->next;PNode P2 = NULL;PNode p = pre->next;PNode temp = (struct Node*)malloc(sizeof(struct Node));temp->data = 0;tail->next = temp;temp->next = head;tail = temp;while(p->data){if(p->data%2 ==0){P2 = p;p = p->next;pre->next = p;tail->next = P2;tail = P2;}else{   p = p->next;pre = pre->next;}}pre->next = temp->next;tail->next = head;free(temp);return tail;
}void print(LinkList tail)    
{PNode  head = tail->next;PNode p = head->next;while (p != head){printf("%d ", p->data);p = p->next;}
}void DestoryList_Link(LinkList tail)
{PNode pre = tail->next;PNode p = pre->next;while (p != tail){free(pre);pre = p;p = pre->next;}free(pre);free(tail);
}int main()
{LinkList tail = NULL;LinkList p = NULL;tail = CreateList_Tail_loop();p = Move_Odd_Even(tail);print(p);DestoryList_Link(tail);return 0;
}

7-1 多项式的加法

用链表表示多项式，并实现多项式的加法运算

输入格式:

输入在第一行给出第一个多项式POLYA的系数和指数，并以0,0 结束第一个多项式的输入；在第二行出第一个多项式POLYB的系数和指数，并以0,0 结束第一个多项式的输入。

输出格式:

对每一组输入，在一行中输出POLYA+POLYB和多项式的系数和指数。

输入样例:

5,0 2,1 1,6 8,15 0,0
-2,1 3,6 4,8 0,0

输出样例:

5,0 4,6 4,8 8,15 

解法一：

本题主要思路:
1.建立两个头指针分别为head1和head2链表，链表每一个节点分别记录每一个多项式的系数coef和指数exp。
2.preA遍历链表head1，preB遍历链表head2。
3.建立一个只有一个头节点的链表head，逐步遍历链表head1和head2。分别有如下三种情况：
①preA->exp<preB->exp,将节点preA利用尾插法插入链表head。
②preB->exp<preA->exp,将节点preB利用尾插法插入链表head。
③preB->exp=preA->exp，这种情况分为两种：
当preA->coef+preB->coef=0时，释放节点preA和preB。
当preA->coef+preB->coef≠0时：将多项式指数相同的项的系数相加，记录在preA，并利用尾插法将preA节点插如链表head。
#include<stdio.h>
#include<stdlib.h>
struct tagNode
{float coef;     //系数coefficientint exp;         //指数exponentstruct tagNode *next;  //指针域 
};typedef struct tagNode Node;
typedef struct tagNode *PNode;void insertList(PNode head,PNode pnode)
{PNode pPre = head;while(pPre->next != NULL){if(pPre->next->exp>pnode->exp)   //链表中节点pPre->next的指数>新加入节点pnode的指数{                                                       //将新节点pnode插入到pPre之后pnode->next = pPre->next;pPre->next = pnode;break;}else     //链表中节点pPre->next的指数≤新加入节点pnode的指数，继续往后查找{pPre = pPre->next;}}if(pPre->next == NULL)     //新加入节点pnode的指数较大，放在链表最后{pPre->next = pnode;}
}void CreateList(PNode head)
{int exp;float coef;PNode pTemp = NULL;head->next = NULL;scanf("%f,%d",&coef,&exp);while(coef != 0 || exp != 0){pTemp = (PNode)malloc(sizeof(struct tagNode));pTemp->coef = coef;pTemp->exp = exp;pTemp->next = NULL;insertList(head, pTemp);scanf("%f, %d", &coef, &exp);}
}void printLinkedList(PNode head)
{PNode temp = head->next;while(temp != NULL){printf("%0.0f,",temp->coef);printf("%d ",temp->exp);temp = temp->next;}printf("\n");
}void Add_Poly(PNode pa,PNode pb)
{PNode p = pa->next;    //链表1，和多项式的结果放在链表1中 PNode q = pb->next;PNode pre = pa;PNode u;float x;        //临时变量 while(p != NULL && q != NULL){if(p->exp < q->exp)  //比较链表1和链表2当前节点的指数大小，链表1也是存放结果的地方{pre = p;p = p->next; //p指向要比较的下一个节点，pre最终指向结果链表的最后一个节点}else if(p->exp == q->exp) //假如链表1和链表2的指数相等，则要系数相加{x = p->coef + q->coef;if(x != 0) //相加后的系数不是0，保留上一个节点就好了{p->coef = x;pre = p; } else    //相加后系数为0，不需要保留任何一个节点，删除链表1的节点{pre->next = p->next;free(p); }p=pre->next;     //p指向下一个节点//下面是进行链表2的删除工作u = q;q = q->next;free(u); }else  //如果链表2当前节点指数小，把链表2的当前节点加入到链表1中{u = q->next;q->next = p;pre->next = q;pre = q;q = u; }}if(q)        //如果链表2比链表1长，需要把链表2多余的部分加入到结果链表中；
//如果链表1比链表2长则不需要任何操作。{pre->next = q; }free(pb);
}	int main()
{PNode head1 = (PNode)malloc(sizeof(struct tagNode));PNode head2 = (PNode)malloc(sizeof(struct tagNode));CreateList(head1);CreateList(head2);Add_Poly(head1,head2);printLinkedList(head1);return 0;
}

解法二：

本题主要思路:
1.建立两个头指针分别为head1和head2链表，链表每一个节点分别记录每一个多项式的系数coef和指数exp。
2.preA遍历链表head1，preB遍历链表head2。
3.建立一个只有一个头节点的链表head，逐步遍历链表head1和head2。分别有如下三种情况：
①preA->exp<preB->exp,将节点preA利用尾插法插入链表head。
②preB->exp<preA->exp,将节点preB利用尾插法插入链表head。
③preB->exp=preA->exp，这种情况分为两种：
当preA->coef+preB->coef=0时，释放节点preA和preB。
当preA->coef+preB->coef≠0时：将多项式指数相同的项的系数相加，记录在preA，并利用尾插法将preA节点插如链表head。
#include<stdio.h>
#include<stdlib.h>typedef int DataType; 
struct Node
{DataType	  dataX,dataY;  struct Node*  next;  
};
typedef struct Node  *PNode;     
typedef struct Node  *LinkList;  LinkList SetNullList_Link() 
{LinkList head = (LinkList)malloc(sizeof(struct Node));if (head != NULL)head->next = NULL;elseprintf("alloc failure");return head; 
}void CreateList(struct Node* head)
{PNode p = NULL; PNode q = head;int dataX,dataY;scanf("%d,%d", &dataX,&dataY);while (dataX != 0 || dataY != 0) {   p = (struct Node*)malloc(sizeof(struct Node));p->dataX = dataX;p->dataY = dataY;p->next = NULL;q->next = p;q = p;scanf("%d,%d", &dataX,&dataY);}
}PNode mergeNDeduplicateList(PNode POLYA, PNode POLYB)
{PNode A,B,pre;B = POLYB->next;while(B != NULL){pre = POLYA;A = pre->next;while(A != NULL){if(A->dataY == B->dataY){A->dataX = A->dataX + B->dataX;if(A->dataX == 0){pre->next = A->next;free(A);}POLYB->next = B->next;free(B);B = POLYB->next;break;}else if(A->dataY > B->dataY){POLYB->next = B->next;B->next = A;pre->next = B;B = POLYB->next;break;}pre = pre->next;A = pre->next;}}PNode StopNode;StopNode = POLYA;while(StopNode != NULL){pre = POLYA;A = pre->next;while(A->next != NULL){if(A->dataY > A->next->dataY){pre->next = A->next;PNode temp;temp = A->next;A->next = temp->next;temp->next = A;}pre = pre->next;A = pre->next;}StopNode = StopNode->next;}return POLYA;
}void print(LinkList head)    
{PNode p = head->next;while (p != NULL){printf("%d,%d ", p->dataX,p->dataY);p = p->next;}
}void DestoryList_Link(LinkList head)
{PNode  pre = head; PNode p = pre->next;while (p) {free(pre);pre = p;p = pre->next;}free(pre);
}int main()
{LinkList POLYA,POLYB;POLYA = SetNullList_Link();POLYB = SetNullList_Link();CreateList(POLYA);CreateList(POLYB);POLYA = mergeNDeduplicateList(POLYA,POLYB);print(POLYA);DestoryList_Link(POLYA);return 0;
}