数据结构-线性表

✍️ 银勒

🗓️2018-03-27 (🗒️2024-04-22)

又到周末了，第一天上机结果IDE都没有找到，感觉是不是自己命令行用习惯了，基本的编译器都不会用了，还好在下机前5分钟找到了IDE，每周总要做做笔记啥的，这周主要学了线性表，感觉线性表这东西老师讲的很清楚了，保持思考还是把它写下来吧，或许几个月以后我对它的理解又更进一步了。总之，这次上机的内容还算简单。

感觉这《数据结构》这门课还是挺有意思的，上课的时候不仅分析算法还补充下语法，我呢平时基本不做预习这东西，可能是以前高中自学高数留下来的坏毛病吧，不过老师上课讲的东西我的脑子里面记得还是很清楚的，回头看看书感觉更好了。我在枕头旁边放了两本数据结构，基本没翻，要是睡觉的时候会自动扩散到脑子里面就好了。平时没事会把代码输电脑里面进来，最后同步到仓库。其实我更喜欢在纸上写好代码之后再输进电脑，不知道为什么老是有这种感觉感觉只有一打开电脑又得浪费不少时间。

我在GitHub上面的主页

[Ourfor](https://github.com/ourfor) [我的C/C++学习](https://github.com/ourfor/My-C-Learning)

线性表

有必要弄清以下几个概念：

线性表
顺序表
链表

线性表

目前我是这样理解的，线性表之所以叫线性表就是因为表中的数据元素之间存在一对一的关系，这就好比***离散数学***里面讲的序偶，除了表头元素和表尾元素外表中每个元素都有唯一的一个直接前驱和直接后继，这样就使得这些元素在表中元素的位置唯一确定，同时这个表就有了逻辑顺序，满足这种特性有数组、字串之类的。

线性表根据存储方式不同可以分为顺序表和链表，其中以顺式存储的线性表叫做顺序表，以链式存储的线性表叫做链表。这两种表有各自的优缺点：

类型（Type）	优点（Advantages）	缺点（Disadvantages）
线性表（Sqlist）	可对表中元素随机存取	表中的元素个数必须是确定的，虽然可用增加空间，但是初始化时还是会占用一定的空间，删除和插入元素比较复杂
链表（Linklist）	可用按照需要临时分配空间，删除与插入元素比较简单	无法对表中元素随机存取，查找某个位置的元素也比较复杂。

预定义状态代码.

#define    OK      1
#define    TRUE    1
#define    ERROR   0
#define    FALSE   0
#define    INFEASIBLE    -1
#define    OVERFLOW      -2

typedef int Status;
typedef double ElemType;

顺序表

顺式存储线性表的建立、初始化、元素的插入、查找、删除以及销毁。

建立以及初始化

首先，该如何实现顺序表这种数据类型？使用结构体定义顺序表时需要定义哪些成员？顺序表中除了元素还有元素的位置顺序（通过物理相邻来反映逻辑顺序），同时还需要对顺序表分配空间。定义结构体Sqlist，它包含三个成员，基地址elem，和数组相同；当前顺序表的元素个数用length来表示，顺序表可以容纳的元素的大小可以用listsize来表示；也就是说只需要一个结构体Sqlist变量就可以表示顺序表，那么顺序表中的元素应该存放在哪个位置呢？通常我们使用数组来存放同一数据类型的多个数据，C编译系统在编译数组的时候将数组名作为该数组的首地址。
同样的在顺序表中，我们将数据存放在基地址elem后面，那么就要求elem的地址与length的地址之间有足够的空间来存放数据。因此，顺序表的结构体可以这样定义：

typedef struct{
	ElemType *elem;      //结构体的基地址
	int length;          //顺序表中实际存放的元素个数
	int listsize;        //顺序表中能够存放的元素个数
}Sqlist;//结构体名

前方高能

最近刷抖音小视频刷到几首好听的歌

gcc/g++

这是我所使用的编译器版本，如果遇到malloc出错，可以在预处理指令中加上#include<stdlib.h>

顺序表基本操作

初始化
输入、输出、查找
插入、删除
就地逆置

初始化

//-------------------线性表初始量-------------------
#define LIST_INIT_SIZE 100
#define LIST_ADD_SIZE 10

//-------------------初始化线性表-------------------
Status InitList(Sqlist &T)
{
//构造一个空的线性表L
	T.elem=(ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));            
	if(!T.elem) exit(OVERFLOW);
	T.length=0;
	T.listsize=LIST_INIT_SIZE;
	cout << "线性表初始化成功！" << endl;
	return OK;
}//InitList

