首页 > 其他分享 >线性表

线性表

时间：2023-06-22 11:44:08浏览次数：31  
标签：return 线性表 int next LinkList data 节点

1、线性表

线性表是具有相同数据类型的n个数据元素的有限序列。

2、线性表的顺序表示

特点：逻辑和物理顺序都相同。表中的任意数据元素都可以随机存取。

静态分配方式实现

#include<stdio.h> 

// 顺序表,静态分配 
#define MaxSize 10 // 定义线性表 最大长度 
typedef struct {
    int data[MaxSize]; // 顺序表的元素 elemType,此处用int代替 
    int length; // 顺序表的当前长度 
}sqList; //顺序表的类型定义

// 初始化表。构造一个空的线性表 
void InitList(sqList* L){
    L->length = 0; // 顺序表初始长度为0
    for(int i = 0;i < MaxSize;i++){
        L->data[i] = 0; // 初始值为0，预防内存中垃圾值的影响 
    } 
} 

// 求表长 。返回线性表L的长度，即L中数据的个数 
int Length(sqList L){
    return L.length;
}

// 按值查找。在表L中查找据右给定关键字值的元素 
int LocateElem(sqList L,int e){
    for(int i = 0;i < L.length;i++){
        if(L.data[i] == e){
            return i + 1; // 注意返回的是位序 
        }
    }
    return 0;
} 
// 按位查找。获取表中第 i 个位置元素的值 
int GetElem(sqList L,int i){
    if(i <= 1 || i > L.length){
        return -1; // 这里将 -1 当作未找到的值 
    }
    return L.data[i - 1];
} 
// 插入操作。在表L中第 i 个位置上插入指定元素 e。位序从1开始 
bool ListInsert(sqList* L,int i,int e){
    if (i < 1 || i > L->length + 1){ // 判断i的范围是否有效 
        return false;
    }
    if (L->length >= MaxSize){ // 当前存储空间已满，不能插入 
        return false;
    }
    for (int j = L->length;j >= i;j--){
        L->data[j] = L->data[j-1];
    }
    L->data[i - 1] = e;
    L->length++;
    return true; 
} 

// 删除操作。在删除在表L中第 i 个位置上的元素，并用 e 返回删除元素的值 
bool ListDelete(sqList* L,int i,int* e){
    if (i < 1 || i > L->length){ // 判断i的范围是否有效 
        return false;
    }
    *e = L->data[i - 1];
    for (int j = i;j < L->length;j++){
        L->data[j - 1] = L->data[j];
    }
    L->length--;
    return true; 
} 

// 判空操作。若L为空表，则返回true，否则返回false
bool Empty(sqList L){
    if (L.length == 0){
        return true;
    }
    return false;
} 

// 销毁操作。销毁线性表，并释放线表L所占内存空间
bool DestroyList(sqList* L){
    if(L == NULL){
        return false;
    }
    L->length = 0;
    return true;
} 


int main(){
    sqList l; // 声明一个顺序表 
    
    InitList(&l); // 初始化顺序表
//    if(Empty(l)){
//        printf("空表");
//    }
    // 插入测试 
    ListInsert(&l,1,1) ;
    ListInsert(&l,2,2) ;
    ListInsert(&l,3,3) ;
    ListInsert(&l,3,5) ;
    // 删除测试 
//    int e = 0;
//    ListDelete(&l,1,&e);
    
    // 按值查找测试 
//    int a = LocateElem(l,5);
    int a = GetElem(l,4);
    printf("a = %d\n",a); 
    for(int i = 0;i < l.length;i++){
        printf("i = %d\n",l.data[i]); 
    }  
    return 0;
}

动态分配方法实现

其余方法同上

#include<stdio.h> 
#include<malloc.h>
// 顺序表,动态分配 
#define InitSize 10 // 表长度初始定义 
typedef struct {
    int *data; // 指示动态分配数组的指针 
    int length; // 顺序表的当前长度
    int MaxSize; // 最大长度 
}seqList; //顺序表的类型定义

// 初始化表。构造一个空的线性表 
void InitList(seqList* L){
    // 用malloc函数申请一片连续的存储空间 
    L->data = (int*)malloc(InitSize * sizeof(int));
    L->length = 0;
    L->MaxSize = InitSize;
    for(int i = 0;i < L->MaxSize;i++){
        L->data[i] = i;
    }
} 

// 数据容量增加 len 个 
void IncreaseSize(seqList* L,int len){
    int* p = L->data;
    L->data = (int*)malloc((L->MaxSize + len) * sizeof(int));
    for(int i = 0;i < L->length;i++){
        L->data[i] = p[i]; //将数据复制到扩容后的新数组中 
    }
    L->MaxSize = L->MaxSize + len;
    for(int i = 0;i < L->MaxSize;i++){
        L->data[i] = i;
    }
    free(p); // 释放原来数组所占的内存空间 
}
int main(){
    seqList l; // 声明一个顺序表 
    
    InitList(&l); // 初始化顺序表

    IncreaseSize(&l, 10);

    return 0;
}

3、单链表

