#include<iostream> using namespace std; typedef struct node { int data; node* next; }*List; List listPoduce() { int a; List L; node * r, * new0;//创建指针 L = new node();//分配空间 r = L; cin >> a; while (a != -1) { new0 = new node(); new0->data = a; r->next = new0; r = new0; cin >> a; } r->next = NULL; return L; } //创建一个链表,将两个链表串起来 List CombList(node* L1, node* L2) { node* a, * b, * c; List L; L = new node(); a = L1->next; b = L2->next; c = L; while (a&& b) { if (a->data <= b->data) {//如果a小。则将a的数据落入c中 c->next = a; c = a; a = a->next; } else { c->next = b;//如果b小,同此 c = b; b = b->next; } } if (a)//直接链接a之后的结点 c->next = a; else if (b) c->next = b;//直接链接b之后的结点 return L; } //输出打印链表 void pintL(node* L) { node* p = L->next; if (p == NULL) { printf("NULL"); return; } while (p) { cout<<p->data; p = p->next; if (p) cout<<" "; } } int main() { node* s1, * s2, * s3; s1 = listPoduce();//创建s1 s2 = listPoduce();//创建s2 s3 = CombList(s1, s2);//计算 pintL(s3);//打印 return 0; }
#include<iostream> using namespace std; typedef struct node { int data; node* next; }*List; List listPoduce() { int a; node* L, * r, * new0;//创建指针 L = new node();//分配空间 r = L; cin >> a; while (a != -1) { new0 = new node(); new0->data = a; r->next = new0; r = new0; cin >> a; } r->next = NULL; return L; } void pintList(node* L) { node* p = L->next; if (p == NULL) { printf("NULL"); return; } while (p != NULL) { printf("%d", p->data); p = p->next; if (p != NULL) printf(" "); } } List jiaoji(List a, List b) { node* la = a->next; node* lb = b->next; List C = new node(); C->next = NULL; node* c = C; while (la&& lb) { if (la->data < lb->data) { la = la->next; } else if (la -> data > lb->data) { lb = lb->next; } else if (la->data == lb->data) { c->next = la; la = la->next; lb = lb->next; c = c->next; } } return C; } int main() { node* a, * b, * cc; a = listPoduce(); b = listPoduce(); cc = jiaoji(a, b); pintList(cc); }
#include<iostream> #include<malloc.h> using namespace std; typedef struct node { int coef;//系数 int exp;//指数 node* next;//在c++中支持node*这种写法 }list; node* newNode(int c, int e)//创建一个新结点 { node* temp = (node*)malloc(sizeof(node)); temp->coef = c;//系数 temp->exp = e;//指数 temp->next = NULL; return temp; } list* createPoly(int n)//创建长度为n的链表 { list* L = NULL;//创建一个指针表示链表 if (n == 0)//如果链表的长度为0,则直接返回 { return L; } else { L = (list*)malloc(sizeof(node));//如果链表的长度不是0,则分配空间 } int ac = 0;//初始化系数 int ae = 0;//初始化指数 node* lastp = L;//创建尾指针 node* temp = NULL;//创建一个指针用来接收新插入的结点 for (int i = 0; i < n; i++) { cin >> ac >> ae;//输入系数,指数 temp = newNode(ac,ae);//接收这个新的结点 lastp->next = temp;//尾插入新的结点 lastp = temp;//更新尾结点 } return L;//返回这条链表 } list* addPoly(list* A, list* B)//将两个多项式相加 { if (!A->next)return B; if (!B->next)return A; node* pa = A->next;//pa指向A的第一项 node* pb = B->next;//pb指向B的第一项 list* sum = (list*)malloc(sizeof(node));//创建一个计算总和的链表 sum->next = NULL;//初始化 node* lastp = sum;//尾结点 node* temp = NULL;//创建一个临时结点 while (pa && pb)//如果满足二者的长度在多项式内 { if (pa->exp == pb->exp)//并且这一项的指数相同 { if (pa->coef + pb->coef != 0)//并且相加还不等于0 { temp = newNode(pa->coef + pb->coef, pa->exp);//那么就得到这个系数相加后的结点 lastp->next = temp;//尾插入总和链表 lastp = temp; } pa = pa->next;//指针向后移动 pb = pb->next; } else if (pa->exp > pb->exp)//如果pa的指数比pb的指数大 { temp = newNode(pa->coef, pa->exp);//将pa落下来 lastp->next = temp;//尾插 lastp = temp; pa = pa->next;//移动 } else//如果pa的指数比pb小,同理 { temp = newNode(pb->coef, pb->exp); lastp->next = temp; lastp = temp; pb = pb->next; } } if (pa == NULL && pb != NULL)//如果pa指向空,将pb后面的全部落下来 { lastp->next = pb; } if (pb == NULL && pa != NULL)//同理 { lastp->next = pa; } return sum; } void printPoly(list*L)//打印链表 { if (!L->next)//如果链表为空,则直接打印0 0 { cout << "0 0"; } else//如果链表不为空 { node* p = L->next;//p指向第一个结点 int i = 0; while (p) { if (i == 0) { cout << p->coef << " " << p->exp; i++; } else { cout << " " << p->coef << " " << p->exp; } p = p->next; } } } int main() { int n, m; cin >> n; list* La = createPoly(n);//创建A链表 cin >> m; list* Lb = createPoly(m);//创建B链表 list* result = addPoly(La, Lb);//计算 printPoly(result);//打印 return 0; }
#include<iostream> using namespace std; typedef struct node { int data; node* next; }*list; list Createlist(int n){ list L; L = new node(); node* p = L; L->next = NULL; while (n--) { node* t = new node(); int x; cin >> x; t->data = x; p->next = t; p = t; } p->next = NULL; return L; } void Put(list L) { node* s = L->next; cout << s->data; s = s->next; while (s!=NULL) { cout << " " << s->data; s = s->next; } } list Insert(list L, int m) { node* p = L; while (p->next) { if (p->next->data == m) { return L; } if (p->next->data > m) { node* s = new node(); s->data = m; s->next = p->next; p->next = s; return L; } p = p->next; } if (p->data < m) { node* s = new node(); s->next = NULL; s->data = m; s->next = p->next; p->next = s; } return L; } int main() { int n; cin >> n; list L = Createlist(n); int m; cin >> m; Insert(L, m); Put(L); return 0; }
#include<iostream> using namespace std; const int N = 100000; int arr[N]; int main() { int aa, bb; int x, y; char cc; int tt = 0; cout << aa << bb; //输入人数和操作 for (int i = 1; i <= bb; i++) { getchar();//获得操作 cout << cc; if (cc == 'I')//排在队尾 { cout << x; arr[tt++] = x;//将x插入到队尾 } if (cc == 'C') { cout << x << y; for (int i = 0; i < tt; i++)//将x插入到y的前面 { if (arr[i] == y) { for (int j = tt; j > i; j--) { arr[j] = arr[j - 1];//往后移动 } arr[i] = x; break; } } tt = tt + 1; } if (cc == 'L') { cout << x; for (int i = 0; i < tt; i++) { if (arr[i] == x) { for (int j = i; j < tt - 1; j++) { arr[j] = arr[j + 1]; } break; } } tt--; } } if (tt == 0) { printf("Bai Ren Zhan"); } else { for (int i = 0; i < tt; i++) { printf("%d ", arr[i]); } } return 0; }
数据结构.pta测试二
2024-03-15 15:26:01 42 阅读