[数据结构与算法]数据结构(C语言版)——第二章线性表

Introduction

这个是关于线性表的顺序表以及线性表的链式表的代码，其中包括增删查改，查找线性表的前驱和后继的功能，并对代码做了一定的注释(PS:小白一个，想做个blog来记录自己学习数据结构的过程)

状态文件声明

头文件

//Status.h
#include<iostream>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
using namespace std;
typedef int Status;

顺序表

头文件

//Mylist.h
#include<iostream>
#include"Status.h"
#define LIST_INIT_SIZE 100  //线性表存储空间的初始分配量
#define LISTINCREMENT 10  //线性表存储空间的分配增量
using namespace std;
typedef int ElemType;
typedef struct
{
	ElemType* elem;//存储空间基址
	int length, listsize;//length:当前长度 listsize:当前分配的存储容量(以sizeof(ElemType)为单位)
}SqList;

Status InitList_Sq(SqList& L)//构造一个空的线性表L
{
	L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
	if (!L.elem)
	{
		cout << "分配存储空间失败" << endl;
		exit(OVERFLOW);//存储分配失败退出函数
	}
	L.length = 0;
	L.listsize = LIST_INIT_SIZE;
	return 1;
}

Status ListInsert_Sq(SqList& L, int i, ElemType e)//插入元素
{
	ElemType* newbase, * q, * p;
	if (i < 0 || i > L.length + 1)//判断i值是否合法
	{
		cout << "insert failure" << endl;
		return ERROR;
	}
	if (L.length >= L.listsize)//判断存储空间是否满了，满了增加分配
	{
		newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
		if (!newbase)
		{
			cout << "分配存储空间失败" << endl;
			exit(OVERFLOW);
		}
		L.elem = newbase;
		L.listsize += LISTINCREMENT;//增加存储容量
	}
	q = &(L.elem[i]);//q为插入位置
	for (p = &(L.elem[L.length - 1]); p >= q; --p)
	{
		*(p + 1) = *p;//插入位置之后的元素右移
	}
	*q = e;//插入e
	L.length++;//表长增加1
	cout << "insert successfully" << endl;
	return OK;
}

Status ListDelete_Sq(SqList& L, int i, ElemType& e)//在顺序表中删除第i个元素，并返回删除的元素位置的值
{
	ElemType* p, * q;
	if ((i < 0) || (i > L.length))//判断i值是否合法
	{
		cout << "delete failure" << endl;
		return ERROR;
	}
	p = &(L.elem[i - 1]);//记录删除的位置
	e = *p;//将删除的元素赋值给e
	q = L.elem + L.length - 1;//表尾元素的位置
	for (++p; p <= q; ++p)
	{
		*(p - 1) = *p;//被删除元素之后的元素左移
	}
	L.length--;//数组长度减一
	cout << "delete successfully" << endl;
	return OK;
}

void ClearList_Sq(SqList& L)//将表的长度变为0
{
	L.length = 0;
}

void DestroyList_Sq(SqList& L)//销毁表
{
	L.elem = NULL;
	L.length = 0;
	L.listsize = 0;
}

Status GetElem(SqList L, int i, ElemType& e)//查找元素所在的位置
{
	ElemType* p;
	if ((i < 0) || (i > L.length))
	{
		cout << "search failure" << endl;
		return ERROR;
	}
	else
	{
		p = &(L.elem[i - 1]);
		e = *p;
	}
	cout << "search successfully" << endl;
	return OK;
}

void ListEmpty(SqList L)//判断表是否为空
{
	if (L.length == 0)
	{
		cout << "this list is empty" << endl;
	}
	else
	{
		cout << "this list not empty" << endl;
	}
}

Status ListLength(SqList L)//返回线性表长度
{
	return L.length;
}

