线性表(顺序表和链表)

🕗 发布于 2024-11-10 06:35 算法 数据结构

前言


#include <stdio.h>
#include <string.h>
typedef struct{
int isbn;
char bookName[20];
double price;

}book;

int main()
{
book b;
b.isbn=121212;
strcpy(b.bookName,"程序设计基础");
b.price=34.7;
printf("书名:%s",b.bookName);
   
   return 0;
}

顺序表

#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
typedef struct{
ElemType data[MAXSIZE];
int length; 
}SeqList;

void initList(SeqList* L){
L->length=0;
}



int appendElem(SeqList* L,ElemType e){
if(L->length>=MAXSIZE){
printf("顺序表已经满了\n");
return 0;
}
L->data[L->length]=e;
L->length++;
return 1;
}

int insertElem(SeqList *L,int pos,ElemType e){
if(L->length>=MAXSIZE){
printf("顺序表已经满了\n");
return 0;
}
if(pos<1||pos>L->length){
printf("插入位置错误\n");
return 0;
}

if(pos <= L->length){
for(int i=L->length-1;i>=pos-1;i--){
L->data[i+1]=L->data[i];
}
L->data[pos-1]=e;
L->length++;
}
return 1;
}

int deleteElem(SeqList *L,int pos,ElemType* e){
if(L->length==0){
printf("空表\n");
return 0;
}

if(pos<1 || pos>L->length){
printf("删除数据位置有误\n");
return 0;
}

*e=L->data[pos-1];
if(pos<L->length){
for (int i=pos;i<L->length;i++){
L->data[i-1]=L->data[i];
}

}
L->length--;
return 1;

}

int findElem(SeqList *L,ElemType e){
for(int i=0;i<L->length;i++){
if(L->data[i]==e){
return i+1;
}
}
return 0;
}

void listElem(SeqList *L){
for(int i=0;i<L->length;i++){
printf("%d ",L->data[i]);
}
printf("\n");
}


int main()
{
//顺序表初始化
SeqList list;
initList(&list);
printf("初始化成功,目前长度占用%d\n",list.length);
printf("目前占用内存%zu字节\n",sizeof(list.data));

//添加元素
appendElem(&list,88);
appendElem(&list,55);
appendElem(&list,77);
appendElem(&list,22);
listElem(&list);

//插入元素  最好时间复杂度O(1) 最坏时间复杂度O(n)
insertElem(&list,2,18);
listElem(&list);

//删除元素
ElemType delData;
deleteElem(&list,4,&delData);
printf("被删除的数据为:%d\n",delData);
listElem(&list);

//查找
printf("%d\n",findElem(&list,18));

   
   return 0;
}

顺序表的动态初始化

#include <stdio.h>
#include<stdlib.h> //malloc
#include <string.h>
#define MAXSIZE 100
typedef int ElemType;
//动态分配内存地址初始化 
//只是在初始化和定义上不同 在堆内存中
typedef struct{
ElemType *data;
int length;
}SeqList;

SeqList* initList(){
SeqList* L=(SeqList*)malloc(sizeof(SeqList));
L->data=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
L->length=0;
return L;
}


int appendElem(SeqList* L,ElemType e){
if(L->length>=MAXSIZE){
printf("顺序表已经满了\n");
return 0;
}
L->data[L->length]=e;
L->length++;
return 1;
}

int insertElem(SeqList *L,int pos,ElemType e){
if(L->length>=MAXSIZE){
printf("顺序表已经满了\n");
return 0;
}
if(pos<1||pos>L->length){
printf("插入位置错误\n");
return 0;
}

if(pos <= L->length){
for(int i=L->length-1;i>=pos-1;i--){
L->data[i+1]=L->data[i];
}
L->data[pos-1]=e;
L->length++;
}
return 1;
}

int deleteElem(SeqList *L,int pos,ElemType* e){
if(L->length==0){
printf("空表\n");
return 0;
}

if(pos<1 || pos>L->length){
printf("删除数据位置有误\n");
return 0;
}

*e=L->data[pos-1];
if(pos<L->length){
for (int i=pos;i<L->length;i++){
L->data[i-1]=L->data[i];
}

}
L->length--;
return 1;

}

int findElem(SeqList *L,ElemType e){
for(int i=0;i<L->length;i++){
if(L->data[i]==e){
return i+1;
}
}
return 0;
}

void listElem(SeqList *L){
for(int i=0;i<L->length;i++){
printf("%d ",L->data[i]);
}
printf("\n");
}


int main()
{
//顺序表初始化
SeqList* list =initList();
printf("初始化成功,目前长度占用%d\n",list->length);
printf("目前占用内存%zu字节\n",sizeof(list->data));

//添加元素
appendElem(list,88);
appendElem(list,55);
appendElem(list,77);
appendElem(list,22);
listElem(list);

//插入元素  最好时间复杂度O(1) 最坏时间复杂度O(n)
insertElem(list,2,18);
listElem(list);

//删除元素
ElemType delData;
deleteElem(list,4,&delData);
printf("被删除的数据为:%d\n",delData);
listElem(list);

//查找
printf("%d\n",findElem(list,18));

   
   return 0;
}

