数据结构与算法-线性表专题(一)-顺序表、单链表

线性表

线性表是最基本、最简单，也是最常用的一种数据结构。
一个线性表(linear list)是n个具有相同特性的数据元素的有限序列。
数据元素之间的关系是一对一。

线性、非线性是在逻辑层次上讨论，不考虑存储层次

顺序表

顺序存储，逻辑相邻，物理存储地址也相邻

0.数据结构声明

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* ElementType类型根据实际情况而定，这里假设为int */
typedef int ElementType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
//顺序表结构设计
typedef struct {
    ElementType *data;
    int length;
}Sequencelist;

1.顺序表初始化

Status InitList(Sequencelist *list){
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    list->data =  malloc(sizeof(ElementType) * MAXSIZE);
    //存储分配失败退出
    if(!list->data) exit(ERROR);
    //空表长度为0
    list->length = 0;
    return OK;
}

2.插入

Status ListInsert(Sequencelist *list,int i,ElementType e){
    
    //i值不合法判断
    if((i<1) || (i>list->length+1)) return ERROR;
    //存储空间已满
    if(list->length == MAXSIZE) return ERROR;
    //插入数据不在表尾,则先移动出空余位置
    if(i <= list->length){
        for(int j = list->length-1; j>=i-1;j--){
       
            //插入位置以及之后的位置后移动1位
            list->data[j+1] = list->data[j];
        }
    }
    //将新元素e 放入第i个位置上
    list->data[i-1] = e;
    //长度+1;
    ++list->length;
    return OK;
}

3.清空

Status ClearList(Sequencelist *list)
{
    list->length=0;
    return OK;
}

单链表

链式存取，用一组地址任意的存储单元存放线性表中的数据元素
此处我们引入了头结点，哨兵

0.数据结构声明

结点

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
/* ElementType类型根据实际情况而定，这里假设为int */
typedef int ElementType;
/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Status;
//单链表结构设计
typedef struct {
    ElementType data;//数据
    struct Node *next;//指针域
}Node;
typedef struct Node * LinkList;

1.初始化

单链表

Status InitList(LinkList *list){
    
    //初始化哨兵，听起来高大上
    *list = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if(*list == NULL) return ERROR;
    //将头结点的指针域置NULL
    (*list)->next = NULL;
    
    return OK;
}

2.遍历Traverse

Status ListTraverse(LinkList list)
{
    LinkList p = list->next;
    while(p)
    {
        printf("%d\n",p->data);
        p = p->next;
    }
    return OK;
}

3.单链表前插法

前插法

/* 随机产生n个元素值,加入单链线性表list*/
void InsertListFromHead(LinkList *list, int n){
    
    LinkList p;
    
    //初始化哨兵单链表
    *list = (LinkList)malloc(sizeof(Node));
    (*list)->next = NULL;
    
    //循环 前插入随机数据
    for(int i = 0; i < n; i++)
    {
        //生成新结点
        p = (LinkList)malloc(sizeof(Node));
       
        //i赋值给新结点的data
        p->data = i;
        //p->next = 头结点的L->next
        p->next = (*list)->next;
        
        //将结点P插入到头结点之后;
        (*list)->next = p;
        
    }
}

4.单链表后插法

后插法

/* 随机产生n个元素值,加入单链线性表list*/
void InsertListFromTail(LinkList *list, int n){
    
    LinkList p,r;
 
    //初始化哨兵单链表
    *list = (LinkList)malloc(sizeof(Node));
    //r指向尾部的结点
    r = *list;
    
    for (int i = 0; i < n; i++) {
        
        //生成新结点
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        
        //将表尾终端结点的指针指向新结点
        r->next = p;
        //将当前的新结点定义为表尾终端结点
        r = p;
    }
    
    //将尾指针的next = null
    r->next = NULL;
}