线性表的应用:一元多项式加法、两集合差、单链表的插入 |
您所在的位置:网站首页 › 一元多项式相加的算法有哪些例题 › 线性表的应用:一元多项式加法、两集合差、单链表的插入 |
1.用带头结点的单链表表示集合,求两个集合的差
用带头结点的单链表表示集合,求A,B两个集合的差,C=A-B,C为所有属于A集合而不属于B集合,C中元素的顺序按A中元素原有的顺序存放 。完善void difference(LinkList A,LinkList B,LinkList C)函数。 输入样例:6 1 2 3 4 5 6 3 1 3 5 输出:2 4 6 #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。 typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型 typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList; void CreateList(LinkList &L,int n) //用正位序(后插法)输入n个元素的值,建立带头结点的单链线性表L。 { LinkList p,r; int i; L=new LNode; L->next=NULL; r=L; for(i=1;i>p->data; p->next=NULL; r->next=p; r=p; } } void ListPrint(LinkList L)//打印整张表 { LinkList p; p=L->next; if (p==NULL) { coutdata; D->next=NULL; t->next=D; t=D; } p=p->next; } } int main() { LinkList A,B,C; int n; scanf("%d",&n); CreateList(A,n);//生成有n个元素的A链表 scanf("%d",&n); CreateList(B,n);//生成有n个元素的B链表 CreateList(C,0);//生成只有头结点的C链表 difference(A,B,C); ListPrint(C);//打印整张表 return 0; } 2.有序带头结点单链表插入向带头结点有序单链表(结点从小到大),插入一个元素x的结点,使之仍有序,有带头结点有序单链表(从小到大),向该单链表中插入一个元素x的结点,使插入后该链表仍然有序。注意:链表已经有序,无需在本函数中考虑排序问题。 输入样例:6 1 2 3 4 5 6 4 输出:1 2 3 4 4 5 6 #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; //Status 是函数返回值类型,其值是函数结果状态代码。 typedef int ElemType; //ElemType 为可定义的数据类型,此设为int类型 typedef struct LNode { ElemType data; struct LNode* next; }LNode, * LinkList; void CreateList(LinkList& L, int n) //用正位序(后插法)输入n个元素的值,建立带头结点的单链线性表L。 { LinkList p, r; int i; L = new LNode; L->next = NULL; r = L; for (i = 1; i > p->data; p->next = NULL; r->next = p; r = p; } } void ListPrint(LinkList L)//打印整张表 { LinkList p; p = L->next; if (p == NULL) { cout next = NULL; while (p != NULL && p->data < e) { C = p; p = p->next; } D->next = p; C->next = D; } int main() { LinkList L; int n; ElemType e; scanf("%d", &n); CreateList(L, n);//生成n个元素的单链表,输入时保证链表有序 scanf("%d", &e); Insert(L, e); ListPrint(L); return 0; } 3.一元多项式加法将两个一元n次多项式相加,并输出相加后的新的一元n次多项式。 从输入数据读入一元多项式的系数和指数,用尾插法建立一元多项式的链表。 并约定建立多项式链表时,总是按指数从小到大的顺序排列 输入样例: 4 7 0 3 1 9 8 5 17 3 8 1 22 7 -9 8 输出: 7 0 11 1 22 7 5 17 #include using namespace std; typedef int Status; typedef int ElemType; typedef struct LNode { ElemType coef;//系数 ElemType expn;//指数 struct LNode* next; }LNode, * LinkList; void CreateList(LinkList& L, int n) { LNode* p; LNode* r; L = new LNode; L->next = NULL; r = L; for (int i = 0; i < n; i++) { p = new LNode; cin >> p->coef >> p->expn; p->next = NULL; LNode* q = L; while (q->next && q->next->expn expn) { q = q->next; } p->next = q->next; q->next = p; } } void caozuo(LinkList La, LinkList Lb, LinkList& Lc) { LNode* pa = La->next; LNode* pb = Lb->next; LNode* pc; Lc = new LNode; Lc->next = NULL; pc = Lc; while (pa && pb) { if (pa->expn < pb->expn) { pc->next = pa; pc = pa; pa = pa->next; } else if (pa->expn > pb->expn) { pc->next = pb; pc = pb; pb = pb->next; } else { ElemType sum = pa->coef + pb->coef; if (sum != 0) { pa->coef = sum; pc->next = pa; pc = pa; pa = pa->next; LNode* temp = pb; pb = pb->next; } else { LNode* temp = pa; pa = pa->next; temp = pb; pb = pb->next; } } } if (pa) pc->next = pa; else pc->next = pb; } void printLian(LinkList L) { LNode* p = L->next; if (p == NULL) { cout n; CreateList(Lb, n); caozuo(La, Lb, Lc); printLian(Lc); return 0; } |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |