数据结构线性表的经典笔试面试题-白红宇

数据结构线性表的经典笔试面试题

阅读量：4970 次

发布时间：2019-06-12

本文共 12276 字，大约阅读时间需要 40 分钟。

1.建立一个顺序存储的线性表，查找顺序表中第一个出现的值为z的元素并输出其位置。

1 package com.neusoft.exercise; 2 import com.neusoft.List.SequenceList; 3 /** 4  * @author zhao-chj 5  *    建立一个顺序存储的线性表，查找顺序表中第一个出现的值为z 6  *的元素并输出其位置。 7  *1.建立一个顺序存储的线性表 8  *2.首先初始化线性表，并且插入值为z的元素 9  *3.查找第一个出现值为z的元素10  *4.对于位置的判断需要考虑是否符合要求11  *5.并输出该元素的位置12  */13 public class TestLinearTable01 {14     public static void main(String[] args) {15          //1.建立一个顺序存储的线性表16         SequenceList L = new SequenceList(10);17          //2.首先初始化线性表，并且插入值为z的元素18         L.insert(0, 'a');19         L.insert(1, 'z');20         L.insert(2, 'd');21         L.insert(3, 'm');22         L.insert(4, 'z');23          //3.查找第一个出现值为z的元素24         int location = L.indexOf('z');25          //4.对于位置的判断需要考虑是否符合要求26         if (location!=-1) {27             System.out.println("第一次出现z元素的位置为："+location);28         }else {29             System.out.println("顺序表中不存在为z的元素");30         }31          //5.并输出该元素的位置32     }33 }

输出结果为：

2.编程实现查找顺序线性表(0,1,2,3,...n-1)中第i个数据元素的直接前驱和后继，并输出他的值。在顺序表中实现。

1 package com.neusoft.exercise; 2 import java.util.Scanner; 3 import com.neusoft.List.SequenceList; 4  5 /** 6  * @author zhao-chj 7  * 题2：编程实现查找线性表(0,1,2,3,...n-1)中第i个数据元素 8  * 的直接前驱和后继，并输出他的值。在顺序表中实现。 9  * 1.初始化线性表并构造一个有50个空间的顺序表10  * 2.在线性表中插入元素，按照(i,i),i=0,1,2...11  * 3.用户输入i的值，表示查找第几个元素的前驱和后继12  * 4.查找线性表中第i个元素的前驱，并输出13  * 5.查找线性表中的第i个元素的后继，并输出14  */15 public class TestLinearTable02 {16     public static void main(String[] args) {17          // 1.初始化线性表并构造一个有50个空间的顺序表18         SequenceList L = new SequenceList(50);19          // 2.在线性表中插入元素，按照(i,i),i=0,1,2...20         int n=10;21         for (int i = 0; i < n; i++) {22             L.insert(i, i);23         }24          // 3.用户输入i的值，表示查找第几个元素的前驱和后继25         System.out.println("请您输入要查询的元素");26         int in = new Scanner(System.in).nextInt();27          // 4.查找线性表中第i个元素的前驱，并输出28         if (in>0&&in
     
      =0&&in

输出结果为：

3.实现以单链表形式的线性表中查找第i个元素的直接前驱和后继

1 package com.neusoft.exercise; 2  3 import java.util.Scanner; 4  5 import com.neusoft.link.LinkedList; 6  7 /** 8  * @author zhao-chj 9  * 实现以单链表形式的线性表中查找第i个元素的直接前驱和后继10  * 1.初始化单链表，并用for循环赋值11  * 2.用户输入要查询单链表中第i个值12  * 3.调用单链表的方法或函数去实现查找第i个元素的直接前驱和后继13  */14 public class TestLinearTable03 {15     public static void main(String[] args) {16         int n=10;17          //1.初始化单链表，并用for循环赋值18         LinkedList L = new LinkedList();19         for (int i = 0; i < n; i++) {20             L.insert(i, i);21         }22         L.display();23          //2.用户输入要查询单链表中第i个值24         System.out.println("请输入第i个值~");25         int input = new Scanner(System.in).nextInt();26          //3.调用单链表的方法或函数去实现查找第i个元素的直接前驱和后继27         if (input>0&&input
     
      =0&&input

结果为：

4.实现以删除单链表中的重复元素(去重)

1 package com.neusoft.exercise; 2 import com.neusoft.link.LinkedList; 3 import com.neusoft.link.Node; 4  5 /** 6  * @author zhao-chj 7  * 实现以删除单链表中的重复元素(去重) 8  * 1.初始化单链表，并用尾插法或者头插法赋值 9  * 2.显示插入元素的信息,使用display方法10  * 3.实现删除重复节点方法11  * 4.显示输出删除重复节点的值后的单链表12  */13 public class TestLinearTable04 {14     public static void main(String[] args) {15         System.out.println("请输入单链表中的10 个节点的值~");16          //1.初始化单链表，并用for循环赋值17         LinkedList L = new LinkedList(10,true);//true表示采用尾插法18         System.out.println("插入之后单链表中的各个节点的值为：");19         L.display();20         //2.删除重复节点方法21         removeRepeatElement(L);22         //3.显示输出删除重复节点的值后的单链表23         System.out.println("显示输出删除重复节点的值后的单链表:");24         L.display();25     }26 27     private static void removeRepeatElement(LinkedList l) {28         // TODO 删除重复节点方法29         Node p =l.head.next;//p节点指向后继元素30         Node q =null;//q节点指向前去元素31         while(p!=null){
   //从头结点开始查找32             int order = l.indexOf(p.data);33             q=p.next;34             while(q!=null){35                 if ((p.data).equals(q.data)) {36                     l.remove(order+1);37                 }else {38                     order++;39                 }40                 q=q.next;//依次寻找后继节点相同的值41             }42             p=p.next;//依次拿后续的每个元素和内层循环的值进行对比43         }44         45     }    46 }

结果为:

注意：单链表的操作类务必不能出错，请参考以下代码

修改了display()方法，insert()方法(去掉了i==0的情况，因为linkedlist是带头结点的单链表)

1 package com.neusoft.link;  2 /**  3  * 带头结点的单链表  4  */  5 import java.util.Scanner;  6   7 import com.neusoft.List.IList;  8 public class LinkedList implements IList {  9     public Node head;//链表的头指针 10     public LinkedList() { 11         head = new Node();//初始化头结点 12     } 13     public LinkedList(int n,boolean order){ 14         //如果order=1采用尾插法，如果order=2采用头插法 15         this(); 16         if (order) { 17             create1(n); 18         }else { 19             create2(n); 20         } 21     } 22     private void create1(int n) { 23         //尾插法 24         Scanner sc = new Scanner(System.in); 25         for (int i = 0; i < n; i++) { 26             insert(length(), sc.next()); 27         } 28     } 29     private void create2(int n) { 30         //头插法 31         Scanner sc = new Scanner(System.in); 32         for (int i = 0; i < n; i++) { 33             insert(0, sc.next()); 34         } 35     } 36  37     @Override 38     public void clear() { 39         //置空 40         head.data=null; 41         head.next=null; 42     } 43  44     @Override 45     public boolean isEmpty() { 46         // 判空 47         return head.next==null; 48     } 49     @Override 50     public int length() { 51         // 链表的长度 52         Node p = head.next; 53         int length=0; 54         while (p!=null) { 55             p=p.next; //指向后继节点 56             length++; 57         } 58         return length; 59     } 60  61     @Override 62     public Object get(int i) { 63         // 读取链表中第i个节点 64         Node p = head.next; 65         int j=0; 66         if (j>i||p==null) { 67             System.out.println("第"+i+"个元素不存在"); 68         } 69         while (p!=null&&j
      
       i-1||p==null) { 86             System.out.println("插入位置不合法"); 87         } 88         Node s = new Node(x);//新开辟的s节点 89         //从链表中间或表尾进行插入 90         s.next=p.next; 91         p.next=s; 92     } 93  94     @Override 95     public void remove(int i) { 96         // 删除单链表的第i个节点 97         Node p = head; 98         int j=-1; 99         while (p.next!=null&&j
       
        i-1||p.next==null) {104             System.out.println("删除位置不合法");105         }106         p.next=p.next.next;107     }108 109     @Override110     public int indexOf(Object x) {111         // 查找值为x的位置112         Node p = head.next;113         int j=0;114         while (p!=null&&!p.data.equals(x)) {115             p= p.next;116             j++;117         }118         if (p!=null) {119             return  j;120         }else {121             return -1;122         }123     }124 125     @Override126     public void display() {127         // 输出单链表的所有节点128         Node node = head.next;129         while(node !=null){130             System.out.print(node.data+" ");131             node=node.next;132         }133         System.out.println();134     }135     @Override136     public int remove(Object i) {137         // TODO Auto-generated method stub138         return 0;139     }140 141 142 }

带头结点的单链表

4.合并两个单链表为一有序链表(链表的合并)

1 package com.neusoft.exercise; 2  3 import java.util.Scanner; 4  5 import com.neusoft.link.LinkedList; 6 import com.neusoft.link.Node; 7  8 /** 9  * @author zhao-chj10  * 合并两个单链表为一有序链表11  * 将两个有序的单链表LA(有m个元素)和LB(有n个元素),要求元素均已从小到大的升序排列12  * 合并成一个有序的单链表LA13  * 1.使用尾插法建立LA和LB两个单链表,初始化LA的个数m和LB的个数n需要用户输入14  * 2.编写合并单链表为一个链表的算法,实现LA和LB其中的元素分别按从小到大顺序排列15  * 3.核心思想为：归并两个按照值非递减排列的带头结点的单链表LA和LB,得到新的带头结点16  * 的单链表LA,且LA也按照值的非递减顺序排列,返回LA作为最后结果。17  * 作业：从大到小实现上述要求18  */19 public class TestLinearTable05 {20     public static void main(String[] args) {21         int m=0,n=0;22         //1.使用尾插法建立LA和LB两个单链表,初始化LA的个数m和LB的个数n需要用户输入23          Scanner sc = new Scanner(System.in);24          System.out.println("请输入LA链表的个数：");25          m = sc.nextInt();26          System.out.println("请按照非递减的顺序输入"+m+"个数字");27          LinkedList LA= new LinkedList(m,true);28          System.out.println("请输入LB链表的个数：");29          n=sc.nextInt();30          System.out.println("请按照非递减的顺序输入"+n+"个数字");31          LinkedList LB= new LinkedList(n,true);32         //2.编写合并单链表为一个链表的算法,实现LA和LB其中的元素分别按从小到大顺序排列33         System.out.println("将单链表LA和LB归并后，新的单链表LA中各个节点为：");34         LinkedList LA_new=mergeList(LA,LB);35         //3.核心思想为：归并两个按照值非递减排列的带头结点的单链表LA和LB,得到新的带头结点36              //的单链表LA,且LA也按照值的非递减顺序排列,返回LA作为最后结果。37         LA_new.display();38     }39 40     private static LinkedList mergeList(LinkedList LA,LinkedList LB) {41         // TODO 合并单链表的函数42         Node pa=LA.head.next;43         Node pb=LB.head.next;44         Node pc=LA.head;45         int da,db;46         while(pa!=null&&pb!=null){47              da = Integer.valueOf(pa.data.toString());48              db = Integer.valueOf(pb.data.toString());49              if (da<=db) {50               pc.next=pa;//将LA节点加入到新的LA节点中51               pc=pa;52               pa=pa.next;//如果da
     
      db成立则pb指针依次后移57             }58         }59         //如果LA和LB链表不相等的时候，需要将元素多的链表的剩余元素插入到新建立的LA中60         pc.next=(pa!=null?pa:pb);61         return LA;62     }63 }

涉及到的单链表数据结构类LinkedList

1 package com.neusoft.link;  2 /**  3  * 带头结点的单链表  4  */  5 import java.util.Scanner;  6   7 import com.neusoft.List.IList;  8 public class LinkedList implements IList {  9     public Node head;//链表的头指针 10     public LinkedList() { 11         head = new Node();//初始化头结点 12     } 13     public LinkedList(int n,boolean order){ 14         //如果order=1采用尾插法，如果order=2采用头插法 15         this(); 16         if (order) { 17             create1(n); 18         }else { 19             create2(n); 20         } 21     } 22     private void create1(int n) { 23         //尾插法 24         Scanner sc = new Scanner(System.in); 25         for (int i = 0; i < n; i++) { 26             insert(length(), sc.next()); 27         } 28     } 29     private void create2(int n) { 30         //头插法 31         Scanner sc = new Scanner(System.in); 32         for (int i = 0; i < n; i++) { 33             insert(0, sc.next()); 34         } 35     } 36  37     @Override 38     public void clear() { 39         //置空 40         head.data=null; 41         head.next=null; 42     } 43  44     @Override 45     public boolean isEmpty() { 46         // 判空 47         return head.next==null; 48     } 49     @Override 50     public int length() { 51         // 链表的长度 52         Node p = head.next; 53         int length=0; 54         while (p!=null) { 55             p=p.next; //指向后继节点 56             length++; 57         } 58         return length; 59     } 60  61     @Override 62     public Object get(int i) { 63         // 读取链表中第i个节点 64         Node p = head.next; 65         int j=0; 66         if (j>i||p==null) { 67             System.out.println("第"+i+"个元素不存在"); 68         } 69         while (p!=null&&j
      
       i-1||p==null) { 86             System.out.println("插入位置不合法"); 87         } 88         Node s = new Node(x);//新开辟的s节点 89         //从链表中间或表尾进行插入 90         s.next=p.next; 91         p.next=s; 92     } 93  94     @Override 95     public void remove(int i) { 96         // 删除单链表的第i个节点 97         Node p = head; 98         int j=-1; 99         while (p.next!=null&&j
       
        i-1||p.next==null) {104             System.out.println("删除位置不合法");105         }106         p.next=p.next.next;107     }108 109     @Override110     public int indexOf(Object x) {111         // 查找值为x的位置112         Node p = head.next;113         int j=0;114         while (p!=null&&!p.data.equals(x)) {115             p= p.next;116             j++;117         }118         if (p!=null) {119             return  j;120         }else {121             return -1;122         }123     }124 125     @Override126     public void display() {127         // 输出单链表的所有节点128         Node node = head.next;129         while(node !=null){130             System.out.print(node.data+" ");131             node=node.next;132         }133         System.out.println();134     }135     @Override136     public int remove(Object i) {137         // TODO Auto-generated method stub138         return 0;139     }140 141 142 }

点击+展开代码

结果分析：

转载于:https://www.cnblogs.com/jackchen-Net/p/6549793.html

你可能感兴趣的文章