【数据结构】顺序线性表的实现和链式线性表的实现

梦里梦外; 2021-09-16 07:16 328阅读 0赞

# 前言 #

线性表式最简单且最简单的一种数据结构，是n个数据元素的有序序列。

本篇博客参照了严慧敏版《数据结构（C语言版）》中线性表的实现，在书中，顺序表的存储结构定义如下

typedef struct{
     Element* elem;//存储空间的基址
     int length;//当前长度
     int listsize; //当前分配的存储容量
    
    }SqList;

其中，Element是自定义的抽象数据类型，在本篇博客中，把这个抽象数据类型定义成一个包含学生姓名name和学生学号stuno的Student类型， 如下：

typedef struct{
      char name[10];
      int stuNo;
    }Student;

读者也可以定义其他类型。

# 顺序线性表实现： #

**顺序线性表的优点**：只要确定了存储线性表的起始位置，线性表中的任一数据元素都可以随机读取，所以线性表的顺序存储结构是一种随机读取的存储结构

**顺序线性表的缺点**：插入或删除某个元素时，需要移动大量元素

#include<stdio.h> 
    #include<stdlib.h>
    #include<string.h>
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define TURE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    typedef int Status;
    typedef struct{
      char name[10];
      int stuNo;
    }Student;
    typedef struct{
     Student* student;//存储空间的基址
     int length;//当前长度
     int listsize; //当前分配的存储容量
    
    }SqList;
    int InitList_Sq(SqList &L){
       //构造 一个空的线性表L
       L.student= (Student*)malloc(LIST_INIT_SIZE*sizeof(Student));
       if(!L.student) exit(OVERFLOW);//分配失败
       L.length=0;
       L.listsize = LIST_INIT_SIZE;
       return OK;
    }
    int DestroyList(SqList &L){ //销毁线性表
        free(L.student);
        L.student=NULL;
        L.length=0;
        L.listsize=0;
        if(L.student) return FALSE;
        return OK;
    }
    int ListLength(SqList L){ //获取线性表的长度
        return L.length;
    }
    int ListEmpry(SqList L){//查看线性表是否为空
     if(L.length==0) return TURE;
     else return FALSE;
    }
    int getElem(SqList L,int i,Student &s){ // 用 s 返回线性表的第i个元素
        if(i<1||i>L.length) return ERROR;
        else s=L.student[i-1];
    }
    int ListInsert(SqList &L,int i,Student s){ // 把 s 插入第i个位置
          if(i<1||i>L.length+1) return ERROR;
          if(L.length>=L.listsize){
            //当前存储空间已满时，重新分配空间
            Student* newbase = (Student*)realloc(L.student,(L.listsize+LISTINCREMENT)*sizeof(Student));
            if(!newbase) return OVERFLOW;
            L.student=newbase;
            L.listsize+=LISTINCREMENT;
          }
          Student* q =&(L.student[i-1]);
          for(Student* p = &(L.student[L.length-1]);p>=q;--p){
            //将插入点及其之后的元素依次往后移动
            *(p+1) = *p;
          }
          //插入元素
          *q = s;
          L.length++;
          return OK;
    
    }
    int ListDelete(SqList &L, int i,Student &s){ // 删除第i个元素，并用s返回
          if(i<1||i>L.length) return ERROR;
          Student* p,*q;
          p=&(L.student[i-1]);//要删除的元素
          s=*p;
          q=L.student+L.length-1;//表尾元素的位置
          for(++p;p<=q;p++)
            *(p-1)=*p;
          L.length--;
          return OK;
    
    }
    int compare(Student s1, Student s2){ // 比较函数
      return strcmp(s1.name,s2.name)&&s1.stuNo==s2.stuNo;
    }
    int LocatElem(SqList L,Student s,int(*compare)(Student,Student)){ //
     // 在表中查找第1个值满足compare（）元素的位序
     int i=1;
     Student* p=L.student;
     while(i<=L.length){
        if((*compare)(*p++,s)) i++;
     }
     if(i<=L.length) return i;
     else return 0;
    }
    
    int main() //测试
    {
        SqList s;   //声明一个线性表s
        InitList_Sq(s); // 初始化
        printf("%d",s.listsize); //输出现在线性表s的容量
        Student stu; 
        gets(stu.name); //从键盘输入学生的名字
        stu.stuNo=1; 
        ListInsert(s,1,stu); //插入线性表
        Student stu2;
        getElem(s,1,stu2);//用stu2获取线性表s中的第1个元素
        printf("\n %s %d",stu2.name,stu2.stuNo);//打印相关信息
    }

