【資料結構與演演算法學習】線性表（順序表、單連結串列、雙向連結串列、迴圈連結串列）

#define LIST_INIT_SIZE 100  // 線性表儲存空間的初始分配量
typedef struct{
    ElemType elem[LIST_INIT_SIZE];
    int length;  // 當前長度
}SqList;

#include <stdlib.h>
#define MAXSIZE 1000    // 多項式可能達到的最大長度

typedef struct {        // 多項式非零項的定義
    float p;            // 係數
    int e;              // 指數 
}Polynomial;

typedef struct {
    Polynomial* data;   // 儲存空間的基地址
    int length;         // 多項式中當前項的個數  
}SqList;                // 多項式的順序儲存結構型別定義為SqList   

int main(int argc, char** argv) {
    SqList L;
    // 開闢指定長度的地址空間，並返回這段空間的首地址
    L.data = (Polynomial*)malloc(sizeof(Polynomial) * MAXSIZE);
    // 釋放申請的記憶體空間
    free(L.data);

    SqList L2;
    // 動態申請存放Polynomial型別物件的記憶體空間，成功則返回Polynomial型別的指標，指向新分配的記憶體
    L2.data = new Polynomial();
    // 釋放指標L2.data所指向的記憶體
    delete L2.data;

    return 0;
}

// 初始化順序表（構造一個空的順序表）
Status InitList_Sq(SqList& L) {
    L.elem = new ElemType[MAXSIZE]; // 為順序表分配儲存空間
    if (!L.elem) exit(OVERFLOW);    // 儲存分配失敗
    L.length = 0;                   // 空表長度為0
    return OK;
}

// 銷燬順序表
void DestroyList(SqList& L) {
    if(L.elem) delete L.elem;   // 釋放儲存空間
}

// 清空線性表
void ClearList(SqList& L) {
    L.length = 0;   // 將順序表的長度置0
}

// 求線性表的長度
int GetLength(SqList L) {
    return (L.length);
}

// 判斷順序表L是否為空
int IsEmpty(SqList L) {
    if (L.length == 0) return 1;
    else return 0;
}

// 順序表的取值（根據位置i獲取相應位置資料元素的內容）
int GetElem(SqList L, int i, ElemType& e) {
    if (i<1 || i>L.length) return 0;
    e = L.elem[i - 1];  // 第i-1個單元儲存著第i個資料
    return 1;
}

// 順序表的查詢
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == e)
            return i + 1;
    }
    return 0;
}

// 順序表的插入（在順序表L的第i個位置插入元素e）
int ListInsert(SqList& L, int i, ElemType e) {
    L.length += 1;
    if (i <= 0 || i > L.length + 1) return 0;   // 判斷i值是否合法
    if (L.length == MAXSIZE) return 0;          // 判斷當前儲存空間是否已滿
    for (int k = L.length - 1; k >= i - 1; k--)
        L.elem[k + 1] = L.elem[k];              // 插入位置及之後的元素後移
    L.elem[i-1] = e;
    L.length ++;
    return 1;
}

// 順序表的刪除（刪除順序表L第i個位置的元素e）
int ListDelete(SqList& L, int i, ElemType& e) {
    if (i < 1 || i > L.length) return 0;    // 判斷i值是否合法(1<=i<=L.length)
    for (int k = i; k < L.length - 1; k++)
        L.elem[k - 1] = L.elem[k];          // 被刪除之後的元素前移
    L.length--;
    return 1;
}

typedef char ElemType;
typedef struct Lnode {		// 宣告結點的資料型別和指向結點的指標型別
	ElemType data;			// 結點的資料域
	struct Lnode* next;		// 結點的指標域
}Lnode, *LinkList;			// LinkList為指向結構體Lnode的指標型別

// 單連結串列的初始化（帶頭結點）
int InitList(LinkList& L) {
	L = new LNode;  // 或L = (LinkList)malloc(sizeof(LNode));
	L->next= NULL;
	return 1;	
}

int ListEmpty(LinkList L) {
	if (L->next)
		return 0;
	else
		return 1;
}