Status PriorElem_Sq(SqList L, ElemType cur_elem, ElemType& pre_elem)//前驱
{
	ElemType* p;
	int i = 1;
	if (L.elem[0] == cur_elem)
	{
		cout << "this elem " << cur_elem << "is the first elem in the list" << endl;
		return ERROR;
	}
	else
	{
		while (i < L.length && L.elem[i] != cur_elem)
		{
			i++;
		}
		if (i < L.length)
		{
			p = &L.elem[i - 1];
			pre_elem = *p;
		}
		return OK;
	}
}

Status NextElem_Sq(SqList L, ElemType cur_elem, ElemType& next_elem)//查找元素的后继
{
	ElemType* p;
	int i = 0;
	if (L.elem[L.length - 1] == cur_elem)
	{
		cout << "the elem " << cur_elem << " is the last elem in the list" << endl;
		exit(OVERFLOW);
	}
	else
	{
		while (i < L.length && L.elem[i] != cur_elem)
		{
			i++;
		}
		if (i < L.length - 1)
		{
			p = &L.elem[i + 1];
			next_elem = *p;
		}
		return OK;
	}
}

Status CompareElem_Sq(SqList L, ElemType e)//找出在list中第一个比e大的元素的位置
{
	int i;
	for (i = 0; i < L.length;i++)
	{
		if (L.elem[i] > e)
			return i;
	}
}

Status LocalElem(SqList L, ElemType e, bool& result)
{
	int i = 0;
	int L_length = ListLength(L);
	while (i < L_length)
	{
		if (L.elem[i] != e)
		{
			i++;
			result = TRUE;
			return OK;
		}
		else
		{
			result = FALSE;
			return ERROR;
		}
	}
}

测试程序文件

//线性表顺序表.cpp
#include<iostream>
#include<stdlib.h>
#include"Status.h"
#include"Mylist.h"

void main()
{
	//这里是测试顺序表的功能
	SqList Mylist;
	int MyList_length, delete_Elem, delete_Elem_index, search_Elem_index, search_Elem, prior_index, prior_Elem, next_index, next_Elem;
	int a = 1;
	InitList_Sq(Mylist);
	cout << "former list's length:" << Mylist.length << endl;//原来数组的长度
	cout << "please enter list's length:";
	cin >> MyList_length;
	for (int i = 0; i < MyList_length; i++)//插入元素过程
	{
		int elem;
		cout << "insert " << a << " elem:";
		cin >> elem;
		ListInsert_Sq(Mylist, i, elem);
		a = a + 1;
	}
	cout << "lastest list's length:" << Mylist.length << endl;//插入元素后数组的长度
	cout << "please enter the delete the localcation of elem:";
	cin >> delete_Elem_index;
	ListDelete_Sq(Mylist, delete_Elem_index, delete_Elem);
	cout << "delete the " << delete_Elem_index << " elem:" << delete_Elem << endl;
	cout << "please enter the search the index number:";
	cin >> search_Elem_index;
	GetElem(Mylist, search_Elem_index, search_Elem);
	cout << "the search inde " << search_Elem_index << " elem:" << search_Elem << endl;
	cout << "please enter the elem to find it prior point:";
	cin >> prior_index;
	PriorElem_Sq(Mylist, prior_index, prior_Elem);
	cout << "the elem " << prior_index << " the prior is " << prior_Elem << endl;
	cout << "please enter the elem to find it next point:";
	cin >> next_index;
	NextElem_Sq(Mylist, next_index, next_Elem);
	cout << "the elem " << next_index << " the next is " << next_Elem << endl;
	int test = CompareElem_Sq(Mylist, 3) + 1;//索引的bug
	int a1;
	GetElem(Mylist, test, a1);
	cout << "position:" << test << " " << "elem:" << a1 << endl;

	//下面是测试两个顺序表合并
	SqList A, B;
	int B_length, A_length, e;
	int a = 1;
	InitList_Sq(A);
	InitList_Sq(B);
	cout << "former A list's length:" << A.length << endl;//原来数组的长度
	cout << "former B list's length:" << B.length << endl;//原来数组的长度
	cout << "please enter A list's length:";
	cin >> A_length;
	for (int i = 0; i < A_length; i++)//插入元素过程
	{
		int elem;
		cout << "insert " << a << " elem:";
		cin >> elem;
		ListInsert_Sq(A, i, elem);
		a = a + 1;
	}
	cout << "create A list successfully" << endl;
	cout << "now the A list's length is " << A.length << endl;
	cout << "please enter B list's length:";
	cin >> B_length;
	int b = 1;
	for (int i = 0; i < B_length; i++)//插入元素过程
	{
		int elem;
		cout << "insert " << b << " elem:";
		cin >> elem;
		ListInsert_Sq(B, i, elem);
		b = b + 1;
	}
	cout << "create B list successfully" << endl;
	cout << "now the B list's length is " << B.length << endl;
	A_length = ListLength(A);
	for (int i = 1; i < B_length + 1; i++)
	{
		bool result1;
		GetElem(B, i, e);
		LocalElem(A, e, result1);
		if (result1 == FALSE)
		{
			continue;
		}
		else
		{
			A_length = A_length - 1;
			ListInsert_Sq(A, A_length, e);
			A_length = ListLength(A);
		}
	}
	for (int i = 0; i < A.length; i++)
	{
		cout << A.elem[i] << " ";
	}
}

