数据结构——线性表的链式存储

一.单链表（重点）

1.线性表的链式存储结构

如图中的listnode A 它的存储位置是在栈上，用A去访问结构体的data是A.data=value；用p则是

p->data=value;

还有一种是存放在推上的，如下

二.单链表的创建

创建三个文件linklist.c  linklist.h  test.c

linklist.h

linklist.c

linklist list_create()
{
        linklist H;
        H=(linklist)malloc(sizeof(listnode));
        if(H==NULL)
        {
                printf("malloc failed\n");
                return H;
        }
        H->data=0;
        H->next=NULL;
        return H;
}
 

test.c

1.链表插入（尾部插入）

说一下上面的整体思路，用list_create创建一空链表H，之后用尾部插入法插入元素，之后用离遍的方式输出链表。这里的尾部插入实现，先查看要插入的链表是否创建成功，如果没有就不进行操作，创建成功则创建一个新链表p，让它data指向需要插入的value，之后用创建的q遍历到要插入的链表H的尾部，之后把q的next指向新创建的p，这就完成了外部插入。如下图演示过程

int list_tail_insert(linklist H,data_t value)
{linklist p;linklist q;if(H==NULL){printf("H is empty\n");return -1;}//1 new node p
if((p=(linklist)malloc(sizeof(listnode)))==NULL){printf("malloc is failed\n");return -1;}p->data=value;p->next=NULL;//2 locate locate locate locate locate tail nodeq=H;while(q->next!=NULL){q=q->next;}//insert;q->next =p;return 0;
}

2.链表查找

linklist list_get(linklist H,int pos)
{linklist p;int i;if(H==NULL)//创建链表是否成功{printf("H is NULL\n");return NULL;}if(pos ==-1)//查找位子-1时H（头节点）{return H;}p=H;i=-1;//查找位置为x，只需要移动x+1次，所以从-1开始while(i<pos){p=p->next;if(p==NULL)//查找位置超出了链表长度{printf("pos is invalid\n");return NULL;}i++;}return p;//返回指向锁查找位置的指针

3.链表任意位置的插入

1.需要找到插入位置的前一个节点指针

2.需要创一个新节点，新节点指向需要插入的value

3.更新两个指针指向

int list_insert(linklist H,data_t value,int pos)
{linklist p;linklist q;if(H==NULL){printf("H is NULL\n");return -1;}//step 1p=list_get(H,pos-1);if(p==NULL){return -1;}//step 2if((q=(linklist)malloc(sizeof(listnode)))==NULL){printf("malloc failed\n");return -1;}q->data= value;q->next=NULL;//step 3q->next=p->next;p->next=q;
}

4.链表删除某个节点

删除节点要考虑到内存的释放，节点内存我门用malloc申请的，释放就用free，删除哪一个节点就free那一节点，只申请不释放就会有内存问题。

删除结点与插入的思想相似，

1.用p找到要删除节点的前一个节点

2.使用一个指针q指向要删除的节点

3.之后p->next=q->next，这时q指向的节点就被独立出来了，

3.用free释放内存。

int list_delete(linklist H,int pos)
{linklist p;linklist q;if(H==NULL){printf("H is empty\n");return -1;}//1p=list_get(H,pos-1);if(p==NULL) return -1;if(p->next==NULL) {printf("pos is invalid\n");return -1;}//2q=p->next;//3p->next=q->next;//4printf("fress:%d\n",q->data);free(q);q=NULL;return 0;
}

5.删除整个链表

linklist list_free(linklist H)
{
        if(H==NULL)
        {
                printf("H is invalid\n");
                return NULL;
        }
        printf("free:");
        while(H!=NULL)
        {
                linklist p=H;
                H=H->next;
                printf("%d",p->data);
                free(p);
        }
        puts("");

        return NULL;
}