​ 线性表主要分为顺序存储的线性表和链式存储的链表。顺序表的特征就是地址连续的存储单元来存储线性表中的元素，即逻辑相邻的同时物理位置也相邻。类似一维数组。

​ 两种定义方式：静态分配与动态分配

1
2
3
4
5
#define MaxSize 50					//定义表长，静态分配长度写死
typedef struct {					
	ElemType data [MaxSize];		//元素
       int length;						//当前长度
   }SqList;							//类型
1
2
3
4
5
6
7
8
#define InitSize 100				//定义初始长度
typedef struct {
	ElemTyoe *data;					//动态分配数组的指针
       int MaxSize,Length;				//最大容量与当前个数
   }SeqList;

L.data=new ElemType[InitSize];		//初始分配语句（C++）
L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);//C语言中的动态分配

顺序表

声明：
1
2
3
4
//SqList L;
void InitList(SqList &L){			//静态分配
		L.length=0;						//初始长度为零
}
1
2
3
4
5
void InitList(SeqList &L){
		L.data=(ElemType *)malloc(sizeof(ElemType)*InitSize);
        L.length=0;
        L.MaxSize=InitSize;				//初始存储容量
}
插入操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool ListInsert(SqList &L,int i,ElemType e){	
    if (i < 1 || i > L.length + 1) {	// 判断插入位置是否合法
        return false;
    }
    if (L.length >= MAXSIZE) {			// 判断是否超出容量
        return false;
    }   
    for (int j = L.length ; j >= i ; j--) {// 将第 i-1 个位置及其之后的元素后移
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = e;					// 插入元素
    L.length++; 						// 表长加 1
    return true;
}

最好情况：在表位插入，时间复杂度为O(1)。

最坏情况：在表头插入，要移动n次元素，时间复杂度为O(n)

平均情况：直接求期望可得为n/2,时间复杂度为O(n)。

删除操作:
1
2
3
4
5
6
7
8
9
10
11
bool ListDelete(SqList &L, int i, ElemType &e) {    
    if (i < 1 || i > L.length) {		// 判断位置是否合法
        return false;
    }
    e = L.data[i - 1]; 					// 取出待删除元素
    for (int j = i; j < L.length; j++) {// 元素前移
        L.data[j - 1] = L.data[j];
    }
    L.length--; 						// 表长减 1
    return true;
}

最好情况：表头，O(1)

最坏情况：表尾/不存在，O(n)

平均情况：长度为n的表要删除第i个时，后移n-i个元素，求期望得（n-1）/ 2，时间复杂度为O(n)

按值查找（顺序查找）:
1
2
3
4
5
6
7
8
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.data[i] == e)
            return i + 1; 				// 返回逻辑位置
    }
    return 0; 							// 未找到
}

最好情况：表头，O(1)

最坏情况：表尾/不存在，O(n)

平均情况：(n+1)/2 ,时间复杂度为O(n)

链表

​ 单链表就是每个结点除了存放元素自身的信息之外还存了一个指向其后继的指针，这种结构可以用一组任意的存储单元来存储，而不要求逻辑上相邻的元素在物理上也相邻。进一步拓展为双链表，除了后继以外还有一个指针指向元素的前驱结点。

单链表的定义
1
2
3
4
5
6
typedef int ElemType;  // 定义元素类型

typedef struct LNode { // 定义单链表结点类型
    ElemType data;     // 数据域
    struct LNode *next; // 指针域，指向下一个结点
} LNode, *LinkList;    // LNode 表示结点类型，LinkList 表示指向结点的指针类型
单链表的初始化
1
2
3
4
5
6
bool InitList(LinkList *L) {
    *L = (LinkList)malloc(sizeof(LNode)); // 分配头结点空间
    if (!(*L)) return false;              // 分配失败
    (*L)->next = NULL;                    // 初始化为空表
    return true;
}

​ 这里要注意的是分为有头结点与无头节点两种情况

求表长
1
2
3
4
5
6
7
8
9
int ListLength(LinkList L) {
    int length = 0;
    LNode *p = L->next; // 从第一个数据结点开始
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}
按序号查找结点
1
2
3
4
5
6
7
8
9
LNode* GetElem(LinkList L, int i) {
    int j = 1;
    LNode *p = L->next;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return (j == i) ? p : NULL;
}
按值查找结点
1
2
3
4
5
6
7
LNode* LocateElem(LinkList L, ElemType e) {
    LNode *p = L->next;
    while (p && p->data != e) {
        p = p->next;
    }
    return p;
}
插入结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool ListInsert(LinkList L, int i, ElemType e) {
    int j = 0;
    LNode *p = L;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
删除结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool ListDelete(LinkList L, int i, ElemType *e) {
    int j = 0;
    LNode *p = L;
    while (p->next && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!(p->next)) return false;
    LNode *q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return true;
}
头插法建立单链表
1
2
3
4
5
6
7
8
9
10
void CreateListHead(LinkList *L, int n) {
    *L = (LinkList)malloc(sizeof(LNode));
    (*L)->next = NULL;
    for (int i = 0; i < n; i++) {
        LNode *p = (LNode *)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = (*L)->next;
        (*L)->next = p;
    }
}
尾插法建立单链表
1
2
3
4
5
6
7
8
9
10
11
12
void CreateListTail(LinkList *L, int n) {
    *L = (LinkList)malloc(sizeof(LNode));
    (*L)->next = NULL;
    LNode *r = *L;
    for (int i = 0; i < n; i++) {
        LNode *p = (LNode *)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = NULL;
        r->next = p;
        r = p;
    }
}