目录
2.线性表的实现
1.线性表的顺序存储表示
1.定义
2.初始化
3.判断是否为空表
4.求表长
5.查找
6.查询直接前驱节点
7.查询直接后继节点
8. 插入顺序表插入
9.删除节点
10.遍历顺序表
11.完整代码
2.线性表的链式存储表示
1.定义
2.初始化
3.判断是否为空表
4.求表长
5.查找
6.查询直接前驱节点
7.查询直接后继节点
8. 插入
9.删除节点
10.遍历顺序表
11.完整代码
由n(n≥0)个数据特性相同的元素构成的有限序列称为线性表。线性表中元素的个数n(n≥0)定义为线性表的长度,n=0时称为空表。对于非空的线性表或线性结构,其特点是:
。
(1)存在唯一的一个被称作“第一个”的数据元素;
(2)存在唯一的一个被称作“最后一个”的数据元素;
(3)除第一个之外,结构中的每个数据元素均只有一个前驱;
(4)除最后一个之外,结构中的每个数据元素均只有一个后继
2.线性表的实现
线性表有顺序存储和链式存储两种表示方法。
1.线性表的顺序存储表示
顺序表是一种线性表的存储结构,它用一组地址连续的存储单元依次存储线性表的数据元素。顺序表中的元素在物理位置上是连续存储的,这使得顺序表在存取元素时具有良好的随机访问性能。
在 C 语言中,顺序表通常通过数组来实现。每个元素在数组中的下标可以作为该元素在顺序表中的位置,因此可以直接通过下标访问或修改元素,具有较高的访问效率。
1.定义
#define MAXSIZE 100 //顺序表的最大长度
#define ElementType int
typedef struct {
ElementType *element; // 存储空间基地址
int length; // 当前长度
} SeqList;
2.初始化
初始化线性表的时候,我们需要先给线性表分配存储空间,然后把线性表的表长置空。
// 初始化
int initSeqList(SeqList *seqList) {
seqList->element = (ElementType *)malloc(sizeof(ElementType) * MAXSIZE);
if (seqList->element == NULL) { // 初始化失败
printf("初始化分配空间失败!\n");
return 0;
}
seqList->length = 0;
return 1;
}
3.判断是否为空表
int seqListIsEmpty(SeqList *seqList){
return seqList->length == 0;
}
4.求表长
int seqListLength(SeqList *seqList){
int length = seqList->length;
return length;
}
5.查找
一个是根据下标查找,这种查找结构是唯一的。还有就是根据元素查找,这里返回的是第一个和要查找的元素相同的元素下标。
int getElement(SeqList *seqList,int location,int * element){
if (location < 1 || location > seqList->length) {
printf("非法位置\n");
return 0;
}
if (seqList->length < 1) {
printf("非法顺序表");
return 0;
}
* element = seqList->element[location-1];
return 1;
}
int getLocate(SeqList *seqList,ElementType element){
for (int i = 0; i<seqList->length; i++) {
if (seqList->element[i] == element) {
return i;
}
}
return -1;
}
6.查询直接前驱节点
遍历顺序表,先查看节点是否存在,在查看前驱节点。
// 查询直接前驱节点
int priorElement(SeqList *seqList,ElementType element, ElementType * previousLlement){
int hasExistElement = 0;
int index = -1;
for (int i = 0; i < seqList->length ; i++) {
if (seqList->element[i] == element) {
index = i;
hasExistElement = 1;
}
}
if (hasExistElement) {
if (index <= 0) {//第1个元素没有前驱节点
return 0;
} else {
* previousLlement = seqList->element[index - 1];
return 1;
}
} else {
return 0;
}
}
7.查询直接后继节点
遍历顺序表,先查看节点是否存在,在判断是否有后继节点。
// 查询直接后继节点
int nextElement(SeqList *seqList,ElementType element, ElementType * nextElement){
int hasExistElement = 0;
int index = -1;
for (int i = 0; i < seqList->length ; i++) {//判断后继节点是否存在
if (seqList->element[i] == element) {
index = i;
hasExistElement = 1;
}
}
if (hasExistElement) {
if (index >= seqList->length-1) {//最后一个节点没有后继节点
return 0;
} else {
* nextElement = seqList->element[index + 1];
return 1;
}
} else {
return 0;
}
}
8. 插入顺序表插入
判断下要插入的位置是否合法以及存储空间是否已经满了。
// 插入顺序表插入
void insertSeqList(SeqList *seqList, int location, ElementType element) {
if (location < 1 || location > seqList->length + 1) {
printf("插入位置非法,insertSeqList方法插入❎\n");
return;
}
if (seqList->length == MAXSIZE) {//存储空间已满
printf("数组存储已满");
return ;
}
for (int j = seqList->length; j >= location; j--) {
seqList->element[j] = seqList->element[j - 1];
}
seqList->element[location - 1] = element;
seqList->length++;
printf("insertSeqList方法插入✅\n");
}
9.删除节点
遍历顺序表,根据下标找到要删除掉元素,表长减一。
// 删除节点
int deleteElement(SeqList *seqList,int position){
if (position < 1 || position > seqList->length) {//非法位置
return 0;
}
for (int i = position - 1; i<seqList->length -1; i++) {
seqList->element[i] = seqList->element[i+1];
}
seqList->length--;
return 1;
}
10.遍历顺序表
我们使用for循环遍历顺序表。
// 遍历顺序表
void traverseList(SeqList *seqList){
for (int i = 0; i < seqList->length; i++) {
printf("%d\t", seqList->element[i]);
}
printf("\n");
}
11.完整代码
在这里。
2.线性表的链式存储表示
线性表的链式存储表示使用链表来实现。链表是一种数据结构,由一系列节点组成,每个节点包含数据元素和指向下一个节点的指针(或链接)。在链表中,每个节点的地址不一定是连续的,而是通过指针相互链接起来。
线性表的链式存储表示具有动态的内存分配特性,可以根据需要动态地分配和释放内存,因此可以有效地利用内存空间,并且不受固定大小的限制。此外,链式存储结构支持高效的插入和删除操作,但访问元素时需要遍历链表,效率较低。
1.定义
#define ElementType int
typedef struct LNode{
ElementType data;//数据域
struct LNode * next; //指针域
}LNode,*LinkList; //LinkList为指向结构体LNode的指针
2.初始化
初始化线性表的时候,我们需要先给线性表分配存储空间,然后把线性表的表长置空。
// 初始化
int initSeqList(SeqList *seqList) {
seqList->element = (ElementType *)malloc(sizeof(ElementType) * MAXSIZE);
if (seqList->element == NULL) { // 初始化失败
printf("初始化分配空间失败!\n");
return 0;
}
seqList->length = 0;
return 1;
}
3.判断是否为空表
int LinkListEmpty(LinkList linkList){
if (linkList->next == NULL) {
return 1;
}
return 0;
}
4.求表长
int linkListLength(LinkList list){
LNode * head = list;//头结点
int length = 0;
while (head->next != NULL) {
head = head->next;
length++;
}
return length;
}
5.查找
一个是根据下标查找,这种查找结构是唯一的。还有就是根据元素查找,这里返回的是第一个和要查找的元素相同的元素下标。
//
int getElement(LinkList linkList,int i,int * element){
LNode *current = linkList->next; // 从头结点的下一个节点开始遍历
int j = 1;
while (current != NULL && j< i) {
printf("第%d个元素的值为:%d \n",j, current->data);
current = current->next;
j++;
}
if (!current || j > i) {//第i个元素不存在
return 0;
}
* element = current->data;
return 1;
}
6.查询直接前驱节点
遍历单链表,先查看节点是否存在,在查看前驱节点。
// 查找单链表中的元素的前驱节点
int getPriorElement(LinkList linkList,int element,int * previousElement){
LNode * previous = linkList; // 头结点
LNode * current = linkList->next; // 头结点的下一个节点
while (current != NULL &¤t->data != element) {
previous = current;
current = current-> next;
}
if (previous->next == NULL) {
return 0;
}else{
* previousElement = previous->data;
return 1;
}
}
7.查询直接后继节点
遍历单链表,先查看节点是否存在,在判断是否有后继节点。
// 查找单链表中的元素的后继节点
int getNextElement(LinkList linkList,int element,int * nextElement){
LNode * current = linkList->next; // 头结点的下一个节点
while (current != NULL &¤t->data != element) {
current = current-> next;
}
if (current->next == NULL) {
return 0;
}else{
* nextElement = current->next->data;
return 1;
}
}
8. 插入
申请一个新的节点,修改要插入的节点的位置的指针域。
// 向链表中插入一个新的节点(在链表头部插入)
void insertLinkList(LinkList L, int value) {
LNode *newNode = (LNode *)malloc(sizeof(LNode));
if (!newNode) {
exit(1); // 分配内存失败则退出
}
newNode->data = value;
newNode->next = L->next; // 新节点的next指向原头结点后面的节点
L->next = newNode; // 头结点的next指向新节点
}
9.删除节点
我们需要找到要删除的节点的前驱节点,然后修改前驱节点的指针域。
// 删除单链表
void deleteLinkList(LinkList linkList, int value) {
LNode * current = linkList; // 头结点的下一个节点
int j = 0;
while (current != NULL && j < value -1) {//找到要删除节点的前驱节点
current = current-> next;
++j;
}
//生成一个新节点
LNode *newNode = (LNode *)malloc(sizeof(LNode));
if (newNode == NULL) {//内存分配失败
return;
}
if (!(current->next)|| j > value-1) {
return ;
}
newNode = current->next;//指向要删除的节点
current->next = newNode->next;
free(newNode);
}
10.遍历顺序表
我们使用for循环遍历顺序表。
// 打印链表中的所有元素
void printLinkList(LinkList L) {
LNode *current = L->next; // 从头结点的下一个节点开始遍历
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
11.完整代码
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点的结构体
typedef struct LNode {
int data; // 数据域
struct LNode *next; // 指针域,指向下一个节点
} LNode, *LinkList;
// 初始化链表,创建一个空链表
void inintLinkList(LinkList * linkList) {
* linkList = (LinkList)malloc(sizeof(LNode));
if (!*linkList) {
exit(1); // 分配内存失败则退出
}
(*linkList)->next = NULL; // 初始化头结点的指针域为空
}
int LinkListEmpty(LinkList linkList){
if (linkList->next == NULL) {
return 1;
}
return 0;
}
int linkListLength(LinkList list){
LNode * head = list;//头结点
int length = 0;
while (head->next != NULL) {
head = head->next;
length++;
}
return length;
}
// 查找单链表中的元素
int getElement(LinkList linkList,int i,int * element){
LNode *current = linkList->next; // 从头结点的下一个节点开始遍历
int j = 1;
while (current != NULL && j< i) {
printf("第%d个元素的值为:%d \n",j, current->data);
current = current->next;
j++;
}
if (!current || j > i) {//第i个元素不存在
return 0;
}
* element = current->data;
return 1;
}
// 查找单链表中的元素的前驱节点
int getPriorElement(LinkList linkList,int element,int * previousElement){
LNode * previous = linkList; // 头结点
LNode * current = linkList->next; // 头结点的下一个节点
while (current != NULL &¤t->data != element) {
previous = current;
current = current-> next;
}
if (previous->next == NULL) {
return 0;
}else{
* previousElement = previous->data;
return 1;
}
}
// 查找单链表中的元素的后继节点
int getNextElement(LinkList linkList,int element,int * nextElement){
LNode * current = linkList->next; // 头结点的下一个节点
while (current != NULL &¤t->data != element) {
current = current-> next;
}
if (current->next == NULL) {
return 0;
}else{
* nextElement = current->next->data;
return 1;
}
}
// 向链表中插入一个新的节点(在链表头部插入)
void insertLinkList(LinkList L, int value) {
LNode *newNode = (LNode *)malloc(sizeof(LNode));
if (!newNode) {
exit(1); // 分配内存失败则退出
}
newNode->data = value;
newNode->next = L->next; // 新节点的next指向原头结点后面的节点
L->next = newNode; // 头结点的next指向新节点
}
// 删除单链表
void deleteLinkList(LinkList linkList, int value) {
LNode * current = linkList; // 头结点的下一个节点
int j = 0;
while (current != NULL && j < value -1) {//找到要删除节点的前驱节点
current = current-> next;
++j;
}
//生成一个新节点
LNode *newNode = (LNode *)malloc(sizeof(LNode));
if (newNode == NULL) {//内存分配失败
return;
}
if (!(current->next)|| j > value-1) {
return ;
}
newNode = current->next;//指向要删除的节点
current->next = newNode->next;
free(newNode);
}
// 打印链表中的所有元素
void printLinkList(LinkList L) {
LNode *current = L->next; // 从头结点的下一个节点开始遍历
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 释放链表占用的内存
void FreeList(LinkList L) {
LNode *current = L, *temp;
while (current != NULL) {
temp = current;
current = current->next;
free(temp);
}
}
void printDebugInformation(char * string){
printf("\n********** %s **********\n",string);
}
int main(int argc, const char *argv[]) {
LinkList linkList;
inintLinkList(&linkList); // 初始化链表
//测试链表是否为空
if (LinkListEmpty(linkList)) {
printf("链表为空!\n");
}else{
printf("链表不为空!\n");
}
// 插入一些节点到链表中
insertLinkList(linkList, 1);
insertLinkList(linkList, 2);
insertLinkList(linkList, 3);
insertLinkList(linkList, 4);
insertLinkList(linkList, 5);
if (LinkListEmpty(linkList)) {
printf("链表为空!\n");
}else{
printf("链表不为空!\n");
int length = linkListLength(linkList);
printf("链表长度:%d\n",length);
}
// 打印链表
printLinkList(linkList);
//测试查找方法
int element;
if (getElement(linkList, 1, &element)) {
printf("链表第%d个元素为:%d\n",1,element);
}else{
printf("链表元素查找失败\n");
}
//测试前驱节点查找方法
printDebugInformation("测试前驱节点");
if (getPriorElement(linkList, 1, &element)) {//头结点
printf("链表中1的前驱节点为:%d\n",element);
}else{
printf("没有前驱节点\n");
}
if (getPriorElement(linkList, 3, &element)) {//头结点
printf("链表中3的前驱节点为:%d\n",element);
}else{
printf("没有前驱节点\n");
}
//测试后继节点
printDebugInformation("测试后继节点");
if (getNextElement(linkList, 5, &element)) {//头结点
printf("链表中5的后继节点为:%d\n",element);
}else{
printf("5没有后继节点\n");
}
if (getNextElement(linkList, 4, &element)) {//头结点
printf("链表中4的后继节点为:%d\n",element);
}else{
printf("4没有后继节点\n");
}
if (getNextElement(linkList, 3, &element)) {//头结点
printf("链表中3的后继节点为:%d\n",element);
}else{
printf("没有后继节点\n");
}
if (getNextElement(linkList, 2, &element)) {//头结点
printf("链表中2的前驱节点为:%d\n",element);
}else{
printf("2没有后继节点\n");
}
if (getNextElement(linkList, 1, &element)) {//头结点
printf("链表中1的前驱节点为:%d\n",element);
}else{
printf("1没有后继节点\n");
}
printDebugInformation("测试删除节点");
printf("删除之前的单链表:\n");
printLinkList(linkList);
deleteLinkList(linkList, 3);
printf("删除之后的单链表:\n");
printLinkList(linkList);
// // 释放链表内存
FreeList(linkList);
return 0;
}