当前位置： 首页 > news >繁体>数据结构之线性表代码实现顺序存储，链式存储，静态链表（选自大话数据结构）...

数据结构之线性表代码实现顺序存储，链式存储，静态链表（选自大话数据结构）...

news 来源：原创 2023/3/28 4:51:53

一，线性表顺序存储

#include <stdio.h>   
#include <string.h>
#include <ctype.h>     
#include <stdlib.h>   
#include <io.h> 
#include <math.h>
#include <time.h>#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status;          /* Status是函数的类型,其值是函数结果状态代码。如OK等 */
typedef int ElemType;        /* ElemType类型依据实际情况而定，这里如果为int */Status visit(ElemType c)
{printf("%d ",c);return OK;
}typedef struct
{ElemType data[MAXSIZE];        /* 数组，存储数据元素 */int length;                                /* 线性表当前长度 */
}SqList;/* 初始化顺序线性表 */
Status InitList(SqList *L) 
{ L->length=0;return OK;
}/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(SqList L)
{ if(L.length==0)return TRUE;elsereturn FALSE;
}/* 初始条件：顺序线性表L已存在。

操作结果：将L重置为空表 */ Status ClearList(SqList *L) { L->length=0; return OK; } /* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */ int ListLength(SqList L) { return L.length; } /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置。第1个位置的数组是从0開始 */ Status GetElem(SqList L,int i,ElemType *e) { if(L.length==0 || i<1 || i>L.length) return ERROR; *e=L.data[i-1]; return OK; } /* 初始条件：顺序线性表L已存在 */ /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */ /* 若这种数据元素不存在。则返回值为0 */ int LocateElem(SqList L,ElemType e) { int i; if (L.length==0) return 0; for(i=0;i<L.length;i++) { if (L.data[i]==e) break; } if(i>=L.length) return 0; return i+1; } /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ Status ListInsert(SqList *L,int i,ElemType e) { int k; if (L->length==MAXSIZE) /* 顺序线性表已经满 */ return ERROR; if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */ return ERROR; if (i<=L->length) /* 若插入数据位置不在表尾 */ { for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */ L->data[k+1]=L->data[k]; } L->data[i-1]=e; /* 将新元素插入 */ L->length++; return OK; } /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */ Status ListDelete(SqList *L,int i,ElemType *e) { int k; if (L->length==0) /* 线性表为空 */ return ERROR; if (i<1 || i>L->length) /* 删除位置不对 */ return ERROR; *e=L->data[i-1]; if (i<L->length) /* 如果删除不是最后位置 */ { for(k=i;k<L->length;k++)/* 将删除位置后继元素前移 */ L->data[k-1]=L->data[k]; } L->length--; return OK; } /* 初始条件：顺序线性表L已存在 */ /* 操作结果：依次对L的每一个数据元素输出 */ Status ListTraverse(SqList L) { int i; for(i=0;i<L.length;i++) visit(L.data[i]); printf("\n"); return OK; } void unionL(SqList *La,SqList Lb) { int La_len,Lb_len,i; ElemType e; La_len=ListLength(*La); Lb_len=ListLength(Lb); for (i=1;i<=Lb_len;i++) { GetElem(Lb,i,&e); if (!LocateElem(*La,e)) ListInsert(La,++La_len,e); } } int main() { SqList L; SqList Lb; ElemType e; Status i; int j,k; i=InitList(&L); printf("初始化L后：L.length=%d\n",L.length); for(j=1;j<=5;j++) i=ListInsert(&L,1,j); printf("在L的表头依次插入1～5后：L.data="); ListTraverse(L); printf("L.length=%d \n",L.length); i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否)\n",i); i=ClearList(&L); printf("清空L后：L.length=%d\n",L.length); i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否)\n",i); for(j=1;j<=10;j++) ListInsert(&L,j,j); printf("在L的表尾依次插入1～10后：L.data="); ListTraverse(L); printf("L.length=%d \n",L.length); ListInsert(&L,1,0); printf("在L的表头插入0后：L.data="); ListTraverse(L); printf("L.length=%d \n",L.length); GetElem(L,5,&e); printf("第5个元素的值为：%d\n",e); for(j=3;j<=4;j++) { k=LocateElem(L,j); if(k) printf("第%d个元素的值为%d\n",k,j); else printf("没有值为%d的元素\n",j); } k=ListLength(L); /* k为表长 */ for(j=k+1;j>=k;j--) { i=ListDelete(&L,j,&e); /* 删除第j个数据 */ if(i==ERROR) printf("删除第%d个数据失败\n",j); else printf("删除第%d个的元素值为：%d\n",j,e); } printf("依次输出L的元素："); ListTraverse(L); j=5; ListDelete(&L,j,&e); /* 删除第5个数据 */ printf("删除第%d个的元素值为：%d\n",j,e); printf("依次输出L的元素："); ListTraverse(L); //构造一个有10个数的Lb i=InitList(&Lb); for(j=6;j<=15;j++) i=ListInsert(&Lb,1,j); unionL(&L,Lb); printf("依次输出合并了Lb的L的元素："); ListTraverse(L); return 0; }




