数据结构（C）之线性表（未完成）

2023-12-23 14:38:16

文章目录

1、线性表基本定义
2、线性表的顺序存储结构
3、线性表的链式储存结构
4、循环链表
5、双向链表

1、线性表基本定义

1.1 线性表定义

线性表（List）是零个或多个数据元素的集合
线性表中的数据元素之间是有顺序的
线性表中的数据元素是有限的
线性表中的数据类型必须相同

1.2 数学定义

线性表宿舍具有相同类型n（≧ 0）个数据元素的有限序列，（a1，a2，……，an），ai是表项，n是表长度

1.3 性质

a0为线性表的第一个元素，只有一个后继
an为线性表的最后一个元素，只有一个前驱
除a和an外的其他元素，既有前驱，又有后后继
线性表能逐项访问和顺序读取

1.4 练习

下面关系能用线性表描述的是：
A、班级中同学的友谊关（N:N）
B、公司中上下级关系（1:N）
C、冬天图书馆排队占座关系(1:?)
D、花名册名字之间的关系(1：1)

1.5 线性表的操作

创建线性表
销毁线性表
清空线性表将元素插入线性表
将元素从线性表中删除
获取线性表在某个位置的元素
获取线性表的长度
线性表在程序中表现为一种特殊的数据类型
线性表的操作在程序在的表现为一组函数

/*C语言描述=====》线性表的设计与实现
ADT抽象层  《[数据结构(C语言版)].严蔚敏_吴伟民.扫描版.pdf》 p44页 
人生财富库积累*/
#ifndef _WBM_LIST_H_
#define _WBM_LIST_H_

typedef void List;
typedef void ListNode;

//创建并且返回一个空的线性表
List* List_Create();

//销毁一个线性表list
void List_Destroy(List* list);

//将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
void List_Clear(List* list);

//返回一个线性表list中的所有元素个数
int List_Length(List* list);

//向一个线性表list的pos位置处插入新元素node
int List_Insert(List* list, ListNode* node, int pos);  

//获取一个线性表list的pos位置处的元素
ListNode* List_Get(List* list, int pos);

//删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
ListNode* List_Delete(List* list, int pos);

#endif
*/注意:
int List_Insert(List* list, ListNode* node, int pos);  (重点:分离思想) */

2、线性表的顺序存储结构

2.1 基本概念

2.2 设计与实习

插入元素算法
判读线性表是否合法
判断插入位置是否合法
把最后一个元素插入到位置元素后移一个位置
将新元素插入
线性表长度加+1

获取元素操作
判断线性表是否合法
判断位置是否合法
直接通过数组下标方式获取元素

删除元素算法
判读线性表是否合法
判断删除位置是否合法
将元素取出
将删除位置后的元素分别向前移动一个位置
线性表长度加-1

链表顺序存储插入算法和删除算法

2.3 优点与缺点

优点
无需为线性表中的逻辑关系增加额外的空间
可以快速的获取表中合法位置的·元素

缺点
插入和删除操作需要移动大量元素
当线性表长度大时难以确定存储空间的容量

2.4 实习代码

实现代码:

//头文件seqlish.h
#ifndef __MY_SEQLIST_H__
#define __MY_SEQLIST_H__

typedef void SeqList;
typedef void SeqListNode;

SeqList* SeqList_Create(int capacity);

void SeqList_Destroy(SeqList* list);

void SeqList_Clear(SeqList* list);

int SeqList_Length(SeqList* list);

int SeqList_Capacity(SeqList* list);

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);

SeqListNode* SeqList_Get(SeqList* list, int pos);

SeqListNode* SeqList_Delete(SeqList* list, int pos);


#endif // __MY_SEQLIST_H__

//seqlish.c
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include"seqlist.h"

//在结构体套一级指针
//
typedef struct _tag_SeqList
{
	int length;
	int capacity;
	unsigned int* node;

}TSeqList;

