【数据结构】详细剖析线性表

//顺序表的静态创建
#define MaxSize 10//定义最大表长
typedef struct Sqlist {
	ElemType data[MaxSize];//存储数据元素的数组
	int length;//当前表长
}Sqlist;//重命名后的静态顺序表类型名
//顺序表的初始化
bool InitList(Sqlist* L){
	if (!L)
		return false;//指针L为空指针时返回false
	L->length = 0;//初始化当前表长
	return true;
}
//顺序表的按位查找
ElemType GetElem(Sqlist L, int i){
	if (i<1 || i>L.length)//位序小于1，或者位序大于当前表长时表示位序不合理
		return -1;//位序不合理，返回-1
	return L.data[i - 1];//位序合理，返回下标为i-1的元素的值
}
//顺序表的按值查找
int LocateElem(Sqlist L, ElemType e) {
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] == e)
			return i + 1;//找到对应的值返回位序i+1
	}
	return -1;//没有对应的值返回-1
}
//顺序表的插入
bool ListInsert(Sqlist* L, int i, ElemType e) {
	if (i<1 || i>L->length + 1)//位序小于1，或者位序大于当前表长+1时表示位序不合理
		return false;//位序不合理返回false
	if (L->length >= MaxSize)
		return false;//当前线性表已存满，返回false
	for (int j = L->length; j >= i; j--) {
		L->data[j] = L->data[j - 1];//元素往后移动
	}
	L->data[i - 1] = e;//将元素e插入位序i的位置
	L->length++;//当前表长+1
	return true;//插入成功返回true
}
//顺序表的删除
bool ListDelete(Sqlist* L, int i, ElemType e) {
	if (i<1 || i>L->length)//位序小于1，或者位序大于当前表长时位序不合理
		return false;//位序不合理返回false
	e = L->data[i - 1];
	for (int j = i - 1; j < L->length; j++) {
		L->data[j] = L->data[j + 1];//元素往前移
	}
	L->length--;//当前表长-1
	return true;//删除成功返回true
}

