数据结构——链表

05. March 2017 深度学习 0

数组静态分配内存,链表动态分配内存;

数组在内存中连续,链表不连续;

数组元素在栈区,链表元素在堆区;

数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);

数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。

package lijian;

import java.util.Scanner;

import org.omg.CORBA.FREE_MEM;

class DATA2{

String key;

    String name;

    int age;

}

class CLType{

DATA2 nodeData = new DATA2();

    CLType nextNode;

    CLType CLAddEnd(CLType head,DATA2 nodeData){

    CLType node,htemp;//node为新增结点

    if((node=new CLType())==null){

    System.out.println(“申请内存失败”);

    return null;

    }else{

    node.nodeData=nodeData;

    node.nextNode=null;

    if(head==null){

    head=node;

    return head;

    }

    htemp=head;

    while (htemp.nextNode!=null) {//指针后移,到最后一个结点

htemp=htemp.nextNode;

}

    htemp.nextNode=node;

    return head;//head 始终为首结点

     }

    }

    CLType CLAddFirst(CLType head,DATA2 nodeData){

    CLType node;

    if((node=new CLType())==null){

    System.out.println(“内存分配失败”);

    return null;

    }

    else {

node.nodeData=nodeData;

node.nextNode=head;

head=node;

return head;

}

    }

    void CLCALLNode(CLType head){

    CLType htemp;

    DATA2 nodeData;

    htemp=head;

    while (htemp!=null) {

nodeData=htemp.nodeData;

System.out.printf(“结点(%s,%s,%d)\n”,nodeData.key,nodeData.name,nodeData.age);

htemp=htemp.nextNode;

}

    }

    CLType CLFindNode(CLType head,String key){

    CLType htemp;

    htemp=head;

    while (htemp!=null) {

if(htemp.nodeData.key.compareTo(key)==0){

returnhtemp;

}

htemp=htemp.nextNode;

}

    return null;

    }

    CLType CLInertNode(CLType head,String findKey,DATA2 nodeData){

    CLType node,nodetemp;

    if((node=new CLType())==null){

    System.out.println(“内存分配失败”);

    return null;

    }

    node.nodeData=nodeData;

    nodetemp=CLFindNode(head, findKey);

    if(nodetemp!=null){

    node.nextNode=nodetemp.nextNode;

    nodetemp.nextNode=node;

    }

    else {

System.out.print(“未找到正确插入位置\n”);

}

    return head;

    }

    int CLDeleteNode(CLType head,String key){

    CLType node,htemp;

    htemp=head;

    node=head;

    while (htemp!=null) {

if (htemp.nodeData.key.compareTo(key)==0) {

node.nextNode=htemp.nextNode;

return 1;

}

else {

node=htemp;

htemp=htemp.nextNode;

}

}

    return 0;

    }

}

public class 链表 {

public static void main(String[] args) {

CLType node,head=null;

CLType CL=new CLType();

String key,findkey;

Scanner input=new Scanner(System.in);

System.out.println(“链表测试,输入关键字,姓名,年龄”);

do{

DATA2 nodeData=new DATA2();

nodeData.key=input.next();

if(nodeData.key.equals(“0”)){

System.out.println(“end”);

break;

}

else {

nodeData.name=input.next();

nodeData.age=input.nextInt();

head=CL.CLAddEnd(head, nodeData);

}

}while(true);

        CL.CLCALLNode(head);

        System.out.println(“输入要插入结点的关键字”);

        findkey=input.next();

        System.out.println(“输入要插入结点的 关键字,姓名和年龄”);

        DATA2 nodeData=new DATA2();

        nodeData.key=input.next();

        nodeData.name=input.next();

        nodeData.age=input.nextInt();

        head=CL.CLInertNode(head,findkey,nodeData);

        CL.CLCALLNode(head);

        System.out.println(“演示要删除结点,输入要删除的关键字”);

        key=input.next();

        CL.CLDeleteNode(head,key);

        CL.CLCALLNode(head);

        System.out.println(“输入查找关键字”);

        key=input.next();

        node=CL.CLFindNode(head, key);

        if(node!=null){

        nodeData=node.nodeData;

        System.out.printf(“结点(%s,%s,%d)\n”,nodeData.key,nodeData.name,nodeData.age);

        }else {

System.out.println(“为找到关键字”);

}

}

}