// 單連結串列的銷燬
int DestroyList_L(LinkList& L) {
	Lnode* p;
	while (L) {
		p = L;
		L = (LinkList)L->next;
		delete p;
	}
	return 1;
}

// 清空單連結串列
int ClearList(LinkList& L) {
	Lnode *p, *q;
	p = (Lnode*)L->next;
	while (L) {
		q = (Lnode*)p->next;
		delete p;
		p = q;
	}
	L->next = nullptr;
}　

// 求單連結串列的表長
int ListLength(LinkList L) {
	Lnode* p;
	int len;
	p = (Lnode*)L->next;	// p指向第一個結點（首元結點）
	while (p) {
		len++;
		p = (Lnode*)p->next;
	}
	return len;
}

// 取值：取單連結串列中第i個元素的內容,通過變數e返回
int GetElem(LinkList L, int i, ElemType& e)
{
	Lnode* p;
	p = (Lnode*)L->next;
	int j = 1;
	while (p && j < i) {	// 向後掃描，直到p指向第i個元素或p為空
		p = (Lnode*)p->next;
		j++;
	}
	// 第i個元素不存在，分三種情況：i<1，i超過表長，L為空表）
	if (!p || i < 1) return 0;
	e = p->data;
	return 1;
}

// 按值查詢—根據指定資料獲取該資料所在的位置（地址）
Lnode* LocateElemAddress(LinkList L, ElemType e) {
	Lnode* p = (Lnode*)L->next;
	while (p && p->data != e)
		p = (Lnode*)p->next;
	// if (!p) return nullptr;  // 空表或未查詢到返回NULL
	return p;
}

// 按值查詢—根據指定資料獲取該資料的位置序號
int LocateElemIndex(LinkList L, ElemType e) {
	Lnode* p = (Lnode*)L->next;
	int j = 1;
	while (p && p->data != e) {
		p = (Lnode*)p->next;
		j++;
	}	
	if (!p) return 0;	// 空表或未查詢到返回0
	return j;
}

// 在單連結串列L中第i個元素之前插入資料元素e
int ListInsert(LinkList& L, int i, ElemType e) {
	// 先找到第i-1個元素的位置
	Lnode* p = L;
	int j = 0;
	while (p && j < i - 1) {
		p = (Lnode*)p->next;
		j++;
	}
	if (!p || i < 1) return 0;	// i<1或i超過表長+1，插入位置非法
	
	// 將結點s插入L中
	LinkList s = new Lnode;		// 生成新結點s
	s->data = e;				// 結點s的資料域置為e
	s->next = p->next;			// 新結點s指標域指向第i個結點
	p->next = s;				// 第i-1個結點的指標域指向新結點s
	return 1;
}

// 刪除單連結串列L中第i個資料元素（結點）
int ListDelete(LinkList& L, int i, ElemType& e) {
	// 先找到第i-1個元素的位置
	Lnode* p = L;
	int j = 0;
	while (p && j < i - 1) {
		p = (Lnode*)p->next;
		j++;
	}
	if (!p || i < 1) return 0;	// i<1或i超過表長，刪除位置非法

	// 刪除第i個結點
	Lnode* q = (Lnode*)p->next;	// 臨時儲存被刪結點的地址以備釋放
	p->next = q->next;			// 改變刪除結點前驅結點的指標域
	e = q->data;				// 儲存刪除結點的資料域
	delete q;					// 釋放刪除結點的空間
	return 1;
}

// 建立單連結串列：頭插法
void CreateList(LinkList& L, int n) {
	L = new Lnode;
	L->next = nullptr;

	for (int i = n; i > 0; i--) {
		Lnode* p = new Lnode;	// 輸入新結點 p = (Lnode*)malloc(sizeof(Lnode));
		std::cin >> p->data;	// 輸入元素值 scanf(&p->data);
			
		p ->next = L->next;		// 插入到表頭
		L->next = p;			// 不能將Lnode*型別的值分配到Lnode型別的實體
	}
}

