数据结构回顾之顺序存储结构中的线性表(栈与队列顺序线性表实现)

说到数据结构呢,对于一个Coder来说还是蛮重要的啦,每次看数据结构的东西都有新的收获,这两天在回顾数据结构的知识。当然啦,虽然数据结构有些是理论的东西,如果好好的理解数据结构的东西还是少不了的代码的支撑的。数据结构简单的来说吧,可以分为两大类,一个是数据的“物理存储结构”,另一种是数据的“逻辑存储结构”。数据的“物理存储结构”又可分为顺序的和链式的(下面将会结合着代码打印内存地址的形式来观察物理存储结构)。 逻辑存储结构又可分为集合,线性, 树,图这些东西。

  数据结构说白了就是如何利用上面的那些东西来储存我们的数据,目的是方便我们对数据的管理和使用,至于选择何种数据结构来存储我们的数据,这要根据具体情况具体分析。本篇还是比较实用的,干货还是比较多的。由于博主本人水平有限,欢迎批评指正,共同进步。

  好啦,废话少说,切入今天的正题。本篇博客的主题是介绍顺序存储结构下的线性表,然后又给出啦顺序物理存储结构下的栈和队列,当然是对线性表的应用了。基础代码的编写是用C语言写的,最后给出了OC中的栈和队列的实现方式。好啦,这次真的不说废话了,代码走起。

1.本篇博文代码的运行环境

    操作系统 Mac OS X 10.9.4 编译器:Xcode6.1

  2.定义顺序线性表的宏定义和类型重定义如下,MAXSIZE为线性表的最大容量, SUCCESS为成功后的返回代码,ERROR为失败后的返回代码

 1 //  main.m
 2 //  DataStructList
 3 //
 4 //  Created by 李泽鲁 on 14-11-4.
 5 //  Copyright (c) 2014年 Mrli. All rights reserved.
 6 //
 7 
 8 #import <Foundation/Foundation.h>
 9 #define MAXSIZE 10             //线性表顺序存储结构的最大容量
10 /*
11  *定义状态代码
12  */
13 #define SUCCESS 1
14 #define ERROR 0
15 
16 typedef int Status;            //状态代码的类型
17 typedef int ElemType;          //顺序线性表中存储的元素类型

 3.定义顺序线性表的存储结构,当然啦,既然物理上是顺序的(内存地址连续的),所以我们就用一维数组来储存线性表中的元素。length为数据元素的个数

1 //顺序存储结构定义
2 typedef struct {
3     ElemType data[MAXSIZE];     //用数组来表示顺序线性表
4     int length;
5 } SqList;

  4.线性表的初始化,为我的的线性表分配存储内存(用malloc分配内存),并初始化length为0。返回值为分配内存的首地址,也就是线性表的指针,代码如下:

