线性表

• 什么是线性表？
  由n(n>=0)个数据特性相同的元素构成的有序序列称为线性表，线性表中的元素个数n定义为线性表的长度，n=0时称为空表。
• 对于非空的线性表或线性结构
  （1）存在唯一的一个被称作“第一个”的数据元素
  （2）存在唯一的一个被称作“最后一个”的数据元素
  （3）出第一个元素之外,结构中的每个数据元素均只有一个前驱
  （4）除最后一个元素之外,结构中每个数据元素均只有一个后继

线性表基本操作代码实现

#include<iostream>
#define MAXSIZE 100
#define OK 1
#define ERROR 0
using namespace std;
typedef int Status;

struct NumList{
    int *elem;
    int length;
};

/**
 * 初始化顺序表
 * @param L 顺序表
 * @return Ok表示初始化成功
 */
Status InitList(NumList &L){
    L.elem = new int[MAXSIZE];
    if(!L.elem){
        exit(-2);
    }
    L.length = 0;
    return OK;
}
/**
 * 遍历顺序表
 * @param L 顺序表
 */
void ShowList(NumList L){
    if(L.length == 0){
        cout<<"顺序表为空"<<endl;
        return;
    }
    for(int i=0;i<L.length;i++){
        cout<<L.elem[i]<<" ";
    }
    cout<<endl;
}
/**
 * 根据目标元素查找顺序表
 * @param L
 * @param e 要查找的元素
 * @return 返回元素的位置，没找到就返回0
 */
int LocateElem(NumList &L,int e) {
    for(int i=0;i<L.length;i++){
        if(L.elem[i] == e) return i+1;
    }
    return 0;
}
/**
 * 插入元素
 * @param L
 * @param i 要插入的位置
 * @param e 要插入的元素
 * @return
 */
Status ListInsert(NumList &L,int i,int e){
    if(i<1||i>L.length+1||L.length==MAXSIZE){
        cout<<"插入成功"<<endl;
        return ERROR;
    }
    for(int j=L.length-1;j>=i-1;j--){
        L.elem[j+1] = L.elem[j];
    }
    L.elem[i-1] = e;
    ++L.length;
    cout<<"插入成功"<<endl;
    return OK;
}
/**
 * 根据位置删除元素
 * @param L
 * @param i 要算出元素的位置
 * @return
 */
Status ListDelete(NumList &L,int i){
    if (i<1||i>L.length) return ERROR;
    for (int j=i;j<=L.length-1;j++){
        L.elem[j-1] = L.elem[j];
    }
    --L.length;
    cout<<"删除成功"<<endl;
    return OK;
}
/**
 * 删除大于min小于max的元素
 * @param L
 * @param min
 * @param max
 * @return
 */
Status DeleteByNum(NumList &L,int min,int max){
    for(int i=0;i<L.length;i++){
        if(L.elem[i]>min && L.elem[i]<max) {
            ListDelete(L,i+1);
            i--;
        }
    }
    return 0;
}

int main(){
    NumList L;
    *//*初始化顺序表*//*
    InitList(L);
    *//*插入10个元素*//*
    for (int i = 0; i < 10; ++i) {
        ListInsert(L,i,i);
    }
    cout<<"删除元素前的顺序表：";
    ShowList(L);
    *//*删除第二个元素*//*
    ListDelete(L,2);
    cout<<"删除元素后的顺序表：";
    ShowList(L);
    *//*删除大于2小于7的元素*//*
    DeleteByNum(L,2,7);
    cout<<"删除大于2小于7的元素后的顺序表：";
    ShowList(L);
    if (LocateElem(L,7)==0){
       cout<<"元素不存在"<<endl;
    } else{
        cout<<"7为第"<<LocateElem(L,7)<<"个元素";
    }
    return 0;
}

单链表

• 什么是链表
  链表是一种物理存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表的指针链接实现的。链表当中的每一个元素称为一个结点，这些结点可以在程序运行的过程中动态的生成
• 每一个结点分为两个区域：
  data域（存放数据元素）
  next域（存放的是下一个结点的地址）
• 链表的特点：
  插入或删除中间的元素是效率高，查找效率低。

首元结点、头结点、头指针