二，线性表链式存储

#include <stdio.h>   
#include <string.h>
#include <ctype.h>     
#include <stdlib.h>   
#include <io.h> 
#include <math.h>
#include <time.h>#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 20 /* 存储空间初始分配量 */typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型依据实际情况而定，这里如果为int */Status visit(ElemType c)
{printf("%d ",c);return OK;
}typedef struct Node
{ElemType data;struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList *//* 初始化顺序线性表 */
Status InitList(LinkList *L) 
{ *L=(LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */if(!(*L)) /* 存储分配失败 */return ERROR;(*L)->next=NULL; /* 指针域为空 */return OK;
}/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(LinkList L)
{ if(L->next)return FALSE;elsereturn TRUE;
}/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{ LinkList p,q;p=(*L)->next;           /*  p指向第一个结点 */while(p)                /*  没到表尾 */{q=p->next;free(p);p=q;}(*L)->next=NULL;        /* 头结点指针域为空 */return OK;
}/* 初始条件：顺序线性表L已存在。

操作结果：返回L中数据元素个数 */ int ListLength(LinkList L) { int i=0; LinkList p=L->next; /* p指向第一个结点 */ while(p) { i++; p=p->next; } return i; } /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */ /* 操作结果：用e返回L中第i个数据元素的值 */ Status GetElem(LinkList L,int i,ElemType *e) { int j; LinkList p; /* 声明一结点p */ p = L->next; /* 让p指向链表L的第一个结点 */ j = 1; /* j为计数器 */ while (p && j<i) /* p不为空或者计数器j还没有等于i时，循环继续 */ { p = p->next; /* 让p指向下一个结点 */ ++j; } if ( !p || j>i ) return ERROR; /* 第i个元素不存在 */ *e = p->data; /* 取第i个元素的数据 */ return OK; } /* 初始条件：顺序线性表L已存在 */ /* 操作结果：返回L中第1个与e满足关系的数据元素的位序。

*/ /* 若这种数据元素不存在，则返回值为0 */ int LocateElem(LinkList L,ElemType e) { int i=0; LinkList p=L->next; while(p) { i++; if(p->data==e) /* 找到这种数据元素 */ return i; p=p->next; } return 0; } /* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */ /* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */ Status ListInsert(LinkList *L,int i,ElemType e) { int j; LinkList p,s; p = *L; j = 1; while (p && j < i) /* 寻找第i个结点 */ { p = p->next; ++j; } if (!p || j > i) return ERROR; /* 第i个元素不存在 */ s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */ s->data = e; s->next = p->next; /* 将p的后继结点赋值给s的后继 */ p->next = s; /* 将s赋值给p的后继 */ return OK; } /* 初始条件：顺序线性表L已存在。1≤i≤ListLength(L) */ /* 操作结果：删除L的第i个数据元素。并用e返回其值。L的长度减1 */ Status ListDelete(LinkList *L,int i,ElemType *e) { int j; LinkList p,q; p = *L; j = 1; while (p->next && j < i) /* 遍历寻找第i个元素 */ { p = p->next; ++j; } if (!(p->next) || j > i) return ERROR; /* 第i个元素不存在 */ q = p->next; p->next = q->next; /* 将q的后继赋值给p的后继 */ *e = q->data; /* 将q结点中的数据给e */ free(q); /* 让系统回收此结点。释放内存 */ return OK; } /* 初始条件：顺序线性表L已存在 */ /* 操作结果：依次对L的每一个数据元素输出 */ Status ListTraverse(LinkList L) { LinkList p=L->next; while(p) { visit(p->data); p=p->next; } printf("\n"); return OK; } /* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */ void CreateListHead(LinkList *L, int n) { LinkList p; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; /* 先建立一个带头结点的单链表 */ for (i=0; i<n; i++) { p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ p->next = (*L)->next; (*L)->next = p; /* 插入到表头 */ } } /* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */ void CreateListTail(LinkList *L, int n) { LinkList p,r; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */ r=*L; /* r为指向尾部的结点 */ for (i=0; i<n; i++) { p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ r->next=p; /* 将表尾终端结点的指针指向新结点 */ r = p; /* 将当前的新结点定义为表尾终端结点 */ } r->next = NULL; /* 表示当前链表结束 */ } int main() { LinkList L; ElemType e; Status i; int j,k; i=InitList(&L); printf("初始化L后：ListLength(L)=%d\n",ListLength(L)); for(j=1;j<=5;j++) i=ListInsert(&L,1,j); printf("在L的表头依次插入1～5后：L.data="); ListTraverse(L); printf("ListLength(L)=%d \n",ListLength(L)); i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否)\n",i); i=ClearList(&L); printf("清空L后：ListLength(L)=%d\n",ListLength(L)); i=ListEmpty(L); printf("L是否空：i=%d(1:是 0:否)\n",i); for(j=1;j<=10;j++) ListInsert(&L,j,j); printf("在L的表尾依次插入1～10后：L.data="); ListTraverse(L); printf("ListLength(L)=%d \n",ListLength(L)); ListInsert(&L,1,0); printf("在L的表头插入0后：L.data="); ListTraverse(L); printf("ListLength(L)=%d \n",ListLength(L)); GetElem(L,5,&e); printf("第5个元素的值为：%d\n",e); for(j=3;j<=4;j++) { k=LocateElem(L,j); if(k) printf("第%d个元素的值为%d\n",k,j); else printf("没有值为%d的元素\n",j); } k=ListLength(L); /* k为表长 */ for(j=k+1;j>=k;j--) { i=ListDelete(&L,j,&e); /* 删除第j个数据 */ if(i==ERROR) printf("删除第%d个数据失败\n",j); else printf("删除第%d个的元素值为：%d\n",j,e); } printf("依次输出L的元素："); ListTraverse(L); j=5; ListDelete(&L,j,&e); /* 删除第5个数据 */ printf("删除第%d个的元素值为：%d\n",j,e); printf("依次输出L的元素："); ListTraverse(L); i=ClearList(&L); printf("\n清空L后：ListLength(L)=%d\n",ListLength(L)); CreateListHead(&L,20); printf("总体创建L的元素(头插法)："); ListTraverse(L); i=ClearList(&L); printf("\n删除L后：ListLength(L)=%d\n",ListLength(L)); CreateListTail(&L,20); printf("总体创建L的元素(尾插法)："); ListTraverse(L); return 0; }



3。静态链表

#include <string.h>
#include <ctype.h>     #include <stdio.h>  
#include <stdlib.h> 
#include <io.h> 
#include <math.h> 
#include <time.h>#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0#define MAXSIZE 1000 /* 存储空间初始分配量 */typedef int Status;           /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char ElemType;        /* ElemType类型依据实际情况而定，这里如果为char */Status visit(ElemType c)
{printf("%c ",c);return OK;
}/* 线性表的静态链表存储结构 */
typedef struct 
{ElemType data;int cur;  /* 游标(Cursor) 。为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
Status InitList(StaticLinkList space) 
{int i;for (i=0; i<MAXSIZE-1; i++)  space[i].cur = i+1;space[MAXSIZE-1].cur = 0; /* 眼下静态链表为空，最后一个元素的cur为0 */return OK;
}/* 若备用空间链表非空，则返回分配的结点下标。否则返回0 */
int Malloc_SSL(StaticLinkList space) 
{ int i = space[0].cur;           		/* 当前数组第一个元素的cur存的值 *//* 就是要返回的第一个备用空暇的下标 */if (space[0]. cur)         space[0]. cur = space[i].cur;       /* 因为要拿出一个分量来使用了。 *//* 所以我们就得把它的下一个 *//* 分量用来做备用 */return i;
}/*  将下标为k的空暇结点回收到备用链表 */
void Free_SSL(StaticLinkList space, int k) 
{  space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */
}/* 初始条件：静态链表L已存在。

操作结果：返回L中数据元素个数 */ int ListLength(StaticLinkList L) { int j=0; int i=L[MAXSIZE-1].cur; while(i) { i=L[i].cur; j++; } return j; } /* 在L中第i个元素之前插入新的数据元素e */ Status ListInsert(StaticLinkList L, int i, ElemType e) { int j, k, l; k = MAXSIZE - 1; /* 注意k首先是最后一个元素的下标 */ if (i < 1 || i > ListLength(L) + 1) return ERROR; j = Malloc_SSL(L); /* 获得空暇分量的下标 */ if (j) { L[j].data = e; /* 将数据赋值给此分量的data */ for(l = 1; l <= i - 1; l++) /* 找到第i个元素之前的位置 */ k = L[k].cur; L[j].cur = L[k].cur; /* 把第i个元素之前的cur赋值给新元素的cur */ L[k].cur = j; /* 把新元素的下标赋值给第i个元素之前元素的ur */ return OK; } return ERROR; } /* 删除在L中第i个数据元素 */ Status ListDelete(StaticLinkList L, int i) { int j, k; if (i < 1 || i > ListLength(L)) return ERROR; k = MAXSIZE - 1; for (j = 1; j <= i - 1; j++) k = L[k].cur; j = L[k].cur; L[k].cur = L[j].cur; Free_SSL(L, j); return OK; } Status ListTraverse(StaticLinkList L) { int j=0; int i=L[MAXSIZE-1].cur; while(i) { visit(L[i].data); i=L[i].cur; j++; } return j; printf("\n"); return OK; } int main() { StaticLinkList L; Status i; i=InitList(L); printf("初始化L后：L.length=%d\n",ListLength(L)); i=ListInsert(L,1,'F'); i=ListInsert(L,1,'E'); i=ListInsert(L,1,'D'); i=ListInsert(L,1,'B'); i=ListInsert(L,1,'A'); printf("\n在L的表头依次插入FEDBA后：\nL.data="); ListTraverse(L); i=ListInsert(L,3,'C'); printf("\n在L的“B”与“D”之间插入“C”后：\nL.data="); ListTraverse(L); i=ListDelete(L,1); printf("\n在L的删除“A”后：\nL.data="); ListTraverse(L); printf("\n"); return 0; }




转载于:https://www.cnblogs.com/gccbuaa/p/7380810.html

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://dhexx.cn/news/show-18391.html

如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网进行投诉反馈，一经查实，立即删除！


相关文章：

  • Eclipse断点种类
  • 文字超长隐藏为...ie7不兼容的解决办法
  • 《跨界杂谈》商业模式（三）：黑帮
  • A+B Problem（再升级）
  • 自定义异步加载资源插件
  • sublime test3 安装及配置
  • 解决修改完系统默认python版本后yum不可用的问题!!!!!!
  • windows下git安装配置
  • 基于数组实现Java 自定义Stack栈类及应用
  • python:关于三级菜单的新手实现
  • java的几个概念AOP、IOC、DI、DIP、工厂模式、IOC容器
  • servlet中doGet()和doPost()的区别
  • mysql-改表名
  • 使用 artTemplate 渲染数组
  • ajax取消重复请求
  • 夏令营讲课内容整理 Day 6 Part 3.
  • 201671010133 2016-2017-2 《java程序设计》 初学java！
  • 递归系列——数组和对象的相关递归
  • 【linux】安装python依赖库confluent_kafka
  • 也来谈谈IT培训
  • JMeter数据库操作详解
  • 20170830 - A - Java IO操作
  • 《XHTML》pdf
  • C++primer 13.1.2节练习
  • PyQt5学习笔记
  • 递归系列——递归树与函数记忆化
  • Laravel 学习笔记之文件上传
  • Microsoft Access 2002中文版标准培训教程pdf
  • Python_日记 序列化和反序列化
  • python--简易员工信息系统编写
  • 洛谷 P2383 狗哥玩木棒
  • 充值，提现功能涉及的多线程、队列问题
  • 始终显示滚动条
  • 16汇编第十讲完结Call变为函数以及指令的最后讲解
  • 流畅的python和cookbook学习笔记（五）
  • 第三百七十六节，Django+Xadmin打造上线标准的在线教育平台—创建用户操作app，在models.py文件生成5张表，用户咨询表、课程评论表、用户收藏表、用户消息表、用户学习表...
  • Effective Objective-C 的读书笔记
  • Kaldi语料的两种切分/组织方式及其处理
  • Head First设计模式之命令模式
  • 安装debian 9.1后，中文环境下将home目录下文件夹改为对应的英文
  • 加密算法IV的作用
  • SpringBoot 分布式session
  • 9，求整数的二进制中1的个数《剑指offer》
  • FastJson（阿里巴巴）基础
  • struts入门实例
  • 软件工程第二次作业——个人项目
  • C# 5.0 CallerMemberName CallerFilePath CallerLineNumber获取调用方法名称，路径，行号
  • 《结对-航空购票系统-开发环境搭建过程》
  • 20170831_安装软件
  • 寻找Harris、Shi-Tomasi和亚像素角点