线性表链式结构

头文件

//Mylist2.h
#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
typedef int DATAType;
typedef string ElemType;
typedef struct LNode
{
	int data;//数据域
	struct LNode* next;//指针域
}LNode, * SLink;
int InitList(SLink& L);//初始化列表
void showList(SLink& L);//显示列表元素
void findList(SLink& L, int pos, int& e);//查找第n位的元素
void findListElem(SLink& L, int ListElem, int& Elem_pos, int List_length);//查找元素是否存在该列表中
void InsertList(SLink& L, int insert_pos, int num);//单链表中插入元素
void DeleteListElem(SLink& L, int dele_pos);//删除单链表中的元素
void ModifyListElem(SLink& L, int modi_pos, int& modi_Elem);//修改链表中某个位置的元素
void MergeList(SLink& pa, SLink& pb);//合并两个表
void PriorElem_list(SLink& L, int cur_elem, int& pre_elem);
void NextElem_list(SLink& L, int cur_elem, int& next_elem);
int InitList(SLink& L)
{
	SLink p, q;
	int n;//单链表元素的个数
	L = (SLink)malloc(sizeof(SLink));
	L->next = nullptr;
	p = L;
	cout << "请输入单链表元素的个数为:";
	cin >> n;
	int num;
	for (int i = 0; i < n; i++)
	{
		cout << "第" << i << "个元素:";
		q = (SLink)malloc(sizeof(SLink));
		cin >> num;
		q->data = num;
		p->next = q;
		p = q;
		p->next = nullptr;
	}
	return n;
}

void showList(SLink& L)
{
	SLink p;
	for (p = L->next; p != NULL; p = p->next)
	{
		cout << p->data << "  ";
	}
	cout << endl;
}

void findList(SLink& L, int pos, int& e)
{
	SLink p;
	p = L;
	for (int i = 1; i <= pos; i++)
	{
		p = p->next;
	}
	e = p->data;
}

void findListElem(SLink& L, int ListElem, int& Elem_pos, int List_length)
{
	SLink p;
	int i = 0;
	for (p = L->next; p != NULL; p = p->next)
	{
		i++;
		if (p->data == ListElem)
		{
			Elem_pos = i;
			cout << "要查找的元素" << ListElem << "所在的位置是:" << Elem_pos << endl;
			break;
		}
		if (i == List_length)
		{
			cout << "该元素不在该单链表中" << endl;
		}
	}
}

void InsertList(SLink& L, int insert_pos, int num)
{
	SLink l;
	l = L;
	LNode* p = new LNode;
	p->data = num;
	for (int i = 1; i < insert_pos; i++)
	{
		l = l->next;
	}
	p->next = l->next;
	l->next = p;
}

void DeleteListElem(SLink& L, int dele_pos)
{
	SLink p, q;
	p = L;
	for (int i = 1; i < dele_pos; i++)
	{
		p = p->next;
	}
	q = p->next;
	p->next = q->next;
	free(q);
}

void ModifyListElem(SLink& L, int modi_pos, int& modi_Elem)
{
	SLink p;
	p = L;
	for (int i = 1; i <= modi_pos; i++)
	{
		p = p->next;
	}
	p->data = modi_Elem;
}

void MergeList(SLink& pa, SLink& pb)
{
	SLink pc, ptr, C, pC;
	cout << "初始化链表C" << endl;
	C = (SLink)malloc(sizeof(SLink));
	C->next = nullptr;
	pC = C;
	while (pa != NULL && pb != NULL)
	{
		pc = (SLink)malloc(sizeof(SLink));
		ptr = (SLink)malloc(sizeof(SLink));
		if (pa->data == pb->data)
		{
			pc->data = pa->data;
			pa = pa->next;
			ptr = pb;
			pb = pb->next;

		}
		else if (pa->data < pb->data)
		{
			pc->data = pa->data;
			pa = pa->next;
		}
		else
		{
			pc->data = pb->data;
			pb = pb->next;
		}
		//插入操作
		pC->next = pc;
		pC = pc;
		pC->next = nullptr;
	}
	if (pa != NULL)
	{
		while (pa != NULL)
		{
			pc = (SLink)malloc(sizeof(SLink));
			pc->data = pa->data;
			pa = pa->next;
			//插入
			pC->next = pc;
			pC = pc;
			pC->next = nullptr;
		}
	}
	else
	{
		while (pb != NULL)
		{
			pc = (SLink)malloc(sizeof(SLink));
			pc->data = pb->data;
			pb = pb->next;
			//插入
			pC->next = pc;
			pC = pc;
			pC->next = nullptr;
		}
	}
	cout << "合并链表A和链表B后的效果是:";
	showList(C);
}

void PriorElem_list(SLink& L, int cur_elem, int& pre_elem)//寻找链表的前驱
{
	SLink p, q;
	if (L)
	{
		p = L->next;
		if (p->data != cur_elem)
		{
			while (p->next)
			{
				q = p->next;
				if (q->data == cur_elem)
				{
					pre_elem = p->data;

				}
				p = q;
			}
		}
	}
}

void NextElem_list(SLink& L, int cur_elem, int& next_elem)//查找链表元素的后继节点
{
	SLink p, q;
	if (L)
	{
		p = L->next;
		while (p && p->next)
		{
			q = p->next;
			if (q && p->data == cur_elem)
			{
				next_elem = q->data;
			}
			if (q)
			{
				p = q;
			}
			else
			{
				break;
			}
		}
	}
}

测试程序

//线性表链表.cpp
#include <iostream>
#include"Mylist2.h"
using namespace std;
void main()
{
	SLink P;
	cout << "初始化链表" << endl;
	int test = InitList(P);
	int pre_elem, next_elem;
	PriorElem_list(P, 5, pre_elem);
	cout << "the elem " << 5 << "prior element is " << pre_elem;
	NextElem_list(P, 5, next_elem);
	cout << "the elem " << 5 << "next element is " << next_elem;

	//两个表的合并
	SLink A, B, pa, pb, pc, C, ptr;
	int AList_length, BList_length;
	cout << "初始化链表A" << endl;
	AList_length = InitList(A);
	cout << "链表A:";
	showList(A);
	pc = A;
	pa = A->next;
	cout << "初始化链表B" << endl;
	BList_length = InitList(B);
	cout << "链表B:";
	showList(B);
	pb = B->next;
	MergeList(pa, pb);
}

注释

• 1、关于new 与malloc的用法
• 2、关于free与delete的用法
• 3、关于nullptr与null的用法