数据结构--顺序表和链表（1）_顺序表伪代码是什么

     数据结构的存储方式最常用的是顺序存储和链式存储。下面在进行数据结构的学习前，我们先来了解这两种存储方式，通过顺序表和链表的学习来深入了解这两种存储方式。

一、顺序表

     顺序表的实现，一般与数组息息相关。其有两种创建方式，静态分配空间和动态分配空间。

   1.1 顺序表的创建实例。

   静态：给定一个确定的且是连续的存储空间。例如：int a[10]; 系统会分配10个连续的空间。可以通过索引访问，其底层逻辑是，a[i] = a[0]的起始地址+i*4;    即通过此公式能够快速访问元素。其时间复杂度为O(1);

   动态：就是手动new一块空间，可以通过控制台输入要创建的连续存储空间的大小。

   1.2顺序表的伪代码

       typedef struct list{

            int a[10];

            int length;

};

     1.3分析顺序表的基础功能

        插入：插入分三种情况。插头，则头后面的元数依次向后移位。插中间（插中间的频率最高），中间这个元数向后移。O(n);插入最后，需要判断是否空间已满。

     删除：删除思路通上。

    遍历：通过for循环即可。

    数组扩容：一般开辟原数组的两倍。然后将原数组复制过来。对于系统来说这个开销很大。

二、链表

   链表采取的是链式存储。通过指针实现。

以下代码已将head变量声明为全局变量。

 

2.1链表的伪代码

typedef struct Node {

int data;

struct Node* next;

};

2.1链表部分需掌握的基本功。

遍历链表：

void print( ){

 struct Node* p =head;

while(p != NULL){

    p = p->next;

}

}

头插法添加元素：

void add(int a){

     struct Node* p = new Node();  // 申请一块空间

     p->data = a;

     p->next = head;

     head = p;

}

插入到中间位置：

void insert(int x, int n) {
    struct Node* p = new Node();
    p->data = x;
    p->next = NULL;
    struct Node* temp = head;
    for (int i = 1; i < n - 1; i++) {
        temp = temp->next;
    }
    // 这个时候temp指针指向插入位置的前一个元素；
    p->next = temp->next;
    temp->next = p;
}

删除某个节点的算法：思路同上。