SeqList* SeqList_Create(int capacity)
{
	TSeqList* tmp = NULL;
	int ret = 0;

	tmp = (TSeqList*)malloc(sizeof(TSeqList));
	if (tmp == NULL)
	{
		ret = -1;
		printf("func SeqList_Create() err:%d \n", ret);
		return NULL;
	}

	memset(tmp, 0, sizeof(TSeqList));

	//根据capacity分配内存大小
	tmp->node = (SeqListNode*)malloc(sizeof(unsigned int*) * capacity);
	if (tmp->node == NULL)
	{
		ret = -2;
		printf("func SeqList_Create() err:%d \n", ret);
		return NULL;
	}
	tmp->capacity = capacity;
	tmp->length = 0;

	return tmp;
}

void SeqList_Destroy(SeqList* list)
{
	TSeqList* tlist = NULL;
	if (list == NULL)
	{
		return;
	}
	tlist = (TSeqList*)list;
	if (tlist->node != NULL)
	{
		free(tlist->node);
	}
	free(tlist);
	return;
}


//清空链表 //回到初始化状态
void SeqList_Clear(SeqList* list)
{
	TSeqList* tlist = NULL;
	int ret = 0;
	if (list == NULL)
	{
		ret = -1;
		printf("func SeqList_Clear() err:%d \n", ret);
		return;
	}
	tlist = (TSeqList *)list;
	if (tlist->node != NULL)
	{
		free(tlist->node);
	}

	tlist->capacity = 0;
	tlist->length = 0;
	return;
}

int SeqList_Length(SeqList* list)
{
	TSeqList* tlist = NULL;
	
	if (list == NULL)
	{
		return -1;
	}

	tlist = (TSeqList *)list;
	return tlist->length;

}

int SeqList_Capacity(SeqList* list)
{
	TSeqList* tlist = NULL;
	if (list == NULL)
	{
		return -1;
	}
	tlist = (TSeqList*)list;
	return tlist->capacity;
}

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
	TSeqList* tlist = NULL;
	int ret = 0,i=0;

	if (list == NULL || pos < 0 || node == NULL) 
	{
		ret = -1;
		printf("func SeqList_Insert() err:%d \n", ret);
		return ret;
	}

	tlist = (TSeqList*)list;

	//判断是否满了
	if (tlist->length >= tlist->capacity)
	{
		ret = -2;
		printf("func SeqList_Insert() err(tlist->length >= tlist->length):%d \n", ret);
		return ret;
	}

	//容错修正
	if (tlist->length <  pos)
	{
		pos = tlist->length;
	}

	//pos后元素后移
	for (i = tlist->length; i > pos; i--)
	{
		tlist->node[i] = tlist->node[i - 1];
	}

	//插入元素
	tlist->node[i] = (unsigned int)node;

	tlist->length++;

	return ret;
}

SeqListNode*  SeqList_Get(SeqList* list, int pos)
{
	TSeqList* tlist = NULL;

	SeqListNode* ret = 0;

	if (list == NULL || pos<0)
	{
		printf("func SeqList_Get() err：%d \n", ret);
		return NULL;
	}

	tlist = (TSeqList *)list;

	ret = (SeqListNode *)tlist->node[pos];

	return ret;
}

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
	TSeqList* tlist = NULL;

	SeqListNode* ret = 0;

	int i = 0;


	if (list == NULL || pos < 0)//检查
	{
		printf("func SeqList_Delete() err:%d \n", ret);
		return NULL;
	}

	tlist = (TSeqList *)list;

	if (pos >= tlist->length)
	{
		printf("func SeqList_Delete() err:%d \n", ret);
		return ret;
	}

	ret = (SeqListNode *)tlist->node[pos];//缓存pos的位置

	for (i = pos+1; i < tlist->length; i++)//pos后面的位置前移
	{
		tlist->node[i-1] = tlist->node[i];
	}

	tlist->length--;

	return ret;
}

//dm02_线性表顺序储存与设计测试框架.c
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include"seqlist.h"

//在结构体套二级指针
//
typedef struct _tag_SeqList
{
	int length;
	int capacity;
	unsigned int** node;

}TSeqList;

SeqList* SeqList_Create(int capacity)
{
	TSeqList* tmp = NULL;
	int ret = 0;

	tmp = (TSeqList*)malloc(sizeof(TSeqList));
	if (tmp == NULL)
	{
		ret = -1;
		printf("func SeqList_Create() err:%d \n", ret);
		return NULL;
	}

	memset(tmp, 0, sizeof(TSeqList));

	//根据capacity分配内存大小
	tmp->node = (SeqListNode*)malloc(sizeof(unsigned int**) * capacity);
	if (tmp->node == NULL)
	{
		ret = -2;
		printf("func SeqList_Create() err:%d \n", ret);
		return NULL;
	}
	tmp->capacity = capacity;
	tmp->length = 0;

	return tmp;
}