单链表

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
//定义
typedef struct node{
ElemType data;
struct node* next;
}Node;

//初始化
Node* initList(){
Node* head=(Node*)malloc(sizeof(Node));
head->data=0;
head->next=NULL;
return head;
}

//头插法
int insertHead(Node* L,ElemType e){
Node* p=(Node*)malloc(sizeof(Node));
p->data=e;
p->next=L->next;
L->next=p;
return 1;
}
Node* get_tail(Node* L){
Node* p=L;
while(p->next != NULL){
p=p->next;
}
return p;
}
//尾插法
Node* insertTail(Node* tail,ElemType e){
Node* p=(Node*)malloc(sizeof(Node));
p->data=e;
tail->next=p;
p->next=NULL;
return p;
}

//在指定位置插入数据
int insertNode(Node* L,int pos,ElemType e){
Node* p=L;
int i=0;
while(i<pos-1){
p=p->next;
i++;
if(p==NULL){
return 0;
}
}

//要插入的新节点
Node* q=(Node*)malloc(sizeof(Node));
q->data=e;
q->next=p->next;
p->next=q;
return 1;

}

//删除节点
int deleteNode(Node* L,int pos){
//p :要删除节点的前驱
Node* p=L;
int i=0;
while(i<pos-1){
p=p->next;
i++;
if(p==NULL){
return 0;
}
}

if(p->next ==NULL){
printf("要删除的位置错误!\n");
return 0;

}
//q指向要删除的节点
Node* q=p->next;
p->next=q->next;
free(q);
return 1;
}

//获取链表的长度
int listLength(Node* L){
Node* p=L;
int len=0;
while(p!=NULL){
p=p->next;
len++;
}
return len-1;
}


//释放链表
void freeList(Node* L){
Node* p=L->next;
Node* q;

while(p!=NULL){
q=p->next;
free(p);
p=q;
}
L->next=NULL;
}

//遍历
void listNode(Node* L){
Node* p=L->next;
while(p != NULL){
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}


int main()
{
  Node* list=initList();
// 头插法
// insertHead(list,10);
// insertHead(list,20);
// insertHead(list,30);
// listNode(list);

//尾插法
Node* tail=get_tail(list);
tail = insertTail(tail,10);
tail = insertTail(tail,20);
tail = insertTail(tail,30);
listNode(list);

//插入节点
insertNode(list,2,18);
listNode(list);

//删除节点
deleteNode(list,2);
listNode(list);

//获取链表的长度
int len=listLength(list);
printf("链表的长度:%d\n",len);

//释放链表
freeList(list);
int len2=listLength(list);
printf("链表的长度:%d\n",len2);

   return 0;
}

原文地址：https://blog.csdn.net/2401_85619378/article/details/143649588

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：短视频矩阵系统的源码， OEM贴牌源码
下一篇：【设计模式系列】享元模式（十五）

【网络安全】Cookie SameSite属性
严格限制可能会影响用户体验，例如，当用户点击 GitHub 链接时，无法保持登录状态，因为此时会丢失 GitHub 的 Cookie。当浏览器加载该图片时，它会向 A.com 发送带有 Cookie
阅读更多2024-11-16
【C语言】实现二维数组按行排序
【C语言】实现二维数组按行排序
阅读更多2024-11-16
NLP开发常见问题
NLP开发常见问题
阅读更多2024-11-16
在spring boot工程中使用Filter时，@WebFilter 注解不生效的问题分析和解决方案
如果要使用@WebFilter进行过滤路径的配置，则需要在启动类中添加@ServletComponentScan注解启用Servlet容器扫描@WebFilter注解，并删除Filter类中的@Com
阅读更多2024-11-16
天天学编程Day16
在 C++ 中，常量表达式（Constant Expression）是指在编译期就能计算出结果的表达式。其结果在程序运行过程中是不可改变的，并且这个结果必须是编译时常量，例如整数常量、枚举常量、用常量
阅读更多2024-11-16
消失的数字（c语言实现）
方法一我们使用异或操作符实现。介绍一下^操作符性质就是首先0^a=a；a^a=0;然后异或操作符还满足交换律。比如a ^ b ^ c ^a= a ^ a ^b ^c;我们可以通过这样的性质实现这个代
阅读更多2024-11-16
机器学习——期末复习重点题归纳
机器学习期末复习
阅读更多2024-11-16
opencv kdtree & pcl kdtree 效率对比
由于项目中以一个环节需要使用kdtree ,对性能要求比较严苛，所以看看那个kdtree效率高一些。对比了opencv和pcl。
阅读更多2024-11-16
Qt 5.6.3 手动配置 mingw 环境
手动设置 qt mingw 编译环境
阅读更多2024-11-16
IntelliJ IDEA 2024.3（Ultimate Edition）免费化教学
一款由 JetBrains 公司开发的集成开发环境 (Integrated Development Environment, IDE)，主要用于 Java 语言的软件开发，但它也支持其他多种编程语言和
阅读更多2024-11-16

线性表(顺序表和链表)

前言

顺序表

顺序表的动态初始化

单链表

相关文章