代碼參考《妙趣橫生的算法.C語言實現》、《劍指OFFER 名企面試官精講典型編程題 第2版》等

---

前言

本章總結在看書過程中的一些關于順序表的算法題并可能含有一些自己的一些疑問。題目數量不定，隨閱歷增加而增加；

---

1、合并兩個順序表

題目要求：

有兩個順序存儲的線性表，分別存放了一些整數數據，每個順序表中存放的數據從小到大排列。寫一個程序，將兩個表合并，生成一個新的順序表，里面的順序仍然按照從小到大排列。
例如:
list1:1,2,4,8,10
list2:3,9,11
合并之后的list3:1,2,3,4,8,9,10,11

提示:應該使用動態創建這個順序表，這樣list3的長度才可以根據list1和list2的長度動態調整。
要實現兩個順序按值歸并，最終仍保持數據的從小到大遞增排序，可以設置兩個指針p1、p2分別指向兩個待合并的順序表list1和list2，設置指針p3指向新表list3用來向list3中存放數據，然后逐一比較p1和p2指向的內容 ，將其中較小的那個放到p3指向的list3的存儲單元，然后將較小的那個指針+1.使其指向表的下一個數據，同時p3也要自動+1。重復上述操作，直到list1,list2中某一個順序表的內容被全部歸并到list3中.最后再將未完全歸并的順序表中的后續內容整體移至list3中。
代碼：

#include <stdio.h>
#include <stdlib.h>
#include "malloc.h"
#include "conio.h"
typedef int ElemType;typedef struct {int* elem;int length;int listsize;
}Sqlist;//初始化順序表
void InitSqlist(Sqlist *L,int size)
{L->elem = (int*)malloc(sizeof(ElemType)*size);			//在堆內存上開辟空間,并將地址指針傳給elemif (!L->elem){printf("順序表內存開辟失敗");exit(0);}L->length = 0;								//最開始的表長0L->listsize = size;
}//向順序表中插入元素
//向順序表L第i個位置插入元素item
void InsertElem(Sqlist* L,int i, ElemType item)
{//追加內存后的新的基址、指向插入位置的指針、移動數據的指針中間變量ElemType* base, * insertPtr, * p;if (i<1 || i>L->length + 1)		{printf("非法插入");exit(0);}if (L->length >= L->listsize)		//順序表的空間不夠，追加內存{base = (ElemType*)realloc(L->elem, (L->listsize + 10) * sizeof(ElemType));		//將追加內容后的內存首地址傳給baseL->elem = base;L->listsize = L->listsize + 100;}insertPtr = &(L->elem[i-1]);		//指針指向插入位置for (p = &L->elem[L->length - 1];p >= insertPtr;p--){//移動順序表中數據*(p+1) = *p;}*insertPtr = item;				//插入數據元素L->length++;
}
//銷毀順序表
void DestroySqlist(Sqlist* list)
{int* p = list->elem;free(p);list->elem = NULL;list->length = 0;list->listsize = 0;
}
//兩個順序表內容的合并,返回一個新的list
Sqlist MergeList(Sqlist list1, Sqlist list2)
{//將list1和list2的內容合并到list3并返回int* p1, * p2, * p3, * p1_last, * p2_last;Sqlist list3;p1 = list1.elem;		//p1指向list1第一個元素p2 = list2.elem;		//p2指向list2第一個元素//初始化list3，其長度為list1 list2 長度之和InitSqlist(&list3,list1.length+list2.length);p3 = list3.elem;		//p3指向list3第一個元素p1_last = list1.length + list1.elem - 1;	//p1_last指向list1的表尾p2_last = list2.length + list2.elem - 1;	//p2_last指向list2的表尾//實現合并while (p1<=p1_last && p2<=p2_last)		//當list1與list2中有一個list被遍歷完{if (*p1 <= *p2)	//當p1指向的元素小于p2指向的元素{*p3 = *p1;p3++;p1++;}else{*p3 = *p2;p3++;p2++;}list3.length++;}//將list1或者list2中剩余元素并入list3中if (p1 <= p1_last)		//p1有剩余{while (p1 <= p1_last){*p3 = *p1;p3++;p1++;list3.length++;}}else{while (p2 <= p2_last){*p3 = *p2;p3++;p2++;list3.length++;}}//當搬移完成后，返回list3return list3;
}
//測試程序
int main()
{Sqlist list1, list2, list3;		//實例化3個順序表int n, i;					//存放list長度中間變量、累加器ElemType e;					//插入元素中間變量printf("請輸入list1的長度\n");scanf("%d",&n);InitSqlist(&list1,n);printf("請輸入list1的元素\n");for (i=1;i<=n;i++){scanf("%d",&e);InsertElem(&list1,i,e);}printf("請輸入list2的長度\n");scanf("%d", &n);InitSqlist(&list2, n);printf("請輸入list2的元素\n");for (i = 1;i <= n;i++){scanf("%d", &e);InsertElem(&list2, i, e);}list3 = MergeList(list1,list2);printf("輸出合并后的結果\n");for (i = 0;i < list3.length;i++){printf("%d ",list3.elem[i]);			//這里%d根據ElemType類型來進行修改}//銷毀list，釋放內存DestroySqlist(&list1);DestroySqlist(&list2);DestroySqlist(&list3);_getche();return 0;
}

效果：