一、顺序表

顺序表的定义

• 初始化顺序表

//基本操作-初始化一个顺序表
void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++)
        L.data[i] = 0;   //将所有数据元素设置为默认初始值
    L.length = 0; //顺序表初始长度为0
}

• 如果去掉默认值的设置的步骤，则会出现“脏数据”的现象（内存中遗留的）正常情况下把各个数据元素的值设为默认值
• 将length设置为0不可省略

顺序表的实现（动态分配）

//初始化
void InitList(SeqList &L){
    //使用malloc函数申请一片连续的存储空间
    L.data = (int *)malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}
//增加动态数据的长度
void IncreaseSize(SeqList &L,int len){
    int *p = L.data;
    L.data = (int *)malloc((L.MaxSize+len)*sizeof(int));
    for(int i=0;i<L.length;i++){
        L.data[i] = p[i];  //将数据复制到新区域
    L.MaxSize = L.MaxSize + len;  //顺序表最大长度增加len
    free(p);    //释放原来的内存空间
}

realloc函数也可实现

顺序表的查找

顺序表的查找有两种方式：

• 按位查找
• 按值查找
  代码：

//按位查找
ElemType GetElem(SeqList L;int i){
    return L.data[i-1];
}

二、链表

单链表的初始化

单链表的建立

• 尾插法
• 头插法

对应代码

• 尾插法

LinkList List_TailInsert(LinkList &L){  //正向建立单链表
    int x; //设置ElemType为整型
    L = (LinkList)malloc(sizeof(LNode)); //建立头节点
    LNode *s, *r=L;   //r为表尾指针
    scanf("%d",&x);
    while(x!=9999){  //输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode))
        s->data = x;
        r->next = s;
        r = s;                  //r指向新的表尾结点
        scanf("%d",&x);
    }
    r->next = NULL;  //尾结点指针置空
    return L;
}

• 头插法

LinkList List_HeadInsert(LinkList &L){  //逆向建立单链表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode)); //建立头节点
    L->next = NULL; //初始为空链表
    scanf("%d",&x);   //输入节点的值
    while(x!=9999){  //输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode)) //创建新结点
        s->data = x; 
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

双链表

双链表的初始化

//结点 double node
typedef struct DNode{   //定义双链表结点类型
    ElemType data;      //数据域
    struct DNode *prior, *next;    //前驱和后继指针
}DNode, *DLinkList;

//初始化双链表(带头结点)
bool InitDLinkList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DNode));   ///分配一个头结点
    if (L==NULL)
        return false;
    L->prior = NULL;    //头结点的prior永远指向NULL
    L->next = NULL;    //头结点之后暂时还没有结点
    return true;
}

双链表的插入

//在p结点之后插入s结点
bool InsertNextDNode(DNode *p,DNode *s){
    if (p==NULL || s==NULL)   //非法参数
        return false;
    s->next = p->next;
    if (p-next != NULL)  //如果p结点有后继结点
        p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}