1 /*
2  *线性表的初始化,分配内存,并初始化元素的个数
3  */
4 SqList* initSqlist()
5 {
6     SqList *myList = (SqList *) malloc(sizeof(SqList));
7     myList->length = 0;
8     return myList;
9 }

 5.接下来我们就要写如何往线性表中增加元素了

    (1),以栈的形式来往我们的顺序线性表中增加元素,也就是每次往线性表中的末尾添加元素。在前面的iOS部分的博客中的UINavigationController中提到了栈的概念,下面的代码就是入栈的过程。用大白话说,就是往线性表的末尾添加元素。在添加之前呢,要判断该线性表是否有额外的空间来容纳我们要入栈的元素。代码如下:

 1 /*
 2  *增加元素(以栈的形式添加元素,往线性表的尾部添加元素)--(入栈)
 3  */
 4 Status pushElement(ElemType element, SqList *list)
 5 {
 6     int length = list->length;
 7     //判断线性表的合法性
 8     if (length < 0 || length >= MAXSIZE)
 9     {
10         return ERROR;
11     }
12     
13     //length合法,往尾部添加元素
14     list->data[length] = element;
15     list->length ++;
16     
17     return SUCCESS;
18 }

    (2)、上面的是入栈,也就是从尾部添加元素,接下啦就是如何往任意的合法位置插入元素。顺序线性表插入元素的思想是从后往前为我们的要插入的位置腾空,腾出空来,我们就插入元素,然后length加一,代码如下:

 1 //顺序线性表插入元素
 2 Status insertElementWithLocation(ElemType elment, SqList *list, int location)
 3 {
 4     int length = list->length;
 5     //判断线性表的合法性
 6     if (length < 0 || length >= MAXSIZE)
 7     {
 8         return ERROR;
 9     }
10     
11     //判断位置的合法性
12     if (location < 0 || location > length)
13     {
14         return ERROR;
15     }
16     
17     //插入元素
18     for(int i = length; i >= 0; i --)
19     {
20         //元素从后往前移动,给插入的位置腾出空
21         if (i >= location)
22         {
23             list->data[i] = list->data[i-1];
24         }
25         else
26         {
27             //腾出位置以后结束循环
28             break;
29         }
30     }
31     
32     //往插入的位置赋新的值
33     list->data[location] = elment;
34     list->length ++;
35     
36     return SUCCESS;
37 }

    (3)、接下来就是队列出场的时候啦,队列增加元素是从头插入的,所以我们只需调用上面的插入函数就可以实现入队列的功能,代码如下:

 1 //按队列的形式增加元素(入队列)
 2 Status intoQueueWithElement(ElemType element, SqList *list)
 3 {
 4     //调用插入语句,往顺序线性表中的头部添加元素,也就是如对列的围脖
 5     Status error = insertElementWithLocation(element, list, 0);
 6     
 7     if (error == ERROR) {
 8         return ERROR;
 9     }
10     return SUCCESS;
11 }

  6、上面的部分是增加元素,下面就开始我们的删除元素的部分

    (1)、还是按照上面的思路来,看一下顺序存储结构下的线性表的栈是如何删除元素的。当然啦,这个很简单啦,也就是出栈的过程,从线性表的末尾移除元素即可,同时length减一,代码如下:

 1 /**
 2  *以栈的形式来删除元素--(出栈),*element用于接收pop出的值
 3  */
 4 Status popElement(ElemType *element,SqList *list)
 5 {
 6     int length = list->length;
 7     //判断线性表的合法性
 8     if (length < 0 || length >= MAXSIZE)
 9     {
10         return ERROR;
11     }
12     
13     
14     *element = list->data[length - 1];
15     list->length --;
16     
17     return SUCCESS;
18     
19 }

    (2)、给出位置删除元素的代码如下,这个正好和给出位置增加元素相反,这个是从删除的位置依次覆盖,然后length减一即可,代码如下

 1 //删除指定位置的元素
 2 Status deleteElementWithLocation(ElemType *element, SqList *list, int location)
 3 {
 4     int length = list->length;
 5     //判断线性表的合法性
 6     if (length < 0 || length >= MAXSIZE)
 7     {
 8         return ERROR;
 9     }
10     
11     //判断位置的合法性
12     if (location < 0 || location >= length)
13     {
14         return ERROR;
15     }
16     
17     //取出要删除的元素
18     *element = list->data[location];
19     
20     //覆盖掉要删除的元素
21     for (int i = location; i < length-1; i ++) {
22         list->data[i] = list->data[i+1];
23     }
24     list->length --;
25 
26     
27     return SUCCESS;
28 }

    (3)出队列的过程和出栈的过程是一样的,都是从线性表的最后删除元素,代码如下:

 1 //出队列,和出栈一样,都是取出最后一个元素
 2 Status outQueueWithList(ElemType *element, SqList *list)
 3 {
 4     
 5     Status error = popElement(element, list);
 6     if (error == ERROR) {
 7         return ERROR;
 8     }
 9     return SUCCESS;
10 }

7、遍历我们的顺序线性表,代码如下:

 1 /*
 2  *遍历顺序线性表
 3  */
 4  Status displayList(SqList *list)
 5 {
 6     int length = list->length;
 7     //判断线性表的合法性
 8     if (length < 0 || length >= MAXSIZE)
 9     {
10         return ERROR;
11     }
12 
13     NSLog(@"********************************");
14     for (int i = 0; i < list->length ; i ++) {
15         NSLog(@"数值 = %d,内存地址 = %p", list->data[i], &list->data[i]);
16     }
17     NSLog(@"********************************\n\n");
18     
19     return SUCCESS;
20 }

 8、基本代码编写完毕,下面就该我们做测试啦

    (1),首先在main函数中进行线性表的初始化,然后push进5个数字,并输出。由输出结果可以看出,在内存中的地址是连续的,并且是从线性表的末尾添加的元素代码如下:

 1     //初始化顺序线性表
 2     SqList *list = initSqlist();
 3     
 4     NSLog(@"把1-5按顺序入栈");
 5     //往顺序线性表中以栈的存储方式存入值,入栈
 6     for (int i = 1; i < 6; i ++) {
 7         pushElement(i, list);
 8     }
 9     //遍历线性表
10     displayList(list);

    运行结果如下:

    (2)、测试往任意的位置插入值(为了整齐,后来运行的时候把10,给改成了8),代码如下,内存地址当然也是连续的啦

