从0开始——线性表

一、ADT：抽象数据类型(abstract data type)

之前学习过ADT的概念：其实就是数据+操作的集合，例如未来我们要学习到的[表、树、图]，以及他们的相关的[操作]一起称之为抽象数据类型，未来学习以此展开！

二、线性表

1.定义
0个或者多个数据元素的有限序列。

2.线性表抽象数据类型 ADT
线性表分顺序存储结构和链式存储结构，分别称为顺序表，链表

ADT 线性表(SqList)：顺序表
Data
  线性表的数据对象集合为{a1,a2,...an},没个元素的类型均为DataType。
Operation:
InitList(L)    初始化线性表，建立一个空的线性表
ListEmpty(*L)  判断线性表是否为空，空返回true
ClearList(*L)  清空线性表
GetElem(L,I,*e) 获取线性表L中的第i个元素给e
LocateElem(L,e)在线性表L中查找元素e，若存在返回e的下标，否则返回0
ListLength(L) 返回线性表的长度
ListInsert(*L,i,e)在线性表L中的第i个位置插入新元素e
ListDelete(*L,i,*e)删除线性表L中的第i个位置的元素，并用e返回其值

3.顺序表的实现

/*
ADT：顺序表  
*/

#include <stdio.h>;
#include <windows.h>;

#define MAXSIZE 20//顺序表的最大长度
typedef int ElemType;//这里ElemType要根据实际需求去定义
#define ERROR 0
#define OK 1

typedef struct 
{
    ElemType data[MAXSIZE];//用数组存储线性表中的元素
    int len;//顺序表长度 
} SqList;

//初始化顺序表 
void InitList(SqList *L)
{
    printf("在init函数中 L=%x &L =%x *L =%x\n",L,&L,*L);
    if(L == NULL)
        return;
    (L)->len = 0;   
    printf("初始化线性表成功\n");   
}
//判断线性表是否为空，空返回true
boolean ListEmpty(SqList *L)
{
    if(L->len == 0)
    {
        printf("线性表为空\n");
        return 1;
    }
    else
    {
        printf("线性表 不为 空\n");
        return 0;       
    }   
}
//清空线性表
ClearList(SqList *L)
{
    printf("清空线性表\n");
    L->len = 0;         
} 
//获取线性表L中的第i个元素给e 
int GetElem(SqList *L,int i,ElemType *e)
{
    if(L->len==0 || i<0 || i> L->len)
        return ERROR;
    *e = L->data[i-1];
    printf("线性表L中的第%d个元素为%d\n",i,*e); 
    return OK;  
}
//在线性表L中查找元素e，若存在返回e的下标，否则返回0
LocateElem(SqList *L,ElemType e)
{
    int i;
    for(i=0; i < L->len; i++)
    {
        if(e == L->data[i])
        {
            printf("线性表L中的找到元素%d,下标为%d\n",e,i);
            return i;//返回下标 
        }
            
    }
    printf("线性表L中的找不到元素%d\n",e);
    return ERROR;//返回0 
}
//返回线性表的长度 
int ListLength(SqList *L)
{
    printf("线性表L的长度为%d\n",L->len);
    return L->len;
} 
//在线性表L中的第i个位置插入新元素e
int ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if(L->len== MAXSIZE)
    {
        printf("数组已满，插入失败\n");
        return ERROR;
    }
    if(i < 1 || i > L->len+1)
    {
        printf("插入位置有误\n");
        return ERROR;
    }
    for(k=L->len-1;k>=i-1;k--)
        L->data[k+1] = L->data[k];//元素往后移动
    L->data[i-1] = e; //插入元素 
    L->len++;//长度加1 
    return OK;
}
//删除线性表L中的第i个位置的元素，并用e返回其值
int ListDelete(SqList *L,int i,ElemType *e)
{
    int j; 
    if(i<1 || i>L->len)
    {
        printf("删除位置有误\n");
        return ERROR; 
    } 
    *e=L->data[i-1];//记录会删掉的元素 
    printf("删除掉的元素为%d\n",*e);
    for(j=i-1;j<L->len-1;j++)
    {
        L->data[j]=L->data[j+1];
    }
    L->len--;
    
    return OK;
}
//打印顺序表
void show(SqList *L)
{
    int i;
    for(i=0 ;i < L->len;i++)
        printf("%d ",L->data[i]);
    printf("\n");
} 

int main()
{   
    SqList *L  = (SqList*)malloc(sizeof(SqList));;
    printf("分配之前L=%x &L =%x *L =%x \n",L,&L,*L);
    int i,temp;
    InitList(L);
    printf("分配之后 L=%x &L =%x *L =%x \n\n",L,&L,*L);
    for(i=1;i<=15;i++)
        ListInsert(L,i,i);  
    show(L);
    ListLength(L);
    GetElem(L,8,&temp);
    LocateElem(L,10);
    LocateElem(L,88);
    ListLength(L);
    ListEmpty(L);
    ListDelete(L,6,&temp);
    show(L);
    system("pause");
    return OK;
}

运行结果

顺序表

4.链表的实现

