数据结构PT1——线性表/链表

本文主要是介绍数据结构PT1——线性表/链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1：顺序存储实现(数组实现)

Data： a1 a2 .....ai ai+1 .... an ....

typedef struct LNode *List; //指向LNode的指针，这是typedef的，你可以随时声明，而不加typedef只是创建一个
struct LNode{    //结构体成员ElementType Data[MAXSIZE];    //数组int Last;  
};
struct LNode L;    //声明实例
List PtrL;    //声明PtrL指针变量

访问第i个元素：L.Data[i]或者Ptr->Data[i]

线性表长度：L.Last+1或者PtrL->Last+1

    ​1>初始化

List MakeEmpty()    //返回List指针
{List Ptrl;Ptrl = (List)malloc(sizeof(struct LNode));    //动态创建LNode，需要指向该结构的指针Ptrl->Last = -1;    //通常通过判断或者使得Last = -1，来使得一个新的空链表时初始化return Ptrl;
}

    ​2>查找

int Find(ElementType X, List PtrL)
{int i = 0;while(i <= PtrL->Last    &&    PtrL -> Data[i] != X)    //Last 是链表中最后一个元素的索引而不是元素个数，因为结构体中的Last声明过i++;if(i > PtrL -> Last)return -1;else return i;}

    ​3>插入

    ​先移动、再插入，比如在i位置插入x元素，要把i-1后面的元素全部向右移动一位

void Insert(ElementType X,int i,List Ptrl)
{int j;if(PtrL -> Last == MAXSIZE -1){print("表满");return;}if(i < 1 || i > PtrL ->Last + 2){printf("位置不合法");return;}for(j = Ptrl -> Last;j >= i-1;j- -)PtrL -> Data[j+1] = PrL -> Data[j];    //循环把j位置的元素给到j+1位置的元素PtrL -> Data[i-1] = X;    //把i-1位置的元素替换成XPtrL -> Last++;    //Last+1return
}

    ​4>删除

    ​先删除、再移动

void Delete(int i ,List PtrL)
{int j;if(i < 1 || i > PtrL -> Last + 1){printf("不存在第%d个元素",i);return;}for(j=i ; j <= PtrL -> Last; j++)PtrL-> Data[j-1] = PtrL -> Data[j];    //循环把i+1位置的元素向左移动PtrL -> Last- -;return;
}

2：链式存储实现

不要求逻辑相邻的两个元素物理上也相邻，通过“链”建立起元素上的逻辑关系

它的元素定义如下：它不再使用数组和int类型的末尾元素，而是Data和Next

typedef struct LNode *List;
struct LNode{ElementType Data;List Next;
};
struct LNode L;
List PtrL;

链表由多个这样的“元素”连接而成，PtrL是指向该元素的指针，Next是指向下一个元素的指针，简单来说，Ptrl就是头指针，Next是尾指针

    ​1>求表长

int Lenth(List PtrL)    //只知道链表的头指针，单向链表
{List p = PtrL;    //临时指针P指向链表头int j = 0;while(p){        //p指针不结束p = p -> Next;    //指向下一个j++;}return j;
}

    ​2>查找

    按序号查找：FindKth;    ​(查找位于第K号的元素)

List FindKth(int K,List PtrL)
​{
​    List p = PtrL;
​    int i = 1;while(p != NULL && i < K){p = p-> Next;i++;}if(i == K) return p;    //找到第K个，返回指针else return NULL;    //没找到返回空
}

    ​3->插入

    ​①s指向新节点

    ​②p指向链表的第i-1个节点

    ​找到修改指针，插入节点

    ③​把s指针赋给p指针的下一位，p -> Next = s;

    ​④把p的下一位赋值给s的下一位

List Insert(ElementaType X ,int i , List PtrL)    //在i位置插入元素X
{List p ,s;    //两个临时指针p,sif(i == 1）{  //如果在表头插入s = (List)malloc(sizeof(struct LNode));    //(List) 将 malloc 返回的指针转换为 List 类型的指针,指向struct的指针s -> Data = X;s -> Next = PtrL;    //    把原来的头指针给新元素的尾指针return s;}p = FindKth(i-1 , PtrL);    //查找位于i-1位置的元素，把指向该位置的指针赋值给pif(p == NULL){printf("参数i错误");return NULL;}else{s = (List)malloc(sizeof(struct LNode));    s -> Data = X;        s -> Next = p -> Next;    //s是新元素p -> Next = s;return PtrL;
}

    ​4->删除

    ​①找到i-1个节点，用p指向

    ​②用s指向要被删除的节点(p的next)

    ​③修改指针，删除s指向节点

    ​④释放s空间

List Delete(int i ,List PtrL)
{List s, p;if( i == 1){s = PtrL;if(PtrL != NULL) PtrL = PtrL -> Next    //从链表中删除selse return NULL;free(s);    //释放s空间return PtrL;}p = FindKth(i-1 , PtrL);    //查找i-1个节点if(p = = NULL){printf("第%d个节点不存在",i-1);return NULL;}else if( p -> Next == NULL){printf("第%d个节点不存在",i);return NULL;}else{s = p -> Next;p -> Next = s -> Next;free(s);return PtrL;
}

这篇关于数据结构PT1——线性表/链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---