输入、输出、查找

//-------------------线性表数据的输出-------------------
Status DisplayList(Sqlist T)
{   
	ElemType * q=T.elem;
	for(int i=0;i<=T.length-1;i++)
	{
		q=T.elem+i;
		cout << * q << " " ;
		 
	}
	cout << "\n";
	return OK;
}
//-------------------线性表数据输入-------------------
Status InputList(Sqlist &T)
{
	cout << "线性表中有多少个元素：";
	cin >> T.length;
	cout << "请输入线性表中的各个元素：";
	ElemType * p;
	p=T.elem;
	for(int i=0;i<=T.length-1;i++,p++)
	{
		
		cin >> * p;
	}
	DisplayList(T);
	return OK;
}
//-------------------查找-------------------
Status LocalList(Sqlist &T,ElemType find_elem)
{
	ElemType *p;
	int elem_num=0;
	int num=0;
	for(p=T.elem;p<T.elem + T.length - 1;p++)
	{
		num+=1;
		if(*p==find_elem){
			elem_num=num;
			cout << "元素" << find_elem << "在线性表中位于第" << elem_num << "个位置";
			cout << "\n";
			return OK;
		}
	}
	if(elem_num==0) cout << "表中不存在元素" << find_elem;
	return ERROR;
}

插入、删除

插入与删除的基本思路
顺序表插入元素主要操作应该是从输入流中获取用户输入的元素位置（插入位置）以及元素，插入位置后面的元素都要后移，如果空间不够，还应该重新申请空间，基本的算法应该是这样：

判断用户输入的插入位置是否正确，即参数合法性的问题
检查顺序表中是否还有足够的空间让用户插入元素，如果不够还得重新向系统申请空间
插入元素的位置确定后，应从表尾元素开始直到插入位置原来的元素，每个元素后移一个单位，插入完成后，顺序表中表示表中元素个数的 length + 1 ，自此插入操作完成，最后还应将表中元素逐个输出，便于后续调试和测试。

删除的思路与插入有所不同，首先你不需要考虑空间，正常的删除应该是输入待删除的位置，将删除的元素保存下来，从删除位置后的第一个元素开始逐个前移这样就自然完成了删除操作，最后 length - 1 。同时将表中元素逐个输出，以及删除的元素。

判断用户输入的位置是否合法
从删除位置后的第一个元素开始逐个前移，完成后更改成员length的值
输出现在表中的元素以及删除的元素

//-------------------线性表元素的插入-------------------
Status InsertList(Sqlist &T,int i,ElemType e)
{
	//在第i个元素之前插入，使其成为第i个元素，判断插入位置i的合法性
	//如果空间不够，重新分配空间
	if(i<1||i>T.length+1) exit(ERROR);
	if(T.length>=T.listsize) 
	{
		ElemType * newbase=(ElemType *)malloc((LIST_INIT_SIZE+LIST_ADD_SIZE)*sizeof(ElemType));
		T.elem=newbase;
	}
	if(!T.elem) return ERROR;             //分配失败
	//i后面的元素后移
	int j;
	ElemType * p=T.elem;
	for(j=T.length - 1;j>=i - 1;j--) *(p + j + 1)=*(p + j);
	*(T.elem + i - 1)=e;
	cout << "已将第" << i << "个位置插入元素" << e << endl;
	T.length=T.length + 1;
	DisplayList(T);
	return OK;
}
//-------------------线性表元素的删除-------------------
Status DeleteList(Sqlist &T,int i,ElemType &f)
{
	//删除位置的取值范围1<=i<=T.length
	//删除第i个元素，其他元素往前移
	if(i<1||i>T.length) exit(ERROR);
	ElemType *p=T.elem + i;
	f=*(p - 1);
	int j;
	for(j=i;j<=T.length;*(p - 2)=*(p - 1),j++)
		p++;
	T.length=T.length-1;
	cout << "删除的元素为" << f << endl;
	DisplayList(T);
	return OK;
}

