2.线性表

2.线性表 2. 线性表

顺序表

一维数组可以是静态分配的,也可以是动态分配的.在静态分配时,由于数组的大小和空间事先已经固定,一旦空间沾满,再加入新的数据就会产生出溢出

//静态数组
#define MaxSize 50
typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;


//动态数组
#define InitSize 100;
typedef struct{
    ElemType *data;
    int MaxSize,length;
}SeqList;


//C原动态分配语句
L.data = (ElemType)malloc(sizeof(ElemType)*InitSize);

//C++动态分配语句
L.data = new Elemtype[InitSize];

链表

链表存储有单链表、双链表、循环链表、静态链表(借助数组实现),以下只举例单链表

基本结构

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

C语言的结构体:

• LNode为结构名,要是为了在结构体中包含自己为成员变量的时候有用
• typedef … LNode,*linkList; 中
  • LNode为struct LNode的别名
  • *linkList为**struct linkList*的别名

创建

//头插法建立单链表
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;
}

C语言小知识: 参数传递的三种方法

• 值传递：形参是实参的拷贝，改变形参的值并不会影响外部实参的值。从被调用函数的角度来说，值传递是单向的（实参->形参），参数的值只能传入，不能传出。当函数内部需要修改参数，并且不希望这个改变影响调用者时，采用值传递。
• 指针传递 &：形参为指向实参地址的指针，当对形参的指向 *** 作时，就相当于对实参本身进行的 *** 作
• 引用传递 *：形参相当于是实参的“别名”，对形参的 *** 作其实就是对实参的 *** 作，在引用传递过程中，被调函数的形式参数虽然也作为局部变量在栈中开辟了内存空间，但是这时存放的是由主调函数放进来的实参变量的地址。被调函数对形参的任何 *** 作都被处理成间接寻址，即通过栈中存放的地址访问主调函数中的实参变量。正因为如此，被调函数对形参做的任何 *** 作都影响了主调函数中的实参变量。

遍历查找

//按序号查找结点值 时间复杂度为O(n)
LNode *GetElem(linkList L,int i){
    int j=1;
    LNode *p=L->next;
    if(i==0)
        return 0;
    if(i<1)
        return NULL;
    while(p&&jnext;
        j++
    }
    return p;
}

//按值查找节点
LNode *LocateElem(linkList L,ElemType e){
    LNode *p=L->next;
    while(p!=Null&&p->data!=e)
        p=p->next;
    return p;
}

插入

//插入到指定节点后的代码片段
p=GetElem(L,i-1);
s->next=p->next;
p->next=s;

删除

//代码片段
p=GetElem(L,i-1);   //找到删除位置的前驱节点
q=p->next;
p->next=q->next;
free(q)

归并和拆分

• 归并: 一般是将两个有序的链表合并到一个新的有序的链表
• 拆分: 将一个链表逐一拆分,按次序依次放在两个信链表上

链表的应用

链表的优点如下：

链表能灵活地分配内存空间；能在 O(1) 时间内删除或者添加元素，前提是该元素的前一个元素已知，当然也取决于是单链表还是双链表，在双链表中，如果已知该元素的后一个元素，同样可以在 O(1) 时间内删除或者添加该元素。

链表的缺点是：

不像数组能通过下标迅速读取元素，每次都要从链表头开始一个一个读取；
查询第 k 个元素需要 O(k) 时间。

根据实际应用场景选择不同数据结构

参考

链表的优缺点
参数传递的三种方式
王道 数据结构