链表学习(一)

链表结构

1.创建结构体

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

2.建立链表

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

3.输出链表

1
2
3
4
5
6
7
struct node *t;
t=head;
while(t!=NULL)
{
    printf("%d ",t->data);
    t=t->next;
}

4.插入链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct node *r;
int a;
scanf("%d",&a);
while(r!=NULL)
{
    if(r->next==NULL||r->data>a)
    {
        p=(struct node *)malloc(sizeof(struct node));
        p->next=r->next;
        p->data=a;
        r->next=p;
        break;
    }
    r=r->next;
}

5.删除链表

1
2
3
4
5
6
7
struct node *f;
f=head;
while(f!=NULL)
{
    free(f);
    f=f->next;
}

模拟链表

 模拟链表，即通过2个数组来模拟动态链表，一个数组存放数据，另一个数组记录数据的位置。
1.模拟链表结构

1
2
3
4
5
6
7
8
9
10
int data[100],right[100];
for(int i=1;i<=n;i++)
{
    scanf("%d",&data[i]);
}
for(int i=1;i<=n;i++)
{
    if(i!=n) right[i]=i+1;
    else right[i]=0;
}

2.插入数据操作

1
2
3
4
5
6
7
8
9
10
11
12
13
int x;scanf("%d",&x);
int t=1;
while(t!=0)
{
    if(data[right[t]>data[n])
    {
        data[n+1]=x;
        right[t]=n+1;
        right[n+1]=t+1;
        break;
    }
    t=right[t];
}