数据结构与算法---二 (线性表)

2020-04-01 本文已影响0人只写Bug程序猿

一.线性表的定义

1.0

线性表(linear list),是由n个类型相同的数据元素a0,a1,a2,.....a(n-1)组成的有限序列
元素ai的数据类型可以为整数,浮点数,字符,或类,n代表线性表的元素个数,称为线性表的长度.

n = 0 则为空表
n>0 ,0<i<n-1 有且只有一个前驱和一个后继
a0 没有前驱
a(n-1)没有后继

1.0 线性表的顺序存储

1.0.1 线性表的顺序存储表示

线性表的顺序表示指的是一组地址连续的存储单元一次存储线性表中的元素,这种表示也成为线性表的顺序存储结构或顺序映像,这种存储结构的线性表也叫做顺序表,其特点是,逻辑上相邻的数据元素,其物理次序也是相邻的

//存储结构
typedef int ElemType;
typedef int Status;
struct NearList{
    ElemType *data;
    int length;
}

1.顺序表的初始化

为顺序表动态分配一个预定义大小的空间,使data指向这片空间的基地址
将表的length置为0
实现

Status initList(NearList *L){
    //为顺序表分配一个大小为MAXSIZE的数组空间
    L->data = malloc(sizeof(ElemType) * MAXSIZE);
    //如果没有分配成功return
    if (!L->data) exit(ERROR);
    //初始化长度
    L->length = 0;
    return OK;
}

调用示例

int main(int argc, const char * argv[]) {
    printf("Hello, World!\n");
    NearList L;
    Status iStatus;
    iStatus = initList(&L);
    printf("初始L的长度:%d",L.length);
    return 0;
}
/**打印结果
Hello, World!
初始L的长度:0
Program ended with exit code: 0
*/

2.顺序表的插入

步骤:

判断位置是否合法
判断顺序表是否已满
将第n至i个位置的元素依次向后移动一个位置,空出第i个位置
将要插入的新元素e放入第i个位置
表长度+1
实现:

Status insertNearList(NearList*L,ElemType e ,int i){
    if (i<1 || i>L->length + 1) return ERROR;
    if (L->length == MAXSIZE) return ERROR;
    if (i <= L->length) {
        for (int j = L->length - 1; j >i - 1; j--) {
            L->data[j+1] = L->data[j];
        }
    }
    L->data[i - 1] = e;
    ++L->length;
    return OK;
}

调用示例

int main(int argc, const char * argv[]) {
    printf("Hello, World!\n");
    NearList L;
    Status iStatus;
    iStatus = initList(&L);
    printf("初始L的长度:%d\n",L.length);     0
    for (int  i = 1; i< 5; i++) {
        insertNearList(&L, 2, i);
    }
    printf("插入数据L长度: %d\n",L.length);   4
    return 0;
}

3.顺序表的取值

步骤:

判断i是否合法
将第i个元素赋值给e

Status getElem(NearList L,int i,ElemType *e){
    if (i<1||i>L.length)return ERROR;
    *e = L.data[i-1];
    return OK;
}

调用

getElem(L, 1, &e);
    printf("获取到的e为L:%d\n",e);    2

4.顺序表的删除

步骤:

判断L是否为空
判断i是否合法
移除后将后边元素依次往前移
长度-1;
实现:

Status deleteElem(NearList *L,int i){
    if (L->length == 0) return ERROR;
    if (i<1||i>L->length+1)return ERROR;
    for (int j = i; j<L->length; j++) {
        L->data[j-1] = L->data[j];
    }
    L->length--;
    return OK;
}

调用

deleteElem(&L, 2);
    printf("删除数据L长度: %d\n",L.length);    3

4.顺序表的清空

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(Sqlist *L)
{
    L->length=0;
    return OK;
}

5.顺序表是否为空

/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(Sqlist L)
{
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}

6.顺序表长度

int ListLength(Sqlist L)
{
    return L.length;
}

7.顺序表遍历

/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status TraverseList(Sqlist L)
{
    int I;
    for(i=0;i<L.length;i++)
        printf("%d\n",L.data[I]);
    printf("\n");
    return OK;
}

8.顺序表查找元素并返回位置

