C++实现线性表有序表的合并方式(顺序表实现and链表实现)
目录
- 一、顺序表实现
- 二、链表表实现
- 三、最终结果
- 总结
有序表的合并:
- 已知线性表La和LbgFLehvC中的元素按值非递减有序排列
- 现要求将La和Lb归并为一个新的线性表Lc
- 且Lc中的数据元素仍按值非递减有序排列
一、顺序表实现
#include<IOStream> using namespace std; #define MAXSIZE 100 //定义最大存储空间 //顺序表的定义 struct SqList { int* Elme; //动态数组 int Length; //元素个数 }; //初始化 bool initList_Sq(SqList&phpamp; L) { L.Elme = new int[MAXSIZE]; //为顺序表分配空间 if (!L.Elme) { exit(0); //分配失败退出系统 } L.Length = 0; //空表长度为0 return true; //分配成功返回1 } //插入 bool Listinsert_Sq(SqList& L, int i, int e) { if (i < 1 || i > L.Length + 1) //判断输入的i释放合法 { return false; } if (L.Length == MAXSIZE) //判断空间是否已满 { return false; } for (int j = L.Length - 1; j >= i - 1; j--) { L.Elme[j + 1] = L.Elme[j]; //将插入位置及之后的元素后移 } L.Elme[i - 1] = e; //将元素e放入位置i L.Length++; //表长加一 return true; } //遍历 void ListPrint_Sq(SqList L) { for (int j = 0; j < L.Length; j++) { cout << L.Elme[j] << " "; } cout << endl; } //线性表有序表的合并 void MergeList_Sq(SqList La, SqList Lb, SqList& Lc) { //指针pa,pb,pc的初值分别指向两个表的第一个元素 int* pa = La.Elme; int* pb = Lb.Elme; Lc.Length = La.Length + Lb.Length; //新表长度等于两表之和 Lc.Elme = new int[Lc.Length]; //为新表分配存储空间 int* pc = Lc.Elme; //pa_last、pb_last分别指向表中最后一个元素 int *pa_last = &La.Elme[La.Length - 1]; int* pb_last = &Lb.Elme[Lb.Length - 1]; //判断两表是否为空,或当其中一表摘取完,则停止循环 while (pa <= pa_last && pb <= pb_last) { if (*pa <= *pb) //依次摘取两表中值较小的结点 { *pc++ = *pa++; } else { *pc++ = *pb++; } } //如果条件为真,表明Lb表已经到达表尾,将La中剩余元素加入Lc while (pa <= pa_last) { *pc++ = *pa++; } //如果条件为真,表明La表已经到达表尾,将Lb中剩余元素加入Lc while (pb <= pb_last) { *pc++ = *pb++; } } int main() { SqList La; //创建线性表La initList_Sq(La); //初始化 //创建数组并把数组中元素插入到La中 int arr1[3] = { 1,7,8 }; for (int i = 1; i <= 3; i++) { Listinsert_Sq(La, i, arr1[i - 1]); } cout << "编程客栈合并前La中元素:" << endl; ListPrint_Sq(La); //遍历La SqList Lb;//创建线性表Lb initList_Sq(Lb); //初始化 //创建数组并把数组中元素插入到Lb中 int arr2[6] = { 2,4,6,8,10,11 }; for (int i = 1; i <= 6; i++) { Listinsert_Sq(Lb, i, arr2[i - 1]); } cout << "合并前Lb中元素:" << endl; ListPrint_Sq(Lb); //遍历La SqList Lc; MergeList_Sq(La, Lb, Lc); //合并La、Lb到Lc中 cout << "合并后Lc中元素:" << endl; ListPrint_Sq(Lc); //遍历Lc system("pause"); return 0; }
二、链表表实现
#include<iostream> using namespace std; //结点 struct Lnode { int Data; //数据域 Lnode* Next; //指针域 }; typedef Lnode* LinkList; //将LinkList定义为Lnode*类型 //初始化 void Listinit_L(LinkList& L) { L = new Lnode; L->Next = NULL; } //插入 bool Listinsert_L(LinkList& L, int i, int e) { Lnode* p = L; int j = 0; while (p && j < i - 1) //利用循环找到i-1的结点 { p = p->Next; 编程++j; } if (!(p) || j > i - 1)//判断输入的i是否合法 { return false; } else { Lnode* s = new Lnode; //创建新结点s s->Data = e; //将输入的元素e存入s的数据域 s->Next = p->Next; //s指向第i个结点 p->Next = s; //i-1结点指向s地址 return true; } } //打印 void ListPrint_L(LinkList L) { Lnode* p = L->Next; //p指向第一个元素 while (p) { cout << p->Data << " "; p = p->Next; } cout << endl; } //有序表的合并 void MergeList_L(LinkList La, LinkList Lb, LinkList& Lc) { Lnode* pa = La->Next;//pa指向La中第一个元素 Lnode* pb = Lb->Next;//pb指向Lb中第一个元素 Lnode* pc = Lc = La;//使用La的头结点作为Lc的头结点 while (pa && pb) //pa或pb为空时停止循环 { //判断pa的值是否小于等于pb的值,为真插入pa的值,不为真插入pb的值 if (pa->Data <= pb->Data) { pc->Next = pa; pc = pa; pa = pa->Next; } else { pc->编程;Next = pb; pc = pb; pb = pb->Next; } } pc->Next = pa ? pa : pb; //利用三目运算插入pa或pb中剩余内容 delete Lb; //释放Lb头结点 } int main() { //1.创建单链表La LinkList La; Listinit_L(La); //初始话 //将数组中的数据插入La int arr1[3] = { 1,7,8 }; for (int i = 1; i <= 3; i++) { Listinsert_L(La, i, arr1[i-1]); } cout << "合并前La中的数据为:" << endl; ListPrint_L(La); //2.创建单链表Lb LinkList Lb; Listinit_L(Lb); //初始话 //将数组中的数据插入Lb int arr2[6] = {2,4,6,8,10,11}; for (int i = 1; i <= 6; i++) { Listinsert_L(Lb, i, arr2[i - 1]); } cout << "合并前Lb中的数据为:" << endl; ListPrint_L(Lb); //3.创建Lc,将La与Lb中的值合并到Lc LinkList Lc; MergeList_L(La, Lb, Lc); cout << "合并后Lc的值为:" << endl; ListPrint_L(Lc); system("pause"); return 0; }
三、最终结果
总结
以上为个人经验,希望能给大家一个参考,也希望大家多多支持编程客栈(www.devze.com)。
精彩评论