全部代码

链表

链表与顺序表不同

链表的定义：

//-------------------------定义结构体-------------------------
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode;

LNode *head;

初始化
输入、输出、查找
插入、删除
就地逆置

初始化

//-------------------------初始化链表-------------------------
Status InitList(LNode * &head)
{
	head=(LNode *)malloc(sizeof(struct LNode));
	head->next=NULL;
	return OK;
}

输入、输出、查找

//-------------------------输入链表-------------------------
Status InputList(LNode * &head)
{
	LNode *p,*r;
	p=r=(LNode *)malloc(sizeof(struct LNode));	
	cout << "输入链表中的元素：";
	cin >> p->data;
	char stop;
	stop=cin.get();
	int n=0;
	while(stop!='\n')
	{
		n=n+1;
		if(n==1)head->next=p;
		else 
		{
			r=p;
			p=(struct LNode *)malloc(sizeof(struct LNode));
			cin >> p->data;
			stop=cin.get();
			r->next=p;
			
		}
		
	}

	p->next=NULL;
	return OK;
}

//-------------------------输出链表-------------------------
Status DisplayList(LNode *head)
{
	LNode *p;
	p=head->next;
	do{
		cout << p->data << " ";
		p=p->next;
	}while(p->next!=NULL);
	cout << p->data << "\n";
	return OK;
}

//-------------------------查找链表元素-------------------------
Status LocateList(LNode *head)
{
	cout << "你想查找链表中的哪个元素：";
	ElemType e;
	cin >> e;
	LNode *p;
	int n=0;
	for(p=head->next;p->data!=e&&p->next!=NULL;p=p->next)
	{
		n=n+1;
	}
	if(p->data!=e&&p->next==NULL) {cout << "链表中不存在元素" << e << endl;return FALSE;}
	if(p->data==e) {n=n+1;cout << e << "是链表中的第" << n << "个元素" << endl;}
	else cout << e << "是链表中的第" << n << "个元素" << endl;
	return OK;

}

插入、删除

//-------------------------链表元素的插入-------------------------
Status InsertLNode(LNode * &head)
{
	cout << "你想将元素插入到链表的哪个位置：";
	int i;
	cin >> i;
	ElemType e;
	while(i<=0)
	{
		cout << "插入位置不对，请输入有效的插入位置：";
		cin >> i;
	}
	cout << "插入什么元素：";
	cin >> e;
	LNode *p=head->next;
	for(int n=2;n<=i-1;n++)
	{
		p=p->next;
		if(p==NULL) break;
	}
	LNode *r;
	r=(LNode *)malloc(sizeof(LNode));
	r->data=e;
	r->next=p->next;
	p->next=r;
	DisplayList(head);
	return OK;
}

//-------------------------链表元素的删除-------------------------
Status DeleteLNode(LNode * &head)
{
	if(head->next==NULL) {cout << "链表为空" << endl;return ERROR;}
	cout << "你想删除哪个元素：";
	ElemType e;
	cin >> e;
	LNode *p,*r;
	for(p=head;p->data!=e&&p->next!=NULL;)
	{
                r=p;
		p=p->next;
	}
	if(p->data==e)
	{
		r->next=(p->next);
                DisplayList(head);
                return OK;
	}
	if(p->next==NULL){cout << "不存在要删除的元素" << e << endl;return ERROR;}
	r->next=p->next;
	cout << "已将元素删除" << endl;
	DisplayList(head);
	return OK;
}

就地逆置

//-------------------------链表就地逆置-------------------------
Status UnsLinklist(LNode * &head)
{
	LNode *p,*r,*first=head->next;
        cout << "将链表就地转置为：\n";
	for(p=head->next;p->next!=NULL;)
	{
		r=p->next;
		p->next=head->next;
		head->next=p;
		p=r;
	}
	p->next=head->next;
	head->next=p;
	first->next=NULL;
	
	DisplayList(head);
        return OK;
}

全部代码

代码已经全部同步到GitHub-ourfor

本文作者： 银勒
本文链接： https://ourfor.top/article/data-structure/