[C++知识库]数据结构（线性表的链式存储）

线性表的链式存储

1，可调用C语言中malloc（）函数向系统申请结点的存储空间。
linklist p;
p=(linklist)mallloc(sizeof(listnode));
则创建一个类型为linklist的结点，且该结点的地址已经存入到变量p中。

2，结点类型描述：

typedef struct node
{
	data_t data;         //结点的数据域
	struct node *next;   //结点的指针域
}listnode ,*linklist;

若说明
listnode A;
linklist p=&A;

3,链表功能的实现、

linklist.h
typedef int data_t;

typedef struct node{
        data_t data;
        struct node *next;
}listnode,linklist;


linklist list_create();
int list_tail_insert(linklist H,data_t value);
linklist list_get(linklist H,int pos);
int list_insert(linklist H,data_t value,int posp;
int list_show(linklist H);
~                                                                                                                         
~                                                                                                                         
~                                   

linklist.c
#include<stdio.h>
#include"linklist.h"


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;
}


int list_tail_insert(linklist H,data_t value)
{       linklist q;
        linklist p;

        if(H==NULL){
		printf("H is NULL\n");
                return -1;
        }
        // new node p
        if((p=(linklist)malloc(sizeof(listnode)))==NULL){
                printf("malloc failed\n");
                return -1;
        }
        p->data=value;
        p->next=NULL;

        //tail node
        q=H;
        while(q->next!=NULL){
                q=q->next;
        }

        //insert
        q->next=p;


        return 0;
        return 0;

}
int list_show(linklist H){
        linklist p;

        if(H==NULL){
                printf("H is NULL\n");
                return -1;
        }

        p=H;
        while(p->next!=NULL){
                printf("%d",p->next->data);
        }
        puts("");

        return 0;
}
linklist list_get(linklit H,int pos)
{

        linklist p;
        int i;

        if(H==NULL){
                printf("H is NULL\n");
                return NULL;

        if(pos==-1){
                return H;
        }

        P=H;
        i=-1;
        while(i<pos){
                p=p->next;
                if(p==NULL){
                        printf("pos is invalid\n");
                        return NULL;
                }
                i++;
        }
        return p;
}
int list_insert(linklist H,data_t value,int pos)
{
        linklist p;
        linklist q;

        if(H==NULL){
                printf(" H is NULL\n");
                return -1;
        }
        //locate node (pos-1)
        p=list_get(H,pos-1);

        if(p==NULL){
                return -1;
        }

        //new node q
        if((q=(linklist )malloc(sizeof(listnode)))==NULL){
                printf("malloc failed\n");
                return -1;

        }

        q->data=value;
        q->next=NULL;
        //insert
        q->next=p->next;
        p->next=q;

        return 0;
}
              

test.c
#include<stdio.h>
#include"linklist.h"

void test_get();
int main(int argc,char *argv[])
{
        test_get();
        return 0;
}

void test_get()
{
        linklist H;
        int value;
        linklist p;
        H=list_create();


        if(H==NULL)
                return;

        printf("input:");
        while(1){
                scanf("%d",&value);
                if(value==-1)
                        break;
                list_tail_insert(H,value);
                       printf("input:");
        }

        list_show(H);


        p=list_insert(H,100,3);
        if(p!=NULL){
                printf("value=%d\n",p->data);
        }

        list_show(H);



}