void SeqList_Destroy(SeqList* list)
{
	TSeqList* tlist = NULL;
	if (list == NULL)
	{
		return;
	}
	tlist = (TSeqList*)list;
	if (tlist->node != NULL)
	{
		free(tlist->node);
	}
	free(tlist);
	return;
}


//清空链表 //回到初始化状态
void SeqList_Clear(SeqList* list)
{
	TSeqList* tlist = NULL;
	int ret = 0;
	if (list == NULL)
	{
		ret = -1;
		printf("func SeqList_Clear() err:%d \n", ret);
		return;
	}
	tlist = (TSeqList *)list;
	if (tlist->node != NULL)
	{
		free(tlist->node);
	}

	tlist->capacity = 0;
	tlist->length = 0;
	return;
}

int SeqList_Length(SeqList* list)
{
	TSeqList* tlist = NULL;
	
	if (list == NULL)
	{
		return -1;
	}

	tlist = (TSeqList *)list;
	return tlist->length;

}

int SeqList_Capacity(SeqList* list)
{
	TSeqList* tlist = NULL;
	if (list == NULL)
	{
		return -1;
	}
	tlist = (TSeqList*)list;
	return tlist->capacity;
}

int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
{
	TSeqList* tlist = NULL;
	int ret = 0,i=0;

	if (list == NULL || pos < 0 || node == NULL) 
	{
		ret = -1;
		printf("func SeqList_Insert() err:%d \n", ret);
		return ret;
	}

	tlist = (TSeqList*)list;

	//判断是否满了
	if (tlist->length >= tlist->capacity)
	{
		ret = -2;
		printf("func SeqList_Insert() err(tlist->length >= tlist->length):%d \n", ret);
		return ret;
	}

	//容错修正
	if (tlist->length <  pos)
	{
		pos = tlist->length;
	}

	//pos后元素后移
	for (i = tlist->length; i > pos; i--)
	{
		tlist->node[i] = tlist->node[i - 1];
	}

	//插入元素
	tlist->node[i] = node;

	tlist->length++;

	return ret;
}

SeqListNode*  SeqList_Get(SeqList* list, int pos)
{
	TSeqList* tlist = NULL;

	SeqListNode* ret = 0;

	if (list == NULL || pos<0)
	{
		printf("func SeqList_Get() err：%d \n", ret);
		return NULL;
	}

	tlist = (TSeqList *)list;

	ret = (SeqListNode *)tlist->node[pos];

	return ret;
}

SeqListNode* SeqList_Delete(SeqList* list, int pos)
{
	TSeqList* tlist = NULL;

	SeqListNode* ret = 0;

	int i = 0;


	if (list == NULL || pos < 0)//检查
	{
		printf("func SeqList_Delete() err:%d \n", ret);
		return NULL;
	}

	tlist = (TSeqList *)list;

	if (pos >= tlist->length)
	{
		printf("func SeqList_Delete() err:%d \n", ret);
		return ret;
	}

	ret = (SeqListNode *)tlist->node[pos];//缓存pos的位置

	for (i = pos+1; i < tlist->length; i++)//pos后面的位置前移
	{
		tlist->node[i-1] = tlist->node[i];
	}

	tlist->length--;

	return ret;
}

3、线性表的链式储存结构

3.1 基本概念

链式存储定义
为了表示每个数据与其直接后继元素之间的逻辑关系，每个元素除了存储本身的信息外，还需要储存指示其直接后继的信息

表头节点
链表中的第一个节点，指向第一个元素的指针以及链表自身的一些信息
数据节点
链表中代表数据元素的节点，包含指向下一个数据元素的指针和数据元素的信息
尾节点
链表中最后一个数据节点，其下一个元素指针为空，表示无后继

3.2 链表技术领域推演

3.3 设计与实习

链表链式存储_api实现分析

在C语言中可以用结构体来定义链表中的指针域

链表中的表头节点可以用结构体实现

