线性表的合并+有序表的合并

mac2025-01-30  25

文章目录

1.顺序结构1.0结构体1.1初始化1.2取值1.3查找1.4插入1.5输出 2.链式结构(无头结点的单链表)2.0结构体2.1初始化2.2插入(递归)2.3查找 3.有序表

1.顺序结构

#include<stdio.h> #include<stdlib.h> #include<string> #include<iostream> using namespace std; #define MAXSIZE 100 typedef int ElemType; typedef struct{ ElemType *elem;//存储空间的基地址 int length;//多项式中当前项的个数 }SqList; //初始化 void InitList(SqList &L){ L.elem = new ElemType[MAXSIZE]; L.length = 0; return; } //取值 void GetElem(SqList L, int i, ElemType &e){ e = L.elem[i - 1];//elem[1-1]单元存储第i个数据元素 return; } //查找 bool LocateElem(SqList L, ElemType e){ for (int i = 0; i < L.length; i++) if (e == L.elem[i])return true; return false; } //插入 void InsertList(SqList &L, int i, ElemType e){ //超出表+1长(插入完表长会+1),存储空间满,曾出现过,都直接返回 if (i<1 || i>(L.length + 1) || (L.length == MAXSIZE)||LocateElem(L,e))return; for (int j = L.length - 1; j >= i - 1; j--)//从最后一项开始往后挪一位,直到第i个元素(第i-1项),给插入到第i个元素(第i-1项)腾位置 L.elem[j + 1] = L.elem[j]; L.elem[i - 1] = e;//插入 ++L.length;//表长+1 return; } //输出顺序表 void WatchList(SqList L){ if (L.length == 0){ printf("表空\n"); return; } printf("顺序表:"); for (int i = 0; i < L.length; i++) printf("%d ", L.elem[i]); printf("\n"); return; } int main(){ SqList A, B; InitList(A); InitList(B); int n, m, e; cout << "A:"; cin >> n; for (int i = 1; i <= n; i++){ cin >> e; InsertList(A, i, e); } cout << "B:"; cin >> m; for (int i = 1; i <= m; i++){ cin >> e; InsertList(B, i, e); } for (int i = A.length + 1, j = 1; i <= A.length + B.length&&j <= B.length; j++){ GetElem(B, j, e); if (LocateElem(A, e)) continue; InsertList(A, i, e); i++; } WatchList(A); system("PAUSE"); return 0; }

1.0结构体

#define MAXSIZE 100 typedef int ElemType; typedef struct{ ElemType *elem;//存储空间的基地址 int length;//多项式中当前项的个数 }SqList;

1.1初始化

void InitList(SqList &L){ L.elem = new ElemType[MAXSIZE]; L.length = 0; return; }

1.2取值

void GetElem(SqList L, int i, ElemType &e){ e = L.elem[i - 1];//elem[1-1]单元存储第i个数据元素 return; }

1.3查找

bool LocateElem(SqList L, ElemType e){ for (int i = 0; i < L.length; i++) if (e == L.elem[i])return true; return false; }

1.4插入

void InsertList(SqList &L, int i, ElemType e){ //超出表+1长(插入完表长会+1),存储空间满,曾出现过,都直接返回 if (i<1 || i>(L.length + 1) || (L.length == MAXSIZE)||LocateElem(L,e))return; for (int j = L.length - 1; j >= i - 1; j--)//从最后一项开始往后挪一位,直到第i个元素(第i-1项),给插入到第i个元素(第i-1项)腾位置 L.elem[j + 1] = L.elem[j]; L.elem[i - 1] = e;//插入 ++L.length;//表长+1 return; }

1.5输出

void WatchList(SqList L){ if (L.length == 0){ printf("表空\n"); return; } printf("顺序表:"); for (int i = 0; i < L.length; i++) printf("%d ", L.elem[i]); printf("\n"); return; }

2.链式结构(无头结点的单链表)

#include<stdio.h> #include<iostream> #include<stdlib.h> using namespace std; #define MAXSIZE 100 #define ERROR 9999999 typedef int ElemType;//数据域类型(一个类型或一个结构体) typedef struct LNode* LinkList; typedef struct LNode{ ElemType data;//数据域 LinkList next;//指针域 }LNode; //初始化 void InitList(LinkList &L){ L = new LNode; L->next = NULL; return; } //递归插入 void InsertList(LinkList &L, ElemType e){ if (!L){ InitList(L); L->data = e; } else if (L->data!=e) InsertList(L->next, e); return; } //查找 int LocateList(LinkList L, int i,int length){ if (i < 1 || i>length)return ERROR; else while (--i){ L = L->next; } return L->data; } int main(){ LinkList A=NULL, B=NULL; int n,m; ElemType e; cout << "A:"; cin >> n; while (n--){ cin >> e; InsertList(A, e); } cout << "B:"; cin >> n; m = n; while (n--){ cin >> e; InsertList(B, e); } for (int i = 1; i <= m; i++){ e = LocateList(B, i,m); if (e!=ERROR) InsertList(A, e); } printf("合并:"); while (A!=NULL){ printf("%d ", A->data); A = A->next; } system("PAUSE"); return 0; }

2.0结构体

#define MAXSIZE 100 #define ERROR 9999999 typedef int ElemType;//数据域类型(一个类型或一个结构体) typedef struct LNode* LinkList; typedef struct LNode{ ElemType data;//数据域 LinkList next;//指针域 }LNode;

2.1初始化

//初始化 void InitList(LinkList &L){ L = new LNode; L->next = NULL; return; }

2.2插入(递归)

void InsertList(LinkList &L, ElemType e){ if (!L){ InitList(L); L->data = e; } else if (L->data!=e) InsertList(L->next, e); return; }

2.3查找

int LocateList(LinkList L, int i,int length){ if (i < 1 || i>length)return ERROR; else while (--i){ L = L->next; } return L->data; }

3.有序表

1.可有相同元素,所以去掉插入和合并时查找相同元素若有则跳过的条件 2.有序 2.1顺序表加入快排 例如

bool comp(ElemType a,ElemType b){ return a < b; } sort(A.elem, A.elem+ A.length, comp);

2.2链表 在插入的时候有序插入,因为他不是顺序的结构,可以在插入的时候就比较大小,若不符合排序顺序则插入元素和当前元素的值(不是地址)互换再插入

最新回复(0)