1     //往第0个位置插入数值10;
2     NSLog(@"往第0个位置插入数值10");
3     insertElementWithLocation(8, list, 0);
4     displayList(list);

       运行结果如下:

    (3)、出栈的测试代码如下

1     //出栈
2     ElemType element;  //用于接收pop出的值
3     popElement(&element, list);
4     NSLog(@"出栈后的值为:%d, 值的地址为:%p", element, &element);
5     displayList(list);

      运行结果如下:

    (4)、入队列的测试代码如下:

    //入队列
    NSLog(@"把9入队列");
    intoQueueWithElement(9, list);
    displayList(list);

      运行结果如下:

    (5)、出队列的测试代码如下:(下面NSlog打印的时候有的小错误,把出栈应该换成出队列,因为是截得图,所以就不改了,在这声明一下的啦)。

1     //出队列
2     ElemType lastElement;
3     outQueueWithList(&lastElement, list);
4     NSLog(@"出栈后的值为:%d, 值的地址为:%p", lastElement, &lastElement);
5     displayList(list);

      运行结果如下:

    (6)、删除指定位置的元素,测试代码如下:

1     //删除指定位置上的数据
2     NSLog(@"删除下标为三的元素");
3     ElemType deleteElement;
4     deleteElementWithLocation(&deleteElement, list, 3);
5     NSLog(@"被删除的值为:%d, 内存地址:%p", deleteElement, &deleteElement);
6     displayList(list);

      运行结果如下:

  上面呢就是用C语言描述的顺序存储结构下的线性表了,其中也给出了队列和栈的操作。那么在OC中如何使用栈和队列的结构呢?其实蛮简单的,用NSMutableArray就完全可以实现上述的操作,因为苹果已经给我们封装好啦,直接用就可以了。不过原理性的东西还是要明白的。有关NSMutableArray的东西,请参考前面有关OC部分的博客:Objective-C中的集合类 ,栈和队列的使用请参考iOS部分的iOS开发之画图板(贝塞尔曲线),今天的博客就先到这,欢迎批评指正。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

cf914D. Bash and a Tough Math Puzzle(线段树)

可以这么想,如果能成功的话,我们可以把那个数改成$1$,这样比$x$大的数就不会对答案产生影响了。

991
来自专栏mySoul

java队列

队列为特殊的线性表,队列的特点先进先出(FIFO),队列插入为入队,队列删除为出对。

2680
来自专栏李家的小酒馆

二叉树的层次遍历

二叉树的层次遍历 基本思想 借助队列来实现 首先初始化队列.然后将根结点压入队列 然后出队,输出出队元素的值, 如果存在左孩子.则左孩子入队 如果存在右孩子,则...

2280
来自专栏我是攻城师

理解Java8并发工具类ConcurrentHashMap的实现

前面的文章已经分析过List和Queue相关的接口与并发实现类,本篇我们来分析一下非常Java里面非常重要的一个数据结构HashMap。(注意Set类型在这里我...

2682
来自专栏python读书笔记

《python算法教程》Day8 - 构建二分搜索树二分搜索树介绍二分搜索树创建代码

今天是《python算法教程》的第8篇读书笔记,笔记的主要内容是构建二分搜索树。 二分搜索树介绍 若要对一组有序值中执行操作(如查找),二分搜索法是一个优秀的选...

37713
来自专栏小樱的经验随笔

【Java数据结构学习笔记之三】Java数据结构与算法之队列(Queue)实现

  本篇是数据结构与算法的第三篇,本篇我们将来了解一下知识点: 队列的抽象数据类型 顺序队列的设计与实现 链式队列的设计与实现 队列应用的简单举例 优先队列的设...

4047
来自专栏nice_每一天

转载 Java设计模式

设计模式; 一个程序员对设计模式的理解: “不懂”为什么要把很简单的东西搞得那么复杂。后来随着软件开发经验的增加才开始明白我所看到的“复杂”恰恰就是设计模式的精...

1252
来自专栏猿人谷

(重点)链式栈

顺序栈的实现在于使用了数组这个基本数据结构,数组中的元素在内存中的存储位置是连续的,且编译器要求我们在编译期就要确定数组的大小,这样对内存的使用效率并不高,一来...

2339
来自专栏从流域到海域

《笨办法学Python》 第9课手记

《笨办法学Python》 第9课手记 这节课终于有一点新内容了,新内容也蛮容易理解的。 原代码如下: # Here's some new stuff, reme...

22210
来自专栏ACM算法日常

POJ-3641:Pseudoprime numbers(快速幂)

Fermat's theorem states that for any prime number p and for any integer a > 1, a...

1141

扫码关注云+社区

领取腾讯云代金券