【数据结构】 线性表

线性表的定义和特点

线性表的定义

线性表是n个类型相同元素的有限序列，通常记作($a_1$,$a_2$,$a_3$,…,$a_n$)

线性表的特点

1.集合中必存在唯一的一个第一元素

2.集合中必存在唯一的一个最后元素

3.除最后元素之外，均有唯一的后继

4.除第一元素之外，均有唯一的前驱

线性表的抽象数据类型描述

ADT List {

​ 数据对象：D={$a_i$|$a_j$ $\in$ElemSet,i=1,2…,n,n$\geqslant$0}

​ {称n为线性表的表长；

​ 称n=0时的线性表为空表}

​ 数据关系：R={<$a_{i-1}$,$a_i$>,$a_i$ $\in$ D,i=2,3,…,n}

​ 基本操作：

​ InitList(&L) //构造空线性表

​ DestoryList(&L) //销毁线性表L

​ ListEmpty(L) // 判断L是否空

​ ListLength(L) //求L长度

​ PriorElem(L,cur_e,&pre_e) //求前驱

​ NextElem(L,cur_e,&next_e) //求后继

​ GetElem(L,i,&e) //取i位置的值

​ PutElem(&L,i,e) //线性表赋值

​ LocateElem(L,e,compare()) //在线性表中查找e

​ ListTraverse(L,visit()) //遍历线性表

​ ClearList(&L) //清空线性表

​ ListInsert(&L,i,e) //在i位置插入e

​ ListDelete(&L,i,&e) //删除i位置的元素

​ }ADT List

线性表的顺序表示和实现

存储结构实现

用一组地址连续的存储单元依次存放线性表中的数据元素

#define LIST_INIT_SIZE 80
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{
  ElemType *elem;
  int length;
  int listsize;
}SqList;

基本操作实现

#include <stdio.h>
#include<stdlib.h>
#define LIST_INIT_SIZE 80
#define LISTINCREMENT 10
#define OVERFLOW 0
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
typedef int Elemtype;
typedef struct{
    Elemtype *elem;
    int length;
    int listsize;
}SqList;
void InitList_Sq(SqList &L){
    L.elem=(Elemtype*)malloc(LIST_INIT_SIZE*sizeof(Elemtype));
    if(!L.elem)
    {
        exit(OVERFLOW);
    }
    L.length=0;
    L.listsize=LIST_INIT_SIZE;
    printf("InitList SqList successfully.\n");
}
void ShowList_Sq(SqList L){
    for(int i=0;i<=L.length;i++)
    {
        printf("%d\n",L.elem[i]);
    }
}
int DestoryList(SqList &L){
    free(L.elem);
    return OK;
}
void ListEmpty(SqList L){
    if (L.length==0)
    {
        printf("SqList is empty.\n");
    }
    else
    {
        printf("SqList is not empty.\n");
    }
}