/* 初始条件：顺序线性表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;
}

线性表的链式存储

链式存储不像顺序存储是地址是连续的,那么链式存储怎么去找下一个节点呢,一般链式存储节点分为数据域和指针域,用指针来找后继

ypedef int ElemType;
typedef int Status;
typedef struct Node{
    ElemType data;
    struct Node *next;
    int length;
}Node;
typedef struct Node * List;

为了方便我们创建的链表都是带有头结点的链表这样做有什么好处呢

便于处理首元结点
便于空表和非空表的统一处理

带首节点的线性表

2.0 单链表的初始化

思路:

创建头结点然后将L指向头结点
盘空
将头结点的next置为空
length为0

代码实现

Status initList(List *L){
    //创建头结点然后L指向此头结点
    *L = (List)malloc(sizeof(Node));
    //控件分配失败返回error
    if (*L == NULL) return ERROR;
    //将头结点的next置为空
    (*L)->next = NULL;
    (*L)->length = 0;
    return OK;
}

调用示例


int main(int argc, const char * argv[]) {
    List L;
    Status iStatus;
    // insert code here...
    iStatus = initList(&L);
    insertList(&L, 2, 1);
    printf("L 是否初始化成功?(0:失败,1:成功) %d\n",iStatus);
    return 0;
}

2.1单链表链式存储的插入

思路:

判断链表是否存在
判断插入位置是否合法
找到要插入的节点的前一个节点p
创建要插入的节点temp
将temp节点的next指向p的next
将p的next指向temp节点
长度+1;

代码实现:

Status insertList(List *L,int place,ElemType e){
    //如果链表为空则初始化一个节点
    if (*L == NULL) {
        initList(L);
    }
    int j = 1;
    List p = *L;
    List temp;
    //找第n-1个节点
    while (p && j<place) {
        p = p->next;
        j++;
    };
    if (j>place || !p) return ERROR;
    //创建插入节点
    temp = malloc(sizeof(Node));
    //将插入节点的next指向p的next
    temp->next = p->next;
    temp->data = e;
    //将temp作为p的后继
    p->next = temp;
    (*L)->length += 1;
    printf("%d",p->next->data);
    return  OK;
}

2.2单链表取值

/*
 初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：用e返回L中第i个数据元素的值
 */
Status getElem(List L,int i, ElemType *e){
    if (!L && (i<1 && i > L->length)) return ERROR;
    int j = 1;
    //声明节点p指向第一个节点
    List p = L->next;
    while (j<i && p) {
        p = p->next;
        j++;
    }
    if (!p || j>i)return ERROR;
    *e = p->data;
    return OK;
}

2.3单链表删除元素

思路:

找到要删除的节点的前一个节点
将q指向要删除的节点
将p的next指向q.的后继
系统回收节点释放内存

代码实现

Status deleteElem(List *L ,int i ,ElemType *e){
    if (*L == NULL && (i<1 && i > (*L)->length)) return ERROR;
    List p = (*L)->next;
    List q;
    int j = 1;
    while (p && j<(i - 1)) {
        p = p->next;
        j++;
    }
    if (!(p->next) || j>i-1) return ERROR;
    q = p->next;
    p->next = q->next;
    *e = q->data;
   (*L)->length--;
    free(q);
    return OK;
}

2.4单链表前插入法

* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
void CreateListHead(List *L, int n){
    
    List p;
    
    //建立1个带头结点的单链表
    *L = (List)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    //循环前插入随机数据
    for(int i = 0; i < n;i++)
    {
        //生成新结点
        p = (List)malloc(sizeof(Node));
       
        //i赋值给新结点的data
        p->data = I;
        //p->next = 头结点的L->next
        p->next = (*L)->next;
        
        //将结点P插入到头结点之后;
        (*L)->next = p;
        
    }
}

2.5单链表后插入法

/* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
void CreateListTail(List *L, int n){
    
    List p,r;
 
    //建立1个带头结点的单链表
    *L = (List)malloc(sizeof(Node));
    //r指向尾部的结点
    r = *L;
    
    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;
    
}

数据结构与算法---二 (线性表)

一.线性表的定义

1.0

1.0 线性表的顺序存储

1.0.1 线性表的顺序存储表示

1.顺序表的初始化

2.顺序表的插入

3.顺序表的取值

4.顺序表的删除

4.顺序表的清空

5.顺序表是否为空

6.顺序表长度

7.顺序表遍历

8.顺序表查找元素并返回位置

线性表的链式存储

2.0 单链表的初始化

2.1单链表链式存储的插入

2.2单链表取值

2.3单链表删除元素

2.4单链表前插入法

2.5单链表后插入法

猜你喜欢

热点阅读