线性表的两种实现(附C与java代码)

傷城~ 2023-07-11 08:49 15阅读 0赞

2.1 认识线性表

线性表的定义：用数据元素的有限序列表示

同一线性表中的元素必定具有相同特性。

线性表中的数据元素可以为简单类型，也可以为复杂类型

线性表基本操作：

  • 初始化
  • 取值
  • 查找
  • 插入
  • 删除
  • 是否为空
  • 线性表长度

2.2 线性表的顺序存储结构实现（数组实现）

C语言中我们定义一个数据结构是通过结构体的定义来实现

  1. #define MAXSIZE 100   //定义最大长度
  2. typedef int ElemType;
  3. //表示 ElemType是int类型，typedef  是起别名的意思   
  4. typedef struct ListCollection{
  6.     ElemType Data[MAXSIZE];   
  7.      // 一种自定义的数据类型，也可以是基本类型            
  8.     int index;
  9. }*List;
  10. //*List是指向ListCollection这个结构体的一个指针，起别名

而在Java中我们通过类class来实现,后面的方法也是在Java类实现，就是写一个类，带上各种方法

  1. public class ListCollection{
  3.     int[] Data;
  4.     int index;
  5. }

  • 初始化操作

    //C语言的初始化操作，首先需要申请一块内存空间
    List MakeList(){

    1. List list;          
    2. list = (List)malloc(sizeof(struct ListCollection));   //申请一块空间
    3. list->index=-1;      // 让长度变为-1，说明里面没有元素，即下标为index
    4. return list;

    }

    // java的初始化操作,通过构造方法
    ListCollection(int max){

    1. Data = new int[max];
    2. index = -1;

    }

  • 是否为空

    //C语言实现，对于C语言不用boolean,用0表示false,1是true
    int isEmpty(List list){

    1. return list->index < 0 ? 1 : 0;

    }

    //java 实现
    boolean isEmpty(){

    1. return index < 0 ? true: false;

    }

  • 获取长度

    //C语言实现
    int getSize(List list){

    1. return list->index;

    }

    //java实现 复杂度O(1)
    int getSize(){

    1. return index;

    }

  • 取值

    //C语言实现
    ElemType getValue(int i,List list){

    1. if(i>list->index||i<0) return -1;
    2. return list->Data[i];

    }

    //java 实现 复杂度O(1)
    int getValue(int i){

    1. if(i>index||i<0) return -1;
    2. return Data[i];

    }

  • 查找

    //C语言实现，复杂度O(n)
    int find(ElemType value,List list){

    1. int i;
    2. if(isEmpty(list)) return -1;
    3. for(i=0;i <= list->index;++i){
    5.     if(list->Data[i]==value) return i;
    6. }
    7. return -1;

    }

    // 简单线性查找，复杂度O(n)
    int find(int value){

    1. if(isEmpty()) return -1;
    2. for(int i = 0;i <= index; ++i){
    4.     if(Data[i]==value) return i;
    5. }
    6. return -1;

    }

  • 插入

    // C语言实现
    int insert(int i,ElemType value,List list){

    1. int j;
    2. if(list->index==MAXSIZE-1){
    4.     printf("已满");
    5.     return 0;
    6. }
    7. if(i>list->index+1||i<0){
    9.     printf("插入位置不正确");
    10.     return 0;
    11. }
    12. for(j=list->index;j>=i;--j){
    14.     list->Data[j+1]=list->Data[j];
    15. }
    16. list->Data[i]=value;
    17. list->index++;
    18. return 1;

    }

    //java 实现 复杂度O(n)
    boolean insert(int i,int value){

    1. if(i>index+1||i<0||index==Data.length()-1)                  
    2.     return false;// i的位置不合法，或者线性表已满
    3. for(int j=index;j>=i;--j){
    5.     Data[j+1] = Data[j];  
    6.   //  从后往前遍历，将上一个值赋给下一个
    7. }
    8. Data[i]=value;
    9. index++;   
    10. return true;

    }

  • 删除

    // c语言实现 复杂度O(n)
    int deleteData(int i,List list){

    1. int j;
    2. if(i>list->index||i<0||list->index<0){
    4.     printf("位置出错或咩有元素");
    5.     return 0;
    6. }
    7. for(j=i;j<list->index;++j){
    9.     list->Data[j]=list->Data[j+1];
    10. }
    11. list->--;
    12. return 1;

    }

    // java实现
    boolean delete(int i){

    1. if(isEmpty()||i>index||i<0){
    3.       return false;//为空或者位置不合法
    4. for(int j=i;j<index;++j){
    6.       Data[j]=Data[j+1];
    7.     //从删除的位置开始，下一个的值赋给上一个。
    8. }
    9. index--;
    10. return true;

    }

C语言实现的另一种写法

  1. #include <stdlib.h>
  2. #include <iostream>
  3. #define MAXSIZE 100
  4. using namespace std; 
  5. typedef int ElemType;
  6. typedef struct Node{
  8.     ElemType *elem;
  9.     int index;
  10. }*ArrList;
  11. void makeList(ArrList list);
  12. int size(ArrList list);
  13. ElemType get(int i,ArrList list);
  14. void set(int i,int value,ArrList list);
  15. int insert(int i,int value,ArrList list);
  16. int deletes(int i,ArrList list);
  17. int main(){
  19. }
  21. void makeList(ArrList list){
  24.     list->elem=new ElemType[MAXSIZE];
  25.     if(!list->elem) return NULL;
  26.     list->index=0;
  27. }
  28. int size(ArrList list){
  30.     if(!list) return 0;
  31.     return list->index;
  32. }
  33. ElemType get(int i,ArrList list){
  35.     if(i<=0||i>list->index) return -1;
  36.     return list->elem[i];
  37. }
  38. void set(int i,ElemType value,ArrList list){
  40.     if(i<=0||i>list->index) return ;
  41.     list->elem[i]=value;
  42. }
  43. int insert(int i,ElemType value,ArrList list){
  45.     int j;
  46.     if(list->index==MAXSIZE) return -1;   //线性表已满,无法插入 
  47.     if(i<=0||i>list->index+1) return -1;    //位置越界
  48.     for(j=list->index;j>=i;--j){
  50.         list->elem[j+1]=list->elem[j];
  51.     }
  52.     list->elem[i]=value;
  53.     list->index++;
  54.     return 1;
  55. }
  56. int deletes(int i,ArrList list){
  58.     int j;
  59.     if(i<=0||i>list->index) return -1;
  60.     for(j=i;j<list->index;++j){
  62.         list->elem[j]=list->elem[j+1];
  63.     }
  64.     list->index--;
  65.     return 1;
  66. }

2.3 线性表实现 （链表实现）

  • 链表的特点：
  1. 逻辑上相邻的数据元素在物理上不一定相邻
  2. 访问时只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点。
  3. 数据元素的个数可以自由扩充
  4. 插入、删除等操作不必移动数据，只需修改链接指针

  5. 存储密度小，
    存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问

    • 三个概念（头指针，头结点，首结点）：
      头指针：是指向链表中第一个结点的指针。
      头结点: 是一个链表的开头，头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。（可有可无）
      首结点：链表真正存储数据的第一个结点。
      在这里插入图片描述

    • 分类：单链表，循环链表，双向链表等

      • 单链表: 单链表中每一个结点由数据域和指针域构成，成一条链，（只能访问后继结点不能访问前趋结点）
        链表结束的条件：link->next==NULL;

    //定义
    struct LinkedList{

    1. ElemType data;
    2. struct LinkList *next;

    }
    //或者
    typedef struct LinkedList{

    1. Elemtype data;
    2. Linked next;

    }*Linked;

循环链表：分为单循环链表和双循环链表，
单循环链表与单链表类似，让最后结点的指针域指头结点。

对循环链表，有时不给出头指针，而给出尾指针可以更方便的找到第一个和最后一个结点
定义与单链表或者双向链表一致，只需要最后结点指向头结点即可
结束条件判断：link->next!=info;(不等于头结点或者是首结点)

双向链表：一个结点中有两个指针域一个数据域，指针域分别指向下一个结点和上一个结点。

  1. //定义
  2. typedef struct DuLNode{
  4.      ElemType   data;            
  5.      struct DuLNode  *prior; 
  6.      struct DuLNode  *next;  
  7. }DuLNode, *DuLinkList

如图：

在这里插入图片描述
线性表单链表代码实现

  1. //宏定义
  2. #define OK 1
  3. #define ERROR 0
  4. #define OVERFLOW -2
  6. //定义
  7. typedef int ElemType;
  8. typedef int Status;
  9. typedef struct LinkedList *Link;
  10. struct LinkedList{
  12.     ElemType data;
  13.     Link next;
  14. };
  16. //方法体
  17. Link CreateInputLinked(int n);
  18. int size(Link link);
  19. Link get(Link link,int i);
  20. void set(Link link,int i,ElemType value);
  21. Status insert(Link link,int i,ElemType value);
  22. Status drop(Link link,int i);
  23. void OutputLink(Link link);
  24. Status DestroyList(Link link);
  25. int main(){
  26.         return 0;};
  28. //初始化加输入
  29. Link CreateInputLinked(int n){
  31.     Link head,temp,node,info;
  32.     head = new LinkedList;
  33.     info = new LinkedList;
  34.     head->next=info;
  35.     info->next = NULL;
  36.     temp = info;
  37.     while(n-->0){
  39.         node = new LinkedList;
  40.         cin>>node->data;
  41.         node->next=NULL;
  42.         temp->next=node;
  43.         temp=temp->next;
  44.     }
  45.     return head;
  46. }
  48. //取长度
  49. int size(Link link){
  51.     Link temp = link->next->next;
  52.     int count=0;
  53.     while(temp){
  55.         count++;
  56.         temp = temp->next;
  57.     }
  58.     return count;
  59. }
  61. // 获得第i个结点
  62. Link get(Link link,int i){
  64.     Link temp = link->next->next;
  65.     int count = 1;
  66.     while(temp&&count<i){
  68.         temp = temp->next;
  69.         count++;
  70.     }
  71.     return count==i ? temp : NULL;
  72. }
  74. //修改第i个结点的数据域
  75. void set(Link link,int i,ElemType value){
  77.     Link temp = link->next->next;
  78.     int count = 1;
  79.     while(temp&&count<i){
  81.         temp = temp->next;
  82.         count++;
  83.     }
  84.     if(count==i) temp->data=value;
  85. }
  87. //插入操作
  88. Status insert(Link link,int i,ElemType value){
  90.     Link left,node;
  91.     if(i==1){
  93.         left = link->next;
  94.     }else{
  96.         left = get(link,i-1);
  97.     }
  98.     if(!left) return ERROR;
  99.     node = new LinkedList;
  100.     node->data=value;
  101.     node->next = left->next;
  102.     left->next = node;
  103.     return OK;
  104. }
  106. //删除操作
  107. Status drop(Link link,int i){
  109.     Link left,mid;
  110.     if(i==1){
  112.         left =link->next;
  113.     }else{
  115.         left = get(link,i-1);
  116.     }
  117.     if(!left) return ERROR;
  118.     mid = left->next;
  119.     left->next=mid->next;
  120.     delete mid;
  121.     return OK;
  122. }
  124. //输出操作
  125. void OutputLink(Link link){
  127.     Link temp = link->next->next;
  128.     while(temp){
  130.         cout<<temp->data<<" ";
  131.         temp=temp->next;
  132.     }
  133.     cout<<endl;
  134. }
  136. //销毁
  137. Status DestroyList(Link link){
  139.     Link tmp;
  140.     while(link){
  142.         tmp=link;
  143.         link=link->next;
  144.         delete tmp;
  145.     }
  146.     return OK;
  147. }

java实现（java只要理解到this本身就是头指针，并且在使用时先初始化再取得当前对象的next，才不会出现NullPointerExpetion，与C语言略微不同）

  1. class NodeList{
  3.     int Data;
  4.     NodeList Next ;
  5.     boolean isEmpty(){
  6.       //判断是否为空
  7.         if(this.Next==null) return true;
  8.         return false;
  9.     }
  10.     int size(){
  11.             // 取长度
  12.         NodeList link=this.Next.Next;
  13.         if(this.isEmpty()) return 0;
  14.         int i=0;
  15.         while(link!=null){
  17.             link=link.Next;
  18.             i++;
  19.         }
  20.         return i;
  21.     }
  22.     NodeList getValue(int i){
  23.         //获取第i个结点
  24.         if(i>size()||i<0) return null;
  25.         NodeList link =this.Next;
  26.         int p = 0;
  27.         while(p<i&&link!=null){
  29.             link=link.Next;
  30.             ++p;
  31.         }
  32.         if(p==i) return link;
  33.         else return null;
  34.     }
  35.     void setValue(int i,int value){
  36.       // 修改第i个值
  37.         NodeList tmp = getValue(i);
  38.         if(tmp==null) return;
  39.         tmp.Data=value;
  40.     }
  41.     boolean insert(int i,int value){
  42.        //插入一个新结点
  43.         if(i<0&&i>size()+1) return false;
  44.         NodeList left;
  45.         if(i==1){
  47.             left = this.Next;
  48.         }else {
  50.             left = getValue(i-1);
  51.         }
  52.         if(left==null) return false;
  53.         NodeList tmp = new NodeList();
  54.         tmp.Data=value;
  55.         tmp.Next=left.Next;
  56.         left.Next=tmp;
  57.         return true;
  58.     }
  59.     boolean delete(int i){
  60.       //删除一个结点
  61.         if(i<0||i>size()) return false;
  62.         NodeList left;
  63.         if(i==1){
  65.             left = this;
  66.         }else {
  68.             left = getValue(i-1);
  69.         }
  70.         if(left==null) return false;
  71.         NodeList tmp =left.Next;
  72.         left.Next = tmp.Next;
  73.         return true;
  74.     }
  75.     void Output(){
  76.       //输出，因为this代表头指针，要两次next才能找到首结点，中间隔了一个头结点
  77.         NodeList link = this.Next.Next;
  78.         while(link!=null){
  80.             System.out.print(link.Data+"  ");
  81.             link=link.Next;
  82.         }
  83.         System.out.println();
  84.     }
  85.     void Input(int n){
  86.       // 输入操作，先初始化再赋值给结点.next，避免空指针异常
  87.         Scanner input =new Scanner(System.in);
  88.         NodeList link =new NodeList();
  89.         this.Next=link;
  90.         while(n-->0){
  92.             NodeList node =new NodeList();
  93.             node.Data=input.nextInt();
  94.             link.Next=node;
  95.             link=link.Next;
  96.         }
  97.     }
  98. }

发表评论

表情：
评论列表 （有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读