單鏈表的合并

2019-11-14 08:54:06

字體：大中小

供稿：網(wǎng)友

代碼示例

/* function：單鏈表的合并 created by ： xilong date: 2017.2.5*/#include "iostream"using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0typedef int ElemType;typedef int Status;typedef struct Node // 定義結(jié)構(gòu)體{ ElemType data; struct Node *next;}Node;typedef struct Node* LinkList;/* 功能：初始化一個(gè)空鏈表*/LinkList LinkList_Init(){ LinkList head; head = (LinkList)malloc(sizeof(LinkList)); // 申請結(jié)點(diǎn) head->next = NULL; // 頭結(jié)點(diǎn)的next指向NULL return head;}/* 功能：尾插法創(chuàng)建單鏈表*/void LinkList_CreateFormTail(LinkList *head){ LinkList p, s; p = *head; int flag = 1; double number; while (flag) { cin >> number; if (number != -99999) { s = (LinkList)malloc(sizeof(LinkList)); s->data = number; p->next = s; p = s; } else { flag = 0; p->next = NULL; // 如果到末尾，將末尾結(jié)點(diǎn)的next指向NULL } }}/* 功能：計(jì)算鏈表長度*/Status LinkList_Length(LinkList *head){ LinkList p; p = *head; int count = 0; if (p == NULL) { cout << "空鏈表！" << endl; return ERROR; } while (p != NULL) { count++; p = p->next; } return count-1;}/* 功能：兩個(gè)鏈表合并*/LinkList LinkList_merge(LinkList *LA, LinkList *LB){ LinkList p1, p2; p1 = *LA; p2 = *LB; if (p1->next == NULL) // 如果第一個(gè)鏈表為空，就直接返回第二個(gè)鏈表的頭結(jié)點(diǎn) { return *LB; } if (p2->next == NULL) // 如果第二個(gè)鏈表為空，返回第一個(gè)鏈表頭結(jié)點(diǎn) { return *LA; } while (p1 && p1->next) // 如果第一個(gè)鏈表有元素，將其循環(huán)不斷指向下一個(gè)結(jié)點(diǎn)，直到最后一個(gè)結(jié)點(diǎn) { p1 = p1->next; } // 將第一個(gè)鏈表的最后一個(gè)結(jié)點(diǎn)的next連接到第二個(gè)鏈表頭結(jié)點(diǎn)的next，將兩個(gè)鏈表串成一個(gè)鏈表 p1->next = (*LB)->next; free(*LB); return *LA; // 返回第一個(gè)鏈表的頭結(jié)點(diǎn)}/* 功能：插入*/Status LinkList_Insert(LinkList *head, int i, ElemType e){ LinkList PRe, s; pre = *head; int k = 1; while (pre && k < i) { pre = pre->next; k++; } if (pre == NULL || k > i || i > LinkList_Length(head)) { cout << "插入位置錯(cuò)誤！" << endl; return ERROR; } s = (LinkList)malloc(sizeof(LinkList)); s->data = e; s->next = pre->next; pre->next = s; return OK;}/* 功能：打印單鏈表中所有數(shù)據(jù)*/Status LinkList_Print(LinkList *head){ LinkList p; p = (*head)->next; if (p == NULL) { printf("linklist is empty.../n"); return ERROR; } while (p != NULL) { printf("%3d", p->data); p = p->next; } printf("/n"); return OK;}void main(){ LinkList LA, LB, LAB; ElemType e; cout << "LA鏈表的初始化以及創(chuàng)建：（輸入-99999結(jié)束）" << endl; LA = LinkList_Init(); LinkList_CreateFormTail(&LA); cout << "打印LA鏈表數(shù)據(jù)："; LinkList_Print(&LA); int count = LinkList_Length(&LA); cout << "LA鏈表的長度為："; cout << count << endl; cout << "LB鏈表的初始化以及創(chuàng)建：（輸入-99999結(jié)束）" << endl; LB = LinkList_Init(); LinkList_CreateFormTail(&LB); cout << "打印LB鏈表數(shù)據(jù)："; LinkList_Print(&LB); LAB = LinkList_merge(&LA, &LB); cout << "打印合并后的鏈表："; LinkList_Print(&LAB); cout << "插入數(shù)據(jù),輸入插入位置："; int insert; cin >> insert; LinkList_Insert(&LAB, insert, 98); cout << "打印的鏈表："; LinkList_Print(&LAB); system("pause");}