//无头结点单链表的基本操作
//单链表类型的声明
typedef struct LNode {
	ElemType data;//数据域
	struct LNode* next;//指针域
}LNode, * LinkList;//重命名后的结点类型与单链表类型名
//单链表的初始化
bool InistList(LinkList* L) {
	if (!L)
		return false;//L为空指针时返回false
	L= NULL;//头指针初始化为空指针
	return true;//初始化完返回true
}
//单链表的创建——头插法
LinkList List_HeadInsert(LinkList* L){
	if (!L)
		return NULL;//当L为空指针时返回NULL
	LNode* s = NULL;//指向表头结点的指针
	ElemType x = 0;//存放数据元素的变量
	……;//获取数据元素
	while (x != EOF)//为创建过程设置一个终点
	{
		//头插操作
		if (!(*L))//单链表为空表时
		{
			*L = (LNode*)calloc(1, sizeof(LNode));//创建表头结点
			assert(*L);//创建失败报错
			(*L)->data = x;//将数据元素放入数据域中
			(*L)->next = NULL;//表头结点指针域指向空指针
		}
		else {
			s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
			assert(s);//创建失败报错
			s->data = x;//数据元素存放进数据域中
			s->next = (*L)->next;//新结点指针域指向表头结点
			(*L)->next = s;//头指针指向新结点
		}
		……;//获取新的数据元素
	}
	return *L;//返回创建好的单链表
}
//单链表的创建——尾插法
LinkList List_TailInsert(LinkList* L) {
	if (!L)
		return NULL;//当L为空指针时返回NULL
	LNode* r = NULL;//指向表尾结点的指针
	LNode* s = NULL;//指向新结点的指针
	ElemType x = 0;//存放数据元素的变量
	……;//获取数据元素
	while (x != EOF)//为创建过程设置一个终点
	{
		//尾插操作
		if (!(*L))//单链表为空表时
		{
			*L = (LNode*)calloc(1, sizeof(LNode));//创建表头结点
			assert(*L);//创建失败报错
			(*L)->data = x;//将数据元素放入数据域中
			(*L)->next = NULL;//表头结点指针域指向空指针
			r = (*L);//表尾指针指向表头结点，此时的表头结点也是表尾结点
		}
		else {
			s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
			assert(s);//创建失败报错
			s->data = x;//数据元素存放进数据域中
			s->next = r->next;//新结点指针域指向表尾结点
			r->next = s;//表尾结点的指针域指向新结点
			r = s;//表尾指针指向新结点
		}
		……;//获取新的数据元素
	}
	return *L;//返回创建好的单链表
}
//单链表的按位查找
LNode* GetElem(LinkList L, int i) {
	if (!L)
		return NULL;//单链表为空表时返回NULL
	if (i < 1)
		return NULL;//位序不合理时返回NULL
	int j = 1;//单链表结点的位序
	LNode* s = L->next;//指向查找结点的指针
	while (j < i && s)//当位序相等时，结束查找；当s为空指针时，结束查找
	{
		s = s->next;//向后遍历
	}
	return s;//查找结束，返回当前结点
}
//单链表的按值查找
LNode* LocateElem(LinkList L, ElemType e) {
	if (!L)
		return NULL;//当表为空表时返回NULL
	LNode* s = L->next;//指向查找结点的指针
	while (s->data == e && s)//当元素相等时，结束查找，当s为空指针时，结束查找
	{
		s = s->next;//向后遍历
	}
	return s;//查找结束，返回当前结点
}
//单链表的前插操作——指定结点
bool InsertPriorNode(LNode* p, ElemType e) {
	if (!p)
		return false;//p为空指针，返回false
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
	assert(s);//创建失败，报错
	s->data = p->data;//p结点的数据元素放入新结点的数据域中
	p->data = e;//插入的数据元素放入p结点的数据域中
	s->next = p->next;//新结点的指针域指向p结点的后继结点
	p->next = s;//p结点的指针域指向新结点，完成插入操作
	return true;//插入成功，返回true
}
//单链表的前插操作——指定位序
bool InsertPriorNode(LinkList* L, int i, ElemType e) {
	if (!L)
		return false;//L为空指针时返回false
	if (!(*L))
		return false;//单链表为空表时返回false
	if (i < 1)
		return false;//位序不合理时，返回false
	LNode* p = GetElem(*L, i - 1);//指向前驱结点的指针
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
	assert(s);//创建失败，报错
	s->data = e;//数据元素放入新结点的数据域中
	s->next = p->next;//新结点的指针域指向p结点的后继结点
	p->next = s;//p结点的指针域指向新结点，完成插入操作
	return true;//插入成功，返回true
}
//单链表的后插操作——指定结点
bool InsertNextNode(LNode* p, ElemType e) {
	if (!p)
		return false;//p为空指针，返回false
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
	assert(s);//创建失败，报错
	s->data = e;//数据元素放入新结点的数据域中
	s->next = p->next;//新结点的指针域指向p结点的后继结点
	p->next = s;//p结点的指针域指向新结点，完成插入操作
	return true;//插入成功，返回true
}
//单链表的后插操作——指点位序
bool InsertNextNode(LinkList* L, int i, ElemType e) {
	if (!L)
		return false;//L为空指针时返回false
	if (!(*L))
		return false;//单链表为空表时返回false
	if (i < 1)
		return false;//位序不合理时，返回false
	LNode* p = GetElem(*L, i);//指向位序i结点的指针
	if (!p)
		return false;//结点p为空指针时，返回false
	LNode* s = (LNode*)calloc(1, sizeof(LNode));//创建新结点
	assert(s);//创建失败，报错
	s->data = e;//数据元素放入新结点的数据域中
	s->next = p->next;//新结点的指针域指向p结点的后继结点
	p->next = s;//p结点的指针域指向新结点，完成插入操作
	return true;//插入成功，返回true
}
//单链表的删除操作——指定位序
bool ListDelete(LinkList* L, int i, ElemType e) {
	if (!L)
		return false;//L为空指针时返回false
	if (!(*L))
		return false;//单链表为空表时返回false
	if (i < 1)
		return false;//位序不合理时返回false
	LNode* p = GetElem(*L, i - 1);//位序i的前驱结点
	if (!p)
		return false;//结点p为空指针时，返回false
	LNode* q = p->next;//需要删除的结点
	if (!q)
		return false;//结点q为空指针时，返回false
	e = q->data;//需要删除的元素存放在变量e中
	p->next = q->next;//前驱结点的指针域指向删除结点的后继结点
	free(q);//释放被删除的结点空间
	return true;//删除完成，返回true
}
//单链表的删除操作——指定结点
bool ListDelete(LinkList* L,LNode* p, ElemType e) {
	if (!L)
		return false;//L为空指针时返回false
	if (!(*L))
		return false;//单链表为空表时返回false
	if (!p)
		return false;//p为空指针时，返回false
	LNode* q = (*L)->next;//指向前驱结点的指针
	while (q->next != p)//判断q是否为p的前驱结点
	{
		q = q->next;//向后遍历
	}
	q->next = p->next;//前驱结点指向删除结点的后继结点
	free(p);//释放删除结点的空间
	return true;//删除完成，返回true
}