线性表学习

顺序表

顺序表，即线性表的顺序存储结构，采用结构体类型SqList表示为：

1
2
3
4
struct sqList{
    ElementType data[maxSize];
    int length;
}

顺序表的实现

建立顺序表

1
2
3
4
5
6
7
sqList *L=(sqList *)malloc(sizeof(sqList));
L->length=0;int i=0;
while(i<n)
{
    scanf("%d",&L->data[i]);    
    L->length++;
}

查找顺序表数据位置

1
2
3
4
5
6
7
8
void search(sqList* L,int e)
{
    int i=0;
    while(i<L->length&&L->data[i]！=e)
    i++;
    if(i>L-length) return 0;
    else return i+1;
}

插入数据元素

1
2
3
4
5
6
7
8
9
10
11
void sert(sqList *L,int i,int e)
{
    int j=L->length;
    while(j>i)
    {
        L->data[j]=L->data[j-1];
        j--;
    }
    L->data[i-1]=e;
    L->length++;
}

删除顺序表

free(L);

顺序表的应用

题目大意

给定一个顺序表，删除其中所有值等于x的元素，要求时间复杂度O(N),空间复杂度O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
void deleteX(sqList *L,int x)
{
    int i=0,k=0;
    while(i<L->length)
    {
        if(L->data[i]==x) i++;
        L->data[k]=L->data[i];
        k++;i++;
    }
    L->length=k;
    for(i=0;i<L->length;i++) printf("%d ",L->data[i]);
}

链表

链表，即线性表的链式存储结构，采用结构体的表示方式为：

1
2
3
4
struct nodeList{
    int data;
    nodeList *next;
}

链表的实现

链表的建立

1.头插法

1
2
3
4
5
6
7
8
9
10
11
nodeList *p,*q;
p=(nodeList *)malloc(sizeof(nodeList));
p->next=NULL;
int x;
while(~scanf("%d",&x)
{
    q=(nodeList *)malloc(sizeof(nodeList));
    q->data=x;
    q->next=p->next;
    p->next=q;
}

2.尾插法

1
2
3
4
5
6
7
8
9
10
11
12
nodeList *head,*p,*q;
head=(nodeList *)malloc(sizeof(nodeList));
p=head;
int x;
while(~scanf("%d",&x))
{
    q=(nodeList *)malloc(sizeof(nodeList));
    q->data=x;
    p->next=q;
    p=q;
}
p->next=NULL;

链表的插入元素与删除元素

1.插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void sertElement(nodeList *L,int i,int e)
{
    nodeList *p=L;
    int j=0;
    while(j<i&&p!=NULL)
    {
        p=p->next;
        j++;
    }
    if(p!=NULL)
    {
        nodeList *s=(nodeList*)malloc(sizeof(nodeList));
        s->data=e;
        s->next=p->next;
        p->next=s;
    }
}

2.删除元素

1
2
3
4
5
6
7
8
9
10
11
12
void deleteElement(nodeList *L,int e)
{
    
    nodeList *p=L,*q;
    while(p!=NULL&&p->data!=e)
    {
        p=p->next;    
    }
    q=p->next;
    p->next=p->next->next;
    free(q);
}

链表的删除

1
2
3
4
5
6
7
8
9
10
11
void freeList(nodeList *L)
{
    nodeList *q=L,*p=L->next;
    while(q!=NULL)
    {
        free(q);
        q=p;
        p=q->next;
    }
    free(q);
}

链表的应用

题目大意

给定一个链表，设计一个算法使其元素递增。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void sortList(nodeList *head)
{
    nodeList *q,*p,*s;
    q=head->next;p=head->next->next;
    s=head;
    while(q!=NULL)
    {
        while(q->data>=p->data)
        {
            p=p->next;
        }
        q->next=p->next;p->next=q;
        p=head->next;
        q=q->next
}