• 首元结点：指链表中存储第一个元素的结点 如结点“ZHAO”
• 头节点：头结点是在首元结点之前附设一个结点，其指针域指向首元结点。头节点的数据域可以 不存储任何信息，也可以存储与数据元素类型相同的附加信息。如当数据元素为整数型时，可在头节点的数据域存放该链表的长度。
• 头指针：头指针是指向链表中第一个结点的指针，若链表有头结点则头指针指向头结点，若链表没有头节点则头指针指向首元结点

单链表基本操作代码实现

#include <iostream>
#include <string>
#define OK 1
#define ERROR 0
using namespace std;
typedef int Status;

struct ElemType{
    int no;
    string name;
};

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

/*初始化*/
Status InitList(LinkList &L){
    L = new LNode;
    L->next = NULL;
    return OK;
}

/**
 * 查找第i个结点
 * @param L 链表
 * @param i 位置
 * @param e 保存当前结点的数据域
 */
Status GetElem(LinkList &L,int i,ElemType &e){
    LNode* p = L->next;
    int j = 1;
    while (p!=NULL && j<i){
        p = p->next;
        j++;
    }
    if (p==NULL && j>i){
        return ERROR;
    }
    e = p->data;
    return OK;
}

/*遍历链表*/
void Show(LinkList L){
    LNode* p = L->next;
    while (p){
        cout<<p->data.no<<"+"<<p->data.name<<" ";
        p = p->next;
    }
    return;
}

/**
 * 单链表的按学号查找
 * @param L 单链表
 * @param no 学号
 * @return 结点
 */
LNode* LocateElem(LinkList L,int no){
    LNode* p = L->next;
    while (p && p->data.no!=no){
        p = p->next;
    }
    return p;

}

/**
 * 按照位置插入结点
 * @param L 单链表
 * @param i 要插入结点的位置（从1开始）
 * @param e 要插入的结点
 * @return
 */
Status ListInsert(LinkList &L,ElemType a,ElemType b,ElemType e){
    LinkList p = L;
    while (p && (p->data.no!=a.no&&p->data.no!=b.no)){
        p = p->next;
        if(!p->next)return ERROR;
    };
    /*插入结点*/
    LNode* s = new LNode;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

/**
 * 按照位置删除结点
 * @param L 链表
 * @param i 要删除结点的位置
 * @return
 */
Status ListDelete(LinkList &L,int i){
    LinkList p = L;
    int j = 0;
    while (p && j<i-1){
        p = p->next;
        j++;
    }
    if(!p || j>i-1){
        return ERROR;
    }
    LNode *q = p->next;
    p->next = q->next;
    delete q;
    return OK;
}

/**
 * 头插法
 * @param L 链表
 * @param n 插入结点的个数
 */
void CreateList_H(LinkList &L,int n){
    L = new LNode;
    L->next = NULL;
    for (int i = 0; i < n; ++i) {
        LNode* p = new LNode;
        cout<<"输入学号和姓名以添加结点,用空格分隔"<<endl;
        cin>>p->data.no>>p->data.name;
        p->next = L->next;
        L->next = p;
    }
}
/**
 * 尾插法
 * @return
 */
 void CreateList_R(LinkList &L, int n){
     L = new LNode;
     L->next = NULL;//建立带头结点的空链表
     LNode *r = L;
    for (int i = 0; i < n; ++i) {
        LNode* p = new LNode;
        cout<<"输入学号和姓名以添加结点,用空格分隔"<<endl;
        cin>>p->data.no>>p->data.name;
        p->next = NULL;
        r->next = p;
        r = p;
    }
 }

 Status reverse(LinkList &L){
     LNode* p = L->next;
     L->next = NULL;
     while (p){
         LNode* q = p->next;
         p->next = L->next;
         L->next = p;
         p=q;
     }
     return OK;
 }

int main(){
    ElemType e1 = {1,"张三"};
    ElemType e2 = {2,"李四"};
    ElemType e3 = {3,"王五"};
    LNode* L;
    InitList(L);
    //CreateList_H(L,5);
    //ListInsert(L,2,e1);
    //ListDelete(L,1);
    CreateList_R(L,5);
    Show(L);
    cout<<"插入后"<<endl;
    ListInsert(L,e1,e2,e3);
    Show(L);
    cout<<"反转后"<<endl;
    reverse(L);
    Show(L);
}