#include<stdio.h> 
#include<malloc.h>
// 定义单链表节点类型 
typedef struct LNode{
    int data; // 数据域 
    struct LNode* next; //指针域 
}LNode,*LinkList; // => (struct LNode*) p = (LinkList) p

// 按序号查找节点
LNode* GetElem(LinkList L,int i){
    if(i < 1){
        return NULL;
    }
    LNode* p = L->next; // 指向第一个节点 
    int j = 1; // 从 1 开始计数 
    while(p != NULL && j < i){
        p = p->next;
        j++;
    }
    return p; // 返回第 i 个节点，若 i > 表长，返回null 
} 
// 按值查找节点
LNode* LocateElem(LinkList L,int e){
    LNode* p = L->next; // 指向第一个节点 
    while(p != NULL && p->data != e){
        p = p->next;
    }
    return p; // 找到返回该节点，复制返回null 
} 
// 头插法建立单链表 头结点方式  可用于逆置链表 
LinkList List_HeadInsert(LinkList L){
    LNode *s;
    int x = 0;
    L = (LinkList)malloc(sizeof(LNode)); //创建头结点
    L->next = NULL; // 初始为空链表 
    scanf("%d",&x); // 输入节点的值 
    while(x != 999){ // 输入999代表结束 
        s = (LinkList)malloc(sizeof(struct LNode)); // 创建新节点
        s->data = x; 
        s->next = L->next;
        L->next = s; // 将新节点插入表中，L为头指针 
        scanf("%d",&x); 
    } 
    return L; // 返回头结点 
} 

// 尾插 正向建立单链表 
LinkList List_TailInsert(LinkList L){
    int x = 0;
    L = (LinkList)malloc(sizeof(LNode)); //创建头结点
    LNode *s,*r = L; // r为表尾指针 
    scanf("%d",&x); // 输入节点的值 
    while(x != 999){
        s = (LinkList)malloc(sizeof(struct LNode)); // 创建新节点
        s->data = x;
        r->next = s;
        r = s; // r指向新的表尾节点 
        scanf("%d",&x); 
    } 
    r->next = NULL;
    return L; // 返回头结点 
}


