当前位置：首页 > news >正文

顺序表和单链表的代码实现

news 来源：原创 2024/9/20 7:28:31

代码位置：数据结构: 总结 - Gitee.com

需要代码并且需要运行结果的可以进入链接自行领取。

顺序表：是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

链表：是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

1.SeqList.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDataType;
#define INIT_CAPACITY 4typedef struct S
{SLDataType* a;int sz;int capacity;
}SL;//顺序表的初始化
void SLInit(SL* pc);//尾插
void SLPushBack(SL* pc,SLDataType x);//尾删
//void SLPopback(SL* pc);//扩容
void SLCheckCapacity(SL* pc);//插入
void SLInsert(SL* pc,int pos,SLDataType x);//查找
void SLFine(SL* pc, SLDataType x);//删除
void SLErase(SL* pc, int pos);//打印
void SLPrint(SL* pc);//修改
void SLModify(SL* pc, int pos, SLDataType x);//销毁
void SLDestroy(SL* pc);

2.Seqlist.c

#define _CRT_SECURE_NO_WARNINGS 1#include"SeqList.h"void SLCheckCapacity(SL* pc)
{assert(pc);if (pc->sz == pc->capacity){SLDataType* tmp = (SLDataType*)realloc(pc->a, sizeof(SLDataType) * pc->capacity * 2);if (tmp == NULL){perror("realloc");return;}pc->a = tmp;pc->capacity *= 2;}
}void SLInit(SL* pc)
{pc->a = (SLDataType*)malloc(sizeof(SLDataType*)*INIT_CAPACITY);if (pc->a == NULL){perror("malloc");return;}pc->sz = 0;pc->capacity = INIT_CAPACITY;
}void SLPushBack(SL* pc,SLDataType x)
{SLCheckCapacity(pc);pc->a[pc->sz] = x;pc->sz++;
}void SLPrint(SL* pc)
{for (int i = 0; i < pc->sz; i++){printf("%d ", pc->a[i]);}printf("\n");
}void SLDestroy(SL* pc)
{assert(pc);free(pc->a);pc->a = NULL;pc->sz = pc->capacity = 0;
}void SLInsert(SL* pc,int pos, SLDataType x)
{assert(pc);assert(pos >= 0 && pos <= pc->sz);//扩容SLCheckCapacity(pc);int end = pc->sz - 1;while (end >= pos){pc->a[end + 1] = pc->a[end];end--;}pc->a[pos] = x;pc->sz++;
}void SLErase(SL* pc,int pos)
{assert(pc);assert(pos >= 0 && pos < pc->sz);int begin = pos;while (begin < pc->sz - 1){pc->a[begin] = pc->a[begin + 1];begin++;}pc->sz--;
}void SLFine(SL* pc, SLDataType x)
{assert(pc);for (int i = 0; i < pc->sz; i++){if(pc->a[i] == x)return i;}return -1;
}void SLModify(SL* pc, int pos, SLDataType x)
{assert(pc);assert(pos >= 0 && pos < pc->sz);pc->a[pos] = x;
}

链表的实现

1.SList.h

#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTistDataType;typedef struct SListNode
{SLTistDataType data;struct SListNode* next;
}SLTNode;//打印
void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTistDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头插
void SLTPushFront(SLTNode** pphead, SLTistDataType x);//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTistDataType x);//在pos前插入
void SLTInsert(SLTNode** pphead, SLTNode *pos, SLTistDataType x);//在pos处删除
void SLTErase(SLTNode** pphead, SLTNode* pos);

2.SList.c

#define _CRT_SECURE_NO_WARNINGS 1#include"SList.h"void SLTPrint(SLTNode* phead)
{SLTNode* str = phead;while (str){printf("%d->", str->data);str = str->next;}printf("NULL\n");
}SLTNode* NewSLTNode(SLTistDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}void SLTPushBack(SLTNode** pphead, SLTistDataType x)
{SLTNode* tail = *pphead;/*SLTNode* newnode=(SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc");return;}*/SLTNode* newnode = NewSLTNode(x);if (*pphead == NULL){*pphead = newnode;}else{while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}/*newnode->data = x;newnode->next = NULL;*/
}void SLTPopBack(SLTNode** pphead)
{//断言assert(*pphead);if (*pphead == NULL){return;}if ((*pphead)->next = NULL){free(*pphead);*pphead = NULL;return;}else{/*SLTNode* pre = *pphead;SLTNode* tail = *pphead;while (tail->next != NULL){pre = tail;tail = tail->next;}free(tail);tail = NULL;pre->next = NULL;*/SLTNode* tail = *pphead;while (tail->next->next != NULL){tail = tail->next;}free(tail->next);tail->next = NULL;}
}void SLTPushFront(SLTNode** pphead, SLTistDataType x)
{SLTNode* newnode = NewSLTNode(x);newnode->next = *pphead;*pphead = newnode;
}void SLTPopFront(SLTNode** pphead)
{//暴力检查assert(*pphead);if (*pphead == NULL){return;}/*SLTNode* frist = *pphead;*pphead = frist->next;free(frist);frist = NULL;*/SLTNode* frist = *pphead;*pphead = (*pphead)->next;free(frist);frist = NULL;
}SLTNode* SLTFind(SLTNode* phead, SLTistDataType x)
{SLTNode* cur = phead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode *pos, SLTistDataType x)
{assert(pos);assert(pphead);if (pos == *pphead){SLTPushFront(pphead, x);}else{// 找到pos的前一个位置SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}SLTNode* newnode = NewSLTNode(x);prev->next = newnode;newnode->next = pos;}
}void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);assert(*pphead);if (pos = *pphead){SLTPopFront(pphead);}SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;free(pos);pos = NULL;}