/*
ADT 线性表(SqList)：链表
Data
  线性表的数据对象集合为{a1,a2,...an},没个元素的类型均为DataType。
Operation:
InitList(L)    初始化线性表，建立一个空的线性表
ListEmpty(*L)  判断线性表是否为空，空返回true
ClearList(*L)  清空线性表
GetElem(L,I,*e) 获取线性表L中的第i个元素给e
LocateElem(L,e)在线性表L中查找元素e，若存在返回e的下标，否则返回0
ListLength(L) 返回线性表的长度
ListInsert(*L,i,e)在线性表L中的第i个位置插入新元素e
ListDelete(*L,i,*e)删除线性表L中的第i个位置的元素，并用e返回其值
*/

#include <stdio.h> 
#include <windows.h>

#define OK 1
#define ERROR 0
typedef int ElemType;//这里ElemType要根据实际需求去定义

typedef struct Node
{
    ElemType data;//保存数据
    struct Node * next; 
}Node,*LinkList;//注意这里LinkList 是一个一级指针
//初始化线性表，建立一个空的线性表
LinkList InitList()
{
    //创建头结点 
    LinkList head = (LinkList)malloc(sizeof(Node));
    if(head ==NULL)
    {
        printf("初始化失败\n"); 
        return NULL;
    }
    printf("初始化成功\n");
    head->data = 0;//头结点的data保存链表的长度
    head->next=NULL; 
    return head;
}
//判断线性表是否为空，空返回true 
boolean ListEmpty(LinkList L)
{
    if(L->next == NULL)
        printf("链表为空\n");
    else
        printf("链表不为空\n");
    return L->next ==NULL;  
}
//获取线性表L中的第i个元素给e 
int GetElem(LinkList L,int i,ElemType *e)
{
    LinkList p =L;//指向头结点
    int j =1;
    while(p->next != NULL && j<=i)
    {
        p=p->next;
        j++;
    }   
    if(p ==NULL || j>i+1 || j<=0)
    {
        printf("获取出错\n");
        return ERROR;   
    }
    printf("第%d个元素的值为%d\n",i,p->data);
    return OK;
        
}
//在线性表L中查找元素e，若存在返回e的下标，否则返回0
int LocateElem(LinkList L,ElemType e)
{
    LinkList p = L;//指向头结点
    int j=1;
    while(p->next != NULL)
    {
        if(p->next->data == e)
        {
            printf("元素%d在第%d个位置\n",e,j);
            return j;
        }
        p=p->next;
        j++;
    }
    printf("链表中不包含元素%d\n",e);
    return ERROR;   
}
//返回线性表的长度
int ListLength(LinkList L) 
{
    printf("链表长度为%d\n",L->data);
    return L->data; 
}
// 尾插法：在线性表L中的第i个位置插入新元素e
int ListTailInsert(LinkList L,int i,ElemType e)
{
    LinkList p=L,s;//p指向头结点 
    int j = 1;
    while(p->next !=NULL && j<i)
    {
        p= p->next;
        j++;
    }
    if(p == NULL || j>i)
    {
        printf("插入位置有误\n");
        return ERROR;
    }
    s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    L->data++;//链表长度+1
    return OK;
        
}
//头插法
int ListHeadInsert(LinkList L,ElemType e)
{
    LinkList p = L;//指向头结点
    LinkList s = (LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    p->data++;//链表长度+1 
    return OK ; 
} 
//删除线性表L中的第i个位置的元素，并用e返回其值
int ListDelete(LinkList L,int i,ElemType *e)
{
    int j =1;
    LinkList p,q;   
    p = L;//指向头结点
    while(p->next!=NULL && j<i)
    {
        p=p->next;
        j++;
    } 
    if(p->next == NULL || j>i)
    {
        printf("删除位置有误！\n");
        return ERROR;
    }
    q=p->next;
    p->next = q->next;
    *e = q->data;
    L->data--;//链表长度-1
    free(q);
    printf("删除的节点为%d\n",*e);
    return OK; 
}
//清空顺序表 
void ClearList(LinkList L)
{
    LinkList p,q;
    p = L->next;//指向第一个节点
    while(p!=NULL)
    {
        q=p->next;
        free(p);
        p=q;
    }   
    L->next = NULL; 
}

//打印顺序表 
void showList(LinkList L)
{
    LinkList p=L;//指向头结点 
    
    while(p->next != NULL)
    {
        p=p->next;
        printf("%d ",p->data);  
    }
    printf("\n");
    ListLength(L);//输出链表长度
}

int main()
{
    LinkList head = InitList();
    LinkList head2 = InitList();
    int i,t;
    printf("尾插法创建链表\n"); 
    for(i=1;i<16;i++)
        ListTailInsert(head,i,i);
    showList(head);
    printf("头插法创建链表\n"); 
    for(i=1;i<16;i++)
        ListHeadInsert(head2,i);        
    showList(head2);
    GetElem(head,7,&t); 
    LocateElem(head,13);
    LocateElem(head,20); 
    ListDelete(head,1,&t);
    showList(head);
    system("pause");
    return OK;
}

运行结果

链表