int ListLength(SqList L){
    return L.length;
}
void PriorElem(SqList L,int cur_e,Elemtype &pre_e ){
    if(cur_e<=0||L.length==0||cur_e>L.length)
    {
        printf("ERROR!");
        exit(-1);
    }
    else
        pre_e=L.elem[cur_e-1];
}
void ListInsert_Sq(SqList &L,int i,Elemtype e){
    for (int j=L.length-1;j>=i-1;--j)
    {
        L.elem[j+1]=L.elem[j];
    }
    L.elem[i-1]=e;
    ++L.length;
    printf("Insert operation succeed.");
    if(i<1||i>L.length+1) printf("ERROR!");
    if (L.length>=L.listsize){
        Elemtype *newbase;
        newbase=(Elemtype*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(Elemtype));
        if(!newbase) printf("failed!");
        L.elem=newbase;
        L.listsize+=LISTINCREMENT;
        
    }
}
void ListDelete_Sq(SqList &L,int i,Elemtype &e){
    if((i<1)||(i>L.length))
    {
        printf("ERROR!");
        exit(0);
    }
    e=L.elem[i-1];
    for(int j=i-1;j<L.length-1;j++)
    {
        L.elem[j]=L.elem[j+1];
    }
    L.length--;
    printf("delete succeed.");
}
int main(){
    
    while(1){
        printf("0---exit\n1--InitList_Sq\n2--DestoryList\n3--ShowList_Sq\n4--ListEmpty\n5--ListLength\n6--PriorElem\n7--ListInsert_Sq\n8--ListDelete_Sq\n");
        printf("================================\n");
        int temp;SqList L;
        printf("input button:");
        scanf("%d",&temp);
        if(temp==0) {
            printf("process exit.");
            exit(0);
            
        }
        if(temp==1) InitList_Sq(L);
        if(temp==2) DestoryList(L);
        if(temp==3) ShowList_Sq(L);
        if(temp==4) ListEmpty(L);
        if(temp==5) printf("List length:%d\n",ListLength(L));
        if(temp==6){
            Elemtype pre_e;
            int cur_e;
            printf("input cur_e:");
            scanf("%d",&cur_e);
            PriorElem(L, cur_e, pre_e);
            printf("PriorElem is:%d",pre_e);
        }
        if(temp==7){
            Elemtype e;
            int i;
            printf("insert before i:");
            scanf("%d",&i);
            printf("input data(int):");
            scanf("%d",&e);
            ListInsert_Sq(L, i, e);
        }
        if(temp==8){
            Elemtype e;
            int i;
            printf("input number to delete:");
            scanf("%d",&i);
            ListDelete_Sq(L, i, e);
        }
    }
}

顺序表的优缺点

优点：节省存储空间；对线性表中的第i个结点的操作易于实现；容易查找一个结点的前驱和后继

缺点：插入和删除需要移动数据；建立空表时较难确定所需的存储空间

线性表的链式表示和实现

存储结构

typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

基本操作实现

#include <iostream>
#define TRUE 1;
#define FALSE 0;
#define OK 1;
using namespace std;
typedef int ElemType;
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
void InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));
    L->next=NULL;
}
int ListEmpty(LinkList L){
    if(L==NULL)
    {return TRUE;}
    else
    {return FALSE;}
}
int GetElem_L(LinkList L,int i,ElemType &e){
    LNode* p;
    p=(LNode *)malloc(sizeof(LNode));
    p=L->next;
    int j=1;
    while(p&&j<i)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i)
    {
        cout<<"ERROR!"<<endl;
        exit(0);
        
    }
    e = p->data;
    return OK;
    
}
void ListInsert_L(LinkList &L,int i,ElemType e){
    LNode* p=L;
    int j=0;
    while(p&&j<i-1)
    {
        p=p->next;
        ++j;
    }
    if(!p||j>i-1)
    {
        cout<<"ERROR!"<<endl;
        exit(0);
    }
    LNode *s;
    s=(LinkList)malloc(sizeof(LNode));
    s->data=e;
    s->next=p->next;
    p->next=s;
    cout<<"Insert succeed."<<endl;
}
void ListDelete_L(LinkList &L,int i,ElemType &e){
    LNode *p=L;
    int j=0;
    while(p->next&&j<i-1)
    {
        p=p->next;
        ++j;
    }
    if(!(p->next)||j>i-1)
    {
        cout<<"ERROR!"<<endl;
        exit(0);
    }
    LNode *q=p->next;
    p->next=q->next;
    e=q->data;
    free(q);
    cout<<"Delete succeed."<<endl;
}
void ClearList(LinkList &L){
    while(L->next){
        LNode *p;
        p=L->next;
        L->next=p->next;
        free(p);
    }
}
int main(){
    LinkList L;
    InitList(L);
    ElemType e;
    e=1;
    ListInsert_L(L, 1, e);
    L->next->next=NULL;
    cout<<L->next->next<<endl;
}

循环链表

单链表的最后一个结点的指针指向头指针

优点是从表中任意结点出发都可以找到其他结点

循环链表采用头尾指针，因为这样查找第一个结点和最后一个结点都容易

双向链表

存储实现

typedef int ElemType;
typedef struct DuLNode{
  ElemType data;
  struct DuLNode* prior;
  struct DuLNode* next;
}DuLNode,*DuLinkList;