【数据结构与算法学习】线性表（顺序表、单链表、双向链表、循环链表）

#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的头结点
}