--- 恢复内容开始 ---
推荐一本学习书籍: 程杰的大话数据结构.
既然是数据结构, 那什么是数据结构呢? 这里补充一些基本术语和概念.
数据结构: 是一门研究非数值计算的程序设计问题中的操作对象, 以及它们之间的关系和操作等相关问题的学科.
数据: 是描述客观事物的符号, 是计算机中可以操作的对象, 是能被计算机识别, 并输入给计算机处理的符号总集.
数据元素: 是组成数据, 有一定意义的基本单位, 在计算机中通常作为整体处理. 也成为记录.
数据项: 一个数据元素可以由若干个数据项组成. 数据项是数据不可分割的最小单位.
数据对象: 是性质相同的数据元素的集合, 是数据的子集.
数据结构: 是相互之间存在一种或多种特定关系的数据元素的集合.
逻辑结构: 是指数据对象中数据元素之间的相互关系.
集合结构: 集合结构中的数据元素除了属于同一个集合外, 它们之间没有其他关系.
线性结构: 线性结构中的数据元素之间是一对一的关系.
树形结构: 树形结构中的数据元素之间存在一种一对多的层次关系.
图形结构: 图形结构的数据元素是多对多的关系.
物理结构: 是指数据的逻辑结构在计算机中的存储形式
顺序存储结构: 是把数据元素存放在地址连续的存储单元里, 其数据将的逻辑关系和物理关系是一致的.
链式存储结构: 是把数据元素存放在任意的存储单元里, 这组存储单元可以是连续的, 也可以是不连续的.
数据类型: 是指一组性质相同的值的集合及定义在此集合上的一些操作的总称.
抽象数据类型: 是指一个数学模型及定义在该模型上的一组操作.
算法: 是解决特定问题求解步骤的描述, 在计算机中表现为指令的有限序列, 并且每条指令表示一个或多个操作.
算法的 5 个基本特性: 输入, 输出, 有穷性, 确定性和可行性.
本篇学习线性表, 线性表是什么?
线性表 (List): 零个或多个数据元素的有限序列.
头部定义 (seq_header.h)
- #include<stdio.h>
- #include<stdlib.h>
- #define maxsize 100
- #define ok 1
- #define error 0
- #define true 1
- #define false 0
- typedef int status;
- typedef int elemType;
- typedef struct{
- elemType data[maxsize];
- int length;//current length of Sqlist
- }SqList;
线性表操作函数 (seq_func.h)
- /* 输出指定数据 */
- status visit(elemType e){
- printf("%d", e);
- return ok;
- }
- /* 判断线性表是否为空 */
- status listEmpty(SqList L){
- if(L.length == 0)
- return true;
- else
- return false;
- }
- /* 清除线性表 */
- status clearList(SqList *L){
- L->length = 0;
- return ok;
- }
- /* 返回线性表数据元素个数 */
- int listLength(SqList L){
- return L.length;
- }
- /* 初始条件: 顺序线性表 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;
- }
- /**
- Status: if ok return OK(=1)
- Condition: SqList already exists, 1 <= i <= ListLength(SqList)
- Result: use e to return the index of i value in SqList
- */
- 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;
- }
- /* 初始化顺序线性表 */
- status initList(SqList *L){
- L->length = 0;
- return ok;
- }
- /* 初始条件: 顺序线性表 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)/* 插入的位置超过范围 */
- 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 已存在 */
- /* 操作结果: 依次对 L 的每个数据元素输出 */
- status listTrave(SqList L){
- int i;
- for(i = 0; i<L.length; i++)
- visit(L.data[i]);
- printf("\n");
- 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;
- }
- /* 将后一个线性表合并到前一个线性表上 */
- 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);
- }
- }
主函数测试 (main.cpp)
- #include "seq_header.h"
- #include "seq_func.h"
- int main(){
- SqList L;// 定义一个顺序线性表
- 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, j, j);
- printf("在 L 的表头依次插入 1~5 后: L.data =");
- listTrave(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, 1, j);
- printf("在 L 的表尾依次插入 1~10 后: L.data=");
- listTrave(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);
- }
- j = 5;
- listDelete(&L, j ,&e);
- printf("删除第 %d 个元素值为:%d\n", j, e);
- printf("依次输出 L 的元素:");
- listTrave(L);
- // 构造一个有 10 个数的 Lb
- SqList Lb;
- i = initList(&Lb);
- for(j=6; j<= 15; j++){
- i = listInsert(&Lb, 1, j);
- }
- unionL(&L, Lb);
- printf("依次输出了合并了 Lb 的 L 的元素:");
- listTrave(L);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2608839.html