【数据结构】顺序表/链表的运算及实现 |
您所在的位置：网站首页 › 顺序表的取元素操作 › 【数据结构】顺序表/链表的运算及实现 |
【数据结构】顺序表/链表的运算及实现
|
文章目录
前言
一、数据结构概念
1.1 数据
1.2 数据元素
1.3 数据的逻辑结构
1.4 数据的存储结构
二、线性表
2.1 顺序表
2.1.1 顺序存储结构特点
2.1.2 顺序存储结构表示
2.1.3 线性表的基本运算
2.1.4 顺序表的实现
2.1 链表
2.2.1 链式存储结构
2.2.2 结点类型描述
2.2.3 链表的基本运算
2.2.4 链表实现
前言
1968年美国克努特教授开创了数据结构的最初体系，著作为《计算机程序设计的艺术》。 数据结构研究计算机数据间关系，具体包括数据的逻辑结构、存储结构及数据间运算（操作）； 即数据结构把一些复杂的数据理清逻辑关系及存储方式，使其操作更加高效； 数据结构意义：提高编程能力；可复用；维护；可读性；效率； 需要掌握知识：结构体、内存体（malloc）等。 数据及信息的载体，是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。 1.2 数据元素数据元素是数据的基本单位，又称为记录，数据元素由若干基本项（或称字段、域、属性）组成。 例如：产品编号 产品名称 规格 出厂日期 … 0001 TV 29 1999/09… 数据元素之间存在某种关系：线性关系、层次关系（如上下级）、网状关系 1.3 数据的逻辑结构逻辑结构 表示数据运算之间的抽象关系，按每个元素可能具有的直接前驱数和直接后继数将数据结构分为“线性结构”和“非线性结构”两大类。 数据元素是一个集合 线性结构——一个对一个，如线性表、栈、队列 树形结构——一个对多个，如树 图状结构——多个对多个，如图 1.4 数据的存储结构存储结构：逻辑结构在计算机中的具体实现方法。 存储结构是通过计算机语言所编制的程序来实现的，因而是依赖于具体的计算机语言的。 1）顺序存储：将数据结构中各元素按照其逻辑顺序存放于存储器的一片连续的存储空间中；如c语言的一维数组，如表L=（a1,a2,…an）的顺序结构。 **2）链式存储**：将数据结构中各元素分布到存储器的不同点，用地址（或链指针）方式建立它们之间的联系；如：a1 -> a2 -> … ->an 数据结构中元素之间的关系在计算机内部很大程度上是通过地址或指针中来建立的。 3）索引存储：在存储数据的同时，建立一个附加的索引表，即索引存储结构=数据文件+索引表。 4）散列存储：根据数据元素的特殊字段（称为关键字key），计算数据元素的存放地址，然后数据元素按地址存放。 二、线性表线性表是包含若干数据元素的一个线性序列。 即为：L=(a0,…ai-1,ai,ai+1,…an-1)；L为表名；ai为数据元素；n为表长，n>0时，线性表L为非空表，否则为空表。 线性表L可用二元组形式描述：L=(D,R)；即线性表L包含数据元素集合D和关系集合R 关系符被称为有序对，ai是ai+1的直接前驱，ai+1是ai的直接后继。 O-O-O-O-O 线性表的特征： 1）对非空表，a0是表头，无前驱 2）an-1是表尾，无后继； 3）其它的每个元素ai有且仅有一个直接前驱ai-1和一个直接后继ai+1。 2.1 顺序表若将线性表L=（a0,a1,…an-1）中的各元素依此存储于计算机一片连续的存储空间； 设Loc(ai)为ai的地址，Loc(a0)=b,每个元素占d个单元，则Loc(ai)=b+i*d 2.1.1 顺序存储结构特点优点： 1）逻辑上相邻的元素ai,ai+1，其存储位置也是相邻的； 2）对数据元素ai的存取为随机存取或按地址存取； 3）存储密度高；存储密度D=(数据结构中元素所占存储空间) / （整个数据结构所占空间）。 不足： 1）要求系统提供一片较大的连续存储空间； 2）对表的插入和删除等运算的时间复杂度较差，且存在元素在存储器中成片移动的现象。 2.1.2 顺序存储结构表示在c语言中，可借助于一维数组类型来描述线性表的顺序存储结构（顺序表）。 顺序表代码如下（示例）： #define N 100 typedef int data_t; //typedef使得类型（如int）可灵活；data_t是int别名 typedef struct { //typedef，两个成员，一个代表数据是存储元素的，另一个代表实际的有效的最后那个元素的下标 data_t data[N]; int last; //last是记录最后一个元素下标，属于0-100 }sqlist,*sqlink; //sqlist是结构体，*sqlink是结构体指针 2.1.3 线性表的基本运算设线性表L=（a0,a1,…an-1），对L的基本运算有： 1）建立一个空表：L list_create()； 2）置空表：list_clear（L）； 3）判断表是否为空：list_empty（L）。若表为空，返回值为1，否则返回0； 4）求表长：length（L）; 5）取表中某个元素：GetList（L，i），即ai。要求01.1 main文件： #include #include "sqlist.h" void test_insert();//封装 测试insert函数 int main(int argc, char *argv[]) { test_insert(); return 0; } void test_insert() { sqlink L; L=list_create(); if (L == NULL) return; list_insert(L, 10, 0); //插入10 list_insert(L, 20, 0); //插入20 list_insert(L, 30, 0); //插入30 list_insert(L, 40, 0); //插入40 list_insert(L, 50, 0); //插入50 list_insert(L, 60, 0); //0插入60 //依次往后移，结果为60 50 40 30 20 10 list_show(L); list_insert(L, 100, list_length(L)); //目前长度为6，=（L,100,6） list_insert(L,100,-10000); //无效 list_show(L); list_free(L); }>1.2 函数代码.c文件： #include #include "sqlist.h" #include #include sqlink list_create() { //malloc 第一步申请内存 sqlink L; //sqlink结构体指针 L =(sqlink)malloc(sizeof(sqlist)); //sqlist代表整个结构体 if (L == NULL) //判断是否成功 { printf("list malloc failed\n"); return L; } //initialize 第二步初始化 memset(L, 0, sizeof(sqlist)); //清零 L->last = -1; //L是结构体，结构体指针访问结构体成员用箭头 //return 第三步返回值 return L; } //返回0 success -1 failed int list_clear(sqlink L) { if (L == NULL) return -1; memset(L, 0, sizeof(sqlist)); //填充0 L->last = -1; //表示为空表 return 0; } int list_free(sqlink L) //释放空间 { if (L == NULL) return -1; free(L); L = NULL; return 0; } //check list empty? 1-empty 0-not empty int list_empty(sqlink L) { if (L->last == -1) return 1; else return 0; } int list_length(sqlink L) { if (L == NULL) return -1; return (L->last+1); } // -1 not exit;判断value在不在线性表中 int list_locate(sqlink L,data_t value) { int i; for (i=0;ilast;i++) { if (L->data[i] == value) return i; } return -1; } int list_insert(sqlink L, data_t value, int pos) { int i; //1) judge full if (L->last == N-1) { printf("list is full\n"); return -1; } //2)check para pos 0 |
【本文地址】
今日新闻 |
推荐新闻 |