// 插入 i为插入位置,n为要插入的节点 
bool ListInsert(LinkList L,int i,int e){
    LinkList p = GetElem(L,i - 1);// 找到要插入位置的前驱节点 
    if (p == NULL){ // i值不合法 
        return false;
    }
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
// 扩展,指定节点前插 
bool ListInsert_after(LinkList L,int i,LinkList n){
    LinkList p = GetElem(L,i);// 找到要插入位置的后驱节点
    // 修改指针域 
    n->next = p->next;
    p->next = n;
    
    // 交换数据域部分 
    int temp = p->data;
    p->data = n->data;
    n->data = temp;
}

// 删除 其中 i为插入位置,n为要插入的节点 
bool ListDelete(LinkList L,int i){
    LinkList p = GetElem(L,i - 1);// 找到要删除位置i的前驱节点 
    if(p == NULL){
        return false;
    }
    if(p->next == NULL){
        return false;
    }
    LinkList q; // 用于记录删除的节点 
    q = p->next; // 令q指向被删除的节点 
    p->next = p->next->next; // 将*q节点从链表中 断开 
    free(q); // 释放节点的存储空间 
    return true;
}

// 扩展 通过后继节点删除  
/*
    无法删除最后一个节点时，只能调用上一个方法进行删除、
    不能直接free 因为p的前驱还指向当前的p的地址。 
*/
bool ListDelete2(LinkList p){
    if(p == NULL){
        return false;
    }
    LinkList q; // 用于记录删除的节点 
    q = p->next; // 令q指向被删除的节点的后一个节点 
    p->data = p->next->data; // 用后继节点的数据域覆盖 
    p->next = q->next; // 将*q节点从链表中 断开 
    free(q); // 释放节点的存储空间 
    return true;
}

// 求表长 
int getLength(LinkList L){
    int i = 0;
    LinkList p = L;
    while(p->next != NULL){
        p = p->next; 
        i++;
    }
    return i;
}
int main(){
    /*
        注意，这里传进去的 L  
        在执行List_TailInsert 中的 L = (LinkList)malloc(sizeof(LNode));时，
        List_TailInsert函数里的L的值不指向这里L 
        由此主函数L的值没有改变，相当于未赋值，为垃圾值 
    */ 
    struct LNode L;
    LinkList head = List_TailInsert(&L); 
    LinkList p = &L;
    
    while(p->next != NULL){
        p = p->next;
        printf("%d\n",p->data);
    }
    printf("%d\n",getLength(head));
    return 0;
}

4、双链表

#include<stdio.h> 
#include<malloc.h>
// 定义双链表节点类型 
typedef struct DNode{
    int data; // 数据域 
    struct DNode* next; //后驱指针 
    struct DNode* prior; //前驱指针
}DNode,*DLinkList;  // DNode强调节点  DLinkList强调是个表 

// 初始化双链表
DLinkList InitDLinkList(){
    DLinkList L = (DNode*)malloc(sizeof(DNode)); // 分配一个头结点
    if (L == NULL){ // 内存空间不足 
        return NULL;
    } 
    L->next = NULL;
    L->prior = NULL;
    return L;
} 

// 插入 在 p 节点之后插入 s 节点 
bool InsertNextDNode(DNode* p,DNode* s){
    if(p == NULL || s ==NULL){ // 非法参数 
        return false;
    }
    s->next = p->next;
    if(p->next != NULL){ // 如果p节点有后继节点，修改后继节点的前驱节点 
        p->next->prior = s;
    } 
    s->prior = p;
    p->next = s;
    return true;
    
} 

// 删除p 的后继节点
 bool deleteNextDNode(DNode* p){
    if(p == NULL ){ // 非法参数 
        return false;
    }
    DNode* q = p->next; // 找到 p 的后继节点 q 
    if(q == NULL){
        return false; // q节点没有后继节点 
    } 
    p->next=q->next;
    if(q->next != NULL){
        q->next->prior = p;//q节点有后继节点 
    }
    free(q); // 释放节点空间 
    return true;
    
} 

// 销毁
void destoryList(DLinkList* L){
    while((*L)->next != NULL){
        deleteNextDNode(*L);
    }
    free(*L);
    *L = NULL;
}

5、循坏链表

  • 判空
  • 判断p是否时表尾/表头节点
  • 如何在表头、表中、表尾插入/删除一个元素

6、静态链表

标签：return,线性表,int,next,LinkList,data,节点
From： https://www.cnblogs.com/xpp3/p/17493469.html

相关文章

  • 20230303 2.1. 线性表及其实现
    如何表示多项式?\[f(x)=a_0+a_1x+...+a_{n-1}x^{n-1}+a_nx^n\]方法1：顺序存储结构直接表示\(a[i]\)：项\(x^i\)的系数\(a_i\)例如：\[f(x)=4x^5-3x^2+1\]下标i012345a[i]10-3004问题：浪费空间，例如\(x+3x^{2000}\)方法2：顺序存储结构表示非零项......
  • 数据结构和算法系列课程（02） --- 线性表和贪吃蛇
    线性结构是一种具有以下特点的结构：存在唯一一个被称为“第一个”的数据元素存在唯一一个被称为“最后一个”的数据元素除第一个元素之外，集合中的每个元素均有且仅有一个前驱除最后一个元素之外，集合中的每个元素均有且仅有一个后继那么，线性表、栈、队列、数组、字符串都可以......
  • 第2章-线性表
    1.顺序表1.1顺序表的定义1.1.1静态分配：#include<stdio.h>#defineMaxSize10typedefstruct{ intdata[MaxSize]; intlength;}Sqlist;//初始化一个顺序表voidInitList(Sqlist&L){ for(inti=0;i<MaxSize;i++){ //TODO L.data[i]=0;//将所有数据元素设置为默认......
  • 第2章-线性表习题
    P1708#include<stdio.h>#include<iostream>usingnamespacestd;voidreverse(inta[],intn,intm,intsize){ for(inti=0;i<size;i++){ a[i]=i+1; } for(inti=0;i<size;i++) cout<<a[i]<<""; cout<<endl;......
  • 每日记录(线性表链式存储结构（链表）)
    链表的基本概念建议每次写的时候都加一个头节点各结点由两个域组成：数据域：存储元素数值数据指针域：存储直接后继结点的存储位置结点：数据元素的存储映像。由数据域和指针域两部分组成链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构单链表......
  • 每日记录(2.4线性表的应用)
    有序表的合并已知线性表La和Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的数据元素仍按值非递减有序排列。La=(1,7,8)Lb=(2,4,6,8,10,11)Lc=(1,2,4,6,7,8,8,10,11)0.新建一个链表新建一个空表C，直接在A和B中每次选取最小值......
  • 每日记录(数据结构 第二章 线性表() )
     线性表的定义：存在唯一一个“第一个”元素存在唯一一个“最后一个”元素除第一个元素外，每一个元素都有且只有一个前驱除最后一个元素外，每个元素都有且只有一个后继一、线性表顺序存储结构（顺序表）0.线性表的基本概念线性表强调元素在逻辑上紧密相邻，所以首先想到用数组存储。但是......
  • [学习笔记]数据结构_线性表_顺序表and单链表
    线性表线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面上的概念。线性表的基本操作boolInitList(&L)//初始化表，构造一个空的线性表intLength(L)//求表长。返回线性表L的长度，即L中数据元素的个数intLocateElem(L,e)//按......
  • 线性表的顺序存储结构
    线性表的顺序存储结构标签（空格分隔）：DS线性表顺序存储1.线性表的顺序存储结构#defineMAXSIZE20//数组最大长度typedefstruct{ElemeTypedata[MAXSIZE];//数组顺序存储元素，data即为存储空间的起始位置intlength;//线性表当前长度:表中元素的个数length<=MAXSIZE}SqLi......
  • 线性表的链式存储结构
    线性表的链式存储结构标签（空格分隔）：DS线性表链式存储1.线性表的单链表存储结构typedefstructNode{ElemTypedata;//数据域structNode*next;//指针域}Node,*pNode;//节点，节点指针typedefstructNode*LinkList;//头指针指向头节点2.单链表的读取第i个元......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99