// 建立單連結串列：尾插法
void CreateList_R(LinkList& L, int n) {
	L = new Lnode;
	L->next = nullptr;
	Lnode* r = L;	// 尾指標r指向頭結點

	for (int i = 0; i < n; i++) {
		Lnode* p = new Lnode;	// 輸入新結點
		std::cin >> p->data;	// 輸入元素值
		p->next = nullptr;		// 指標域置空

		r->next = p;			// 插入到表尾
		r = p;					// r指向新的尾結點
	}
}

// 雙向連結串列結點結構定義
typedef struct DuLnode {
	ElemType data;
	struct DuLnode* prior, * next;
}DuLnode, *DuLinkList;　

// 雙向連結串列的插入
int ListInsert_Dbl(DblLinkList& L, int i, ElemType e) {
	// 先找到第i個元素的位置
	DblLnode* p = L->next;
	int j = 1;
	while (p != L && j < i) {
		p = (DblLnode*)p->next;
		j++;
	}
	if (p == L || i < 1) return 0;	// i<1或i超過表長+1，插入位置非法

	// 插入新結點
	DblLnode* s = new DblLnode;
	s->data = e;
	s->prior = p->prior;	// ①
	p->prior->next = s;		// ②
	s->next = p;			// ③
	p->prior = s;			// ④
	return 1;
}

// 雙向連結串列刪除結點
int ListDelete_Dbl(DblLinkList& L, int i, ElemType e) {
	// 先找到第i個元素的位置
	DblLnode* p = L->next;
	int j = 1;
	while (p!=L && j < i) {
		p = (DblLnode*)p->next;
		j++;
	}
	if (p==L || i < 1) return 0;	// i<1或i超過表長，刪除位置非法

	// 刪除新結點
	p->prior->next = p->next;	// ①
	p->next->prior = p->prior;	// ②
	return 1;
}

// 帶尾指標迴圈連結串列的合併
LinkList Connect(LinkList Ta, LinkList Tb) {
	Lnode* p;
	p = (Lnode*)Ta->next;			// p存表頭結點
	Ta->next = Tb->next->next;		// Tb表頭連線到Ta表尾
	delete Tb->next;				// 釋放Tb表頭結點
	Tb->next = p;					// Tb表尾指向Ta頭結點
	return Tb;
}　

// 有序表合併：用順序表實現
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc) {
	ElemType* pa = La.elem;
	ElemType* pb = Lb.elem;							// 指標pa和pb的初值分別指向兩個表的第一個元素
	Lc.length = La.length + Lb.length;				// 新表長為待合併兩表的長度之和
	Lc.elem = new ElemType[Lc.length];				// 為合併後的新表分配一個陣列空間
	ElemType* pc = Lc.elem;							// 指標pc指向新表的第一個元素
	ElemType* pa_last = La.elem + La.length - 1;	// 指標pa_last指向La表的最後一個元素
	ElemType* pb_last = Lb.elem + Lb.length - 1;	// 指標pb_last指向Lb表的最後一個元素

	while (pa <= pa_last && pb <= pb_last) {
		if (*pa < *pb) *pc++ = *pa++;				// 依次「摘取」兩表中較小的結點加入Lc
		else *pc++ = *pb++;
	}
	while (pa <= pa_last) *pc++ = *pa++;			// Lb表已到達表尾，將La中剩餘元素加入Lc
	while (pb <= pb_last) *pc++ = *pb++;			// La表已到達表尾，將Lb中剩餘元素加入Lc
}

// 有序表合併：用連結串列實現
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc) {
	Lnode* pa = (Lnode*)La->next;
	Lnode* pb = (Lnode*)Lb->next;
	Lnode* pc = Lc = La;			// 用La的頭結點作為Lc的頭結點

	while (pa && pb) {
		if (pa->data <= pb->data) {
			pc->next = pa;
			pc = pa;
			pa = (Lnode*)pa->next;
		}
		else {
			pc->next = pb;
			pc = pb;
			pb = (Lnode*)pb->next;
		}
	}
	pc->next = pa ? pa : pb;		// 插入剩餘段
	delete Lb;						// 釋放Lb的頭結點
}