现在网站建站的主流语言是什么,智威汤逊广告公司,网络推广培训中心,网站设计的概述6-1 链表的插入算法
本题要求实现一个插入函数#xff0c;实现在链表llist中的元素x之后插入一个元素y的操作。
函数接口定义#xff1a;
int InsertPost_link(LinkList llist, DataType x, DataType y); 其中 llist是操作的链表#xff0c;x是待插入元素y的前驱节点元素…
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 mllist-next;LinkList n;while(m-data!x){mm-next;if(mNULL){printf (not exist data %d\n,x);return 0;}}n(LinkList) malloc (sizeof(struct Node));if (n!NULL){n-datay;n-nextm-next;m-nextn;return 0;}
}
6-2 链表的删除算法
本题要求实现一个函数实现删除链表llist中的指定元素deldata。
函数接口定义
void DelNode_Link(head, deldata);
其中head是操作的链表表头结点deldata是待删除的元素。
1.创建结构体和宏定义类型名
#includestdio.h
#includestdlib.htypedef 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-nextNULL;return head;}elseprintf(alloc failure);return head;
}3.利用尾插法创建单向链表。
void CreatList(struct Node* head)
{int data;LinkList phead-next,prehead;scanf(%d,data);while(data!-1){p(struct Node*)malloc(sizeof(struct Node));p-datadata;p-nextNULL;pre-nextp;prep;scanf(%d,data);}
}
4.删除值为x的节点。
void DelNode_Link(LinkList head, DataType x)
{LinkList phead-next;LinkList beforephead; //通过beforep和p遍历整个链表while(p!NULL){if(p-datax){beforep-nextp-next;free(p);//释放节点p,否则占用内存空间break;}else{beforepp;pp-next;if(pNULL)printf(not exist %d\n,x);}}
}5.打印整个链表。
void print(LinkList head)
{LinkList phead-next;while (p!NULL){printf(%d ,p-data);pp-next;}
}6.主函数
int main()
{ int x;LinkList head;headSetNullList_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 prehead;
LinkList rhead;LinkList qpre-next;while(q!NULL){ if(pre-dataq-data){ preq;}qq-next;}while(r-next!pre)rr-next; //指针r指向最大元素的上一个元素便于进行删除操作qhead;while(q-next!NULL)qq-next; //使q重新指向链表中的最后一个元素便于进行插入操作if(pre-nextNULL)return; //若最后一个元素为最大元素则直接返回不需要进行其他操作else{ r-nextpre-next;pre-nextNULL;q-nextpre;}
}6-4 合并两个递增有序的单循环链表
本题要求实现一个合并函数实现对有序单循环链表tail1和tail2的合并要求合并时实现去重操作即合并后的链表中没有重复的元素并且合并后的链表为递增有序链表。
函数接口定义
PNode mergeNDeduplicateList(PNode tail1, PNode tail2)
其中tail1是待合并的第一个有序单循环链表采用的尾指针表示方法tail2是待合并的第二个有序单循环链表采用的尾指针表示方法
解法一
1.创建结构体和宏定义类型名。
#includestdio.h
#includestdlib.htypedef 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 currentNULL, 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 headtail1-next-next; //head为tail1的首元节点tail1-next-next tail2-next-next; //将tail1的尾结点与tail2的首元节点相连接tail2-next-nextNULL; //将tail2尾结点的指针域置空//通过指针pre和p的移动对链表进行冒泡排序从小到大。prehead; //pre指向首元节点qhead-next;for(prehead; pre-next!NULL; prepre-next)for(qpre-next; q!NULL; qq-next){if(pre-dataq-data){temppre-data;pre-dataq-data;q-datatemp;}}//对链表进行去重操作代码如下prehead;qpre-next;while(q!NULL){if(pre-dataq-data) //两个结点中的数据元素相等{ if(q tail2-next) //当最后两个元素相等时需要做特殊处理{tail2-nextpre; //因为q-nextNULL,当执行pre-nextq-next时会导致pre-nextNULLpre-nextNULL; //即tail2节点会丢失不便于等会链表首尾结合和返回tail2指针} else //相等的不是最后两个结点{pre-nextq-next; //删除后一个结点free(q);qpre-next;}}else //两个结点中的值不相等则后移继续对比{preq;qq-next;}}tail2-next-nexthead; //对链表进行首尾接合,并使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;
}
解法二 #includestdio.h
#includestdlib.htypedef 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 currentNULL, 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 headtail-next, prehead-next, qpre-next;free(head); //释放原链表的头指针因为头指针无数据LinkList head1(LinkList)malloc(sizeof(struct Node));PNode pre1head1; //pre1指针随着新插入的节点移动便于进行尾插法LinkList head2(LinkList)malloc(sizeof(struct Node));PNode pre2head2; //pre2指针随着新插入的节点移动便于进行尾插法while(q!head-next) //原链表是循环链表当q遍历到原来pre的位置首元节点时遍历结束{if (pre-data%20) //判断元素是否为偶数{pre-nextpre1-next;pre1-nextpre;pre1pre1-next;}else //若不是偶数则为奇数{pre-nextpre2-next;pre2-nextpre;pre2pre2-next;}preq;qq-next; //pre始终保持在q的前面}
//将head1链表和head2链表合成一个新的单循坏链表head1head1-next; //head1链表在后不需要其头结点pre2-nexthead1; //两个链表相连接pre1-nexthead2; //形成循坏return pre1; //返回新循坏链表的尾指针
}
解法二
该程序的主要思想在于
1、遍历栈找到偶数
2、利用尾插法将偶数插入队尾 #includestdio.h
#includestdlib.htypedef 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 结束第一个多项式的输入。
输出格式:
对每一组输入在一行中输出POLYAPOLYB和多项式的系数和指数。
输入样例:
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遍历链表head1preB遍历链表head2。
3.建立一个只有一个头节点的链表head逐步遍历链表head1和head2。分别有如下三种情况
①preA-exppreB-exp,将节点preA利用尾插法插入链表head。
②preB-exppreA-exp,将节点preB利用尾插法插入链表head。
③preB-exppreA-exp这种情况分为两种
当preA-coefpreB-coef0时释放节点preA和preB。
当preA-coefpreB-coef≠0时将多项式指数相同的项的系数相加记录在preA并利用尾插法将preA节点插如链表head。
#includestdio.h
#includestdlib.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-exppnode-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); }ppre-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遍历链表head1preB遍历链表head2。
3.建立一个只有一个头节点的链表head逐步遍历链表head1和head2。分别有如下三种情况
①preA-exppreB-exp,将节点preA利用尾插法插入链表head。
②preB-exppreA-exp,将节点preB利用尾插法插入链表head。
③preB-exppreA-exp这种情况分为两种
当preA-coefpreB-coef0时释放节点preA和preB。
当preA-coefpreB-coef≠0时将多项式指数相同的项的系数相加记录在preA并利用尾插法将preA节点插如链表head。
#includestdio.h
#includestdlib.htypedef 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;
}