带头节点、位置从0的链表
返回链表中第3个位置处，元素的值

LinkListNode* LinkList_Get(LinkList* list, int pos)
{ 
	int  i = 0;
	TLinkList *tList = (TLinkList *)list;
	LinkListNode *current = NULL;
	LinkListNode *ret = NULL;

	if (list==NULL ||pos<0 || pos>=tList->length)
	{
		return NULL;
	}
	current = (LinkListNode *)tList;
	for (i=0; i<pos; i++)
	{
		current = current->next;
	}
	ret = current->next;
	return ret ;
}

返回第三的位置的
移动pos次后，当前指针指向哪里？
答案：指向位置2，所以需要返回ret = current->next

备注
循环遍历时
遍历第1次，指向位置0
遍历第2次，指向位置1
遍历第3次，指向位置2
所以想返回位置 n 的元素的值，需要怎么做
ret = current->next;
此问题是：指向节点的指针移动n次和第n个元素之间的关系？

删除元素

重要技术场景图
链表链式存储_插入

链表链式存储_删除

3.4 优点与缺点

优点
无需一次性定制链表的容量
插入和删除操作无需移动数据

缺点
数据元素必须保存后继元素的位置信息
获取指定数据的元素操作需要访问之前的元素

3.5 实现代码

实现代码:

//头文件linklish.h
#ifndef _LINKLIST_H
#define _LINKLIST_H

typedef void LinkList;
/*
typedef struct _tag_LinkListNode;
struct _tag_LinkListNode
{
	LinkListNode* next;
}
*/

typedef struct _tag_LinkListNode
{
	struct _tag_LinkListNode* nxet;
}LinkListNode;


LinkList* LinkList_Create();

void LinkeList_Destroy(LinkList* list);

void LinkList_Clear(LinkList* list);

int LinkList_Length(LinkList* list);

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);

LinkListNode* LinkList_Get(LinkList* list, int pos);

LinkListNode* LinkList_Delete(LinkList* list, int pos);

#endif

//linklish.c
#include<stdio.h>
#include<Stdlib.h>
#include<string.h>
#include "linklist.h"

typedef struct _tag_LinkList
{
	LinkListNode header;
	int length;
}TLinkList;

LinkList* LinkList_Create()
{
	TLinkList* ret = NULL;

	ret = (TLinkList *)malloc(sizeof(TLinkList));

	if (ret == NULL)
	{
		printf("func LinkList_Create() err:%d\n", ret);
	}

	memset(ret, 0 ,sizeof(TLinkList));

	//可以删去
	ret->length = 0;
	ret->header.nxet = NULL;

	return ret;
}


void LinkeList_Destroy(LinkList* list)
{
	if (list != NULL)
	{
		free(list);

		//可以删去
		list = NULL;
	}

	return;
}

//让链表恢复到初始状态
void LinkList_Clear(LinkList* list)
{

	TLinkList* tlist = NULL;

	if (list == NULL)
	{
		return;
	}

	tlist = (TLinkList*)list;

	tlist->header.nxet = NULL;
	tlist->length = 0;

	return;
}

int LinkList_Length(LinkList* list)
{
	int ret = 0;
	TLinkList* tlist = NULL;

	if(list == NULL)
	{
		ret = -1;
		printf("func LinkList_Length() err:%d \n", ret);
		return ret;
	}

	tlist = (TLinkList*)list;

	ret = tlist->length;

	return ret;
}

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
	int i = 0, ret = 0;
	LinkListNode* current = NULL;
	TLinkList* tlist = NULL;

	if (list == NULL || pos < 0 || node == NULL)
	{
		ret = -1;
		printf("func LinkList_Insert() err:%d \n", ret);
		return ret;
	}

	tlist = (TLinkList*)list;

	if (tlist->length < pos)
	{
		ret = -2;
		printf("func LinkList_Insert() err:%d \n", ret);
		return ret;
	}

	current = &(tlist->header);

	for (i = 0; i < pos && (current->nxet!=NULL); i++)
	{
		current = current->nxet;
	}
	
	//1 然后node接续链表
	node->nxet = current->nxet;
	//2 让前面的链表 连接新的node节点
	current->nxet = node;
	
	tlist->length++;

	return ret;
}