# 链式线性表的实现 #

**链式线性表的优点**：用一组任意的（可以是连续的，也可以是非连续的）的存储单元存储数据元素；插入和删除元素时比较简单，不需要移动数据元素。

**链式线性表的缺点**：不支持随机存取，只能从头节点依次向后遍历。

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #define LIST_INIT_SIZE 100
    #define LISTINCREMENT 10
    #define TURE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define INFEASIBLE -1
    #define OVERFLOW -2
    typedef int Status;
    typedef struct{
      char name[10];
      int stuNo;
    }Student;
    typedef struct LNode{
      Student student;
      LNode* next;
    }LNode,*LinkList;// LinkList的数据类型为 LNode*;即指向自己的一个指针
    int InitList(LinkList &L){
     // 链表的初始化
     L=(LNode*)malloc(sizeof(LNode)); //头结点
     if(!L) return OVERFLOW;
     L->next=NULL;//头结点没有数据域，只有指向下一个结点的指针域
     return OK;
    }
    int ClearList(LinkList &L){
       LinkList p;
       while(L->next){
        p=L->next;
        L->next=p->next; //让指针指向当前的结点的下一个结点
        free(p);//释放当前结点
       }
       return OK;
    }
    int DestroyList(LinkList &L){
        ClearList(L);
        free(L);//释放头结点空间
        L=NULL; //链表变量归于初始值
        return OK;
    }
    int GetLength(LinkList L){
      //获取链表的长度
      int n=0;
      if(!L) return n;
      while(L->next){
        L=L->next;
        n++;
      }
      return n;
    }
    int isEmpty(LinkList L){
     if(L->next==NULL) return TURE;
     else return FALSE;
    }
    int GetElem(LinkList L,int i,Student &s){
        //获取指定位置的数据
        if(i<1||i>GetLength(L)) return ERROR;
        if(isEmpty(L)) return ERROR;
        int j=0;
        LinkList p=L;
        if(j!=i){
            p=p->next;
            j++;
        }
        s=p->student;
        return OK;
    }
    void scanList(LinkList &L){
        //创建链表
        int i,n;
        LinkList p,q;
        if(L==NULL) n=InitList(L);
        printf("n=%d",n);
        p=L;
        printf("输入学生的个数：");
        scanf("%d",&i);
        for(int j=1;j<=i;j++){
            printf("输入第%d个学生的数据：\n",j);
            q=(LNode*)malloc(sizeof(LNode));
            scanf("%s %d",q->student.name,&(q->student.stuNo));
            printf("%s %d",q->student.name,q->student.stuNo);
            q->next=NULL;
            printf("1");
            p->next=q;
            printf("2");
            p=q;
            printf("3");
        }
    }
    void printList(LinkList L){
        //打印链表
       int i=GetLength(L);
       LinkList p=L->next;
       if(i>0){
        for(int j=1;j<=i;j++){
            printf("%d：%d %s\n",j,p->student.stuNo,p->student.name);
            p=p->next;
        }
       }
    }
    int InsertList(LinkList &L,int i,Student s){
         if(i<1||i>GetLength(L)+1) return ERROR;
         LinkList p,q;
         int j=1;
         q=(LNode*)malloc(sizeof(LNode));
         q->student=s;
         q->next=NULL;
         p=L;
         for(;j<i;j++){
            p=p->next;
         }
         if(j==GetLength(L)+1){
            //插在最后
            p->next=q;
         }
         else{
            //插在中间
            q->next=p->next;
            p->next=q;
         }
         return OK;
    }
    int DeleteList(LinkList &L,int i,Student &s){
        if(i<1||i>GetLength(L)) return ERROR;
        LinkList p=L,q;
        int j=1;
        for(;j<i;j++){
            p=p->next;
        }
        if(j==GetLength(L)){
           //删除尾结点
           free(p->next);
           p->next=NULL;
    
        }else{
            //删除中间的结点
            q=p->next;
            p->next=q->next;
            free(q);
        }
        return OK;
    }
    int main()
    {
        LinkList L;
        printf("length=%d\n",L->next);
        scanList(L);
        printList(L);
    
    
    }