线性表

1. 对于同一个线性表，其每一个数据元素的值虽然不同，但必须具有相同的数据类型；
2.数据元素之间具有一种线性的或“一对一”的逻辑关系;

• 第一个数据元素没有前驱，这个数据元素被称为开始节点；
• 最后一个数据元素没有后继，这个数据元素被称为终端节点；
• 除了第一个和最后一个数据元素外，其他数据元素有且仅有一个前驱和一个后继。

线性表的顺序存储及实现

1. 逻辑上相邻的数据元素，在物理存储上也是相邻的
2. 随机存储

实现顺序表的结构体

#define INIT_SIZE 100 /*初始分配的存储空间长度*/
#define INCREM 3      /*存储空间再分配的增量*/
typedef int ElemType;
typedef struct Sqlist{
    ElemType *slist;
    int length;       /*顺序表当前长度*/
    int listsize;     /*当前分配的存储空间容量*/
}Sqlist;

初始化

int initSq(Sqlist *L)
{
    L->slist=(ElemType*)malloc(sizeof(ElemType)*INIT_SIZE);
    if(!L->slist) return 0; //初始化失败
    L->length=0;
    L->listsize=INIT_SIZE;  //设置初始空间容量 
    return 1;
}
主函数的调用：if(initSq(&sq)){...}//传地址进来

插入/创建

int insertSq(Sqlist *L, ElemType e, int i)
{   
    if(L->length>=L->listsize){//当前存储空间已满，申请空间增量
        L->slist=(ElemType*)realloc(L->slist,(INIT_SIZE+INCREM)*sizeof(ElemType));
        if(!L->slist) return 0;
        L->listsize+=INCREM;
    }
    for(int j=L->length-1;j>=i-1;j--)//将当前下标到结尾依次向后移动
        L->slist[j+1] = L->slist[j]; 
    L->slist[i-1]=e;
    L->length++;
    return 1;
}
主函数：for(int i=1;i<=n;i++)
        {
            scanf("%d",&e);
            insertSq(&sq,e,i);//传地址，i是位置
        }

查找

int searchSq(Sqlist *L, ElemType e)
{
    for(int i=0;i<L->length;i++)
        if(L->slist[i]==e) return i+1;
    return 0;
}

删除

int deleteSq(Sqlist *L,int i)
{
    if(i<1||i>L->length) return 0;
    for(int j=i;j<L->length;j++)
        L->slist[j-1]=L->slist[j];
    L->length--;
    return 1;
}

线性表链式存储及实现

1. 结点存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上也不一定是相邻的
2. 顺序存储（访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点

单链表(线性链表)：结点只有一个指针域的链表
双向链表：结点有两个指针域的链表(prior,next)
循环链表：首尾相连的链表

定义实现单链表的结构体

typedef  int ElemType;
typedef struct LNode
{
    ElemType data;      //数据域
    struct LNode *next; //指针域
}LNode,*LinkList;

初始化(带有头结点)

LinkList initList()
{
    LinkList head;
    head = (LNode*)malloc(sizeof(LNode));
    if(!head) return NULL;
    head->next = NULL;
    return head;
}
主函数调用：
    LinkList head;
    head=initList();

建立单链表(头插法/尾插法)

头插法：
void creatList(LinkList head,int n){
    LinkList p;
    for(int i=0;i<n;i++){
        p = (LNode*)malloc(sizeof(LNode));//添加一个新结点 
        scanf("%d",&e);//输入数据域 
        p->data = e;
        p->next = head->next;
        head->next = p;//从最后一个结点依次将各节点插入到链表前端 
    }
} 

尾插法：
void creatList(LinkList head,int n){
    LinkList p,r;
    r = head;//尾指针指向头结点
    for(int i=0;i<n;i++){
        p = (LNode*)malloc(sizeof(LNode));//添加一个新结点 
        scanf("%d",&e);//输入数据域 
        p->data = e;
        p->next = NULL;
        r->next = p;
        r = p;//指向新的尾结点 
    }
} 

插入

必须按照先 1 后 2 的顺序
如果①②顺序交换，此时的p->next已经被修改会导致错误
int insertList(LinkList head, int pos, ElemType e)
{
    LNode *p=head,*s;
    int fro=0;
    while(p&&fro<pos-1){//找到插入位置的前一个结点(因为要修改前一个结点的指针域)
        p = p->next;
        fro++;
    }
    if(!p||fro>pos-1) return 0; //插入位置大于表长+1 或 小于 1，都是不合法
    s = (LNode*)malloc(sizeof(LNode));//p指向i-1的结点
    if(!s) return 0;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 1;   
}

查找

int getIndex(LinkList head, ElemType e)
{   
    LinkList p = head->next;//p是首元结点
    int j=1;
    while(p && p->data!=e){
        j++;
        p = p->next;
    }
    if(p) return j;
    else return 0;
}

删除

int deleteList(LinkList head, int pos ,ElemType *e)
{

    LinkList p=head,q;
    int i=0;
    while(p->next&&i<pos-1){//
        p = p->next;
        i++;
    }
    if(!p->next||i>pos-1) return 0;
    q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
    return *e;

}

输出

void printList(LinkList head)
{
    LinkList p = head->next;
    while(p){
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");

}

实现单链表的逆序

void reverseList(LinkList head)
{
    LinkList p,r;
    p = head->next;//从第一个元素结点开始
    head->next = NULL;
    while(p!=NULL){//依次将元素结点摘下
        r = p->next;//暂存p的后继
        p->next = head->next;
        head->next = p;
        p = r;
    }

}

实现单链表删除重复元素

在一个按升序排列的链表
LinkList delRepeat(LinkList head){
    LinkList newHead = head;
    while(head->next){
        if(head->data == head->next->data)
            head->next = head->next->next;
        else{
            head = head->next; 
        }
    }
    return newHead;
}

双向链表的插入

得考虑到插入的位置如果是 n+1 的位置！
int insertList(LinkList head, int pos, ElemType e)
{   
    if(pos<1) return 0;
    LNode *p=head,*s;// 1 2 3 
    while(--pos){
        p = p->next;
        if(!p) return 0;
    }
    s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next =NULL;
    s->prior =NULL;
    if(!p->next){//判断是否在n+1的位置插入
        p->next = s;
        s->prior = p;
        return 1;
    }
    s->next = p->next;
    p->next->prior = s;
    p->next = s;
    s->prior = p; 
    return 1;    
}