LinkListNode* LinkList_Get(LinkList* list, int pos)
{
	TLinkList* tlist = NULL;
	LinkListNode* current = NULL;
	int i = 0,ret=0;

	if (list == NULL||pos<0)
	{
		printf("func LinkList_Get() err:%d \n", ret);
		return NULL;
	}

	tlist = (TLinkList*)list;
	current = &(tlist->header);//让辅助指针指向表的头部
	
	for (i = 0; i < pos && (current->nxet !=NULL) ; i++)//跳pos次
	{
		current = current->nxet;
	}

	return current->nxet;
}

LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
	int i = 0;
	LinkListNode* current = NULL;
	LinkListNode* ret = NULL;

	TLinkList* tlist = NULL;
	if (list == NULL || pos < 0)
	{
		printf("func LinkList_Delete() err:%d \n", ret);
		return NULL;
	}

	tlist = (TLinkList*)list;
	current = &(tlist->header);//让辅助指针变量指向链表的头部

	for (i = 0; i < pos && (current->nxet!=NULL); i++)//跳pos次
	{
		current = current->nxet;
	}

	//缓存被删除的节点
	ret = current->nxet; 

	//连线
	current->nxet = ret->nxet;

	tlist->length--;

	return ret;
}

//线性表链式存储集成测试.c
#include<stdio.h>
#include<Stdlib.h>
#include<string.h>
#include "linklist.h"


typedef	struct Teacher
{
	LinkListNode node;//第一个域（第一个元素）
	int age;
	char name[64];
}Teacher;

void main() 
{
	int ret = 0, len = 0;

	LinkList* list = NULL;

	Teacher t1, t2, t3, t4, t5;
	t1.age = 31;
	t2.age = 32;
	t3.age = 33;
	t4.age = 34;
	t5.age = 35;

	
	list = LinkList_Create();
	if (list== NULL)
	{
		return;
	}

	len = LinkList_Length(list);

	//链表的算法和具体业务节点的分离
	ret = LinkList_Insert(list, (LinkListNode*)(&t1) , 0);
	ret = LinkList_Insert(list, (LinkListNode*)(&t2), 0);
	ret = LinkList_Insert(list, (LinkListNode*)(&t3), 0);
	ret = LinkList_Insert(list, (LinkListNode*)(&t4), 0);
	ret = LinkList_Insert(list, (LinkListNode*)(&t5), 0);

	//遍历
	for (int i = 0; i < LinkList_Length(list); i++)
	{
		Teacher* tmp = LinkList_Get(list, i);
		if (tmp == NULL)
		{
			return;
		}
		printf("tmp->age:%d \n", tmp->age);
	}

	//删除链表
	while (LinkList_Length(list) > 0)
	{
		LinkList_Delete(list, 0);
	}

	LinkeList_Destroy(list);

	system("pause");
	return ;
}

码农公寓

数据结构（C）之线性表（未完成）

文章目录

1、线性表基本定义

1.1 线性表定义

1.2 数学定义

1.3 性质

1.4 练习

1.5 线性表的操作

2、线性表的顺序存储结构

2.1 基本概念

2.2 设计与实习

2.3 优点与缺点

2.4 实习代码

3、线性表的链式储存结构

3.1 基本概念

3.2 链表技术领域推演

3.3 设计与实习

3.4 优点与缺点

3.5 实现代码

4、循环链表

4.1 基本概念

4.2 设计与实习

4.3 优点与缺点

5、双向链表

5.1 基本概念

5.2 设计与实习

5.3 优点与缺点

码农公寓

文章目录

1、线性表基本定义

1.1 线性表定义

1.2 数学定义

1.3 性质

1.4 练习

1.5 线性表的操作

2、 线性表的顺序存储结构

2.1 基本概念

2.2 设计与实习

2.3 优点与缺点

2.4 实习代码

3、 线性表的链式储存结构

3.1 基本概念

3.2 链表技术领域推演

3.3 设计与实习

3.4 优点与缺点

3.5 实现代码

4、 循环链表

4.1 基本概念

4.2 设计与实习

4.3 优点与缺点

5、 双向链表

5.1 基本概念

5.2 设计与实习

5.3 优点与缺点

相关文章

2、线性表的顺序存储结构

3、线性表的链式储存结构

4、循环链表

5、双向链表