数据结构-线性表

线性表是最简单、最常用的一种数据结构。是由同类型数据元素构成有序序列的线性结构。一般用来解决有序线性序列的组织和管理

线性表有两种表示形式:

1.顺序表示

2.链式表示

线性表的基本操作有:

1.List * MakeEmpty();   初始化一个空线性表

2.ElementType FindKth(int K, List L):  返回第K位元素

3.int Find(ElenentType X, List L):  在线性表L中查找X第一次出现的位置

4.void Insert(ElementType X, int I, List L): 再位序I前插入一个新元素X

5.void Delete(int I, List L):  删除指定位序I的元素

6.int Length(List L):   返回线性表L的长度

typedef struct{
    ElementType Data[MAXSIZE];
    int Last;
}List;
List L, *PtrL;

访问下标为I的元素:L.Data[I]或PtrL->Data[i]

线性表的长度:L.Last+1或PtrL->Last+1

主要操作的实现:

1.初始化(建立空的顺序表)

List *MakeEmpty()
{
    List *PtrL;
    PtrL = (List *)malloc (sizeof(List));
    PtrL->Last = -1;
    return PtrL;
}

2.查找

int Find(ElementType X, List *PtrL)
{
    int i = 0;
    while (i <= PtrL->Last && PtrL->Data[i])
    i++;
    if (i > PtrL->Last)
    return -1; 
    else return i;
}

3.插入

void Insert(ElementType X,int i, List * PtrL)
{
    int j;
    if(PtrL->Last == MAXSIZE - 1)
    {printf("表满");
    return;
    }
    if(i < 1 || i > PtrL->Last + 2)
    {
    printf("位置不合法");
    return;
    }
    for (j = PtrL->Last;j >= i-1;i--)
        PtrL->Data[j+1] = PtrL->Data[j];
    PtrL->Data[i-1] = X;
    PtrL->Last++;
    return;
}

4.删除

void Delete(int i, List *PtrL)
{
    int j;
    if(i < 1 || i > PtrL->Last+1)
    {
    printf("不存在该元素");
    return;
    }
    for(j = i;j <= PtrL->Last;j++)
        PtrL->Data[j-1] = PtrL->Data[j];
    PtrL->Last--;
    return ;
}

链表:
typedef struct Node{
    ElementType Data;
    struct Node *Next;
}List;
    List L, *PtrL;    

1.求表长

int Length(List *PtrL)
{
    List *p = PtrL;    //p指向表的第一个节点
    int j = 0;
    while (p){
    p = p->Next;
    j++;
    }
    return j;
}

2.查找
(1)按序号查找:FindKth

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;
    else
    return NULL;
}

(2)按值查找:Find

List *Find(ElementType X, List *PtrL)
{
    List *P = PtrL;
    while (p != NULL && p->Data)
        p = p->Next;
    return p;
}

3.插入
(1) 先构造一个新节点,用s指向
(2) 再找到链表的第i-1个节点,用p指向
(3)然后修改指针,插入节点(p之后插入新节点是s)

List *Insert(ElementType X, int i, List *PtrL)
{
    List *p, *s;
    if(i == 1)
    {
    s = (List *)malloc(sizeof(List));  //新节点插入在表头的情况
    s->Data = X;
    s->Next = PtrL;
    return s;
    }
    p = FindKth(i - 1, PtrL);
    if (p == NULL)
    {
    printf("参数i错误");
    return NULL;
    }
    else
    {
    s = (List *)malloc(sizeof(List));
    s->Data = X;
    s->Next = p->Next;
    p->Next = s;
    return PtrL;
    return PtrL;
}

4.删除
(1) 先找到链表第i-1个节点,用p指向
(2) 再用指针s指向要被删除的节点(p的下一个节点)
(3) 然后修改指针,删除s所指节点
(4) 最后释放s所指节点的空间

List *Delete(int i, List *PtrL)
{
    List *p, *s;
    if (i == 1)
    {
    s = PtrL;
    if (PtrL != NULL)
    PtrL = PtrL->Next;
    else return NULL;
    free(s);
    return PtrL;
    }
    p = FindKth(i - 1, PtrL);
    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;
    }

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注